GCM / seqiv and SP800-38D

GCM / seqiv and SP800-38D

[Stephan Mueller]

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

Re: GCM / seqiv and SP800-38D

[Herbert Xu]

On Thu, Feb 19, 2015 at 07:56:48AM +0100, Stephan Mueller wrote:
>
> In case of rfc4106(gcm(aes)), the IV is 96 bits. Thus, our constructed 
> IV looks like:

The IV to rfc4106 is 96 bits, but the IV to the underlying gcm
is 128 bits so that's what guarantees the uniqueness.

Cheers,
-- 
Email: Herbert Xu <herbert@gondor.apana.org.au>
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt

Re: GCM / seqiv and SP800-38D

[Stephan Mueller]

Am Samstag, 28. Februar 2015, 23:47:12 schrieb Herbert Xu:

Hi Herbert,

> On Thu, Feb 19, 2015 at 07:56:48AM +0100, Stephan Mueller wrote:
> > In case of rfc4106(gcm(aes)), the IV is 96 bits. Thus, our constructed
> 
> > IV looks like:
> The IV to rfc4106 is 96 bits, but the IV to the underlying gcm
> is 128 bits so that's what guarantees the uniqueness.

We have to be careful with the wording here: SP800-38D specifies the 96 bits 
as the IV (also called the nonce). The additional 32 bit you refer to is the 
counter for the CTR mode. The complete 128 bit are *not* referred to when 
SP800-38D speaks about the uniqueness of IVs in section 8.2.1 or 8.2.2.

Thus, we come back to the 96 bits. And I do not dispute that there is almost 
zip probability of collisions, all I want to state is that the construction 
method with seqiv does neither comply with section 8.2.1 nor with 8.2.2. That 
means, the GCM IV construction currently does not meet the specification of 
SP800-38D. Furthermore, the authors of SP800-38D currently do not approve of 
the seqiv construction method.

-- 
Ciao
Stephan

Re: GCM / seqiv and SP800-38D

[Herbert Xu]

On Sat, Feb 28, 2015 at 01:08:03PM +0100, Stephan Mueller wrote:
> Am Samstag, 28. Februar 2015, 23:47:12 schrieb Herbert Xu:
> 
> Hi Herbert,
> 
> > On Thu, Feb 19, 2015 at 07:56:48AM +0100, Stephan Mueller wrote:
> > > In case of rfc4106(gcm(aes)), the IV is 96 bits. Thus, our constructed
> > 
> > > IV looks like:
> > The IV to rfc4106 is 96 bits, but the IV to the underlying gcm
> > is 128 bits so that's what guarantees the uniqueness.
> 
> We have to be careful with the wording here: SP800-38D specifies the 96 bits 
> as the IV (also called the nonce). The additional 32 bit you refer to is the 
> counter for the CTR mode. The complete 128 bit are *not* referred to when 
> SP800-38D speaks about the uniqueness of IVs in section 8.2.1 or 8.2.2.
> 
> Thus, we come back to the 96 bits. And I do not dispute that there is almost 
> zip probability of collisions, all I want to state is that the construction 
> method with seqiv does neither comply with section 8.2.1 nor with 8.2.2. That 
> means, the GCM IV construction currently does not meet the specification of 
> SP800-38D. Furthermore, the authors of SP800-38D currently do not approve of 
> the seqiv construction method.

The 96 bits are guaranteed to be unique for a given key because the
64-bit sequence number is given to us by the IPsec stack which must
guarantee its uniqueness.

Cheers,
-- 
Email: Herbert Xu <herbert@gondor.apana.org.au>
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt

Re: GCM / seqiv and SP800-38D

[Marcus Meissner]

Hi,

I had some offline discussion with Stephan and it seems to me
at least that it is very hard to use the described "Deterministic"
method under Linux while at the same time still keeping the
uniqueness requirement to stay FIPS 140-2 certifiable.


How about going full randomized IV generation on GCM?

For that I wonder if the givencrypt can ever be called with the same
sequence number again so we would need to reproduce earlier randomness?

Ciao, Marcus


> 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