Subject: [kitten] AES-GCM for Kerberos GSS-API

From: Luke Howard <[email-masked]>
Date: Mon, 7 Dec 2015 19:52:35 +1100

I had a bit of a play with adding support for AES-GCM to Heimdal. Notes:

* GCM is added as a RFC 3961 enctype, but it’s really a pseudo-enctype – were it to be documented, it might not be at the 3961 layer at all (except camping on the enctype namespace for negotiation).

* The target application is only GSS, and it’s assumed it'd be negotiated using RFC4537.

* Encryption/decryption functions are extended to support associated data (this was already there in the implementation, but 3961 would need to be updated).

* KDF is SP800-108 in counter/feedback mode with CMAC, this is used both for key derivation and for RFC4401 PRF. (Wasn’t sure if was safe to use GMAC here?)

   Ke  = KDF-CMAC(base-key, usage | 0xAA)
   PRF = KDF-CMAC(base-key, "prf" | octet-string)

There is no Ki/Kc because there is no separate checksum or integrity usage.

* No string-to-key function is defined.

* No checksum types are defined, instead MIC tokens are constructed using the encryption function with an empty plaintext. I figured this was less intrusive than extending the checksum function to take a cipher state parameter, but comments are welcome.

* The cipher state is the GCM initialisation vector length; the length is 96 bits (excluding counter). A (key, IV) combination must never be reused. TOK_ID || Flags || 0xFF || SND_SEQ is used as the initialisation vector for all RFC 4121 tokens.

* The encrypted copy of the 4121 token header is removed (it is protected by the IV, except for the EC field which implementations must validate independently). We could additionally protect it as associated data.

Implementation (forked off aes-sha2 work):

https://github.com/heimdal/heimdal/tree/lukeh/aes-gcm <https://github.com/heimdal/heimdal/tree/lukeh/aes-gcm>

— Luke

---

From: Luke Howard <[email-masked]>
Date: Mon, 7 Dec 2015 20:27:04 +1100

> * The cipher state is the GCM initialisation vector length; the length is 96 bits (excluding counter). A (key, IV) combination must never be reused. TOK_ID || Flags || 0xFF || SND_SEQ is used as th…

Poorly worded - the cipher state is the GCM IV, the GCM IV is 96 bits long.

---

From: Luke Howard <[email-masked]>
Date: Mon, 7 Dec 2015 23:44:33 +1100

> On 7 Dec 2015, at 7:52 PM, Luke Howard <[email-masked]> wrote:
> 

I can’t find much about using a GMAC-based KDF, and I have no idea how safe it is in this usage with a constant IV. Still, if it’s possible, it would certainly be nice and symmetrical.

— Luke

---

From: Luke Howard <[email-masked]>
Date: Tue, 8 Dec 2015 09:03:03 +1100

> On 7 Dec 2015, at 11:44 PM, Luke Howard <[email-masked]> wrote:
> 
> 
>> On 7 Dec 2015, at 7:52 PM, Luke Howard <[email-masked] <mailto:[email-masked]>> wrote:
>> 

I did find this however:

http://marc.info/?l=cfrg&m=143336328026648&w=2 <http://marc.info/?l=cfrg&m=143336328026648&w=2>
https://www.ietf.org/mail-archive/web/cfrg/current/msg02689.html <https://www.ietf.org/mail-archive/web/cfrg/current/msg02689.html>

— Luke

---

From: Benjamin Kaduk <[email-masked]>
Date: Mon, 7 Dec 2015 17:08:10 -0500 (EST)

> https://www.ietf.org/mail-archive/web/cfrg/current/msg02689.html <https://www.ietf.org/mail-archive/web/cfrg/current/msg02689.html>

Perhaps I am just remembering those posts, but I do agree that GMAC is not
appropriate for KDF usage.

> * No checksum types are defined, instead MIC tokens are constructed
> using the encryption function with an empty plaintext. I figured this
> was less intrusive than extending the checksum function to take a cipher
> state parameter, but comments are
> welcome.

That seems reasonable at first glance.

I did not get to take a glance at the code itself yet, but thanks for
putting together the proof-of-concept.  Do you have any performance
numbers for comparison?

-Ben

---

From: Luke Howard <[email-masked]>
Date: Tue, 8 Dec 2015 09:17:27 +1100

> On 8 Dec 2015, at 9:08 AM, Benjamin Kaduk <[email-masked]> wrote:
> 

Not yet but given this is the principal motivation for GCM, I should really get some together. Will do.

— Luke

---

From: Luke Howard <[email-masked]>
Date: Tue, 8 Dec 2015 11:28:47 +1100

