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
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
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 <[email protected]>
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt
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
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 <[email protected]>
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt