RFC 9588: Kerberos Simple Password-Authenticated Key Exchange (SPAKE) Pre-authentication

1.1. Properties of PAKE

Password-authenticated key exchange (PAKE) algorithms [RFC8125] provide several properties that defend against offline dictionary attacks and make them ideal for use in a Kerberos pre-authentication mechanism.¶

These properties of PAKE allow us to establish high-entropy encryption keys resistant to offline brute-force attacks, even when the passwords used are weak (low entropy).¶

1.2. PAKE Algorithm Selection

The SPAKE algorithm (defined in [SPAKE]) works by encrypting the public keys of a Diffie-Hellman (DH) key exchange with a shared secret. SPAKE is selected for this pre-authentication mechanism for the following properties:¶

1.3. PAKE and Two-Factor Authentication

Using PAKE in a pre-authentication mechanism also has another benefit when used as a component of two-factor authentication (2FA). 2FA methods often require the secure transfer of plaintext material to the KDC for verification. This includes one-time passwords, challenge/response signatures, and biometric data. Encrypting this data using the long-term secret results in packets that are vulnerable to offline brute-force attacks on the password, using either an authentication tag or statistical properties of the 2FA credentials to determine whether a password guess is correct.¶

In "One-Time Password (OTP) Pre-Authentication" [RFC6560], this problem is mitigated using flexible authentication secure tunneling (FAST) (Section 5.4 of [RFC6113]), which uses a secondary trust relationship to create a secure encryption channel within which pre-authentication data can be sent. However, the requirement for a secondary trust relationship has proven to be cumbersome to deploy and often introduces third parties into the trust chain (such as certification authorities). These requirements make it difficult to enable FAST without manual configuration of client hosts. In contrast, SPAKE pre-authentication, can create a secure encryption channel implicitly, using the key exchange to negotiate a high-entropy encryption key. This key can then be used to securely encrypt 2FA plaintext data without the need for a secondary trust relationship. Further, if the second-factor verifiers are sent at the same time as the first-factor verifier, and the KDC is careful to prevent timing attacks, then an online brute-force attack cannot be used to attack the factors separately.¶

For these reasons, this document departs from the advice given in Section 1 of [RFC6113], which states: "Mechanism designers should design FAST factors, instead of new pre-authentication mechanisms outside of FAST." However, the SPAKE pre-authentication mechanism does not intend to replace FAST and may be used with it to further conceal the metadata of the Kerberos messages.¶

1.4. SPAKE Overview

The SPAKE algorithm can be broadly described in a series of four steps:¶

In this mechanism, key verification happens implicitly by a successful decryption of the 2FA data or of a placeholder value when no second factor is required. This mechanism uses a tailored method of deriving encryption keys from the calculated shared secret K, for several reasons:¶

3.1. PA-ETYPE-INFO2

This mechanism requires the initial KDC pre-authentication state to contain a singular reply key. Therefore, a KDC that offers SPAKE pre-authentication as a stand-alone mechanism MUST supply a PA-ETYPE-INFO2 value containing a single ETYPE-INFO2-ENTRY, following the guidance in Section 2.1 of [RFC6113]. PA-ETYPE-INFO2 is specified in Section 5.2.7.5 of [RFC4120].¶

3.2. Cookie Support

KDCs that implement SPAKE pre-authentication MUST have some secure mechanism for retaining state between authentication service requests (AS-REQs). For stateless KDC implementations, this method will most commonly be an encrypted PA-FX-COOKIE. Clients that implement SPAKE pre-authentication MUST support PA-FX-COOKIE, as described in Section 5.2 of [RFC6113].¶

3.3. More Pre-authentication Data Required

Both KDCs and clients that implement SPAKE pre-authentication MUST support the use of KDC_ERR_MORE_PREAUTH_DATA_REQUIRED, as described in Section 5.2 of [RFC6113].¶

4.1. First Pass

