[147927] in cryptography@c2.net mail archive
Re: [Cryptography] What's a Plausible Attack On Random Number
daemon@ATHENA.MIT.EDU (David Mercer)
Thu Oct 31 16:04:56 2013
X-Original-To: cryptography@metzdowd.com
In-Reply-To: <692B2B5B-0546-49B6-BDBF-4EF7C13D5956@lrw.com>
Date: Fri, 1 Nov 2013 02:48:19 +0800
From: David Mercer <radix42@gmail.com>
To: Jerry Leichter <leichter@lrw.com>
Cc: "cryptography@metzdowd.com List" <cryptography@metzdowd.com>
Errors-To: cryptography-bounces+crypto.discuss=bloom-picayune.mit.edu@metzdowd.com
--===============2279240460110913789==
Content-Type: multipart/alternative; boundary=089e01681470bbf42b04ea0de4ce
--089e01681470bbf42b04ea0de4ce
Content-Type: text/plain; charset=UTF-8
On Thu, Oct 31, 2013 at 11:09 PM, Jerry Leichter <leichter@lrw.com> wrote:
> I am the owner of a data center. I have some hundreds of physical
> machines, with old ones being decommissioned and new ones being added
> periodically. These run thousands of VM's that are created and destroyed
> much more frequently. The machines are interconnected by a number of
> high-speed (say 10GigE or better) networks, further partitioned for
> security purposes into multiple VLAN's. None of these networks are visible
> outside the boundaries of my data center. Connection to the Internet is
> via bastion routers. There's a DMZ, all the usual stuff. I have excellent
> physical security, and I regularly "patrol the perimeter", as well as the
> internal physical plant, so I assume that any attempt to run additional
> network links into my data center, plant significant hardware, etc., will
> be noticed fairly quickly. I'm actually paranoid enough that I've spec'ed
> conductive mesh throughout the outer structure, so the data center is
> effectively inside a Faraday cage (i.e., no magic r
> adio connections to the outside), and of course I check this periodically
> as well. As a result of all this, I choose not to consider physical
> threats; nor, because ultimately there's nothing I can do about them,
> on-going sophisticated insider attacks.
>
> I use a very simple random number generator: There's a "random pool" of a
> few thousand bits. At first boot, it's initially populated using whatever
> I can get my hands on principally the MAC address, any serial numbers
> available, etc. At shutdown, the state is stored locally; at restart, it's
> restored to the previous state. The first boot logic will wait for a
> significant period of time to gather entropy as I'll describe in a moment
> before allowing any processes that use random numbers to proceed. (Reboot
> may also wait a bit, but not nearly as long.)
>
> There is *exactly two* sources of entropy. The primary one is watching
> the network: Each time a network packet arrives, mix into my pool the full
> contents of the packet, the value of the real-time clock, and the value of
> the CPU cycle counter. The secondary source is other machines in the
> datacenter: Each machine will periodically get from some fraction of other
> machines scattered through the network some number of random bits,
> delivered in an encrypted packet using a key agreed upon between the two
> (based on their own randomness), and also mix that in. The mixing function
> is like that in the Linux RNG - "good enough but fast enough" - but not
> cryptographically secure as that's too expensive. To make up for that,
> periodically (say every millisecond or so) I also scramble the pool using a
> cryptographically secure 1-way hash.
> Whenever I've delivered more than (arbitrary number) 1/3 of the bits in
> the pool, I won't deliver any more until I've (a) done a cryptographically
> secure hash; (b) received at least N network packets; (c) received at least
> K updates from other machines. If network packets aren't arriving fast
> enough, I'll start listening promiscuously. If that doesn't give me
> enough, I can start sending "please send me a random update" requests to
> nodes I know about, which generates both those updates, and traffic.
> (During the first boot the "wait long enough" logic actually isn't based
> on time but on number of packets received.)
>
Your datacenter description is a pretty good match for what I've seen in
the last 10+ years for decently high-end facilities. The main flaw I can
see is in using the network for entropy on boot up, especially on first
boot. As there are quite a few services starting up that need good random
numbers in most systems, you are as you say going to wait a while to grab
enough entropy. Your entropy collection is going to have to start so early
in the boot process that you aren't going to be sending out much, if any,
network traffic, and are not going to be getting much of it.
You need to wait to start up any services that use encryption of any kind,
and which use it you can't know about ahead of time, so you need to start
before pretty much anything else. Which means before all the things that
might send out network traffic.
Listening promiscuously is NOT going to help, as you're going to be on a
dedicated switch port. The only thing to listen to is the switch. Maybe
some arp packets or similar??
Sticking a transparent bridge machine between a system being measured and a
switch port and sniffing everything travelling between them would let you
see what network traffic you get in a real world install and first boot
scenario.
"First boot" really refers to "first post-install boot", and is one of the
lowest entropy points in a systems life-cycle. If you start collecting
entropy during the installation, when lots of network packets are likely to
be flying around, and save the RNG state so that it has a decent amount of
entropy saved on "first boot". If your install process sucks down your
entropy pool, you might not have much to save, and you'd have to save the
amount of entropy estimated remaining when you saved it's state.
-David Mercer
--089e01681470bbf42b04ea0de4ce
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
<div dir=3D"ltr">On Thu, Oct 31, 2013 at 11:09 PM, Jerry Leichter <span dir=
=3D"ltr"><<a href=3D"mailto:leichter@lrw.com" target=3D"_blank">leichter=
@lrw.com</a>></span> wrote:<br><div class=3D"gmail_extra"><div class=3D"=
gmail_quote">
<blockquote class=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.8ex;border-=
left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;p=
adding-left:1ex">I am the owner of a data center. =C2=A0I have some hundred=
s of physical machines, with old ones being decommissioned and new ones bei=
ng added periodically. =C2=A0These run thousands of VM's that are creat=
ed and destroyed much more frequently. =C2=A0The machines are interconnecte=
d by a number of high-speed (say 10GigE or better) networks, further partit=
ioned for security purposes into multiple VLAN's. =C2=A0None of these n=
etworks are visible outside the boundaries of my data center. =C2=A0Connect=
ion to the Internet is via bastion routers. =C2=A0There's a DMZ, all th=
e usual stuff. =C2=A0I have excellent physical security, and I regularly &q=
uot;patrol the perimeter", as well as the internal physical plant, so =
I assume that any attempt to run additional network links into my data cent=
er, plant significant hardware, etc., will be noticed fairly quickly. =C2=
=A0I'm actually paranoid enough that I've spec'ed conductive me=
sh throughout the outer structure, so the data center is effectively inside=
a Faraday cage (i.e., no magic r<br>
=C2=A0adio connections to the outside), and of course I check this periodic=
ally as well. =C2=A0As a result of all this, I choose not to consider physi=
cal threats; nor, because ultimately there's nothing I can do about the=
m, on-going sophisticated insider attacks.<br>
<br>
I use a very simple random number generator: =C2=A0There's a "rand=
om pool" of a few thousand bits. =C2=A0At first boot, it's initial=
ly populated using whatever I can get my hands on principally the MAC addre=
ss, any serial numbers available, etc. =C2=A0At shutdown, the state is stor=
ed locally; at restart, it's restored to the previous state. =C2=A0The =
first boot logic will wait for a significant period of time to gather entro=
py as I'll describe in a moment before allowing any processes that use =
random numbers to proceed. =C2=A0(Reboot may also wait a bit, but not nearl=
y as long.)<br>
<br>
There is *exactly two* sources of entropy. =C2=A0The primary one is watchin=
g the network: =C2=A0Each time a network packet arrives, mix into my pool t=
he full contents of the packet, the value of the real-time clock, and the v=
alue of the CPU cycle counter. =C2=A0The secondary source is other machines=
in the datacenter: =C2=A0Each machine will periodically get from some frac=
tion of other machines scattered through the network some number of random =
bits, delivered in an encrypted packet using a key agreed upon between the =
two (based on their own randomness), and also mix that in. =C2=A0The mixing=
function is like that in the Linux RNG - "good enough but fast enough=
" - but not cryptographically secure as that's too expensive. =C2=
=A0To make up for that, periodically (say every millisecond or so) I also s=
cramble the pool using a cryptographically secure 1-way hash.</blockquote>
<div>=C2=A0</div><blockquote class=3D"gmail_quote" style=3D"margin:0px 0px =
0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-l=
eft-style:solid;padding-left:1ex"><span style=3D"font-family:arial,sans-ser=
if;font-size:13px">Whenever I've delivered more than (arbitrary number)=
1/3 of the bits in the pool, I won't deliver any more until I've (=
a) done a cryptographically secure hash; (b) received at least N network pa=
ckets; (c) received at least K updates from other machines. =C2=A0If networ=
k packets aren't arriving fast enough, I'll start listening promisc=
uously. =C2=A0If that doesn't give me enough, I can start sending "=
;please send me a random update" requests to nodes I know about, which=
generates both those updates, and traffic. =C2=A0(During the first boot th=
e "wait long enough" logic actually isn't based on time but o=
n number of packets received.)</span><br>
</blockquote></div><br></div><div class=3D"gmail_extra">Your datacenter des=
cription is a pretty good match for what I've seen in the last 10+ year=
s for decently high-end facilities. The main flaw I can see is in using the=
network for entropy on boot up, especially on first boot. As there are qui=
te a few services starting up that need good random numbers in most systems=
, you are as you say going to wait a while to grab enough entropy. Your ent=
ropy collection is going to have to start so early in the boot process that=
you aren't going to be sending out much, if any, network traffic, and =
are not going to be getting much of it. =C2=A0</div>
<div class=3D"gmail_extra"><br></div><div class=3D"gmail_extra">You need to=
wait to start up any services that use encryption of any kind, and which u=
se it you can't know about ahead of time, so you need to start before p=
retty much anything else. Which means before all the things that might send=
out network traffic.</div>
<div class=3D"gmail_extra"><br></div><div class=3D"gmail_extra">Listening p=
romiscuously is NOT going to help, as you're going to be on a dedicated=
switch port. The only thing to listen to is the switch. Maybe some arp pac=
kets or similar??=C2=A0</div>
<div class=3D"gmail_extra"><br></div><div class=3D"gmail_extra">Sticking a =
transparent bridge machine between a system being measured and a switch por=
t and sniffing everything travelling between them would let you see what ne=
twork traffic you get in a real world install and first boot scenario.<br>
</div><div class=3D"gmail_extra"><br></div><div class=3D"gmail_extra">"=
;First boot" really refers to "first post-install boot", and=
is one of the lowest entropy points in a systems life-cycle. If you start =
collecting entropy during the installation, when lots of network packets ar=
e likely to be flying around, and save the RNG state so that it has a decen=
t amount of entropy saved on "first boot". If your install proces=
s sucks down your entropy pool, you might not have much to save, and you=
9;d have to save the amount of entropy estimated remaining when you saved i=
t's state.=C2=A0</div>
<div class=3D"gmail_extra"><br></div><div class=3D"gmail_extra">-David Merc=
er</div></div>
--089e01681470bbf42b04ea0de4ce--
--===============2279240460110913789==
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
--===============2279240460110913789==--
