Fast Random Number Generation For Encrypted FS?

Signal 11 asks: "I've been reviewing different filesystem-level encryption schemes and so far, I have found only one solution - applying a kernel patch and using the loopback device. The problem is in generating large amounts of random data to seed the initial filesystem - it takes about 16 hours to create 20GB of pseudo-random data from /dev/urandom. Is there a faster (and equally secure) way to generate large amounts of random data?" Any clues? I'd figure a kernel patch to turbocharge /dev/urandom (while not losing too much security) might be another route to take.

Comments

How much randomness do you actually need?

[nweaver]

One question to ask is how much randomness do you really need? Depending on the application, you either really have no choice but to sit down and let the system's mix of pseudo random number generation and physcial system measurements generate enough bits. IIRC, linux systems use a mix of measurements (disk timing, keystrokes, mouse behavior) and a pseudo random number generator to create these bits. This makes them pretty GOOD random bits, but slow to gather.

But often you can get away with a GOOD pseudo random number generator, that is well seeded, to generate the mass of bits you need. You only actually need, say, 256 truely random bits to get the job done.

In which case, the easiest thing to do is grab a bunch of 8 sided dice, and roll them a bunch of times to seed your favorite cryptographically secure PRNG, and then use that to get all the pseudorandom bits you want. (8 sided dice are nice, because each roll generates 3 bits of entropy).

For information on PRNGs, go look through Applied Cryptography or a similar text.


Nicholas C Weaver
nweaver@cs.berkeley.edu

slightly OT question: leaky encrypted fs?

[Daffy Duck]

My main question is: what is the reason for filling the file with random data before creating the filesystem?

And the reason I ask is that I've just installed the international patch and started to mess around with the loopback filesystem, and I've noticed that even after the random initialization the encrypted data isn't completely random-looking.

As a simple test, I made a 1MB encrypted filesystem using the serpent cipher, and inside that I created a 900K file full of a repeating 8-byte sequence. Then I unmounted the filesystem.

The 1MB container file is compressible down to 320K by gzip. This doesn't seem right to me - shouldn't there be almost no redundancy in the encrypted file? Further investigation shows that about 930 of the 1024 1K blocks in the container occur in repeated groups of four blocks. The data inside each block are certainly scrambled beyond human recognition, but isn't this exposure of the cleartext's redundancy a sign of something wrong?

Is it my fault? I followed the encrypted loopback HOWTO to the letter. Anyone know what's up?

Strength of Hash function

[drig]

Linux's random device uses a SHA hash to mix the seed and produce decent random numbers. SHA may be a bit more than you need. If you were to change linux/drivers/char/random.c to use MD2 instead of SHA1, you'd probably get a noticeable speed up.