Authenticated Encryption for Dummies

aefd.md

It might seem like a silly exercise, but I was looking at the "NIST approved" algorithms in NaCl (i.e. AES, HMAC) and wondering if I could build an authenticated encryption system with them. djb lists AES-GCM as a "todo" secretbox primitive so unfortunately NaCl does not presently expose any AES-based authenticated encryption, only aes128ctr.

This is what I came up with using the algorithms available in NaCl:

A quick rundown:

Encrypt-then-MAC with AES-CTR (128-bit for now, 256-bit later!) encryption and HMAC SHA-512256 (i.e. SHA-512, truncated to 256-bits by NaCl via crypto_auth_hmacsha512256) authentication. MAC comparisons are performed using a NaCl supplied verifier function which is (hopefully!) constant time.

Separate keys are used for AES and HMAC, derived by combining an initial 256-bit key and a nonce with HKDF and expanding the result into unique keys for AES and HMAC. Because a unique key is used for each AES encryption, the AES counter can always start at 0.

While a cryptographic layman should probably not be designing an authenticated encryption mode, it seems like these particular primitives are relatively free of rough edges, particularly when I am using the implementations available in NaCl

Cool story, should I run off and implement this?

No, you want Crypto::SecretBox

You forgot the nonce in the diagram.

Also, for key derivation, I'd suggest:

k_enc <- HMAC(k, "aes128ctr")
k_auth <- HMAC(k, "hmac-sha512-256")

which is how Schneier et al suggest doing it in Cryptography Engineering (Chapter 7, iirc). With the string values adjusted to taste. The other alternative is to do as djb does and use the encryption of 0s with the first 32 bytes of the stream as the key for the authenticator.

Updated with a nonce. I decided to go with HKDF instead of HMAC + nothing up my sleeve numbers

XSalsa20 seems to work like this (if it used NIST algorithms):

key <- {0,1}^32
nonce <- {0,1}^24

subkey <- HMAC(key, nonce[0,16]) # first 16 bytes of nonce.

ctr_nonce <- nonce[16,8] || 0^8
auth_key <- AES-CTR(subkey, ctr_nonce, 0^32)
ciphertext <- AES-CTR(subkey,ctr_nonce+2, plaintext)
auth <- HMAC(auth_key, ciphertext)

# return
auth || ciphertext

Not suggesting we/you/anyone should do this, but it seems be how the long nonces are used as part of the algorithm.

This approach could support arbitrary length nonces, and they wouldn't have to be random (as long as the key was random). Seems like an interesting property.

Per Matt Green I updated at least the diagrams to show MACing of the nonce. I am not sure the best way to proceed but I was thinking:

HMACSHA512256(nonce || ciphertext, hmac_key)

Edit: Matt says this is ok

Yes, the XSalsa20 scheme is the same in that regard.

Arbitrary length nonces don't make sense (or at least there's a definite point of diminishing returns). At some point, you're mapping more bits of input than you're using the output. At that point, I think you stop getting any benefit from adding more bits to the input.

I'm not sure why you need to MAC the nonce, or if that even makes sense? I might ask Matt Green about this, but the construction requires that you use the nonce, before verification, to create the key used to verify it. If you can choose a nonce such that you can construct a valid authenticator for an arbitrary ciphertext, doesn't seem like that much more effort to forge a nonce that also validates itself?

@namelessjon I think MACing the nonce just removes more margin-of-error. I should probably enquire with Matt Green what the exact rationale is though. Or you can! ;)

RE: Arbitrary length nonces, I'd probably set a cap. Marsh Ray suggested MACing nonce length || nonce || ciphertext. If I used a byte to represent the nonce length, it'd set the maximum size of the nonce at an (unrealistically large) 256 bytes.

Conversations on Twitter while you sleep are fun to wake up to, but hard to contribute to ;)

I guess I buy his "why the hell not?" argument, but I'm also glad I didn't miss a more fundamental one.

Re: nonce length, I would specify one as part of the scheme, e.g. 24 bytes or 32 bytes. Long enough to safely pick at random, short enough it's not wasting effort (or random bytes).

@namelessjon I think originally he didn't see I had changed the scheme to have the nonce be HKDF input, which accomplishes the same thing.

A fixed length nonce is probably fine. 24-bytes seems reasonable.