Projects/PAKE Preauthentication

This is an early stage project for MIT Kerberos. It is being fleshed out by its proponents. Feel free to help flesh out the details of this project. After the project is ready, it will be presented for review and approval.

Rationale

Multi-factor authentication is a highly desired feature. This lead first to the creation of an OTP preauthentication mechanism (RFC 6560). This mechanism sends the OTP over the wire, but encrypted inside of FAST.

While this works, it is somewhat less than optimal. FAST can be difficult for clients to configure. This lead to some initial thoughts regarding the question of OTP Deployability (Projects/Improve OTP deployability).

The best idea to come out of this discussion was to use the first factor to complete a PAKE exchange and then use the exchanged key to encrypt the second factor. So long as only a single round-trip is used to complete the second factor validation, it is possible to evaluate the first and second factors simultaneously. Even when such may not be possible, account locking policy (or some other mechanism) can be used to prevent online dictionary attacks.

PAKE preauthentication also has benefits when not using a second factor. Namely, both sides are authenticated and no time synchronization is required.

Protocol Overview

This preauthentication mechanism differs a bit from establish mechanisms in that it takes an arbitrary number of roundtrips to complete. This varies based upon the PAKE algorithm and the second factor used (if any). At a minimum, two roundtrips are necessary. This is made possible by using KDC_ERR_MORE_PREAUTH_DATA_REQUIRED.

First Roundtrip

Request (AS-REQ)

In the first roundtrip, the client MUST include PA-PAKE padata of PAKESupport. This indicates to the KDC which PAKE methods are supported by the client.

Response (KrbError)

Upon receiving the AS-REQ message, the KDC will:

1. Choose a client-supported PAKEProfile.
2. Choose a client-supported etype with good security properties for the selected PAKEProfile.
3. Choose which second factors are configured, required and/or need to present challenges.
4. Generate the 2FInfo data structure, encode and hash it using the PAKEProfile specified hash: h_2finfo = H(2FInfo).
5. Construct the first PAKEProfile-specific PAKEMessage using the principal's secret key.
6. Construct the PAKEStart padata and return it to the client (KDC_ERR_PREAUTH_REQUIRED).

Upon receipt of the KrbError, the client:

1. Prompts for the password and any second factor information required.
2. Salts the password using ETYPE-INFO2-ENTRY.
3. Hashes the encoded contents of 2FInfo: h_2finfo = H(2FInfo).

Intermediate PAKE Roundtrips (Optional)

Depending on the PAKEProfile chosen, additional roundtrips may be required to complete the key exchange. This includes subsequent AS-REQs and KrbError(KDC_ERR_MORE_PREAUTH_DATA_REQUIRED) responses. These contain PA-PAKE padata of PAKEMessage. The number of intermediate roundtrips here is PAKEProfile specific and may be zero or more. However, the PAKE algorithm in any given PAKEProfile MUST be symmetric.

Last PAKE Roundtrip

Request (AS-REQ)

After any intermediate PAKE roundtrips are completed, the client is on the last step of the (symmetric) PAKE. The client should have, at this point:

• The KDC's public key.
• The 2FA response (optional).

The client then:

1. Calculates the shared key (K).
2. Derives two new keys from the shared key (K): K_kconf, K_2fa.
3. Generates the key confirmation (PAKEProfile) hash: H(K_kconf, h_2finfo).
4. Encrypts any 2FA-specific response: E(K_2fa, 2fa).
5. Generates PAKEFinish with the last PAKE-specific message, the key confirmation and the 2fa message (optional).
6. Sends AS-REQ with PA-PAKE as PAKEFinish.

Response (AS-REP or KrbError)

At this point the KDC, in most cases, will have everything it needs to complete verification. It uses the final PAKEMessage in PAKEFinish to calculate the shared key (K). This will be the same as the client's K if and only if the password, salt and 2FInfo hash are the same. The KDC now:

1. Derives three new keys from K: K_kconf, K_2fa, K_tgt.
2. Verifies key confirmation: kconf == H(K_kconf, h_2finfo).
3. Decrypts and verifies the second factor (if present): verify(D(K_2fa, 2fa)).
4. If all factors validate, the TGT is sent in an AS-REP encrypted with K_tgt.

With some 2FA methods, additional roundtrips may be required. In this case, the KDC MUST return KrbError(KDC_ERR_MORE_PREAUTH_DATA_REQUIRED) with PA-PAKE of PAKESecondFactor.

Subsequent 2F Roundtrips (Optional)

Subsequent roundtrips may be required for 2FA. This includes subsequent AS-REQs and KrbError(KDC_ERR_MORE_PREAUTH_DATA_REQUIRED) responses. These contain PA-PAKE padata of PAKESecondFactor.

An example of a subsequent 2F roundtrip is OTP synchronization after the first code has already been verified.

The conclusion of all subsequent 2F rountrips MUST be either an AS-REP or a final KrbError.

Security Considerations

Presuming that the underlying PAKE is secure, the shared key should be secure and no details about the first factor should be available to an active or passive attacker.

