[148518] in cryptography@c2.net mail archive
Re: [Cryptography] Fwd: [IP] 'We cannot trust' Intel and
daemon@ATHENA.MIT.EDU (Arnold Reinhold)
Thu Dec 19 11:23:33 2013
X-Original-To: cryptography@metzdowd.com
From: Arnold Reinhold <agr@me.com>
Date: Thu, 19 Dec 2013 07:56:36 -0500
To: John Kelsey <crypto.jmk@gmail.com>
Cc: nico@cryptonector.com, Charles Jackson <clj@jacksons.net>,
"cryptography@metzdowd.com" <cryptography@metzdowd.com>
Errors-To: cryptography-bounces+crypto.discuss=bloom-picayune.mit.edu@metzdowd.com
--===============5030085386095847434==
Content-type: multipart/alternative;
boundary="Apple-Mail=_B7FEAD6E-A822-4AE6-9CB5-4D3F752EE2C1"
--Apple-Mail=_B7FEAD6E-A822-4AE6-9CB5-4D3F752EE2C1
Content-Transfer-Encoding: quoted-printable
Content-Type: text/plain;
charset=us-ascii
On 16 Dec 2013 12:52 John Kelsey wrote:
> On Dec 13, 2013, at 2:02 PM, Nico Williams <nico@cryptonector.com> =
wrote:
>=20
>> 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.
>>=20
>> 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.
>=20
> 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. =20
>=20
> 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. =20
>=20
> 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. =20
>=20
> 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.=20
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. =20
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. =20
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
--Apple-Mail=_B7FEAD6E-A822-4AE6-9CB5-4D3F752EE2C1
Content-Transfer-Encoding: quoted-printable
Content-Type: text/html;
charset=us-ascii
<html><head><meta http-equiv=3D"Content-Type" content=3D"text/html =
charset=3Dus-ascii"></head><body style=3D"word-wrap: break-word; =
-webkit-nbsp-mode: space; -webkit-line-break: =
after-white-space;">On 16 Dec 2013 12:52 John Kelsey =
wrote:<br><blockquote type=3D"cite">On Dec 13, 2013, at 2:02 PM, Nico =
Williams <<a =
href=3D"mailto:nico@cryptonector.com">nico@cryptonector.com</a>> =
wrote:<br><br><blockquote type=3D"cite">On Fri, Dec 13, 2013 at =
01:24:21PM -0500, John Kelsey wrote:<br><blockquote type=3D"cite">Why =
not just XOR RD_RAND outputs with Yarrow outputs? That =
guarantees<br>strong results if either one is =
good.<br></blockquote><br>Yes, to reprise the /dev/*random robustness =
thread, we need as many<br>inputs to the CSPRNG as possible. Heck, =
even a constant seed and a seed<br>saved from the previous boot. =
As long as the PRNG is cryptographically<br>secure and at least =
one source of boot-time (and subsequent) entropy is<br>predictable by =
would-be attackers, this should be good enough.<br></blockquote><br>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. <br><br>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. <br><br>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. <br><br>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!<br></blockquote><br><div><div style=3D"margin: 0px;">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.</div><div style=3D"margin: 0px; =
min-height: 14px;"><br></div><div style=3D"margin: 0px;">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. </div><div =
style=3D"margin: 0px; min-height: 14px;"><br></div><div style=3D"margin: =
0px;">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. </div><div =
style=3D"margin: 0px; min-height: 14px;"><br></div><div style=3D"margin: =
0px;">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. </div><div style=3D"margin: 0px; =
min-height: 14px;"><br></div><div style=3D"margin: 0px;">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.</div><div style=3D"margin: 0px; min-height: 14px;"><br></div><div =
style=3D"margin: 0px;">Arnold Reinhold</div><div style=3D"margin: 0px; =
min-height: 14px;"><br></div><div style=3D"margin: 0px; min-height: =
14px;"><br></div><div style=3D"margin: 0px; min-height: =
14px;"><br></div><div style=3D"margin: 0px; min-height: =
14px;"><br></div><div style=3D"margin: 0px; min-height: =
14px;"><br></div><div style=3D"margin: 0px; min-height: =
14px;"><br></div><div style=3D"margin: 0px; min-height: =
14px;"><br></div></div></body></html>=
--Apple-Mail=_B7FEAD6E-A822-4AE6-9CB5-4D3F752EE2C1--
--===============5030085386095847434==
Content-Type: text/plain; charset="us-ascii"
MIME-Version: 1.0
Content-Transfer-Encoding: 7bit
Content-Disposition: inline
_______________________________________________
The cryptography mailing list
cryptography@metzdowd.com
http://www.metzdowd.com/mailman/listinfo/cryptography
--===============5030085386095847434==--
