Project: a standard cell random number generator
Software-generated random numbers are likely to be of poor quality. There just isn't that much true randomness visible to computers. Several ways to build good hardware random number generators are known. But before hardware random number generators can be incorporated into common desktop computers, someone will have to put them into a small fraction of a chip. Currently, random number generators are chips or larger circuits. Nobody will pay to put these on a motherboard. But if a random number generating circuit occupied 1/1000th of a CPU chip or "multi-function I/O" chip, cost would not be a reason to leave it out. You probably can't build a hardware random number generator out of existing "gate array" gates or "standard cell" cells, because all the existing gates and cells are designed to behave completely predictably! It will take designing a new circuit structure. Do we know any solid state physics / circuit design experts who think this might be a fun thing to do? I bet you could get a paper out of it. And probably improve the world a few years later, when companies used your paper to close another hole in their computer security. John PS: It's possible that NSA collusion with chip-makers could produce bad pseudo-random-number generators in popular chips, giving NSA a back-door into any algorithm that used them. This would be harder to detect than poor software random number generators, since it requires prying the lid off the chip, getting out your microscope, and reverse-engineering the circuit, instead of just disassembling the software. In this sense, NSA ought to be *encouraging* Intel and IBM and Motorola to put "generate random bits" instructions into their instruction sets...
On this same track, I suggest that "/dev/random" devices for unix are an excellent idea. Ted Tso did one for Linux that steals all the bits of semi-random timing information it can. Such a driver has the feature that it can be plugged into either a software pseudodriver or a hardware device if one is available. John Gilmore writes:
Do we know any solid state physics / circuit design experts who think this might be a fun thing to do? I bet you could get a paper out of it. And probably improve the world a few years later, when companies used your paper to close another hole in their computer security.
There are companies that sell hardware RNGs -- Newbridge, for instance -- but they charge an arm and a leg for them. There is also a company that I got literature from that sells RS232 interfaceable radiation detectors, which I have thought about using for this purpose, but they are also way too expensive. As you say, what one really needs is something that fits in a small section of a chip. Unfortunately, this stuff is very delicate analog -- not the usual thing you find in standard cell -- and very easy to screw up.
PS: It's possible that NSA collusion with chip-makers could produce bad pseudo-random-number generators in popular chips, giving NSA a back-door into any algorithm that used them. This would be harder to detect than poor software random number generators, since it requires prying the lid off the chip, getting out your microscope, and reverse-engineering the circuit, instead of just disassembling the software. In this sense, NSA ought to be *encouraging* Intel and IBM and Motorola to put "generate random bits" instructions into their instruction sets...
An interesting concept! Perry
On this same track, I suggest that "/dev/random" devices for unix are an excellent idea. Ted Tso did one for Linux that steals all the bits of semi-random timing information it can.
Anyone know where I can find more information on this wonderful device? -- Jeff Simmons jsimmons@goblin.punk.net
Jeff Simmons writes:
On this same track, I suggest that "/dev/random" devices for unix are an excellent idea. Ted Tso did one for Linux that steals all the bits of semi-random timing information it can.
Anyone know where I can find more information on this wonderful device?
I'd ask him. tytso@mit.edu. I've cc'ed him on the mail. Perry
On this same track, I suggest that "/dev/random" devices for unix are an excellent idea. Ted Tso did one for Linux that steals all the bits of semi-random timing information it can.
Anyone know where I can find more information on this wonderful device?
I've just sent patches (versus the Linux 1.3.28 kernel) off to Linus. There's a fairly long exposition at the beginning of drivers/char/random.c which explain its theory of operation. There are some things that I had wanted to do to make it better; for example, not use MD5 in the inner bucket-mixing, but use a CRC-based mixing algorithm that Colin had suggested; this should be much faster, and since I'm using MD5 on the output side of the random number generator, it should be good enough. Also, at some point I want to add code so that it can sample the Pentium instruction cycle clock register, which will give us a much finer granularity clock with which to measure events. However, given the current interest in random number generators --- thank you Netscape for providing such a wonderful object lession! :-) --- and keeping in mind the saying that the best is often the enemy of the good, I've decided to make what I have available now, and worry about improving it later. In any case, here it is. With any luck, it'll be included in the 1.3.29 Linux kernel; the idea is that application programs running under Linux should be able to assume that /dev/random exists and that they can rely on it. Perhaps if enough free OS's do this, commercial OS vendors will get shamed into providing /dev/random on their Unix systems. Or better yet, perhaps hardware vendors will decide it's worth including the $10 (if that) worth of parts necessary to have a real, hardware-based random number generator in their machines. If there are any representatives from such computer manufacturers, please consider this a hint. :-) - Ted begin 644 patches.random.gz M'XL("'WS8C " W!A=&-H97,N<F%N9&]M (Q;^7?;1I+^6?XK>CSOQ9)%201O MVG$VM$39G)4E#4G9DY?-:!I @\0:!!@<HNG=[-^^7U4W#AZ:T"_C(?JLN[XJ MP&=G9^+"54\7818$1Y,L%'_+ F%UA=5_T^J\L7KXT6^].#T]%6[L/ZDXN7#F M,KZ(9>A&BW/G:#K/Q$0M1<,2C>:;=N--LT-;VB]^_EF<U6MU<6K5VAC[^><7 MIQ>O7YR*UR+?*W#W0"1I'(4S,RC";&&K6,Q4J&*91C%MX$V?<;4?A:)^WF_4 M1""35"PBU_=\Y>+N,Y!PADMI)?]U&2W7L3^;IV(Z5Y$;Q4I,DU=1C=GAO]OG M0@R"0/"J1,0J4?&3<L^+&\?*]4&<;V<I70SZ1)8HX8<BB;+843QB^Z&,U\*+ MXD52$RL_G8LHYO^/LI2/T50ZD@ZI"0E"EBI>^&D*PI=Q].2[^)'.98J_% X* M@FCE0R!.%+H^;4KX&-JX4.D;?K#.MZA+1.3E9#F1BZ49!!2K5()<.E?:T1-- M&:GP*?@31JGOJ!JS0LM4F/HYA0G+6Z\@KGU(2<^GZUI^@!\Z0>82O;0=)#F! M]!?0(.A9R1A:37V5L%!%8Y=J'%N18$XUQ.)FN/0 PM.YGX@ 9]*%I<@*ADIY M5FC3,LF/<B,G6X QF:OY AJ,L" 6"YFJV)=!4FJ*56QX+1C1_#7/R=A$*!>* MJ&'J,Q@"G;,FBH6MR(1 601)PBAA3IC%V8LH+>C1W$/8KB*/<X6'><UH$GGI MBBS!&)A(ELHAZ\(F7SL+G;"*R;S"BAK/2\\8W$R'X]O!=/1Y>/.+$:"YDNFT M*ZSA\BP$&<P+1+$@.^-3:.##[8.XS^P U]] &6$"?4"TJ[GOS(4C$ZU EER2 MVRCON[\A<]:Q0/V>P:)<,;J=3(>#*W%W75$[G!*$.*Q2N.OQE(B%%MD/M5^$ MRE%)0A;D9HH$*\42PH39R4#8T@5%(%SR&> M72D5EE2$;L%-]2ZR)'(=1=MQ MXOO)U5F2KH.*(9Z?E"*=?AQ-Q.3N>OIE,!X*_+X?WWT>70VOQ+_^-9A@X-4K M,;B]PO]^$<-_W(^'DXFX&XO1I_N;T?"*C\#.\>!V.AI.:A#%Y<W#U>CV0TV\ M?YB*V[NIN!E]&DUQWO2NAMN&^=;*-CX%POLT'%]^Q-#@_>AF-/V%[[T>36_I MSFM<.A#W@_%T=/EP,QB+^X?Q_=UD*$ V[[\:32YO!J-/PRM(>W2+J\7P\_!V M*B8?!S<W?//@8?H1Q[P?@J;!^YNA/A2,78W&P\NI#@RC6_-$O$ 0(.>F)B;W MP\L1_1C^8PCZ!V.8'S9?WMU.AG]_P"),BJO!I\$'P\[QGT@"8KY\& \_$85@ M??+P?C(=31^F0_'A[NZ*9,S'3(;CSZ/+X>2MN+DCR5^+A\FPAINF R8 QT!" MF":^'B8CEM7H%FXR?KB?CNYNM:H_WGV!,$#O -NO6+!WM\PZY'(W_H4.)IFP MW&OBR\<AQL<D1G X'0]RX4RFX]'EM+H4]T[OQM,*O^)V^.%F]&%X>SFDV3LZ MZ<MH,M24#,:C"2T:Z>N_#'#W XN - 3J],^*4=98CV)T+097GW'.56XNM $F M,!D9<V$Q7GXT:N"P<?'BM$C=QV&T,FDN4#-XV/OSR;F@2&1\>R77Y_3G1%3< M@[PVQB(XE)A)BJR429Y\)'X.O &"HP^7YD ',$()QZ"-FE"I<ZX%1S$=R2>+ MX:"S*'(W,0.6)IF?2CN@J!\+)UXOTV@6RR7B$85='0/?JP1Q/&%B(_O)C[)D M=VE"<1& (#^:LR_20,3W\CET1:(4I[[IY3U^_YZIT%$E-42N3B/+0")((3 J M'..G>>@"&0A]3##BUEP^E??I&$JW4MJ(PF!MF*T)A&6LC2F)\"E+1$^$+6&O M<:.0:2J=KRHN80SA'T1'Z"=:$J9"?./Q=[M_JO!IL43X-YQ#$>O\'B97ZXA" M\D?FF7D2ZEL:JX4"K42?#JR1*))YG*F"C8)1RK@(JOHV ,(S(3&X7$8Z36H. M$Y6YT=FVMO,\$PHE$Q]'&]"(C9!%EI!FI#:<8!8A)<X7(/@AA.;2+,2Z8%TS ME#.#.(5A2"'#A,B?94@O19(HM QQ[B.K!*[& -A,HH5.=G*Y# P23'3BQ7^D M8.DX:LFB!863"$DG295TP:-!<BGH,]+0#B1>[G&@ESE44(5(7VUXFA&:QJ5T M+I(]VQ*1"0<EU]AD/[(9%M<*^*N1JB'%"'Q+J90[2*T/H?]M\_:<9QNY%K@K MU&)AHL$R74ZTX^Y0!17(,F%@R_A!WQ1")R6OE2L,'E4ZZY]]56L[*FS17\ D MDIJ9X[_C;)GF$_I 4I8HYJINS(>H)]Q2]4\;<^)8GD #X9FK""3Y(? 3 @GM M/+9/2@E+[7FYH(UL8Y+S M:7Q:3^\2Z'$'MB1)#C)NFZ&D?"_&$*J*&6<-$H M"E[FCD&P#@ 2U8<C WC'PO]&<"XQ6)U/^7359DL!]F&P[V6A!DI /9?O+ZEV M(9(&2:YA>YUJ(O1Q? B$%>7%0T%&36,J'?03J!0E(DA]#<7[A*I?DS+GT0J0 M,USS,3;5%YL:YI!H$V!+X%$,QLQ5&P97M<6(+)[5%\(K$H!Z53&D+W.<M<.* MCL,ND[SFD<@VZ ^!))5?\_(&XN)CYC*9$ZD4N3*Z"Q$^2XS?A2E;B,F'F[J! M+*?S'/C*A"0>Q?G1^EA&^=K+X/P4W>13Y+L(KHB)5=UM,EE*;B<2<9U+Y<)L MOG&5SD&18OB?*D<7H%IY",)*PH@JLBK-JHRS9*!%;*2=8.M)4;UDW(BJ.EU7 MZ=TKN5/6[.,F+T@STJ5#HLI5(!<D<>*V>OB68^41C-B$^*0?Y$E6QU$8W5>E M2>3P3G9@Y_7ZCGG].],2XIH52 "'%5HKSS" QU7, .X@ R_VYXY0]8/<!_B, MEY0P*][PDBUSHS#9=CI2&Q(:+D;L3RJ]EB(REZXP\C39!1TSL@3(YKN*HPWO M92/$JB#8#OBZ --'OR4N%$4S/S7U[HK2"ZPV\7-,5@$H.G;)8/U=%2+3A.>N M\XP2RF8%&7*1VDN(R&;#H8,UG&0.58@D+U9V;DE;EVE>M8#NYWX@_E/&H3A> MS2-&.PQ'2%X+Y<PE OR"=NIH2G1P "CB08Y]"!&A]-P&/6SYA%LJNCL1%*8U M+-#Z7W+5BM&J$0#D^J'NQS#<YAZ"J;5U;J6"^DD&.#NG@IP]IY.A>QFW2%X@ M!$4^=4<8="5DKRGE<(]W&')DWJC;!,MTMLGK"4),X)+./>G'!/405^$F8<JZ M9KU7#'"(@!:GRA3H'B/D,P* 6C'/8=3]>'7*T)H<))W'2G&TW#K\K>X'^7'" MD"\*=>"?A270S-LSK!^2E)&R!B1O"DA]Q!%YIM)'K9E'SB7'//K:SCR&&"+D MT9.W%23N)R5!N("ZCUS/F 8$L&5"1!N3+T,ZGU1:.-<3#%VW=^)RSX#_0C B M746F$*F(FF6%">KFPLXP:4"];@>;B_,&"8]EIG$K-I:0YJMU%X'$%>59!M5S M?Z83S>^9#/QT74WO?I*G7G%,.]4WN5@&"/[T .B6^SSUKTX,]QS@6'*Z*-+B MDX@XW_Q%MLC=N91@-:16[CZ69>C3:?[YB'-21EV3JW8B[Y;$J^(J"EJ*KP3V M.329ON7"3W4\JQA#SJC."!JE:'T5>M:8;$%=;=K,/[9A3=%>TY:1=PQG_A-' M0'^A"O"QD4/@JS'%N'BF\F0&4@U]21:PU06(]?&63BOP_YI[G@;85:N>6IXE MREJ@4OL4GO)L;/##PT)#M?K59I[%,=4'>P(#BT%75229C;I*9[BR.<&-7^,G MD/&;4NTZ)@"6/^9%QV-I;L=9:"(-"58DR*C4I=>QH;*UJ#NJ>RF6^/'O9G'! ME8YD!6*GK@635U0^C.I-<<.(;J4"A@@YYLK)H+'<F4F^28FSM^#KAEB1*"*J M<)^A8+N^*F\Q3L0W[2D=8#^WP*,: W-U#+++BHP]H6C#)/M*P[]H"RSB"7>O M3>>_."8OO77U0.TD9Q[Q.P5;.3++N]>FA"(S-[%E\PR3.F(URP)IP,F<6P35 MAHDNU(KFC!!7?O)UBRF39FV54C0V!6&>[PT+)$=#AKM[ @<"/B8+*[?KJJ,L MQ@P(+I#?7OA9B952+&4,)$(,EC>2*8=(B]C@<3\&093*/(XN2"E?-23W*FF7 M9&.L)HI=3CE!*I,\H.Y4Y*6]#9ROP).!<F>*'#-YLS\&5."M"_GI/B#"#J T M;)2!GY\\%^;A'UP,<G52-B:(LGM$9AC ![*2>\Q+9_TJ^?< M2B-EK0^U>_& MLD2_"&$45J!,UH])AK.0BQ8N>KTL+OH.Q;M.2'FQ3E0 D)&04:V%%\B55G\2 M!=1B6S#T6N(BW_8I0->*/&XPFGD7!7O,7_,8/]3OJ]B=[C_<T\LI3!"A6PF. MPP9)EQ BM!TF_/Z.RCO4RT0[B>XR"J#:^P ">J51I$\.6;QLRUL5!<<,;(K2 M9JG?+4'&R+V5TIF[%ALHU)DKYVN2+4Q]J>$Z)#6.4&&X8@R-)B;1YKU7\])/ MWS:^OA16LV'5Q,NI*2P^T5NEF8*CSJA9-<CKC)<525QK!0D;UCZ#>]'QE:HT M"K6]I=$2-)IW:T5KH3 0OKS;KN/R2N]G##]9@$+7M M)V!.%- 9]OF1GNV+F M=+Z421I [C4Q29%=Q64<49S1'/]->9Z8.%!B8* A=_3_ZGNN\H!!PNP;/9G& MV8\\<)% I.[Y_*?=&=.=VS>UD/\=Q7MGZ-5:.-L[94 E354G9;*X2-2,=+2U MC6:0#_>-1GH04O.]"H^7=[?7HP^/X\'MU=TG'L<H5;8T<G]W=R/:5H/&=: 0 M.:K/(,14_,^+TR/*P92@EVG\UCR:E/7(I50^B+)KEL[S)\33Q\T1!#RY?ESX MW]Y8-/3XF/7$:TIZ>/KC;84$3E>, AYU?X>H*%!$@$+LB+Z!>*1U^>%'>HB# M:CD64E2O'"^I-;F74?/$][TMEH+&9H/G'HE0@C>_6IW?-A;T\KVTXM=<JK_M M.P2+3/&Y><IS?!=H2L]L$??<+MA'=<.OM^/'T?COD]_>&JL(R2P^C6Y+4\## ML:S9)^+XF+JY/U+G]D3\![=VW_!#:5A'Q?V,W#S4_G.#V([W2O9U5;0XB)19 M'3K[R1B7>"?J;W<F2SO"_.:4&7XM>KO;-BQT_\F%/9KI/T@^S!0+TP]]>H_N M?U=<W.ZA_+R@*]?Z]B7G7%6\JUH(+=D0V@\;\LGI,.\<-U-,V?"I9AK.1_EG M#XB-E<Q3*9NSM$2V&\FE\II38VN@2IR)E)JC6]0?XMKBQL&2T,EWZI1$"[4B MD%KLS8WIVCK^5A/(N]]A3]_$#V(M_E?\'_W *W>N_"[^*=>?;S&K^\G;'+Y MPD:Y$)N^UP0]5A<T-Z[\I]!G5!:T*@O6^BH0]9UN,8SK@HS;V&0[W.54RSP= M;[3;SC?8P-1D.KP_!BA9:<IP34T@=TG E!/Q7U#XL5B)TW?"*ZDX-0LP\4ZL M?OPQ 3VKGWXZ;C;.DA,>QOIOXJ1B"QI[Q,7W-9LM0)UN9:!?7(8H .A%C.E\ M<7>]0.M>D#>\X7F^3M>>L#H<6E= IXR!0K5B&@$^<,3#TJ788@=(KN4K09IG M\P+01&$+!*U+<+:T\C2OZ!-7.HT7FX$$=TQS0S_6(=/.O%];O\&&CXZ.3!1E M0(OC*7X:C]03$*5=$P[DSF'N2$*LM+].8>_(-D\6/SGFJ<%/KGEJZ@!YE.OS M&HBH/)7:6K^*^F^G]6]NMR-EJ]N#EKKDKQL[W,HFVF'1#M5SNG:WW:D)J[&S MPZELHAT-VM%H->K=NHLA:_<.N[*)=C1IAV/9KJ,48%!C]XYM/EJTPVMWG;HG MO8/X:-,.,-UU.@UY$!\=VB%[S7JK8S4/XJ/+5+FM3K]=MP[BHT<[.OU>O=]S M#]-'GW;T[%;+ZQ+G?\Z'Q3KW\*=MV]8A?%BL\UZ_[;A=^R!]6*SSCMVO6U:C M<0@?5E/+JM_K6OWF07RPSF6GVV\U>^H@/K3.^W:KWFL4^JCN:>QJA'GW.I9J MM#O$27OSEL:N1MA.G'JK;C=;J -$?V?'-B=\1Z/35FW9)HVT=G9L6Q;K4/7M MCM.5&&K4=W9L\\&\NYV&9]7;[B%\:#NI-UHMJ]5N'L2'OJ,G+=7I'<8'ZU!U MW:9G.[V#^&![;UC*<ES5.8@/OL-I-KOUKMLYA \=?[R6VZZ[O>Y!?+#?MMIM M:;7HW?.?\Z'M7?954_7K[8/LBGW*<Y0GFU[O(#XX_G2Z':_></N'\*']MN<V M9,OI%795W=-\QK(03F2SWR(/V;JEN<L)2ZO7[5J>MA-K9\=>#^FX?;?#\<3J M[.S8YD1G!%>UF[TZ)AK-G1U[/5VV;*5DJW40'WQ'RW:5X\G^(7R8C-"Q[9;= MJ1_$!WNAK6PX2+=^"!_:LAJ]OMU53N<@/G0TD=)J=#UY$!]\A]M27K/>:Q_" MAXZ*]5:O9[ED[P?H@ST=*F^Y]6;_$#ZT]:J.:_?[JGV07;'M6IYL=!WRJ0/X MX#N<EG3:G4[!1W5/ZQF4Y;4:_4:#+6OKEM:N1MA.6LV&]+P^1:#ZSH[]V="& M"S8E[6CO[-CF1/NMTV]*EF_#VMFQ/ZNWVW:[[S0/XH/MI.?5'<>A?^EQ !\& MG2C/:W7=@_C0Z*3=:[5=USJ$#X.R/-GKJI9W"!_:3CS5<%1'U0_APZ#%9MUJ M-:W6(7QHOVVI>L^RY&%\Z!C7;3>[JM<XB ^6E>TVI==HM@_B0Z-WZ7;=AFT? MI _V6V7W.FZS7_!!-0M7+U0&<D-+ER_T:.>/#7YT\L<F/[IY!^&O&3=ZKJWR M9Z/\V2Q_MHJ?ALRMFK-XR44-.)EFU&PO/G>@/H3^/F)/YT?(I'S?I;_>U=^1 M8!-J[=\SE2F1A7.Y7*[WU80+_YLYRWQ?\&1JOF<:3:CDGNE!G8@GTQ4\\FOT MUN)Q*>G;I[=% ?EZ6?[VGU!W:BW$NWVB(_QW\5I,4AFG8O19-V'X'V5Q=;SU M"0]W@(BQHX5:.,OUL?]4$SB5QT_IE^DBG4&^WU7D8<%)K?+;F$-),_63BET7 M",+<4D*)?>P3A36Q)#D8KD[RN]X*7_Q8Y5SXIZ<GW%H]VJB]F;YJQY,M^ @R M@37BX-?+TU/QSW>"!XHY:WO.*N<:VW.-<JZY/=?4<W^4 ML@II!=(:)-6D]* M!7WQEPHG:OW@+/H2/%=$ I,B1NM[)!UO=R3_V' (V&_A$5A'KPCY$\&=3T%? MYI\]CM+B PC]@E+W4JIK\_>1YG4E?0Y%[T$S_E38?"[@T=<$6!W[^8>=I;OX M84"]J.)E>M[^),J>:\OJQLH1_:,IW5;A9K8SKXP7;7OC=Z#A^"\\('[X051] MX^3_VSO6YK9MY&?Z5Z"^N8QD439%R7JY]HR3*'=I;,MC)]=TV@R'EBF;-?4H M*=G)M+[??OL "#XEQ:G[H7.91*( + @L]@GL(@B4X->0%D*NU<\:I;7:)USH M$9\*0'<);!\E"%M2)K;@ ?#O+#_228*17S+#>!1>$'E4FQO6X]HUI>BY1""- MWM7*QQW*XT5>U2C5@'>?,8(EOW+9M2I=IN3J[, 4:7V$/G'AB"NUXH%W[P5F M;N4>;OW $Q6&J-?%D;!HR7+$ N_;H74R)3QAD]<RO:D.RB;UTL2*IAL>Z67= MZ=);P_P&?9C9SU^S0 K#A3RG<R#X,%UFG,!L(F;'.%PC=WC"BX Z3H7*XEZJ MY$YUJI\-&M"CH1P]C-F@Z%L5IZXBA(MT'"Z 'H4,>UG#L64G/SLR@#C'MJ#V MZ&3,Y*@#6^E"=3Y& A,^,/O%#3#885$01Y:,BWB@Y,8K]RKXPG T6<#NC](F M(&9Q1[R\Y6$0#$RCH@AC&1RAD(]G$;%LI+8HP*DYT,RO_GCL8WB44"="R6-! MGBHTX^;I1O%!8192=YNM56_59XPLG*#P>^ FH>KK^09VHH4=-[$/$G/!,[C4 M&E7%T1'+-]+MM%0DW>0 !)6 #D>BX%Z.CJ1$Q WPA&0!GJZP^*B*%W)VL>*3 MOZLL5C"]&/M-<#\=&@H^[;C&COQFM^TXU031##$,$4I-C 3G &4,?L10C%G M*>1$K$P?8'\L)QSCQ.#$-C<8J "<*>P">@/ CQ\_LB"8>MYUQ(#^%(,;_!M7 M)B(C?0CXFBT75\Z\ AXT*'CT#*L':!$ 68]N9:H"DN7QY?$Y4U21&/2GW$?+ M GN,O8N29NE&18+27BT<]2'G"O&8.E%7Q['ZT/(KP^_6&=(O,B?B<O8Y4048 M>%%T3@UX+T69&H1J4X2Q]I^-L32F5D8;/@$W.%( 11M&GK?SN"BJ=0WZL@?V M\/N3)*9R+2C#ZZ/"K+!L5I2R450&*8=/NRID6F3ZE@ETD59TH8='Q4J59M4> MQE\%WCB.R6;['-T]7YN^<9)Y'(.9M:\HZ)&R34$#4]Z6"A@JMG;)[&$T;&!$ M(?7OX(QC^U8'JK/*7,P<, Q"K31C POP!FX5^4W05#N*B\F</44#A>MH7B)[ MUTE>=$,LY;EL1/-B0Z*GWGB.T$?3[K39 )-%AUQ$/.@A/)<7\F3]$-&@HBT* M1_F]-"K#DOB+0O^UW3K0]JG,&V!C/PZO0-VH%DKN.4J']]!BOQ:<X(0_2Z.K MU3(A-_XG\=VA'*%A7(&FNF-/ 3]P)<F_Q1. UK[=M-BUP/(&EWOCT;5[U>W% MY3:7][I7[O5H[,7E32YO6$U[O]4A099VL:&1F0D(2DZ*O?C1G!&EG?>$XX[5 MM<-VBR>3[UR[_Z.Y]+4!)9K T2LB[]I9S,91A?(V"%#2%X%H!XH=\>)6DI2 M/#35X7X4"G%=\L@DA@D+\+52LLDPC#A:G8/N=- ZF_!*E,4)QEJ:K,^/+TI> M3R9T<>9]TE';,.&%14=6**7T!2P.RZ(J":-8 EFQO$]')V+O:%5E@JS\*8;] M[/"W*0O'R$0[]&4F!%YN@$@,2BP 0U=1OB3#EE+<FQ88Y>V E[M2ALF57H.' MU/2UNLM,V%E.*5?$N]YXZAPQ(E9AX!M&F BQI"<!EF4JRA*IIK[YW5(RC',O M'1)JO E]OES*%I;5;[;Z^YW<Y5+INZ6*.XKCR-_*<%'"E$I_*<N;S5Y^\6.\ MZ>L&#^!'Q\GF*[,59;[>0D9 A^!2+,#,!\T>34#!RZADJ!:3641N^1BP1!E4 MB<P9C&KV KS!@;NAQ&#M0U".Q G.641?HH4WD1F0/B;R53 8/I"W'3S(76N9 M\(:11&/*-.:)9;JD%'[=(PZ4C9H99W5A2@E=]Y&X7RB(9B9;3%)JQ8D'E$1$ MXW(I38P2;PH$57S!1BHC+'V!1/&=&QQ//@\I39\1Y85T"1;=T(62D0!!H8PI M)X4R,B*UU"J>+1<PO)?(2=(A@:E Z@Q,>1#EP5/=E8--;7?]ALUS%#<2L:)$ MT"2DS.INUPDRL9$DR[SC'ZRDU>*58?5S-=VF$(6?=9COX;?_V;IX=4F3Z,>" MR8TF==P\V(.J/3I-"G9OS?LM$,:A[U%N7NCQA5FBL=O8@I&,17TIZB'\RO>B M>MCB[+B26@.%YI[5VT-!VNQ;K7[#,K#WI.Q=!]6$OSV2O/M=LRUJ\ DB'&1O M'/9Z>>R<#4^/+]\9N!G ?U*UP[/!Y;^'[Z&Z&U?'#.0X[P879X,3QTD>O8&8 MN'>#):=X1:XS#MP;SG:A5%W* I7IFU+<N!'E*\DS*-8*X)7>PB('A%XICG1V M$8PLONZ)4A+QII]EI!-#R^$30@-Z.;\8OAPD)IJJO#P^/3\9*/T(!1>#R_?' M%^^3VC2!+9 E+T^&K]Z)^(^%^S<H">F,#8?"*T6"* 7XX2P%VE" R^E:T,O! M>UQ!!6HKT,A;+%3J/,."C(_N$/[Y&,4-YK?NMW,*=U/**NGJ+-7;\+>05U:# MP=\V,4O;0F:!SQ7,(IFA6\(L7-OX/[-\!;,TGLHL]M.9I?F7,TOJ3E;DDU/W MSB.MN2F?I'I0T,0BA34%FJ03<\<F$ V Z!)C-#IF!PQX_$2^.'%@??\U>"_Z MAZ3K=]TM<>H,7_YP"9CM'V*#^(=8++XX_FQW)J8./,(WG@_. @^>E.J'QX@N M[X2'7[;J!H.,%OA[3C#WBUV\>&F"CR,G&H6>-Z7&M<T;2P\#H80!E %OG[AS M/2#^<>\!,UX%[O2.1H6Y![A9/P.&%BGK\=5/KTZ.7P\NGYM,<"*CI]$(@>8) MA(KSU&%;Q=11U'R_T6]*TFBCS(1/)HU\GF$ G(FY?ODJ<#Q**M9D'XHD3";[ M4!3E&>) ;9M&:MN*BI5T@'',G3N8I4%/\*#K\(8=!TQ6[\Y SY@?=36F,7D. M-C+X$1MIX<AE/.YD QA_.BD.E]Z)[_S#3?*),Y[-<0/C=R!6C@;AEYLTF2:C MO=GHFDV;9F.<?3@Y,5"J36=\URS>1@/TBQ?.4,X52L3'@X1BRKA!ZX9$3D$\ MJEIF5+A'$?L.^#,Y>?R-XS-I@&/$)+:^]D,^S\K4,=L55A&G0XV1K\+5R\(D M< %SF<:(J&V$KL)$S"QBEE^%&>U5_9UP%"MZ$1]Y+&0,$Z)JNJD'.:]N$<%' M#SX>?59.WYX-+RK4NG[D.^&U=U_%37-B@199:\TV^#8M9@&#;E?J]/'1P.[J M1V-X/QZ!T>QQB0ZH4FVG%W."[*C;)W\VW5%BM3F81^_,$U"O"&A9"B4Q)_!, M?.PN@P4/7N[WU0=GP]>#_^"8'WG2[1Y.NF7MFSV:,V*+#C>\&S\")]D9W2*6 M*J>#4^?T^(?AA;D-Z[!MOI"K@2.H5O$=\Q 6Z:ZRO9RJ:R]N/+P.[%<PBO[) MER#**#3H+_IENFV*N--J.>JR^RC5Y"2A0]RK#/&(A?0VM*O$A=!4I'L]OR#[ M-0,9S/. SZR$8TOEB9I8P^?5L:[+VE_-?JM=K)-+86RK;[=8WW5(W75*%+-R MA@KTK[X!(%?ESW!G[6O5\Y6_ ++C*J+B#K-NIR&I&*G1NW?B6V[H Y*;V9\ M_;IS=T6;0"%S0AGME6TG);?E%"U"1WA/"-'APKWZ>7SC2#OP$[Q$&/!&J,3W M\CE,3>@6?S:YN>'H=H_V<]C5(Y+#>Q,VI[9<%P1.Q%9<E:6U=M_2M+892*=O MV4QJ32*U9@FI::+)5ZF-O<):C#+X_-6V(&V!KS0%&UW:%6MT>V;#8@)4"BK\ M3=X_OR/DPR%YR36ZIX"+#HAZ[E#5[>I;?2@.HE8KEXPHIKD#4 SD[;_(N<]Q MD&/QIC%O&,?B5/5&+KP78CT>_M_@5JMXE,QF6PU:':O]-YPL6BAJLL_ D[QO M]&U,F>HCPY7YNH(MK5Z:+=?#M/K[MO02FNPE--72KUI*A6(F KG\3 M_Y3KO MX06$_BAU819:)MYG;[14U^.A14J'H6(&2O$6H_C0O2D;3KP+5B6#:27C/(\E M0?M33$+7WA.L"(8GV)0%D2@OL!YZ.>NAO+W=Z#?VI>70;N!^#WWS3JC!Z(W< M>X]W*BOTB:QGC (?K;RZM$/I%D,',%JY??#'8+8C;N&%I+_-U&J8@IO@?\-2 MY6"83?H@ SK9SQ]9BLMU+-"DIINI<\./#6'\/X[>'+\]&;S^;IMKI!7>>'ZB M& <S3"IZ*ETH\ +24%5YZMAOE5!'"0@0B-PG!R^DAP1"WY) 'I$\O(5S/0LK MEBG^"_^ZU0.!T09\*[8_F7C7OKM(7AZ'1%5 .&].AN?G/V%8HBEX,%IT9"EH MFQMLE]#/RJXV(:14_T 3K\DG:52V/VB_*72O!+Q!>DT4/4Y $J_H.Y%7IP>3 /HJ\Z$-C_ %)CF>/=:P end
Some some ramblings on the RNG seeding issue, comments welcome. I'm sort of in the position of Netscape in that I have an SSL library that needs good random numbers for both RSA key generation (soon DH) and SSL sessions. While most of the discussions have been how to generate random data, one solution I will probably follow is that when any 'semi-random' data is generated, make sure to save this for seed data the next time the application starts. I have faith in the RNG capabilites of my RNG (based on MD5) and my RAND_seed() routine only 'adds' to the RNG state (about 1k's worth is kept). I can continue to 'mix' the RNG state at any point in time. My RND_seed() xors into the existing state, it does not overwrite. Because my SSL/encryption library contains 'everything', I have the ability to put calls to my RNG_seed() routine in places like when I decrypt a private key. I can pass both the password (if the key was encrypted) and the private key into the RNG state (making sure any data that goes into the RNG state can not be determinied if a 'core' file is generated). I will probably also put the time() into the RNG state whenever an SSL_connect or SSL_accept is made (I think I do already). I may also put in select data that has been read from the remote host While most of this data can be determined by watching network activity, if it is just a delta to the initial random state it is somewhat more useful. The first time use 'x' runs the application they are made to 'generate' some reasonable random data. For all subsequent executions of the program, any more semi (psuedo?) random data generated can be mixed in with the initial random data. The profile of the usage of the application would end up determining the random data to use. I feel it is a bit much to try to generate good random data every time an application is run. I believe this is the type of aproach PGP uses (I have not looked at the code). eric PS I also do some 'evil' things in that I load 'garbage' bytes from the stack into my RNG state whenever the RNG is called. It may not be random, but I bet it is hard to determine from the outside the running program :-) It can only help :-). -- Eric Young | Signature removed since it was generating AARNet: eay@mincom.oz.au | more followups than the message contents :-)
futplex@pseudonym.com (Futplex) writes: John Gilmore writes:
In this sense, NSA ought to be *encouraging* Intel and IBM and Motorola to put "generate random bits" instructions into their instruction sets...
Does Tessera include any form of hardware RNG ?
Yes. Here's a released CAPSTONE spec sheet. I don't expect an attack like the one on Netscape to work there. Jim Gillogly Sterday, 1 Winterfilth S.R. 1995, 11:07 ------- Forwarded Message Date: Fri, 30 Apr 93 10:11:03 EDT From: Clipper Chip Announcement <clipper@csrc.ncsl.nist.gov> Organization: National Institute of Standards and Technology (NIST) Posted-Date: Fri, 30 Apr 93 10:11:03 EDT Subject: Capstone Chip technology information CAPSTONE CHIP TECHNOLOGY CAPSTONE is an NSA developed, hardware oriented, cryptographic device that implements the same cryptographic algorithm as the CLIPPER chip. In addition, the CAPSTONE chip includes the following functions: 1. The Digital Signature Algorithm (DSA) proposed by NIST as a Federal Information Processing Standard (FIPS); 2. The Secure Hashing Algorithm (SHA) recently approved as FIPS 180; 3. A Key Exchange Algorithm based on a public key exchange; 4. A general purpose exponentiation algorithm; 5. A general purpose, random number generator which uses a pure noise source. The Key exchange Algorithm is programmable on the chip and uses functions 1-2 and 4-5 above. Prototypes of the CAPSTONE chip are due the last week in April. The chips are expected to sell for $85.00 each (programmed). The first CAPSTONE chips are to be installed in PCMCIA electronic boards and used for the PMSP program for the security of the Defense Messaging System. The CAPSTONE chip is big, complex and powerful. Over 850 megabytes are required by the automated design system to define the functions of the chip. VLSI Technology is fabricating the chip, and MYKOTRONX is designing and testing the chip. 1. What are the power requirements of the CAPSTONE chip? Will they fit the power requirements of battery-operated, hand held devices? The CAPSTONE chip requires a 5 volt DC voltage source. Power ratings are currently estimated at 3.5 milliamps per MHz, i.e. at 10 Mhz and 5 volt DC, power consumed is 175 milliwatts. These estimates will be refined as data are taken into the actual chips. In comparison, the CLIPPER chip consumes approximately 150 milliwatts at 5 volts DC and 10 MHz. As you can see, both chips fall within the power requirements of hand held, battery-operated devices. 2. Will the CAPSTONE chip incorporate the key escrow features of the CLIPPER chip? Yes, it will. 3. When will CAPSTONE be announced and available? Prototypes of the CAPSTONE chip are due the end of this month. We ask that you contact the manufacturer, Mykotronx Inc., for further information concerning the timetable for availability of CAPSTONE. 4. Is the Department of Defense working now to incorporate CAPSTONE in the Pre-message Security Protocol? Yes 5. Will CAPSTONE meet the design requirements of a PCMCIA card that combines voice and/or data communications with encryption capabilities? Yes 6. Will CAPSTONE use the Digital Signature Standard? What kind of key management scheme will be employed in the CAPSTONE chip? Will CAPSTONE allow the use of RSA public-key encryption in conjunction with, or as an alternative to, the DSS? If RSA is implemented on the CAPSTONE chip, will the key escrow feature function? CAPSTONE implements the Digital Signature Algorithm (DSA), proposed by NIST as a Federal Information Processing Standard (FIPS), to perform the digital signature functions. Key management is handled by an algorithm based on a public- key exchange technique. The CAPSTONE chip does not implement RSA. 4/30/93 ------- End of Forwarded Message
Jim Gillogly writes:
futplex@pseudonym.com (Futplex) writes: Does Tessera include any form of hardware RNG ?
Yes. Here's a released CAPSTONE spec sheet.
That probably means that this sort of thing *can* be made cost effective on ordinary chips. Now we have to get Tim to lobby Intel to put RNGs on the P7 chip :-) Perry
participants (7)
-
Eric Young -
futplexï¼ pseudonym.com -
Jeff Simmons -
Jim Gillogly -
John Gilmore -
Perry E. Metzger -
Theodore Ts'o