Schneier on Security

Christoph Zurnieden • June 15, 2006 12:51 PM

@RvnPhnx

If you prefer a more practical, hands-on approach:
Take two decks of cards (preferable with different backsides) and throw one of it several times on the floor such that the cardfaces are randomly up or down (you may call face = 1, back = 0), the other deck is left untouched.
The mixed deck “M” is the seed, the untouched deck “U” is the number generator with the very simple algorithm $x=x$, it does nothing so to say.
The seed algorithm is only slightly more complicated: mix both decks by alternately taking one card form deck M and one card from deck U starting with M forming deck “R”. It’s easy to see that every second card must show the backside. It is not so easy to see that by looking at a small part “S” of R:
M=BBFBBFFBFBBBBFFFBBBBBBFFBBBBFFBBFBFBFFBBFFFFFBFBBFFF[1]
U=BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB
R=BBBBFBBBBBFBFBBBFBBBBBBBBBFBFBFBBBBBBBBBBBBBFBFBBBBBBBBBFBFBBBBBFBBBFBBBFBFBBBBBFBFBFBFBFBBBFBBBBBFBF
S=BBFBF

R shows its backsides significantely more often than its faces and you can easily predict every second card. The goal of a PRNG is to reduce this significance and ease of predictability for large amounts of output.
So the deck U needs some mix-up, no random mixing but an algorithm. I’ll use the digits of pi, so I’ll turn the first card of U face up and put it at the bottom of the staple, leave the orientation of the next four cards untouched but put them on the bottom too, turn the next card around, put it at the bottom, leave one untouched but put it at the bottom, turn the next card around and put it at the bottom, leave the next five cards … and so on, I guess you got the rule. Take at least as much steps/digits of pi as there are cards in the deck. Mix it with the random deck as described above and you have a much more random looking deck R.
I used the full seed every time now but “entropy is precious”: my true random number generator has an average output of a mere 30kbit/sec and it’s probably quite arduous to pick a full deck of cards from the floor every time you need some dozen bits of true random[2]. So we take only the first 8 cards of the true random deck “BBFBBFFB”, take it as a number base-2 (face = 0, back = 1) “11011001” wich is decimal 217[3], take that number as the offset in pi and start at digit #217 with the mixture of U as described above but without mixing in the deck M. When you are through all cards in the deck U the entropy of the eight cards of deck M is “consumed” and you take the next eight cards from M with a fresh deck $U_{n+1}$ until you can’t get the needed 8 anymore.
You can change all of the above variables, e.g. use more or less than 8 cards from M for the seed, use longer or shorter intervals for using a new seed than the number of cards in U, use a more sophisticated algorithm than the use of the digits of pi and so on.

Finding the right values for these variables is quite difficult and the NIST-paper is exactly about that: recommending values for all of these variables to get a cryptographically secure stream of pseudo random numbers and describing all of the pros and cons because there are no single optimal values.

Another small experiment:
Choose two different digital english texts of the same size[4], measure the entropy[5] individually, add both bitwise modulo 2 (aka XOR[6]) and measure the entropy again. Do the same with the output of some PRNGs[7] and with some true random[8] too. You might be surprised by the outcome.

CZ

[1]dd if=/dev/random bs=512 count=100 |tr -d ‘\0’|sed -e ‘s/[^FB]*//g’|tr -d ‘\n’|head -c52
/dev/random is true random (radioactive decay of americium) on my machine.

[2] but it might be a good method fighting the obesity epidemic in the west.

[3] perl -we ‘sub bin2dec{unpack(“N”, pack(“B32”, substr(“0” x 32 . shift, -32)));}$d=bin2dec(“0b11011001”);print “$d\n”

[4] http://gutenberg.org might be helpfull

[5] there exist a lot of different tools, see for example http://www.fourmilab.ch/random/ for a copy of ‘ent’

[6] use perl (e.g. perl -we ‘open(A,”file1″)and open(B,”file2″)or die(“open”);while(1){read(A,$one,1) and read(B,$two,1) or die(“read”); $three=$one^$two;print $three }’>xored), use “Monolith” introduced a couple of weeks ago at this place, search Google or ask me (I use the host “gmx.de” and my username there is ‘czurnieden’) for some lines of standard C.

[7] ask me (adress see above) for a couple of bad ones in standard C or search Google

[8] see http://random.org/files for a source of some truely random bytes