Comment by dchest | Hacker News Reader

Comment by dchest | Hacker News Reader

Parent Full thread

The design is very clever: since it's based on CMAC, we can use AES-CBC to derive keys where lower level primitives are not available.

In AES-CBC terms, the algorithm can be described as:

    1. L = AES-CBC-256ₖ(iv = 0¹²⁸, plaintext = 0¹²⁸)[:16]
    2. If MSB₁(L) = 0, then K1 = L << 1;
       Else K1 = (L << 1) ⊕ 0¹²⁰10000111
    3. M1 = 0x00 || 0x01 || X || 0x00 || N[:12]
    4. M2 = 0x00 || 0x02 || X || 0x00 || N[:12]
    5. Kₓ = AES-CBC-256ₖ(iv = K1, plaintext = M1)[:16] || AES-CBC-256ₖ(iv = K1, plaintext = M2)[:16]
    6. Nₓ = N[12:]

Where AES-CBC-256 returns the first 128-bit block of the ciphertext, discarding the padded block. (Thus, if you can't turn off padding, it costs three additional AES calls with the same key compared to a lower level implementation — not bad). After deriving a key, use it with the standard AES-GCM.

Here's my JS implementation based on WebCrypto API, which uses this fact: https://github.com/dchest/xaes

It accepts a proper CryptoKey intended for AES-CBC, supporting all CryptoKey features, e.g. storing it in IndexedDB with "extractable" bit set to false.

Great job, Filippo!

It seems to be standard in that field, but to be honest, I hate cryptographic notation. AFAICT, about half of the numbers in that pseudo-code count a number of bytes, and the other half a number of bits, and without already knowing the algorithms, it's almost impossible to tell which is which. E.g., N[:12] seems to be twelve bytes, while 0¹²⁸ is 16 bytes. X is actually the character 'X', i.e. the bit string 01011000. While L is actually a variable, not the bit string 01001100. And so on. It's clear that mathematicians don't like unambiguous notation nearly as much as CS people do.

Well, X is a variable that's equal to 'X' :) It's a mix of cryptographic notation, Go/Python notations for slices, and my ad-hoc notation for AES-CBC. To be fair, I find such pseudocode easier to read than math notation, but it's because I'm more used to it.

Agree. Bytes and bits mix is quite awful. For implementation purposes it could be more programming oriented. 0¹²⁸ -> `[0] * 16` (it's python oriented, maybe C has short idiom for that) or nice example with padded data: 0¹²⁰10000111 -> `[0] * 15 || 0b10000111`. `X` should be clearly 'X'.

I guess crypto pros are ok with notation. But for hobbyist it requires some reverse engineering every time.

I don't disagree, actually. I was copying the NIST source document notation with 0¹²⁸ and 0¹²⁰10000111, but it probably does more harm than good. `X` was just me being too clever. (In my defense, `X` is formatted differently from variables in the original, and all variables are defined.)

Done. https://github.com/C2SP/C2SP/pull/86/files

> 0¹²⁰10000111

for those of you(like me) wondering where this apparently spooky constant is coming from, it is a bitstring of the coefficients of the lexically first irreducible polynomial of degree b with the minimum possible number of non-zero terms, where b is the block size(in bits) of the underlying block cipher with which CMAC is instantiated. So, nothing up the sleeve here.

My natural follow-up question was "why can't you just have K1 = L?" Obviously it's inherited from CMAC, but why does CMAC do it?

Investigating further, general-case CMAC involves generating a K1 and a K2, which afaict just need to be arbitrarily different from each other. So why not something even simpler, like "xor with 1"?

The multiplication in CMAC is there to distinguish between full and partial final input blocks. It can't be simply a xor with a constant because that would be easily cancelable in the input, and wouldn't satisfy the required xor-universal-like properties required by the security proof.

The input here is highly restricted so there's no point to it.

My reaction was "Huh? What multiplication?"

The answer is that we're treating this as a Galois field/finite field of order 2^128 with the reducing polynomial (2^128 + 0b10000111).

Under that framework, the left shift and possible XOR implement multiplication by 2. (An example of general multiplication here: https://en.wikipedia.org/wiki/Finite_field_arithmetic#Progra...)

It's an 8 bit constant padded to 128 bits, so while I appreciate the explanation it's not nearly enough entropy to spook me.

Not a crypto guy. So would the high-level summary be something like this?

Standard AES-GCM AEAD will catastrophically fail if you use the same nonce twice[1] for different messages, and the size of the size of the nonce is small enough that one cannot safely use a random nonce in many cases.

This work provides an easy to use way to avoid that. It does so by changing not just the nonce but also the key used per message for the AES-GCM call.

And it uses only "plain" AES which is readily available if you have AES-GCM, and no fancy new constructions which may have unknown weaknesses.

The overhead per message is just two small buffers that needs to be encrypted/decrypted with "plain" AES and a longer 192 bit nonce.

[1]: https://frereit.de/aes_gcm/

Reply on news.ycombinator.com