GCM / seqiv and SP800-38D

Hi Herbert,

After some research, we think that the current implementation of seqiv 
as used for GCM does not comply with SP800-38D. Before I outline the 
issue, please allow me to state my understanding of seqiv (to make sure 
I really understand it :-) ).

Seqiv works as a wrapper around the associated cipher (like GCM in our 
case). If a caller wants to use the seqiv helper, the caller must use 
the aead_givcrypt_set_* API calls. For example, esp_output does that.

If the API calls are invoked seqiv performs its work and then calls the 
underlying cipher. The main work in seqiv is implemented in 
seqiv_geniv(). This function creates the IV for GCM. Its logic can be 
characterized as follows:

1. get some salt value from an RNG during init time (ctx->salt)

2. fill the IV with a sequence number provided by the caller (esp_output 
provides the IPSec sequence number here)

3. left-pad the sequence number with zeros

4. XOR the salt with the value from 3.

In case of rfc4106(gcm(aes)), the IV is 96 bits. Thus, our constructed 
IV looks like:

- rightmost 64 bit is an XOR of the sequence number and the rightmost 64 
bit of the random number

- leftmost 32 bit is leftmost 32 bit of the random number

If my understanding is correct, then this does not comply with 
SP800-38D. Even after speaking with the mathematicians at NIST 
controlling SP800-38D, they do not want to accept that solution.

The particular problem is SP800-38D section 8.2.1 and 8.2.2 where one 
can choose which of these two sections are implemented (either a full 
deterministic generation of an IV or a full RNG-based generation with an 
approved DRBG).

The key issue the authors of SP800-38D want to protect against is that 
there is no collision in the generation of an IV (for a given key). 

What seqiv does is to use the output of a DRBG (in FIPS mode) or 
/dev/urandom (in normal mode) and XOR it with a static value. The 
"postprocessing" of the XORing is not allowed as it may introduce 
potential collisions. I do not want to dive into math here, but if 
needed, we can do some calculations.

Thus, may I ask for a change in the GCM/seqiv combo? I think one of the 
following solutions would be possible:

- change seqiv to eliminate the XOR step (not sure whether we need to 
generate a random number every time seq_geniv is invoked)

- create a new IV handler (maybe call it simpleiv that may be a simple 
counter or an LFSR or a frontend to an RNG)

I would prefer the latter and wire up GCM with that "simpleiv".

Ciao
Stephan