1
$\begingroup$

In my implementation of AES-GCM, the key might change only once per minute. However, I wish to calculate a new tag every 6us, to reduce latency (since you have to buffer up a GCM "packet" before checking the tag and releasing it).

  1. May I keep the same key and generate millions of tags using the same key, as long as the GCM counter increments for every 128-bit block?
  2. Do I need to restart the tag computation process (i.e., clear accumulators) for each tag?

  3. Or, must I change the key once a tag is computed and transmitted?

  4. In a related question, can I use an IV of fewer than 96 bits?

Normally there is an IV of 96 bits and a 32-bit counter, but at my data rates (400Gbps) I'll burn through the 32-bit counter in less than 1.5 sec, and I don't want to have to update the key every second.

  1. Could I use, say, an 84-bit IV with a 44-bit counter?
$\endgroup$
  • $\begingroup$ 1. ) The counter should not repeat See Plain text size limits for AES-GCM mode just 64GB? 2) You should. If there is an error that can propagate before you need to call the data back. 3) More secure, right? 4) Yes you can but remember the birthday attack $\sqrt{n}$ 5) $\sqrt{2^{84}}=2^{42}$ seems fine but below the recommendation, are you changing key? If so, better. $\endgroup$ – kelalaka Jan 4 '19 at 23:20
  • $\begingroup$ 6us = 6 microseconds $\endgroup$ – Evariste Jan 4 '19 at 23:27
  • $\begingroup$ To be clearer, I'd like to have a new key and 84-bit IV every ~60 sec, but generate and send a new tag every 6 us. The 44-bit counter appended to the 84-bit IV would start at 1 and increment continuously during the 60 sec, reaching a value of around 2^37. The main thing I don't understand is if I can keep generating new tags with the same key. I can't change the key every 6 us. $\endgroup$ – Evariste Jan 4 '19 at 23:37
  • $\begingroup$ There is no problem if the counter starts from $x$ not 1 as long as you are use the same counter again. $\endgroup$ – kelalaka Jan 4 '19 at 23:43
  • $\begingroup$ For $IV<92$ see this Generate J0 for GCM cipher when len(IV)≠96 bits $\endgroup$ – kelalaka Jan 5 '19 at 10:20
2
$\begingroup$

I thought I'd update this with what I learned designing my ASIC. I found the literature and terminology very ambiguous, even McGrew & Viega's paper on GCM. Thanks to Poncho and others for their answers. Here are some notes from my code:

************************* Nonce Format *****************************

|<--            Counter Block (CB) (128 bits)                   -->|
|<--            Nonce (96 bits)                   -->|
                                  |<-  Invoc Cntr  ->|
                      Salt[56:63] |<-->| 
+-----------------+---------------+------------------+-------------+
|   salt[0:31]    |  salt[32:55]  |       SEQ        |   Blk Ctr   |
+-----------------+---------------+------------------+-------------+
|<--    32      -><--    24     -><-      40       -><-   32     ->|

Salt:  64-bit value used to form the nonce.  This is unique to each
       key.  It should be true-random but need not be secret.
       RFC-4106 recommends that only salt[0:31] be used and that 
       salt[32:63] be left at 32'b0.  salt[56:63] will be XORed 
       with the leftmost 8 bits of SEQ.
SEQ:   Extended sequence number, aka invocation counter.  This is 
       called the IV (Initial Vector) in RFC-4106.  This normally
       starts at 0 with a new key and increments every frm.
Blk Ctr:  This starts at 32'd2 on every frame and increments for
       every 128-bit block of cryptext.
-------------------------------------------------------------------

In my case, I start with a key/salt pair, which should be updated every 8 hours. (I generate a new tag every ~6$\mu$s, and the NIST recommends not using more than $2^{32}$ tags per key.)

Much of the terminology (e.g., "IV") is ambiguous. The terms I use are not completely standardized. There is a unique "nonce" for each "frame", where each frame has a tag. The nonce format is shown above. The "salt" is normally 32 bits but can be up to 64 bits. It changes when the key does.

When the key/salt changes, the 40-bit sequence counter SEQ is reset to 0. SEQ increments for every "frame", each of which is terminated with a tag. In my case, "frames" have about 20e3 128-bit AES blocks. SEQ should not exceed $2^{32}$ to prevent tag forging.

The 32-bit block counter starts at 2 at the beginning of each "frame". It increments for each 128-bit block up to about 20e3 and then resets for the next frame (after a tag is generated).

I don't have to worry about collisions because only one chip is encrypting with a given key, so there will be no nonce reuse.

|improve this answer|||||
$\endgroup$
1
$\begingroup$
  1. May I keep the same key and generate millions of tags using the same key, as long as the GCM counter increments for every 128-bit block?

You can generate millions of tags, but you'd want to use a distinct IV for each one.

  1. Do I need to restart the tag computation process (i.e., clear accumulators) for each tag?

Well, yes, the security proof for GCM assume that each message is encrypted independently (and in your case, each 6usec section of data would be treated as a separate message). Now, it might be possible to prove security when you don't restart things, but I wouldn't count on it. In addition, if you don't clear things out, you might run into problems where an intermediately frame gets an error (possibly due to random line noise); with standard GCM, just that frame will get rejected; if you keep the computation stateful, you might end up throwing everything out until you rekey. So, I think you'd be well advised to reset the computation, even if someone can prove that not doing so is secure.

  1. Or, must I change the key once a tag is computed and transmitted?

Nope, as above, you can use the same key multiple times.

  1. In a related question, can I use an IV of fewer than 96 bits?

Well, you could (GCM does allow variable length IVs); however there is little reason to; in variable length mode, GCM is slower (because it takes some computations to convert the IV into an internal state), and it turns out to be less secure.

On the other hand:

  1. Could I use, say, an 84-bit IV with a 44-bit counter

No; GCM is defined to use a 32 bit counter internally. And, you have no reason to; at 400Gbps (are you really that fast?) GCM will process about 18,750 128 bit blocks (or 300kbytes) in 6usec; after 6usec, you generate a tag, and start on encrypting a distinct message (which resets the internal counter); this doesn't come close to hitting the limit on GCM message size.

|improve this answer|||||
$\endgroup$
  • $\begingroup$ Yes, it's really 400Gbps! (More like 403.) OK; I need to reset the 32-bit counter for each tag (message). Can I then just increment the 96-bit IV for the next "message"? Or does that reduce the effective length of the IV? $\endgroup$ – Evariste Jan 5 '19 at 0:17
  • $\begingroup$ @Evariste: incrementing the IV is just fine (and is the most common way of doing tihngs). As for my surprise for the 400Gbps, well, I knew that there were interfaces that fast; however I didn't think many people worked on them... $\endgroup$ – poncho Jan 5 '19 at 14:55
  • $\begingroup$ 400G is pretty cutting-edge. I think 200G systems exist currently. This is for an ASIC which will have to process 4 128-bit blocks per clock cycle. So it seems what I need to do is to restart the 32-bit counter for each "message", increment the IV for each message (which would be about 3e9 increments per second) and then start with a new IV when I update the key. $\endgroup$ – Evariste Jan 5 '19 at 22:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.