CS 161 Random Number Generation 25 October 2006 2006 Doug Tygar 1 CS 161 25 October 2006 Cryptography requires random numbers Generating random keys for crypto protocols Generating random bits for one time pads We need random bits to be unpredictable Goals Generate truly random bits Stretch small amounts of randomness into large pseudorandom sequences Indistinguishable from random bits 2006 Doug Tygar 2 CS 161 25 October 2006 1 What s wrong with this code unsigned char key 16 srand time NULL for i 0 i 16 i key i rand 0xFF 2006 Doug Tygar 3 CS 161 25 October 2006 What s wrong with this code unsigned char key 16 srand time NULL for i 0 i 16 i key i rand 0xFF int rand void void srand unsigned int seed time t time time t t 2006 Doug Tygar 4 CS 161 25 October 2006 2 What s wrong with this code unsigned char key 16 srand time NULL for i 0 i 16 i key i rand 0xFF static unsigned int next 0 int rand void next next 1103515245 12345 return next 32768 void srand unsigned int seed next seed time t time time t t of seconds since January 1 1970 2006 Doug Tygar 5 CS 161 25 October 2006 Problem easy to guess key Only about 225 seconds year May be able to guess exactly 2006 Doug Tygar 6 CS 161 25 October 2006 3 Problem Output is not random int rand void next next 1103515245 12345 return next 32768 Output is not random low order bits flips between 0 1 Output of rand depends on previous value 2006 Doug Tygar 7 CS 161 25 October 2006 Examples of real problems Netscape generated SSL keys using time process ID as seed easily guessable breakable RSA keys generated same way in Netscape Kerberos had same problem in generating keys Another Kerberos problem memset to erase seed after used actually erased seed before it was used seed always zero X Windows magic cookie generated as shown above only 28 random values 2006 Doug Tygar 8 CS 161 25 October 2006 4 Examples of real problems Sun NFS filehandles generated based on pseudorandom value from time of day and process ID this allows anyone who can guess filehandle to access file Similar problems in DNS resolvers Majordomo had bad pseudorandom number generator could forge mailing list acceptance PGP used return value of read rather than read buffer to seed generator but read always returns 1 byes read Online poker site used bad random number generator could be guessed allowing one to always win at poker 2006 Doug Tygar 9 CS 161 25 October 2006 Morals Seeds must be unpredictable 128 bit sequences are sufficient All possibilities equally likely Best if seed is truly random Pseudorandom generator must be secure No detectable pattern Even if attacker can guess some pseudorandom bits must not be able to find other pseudorandom bits 2006 Doug Tygar 10 CS 161 25 October 2006 5 Two types of generators Truly random number generator TRNG Cryptographically secure Pseudorandom number generator CS PRNG CS PRNG not distinguishable from truly random bits Distinguishing equivalent to breaking cryptosystem 2006 Doug Tygar 11 CS 161 25 October 2006 Structure First generate a seed Truly random For example 128 bits Similar to a cryptographic key Generate pseudorandom output based on the seed Stretched into larger sequence Billions of bits are no problem 2006 Doug Tygar 12 CS 161 25 October 2006 6 CS PRNG Easy to generate For example we can computer AES CBC seed 0n to generate n pseudorandom bits 2006 Doug Tygar 13 CS 161 25 October 2006 TRNG One idea is to use physical process Use randomness from other sources High speed clock nanosecond level Soundcard Keyboard input Disk timing We want to combine data from many sources Good approach use cryptohash e g SHA 1 What doesn t work IP address IP packet content Process ID 2006 Doug Tygar 14 CS 161 25 October 2006 7
View Full Document
Unlocking...