[147274] in cryptography@c2.net mail archive
[Cryptography] The hypothetical random number generator backdoor
daemon@ATHENA.MIT.EDU (Phillip Hallam-Baker)
Tue Sep 24 09:42:09 2013
X-Original-To: cryptography@metzdowd.com
Date: Sun, 22 Sep 2013 20:09:09 -0400
From: Phillip Hallam-Baker <hallam@gmail.com>
To: "cryptography@metzdowd.com" <cryptography@metzdowd.com>
Errors-To: cryptography-bounces+crypto.discuss=bloom-picayune.mit.edu@metzdowd.com
--===============5836137601840350807==
Content-Type: multipart/alternative; boundary=f46d042ac0e84aea6f04e701d4f5
--f46d042ac0e84aea6f04e701d4f5
Content-Type: text/plain; charset=ISO-8859-1
So we think there is 'some kind' of backdoor in a random number generator.
One question is how the EC math might make that possible. Another is how
might the door be opened.
I was thinking about this and it occurred to me that it is fairly easy to
get a public SSL server to provide a client with a session key - just ask
to start a session.
Which suggests that maybe the backdoor is of the form that if you know
nonce i, and the private key to the backdoor, that reduces the search space
for finding nonce i+1.
Or maybe there is some sort of scheme where you get a lot of nonces from
the random number generator, tens of thousands and that allows the seed to
be unearthed.
Either way, the question is how to stop this side channel attack. One
simple way would be to encrypt the nonces from the RNG under a secret key
generated in some other fashion.
nonce = E (R, k)
Or hashing the RNG output and XORing with it
nonce = r XOR H (r)
Either way, there is an extra crypto system in the way that has to be
broken if a random number generator turns out to have some sort of
relationship between sequential outputs.
--
Website: http://hallambaker.com/
--f46d042ac0e84aea6f04e701d4f5
Content-Type: text/html; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable
<div dir=3D"ltr">So we think there is 'some kind' of backdoor in a =
random number generator. One question is how the EC math might make that po=
ssible. Another is how might the door be opened.<div><br></div><div><br></d=
iv>
<div>I was thinking about this and it occurred to me that it is fairly easy=
to get a public SSL server to provide a client with a session key - just a=
sk to start a session.</div><div><br></div><div>Which suggests that maybe t=
he backdoor is of the form that if you know nonce i, and the private key to=
the backdoor, that reduces the search space for finding nonce i+1.=A0</div=
>
<div><br></div><div>Or maybe there is some sort of scheme where you get a l=
ot of nonces from the random number generator, tens of thousands and that a=
llows the seed to be unearthed.</div><div><br></div><div><br></div><div>
Either way, the question is how to stop this side channel attack. One simpl=
e way would be to encrypt the nonces from the RNG under a secret key genera=
ted in some other fashion.=A0</div><div><br></div><div>nonce =3D E (R, k)</=
div>
<div><br></div><div>Or hashing the RNG output and XORing with it=A0</div><d=
iv><div><br></div><div>nonce =3D r =A0XOR H (r)</div><div><br></div><div><b=
r></div><div>Either way, there is an extra crypto system in the way that ha=
s to be broken if a random number generator turns out to have some sort of =
relationship between sequential outputs.</div>
<div><br></div><div><br></div>-- <br>Website: <a href=3D"http://hallambaker=
.com/">http://hallambaker.com/</a><br>
</div></div>
--f46d042ac0e84aea6f04e701d4f5--
--===============5836137601840350807==
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
--===============5836137601840350807==--
