Re: How to make *real* random bits.
Thus spake Poul-Henning Kamp ([EMAIL PROTECTED]): between events. Because of this your T3 value can be considered the T1 value for the next random bit you generate. No it cannot. If you did that then the probability would skew from bit to bit. If the (t3-t2) was large bit N == 1 and the probability of bit N+1 == 0 is .5 then. Yes, but you can use the 3rd bit as bit 1 for the next step. With 15 events, that gives 7 bits/second: bit 1: 3 1 (is event 3 of the last bit) bit 2: 2 1st bit 3: 3 1 bit 4: 2 2nd bit 5: 3 1 bit 6: 2 3rd bit 7: 3 1 bit 8: 2 4th bit 9: 3 1 bit 10: 2 5th bit 11: 3 1 bit 12: 2 6th bit 13: 3 1 bit 14: 2 7th bit 15: 3 1 (is event 1 for the next bit) Alex -- cat: /home/alex/.sig: No such file or directory To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-hackers" in the body of the message
Re: How to make *real* random bits.
On Wed, 02 Aug 2000 06:15:41 +0200, Poul-Henning Kamp [EMAIL PROTECTED] wrote: If I generate true random bits it takes 3 timestamps to get one bit of randomness: ++--+---+--+-+ T1 T2 T3 T4 T5T6 if (T2 - T1 T3 - T2) return 0; else if (T2 - T1 T3 - T2) return 1; else try again. ... Because of this your T3 value can be considered the T1 value for the next random bit you generate. No it cannot. If you did that then the probability would skew from bit to bit. If the (t3-t2) was large bit N == 1 and the probability of bit N+1 == 0 is .5 then. I don't follow. Taking the extended timeline above, and shortening your algorithm above to (T2-T1)(T3-T2): Since the decay intervals are random[1], there is no correlation between (T2-T1), (T3-T2), (T4-T3), etc. I can see that it wouldn't be safe to use (T2-T1)(T3-T2) and (T3-T2)(T4-T3) since this would introduce a (T2-T1)(T4-T3) correlation in adjacent bits. I don't see how there is any correlation between (T2-T1)(T3-T2) and (T4-T3)(T5-T4). This effectively gives you 1 bit of randomness for every two time intervals. (Though, ignoring geek value, I suspect a reverse-biased transistor BE junction would be an easier source of randomness). [1] Subject to slight corrections as a result of the half-lives of the elements in the decay chain. Peter To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-hackers" in the body of the message
Re: How to make *real* random bits.
Poul-Henning Kamp wrote: Ok, some people just can't leave an open end dangling (people like me for instance :-) I located a surplus german geiger counter cheaply [1], I have always wanted to have one anyway, and in my junkbox I already had an old smoke alarm [2]. The Geiger counter has a thin-walled tube which takes about 15 events per second from the Am-241 source in the smoke alarm. Nice. If you're thinking about this a possible commercial product, I'd be a bit dubious though. Even if Am-241 is just an alpha emitter, I'd still be a bit worried about having it built into the guts of a PC. Perhaps there is a cheaper alternative as a good source of random bits. As a former NMR spectroscopist, I know that if you take an Inductive - Capacitive resonant tuned circuit (typically somewhere in the range 5MHz -- 1GHz for NMR), carefully sheilded from any rf interference and amplify the bejezus out of the (non)-output, feed the result into a heterodyne radio receiver tuned to the same frequency as the circuit and then digitise the audio frequency result, and you should end up with a pretty perfect white noise signal. That signal is principally due to the random thermal motion of electrons in the circuitry. What's more, if you choose the operating frequencies wisely, such a circuit can be put together from off-the-shelf components cheaply. Standard audio ADC's should give you about 20,000 samples per second. Efficiently converting the normally distributed white noise samples to the evenly distributed random numbers most computer uses require is left as an exercise for the student. Matthew -- Certe, Toto, sentio nos in Kansate non iam adesse. Dr. Matthew Seaman, Inpharmatica Ltd, 60 Charlotte St, London, W1T 2NU Tel: +44 20 7631 4644 x229 Fax: +44 20 7631 4844 To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-hackers" in the body of the message
Re: How to make *real* random bits.
In message [EMAIL PROTECTED], Matthew Seaman writes: Poul-Henning Kamp wrote: Ok, some people just can't leave an open end dangling (people like me for instance :-) I located a surplus german geiger counter cheaply [1], I have always wanted to have one anyway, and in my junkbox I already had an old smoke alarm [2]. The Geiger counter has a thin-walled tube which takes about 15 events per second from the Am-241 source in the smoke alarm. Nice. If you're thinking about this a possible commercial product, I wouldn't even dream about it :-) Perhaps there is a cheaper alternative as a good source of random bits. There are many ways to get random bits, this was just meant as an example that it doesn't have to be hard or even difficult to use FreeBSD for "special tasks". I'm pretty sure that "noise-diodes" are probably the most efficient way to generate random bits, but it doesn't measure up to a geiger- counter when it comes to "geek value" :-) -- Poul-Henning Kamp | UNIX since Zilog Zeus 3.20 [EMAIL PROTECTED] | TCP/IP since RFC 956 FreeBSD coreteam member | BSD since 4.3-tahoe Never attribute to malice what can adequately be explained by incompetence. To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-hackers" in the body of the message
Re: How to make *real* random bits.
On Tue, 1 Aug 2000, Poul-Henning Kamp wrote: There are many ways to get random bits, this was just meant as an example that it doesn't have to be hard or even difficult to use FreeBSD for "special tasks". I'm pretty sure that "noise-diodes" are probably the most efficient way to generate random bits, but it doesn't measure up to a geiger- counter when it comes to "geek value" :-) Indeed, Poul's idea has massive geek potential. However, for the geek impaired, there is always the 82802 Random Number Generator which is included on newer Intel chipsets. It may not be the holy grail of randomness, but nearly every PC will have one, and I think it'd be good if FreeBSD could at least use it to gather entropy. But, if you are gathering a geek lobby to convince Intel to have an onboard geiger counter, you just might have a new member ;-) -Paul. To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-hackers" in the body of the message
Re: How to make *real* random bits.
I located a surplus german geiger counter cheaply [1], I have always wanted to have one anyway, and in my junkbox I already had an old smoke alarm [2]. The Geiger counter has a thin-walled tube which takes about 15 events per second from the Am-241 source in the smoke alarm. Very cool and probably a lot cheaper than professional offerings (I heard of cards with "nuclear chips"). On the other hand I wonder if this gives a practical advantage, in my naive view I would believe taping randomness from user events plus listing to hardware events (most people should have quite different hardware) would generate good enough results. Has there been any analysis that helps to estimate the difference in security? Regards, Marc To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-hackers" in the body of the message
Re: How to make *real* random bits.
In message [EMAIL PROTECTED] e, Paul Herman writes: But, if you are gathering a geek lobby to convince Intel to have an onboard geiger counter, you just might have a new member ;-) "Cesium-137 inside" Yeah, it does have a ring to it, doesn't it ? :-) -- Poul-Henning Kamp | UNIX since Zilog Zeus 3.20 [EMAIL PROTECTED] | TCP/IP since RFC 956 FreeBSD coreteam member | BSD since 4.3-tahoe Never attribute to malice what can adequately be explained by incompetence. To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-hackers" in the body of the message
Re: How to make *real* random bits.
On Tue, 1 Aug 2000, Poul-Henning Kamp wrote: In message [EMAIL PROTECTED] e, Paul Herman writes: But, if you are gathering a geek lobby to convince Intel to have an onboard geiger counter, you just might have a new member ;-) "Cesium-137 inside" Yeah, it does have a ring to it, doesn't it ? :-) Or a glow... - alex To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-hackers" in the body of the message
Re: How to make *real* random bits.
To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-hackers" in the body of the message
Re: How to make *real* random bits.
| Indeed, Poul's idea has massive geek potential. | | However, for the geek impaired, there is always the 82802 Random | Number Generator which is included on newer Intel chipsets. It may | not be the holy grail of randomness, but nearly every PC will have | one, and I think it'd be good if FreeBSD could at least use it to | gather entropy. I already have a driver for this chip. It just needs to be ported to markm's work, and perhaps beaten into not using pmap_mapdev(). -Dan -- Man is a rational animal who always loses his temper when he is called upon to act in accordance with the dictates of reason. -- Oscar Wilde To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-hackers" in the body of the message
Re: How to make *real* random bits.
http://www.fourmilab.ch/hotbits/ jmb To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-hackers" in the body of the message
Re: How to make *real* random bits.
In message [EMAIL PROTECTED], "Jonathan M. Bresler" writes: http://www.fourmilab.ch/hotbits/ Yup, that's where I got the idea. Difference is that I interface the geiger directly to a UNIX system, he has all sorts of magic stuff in the middle... -- Poul-Henning Kamp | UNIX since Zilog Zeus 3.20 [EMAIL PROTECTED] | TCP/IP since RFC 956 FreeBSD coreteam member | BSD since 4.3-tahoe Never attribute to malice what can adequately be explained by incompetence. To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-hackers" in the body of the message
Re: How to make *real* random bits.
[snip...] If I generate true random bits it takes 3 timestamps to get one bit of randomness: T1: Time of event 1 T2: Time of event 2 T3: Time of event 3 if (T2 - T1 T3 - T2) return 0; else if (T2 - T1 T3 - T2) return 1; else try again. In my rather crude setup it produces about 5 bits per second [3]. It seems to me that if you get about 15 events per second, then you should be able to produce about 7 to 8 random bits per second instead of only 5. What you're looking for is the difference (greater or less) between events. Because of this your T3 value can be considered the T1 value for the next random bit you generate. Also, someone else has already done this to generate truly random bits. Take a look at: http://www.fourmilab.ch/hotbits/ [snip] To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-hackers" in the body of the message
Re: How to make *real* random bits.
In message [EMAIL PROTECTED] Poul-Henning Kamp writes:
: The earphone output of the geiger counter with a 1kOhm load generates
: a nice TTL level pulse which can be fed onto pin 10 of the parallel
: port and timestamped with the PPS-API device ("device pps").
How does the variable, but somewhat predictable, latency of the
parallel port interface interrupt?
Warner
To Unsubscribe: send mail to [EMAIL PROTECTED]
with "unsubscribe freebsd-hackers" in the body of the message
Re: How to make *real* random bits.
In message [EMAIL PROTECTED], Warner Losh writes:
In message [EMAIL PROTECTED] Poul-Henning Kamp writes:
: The earphone output of the geiger counter with a 1kOhm load generates
: a nice TTL level pulse which can be fed onto pin 10 of the parallel
: port and timestamped with the PPS-API device ("device pps").
How does the variable, but somewhat predictable, latency of the
parallel port interface interrupt?
It cancels out since it is the same for all three events. Of course
if you raise the event density so that the interevent interval gets
into the same range as the interrupt jitter you have trouble, but
with ~15 events per second I'm not even close to that.
--
Poul-Henning Kamp | UNIX since Zilog Zeus 3.20
[EMAIL PROTECTED] | TCP/IP since RFC 956
FreeBSD coreteam member | BSD since 4.3-tahoe
Never attribute to malice what can adequately be explained by incompetence.
To Unsubscribe: send mail to [EMAIL PROTECTED]
with "unsubscribe freebsd-hackers" in the body of the message
How to make *real* random bits.
Ok, some people just can't leave an open end dangling (people like
me for instance :-)
I located a surplus german geiger counter cheaply [1], I have always
wanted to have one anyway, and in my junkbox I already had an old
smoke alarm [2]. The Geiger counter has a thin-walled tube which
takes about 15 events per second from the Am-241 source in the
smoke alarm.
The earphone output of the geiger counter with a 1kOhm load generates
a nice TTL level pulse which can be fed onto pin 10 of the parallel
port and timestamped with the PPS-API device ("device pps").
I think the parallel port could even power the geiger counter so that
batteries would be a non-concern.
Random bits are bits where no possible estimation of the next bit
is possible.
Entropy bits are bits which it may be possible to estimate with
a degree of uncertainty which is better than the statistical
average.
If I generate true random bits it takes 3 timestamps to get one
bit of randomness:
T1: Time of event 1
T2: Time of event 2
T3: Time of event 3
if (T2 - T1 T3 - T2)
return 0;
else if (T2 - T1 T3 - T2)
return 1;
else
try again.
In my rather crude setup it produces about 5 bits per second [3].
If the goal is to only provide entropy for a RNG (like Yarrow) we
can get much more mileage from the same number events: if the
average event rate is N events per second we can get roughly
/ T \
| timecounter |
log2| - |
\ N/
2
bits of entropy per event, which in my case (233 MHz and 15 events
per second) gives 12 bits per event or 180 bits of entropy per second.
Not bad...
Poul-Henning
[1] At "http://www.Helmut-Singer.de/" Called "FH40T Satz 2".
[2] Has to be an "ionization" type, otherwise it doesn't contain
the Am-241 alpha particle source.
[3] Feel free to analyze:
begin 644 random.bin
M8E6*C@L`HFII:/C=-8"7J).)`QC4H_`_3YM9W8?JB5,!1SZ%48PN48E
MN]!*;VTMLK\FKH@@6QWJ6JF=01Z:V(*5C?VA_LN[47$*CDOTDMA-8T0-::2D
M`_7L5'-8#GGOSV%X..@NQR"G3WV]I;"%7UKC(T[2]+UCAN:UMZ,_3]ZY
MR=#K6QCE%H8-@34$03"$!?!PT'LQ\)BP[61HP1$5IH"_CF]5=;EENALI8Z
M2'W`9Q-@AQ]UD.ZBONLN['"-9(]+D'/%R:MTQ,LKS8496,W@P$?ZC0!@.+
MMW=LM)\61/__+]EU3#8F1.2X6INC$^92%'T3VJ4?O%Q$)O/\R:+'G`F/!0K
M="/`F4AB'6["JQ]3=J%#^\S8DE]X-.S:_B=MT[4!#;RK.@K_U.*=]Q
MXM\_JVBHT9DEAM8+9@@4`MA[_3W:;"LCA/%W=0;5_K8(I6E\TXD"FY*WC
M4T";DDT,2D#E06D9A*FGR*6_MD#C:Z""_D#4#H-9#VC-W(X"MS50Z:R7N=
M,PW!A!$=YQ*D;P*$J$=2P4\$NYR_Y4KD[FG(OEW!U,31-NZM]3:B!9"?UX]
MR_X\O-C]ZO7R-"WTSHK7!("5CU4;3AE_:5,`1Z^?@M20N^!AI\MJ'3VBP3
MZ(2S^]MGDMA?8QO#WQV\,N_IX"6,6*BM']?IV=$!-5ATDCJHH"AF*GW
MZR?.7.\-_LO6PQVU4+F%)=NBV!9*ZBO(`V/66\+ZYM;(FX5TV'.=4MHOC;
M.IU*B([(\^ILO3NE6H,PC#PS:40CUI`'ZK)+N@$)62[/CW'=-W0HJ9]'T0
MCJ?D))W?.N.`1M?%\5ZFIBST0\YX!V!4-[[0_J+0.6+WWBG6@H?XXE
MO\W)$';`8KECLNU1DJ7E-ZDAG^67Y.`5;D"ZJQ)#;_=L*!A+DI..GC\V6
M1V#^G;0;LH+LVON9/EO43D3=.NW_5V?8M=EX5RL3:WT6R?RL1N67].KU!;,C
MN0QQ_E3*KH,10T::_,FM@LPPATIH+Y69;J7BURX@3E8#34_)98)C9;HK+
M?O3"JWA#-_Q5+@O$'M)\FY'[M61XUWZ+E*/_3WW0(=Y^T4+H@V\3AEFE=S#
MQJ%H=OD:[EMAIL PROTECTED](3D0^X'K@')[HPH!OLRG72!5E8M*9D'QB#ZO.!UF.K9
MPC`0.(6#S=P#2.3LV4:W=[TZPK42)RR5`:8\4R8M#M#7,Y:V6.J`+WQ-8$
M?$-R*K'B^*7.8VR3`+A!C*O5U0M%X$VT!?L1A#K,L8_\`F^'SH=:(2C,MU9
M;.Q@(4;'^0='82?6\57+1/,'?%4R./'AKXJR1Z8CCA`,#+PTS_+M?7
MT8Y2]4"2JVL4#GTLBO$8O1A:IS`:+'2'XB[%DH6;M4H+GGBV6N#\:A;
M:,:#T^BTD0F^=)=`AWQ1^Z5XI*M^3/]!9[:;W?'(O=5W]GCW=7%RAF?6,A!
M"PXR$.APB7,NN_,T54-W-J+SN,^B,B6TMH6!QY58Q/HAY(-"*CQ;9I6`G%
MQ!'#PNSH?;DX63R_#P,#C7:!PK.\;0%2)Q@-*?S"S)$@-!L1]1;*/)N,3
MBJE:!%O^TDY9PKUQ'Z?,A)QX)WGK7G6M5.5[I!2\/E%U7Q6"?YE/@25R
M#WIWAGKIG*Q:`P`-J$J2`:],J?.!'1K;XS1\7GL/XY$7BR(?^N,/\INW%H
M0OE'_\N/FR5",5!/%'I^^X#NO"2+24NWVUNVA.@WO^S)0@2`OKL,U8B#`4(
MR8(!DK(\XR00M4U/"2N62,)\!#K@6\+V#6Q;^?L++U;XBU"5=KH+S/
MZ'$S[7W0(/^,;8/3QDP$R?"+DH2'ZEJN;E(-6IXEZL'HZLY44IV$YU-^PAA
M-Z]O[1]U:+7MBF(G!Y49"7RX[X.!C#NFY,T:2E;6GS)RE;(8I0XA?_AR%
MJYR*,H0X%@G]P,,2JO%-V2`O+H@IKOK"$/7V7_:*6E%Y#OH!'[]5R';
M+YCB;()T?(IPUV*2)QKD)FUON5B4.1".\^@A_M4#FRRY2\U=*1[7Z%
M)]\,L,U;H08)(I";*TF)2*LU+T#L:MY?,T":X7R!V!U$K\OY:9"!KK61
M=?D)PJ4#DVV9X.O(\^KC*H\:FR08-!+4(V?K:1$9'G%.TN%(GG9#S%?4P88C
MDS/,.;H':!1/5%NV55/6H6*QX0U-(-+XA,GU]AB/H#-Q?VVW!UEY+?
M^9BD@;21+]:QLCGU/QD$+58RQ9$B!!:SD9UOA=;#6=*C1G#7\*_!M7'E\
M8%6XS6LN*F(_.)T0]:F?([`VOF-:9?KN`=XSH(KA`.-27(2G+[2H/NG75
MM!=N`V]S\X@SE@3@:6*75I$H1%8L(7\1BI6_(,$N56J!7J=R-4**[Y]HI!3
MN4VFY3JRK9/K"_W@S5FK$B,M?[$_4ET_@-7;'7B\5##I2,^63/WHUC:
M`89];@`QDUP+HK`?A.V@;Y:;KW(:'F$.@E9Y(3)!MX)W$-G/HA+8E/O
$).(Z[@`
`
end
--
Poul-Henning Kamp | UNIX since Zilog Zeus 3.20
[EMAIL PROTECTED] | TCP/IP since RFC 956
FreeBSD coreteam member | BSD since 4.3-tahoe
Never attribute to malice what can adequately be explained by incompetence.
To Unsubscribe: send mail to [EMAIL PROTECTED]
with "unsubscribe freebsd-hackers" in the body of the message
Re: How to make *real* random bits.
On Mon, 31 Jul 2000, Poul-Henning Kamp wrote: [3] Feel free to analyze: Could you post a larger sample (say, 10MB) somewhere for statistical analysis? The 1939 bytes here look pretty good at first glance: 1939 samples, total weight 7729, average weight per sample 3.986075 Bit 0 average weight 0.502837 Bit 1 average weight 0.482723 Bit 2 average weight 0.490975 Bit 3 average weight 0.521919 Bit 4 average weight 0.496132 Bit 5 average weight 0.484786 Bit 6 average weight 0.504899 Bit 7 average weight 0.501805 Kris -- In God we Trust -- all others must submit an X.509 certificate. -- Charles Forsythe [EMAIL PROTECTED] To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-hackers" in the body of the message