> * The cipher state is the GCM initialisation vector length; the length is 96 bits (excluding counter). A (key, IV) combination must never be reused. TOK_ID || Flags || 0xFF || SND_SEQ is used as th…

FWIW I took a quick look at IPsec (RFC4106 s8.1) and we could use that approach for IV construction – make the key length 20 (or 36) bytes and construct the IV as:

last four bytes Ke || SND_SEQ

however this lacks a direction bit, so we’d most likely need to steal the high bit from SND_SEQ which halves the number of messages that can be transmitted (perhaps not a practical issue).

Nico doesn’t think this is worth worrying about (GCM spec says that it’s OK to have a completely deterministic IV as long as it’s not reused with the same key), but perhaps the extra entropy / consistency with TLS/IPsec is a good idea?

— Luke

---

From: Luke Howard <[email-masked]>
Date: Tue, 8 Dec 2015 15:06:06 +1100

OK, I changed the implementation to more closely reflect other IETF usage of GCM. This gives the IV some more entropy I assume is not a bad thing.

The RFC3961 key length is now 20 bytes for aes128-gcm-128 and 36 bytes for aes128-gcm-128; the last four bytes are used to salt the IV in the same manner as TLS and IPsec.

The initialisation vector exposed at the 3961 level is now only eight bytes long and this meeds to include both a direction flag and the sequence number. Hence only 2^63 messages can be sent before the sequence number wraps (not a problem with Heimdal which only uses 32-bit sequence numbers, but perhaps an issue with other implementations). The first bit of the initialisation vector is set if the message is sent by the acceptor, unset if not.

Because the IV now only protects the sequence number, rather than most of the token header, the entire token header is input as the last item of associated data, for both Wrap and MIC tokens. (We could just include the first 8 bytes but I see no reason not to protect the entire header.)
 
Thoughts welcome (I know Nico thinks this change was not necessary!).

— Luke

---

From: Greg Hudson <[email-masked]>
Date: Tue, 8 Dec 2015 00:01:00 -0500

On 12/07/2015 07:28 PM, Luke Howard wrote:
> Nico doesn’t think this is worth worrying about (GCM spec says that it’s
> OK to have a completely deterministic IV as long as it’s not reused with
> the same key), but perhaps the extra entropy / consistency with
> TLS/IPsec is a good idea?

I agree with Nico; I think this is extra complexity we don't want or need.

---

From: Luke Howard <[email-masked]>
Date: Tue, 8 Dec 2015 16:47:21 +1100

> On 8 Dec 2015, at 4:01 PM, Greg Hudson <[email-masked]> wrote:
> 

OK. Are you OK with not protecting the token header in the MAC (i.e. asserting valid values of EC and relying on the IV)?

— Luke

---

From: [email-masked] (Martin Rex)
Date: Tue, 8 Dec 2015 09:09:28 +0100 (CET)

Luke Howard wrote:
> 
>> Luke Howard <[email-masked]> wrote:
>> 
>>> Luke Howard <[email-masked] <mailto:[email-masked]>> wrote:
>>> 
>>> * KDF is SP800-108 in counter/feedback mode with CMAC, this is used
>>>   both for key derivation and for RFC4401 PRF. (Wasn't sure if was
>>>   safe to use GMAC here?)
>>> 
>> I can't find much about using a GMAC-based KDF, and I have no idea
>> how safe it is in this usage with a constant IV. Still, if it's
>> possible, it would certainly be nice and symmetrical.
>
> I did find this however:
> 
> http://marc.info/?l=cfrg&m=143336328026648&w=2
> https://www.ietf.org/mail-archive/web/cfrg/current/msg02689.html

I assume that the hash function for use in the key derivation
needs to have cryptographic hash properties.

NIST SP 800-38D "Galois/Counter Mode (GCM) and GMAC",
2nd paragraph on page 10 of NIST SP 800-38D

http://csrc.nist.gov/publications/nistpubs/800-38D/SP-800-38D.pdf

   GHASH is a keyed hash function but not, on its own, a cryptographic
   hash function. This Recommendation only approves GHASH for use within
   the context of GCM. 

-Martin

---

From: Luke Howard <[email-masked]>
Date: Tue, 8 Dec 2015 21:42:14 +1100

If we profile for GSS only, we could (ignoring 
GSS PRF for a second) eliminate the need for key derivation entirely as there is no Kc/Ki and the token ID in the IV disambiguates Wrap from MIC usage.

But this might be risky if we are defining this at the 3961 level unless we can mandate the usage be part of the IV (but that means increasing the IV size which affects performance and also changes some of the NIST guarantees about safety IIRC).

