[Cryptography] Fwd: [IP] 'We cannot trust' Intel and Via's chip-based crypto, FreeBSD developers say

Arnold Reinhold agr at me.com
Thu Dec 19 07:56:36 EST 2013


On 16 Dec 2013 12:52 John Kelsey wrote:
> On Dec 13, 2013, at 2:02 PM, Nico Williams <nico at cryptonector.com> wrote:
> 
>> On Fri, Dec 13, 2013 at 01:24:21PM -0500, John Kelsey wrote:
>>> Why not just XOR RD_RAND outputs with Yarrow outputs?  That guarantees
>>> strong results if either one is good.
>> 
>> Yes, to reprise the /dev/*random robustness thread, we need as many
>> inputs to the CSPRNG as possible.  Heck, even a constant seed and a seed
>> saved from the previous boot.  As long as the PRNG is cryptographically
>> secure and at least one source of boot-time (and subsequent) entropy is
>> predictable by would-be attackers, this should be good enough.
> 
> It's interesting to ask where the biggest risks are here.  My intuition is that the OS RNGs are often not all that secure, especially soon after boot.  So my first recommendation would be to draw 256 or so bits from RD_RAND and feed them into the OS RNG, with zero assessed entropy.  That gets the OS RNG to a strong state right away if RD_RAND isn't weak.  (Even some ways it could be weak would be masked by using it this way.)  That all by itself would get you to a secure system if the Intel RNG is good.  
> 
> You can then XOR the RD_RAND outputs into the RNG outputs to get (if the Intel RNG is as good as it claims) something close to full entropy outputs.  So long as the RD_RAND outputs aren't somehow predicting the OS RNG outputs, this can only improve the security of the OS RNG outputs.  
> 
> There are obviously many other perfectly fine ways to use them together--for example, initializing a good DRBG with the OS's entropy, and then reseeding it before every output with bits from RD_RAND.  Or initializing a DRBG with RD_RAND and sending in 256 bits of additional input from the OS RNG after it starts working.  
> 
> My sense is that the Intel RNG is almost certainly a huge improvement in security.  It's certainly smart to think about how to use it that doesn't fall apart if the RNG is broken somehow, but it's also smart to realize that what we have now apparently isn't all that great!

How do we safely initialize Yarrow or a another software RNG if the CPU's hardware RNG is compromised and there is no other source of entropy? This is a situation that is increasingly common in all solid-state black box devices, and is especially tricky at first startup, when keys used to manage such units are often generated.

The model I envision for a cooked CPU RNG seeds a deterministic RNG at power up with a secret constant and a small amount of entropy, maybe 30-40 bits.  This gives an attacker with knowledge of the scheme a relatively small search space to find any random bits generated, especially during initialization, while preventing easy detection. 

One approach to ameliorating the situation would be to apply a key stretching algorithm on the random bits obtained from the CPU RNG prior to using them to seed or stir Yarrow. A variant would be to use Yarrow itself as the key stretcher by seeding from the CPU RNG and then generating and discarding a large number of random bits (several seconds worth, say) from Yarrow before any production use. This would be about as effective as PBKDF2 and easier to implement, but it would be much better to use an algorithm like scrypt that employs more memory and CPU resources.  Such an algorithm would increase the cost of key recovery when using massively parallel hardware to search the restricted entropy space.  Note that unlike traditional key stretching, where it is important to have reproducible outcomes among different machines, here we can use expensive CPU capabilities like 80-bit floating point arithmetic that may available only in certain architectures or have minor variations between CPU implementations.  

While key stretchers cannot make a cryptographically weak system impregnable, they can greatly reduce the practicality of attacks. A key stretcher that increases the time to test a trial key from, say, a millisecond to ten seconds increases the work by a factor of 10,000 or ~13 bits. That could be enough to prevent en-mass probing and might force the attacker to reduce the real entropy used in the cooked RNG, making it more detectable.  

While I still think a second, auditable source of randomness should be required in any secure system, that is not happening in the near future and an all software solution like key stretching can be implemented today.

Arnold Reinhold







-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20131219/77bbcb22/attachment.html>


More information about the cryptography mailing list