DRBG seeding
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 Home Page: http://gondor.apana.org.au/~herbert/ PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt -- To unsubscribe from this list: send the line "unsubscribe linux-crypto" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: DRBG seeding
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 -- To unsubscribe from this list: send the line "unsubscribe linux-crypto" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: DRBG seeding
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 Home Page: http://gondor.apana.org.au/~herbert/ PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt -- To unsubscribe from this list: send the line "unsubscribe linux-crypto" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: DRBG seeding
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 majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: DRBG seeding
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 majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html -- == Andreas Steffen andreas.stef...@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]== smime.p7s Description: S/MIME Cryptographic Signature
Re: DRBG seeding
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 majord...@vger.kernel.org > > More majordomo info at http://vger.kernel.org/majordomo-info.html -- Ciao Stephan -- To unsubscribe from this list: send the line "unsubscribe linux-crypto" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: DRBG seeding
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 Home Page: http://gondor.apana.org.au/~herbert/ PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt -- To unsubscribe from this list: send the line "unsubscribe linux-crypto" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: DRBG seeding
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 -- To unsubscribe from this list: send the line "unsubscribe linux-crypto" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: DRBG seeding
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 Home Page: http://gondor.apana.org.au/~herbert/ PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt -- To unsubscribe from this list: send the line "unsubscribe linux-crypto" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: DRBG seeding
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 -- To unsubscribe from this list: send the line "unsubscribe linux-crypto" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: DRBG seeding
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 Home Page: http://gondor.apana.org.au/~herbert/ PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt -- To unsubscribe from this list: send the line "unsubscribe linux-crypto" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: DRBG seeding
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 -- To unsubscribe from this list: send the line "unsubscribe linux-crypto" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: DRBG seeding
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 Home Page: http://gondor.apana.org.au/~herbert/ PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt -- To unsubscribe from this list: send the line "unsubscribe linux-crypto" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: DRBG seeding
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 -- To unsubscribe from this list: send the line "unsubscribe linux-crypto" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: DRBG seeding
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 Home Page: http://gondor.apana.org.au/~herbert/ PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt -- To unsubscribe from this list: send the line "unsubscribe linux-crypto" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html