Thoughts? Seems simplest to align with 3961 as closely as possible if defining at this layer, else if defining at GSS layer we can be more creative.

Sent from my iPhone

> On 8 Dec 2015, at 19:09, Martin Rex <[email-masked]> wrote:
> 
> Luke Howard wrote:
>>

---

From: Nico Williams <[email-masked]>
Date: Tue, 8 Dec 2015 16:36:57 -0600

> > I agree with Nico; I think this is extra complexity we don't want or need.

In particular: a deterministic IV construction is the key to preventing
key/IV reuse, _and_, we only need entropy in the key.

Entropy in the IV doesn't help security because whatever bits of it are
randomly chosen have to be sent in the clear as otherwise the peer won't
be able to reconstruct them.  The IV cannot be secret for GSS because of
the out of sequence token delivery/consumption requirement (well, it's
an option, but one we want).

For an RFC3961 octet stream application like AFS' rx the initial IV
could be secret and non-deterministic, thereafter just a counter.  In
this case entropy in the IV might increase security, but we don't need
that to make the enctype secure for GSS.

Entropy in the IV doesn't help UNLESS you just cannot construct a
deterministic IV.  Since here we can, we should not have any entropy in
the IV.

> OK. Are you OK with not protecting the token header in the MAC (i.e.
> asserting valid values of EC and relying on the IV)?

Putting the header into the IV necessarily protects the header.

This lets us have a savings of 16 bytes (no confounder) and 16 more
bytes (no header added to the plaintext), and costs us 4 bytes (the
integrity tag is 128 bits instead of 96 for the AES CTS HMAC-SHA1
enctypes), saving us a total of 28 bytes of overheade for wrap with
confidentiality tokens.  This is huge for small tokens, and a big
performance improvement: less data to transmit, less to move around, and
two fewer block operations, at no extra cost for protecting the header,
plus it's now parallelizable, and the integrity tag computation is
faster than HMAC-SHA-1.

The whole header is 128 bits and doesn't fit in 96 bits, but there are
five bytes that don't need protection, and if in a pinch we could
squeeze two more bytes out of the header.  So making the IV this is good
enough:

  TOK_ID || Flags || 0xFF || SEND_SEQ

The EC field is going to be a constant in all cases for these enctypes.
And the RRC field has never needed integrity protection.  That's the
four bytes we drop from the header to form the IV.

This leaves us with 32 bits of counter for the message data, which means
64GB wrap token w/ confidentiality max size.  64GB is plenty for this.