We do not provide any sort of integrity for the PAKESupport message and as such a downgrade attack is possible. This behaves similarly to the etype negotiation. The client and KDC should disable any weak PAKEProfile.

Because the hash of 2FInfo appears in the key confirmation, several important properties arise. If an active attacker tampers with the contents of 2FInfo, the key exchange will fail to verify. This guarantees:

• No downgrade attack is possible on the KDC's:
  • etype choice
  • 2FA requirement
  • 2FA methods
• If a 2FA method provides a challenge, it has integrety protection.

Timing attacks are a clear concern. The KDC needs to ensure that the same amount of time is spent no matter which factor fails to validate.

Similarly, if subsequent 2FA roundtrips are required, they should be initiated only after the 2FA has already been verified. A failure to do this opens up the system to an independant online dictionary attack on the first factor. However, if this is not possible, this may be mitigated by an account locking policy. But again, this can be simply avoided by validating the 2F without subsequent roundtrips.

Proposed PAKEs

A brief note is necessary about elliptic curve cryptogrpahy (ECC). The standard integer Diffie-Hellman is rapidly becoming cumbersome. ECC provides an answer for this. PAKEProfile is flexible enough to support non-ECC based PAKEs, but at this time we are only focusing on implementing ECC PAKEs.

JPAKE

JPAKE is a PAKE algorithm with a formal security proof. It is compatible with ECC without fancy tricks. It is broadly implemented (including OpenSSL, NSS and BouncyCastle). There are no known patents covering it. The only major downside of using it is that it requires two roundtrips.

Proposed 2FA Methods

Given that 2FA methods are expandable in this protocol, it is preferred that each type of 2FA create its own method. This will void having to create a 2FA method "to rule them all" and failing.

OATH (HOTP, TOTP, OCRA)

HOTP (RFC 4226) and TOTP (RFC 6238) make great options for this protocol. A (very) simple example implementation is provided. OCRA (RFC 6287) support would be ideal as well; but more research is needed for this.

FIDO Alliance - U2F

U2F is the new cryptographic hardware challenge/response based on USB / Bluetooth HID. It is a clever design and provides great usability. More research is needed.

Proposed ASN.1

KerberosPAKE DEFINITIONS EXPLICIT TAGS ::= BEGIN

IMPORTS
    EncryptedData, Int32
        FROM KerberosV5Spec2 {
            iso(1) identified-organization(3)
            dod(6) internet(1) security(5) kerberosV5(2)
            modules(4) krb5spec2(2)
        }; -- as defined in RFC 4120.

--
--- Preauthentication Data
--
PA-PAKE ::= 150

PAKEPreauthenticationData ::= CHOICE {
  PAKESupport,
  PAKEStart,
  PAKEMessage,
  PAKEFinish,
  PAKESecondFactor
}

--
--- Key Exchange
--
PAKEProfile ::= ENUMERATED {
  jpake-p256-schnorr-sha256 (0)
  jpake-p521-schnorr-sha256 (1)
}

PAKESupport ::= [APPLICATION 1] SEQUENCE OF PAKEProfile

PAKEStart ::= [APPLICATION 2] SEQUENCE {
  message [0] PAKEMessage,
  2fa     [1] 2FInfo
}

PAKEMessage ::= [APPLICATION 3] SEQUENCE {
  profile [0] PAKEProfile,
  message [1] OCTET STRING
}

PAKEFinish ::= [APPLICATION 4] SEQUENCE {
  message [0] PAKEMessage,
  keyconf [1] OCTET STRING,
  2fa     [2] PAKESecondFactor OPTIONAL
}

PAKESecondFactor ::= [APPLICATION 5] SEQUENCE {
  type    [0] 2FType,
  message [1] EncryptedData
}

--
--- Second Factor
--
2FType ::= ENUMERATED {
  oath (0)
}

2FSupport ::= SEQUENCE {
  type      [0] PAKE2FType,
  challenge [1] OCTET STRING OPTIONAL -- Encoded, type-specific
}

2FInfo ::= SEQUENCE {
  etype     [0] Int32,   -- The etype used to encrypt the 2F
  required  [1] BOOLEAN, -- If required is TRUE, there MUST be one supported 2F
  supported [2] SEQUENCE OF 2FSupport OPTIONAL
}

--
--- JPAKE
--
SchnorrVerifiedKey ::= SEQUENCE {
  key [0] BIT STRING,
  gx  [1] BIT STRING,
  r   [2] BIT STRING
}

JPAKEFirstPass ::= [CONTEXT 1] SEQUENCE {
  x [1] SchnorrVerifiedKey,
  y [1] SchnorrVerifiedKey
}

JPAKESecondPass ::= [CONTEXT 2] SchnorrVerifiedKey

-- A note on how OATH works:
--   * No challenge is sent.
--   * The first 2FMessage is 2FOATHCode
--   * If synchronization is required, the second 2FMessage is 2FOATHSync
--   * The reply is the next 2FOATHCode
2FOATHCode ::= IA5String
2FOATHSync ::= BOOLEAN (TRUE)