The SPAKE pre-authentication exchange begins when the client sends an initial authentication service request (AS-REQ) without pre-authentication data. Upon receipt of this AS-REQ, a KDC that requires pre-authentication and supports SPAKE SHOULD (unless configuration indicates otherwise) reply with a KDC_ERR_PREAUTH_REQUIRED error, with METHOD-DATA containing an empty PA-SPAKE PA-DATA element (possibly in addition to other PA-DATA elements). This message indicates to the client that the KDC supports SPAKE pre-authentication.¶

4.2. Second Pass

Once the client knows that the KDC supports SPAKE pre-authentication and the client wants to use it, the client will generate a new AS-REQ message containing a PA-SPAKE PA-DATA element using the support choice. This message indicates to the KDC which groups the client prefers for the SPAKE operation. The group numbers are defined in the "Kerberos SPAKE Groups" registry (see Section 12.2). The group's sequence is ordered from the most preferred group to the least preferred group.¶

SPAKESupport ::= SEQUENCE {
    groups      [0] SEQUENCE (SIZE(1..MAX)) OF Int32,
    ...
}

Upon receipt of the support message, the KDC will select a group. The KDC SHOULD choose a group from the groups provided by the support message. However, if the support message does not contain any group that is supported by the KDC, the KDC MAY select another group in hopes that the client might support it. Otherwise, the KDC MUST respond with a KDC_ERR_PREAUTH_FAILED error.¶

The group selection determines the group order, which shall be a large prime p multiplied by a small cofactor h (possibly 1), a generator P of a prime-order subgroup, and two masking points M and N. The KDC selects a random integer x in the range 0 <= x < h*p, which MUST be divisible by h. The KDC computes a public key T=x*P+w*M, where w is computed from the initial reply key according to Section 5.¶

The KDC will reply to the client with a KDC_ERR_MORE_PREAUTH_DATA_REQUIRED error containing a PA-SPAKE PA-DATA element using the challenge choice.¶

SPAKEChallenge ::= SEQUENCE {
    group       [0] Int32,
    pubkey      [1] OCTET STRING,
    factors     [2] SEQUENCE (SIZE(1..MAX)) OF SPAKESecondFactor,
    ...
}

The group field indicates the KDC-selected group used for all SPAKE calculations as defined in the "Kerberos SPAKE Groups" registry (see Section 12.2).¶

The pubkey field indicates the KDC's public key T, serialized according to Section 5.¶

The factors field contains an unordered list of second factors, which can be used to complete the authentication. Each second factor is represented by a SPAKESecondFactor.¶

SPAKESecondFactor ::= SEQUENCE {
    type        [0] Int32,
    data        [1] OCTET STRING OPTIONAL
}

The type field is a unique integer that identifies the second-factor type. The factors field of SPAKEChallenge MUST NOT contain more than one SPAKESecondFactor with the same type value.¶

The data field contains optional challenge data. The contents in this field will depend upon the second-factor type chosen. Note that this challenge is initially transmitted as unauthenticated plaintext; see Section 10.2.¶

The client and KDC will each initialize a transcript hash (Section 6) using the hash function associated with the chosen group and update it with the concatenation of the DER-encoded PA-SPAKE messages sent by the client and the KDC.¶

4.3. Third Pass

Upon receipt of the challenge message, the client observes which group was selected by the KDC and deserializes the KDC's public key T. The client selects a random integer y in the range 0 <= x < h*p, which MUST be divisible by h. The client computes a public key S=y*P+w*N, where w is computed from the initial reply key according to Section 5. The client computes a shared group element K=y*(T-w*M).¶

The client will then choose one of the second-factor types listed in the factors field of the challenge message and gather whatever data is required for the chosen second-factor type, possibly using the associated challenge data. Finally, the client will send an AS-REQ containing a PA-SPAKE PA-DATA element using the response choice.¶

SPAKEResponse ::= SEQUENCE {
    pubkey      [0] OCTET STRING,
    factor      [1] EncryptedData, -- SPAKESecondFactor
    ...
}

The client and KDC will update the transcript hash with the pubkey value and use the resulting hash for all encryption key derivations.¶

The pubkey field indicates the client's public key S, serialized according to Section 5.¶