(There's only three TOK_ID values of interest here, and only three flags
bits used, so we could fold the TOK_ID into flags, leaving us with three
bytes for whatever we want, if we needed them.  But we don't need them.)

Nico
--

---

From: Luke Howard <[email-masked]>
Date: Wed, 9 Dec 2015 09:46:01 +1100

Note that in my proposal - based on IPSec - the entropy came from the last four bytes of the acceptor sub session key (having made that 20 instead of 16 bytes) so it wasn't sent in the clear, but I agree it probably adds no utility. It looks as if this exists in IPSec because keys may be reused, which we're asserting is not the case in the GSS profile.

Sent from my iPhone

> On 9 Dec 2015, at 09:36, Nico Williams <[email-masked]> wrote:
>

---

From: Nico Williams <[email-masked]>
Date: Tue, 8 Dec 2015 18:11:50 -0600

On Wed, Dec 09, 2015 at 09:46:01AM +1100, Luke Howard wrote:
> Note that in my proposal - based on IPSec - the entropy came from the
> last four bytes of the acceptor sub session key (having made that 20

But in that case no new entropy was contributed anyways...

> instead of 16 bytes) so it wasn't sent in the clear, but I agree it
> probably adds no utility. It looks as if this exists in IPSec because
> keys may be reused, which we're asserting is not the case in the GSS
> profile.

Correct.  Senders never reuse sequence numbers; session keys are chosen
randomly, and hopefully never reused.  Initial sequence numbers are also
chosen randomly (so, in fact, we get some entropy in the IV after all!
just indirectly), though monotonically increasing thereafter.

A bad RNG could result in the same session keys (and initial sequence
numbers) being chosen repeatedly, but only sessions will be compromised,
not long-term keys nor Ticket session keys.

IPsec is a very different beast.

Nico
--

---

From: Luke Howard <[email-masked]>
Date: Mon, 14 Dec 2015 12:33:02 +1100

This document defines extensions to RFC 3961 for use with AEAD ciphers that require deterministic initialisation vectors (such as GCM), by allowing encryption types to modify their behaviour depending on whether they are being used with long-term keys or not.

https://www.ietf.org/id/draft-howard-krb-aead-00.txt

— Luke

---

From: Luke Howard <[email-masked]>
Date: Mon, 14 Dec 2015 13:12:57 +1100

> On 8 Dec 2015, at 4:01 PM, Greg Hudson <[email-masked]> wrote:
> 

Reading RFC 3610 Section 5, this would help guard against pre-computation attacks, but so does the choice of a random initial sequence number in the AP-REQ (RFC 1510 section 3.2.2).

Anyway, on your advice I did not pursue this approach.

— Luke

---

From: Greg Hudson <[email-masked]>
Date: Mon, 14 Dec 2015 00:34:43 -0500

> This document defines extensions to RFC 3961 for use with AEAD ciphers that require deterministic initialisation vectors (such as GCM), by allowing encryption types to modify their behaviour depend…

I am tentatively okay with reserving points in the enctype namespace for
use with GSS AEAD enctypes (I'll call them that even though they could
be used by other protocols), so that we can use RFC 4537 enctype
negotiation during the AP-REQ/AP-REP exchange to negotiate their use.

I am tentatively opposed to sharing any part of the abstract API between
RFC 3961 ciphers and these GSS AEAD enctypes.  There's too much
potential for misuse.

I think we can avoid having to define a KDF (and therefore bring in
dependencies on additional primitives, such as SHA-256 for
chacha20-poly1305).  We may not need an analog to "key usage numbers" at
all, as these enctypes are only for use with ephemeral keys, never with
the same key across multiple protocols.  If we do determine a need for
key usage numbers, I think they could be included at the beginning of
the additional data for each message.

---

From: Luke Howard <[email-masked]>
Date: Mon, 14 Dec 2015 16:53:37 +1100

Hi Greg,

Thanks for the quick feedback.

> RFC 3961 ciphers and these GSS AEAD enctypes.  There's too much

Right, this is the alternate approach: define a single update to RFC 4121 for use with AEAD encryption types, where RFC 3961 is imported purely in order to leverage RFC 4537 enctype negotiation. From an implementation perspective: for Heimdal, it was ostensibly easier to implement this at the RFC 3961 layer. I agree it is probably impossible to completely guard against misuse. For the record I did the following to mitigate against misuse in my Heimdal implementation:

* No string-to-key function or associated checksum types will make most non-AEAD usages fail
* IV must be non-NULL on call to encrypt/decrypt
* AEAD encryption types unavailable except through krb5_encrypt_iov_ivec API
* Encryption type enumerate APIs hide any AEAD types unless the consumer is RFC 4537

Jeff: would be good to hear your thoughts on how useful GCM/etc are for non-GSS-API use (e.g. OpenAFS).

> the additional data for each message.

Good point. Yes, if this is really a RFC 4121 only profile, then TOK_ID is sufficient to disambiguate the Wrap and MIC usages, and we do not need any key derivation.

— Luke

---

From: Luke Howard <[email-masked]>
Date: Mon, 14 Dec 2015 17:07:09 +1100

Another approach is that we do actually define an approach for long-term keys (although I’m not sure how we’d do this elegantly with existing Unix APIs – perhaps checking for the absence of a HEADER in the IOV APIs).

KDF for long-term keys could be KDF(base-key, confounder | usage | 0xAA). I’m sure there are other workable constructions.

But – this is all additional complexity for implementations to deal with.

— Luke

---

From: Luke Howard <[email-masked]>
Date: Mon, 14 Dec 2015 17:14:08 +1100

> On 14 Dec 2015, at 4:34 PM, Greg Hudson <[email-masked]> wrote:
> 

As a middle ground, we could stay a little clearer of RFC 3961 but still define the AEAD primitives separately so that non-GSS consumers can still take advantage of them.

— Luke

---

From: Benjamin Kaduk <[email-masked]>
Date: Mon, 14 Dec 2015 12:54:50 -0500 (EST)

> non-GSS-API use (e.g. OpenAFS).

I'm not Jeff, but I am a coauthor on the rxgk-afs specs [0,1] that would
be applicable for OpenAFS.  We only use GSS-API for a single negotiation
loop in which the AFS server essentually functions as a kerberos KDC,
vending a ticket-analogue ("token") that is used to authenticate
subsequent connections.  The "session key" contained in that token (called
the "token master key") is not used directly; instead a unique transport
key is generated for each connection using PRF+ (this is section 8.3 of
[0]).  It is these subsequent connections that perform bulk data transfer,
and one would expect that GCM/etc would provide some speed benefit, to the
extent that the network stack is not the bottleneck.  (The OpenAFS rx
stack is notoriously non-performant, particularly for links with large
RTT.)  But, the network can be improved with "just" a "small matter of
programming", so it seems beneficial to provide a way that these new
enctypes could be used by non-GSSAPI protocols.

-Ben

[0] https://tools.ietf.org/html/draft-wilkinson-afs3-rxgk-11
[1] https://tools.ietf.org/html/draft-wilkinson-afs3-rxgk-afs-08

---

From: Greg Hudson <[email-masked]>
Date: Mon, 14 Dec 2015 13:20:10 -0500

On 12/14/2015 12:54 PM, Benjamin Kaduk wrote:
> But, the network can be improved with "just" a "small matter of

AES-GCM and chacha20-poly1305 are already well-specified; beyond
assigning enctype numbers that can be negotiated alongside RFC 3961
enctypes, I'm not sure we really have anything to say.

In the GSS layer, we of course have to specify what to use as the IV and
what to provide as additional data.  But all that is very much specific
to GSS.

---

From: Benjamin Kaduk <[email-masked]>
Date: Mon, 14 Dec 2015 13:33:22 -0500 (EST)

Hi Greg,

> what to provide as additional data.  But all that is very much specific

The text you quoted and your reply seem like something of a non-sequitur
to me.

I suppose I did leave out the key fact that the OpenAFS/rxgk case is
currently using raw 3961 crypto for its bulk data protection.  rxgk does
have its own enctype negotiation scheme, though someone would need to do
an audit to ensure that the "token master key" is not used anywhere
without the appropriate key derivation to ensure global uniqueness.

-Ben

---

From: Stefan Metzmacher <[email-masked]>
Date: Tue, 15 Dec 2015 08:33:03 +0100

Hi Benjamin,

> enctypes could be used by non-GSSAPI protocols.

You may want to have a look at
https://msdn.microsoft.com/en-us/library/cc246482.aspx
to see how aes-ccm-128 and aes-gcm-128 are used in SMB3.
It also uses GSSAPI to do the authentication and do custom crypto
based on the authentication session key.

metze

---

From: Luke Howard <[email-masked]>
Date: Tue, 15 Dec 2015 19:06:39 +1100

Thanks Metze, very useful pointer. Out of interest do you know what their nonces look like? I’m surprised they say the nonce formation is implementation-specific as they do not appear to be using different keys for each direction (so the implementations would need to cooperate to avoid repeating nonces).

(FWIW: SMB appears to use HMAC-SHA256 as the KDF hash function for GCM/CCM rather than CMAC.)

— Luke

> On 15 Dec 2015, at 6:33 PM, Stefan Metzmacher <[email-masked]> wrote:
> 

--
www.lukehoward.com
soundcloud.com/lukehoward

---

From: Luke Howard <[email-masked]>
Date: Tue, 15 Dec 2015 19:48:59 +1100

> On 15 Dec 2015, at 7:06 PM, Luke Howard <[email-masked]> wrote:
> 

Sorry this was a bit misleading – what I meant to say is that, for GCM, you want to have a completely deterministic IV construction in order to not be limited to 2^32 invocations. But maybe this is not an issue for SMB3.

— Luke

---

From: Stefan Metzmacher <[email-masked]>
Date: Tue, 15 Dec 2015 10:31:45 +0100

Hi Luke,

> (FWIW: SMB appears to use HMAC-SHA256 as the KDF hash function for GCM/CCM rather than CMAC.)

There's a encryption and a decryption key.

https://git.samba.org/?p=samba.git;a=blob;f=libcli/smb/smbXcli_base.c#l5565

Windows uses the nonce like this:

8 byte counter
8 byte session id

Depending on the algorithm the nonce is then truncated.

Samba uses this:

8 byte counter low
8 byte counter high

The high value is random and truncated by the algorithm nonce size.

See:
https://git.samba.org/?p=samba.git;a=blob;f=libcli/smb/smbXcli_base.c#l5737
https://git.samba.org/?p=samba.git;a=blob;f=libcli/smb/smbXcli_base.c#l2974

metze

---

From: Luke Howard <[email-masked]>
Date: Tue, 15 Dec 2015 20:48:05 +1100

Hi Metze,

> There's a encryption and a decryption key.

Ah, thanks Metze, I’d somehow missed that in [MS-SMB2]. Well, all is good then – sorry for the distraction!

— Luke

---

From: Luke Howard <[email-masked]>
Date: Thu, 17 Dec 2015 23:39:26 +1100

> On 15 Dec 2015, at 5:33 AM, Benjamin Kaduk <[email-masked]> wrote:
> 

Right, I took a quick look at your code/draft, the authenticator and packets are fine (the IV can contain the sequence number, where seq=0 for the authenticator). But token encryption may need more care.

— Luke