Projects/PAKE Preauthentication - Revision history

TomYu: add early project template; bump heading levels

2015-03-17T20:19:37Z

add early project template; bump heading levels

Npmccallum at 19:42, 31 October 2014

2014-10-31T19:42:07Z

Npmccallum at 19:18, 31 October 2014

2014-10-31T19:18:23Z

Npmccallum: /* Rationale */

2014-10-31T17:42:55Z

‎Rationale

Npmccallum: Projects/PAKE 2FA moved to Projects/PAKE Preauthentication

2014-10-31T17:41:42Z

Projects/PAKE 2FA moved to Projects/PAKE Preauthentication

Npmccallum at 17:40, 31 October 2014

2014-10-31T17:40:25Z

Npmccallum: New page: = 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 ...

2014-10-31T17:33:45Z

New page: = 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 ...

New page

= 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.

= 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. We do not provide any sort of integrety on this message and as such a downgrade attack is possible. This behaves similarly to the etype negotiation.

=== Response (KrbError) ===
Upon receiving the AS-REQ message, the KDC will:
# Decide upon a client-supported PAKEProfile.
# Decide upon a client-supported etype with good security properties for the selected PAKEProfile.
# Decide which second factors are configured, required and/or need to present challenges.
# Generate the 2FInfo data structure, encode and hash it using the PAKEProfile specified hash.
# Select a secret key and derive it using the previously created 2FInfo hash.
# Construct the first PAKEProfile-specific PAKEMessage using the derived secret key.
# Construct the PAKEStart padata and return it to the client (KDC_ERR_PREAUTH_REQUIRED).

Because the secret is derived using a hash of the contents of 2FInfo, 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 for the etype.
# No downgrade attack is possible for the requirement of a 2FA.
# No downgrade attack is possible for the 2FA methods.
# If a 2FA method provides a challenge, it has integrety protection.

Upon receipt of the KrbError, the client:
# Prompts for the password and any second factor information required.
# Salts the password using ETYPE-INFO2-ENTRY.
# Hashes the encoded contents of 2FInfo.
# Derives the password using the above hash.

== 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:
# Calculates the shared key (K).
# Derives two new keys from the shared key (K): Kkconf, K2fa.
# Generates the key confirmation (PAKEProfile) hash: H(Kkconf).
# Encrypts any 2FA-specific response: E(K2fa, 2fa).
# Generates PAKEFinish with the last PAKE-specific message, the key confirmation and the 2fa message (optional).
# 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:
# Derives three new keys from K: Kkconf, K2fa, Ktgt.
# Verifies key confirmation: kconf == H(Kkconf).
# Decrypts and verifies the second factor (if present): verify(D(K2fa, 2fa)).
# If all factors validate, the TGT is sent in an AS-REP encrypted with Ktgt.

Special care should be taken by the KDC to avoid timing attacks if a second factor is present so as not to reveal to the client whether the first or second factor has failed. The second factor will often take several orders of magnitude more time than the first factor to validate.

With some 2FA methods, additional roundtrips may be required. It is strongly recommended that subsequent roundtrips only be initiated 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.

If subsequent roundtrips are required for 2FA, 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.

As noted above, the 2F should already be verified.

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