The factor field indicates the client's chosen second-factor data. The key for this field is K'[1] (specified in Section 7). The kvno field of the EncryptedData sequence is omitted. The key usage number for the encryption is KEY_USAGE_SPAKE. The plaintext inside the EncryptedData is an encoding of the SPAKESecondFactor. Once decoded, the SPAKESecondFactor provides the type of the second factor and any optional data used. The contents of the data field will depend on the second-factor type chosen. The client MUST NOT send a response containing a second-factor type that was not listed in the factors field of the challenge message.¶

When the KDC receives the response message from the client, it deserializes the client's public key S, and computes the shared group element K=x*(S-w*N). The KDC derives K'[1] and decrypts the factors field. If decryption is successful, the first factor is successfully validated. The KDC then validates the second factor. If either factor fails to validate, the KDC MUST respond with a KDC_ERR_PREAUTH_FAILED error.¶

If validation of the second factor requires further round trips, the KDC MUST reply to the client with a KDC_ERR_MORE_PREAUTH_DATA_REQUIRED error containing a PA-SPAKE PA-DATA element using the encdata choice. The kvno field of the EncryptedData sequence is omitted. The key for the EncryptedData value is K'[2] (specified in Section 7), and the key usage number is KEY_USAGE_SPAKE. The plaintext of this message contains a DER-encoded SPAKESecondFactor message. As before, the type field of this message will contain the second-factor type and the data field will, optionally, contain data specific to the second-factor type.¶

4.4. Subsequent Passes

Any number of additional round trips may occur using the encdata choice. The contents of the plaintexts are specific to the second-factor type. If a client receives a PA-SPAKE PA-DATA element using the encdata choice from the KDC, it MUST reply with a subsequent AS-REQ with a PA-SPAKE PA-DATA element using the encdata choice or abort the AS exchange.¶

The key for client-originated encdata messages in subsequent passes is K'[3] (specified in Section 7) for the first subsequent pass, K'[5] for the second, and so on. The key for KDC-originated encdata messages is K'[4] for the first subsequent pass, K'[6] for the second, and so on.¶

4.5. Reply Key Strengthening

When the KDC has successfully validated both factors, the reply key is strengthened and the mechanism is complete. The strengthening of the reply key is accomplished by the client and KDC replacing it with K'[0] (as specified in Section 7). The KDC then replies with a KDC-REP message or continues on to the next mechanism in the authentication set. There is no final PA-SPAKE PA-DATA message from the KDC to the client.¶

Reply key strengthening occurs only once: at the end of the exchange. The client and KDC MUST use the initial reply key as the base key for all K'[n] derivations.¶

10.1. SPAKE Computations

The deserialized public keys S and T MUST be verified to be elements of the group to prevent invalid curve attacks. It is not necessary to verify that they are members of the prime-order subgroup; the computation of K by both parties involves a multiplication by the cofactor h.¶

The aforementioned cofactor multiplication is accomplished by choosing private scalars x and y, which are divisible by the cofactor. If the client or KDC chooses a scalar that might not be divisible by the cofactor, an attacker might be able to coerce values of K that are not members of the prime-order subgroup and deduce a limited amount of information about w from the order of K.¶

The scalars x and y MUST be chosen uniformly. They MUST NOT be reused for different initial reply keys. If an x or y value is reused for pre-authentications involving two different initial reply keys, an attacker who observes both authentications and knows one of the initial reply keys can conduct an offline dictionary attack to recover the other one.¶

The M and N values for a group MUST NOT have known discrete logs. An attacker who knows the discrete log of M or N can perform an offline dictionary attack on passwords. Therefore, it is important to demonstrate that the M and N values for each group were computed without multiplying a known value by the generator P.¶

10.3. Side Channels

An implementation of the SPAKE pre-authentication mechanism can have the property of indistinguishability, meaning that an attacker who guesses a long-term key and a second-factor value cannot determine whether one of the factors was correct unless both are correct. Indistinguishability is only maintained if the second factor can be validated solely based on the data in the response; the use of additional round trips will reveal to the attacker whether the long-term key is correct. Indistinguishability also requires that there are no side channels. When the KDC processes a response message, whether or not it decrypts the factor field, it must reply with the same error fields, take the same amount of time, and make the same observable communications to other servers.¶

