DRBG seeding

DRBG seeding

[Herbert Xu]

Hi Stephan:

Currently DRBG is seeded with entropy from get_random_bytes.
However, get_random_bytes is basically the kernel version of
/dev/urandom.  So there is no guarantee that you're actually
getting the amount of entropy required.

Are you sure this is compliant with the DRBG specification?

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: DRBG seeding

[Stephan Mueller]

Am Donnerstag, 16. April 2015, 22:36:17 schrieb Herbert Xu:

Hi Herbert,

>Hi Stephan:
>
>Currently DRBG is seeded with entropy from get_random_bytes.
>However, get_random_bytes is basically the kernel version of
>/dev/urandom.  So there is no guarantee that you're actually
>getting the amount of entropy required.
>
>Are you sure this is compliant with the DRBG specification?

I do not see a specific requirement in SP800-90A about the quality of the 
noise source.

But SP800-90B specifies tests and assessments about the quality. When applying 
that specification, I applied some initial assessments: /dev/urandom complies 
with SP800-90B when disregarding the very early boot stage (i.e. when assuming 
that the input_pool received sufficient entropy).

The only shaky time is the boot time until the nonblocking_pool/input_pool has 
been sufficiently seeded.

That said, I already developed an in-kernel version of /dev/random. I sent the 
patch to LKML some half year ago. If I understood Ted Tso right, there is no 
general objection against adding that in-kernel interface. See [1] for the 
thread.

Furthermore, I already started working on updating the DRBG to use that in-
kernel /dev/random interface.

Shall I pursue that work in earnest now?

[1] https://lkml.org/lkml/2014/5/11/276


Ciao
Stephan

Re: DRBG seeding

[Herbert Xu]

On Thu, Apr 16, 2015 at 05:07:20PM +0200, Stephan Mueller wrote:
>
> I do not see a specific requirement in SP800-90A about the quality of the 
> noise source.

Well it explicitly says that you cannot use a DRBG.  In the worst
case get_random_bytes is completely deterministic.
 
> That said, I already developed an in-kernel version of /dev/random. I sent the 
> patch to LKML some half year ago. If I understood Ted Tso right, there is no 
> general objection against adding that in-kernel interface. See [1] for the 
> thread.
> 
> Furthermore, I already started working on updating the DRBG to use that in-
> kernel /dev/random interface.
> 
> Shall I pursue that work in earnest now?
> 
> [1] https://lkml.org/lkml/2014/5/11/276

Yes I think we should do this.

Thanks,
-- 
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: DRBG seeding

[Stephan Mueller]

Am Donnerstag, 16. April 2015, 23:26:18 schrieb Herbert Xu:

Hi Herbert,

>On Thu, Apr 16, 2015 at 05:07:20PM +0200, Stephan Mueller wrote:
>> I do not see a specific requirement in SP800-90A about the quality of the
>> noise source.
>
>Well it explicitly says that you cannot use a DRBG.  In the worst
>case get_random_bytes is completely deterministic.
>
>> That said, I already developed an in-kernel version of /dev/random. I sent
>> the patch to LKML some half year ago. If I understood Ted Tso right, there
>> is no general objection against adding that in-kernel interface. See [1]
>> for the thread.
>> 
>> Furthermore, I already started working on updating the DRBG to use that in-
>> kernel /dev/random interface.
>> 
>> Shall I pursue that work in earnest now?
>> 
>> [1] https://lkml.org/lkml/2014/5/11/276
>
>Yes I think we should do this.

Ok, I will work on that after I added the global lock to the DRBG.
>
>Thanks,


Ciao
Stephan

Re: DRBG seeding

[Andreas Steffen]