= 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 ==
[http://en.wikipedia.org/wiki/Password_Authenticated_Key_Exchange_by_Juggling 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.

== U2F ==
[https://fidoalliance.org/specifications/download 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.

= Implementation Details =
== Client Roundtrips ==
The MIT Kerberos client will likely require some core modification to handle the number of roundtrips required by this protocol.

== KDC State ==
The KDC is generally stateless. Some mechanism will be needed to carry state across the roundtrips. Using PA-FX-COOKIE is probably the simplist. However, this will also likely break forward secrecy. Careful thought will be required for the implementation.

= Proposed ASN.1 =

<code>
<pre>
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)
</pre>
</code>

@@ Line 29: / Line 29: @@
 # Decide upon a client-supported etype with good security properties for the selected PAKEProfile.
 # Decide which second factors are configured, required and/or need to present challenges.
-# Generate the 2FInfo data structure, encode and hash it using the PAKEProfile specified hash.
+# Generate the 2FInfo data structure, encode and hash it using the PAKEProfile specified hash: h<sub>2finfo</sub> = H(2FInfo).
-# Select a secret key and derive it using the previously created 2FInfo hash.
+# Construct the first PAKEProfile-specific PAKEMessage using the principal's secret key.
 # Construct the PAKEStart padata and return it to the client (KDC_ERR_PREAUTH_REQUIRED).
 Upon receipt of the KrbError, the client:
 # Prompts for the password and any second factor information required.
 # Salts the password using ETYPE-INFO2-ENTRY.
-# Hashes the encoded contents of 2FInfo.
+# Hashes the encoded contents of 2FInfo: h<sub>2finfo</sub> = H(2FInfo).
 == Intermediate PAKE Roundtrips (Optional) ==
@@ Line 56: / Line 50: @@
 # Calculates the shared key (K).
 # Derives two new keys from the shared key (K): K<sub>kconf</sub>, K<sub>2fa</sub>.
-# Generates the key confirmation (PAKEProfile) hash: H(K<sub>kconf</sub>).
+# Generates the key confirmation (PAKEProfile) hash: H(K<sub>kconf</sub>, h<sub>2finfo</sub>).
 # Encrypts any 2FA-specific response: E(K<sub>2fa</sub>, 2fa).
 # Generates PAKEFinish with the last PAKE-specific message, the key confirmation and the 2fa message (optional).
@@ Line 64: / Line 58: @@
 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:
 # Derives three new keys from K: K<sub>kconf</sub>, K<sub>2fa</sub>, K<sub>tgt</sub>.
-# Verifies key confirmation: kconf == H(K<sub>kconf</sub>).
+# Verifies key confirmation: kconf == H(K<sub>kconf</sub>, h<sub>2finfo</sub>).
 # Decrypts and verifies the second factor (if present): verify(D(K<sub>2fa</sub>, 2fa)).
 # If all factors validate, the TGT is sent in an AS-REP encrypted with K<sub>tgt</sub>.
 Special care should be taken by the KDC to avoid timing attacks if a second factor is present so as not to reveal to the client whether the first or second factor has failed. The second factor will often take several orders of magnitude more time than the first factor to validate.

← Older revision		Revision as of 17:42, 31 October 2014
Line 6:		Line 6:

	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.		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 =		= Protocol Overview =

@@ Line 1: / Line 1: @@
 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.
@@ Line 9: / Line 11: @@
 PAKE preauthentication also has benefits when not using a second factor. Namely, both sides are authenticated and no time synchronization is required.
-= Protocol Overview =
+== 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 ==
+=== First Roundtrip ===
-=== Request (AS-REQ) ===
+==== 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) ===
+==== Response (KrbError) ====
 Upon receiving the AS-REQ message, the KDC will:
 # Choose a client-supported PAKEProfile.
@@ Line 31: / Line 33: @@
 # Hashes the encoded contents of 2FInfo: h<sub>2finfo</sub> = H(2FInfo).
-== Intermediate PAKE Roundtrips (Optional) ==
+=== 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 ==
+=== Last PAKE Roundtrip ===
-=== Request (AS-REQ) ===
+==== 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.
@@ Line 48: / Line 50: @@
 # Sends AS-REQ with PA-PAKE as PAKEFinish.
-=== Response (AS-REP or KrbError) ===
+==== 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:
 # Derives three new keys from K: K<sub>kconf</sub>, K<sub>2fa</sub>, K<sub>tgt</sub>.
@@ Line 57: / Line 59: @@
 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 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.
@@ Line 65: / Line 67: @@
 The conclusion of all subsequent 2F rountrips MUST be either an AS-REP or a final KrbError.
-= Security Considerations =
+== 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.
@@ Line 81: / Line 83: @@
 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 =
+== 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 ===
 [http://en.wikipedia.org/wiki/Password_Authenticated_Key_Exchange_by_Juggling 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 =
+== 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) ==
+=== 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 ==
+=== FIDO Alliance - U2F ===
 [https://fidoalliance.org/specifications/download 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 =
+== Proposed ASN.1 ==
 <code>

← Older revision	Revision as of 17:41, 31 October 2014
(No difference)