Both the size of the EncryptedData and the number of EncryptedData messages used for second-factor data (including the factor field of the SPAKEResponse message and messages using the encdata PA-SPAKE choice) may reveal information about the second factor used in an authentication. Care should be taken to keep second-factor messages as small and as few as possible.¶

Any side channels in the creation of the shared secret input w, or in the multiplications wM and wN, could allow an attacker to recover the client long-term key. Implementations MUST take care to avoid side channels, particularly timing channels. Generation of the secret scalar values x and y need not take constant time, but the amount of time taken MUST NOT provide information about the resulting value.¶

The conversion of the scalar multiplier for the SPAKE w parameter may produce a multiplier that is larger than the order of the group. Some group implementations may be unable to handle such a multiplier. Others may silently accept such a multiplier but proceed to perform multiplication that is not constant time. This is only a minor risk in most commonly used groups, but it is a more serious risk for P-521 due to the extra seven high bits in the input octet string. A common solution to this problem is achieved by reducing the multiplier modulo the group order, taking care to ensure constant time operation.¶

10.5. Dictionary Attacks

Although the SPAKE pre-authentication mechanism is designed to prevent an offline dictionary attack by an active attacker posing as the KDC, such an attacker can attempt to downgrade the client to the encrypted timestamp pre-authentication mechanism. Client implementations SHOULD provide a configuration option to enable or disable the encrypted timestamp mechanism on a per-realm basis to mitigate this attack.¶

If the user enters the wrong password, the client might fall back to the encrypted timestamp mechanism after receiving a KDC_ERR_PREAUTH_FAILED error from the KDC, if the encrypted timestamp mechanism is offered by the KDC and not disabled by client configuration. This fallback will enable a passive attacker to mount an offline dictionary attack against the incorrect password, which may be similar to the correct password. Client implementations SHOULD assume that the encrypted timestamp and encrypted challenge mechanisms are unlikely to succeed if SPAKE pre-authentication fails in the second pass and SF-NONE was used.¶

Like any other pre-authentication mechanism using the client long-term key, the SPAKE pre-authentication mechanism does not prevent online password guessing attacks. The KDC is made aware of unsuccessful guesses and can apply facilities such as rate limiting to mitigate the risk of online attacks.¶

10.6. Brute-Force Attacks

The selected group's resistance to offline brute-force attacks may not correspond to the size of the reply key. For performance reasons, a KDC MAY select a group whose brute-force work factor is less than the reply key length. A passive attacker who solves the group discrete logarithm problem after the exchange will be able to conduct an offline attack against the client long-term key. Although the use of password policies and costly, salted string-to-key functions may increase the cost of such an attack, the resulting cost will likely not be higher than the cost of solving the group discrete logarithm.¶

10.7. Denial-of-Service Attacks

Elliptic curve group operations are more computationally expensive than secret-key operations. As a result, the use of this mechanism may affect the KDC's performance under normal load and its resistance to denial-of-service attacks.¶

10.8. Reflection Attacks

The encdata choice of PA-SPAKE can be used in either direction; the factor-specific plaintext does not necessarily indicate a direction. However, each encdata message is encrypted using a derived key K'[n], with client-originated messages using only odd values of n and KDC-originated messages using only even values. Therefore, an attempted reflection attack would result in a failed decryption.¶

10.9. Reply Key Encryption Type

This mechanism does not upgrade the encryption type of the initial reply key and relies on that encryption type for confidentiality, integrity, and pseudorandom functions. If the client long-term key uses a weak encryption type, an attacker might be able to subvert the exchange, and the replaced reply key will also be of the same weak encryption type.¶

10.10. KDC Authentication

This mechanism does not directly provide the KDC Authentication pre-authentication facility because it does not send a key confirmation from the KDC to the client. When used as a stand-alone mechanism, the preexisting KDC authentication provided by the KDC-REP enc-part still applies.¶

13.1. Normative References

[ITU-T.X680.2021]