[-- Attachment #1: Type: text/plain, Size: 2271 bytes --]

Hi Stephan,

in my opinion you definitively have to seed the DRBG with true
entropy from /dev/random. This is what we are currently doing
in userland with the strongSwan DRBG needed for the post-quantum
NTRU-based key exchange algorithm. The NIST SP800-90A spec defines
a parameter which estimates the entropy contained in the seed,
but I think it is extremely difficult to derive an estimate
if /dev/urandom is used.

Our plans within the strongSwan project is to make the Linux
kernel DRBG available via the af-alg interface.

Best regards

Andreas

On 16.04.2015 17:32, Stephan Mueller wrote:
> Am Donnerstag, 16. April 2015, 23:26:18 schrieb Herbert Xu:
>
> Hi Herbert,
>
>> On Thu, Apr 16, 2015 at 05:07:20PM +0200, Stephan Mueller wrote:
>>> I do not see a specific requirement in SP800-90A about the quality of the
>>> noise source.
>>
>> Well it explicitly says that you cannot use a DRBG.  In the worst
>> case get_random_bytes is completely deterministic.
>>
>>> That said, I already developed an in-kernel version of /dev/random. I sent
>>> the patch to LKML some half year ago. If I understood Ted Tso right, there
>>> is no general objection against adding that in-kernel interface. See [1]
>>> for the thread.
>>>
>>> Furthermore, I already started working on updating the DRBG to use that in-
>>> kernel /dev/random interface.
>>>
>>> Shall I pursue that work in earnest now?
>>>
>>> [1] https://lkml.org/lkml/2014/5/11/276
>>
>> Yes I think we should do this.
>
> Ok, I will work on that after I added the global lock to the DRBG.
>>
>> Thanks,
>
>
> Ciao
> Stephan
> --
> To unsubscribe from this list: send the line "unsubscribe linux-crypto" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html
>

-- 
======================================================================
Andreas Steffen                         andreas.steffen@strongswan.org
strongSwan - the Open Source VPN Solution!          www.strongswan.org
Institute for Internet Technologies and Applications
University of Applied Sciences Rapperswil
CH-8640 Rapperswil (Switzerland)
===========================================================[ITA-HSR]==


[-- Attachment #2: S/MIME Cryptographic Signature --]
[-- Type: application/pkcs7-signature, Size: 4255 bytes --]

Re: DRBG seeding

[Stephan Mueller]

Am Donnerstag, 16. April 2015, 19:11:18 schrieb Andreas Steffen:

Hi Andreas,

> Hi Stephan,
> 
> in my opinion you definitively have to seed the DRBG with true
> entropy from /dev/random. This is what we are currently doing
> in userland with the strongSwan DRBG needed for the post-quantum
> NTRU-based key exchange algorithm. The NIST SP800-90A spec defines
> a parameter which estimates the entropy contained in the seed,
> but I think it is extremely difficult to derive an estimate
> if /dev/urandom is used.
> 
> Our plans within the strongSwan project is to make the Linux
> kernel DRBG available via the af-alg interface.

I am working on that. My current idea is the following:

1. during initialization of a DRBG instance, seed from get_random_bytes to 
have a DRBG state that is seeded and usable.

2. at the same time, initiate an async request to the yet to be developed (or 
rather forward-ported and accepted) in-kernel /dev/random interface

3. when the async request returns, re-seed the DRBG with that data

I am playing with the idea that steps 2 and 3 are repeated 2 or 3 times where 
the first invocation only requests a few bytes from the in-kernel /dev/random 
-- this again should seed the DRBG with entropy as it becomes available.

But thank you for your support. It is surely helpful to show also to Ted Tso 
that an update to /dev/random is of interest to various users.

Ciao
Stephan
> 
> Best regards
> 
> Andreas
> 
> On 16.04.2015 17:32, Stephan Mueller wrote:
> > Am Donnerstag, 16. April 2015, 23:26:18 schrieb Herbert Xu:
> > 
> > Hi Herbert,
> > 
> >> On Thu, Apr 16, 2015 at 05:07:20PM +0200, Stephan Mueller wrote:
> >>> I do not see a specific requirement in SP800-90A about the quality of
> >>> the
> >>> noise source.
> >> 
> >> Well it explicitly says that you cannot use a DRBG.  In the worst
> >> case get_random_bytes is completely deterministic.
> >> 
> >>> That said, I already developed an in-kernel version of /dev/random. I
> >>> sent
> >>> the patch to LKML some half year ago. If I understood Ted Tso right,
> >>> there
> >>> is no general objection against adding that in-kernel interface. See [1]
> >>> for the thread.
> >>> 
> >>> Furthermore, I already started working on updating the DRBG to use that
> >>> in-
> >>> kernel /dev/random interface.
> >>> 
> >>> Shall I pursue that work in earnest now?
> >>> 
> >>> [1] https://lkml.org/lkml/2014/5/11/276
> >> 
> >> Yes I think we should do this.
> > 
> > Ok, I will work on that after I added the global lock to the DRBG.
> > 
> >> Thanks,
> > 
> > Ciao
> > Stephan
> > --
> > To unsubscribe from this list: send the line "unsubscribe linux-crypto" in
> > the body of a message to majordomo@vger.kernel.org
> > More majordomo info at  http://vger.kernel.org/majordomo-info.html


-- 
Ciao
Stephan

Re: DRBG seeding

[Herbert Xu]

On Fri, Apr 17, 2015 at 03:19:17AM +0200, Stephan Mueller wrote:
>
> 1. during initialization of a DRBG instance, seed from get_random_bytes to 
> have a DRBG state that is seeded and usable.

I think we either need to use real entropy and block, or mark
the DRBG unusable until such a time that it has been seeded
with real entropy.

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: DRBG seeding

[Stephan Mueller]

Am Freitag, 17. April 2015, 10:14:30 schrieb Herbert Xu:

Hi Herbert,

> On Fri, Apr 17, 2015 at 03:19:17AM +0200, Stephan Mueller wrote:
> > 1. during initialization of a DRBG instance, seed from get_random_bytes to
> > have a DRBG state that is seeded and usable.
> 
> I think we either need to use real entropy and block, or mark
> the DRBG unusable until such a time that it has been seeded
> with real entropy.

Do you really think that this is possible? If the DRBG becomes the stdrng, you 
would imply that those callers (e.g. IPSEC) may suffer from a long block (and 
with long I mean not just seconds, but minutes).

Furthermore, I fail to see the difference between the current default stdrng 
(krng -- which is just get_random_bytes in disguise). Thus, the current 
situation with the DRBG seeding is not different from the non-DRBG use case.

Therefore, I still think we:

- need to satisfy users with an immediate need for random numbers immediately 
after instantiating the DRBG

- need to obtain "/dev/random"-like entropy as we can get hold of it.

Just as a side note, about 2 years ago, I offered a solution that also 
provides instant entropy at the time you need it -- see [1]. Unfortunately, it 
was rejected based on grounds I cannot fully comprehend

[1] https://lkml.org/lkml/2013/10/11/582
-- 
Ciao
Stephan

Re: DRBG seeding

[Herbert Xu]

On Fri, Apr 17, 2015 at 02:48:51PM +0200, Stephan Mueller wrote:
>
> Do you really think that this is possible? If the DRBG becomes the stdrng, you 
> would imply that those callers (e.g. IPSEC) may suffer from a long block (and 
> with long I mean not just seconds, but minutes).

It's only 49 bytes for every 64K so I think it's reasonable.
The only reason someone would use this is to comply with the
standard and this is what the standard requires so I don't see
how we can do anything else.
 
> Furthermore, I fail to see the difference between the current default stdrng 
> (krng -- which is just get_random_bytes in disguise). Thus, the current 
> situation with the DRBG seeding is not different from the non-DRBG use case.

The difference is that krng doesn't have to satisfy any standard.

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: DRBG seeding

[Stephan Mueller]

Am Freitag, 17. April 2015, 21:11:37 schrieb Herbert Xu:

Hi Herbert,

> On Fri, Apr 17, 2015 at 02:48:51PM +0200, Stephan Mueller wrote:
> > Do you really think that this is possible? If the DRBG becomes the stdrng,
> > you would imply that those callers (e.g. IPSEC) may suffer from a long
> > block (and with long I mean not just seconds, but minutes).
> 
> It's only 49 bytes for every 64K so I think it's reasonable.

Just an FYI on a test I did once: on a headless PPC (POWER6), we drained 
/dev/random (simply do a cat /dev/random). Then it took more than 20 hours(!) 
to get 48 bytes to seed OpenSSL from /dev/random. This test was done on some 
2.6.32 kernel.

That issue should be better now considering that interrupts are used as noise 
source by /dev/random.

Furthermore, it gets worse again considering that there is work underway to 
disable SSDs to feed /dev/random. Thus, on a server that is headless but has 
SSDs we only have interrupts feeding into /dev/random.

Thus, getting a full seed of 384 bits is minutes on a headless system will 
definitely be a challenge in a worst case.

> The only reason someone would use this is to comply with the
> standard and this is what the standard requires so I don't see
> how we can do anything else.

I do not see a definite quality requirement of the seed source in SP800-90A. 
In user space, FIPS validations happily used /dev/urandom where NIST has no 
concern.

Currently, there is a draft interpretation that tightens the issue around 
/dev/urandom significantly. Therefore, looking into the issue is definitely 
important. But still, blocking the DRBG right from the start until we have 
data from /dev/random does not seem helpful either.
> 
> > Furthermore, I fail to see the difference between the current default
> > stdrng (krng -- which is just get_random_bytes in disguise). Thus, the
> > current situation with the DRBG seeding is not different from the
> > non-DRBG use case.
> The difference is that krng doesn't have to satisfy any standard.
> 
> Cheers,


-- 
Ciao
Stephan

Re: DRBG seeding

[Herbert Xu]

On Fri, Apr 17, 2015 at 03:22:56PM +0200, Stephan Mueller wrote:
>
> > The only reason someone would use this is to comply with the
> > standard and this is what the standard requires so I don't see
> > how we can do anything else.
> 
> I do not see a definite quality requirement of the seed source in SP800-90A. 

Section 8.6.5 "Source of Entropy Input" explicitly requires this.

TBH whether /dev/random even satisfies 8.6.5 is also debatable.
But it agrees with the specification at least in spirit.

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: DRBG seeding

[Stephan Mueller]

Am Samstag, 18. April 2015, 09:27:44 schrieb Herbert Xu:

Hi Herbert,

> On Fri, Apr 17, 2015 at 03:22:56PM +0200, Stephan Mueller wrote:
> > > The only reason someone would use this is to comply with the
> > > standard and this is what the standard requires so I don't see
> > > how we can do anything else.
> > 
> > I do not see a definite quality requirement of the seed source in
> > SP800-90A.
> Section 8.6.5 "Source of Entropy Input" explicitly requires this.
> 
> TBH whether /dev/random even satisfies 8.6.5 is also debatable.
> But it agrees with the specification at least in spirit.

Ok, if I re-read that one and consider our discussion, I would agree. But it 
was handled differently up to now.

In any case, I am almost ready with the patch for an async seeding. Though, I 
want to give it a thorough testing.

-- 
Ciao
Stephan

Re: DRBG seeding

[Herbert Xu]

On Sat, Apr 18, 2015 at 03:32:03AM +0200, Stephan Mueller wrote:
>
> In any case, I am almost ready with the patch for an async seeding. Though, I 
> want to give it a thorough testing.

I don't see the point of async seeding, unless you're also making
all generate calls block until the seeding is complete.

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: DRBG seeding

[Stephan Mueller]

Am Samstag, 18. April 2015, 09:36:18 schrieb Herbert Xu:

Hi Herbert,

> On Sat, Apr 18, 2015 at 03:32:03AM +0200, Stephan Mueller wrote:
> > In any case, I am almost ready with the patch for an async seeding.
> > Though, I want to give it a thorough testing.
> 
> I don't see the point of async seeding, unless you're also making
> all generate calls block until the seeding is complete.

My plan is seeding first with /dev/urandom followed by the async /dev/random 
call. I.e. during the instantiation of the DRBG, the get_random_bytes is 
pulled for the initial seed. At the same time the async trigger to get data 
from /dev/random is made. Once that async call returns, the DRBG is re-seeded 
with that data.

Any immediate call to any in-kernel /dev/random and block really can cause the 
DRBG to stall. If the DRBG is the stdrng, we invite serious regressions if we 
block during initialization, especially in headless systems.

Furthermore, the DRBG is implemented to pull the nonce also from the seed 
source. As outlined in section 8.6.3 of SP800-90A, the nonce is used as a 
cushion if the entropy string does not have sufficient entropy.

However, the only serious solution I can offer to not block is to use my 
Jitter RNG which delivers entropy in (almost all) use cases. See [1]. The code 
is relatively small and does not have any dependencies. In this case, we could 
perform the initialization of the DRBG as follows:

1. pull buffer of size entropy + nonce from get_random_bytes

2. pull another buffer of size entropy + nonce from my Jitter RNG

3. XOR both

4. seed the DRBG with it

5. trigger the async invocation of the in-kernel /dev/random

6. return the DRBG instance to the caller without waiting for the completion 
of step 5

This way, we will get entropy during the first initialization without 
blocking. After speaking with mathematicians at NIST, that Jitter RNG approach 
would be accepted. Note, I personally think that the Jitter RNG has sufficient 
entropy in almost all circumstances (see the massive testing I conducted on 
all more widely used CPUs).

[1] http://www.chronox.de/jent.html

-- 
Ciao
Stephan

Re: DRBG seeding

[Herbert Xu]

On Sat, Apr 18, 2015 at 04:04:14AM +0200, Stephan Mueller wrote:
> 
> However, the only serious solution I can offer to not block is to use my 
> Jitter RNG which delivers entropy in (almost all) use cases. See [1]. The code 
> is relatively small and does not have any dependencies. In this case, we could 
> perform the initialization of the DRBG as follows:
> 
> 1. pull buffer of size entropy + nonce from get_random_bytes
> 
> 2. pull another buffer of size entropy + nonce from my Jitter RNG
> 
> 3. XOR both

Don't xor them.  Just provide them both as input to the seed
function.

> 4. seed the DRBG with it
> 
> 5. trigger the async invocation of the in-kernel /dev/random
> 
> 6. return the DRBG instance to the caller without waiting for the completion 
> of step 5
> 
> This way, we will get entropy during the first initialization without 
> blocking. After speaking with mathematicians at NIST, that Jitter RNG approach 
> would be accepted. Note, I personally think that the Jitter RNG has sufficient 
> entropy in almost all circumstances (see the massive testing I conducted on 
> all more widely used CPUs).
> 
> [1] http://www.chronox.de/jent.html

OK this sounds like it should satisfy everybody.

Thanks,
-- 
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