Practice Cryptography!

Even with all of the cryptologic and cryptographic technology that has existed in the world for the past 60 years, we still don't really know what encryption is good for or how to use it -- or, more importantly, why it's important. Maybe it's time for people and coders to actually start practicing how to use it, like any other skill.

Tuesday, March 14, 2006

 

Random Numbers...

In cryptography, there are three major aspects to random numbers that people need to look at: How are they generated? How are they used? And, perhaps most importantly, how are they kept secret?

Modern operating systems have sources of entropy that they can use and replenish as the system works (perhaps even by 'thrashing' the system a bit, allocating a large amount of memory and writing to it, memory-mapping files and writing a pseudorandom amount of pseudorandom data to them, and measuring the times it takes for the hard drive read head to move back and forth, given the randomness of fluid dynamics given airflow within hard disks). However, as we move toward solid-state systems, this becomes less effective, and there isn't as much entropy to be found in such operations.

In the case of a system that does precisely the same operations every time it's turned on, it makes sense to save the last bit of entropy that it had available, to 'seed' the randomness next time the system awakens. Note that this is not foolproof: if the seed is read in and not changed before the next random number generation for an application, then a power failure could cause the same seed to be loaded in in successive runs... which could be disastrous. So, loadseed, do various other things, saveseed, then run application that requires random numbers. If there's enough entropy available already to do so.

/dev/random is your friend. This is a distillation of true entropy, and will block reads from it if it doesn't have enough entropy distilled.
/dev/urandom is not your friend. This is a pseudorandom source, and thus deterministic. When fed the seed, it outputs a long-period pseudorandom number of whatever size you ask for, even when it doesn't have enough entropy to make it as secure as the application usually calls for. (The details on the random number generator are left up to the implementor, as well, which means that it's often difficult or impossible to determine how it works except in open-source operating systems.)

Now, we're supposed to be able to determine entropy from various timings of various things, such as keypresses. There isn't really any good measurement for using entropy from what is typed, since languages have specific patterns and patterns can be exploited... but there is good measurement for using entropy from when the keys are hit. So, if someone's sitting at the console, it's very likely that they can create enough entropy just by banging on the keys.

So. We have entropy, we have random numbers. Now, just what do we DO with them?

This varies from algorithm to algorithm. RSA takes random numbers, sets both the high and the low bits to 1 (the top bit to make sure that the key is actually as long as it's supposed to be, and the bottom bit to make it odd and thus have a chance to be prime), and runs various tests for primality. If the random bits generated don't correspond to a prime number, they're incremented -- often going through about 50 to 200 iterations before finding a number that is statistically prime. (Since factoring large numbers is the hard problem we're trying to solve, if we knew how to factor the random numbers, we wouldn't be using RSA.) However: Once the primes are known, and the keys derived from them, just leaving them in memory would be a Bad Idea[tm].

And one other thing: don't feed the random numbers you pulled out back into the seeding function. Random numbers should be used one time and one time ONLY, and as soon as their function is complete, they should be either zeroed or hashed in-place or something else to make it impossible to derive them.

If the same random number is used more than once, it exposes information about what it is, the same way that using a one-time pad more than once exposes information about what it is. Which is why it must be kept secret... which is why it must be kept safe... and which is why it must be burned.

There's undoubtedly more to this than I'm putting in -- I'm writing this on very little sleep, and I'll likely look at it and figure out where and how it needs to be fleshed out -- but it's important to recognize that all three of the questions asked at the beginning must be answered for any cryptosystem to remain secure.

Comments: Post a Comment



<< Home

Archives

2006-02-12   2006-02-19   2006-02-26   2006-03-05   2006-03-12   2006-03-19   2006-03-26   2006-04-02   2006-04-09   2006-04-16   2006-04-23   2006-07-23   2008-01-13   2008-01-20   2008-02-03   2008-02-17   2008-03-16   2008-04-06   2008-05-11  

This page is powered by Blogger. Isn't yours?