[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: randomness & perfect forward (or proactive?) secrecy


> >However, master keys may not be the only secrets whose compromise
> >can compromise old message traffic. Suppose that a pseudo-random
> >number generator is used to generate the key agreement keys.
>
> >Does anyone know if this problem has been considered at all when looking
> >at perfect forward secrecy?

Our `Network Randomization Protocol (NRP)' is addressing exactly this issue.
This is work by Chee-seng Chow and myself. It is based on the (proven secure)
protocol which Ran Canetti and myself presented in Crypto 94.

In fact, NRP achieves an even higher degree of security than perfect forward
secrecy, which I suspect is actually what both of you want. We call it
`Proactive Security', namely security recovers from break-ins.
For more info on Proactive Security see the crypto paper or several
forthcoming additional works. I'll also be happy to discuss it, but I feel
this list is not the right place.

The idea of NRP is to combine sampling methods as Phil describes below with
a distributed security-recovering mechanism based on peer-to-peer support,
much like the Network Time Protocol (NTP). Right now we only have hooks to
put your own sampling routine, but we're working on it.

For details and free code see:

  software.watson.ibm.com/pub/security/nrp.tar.

We may submit this as i-draft; we want first to complete and add a randomness
sampling routine and to port it to platforms other than AIX (it's a portable
design but we tested so far only on AIX). The priorities of these tasks
could be affected by the interest we see.

Phil, is your stuff public-domain? In this case we'll like to merge the
two systems as they appear to be exactly complementary. Or, maybe you can make
some parts public?

Best, Amir Herzberg
p.s. Chee-seng, let's discuss this.

Enc: response from Phil

>
> Yes. I consider random number generation to be the Achilles heel of
> all these schemes, and I've given mine a lot of thought. The random
> number generator in my current code was inspired by PGP, but with some
> tricks of my own.
>
> In my NOS code (a TCP/IP operating environment for DOS in which I've
> been prototyping this stuff) I maintain an internal random number
> generator state that is continually "churned" by keyboard strokes and
> other random external events. That is, whenever you hit a key (for any
> purpose -- there's a direct hook into the keyboard driver) while the
> program is running, the scan code and the PC's real time clock (~1 us
> count rate) are concatenated with the previous generator state and
> hashed through MD5. The result becomes the new generator state.
>
> Whenever I need to generate random data, I hash the current state
> along with a counter. The output becomes 16 bytes of random data that
> I give to the user (e.g., a Diffie-Hellman routine). If the user needs
> more, I increment the counter and rehash as needed.
>
> In essence, I maintain a "reservoir" of entropy, adding to it whenever
> I can and drawing from it as needed. Assuming the reservoir is
> reasonably full when I start, I can continue to generate random data
> even without the addition of additional entropy at the cost of
> degenerating from theoretical randomness (can't guess the sequence
> even with unlimited computer power) to practical randomness (can't
> guess the sequence without enough computing power to invert MD5).
>
> One not-quite-resolved problem is an unattended system that never sees
> any keyboard activity. A security gateway, for example. I do try to seed
> the generator state at startup with a few tricks:
>
> 1) hashing all of main memory, including Ethernet and disk buffers,
> BIOS data, etc
>
> 2) Reading the 1uS time-of-day count in a tight CPU loop and hashing the
> results. On some (but not all) machines that use separate crystals to
> clock the CPU and the TOD clocks, you'll get a fairly random-looking
> dither in the increment between successive clock reads. This doesn't work
> for all PCs, though, especially the newer ones that generate all their
> clocks from a single crystal and a PLL synthesizer.
>
> I do need to add a few more tricks I've heard about, e.g., timing
> floppy disk and/or hard disk accesses, and perhaps hashing cleartext
> packets. And it probably wouldn't hurt to save the random state on
> disk when shutting down so I can use it as yet another source of
> entropy when starting up, much like PGP's randseed.bin file.
>
> Phil
>
>
>
>
Follow-Ups: References: