[147869] in cryptography@c2.net mail archive
Re: [Cryptography] [RNG] /dev/random initialisation
daemon@ATHENA.MIT.EDU (John Kelsey)
Mon Oct 28 15:20:35 2013
X-Original-To: cryptography@metzdowd.com
In-Reply-To: <526D90EA.50405@av8n.com>
From: John Kelsey <crypto.jmk@gmail.com>
Date: Mon, 28 Oct 2013 14:54:59 -0400
To: John Denker <jsd@av8n.com>
Cc: Cryptography <cryptography@metzdowd.com>
Errors-To: cryptography-bounces+crypto.discuss=bloom-picayune.mit.edu@metzdowd.com
--===============8633299880073033395==
Content-Type: multipart/alternative;
boundary=Apple-Mail-089C836F-094A-41B3-96CE-53C360BCE705
Content-Transfer-Encoding: 7bit
--Apple-Mail-089C836F-094A-41B3-96CE-53C360BCE705
Content-Type: text/plain;
charset=us-ascii
Content-Transfer-Encoding: quoted-printable
On Oct 27, 2013, at 6:17 PM, John Denker <jsd@av8n.com> wrote:
...
> On 10/24/2013 07:59 AM, John Kelsey wrote:
>=20
>> a. Get 256 bits of entropy from the OS.
>> b. Get 256 bits of entropy from the hardware entropy source.
>> c. Ping several hosts on the internet and measure the response time, and=
fold that into your seed.
>> d. Fold your ethernet address, IP address, and serial number into the se=
ed.
>> e. Fold the installed-at-birth secret 128 bit value from your device int=
o the seed.
>>=20
>> Initialize a PRNG with all that, and the attacker is in an extremely
>> hard place, as he has to be able to guess all five elements. (d)
>> isn't all that hard to guess, but the rest will in general be very
>> hard to guess.
>=20
> Some comments:
>=20
> a) If you have 256 bits of honest-to-goodness entropy from
> /any/ source, OS or otherwise, then that's more than enough
> to seed the PRNG, and nothing on the list matters.
Right. My point is that we want to consider the possibility that one or mor=
e of our sources aren't good, but we don't know which. For any minimally de=
cent PRNG, if we feed it 128 bits of entropy plus a million bits the attacke=
r gets to choose, we should still get a secure PRNG state. =20
So, we get 256 bits of entropy from the OS. If the OS can actually find tha=
t much entropy, then we're done--we are now in a secure state. If not, thou=
gh, the hardware entropy source can come to our rescue. But suppose the har=
dware RNG is cooked or broken, and the OS isn't able to collect enough entro=
py. Then, what should we do? =20
Well, let's think about our attacker. What we really care about w.r.t. PRNG=
seeding is not the ultimate question of how unpredictable the seed is. We c=
are about how unpredictable it is to the attacker. =20
So, let's partition the attacker space into two categories--some attackers a=
re watching your network traffic at the time you generate your key, and some=
aren't. If we are sampling the high-speed counter every time a packet arri=
ves and folding that into our PRNG seed, then it seems almost certain to me t=
hat an attacker who isn't watching your network traffic right then is going t=
o be unable to reconstruct exactly when each packet arrived. Attackers that=
are not monitoring your network traffic right then are just ruled out. To m=
ake this work even better, do some kind of broadcast on the local network, a=
sking any other devices to respond with 256 bits from /dev/urandom or the sy=
stem PRNG. An attacker who is eavesdropping will see this and you won't ben=
efit from it, but attackers who aren't eavesdropping on your network traffic=
just don't know what was sent, and so you have a secure PRNG seed with resp=
ect to those attackers. =20
Now, let's partition the attacker space into two different categories--those=
who eventually get hold of your machine, and those who do not. If there is=
a fixed 128 bit random number installed on your machine (different for ever=
y one), and you feed that into your PRNG seed, then the attackers who don't e=
ventually get hold of your machine are lost--they simply don't know those 12=
8 bits, and can't guess them, so your PRNG is secure w.r.t. them. (A stored=
seed is even better, though it's not clear whether or not the previous PRNG=
states will be recoverable. In its absense, I'm not sure if there's anythi=
ng else that could be used to get some unique information from the machine t=
hat only someone on the machine could get.) =20
What we can get from this is that, even if the OS and hardware RNGs are weak=
, the only attackers who can exploit this are those who were eavesdropping o=
n your net traffic right before you generated your keypair, and who got hold=
of your machine afterward. Other attackers simply can't get anywhere. =20
I'd love to think of some more classes of attacker we could rule out entirel=
y. Even a high precision timestamp doesn't do much good, since there are on=
ly so many times this particular device could have generated their key. =20
Now, at last, we come to the "salt" inputs--ethernet address, IP address, se=
rial number, etc. (Timestamp is good here, too.) These aren't intended to p=
rovide any entropy. Instead, their goal is to work like salt in a password h=
ashing scheme. =20
Let's suppose the attacker has a predictive model that lets him guess a lot,=
but not all, of our entropy. By including the "salt" inputs, he is forced t=
o rerun his attack on each machine with the same configuration, rather than b=
eing able to run his attack once and then look for matching keypairs from ev=
ery machine with the same configuration. =20
--John=
--Apple-Mail-089C836F-094A-41B3-96CE-53C360BCE705
Content-Type: text/html;
charset=utf-8
Content-Transfer-Encoding: quoted-printable
<html><head><meta http-equiv=3D"content-type" content=3D"text/html; charset=3D=
utf-8"></head><body dir=3D"auto"><div>On Oct 27, 2013, at 6:17 PM, John Denk=
er <<a href=3D"mailto:jsd@av8n.com">jsd@av8n.com</a>> wrote:</div><div=
><span style=3D"color: rgb(0, 80, 1); ">...</span></div><blockquote type=3D"=
cite"><div><span>On 10/24/2013 07:59 AM, John Kelsey wrote:</span><br><span>=
</span><br><blockquote type=3D"cite"><span>a. Get 256 bits of entropy f=
rom the OS.</span><br></blockquote><blockquote type=3D"cite"><span>b. =
Get 256 bits of entropy from the hardware entropy source.</span><br></blockq=
uote><blockquote type=3D"cite"><span>c. Ping several hosts on the inte=
rnet and measure the response time, and fold that into your seed.</span><br>=
</blockquote><blockquote type=3D"cite"><span>d. Fold your ethernet add=
ress, IP address, and serial number into the seed.</span><br></blockquote><b=
lockquote type=3D"cite"><span>e. Fold the installed-at-birth secret 12=
8 bit value from your device into the seed.</span><br></blockquote><blockquo=
te type=3D"cite"><span></span><br></blockquote><blockquote type=3D"cite"><sp=
an>Initialize a PRNG with all that, and the attacker is in an extremely</spa=
n><br></blockquote><blockquote type=3D"cite"><span>hard place, as he has to b=
e able to guess all five elements. (d)</span><br></blockquote><blockquote ty=
pe=3D"cite"><span>isn't all that hard to guess, but the rest will in general=
be very</span><br></blockquote><blockquote type=3D"cite"><span>hard to gues=
s.</span><br></blockquote><span></span><br><span>Some comments:</span><br><s=
pan></span><br><span>a) If you have 256 bits of honest-to-goodness entropy f=
rom</span><br><span> /any/ source, OS or otherwise, then that's more than en=
ough</span><br><span> to seed the PRNG, and nothing on the list matters.</sp=
an><br></div></blockquote><div><br></div><div>Right. My point is that w=
e want to consider the possibility that one or more of our sources aren't go=
od, but we don't know which. For any minimally decent PRNG, if we feed=
it 128 bits of entropy plus a million bits the attacker gets to choose, we s=
hould still get a secure PRNG state. </div><div><br></div><div>So, we g=
et 256 bits of entropy from the OS. If the OS can actually find that m=
uch entropy, then we're done--we are now in a secure state. If not, th=
ough, the hardware entropy source can come to our rescue. But suppose t=
he hardware RNG is cooked or broken, and the OS isn't able to collect enough=
entropy. Then, what should we do? </div><div><br></div><div>Wel=
l, let's think about our attacker. What we really care about w.r.t. PR=
NG seeding is not the ultimate question of how unpredictable the seed is. &n=
bsp;We care about how unpredictable it is to the attacker. </div><div>=
<br></div><div>So, let's partition the attacker space into two categories--s=
ome attackers are watching your network traffic at the time you generate you=
r key, and some aren't. If we are sampling the high-speed counter ever=
y time a packet arrives and folding that into our PRNG seed, then it seems a=
lmost certain to me that an attacker who isn't watching your network traffic=
right then is going to be unable to reconstruct exactly when each packet ar=
rived. Attackers that are not monitoring your network traffic right th=
en are just ruled out. To make this work even better, do some kind of b=
roadcast on the local network, asking any other devices to respond with 256 b=
its from /dev/urandom or the system PRNG. An attacker who is eavesdrop=
ping will see this and you won't benefit from it, but attackers who aren't e=
avesdropping on your network traffic just don't know what was sent, and so y=
ou have a secure PRNG seed with respect to those attackers. </div><div=
><br></div><div>Now, let's partition the attacker space into two different c=
ategories--those who eventually get hold of your machine, and those who do n=
ot. If there is a fixed 128 bit random number installed on your machin=
e (different for every one), and you feed that into your PRNG seed, then the=
attackers who don't eventually get hold of your machine are lost--they simp=
ly don't know those 128 bits, and can't guess them, so your PRNG is secure w=
.r.t. them. (A stored seed is even better, though it's not clear wheth=
er or not the previous PRNG states will be recoverable. In its absense=
, I'm not sure if there's anything else that could be used to get some uniqu=
e information from the machine that only someone on the machine could get.) &=
nbsp;</div><div><br></div><div>What we can get from this is that, even if th=
e OS and hardware RNGs are weak, the only attackers who can exploit this are=
those who were eavesdropping on your net traffic right before you generated=
your keypair, and who got hold of your machine afterward. Other attac=
kers simply can't get anywhere. </div><div><br></div><div>I'd love to t=
hink of some more classes of attacker we could rule out entirely. Even=
a high precision timestamp doesn't do much good, since there are only so ma=
ny times this particular device could have generated their key. </div>=
<div><br></div><div>Now, at last, we come to the "salt" inputs--ethernet add=
ress, IP address, serial number, etc. (Timestamp is good here, too.) &=
nbsp;These aren't intended to provide any entropy. Instead, their goal=
is to work like salt in a password hashing scheme. </div><div><br></d=
iv><div>Let's suppose the attacker has a predictive model that lets him gues=
s a lot, but not all, of our entropy. By including the "salt" inputs, h=
e is forced to rerun his attack on each machine with the same configuration,=
rather than being able to run his attack once and then look for matching ke=
ypairs from every machine with the same configuration. </div><div><br>=
</div><div>--John</div></body></html>=
--Apple-Mail-089C836F-094A-41B3-96CE-53C360BCE705--
--===============8633299880073033395==
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
--===============8633299880073033395==--
