[148396] in cryptography@c2.net mail archive
Re: [Cryptography] Fun with hardware RNGS: the Infinite Noise
daemon@ATHENA.MIT.EDU (Bill Cox)
Mon Dec 9 18:48:49 2013
X-Original-To: cryptography@metzdowd.com
In-Reply-To: <CAMm+Lwi9qQz=yyB3_3VOaicsM=WW=OLeSnkHU6hAv4OUznG6ng@mail.gmail.com>
Date: Mon, 9 Dec 2013 17:21:05 -0500
From: Bill Cox <waywardgeek@gmail.com>
To: "cryptography@metzdowd.com" <cryptography@metzdowd.com>
Errors-To: cryptography-bounces+crypto.discuss=bloom-picayune.mit.edu@metzdowd.com
--===============1225615800007127687==
Content-Type: multipart/alternative; boundary=089e015384d66f23c204ed216916
--089e015384d66f23c204ed216916
Content-Type: text/plain; charset=ISO-8859-1
On Sun, Dec 8, 2013 at 10:23 PM, Phillip Hallam-Baker <hallam@gmail.com>wrote:
> What about RF emissions made by the circuit?
>
> This contraption seems like it would bleed its output into the RF
> spectrum.
>
> --
> Website: http://hallambaker.com/
>
Like any clocked digital chip, it will put out some RF, though I expect it
to be low. This is a slow low power .35u CMOS process, with about 0.4
milliwatt of power per Infinite Noise Multiplier, and there will be 16 of
those. The clocked comparator in each INM is differential, and should
generate nearly the same power spike for a 1 or a 0. All other power drawn
by each INM is in the form of constant current sources in the voltage
buffers, so they should be very hard to read from noise on external power
pins. Shorting the .1pF caps to each other on clock edges doesn't impact
AVDD or AVSS currents, and also should not be detectable from external
power pins. I do not know if this would be detectable from outside the
package with an RF detector. Does anyone have a cool application for
microcontroller with a true RNG that needs super-secret random data that
remains secret even when the attacker has a logic analyzer attached to the
chip and some sort of RF detector? I would need advice on what sorts of
on-chip events are detectable. I don't have any equipment capable of
detecting such low level RF spikes.
I had some fun yesterday and wrote code to predict the output bits based on
the previous 8. It achieved a 74.5% success rate predicting the SPICE
output, which is about what I expected. Today wrote code to eliminate most
of the bias and correlations as a post-process, and it defeats my
prediction code. The algorithm is pretty cool. I think I can get the data
to be around 99% free of correlation and bias, while compressing this data
by about 2X. This would make the bias drop by a factor of 0.02 for each
compressed bit XORed together, rather than the 0.5 I get now, meaning I get
about a 2.8X improvement in output rate at the same quality. That would
provide bits with no more than about 1e-24 of non-randomness leading to a
rate of about 5 M-bits/sec.
The bias/correlation removal algorithm has two parts. First, read about a
megabyte (8 seconds worth) from a given channel, and use it to gather
prediction statistics. For each place a given 8-bit sequence occurs,
record how many times the next bit is a 1 and how many times it's a 0 in
arrays called 'zeros' and 'ones'. Then, as bits come in, I run the
following C code to remove the detected bias and correlation:
void removeBias(int *data, int length) {
double prob, lower = 0.0, upper = 1.0;
int i;
unsigned char value = 0;
for(i = 0; i < length; i++) {
if(data[i]) {
prob = ((double)zeros[value])/(ones[value] + zeros[value]);
lower += prob*(upper - lower);
} else {
prob = ((double)ones[value])/(ones[value] + zeros[value]);
upper -= prob*(upper - lower);
}
while(lower >= 0.5 || upper <= 0.5) {
if(upper <= 0.5) {
upper *= 2.0;
lower *= 2.0;
printf("0");
} else {
printf("1");
upper = 2.0*upper - 1.0;
lower = 2.0*lower - 1.0;
}
}
value <<= 1;
if(data[i]) {
value |= 1;
}
}
printf("\n");
}
For use in one-time-pad encryption or generating keys, I'd still want to
XOR 14 of these 2-to-1 compressed bits together, and then run a
cryptographic randomizer on the results. I don't think I use any hash
function like SHA-256 which is not reversible, unless someone convinces me
that it does not introduce correlations. Any permutation should be fine,
such as encrypting the random data with block-chained AES-256 and a random
key. Does that sound reasonable?
--089e015384d66f23c204ed216916
Content-Type: text/html; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable
<div dir=3D"ltr"><div class=3D"gmail_extra"><div class=3D"gmail_quote">On S=
un, Dec 8, 2013 at 10:23 PM, Phillip Hallam-Baker <span dir=3D"ltr"><<a =
href=3D"mailto:hallam@gmail.com" target=3D"_blank">hallam@gmail.com</a>>=
</span> wrote:<br>
<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"><div dir=3D"ltr"><div class=3D"gmail_extra"><div class=3D"=
gmail_quote">
<div>What about RF emissions made by the circuit?</div><div><br></div><div>=
This contraption seems like it would bleed its output into the RF spectrum.=
=A0</div><span class=3D""><font color=3D"#888888">
<div>=A0</div></font></span></div><span class=3D""><font color=3D"#888888">=
-- <br>Website: <a href=3D"http://hallambaker.com/" target=3D"_blank">http:=
//hallambaker.com/</a><br>
</font></span></div></div>
</blockquote></div><br></div><div class=3D"gmail_extra"><font face=3D"arial=
, sans-serif"><span style=3D"font-size:19px">Like any clocked digital chip,=
it will put out some RF, though I expect it to be low. =A0This is a slow l=
ow power .35u CMOS process, with about 0.4 milliwatt of power per Infinite =
Noise Multiplier, and there will be 16 of those. =A0The clocked comparator =
in each INM is differential, and should generate nearly the same power spik=
e for a 1 or a 0. =A0All other power drawn by each INM is in the form of co=
nstant current sources in the voltage buffers, so they should be very hard =
to read from noise on external power pins. =A0Shorting the .1pF caps to eac=
h other on clock edges doesn't impact AVDD or AVSS currents, and also s=
hould not be detectable from external power pins. =A0I do not know if this =
would be detectable from outside the package with an RF detector. =A0Does a=
nyone have a cool application for microcontroller with a true RNG that need=
s super-secret random data that remains secret even when the attacker has a=
logic analyzer attached to the chip and some sort of RF detector? =A0I wou=
ld need advice on what sorts of on-chip events are detectable. =A0I don'=
;t have any equipment capable of detecting such low level RF spikes.</span>=
</font><div style=3D"font-family:arial,sans-serif;font-size:19px">
<br></div><div style=3D"font-family:arial,sans-serif;font-size:19px">I had =
some fun yesterday and wrote code to predict the output bits based on the p=
revious 8. =A0It achieved a 74.5% success rate predicting the SPICE output,=
which is about what I expected. =A0Today wrote code to eliminate most of t=
he bias and correlations as a post-process, and it defeats my prediction co=
de. =A0The algorithm is pretty cool. =A0I think I can get the data to be ar=
ound 99% free of correlation and bias, while compressing this data by about=
2X. =A0This would make the bias drop by a factor of 0.02 for each compress=
ed bit XORed together, rather than the 0.5 I get now, meaning I get about a=
2.8X improvement in output rate at the same quality. =A0That would provide=
bits with no more than about 1e-24 of non-randomness leading to a rate of =
about 5 M-bits/sec.</div>
<div style=3D"font-family:arial,sans-serif;font-size:19px"><br></div><div s=
tyle=3D"font-family:arial,sans-serif;font-size:19px">The bias/correlation r=
emoval algorithm has two parts. =A0First, read about a megabyte (8 seconds =
worth) from a given channel, and use it to gather prediction statistics. =
=A0For each place a given 8-bit sequence occurs, record how many times the =
next bit is a 1 and how many times it's a 0 in arrays called 'zeros=
' and 'ones'. =A0Then, as bits come in, I run the following C c=
ode to remove the detected bias and correlation:</div>
<div style=3D"font-family:arial,sans-serif;font-size:19px"><br></div><div><=
div><font face=3D"arial, sans-serif"><span style=3D"font-size:19px">void re=
moveBias(int *data, int length) {</span></font></div><div><font face=3D"ari=
al, sans-serif"><span style=3D"font-size:19px">=A0 =A0 double prob, lower =
=3D 0.0, upper =3D 1.0;</span></font></div>
<div><font face=3D"arial, sans-serif"><span style=3D"font-size:19px">=A0 =
=A0 int i;</span></font></div><div><span style=3D"font-size:19px;font-famil=
y:arial,sans-serif">=A0 =A0 unsigned char value =3D 0;</span><br></div><div=
><font face=3D"arial, sans-serif"><span style=3D"font-size:19px">=A0 =A0 fo=
r(i =3D 0; i < length; i++) {</span></font></div>
<div><span style=3D"font-size:19px;font-family:arial,sans-serif">=A0 =A0 =
=A0 =A0 if(data[i]) {</span><br></div><div><font face=3D"arial, sans-serif"=
><span style=3D"font-size:19px">=A0 =A0 =A0 =A0 =A0 =A0 prob =3D ((double)z=
eros[value])/(ones[value] + zeros[value]);</span></font></div>
<div><font face=3D"arial, sans-serif"><span style=3D"font-size:19px">=A0 =
=A0 =A0 =A0 =A0 =A0 lower +=3D prob*(upper - lower);</span></font></div><di=
v><font face=3D"arial, sans-serif"><span style=3D"font-size:19px">=A0 =A0 =
=A0 =A0 } else {</span></font></div>
<div><font face=3D"arial, sans-serif"><span style=3D"font-size:19px">=A0 =
=A0 =A0 =A0 =A0 =A0 prob =3D ((double)ones[value])/(ones[value] + zeros[val=
ue]);</span></font></div><div><font face=3D"arial, sans-serif"><span style=
=3D"font-size:19px">=A0 =A0 =A0 =A0 =A0 =A0 upper -=3D prob*(upper - lower)=
;</span></font></div>
<div><font face=3D"arial, sans-serif"><span style=3D"font-size:19px">=A0 =
=A0 =A0 =A0 }</span></font></div><div><font face=3D"arial, sans-serif"><spa=
n style=3D"font-size:19px">=A0 =A0 =A0 =A0 while(lower >=3D 0.5 || upper=
<=3D 0.5) {</span></font></div>
<div><font face=3D"arial, sans-serif"><span style=3D"font-size:19px">=A0 =
=A0 =A0 =A0 =A0 =A0 if(upper <=3D 0.5) {</span></font></div><div><font f=
ace=3D"arial, sans-serif"><span style=3D"font-size:19px">=A0 =A0 =A0 =A0 =
=A0 =A0 =A0 =A0 upper *=3D 2.0;</span></font></div>
<div><font face=3D"arial, sans-serif"><span style=3D"font-size:19px">=A0 =
=A0 =A0 =A0 =A0 =A0 =A0 =A0 lower *=3D 2.0;</span></font></div><div><font f=
ace=3D"arial, sans-serif"><span style=3D"font-size:19px">=A0 =A0 =A0 =A0 =
=A0 =A0 =A0 =A0 printf("0");</span></font></div>
<div><font face=3D"arial, sans-serif"><span style=3D"font-size:19px">=A0 =
=A0 =A0 =A0 =A0 =A0 } else {</span></font></div><div><font face=3D"arial, s=
ans-serif"><span style=3D"font-size:19px">=A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 p=
rintf("1");</span></font></div>
<div><font face=3D"arial, sans-serif"><span style=3D"font-size:19px">=A0 =
=A0 =A0 =A0 =A0 =A0 =A0 =A0 upper =3D 2.0*upper - 1.0;</span></font></div><=
div><font face=3D"arial, sans-serif"><span style=3D"font-size:19px">=A0 =A0=
=A0 =A0 =A0 =A0 =A0 =A0 lower =3D 2.0*lower - 1.0;</span></font></div>
<div><font face=3D"arial, sans-serif"><span style=3D"font-size:19px">=A0 =
=A0 =A0 =A0 =A0 =A0 }</span></font></div><div><span style=3D"font-size:19px=
;font-family:arial,sans-serif">=A0 =A0 =A0 =A0 }</span><br></div><div><div>=
<font face=3D"arial, sans-serif"><span style=3D"font-size:19px">=A0 =A0 =A0=
=A0 value <<=3D 1;</span></font></div>
<div><font face=3D"arial, sans-serif"><span style=3D"font-size:19px">=A0 =
=A0 =A0 =A0 if(data[i]) {</span></font></div><div><font face=3D"arial, sans=
-serif"><span style=3D"font-size:19px">=A0 =A0 =A0 =A0 =A0 =A0 value |=3D 1=
;</span></font></div><div><font face=3D"arial, sans-serif"><span style=3D"f=
ont-size:19px">=A0 =A0 =A0 =A0 }</span></font></div>
<div><font face=3D"arial, sans-serif"><span style=3D"font-size:19px">=A0 =
=A0 }</span></font></div><div><font face=3D"arial, sans-serif"><span style=
=3D"font-size:19px">=A0 =A0 printf("\n");</span></font></div><div=
><font face=3D"arial, sans-serif"><span style=3D"font-size:19px">}</span></=
font></div>
<div style=3D"font-family:arial,sans-serif;font-size:19px"><br></div></div>=
</div><div style=3D"font-family:arial,sans-serif;font-size:19px">For use in=
one-time-pad encryption or generating keys, I'd still want to XOR 14 o=
f these 2-to-1 compressed bits together, and then run a cryptographic rando=
mizer on the results. =A0I don't think I use any hash function like SHA=
-256 which is not reversible, unless someone convinces me that it does not =
introduce correlations. =A0Any permutation should be fine, such as encrypti=
ng the random data with block-chained AES-256 and a random key. =A0Does tha=
t sound reasonable?</div>
</div></div>
--089e015384d66f23c204ed216916--
--===============1225615800007127687==
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
--===============1225615800007127687==--