ITU-T, "Information technology - Abstract Syntax Notation One (ASN.1): Specification of basic notation", ITU-T Recommendation X.680, ISO/IEC 8824-1:2021, February 2021.

[ITU-T.X690.2021]

ITU-T, "Information technology - ASN.1 encoding rules: Specification of Basic Encoding Rules (BER), Canonical Encoding Rules (CER) and Distinguished Encoding Rules (DER)", ITU-T Recommendation X.690, ISO/IEC 8825-1:2021, February 2021.

[RFC2119]

Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, DOI 10.17487/RFC2119, March 1997, <https://www.rfc-editor.org/info/rfc2119>.

[RFC3961]

Raeburn, K., "Encryption and Checksum Specifications for Kerberos 5", RFC 3961, DOI 10.17487/RFC3961, February 2005, <https://www.rfc-editor.org/info/rfc3961>.

[RFC4120]

Neuman, C., Yu, T., Hartman, S., and K. Raeburn, "The Kerberos Network Authentication Service (V5)", RFC 4120, DOI 10.17487/RFC4120, July 2005, <https://www.rfc-editor.org/info/rfc4120>.

[RFC6113]

Hartman, S. and L. Zhu, "A Generalized Framework for Kerberos Pre-Authentication", RFC 6113, DOI 10.17487/RFC6113, April 2011, <https://www.rfc-editor.org/info/rfc6113>.

[RFC6234]

Eastlake 3rd, D. and T. Hansen, "US Secure Hash Algorithms (SHA and SHA-based HMAC and HKDF)", RFC 6234, DOI 10.17487/RFC6234, May 2011, <https://www.rfc-editor.org/info/rfc6234>.

[RFC7748]

Langley, A., Hamburg, M., and S. Turner, "Elliptic Curves for Security", RFC 7748, DOI 10.17487/RFC7748, January 2016, <https://www.rfc-editor.org/info/rfc7748>.

[RFC8032]

Josefsson, S. and I. Liusvaara, "Edwards-Curve Digital Signature Algorithm (EdDSA)", RFC 8032, DOI 10.17487/RFC8032, January 2017, <https://www.rfc-editor.org/info/rfc8032>.

[RFC8126]

Cotton, M., Leiba, B., and T. Narten, "Guidelines for Writing an IANA Considerations Section in RFCs", BCP 26, RFC 8126, DOI 10.17487/RFC8126, June 2017, <https://www.rfc-editor.org/info/rfc8126>.

[RFC8174]

Leiba, B., "Ambiguity of Uppercase vs Lowercase in RFC 2119 Key Words", BCP 14, RFC 8174, DOI 10.17487/RFC8174, May 2017, <https://www.rfc-editor.org/info/rfc8174>.

[SEC1]

Standards for Efficient Cryptography Group, "SEC 1: Elliptic Curve Cryptography", May 2009.

[SEC2]

Standards for Efficient Cryptography Group, "SEC 2: Recommended Elliptic Curve Domain Parameters", January 2010.

13.2. Informative References

[RFC6090]

McGrew, D., Igoe, K., and M. Salter, "Fundamental Elliptic Curve Cryptography Algorithms", RFC 6090, DOI 10.17487/RFC6090, February 2011, <https://www.rfc-editor.org/info/rfc6090>.

[RFC6560]

Richards, G., "One-Time Password (OTP) Pre-Authentication", RFC 6560, DOI 10.17487/RFC6560, April 2012, <https://www.rfc-editor.org/info/rfc6560>.

[RFC8125]

Schmidt, J., "Requirements for Password-Authenticated Key Agreement (PAKE) Schemes", RFC 8125, DOI 10.17487/RFC8125, April 2017, <https://www.rfc-editor.org/info/rfc8125>.

[SPAKE]

Abdalla, M. and D. Pointcheval, "Simple Password-Based Encrypted Key Exchange Protocols", CT-RSA 2005, Lecture Notes in Computer Science, Volume 3376, pages 191-208, Springer, DOI 10.1007/978-3-540-30574-3_14, February 2005, <https://doi.org/10.1007/978-3-540-30574-3_14>.