Projects/SPAKE Preauthentication
This project will implement SPAKE pre-authentication as specified by draft-mccallum-kitten-krb-spake-preauth. The mechanism will be off by default for one release, and then can hopefully be turned on by default in the following release.
Very briefly, the SPAKE pre-authentication mechanism works as follows:
- The KDC provides an empty hint with the initial PREAUTH_REQUIRED error.
- The client sends a support message indicating which groups it permits.
- The KDC sends a challenge containing T=xG+wM, where x is a randomly chosen scalar value, G is the group's generator, w is a scalar value derived from the initial reply key, and M is a constant element of the group. The challenge also contains one or more second-factor challenges, which may include a trivial challenge for the type SF-NONE if using no second factor is permitted.
- The client sends a response containing S=yG+wN, where y is a randomly chosen scalar and N is a different constant element of the group. The challenge also contains an encrypted second-factor response.
- The client and KDC can derive keys K'[n] from the initial reply key, K=y(T-wM) or K=x(S-wN), a transcript checksum, and the encoded KDC-REQ-BODY. K'[0] is used as the reply key when the ticket is issued; K'[1] is used to encrypt the second-factor response.
- The KDC either issues a ticket or sends an encdata message containing an additional second-factor challenge. If it sends an encdata message, the client responds with an encdata message, and this step repeats until the KDC issues a ticket. encdata messages are encrypted in K'[2], K'[3], etc..
Design
The mechanism will be a shared object implementing clpreauth and kdcpreauth modules, similar to PKINIT. It will be auto-registered like PKINIT, but will fail to initialize in 1.15 unless "spake_preauth_groups" is defined in krb5.conf.
ASN.1 encoders and decoders will be added in the usual way, with test vectors constructed using asn1c. Structures and prototypes will be placed in a new header k5-spake.h.
The client module will be implemented in the file spake_client.c. It is responsible for decoding PA-SPAKE padata messages from the KDC, maintaining the client transcript hash, generating response padata to be sent to the KDC with the next request, and replacing the reply key.
The KDC module will be implemented in the file spake_kdc.c. It is responsible for generating a hint (either trivial or containing an optimistic challenge), decoding PA-SPAKE padata messages from the client, maintaining the KDC transcript hash, storing state in a cookie, generating challenges in response to support messages, verifying challenge messages, continuing the second-factor exchange with encdata messages if necessary, and replacing the reply key.
The file util.c will contain shared operations which are not directly involved in implementing the SPAKE algorithm, including transcript checksum updates and derivation of K'[n] keys.
Cookie format
The KDC maintains its state between requests in a secure cookie (see Projects/SPAKE_preauth_prereqs), which contains:
- A stage, whose value is 0 if the cookie was sent with a challenge message and n>0 if the cookie was sent with the n'th encdata message from the KDC.
- The group number used in the challenge.
- The KDC private scalar value in a stage-0 cookie, or the SPAKE result K in a later cookie.
- The partial transcript checksum in a stage-0 cookie, or the final transcript checksum in a later cookie.
- Zero or more records of second-factor state, indexed by second-factor type. For a non-stage-0 cookie, there will be exactly one record, corresponding to the factor type chosen by the client.
Group operations
The SPAKE algorithm itself is parameterized by a group number. Initially only the NIST P-256 curve will be implemented; there is a high-performance assembly implementation of elliptic curve math for this group in OpenSSL for most platforms with minimal side channels. A group using the Edwards 25519 curve could perhaps beat this curve in performance, but there is currently no suitable implementation of the underlying math primitives.
The file groups.c will implement an interface to groups. As the SPAKE operations are symmetric on the client and server, the fundamental operations are divided into "keygen" which computes x and T or y and S, and "result" which computes K from x and S or from y and T. Both operations require the initial key as input. groups.c is also responsible for reading configuration to determine which groups are permitted.
Second-factor support
Design TBD. Considerations:
- We need a pluggable interface for the KDC and for the client.
- The KDC interface should support using the verto loop to contact back-end resources without blocking.
- There could be multiple KDC modules for the same second-factor type; e.g. a second-factor type which sends an OTP token value could be used with several different kinds of verifier modules. The same client module could be used for each of these KDC modules.
- For proper testing, we will need a test factor module which exercises additional encdata challenges.
- Policy controls are needed to determine whether to offer specific factors (including SF-NONE) for a particular client principal.
