Difference between revisions of "Projects/SPAKE Preauthentication"

Revision as of 15:02, 27 October 2015

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, in the following format:

   version (16-bit unsigned integer)
   stage (16-bit unsigned integer)
   group (32-bit signed integer)
   SPAKE value (32-bit unsigned length, followed by data)
   Transcript checksum (32-bit unsigned length, followed by data)
   Zero or more instances of:
       second-factor number (32-bit signed integer)
       second-factor data (32-bit unsigned length, followed by data)

The only currently supported version is 1. stage is 0 if the cookie was sent with a challenge message. stage is n>0 if the cookie was sent with an encdata message encrypted in K'[2n]. group indicates the group number used in the SPAKE challenge. The SPAKE value is the KDC private key for a stage-0 cookie, represented in the scalar marshalling form of the group; for other cookies, the SPAKE value is the SPAKE result K, represented in the group element marshalling form. The transcript checksum is the intermediate checksum after updating with the challenge for a stage-0 cookie, or the final checksum for other cookies. For a stage 0 cookie, there may be any number of second-factor records, including none (no record is generated for SF-NONE); for other cookies, there must be exactly one second-factor 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.