Random Numbers,

Posts,

and

CryptixTM

Intro

Random Posts on Numbers. Important topic. Mucho ranto. Need Ed. Apply within.

Sources of Random

F.Baube(tm) <fred@moremagic.com> asked what should have been a simple question:

We're trying to find a good source of random for Java clients. The 3.0.3 docs talk about writing a utility to gather mouse input, but I for one have no idea how to convert mouse motion timestamps and coordinates into entropy.

Has anyone thought of using keyboard input ? The timestamps might not be very granular, but the order of keypresses should be preserved, and if you can stop the user from ping-ponging between a pair of keys, or running his/her finger along a row of keys, you ought to get some usable entropy, maybe as much as five bits per keypress.

Any thoughts on this ? Has it been done already ?

One way to prevent the use of simple finger-press patterns, and force the user to bang away at random, might be to say that none of the last 15 keys pressed are valid for the current keypress. That way you still always have about half the alphanumeric keys valid at any point, so the user will still be able to generate action on the progress bar if s/he really does move them fingers around.

You could also have checks to disallow adjacent keys, e.g. any of the sequences "as", "sd", "df", "dr", "r5", "54", "4e" (this is on a Euro keyboard), and that would disallow other common nonrandom (read: lazy) keypress patterns.

Fred Baube

Use Mouse Movements

Stephen Vermeulen <svermeul@netcom.ca>

For a project I did about 6 months ago I used mouse movement information, essentially I took the least significant couple of bits off the mouse x and y positions along with a few bits from the event time and accumulated these in into an MD5 sum. Worked quite well.

The Red Book (Scheiner's Applied Crytpo) has a section on generating randomness that suggests this technique and cautions one to only take a few bits from each independant source.

Stephen

Bits of Entropy versus Hash Data

Bill Frantz <frantz@communities.com> :

At 08:44 AM 1/20/98 -0700, Stephen Vermeulen wrote:

>For a project I did about 6 months ago I used mouse movement information,
>essentially I took the least significant couple of bits off the mouse x
and y positions
>along with a few bits from the event time and accumulated these in into an
>MD5 sum.  Worked quite well.
>
>The Red Book (Scheiner's Applied Crytpo) has a section on generating
>randomness that suggests this technique and cautions one to only take
>a few bits from each independant source.

There are two separate issues: (1) The number of bits of entropy you estimate you have gained, and (2) The data you pass through the MD5 checksum. Because mixing functions like MD5 allow you to combine bad entropy and good entropy getting good entropy out, I am in favor of passing lots of bits to MD5, but only assuming a few bits of entropy.

Another gotcha in this space is the granularity of the clock. On Windows/95, calls to System.currentTimeMillis() seem to have a granularity of about 50 milliseconds. If you can use native code in your system, it is probably better to use the CPU performance counters for "timing" information. (If you the performance counters, send all the bits to MD5. My experiments show the low order bit to be correlated, but the higher order bits to be not correlated. Why is another one of life's little mysteries.)

The FIPS-140 standard gives techniques for testing random number generators. If there are no obvious biases in the random source, and it passes FIPS-140, it is probably fairly good.

Theoretically, Java cannot provide Entropy

Amos Elberg <aelberg@wesleyan.edu>

>You could also have checks to disallow adjacent keys, e.g. any
>of the sequences "as", "sd", "df", "dr", "r5", "54", "4e" (this
>is on a Euro keyboard), and that would disallow other common
>nonrandom (read: lazy) keypress patterns.

There's no access in java to the layout of the keyboard, so this is impossible.

I've said something on this subject before that I now feel the need to reaffirm in stronger language. All known methods of generating entropy (with the exception of user-selected passwords) rely on machine-specific techniques because they all attempt to access information that exists beyond the deterministic confines of the machine. But all of these methods, timing keypresses, mouse movements, etc. depend on the underlying characteristics of the machine for efficacy. Differences not just in granularity of time, but also in what the system considers a mouse movement, the size of a pixel, the speed of the system clock, the bundling of events by the OS or virtual machine, and endless other details determine what entropy generator will work on a given platform.

Given this state of affairs, it is not just impossible to write a secure entropy source in pure java, it is dangerous to try. Code that generates entropy on one virtual machine may be deterministic on others (in fact, this is definitely true of mouse movement detection and the mac vm), and the code might even break from minor changes in VM version, bug fix, or change in the implementation of a GUI element. The user will never know the difference.

It is simply the nature of writing in java that the only behaviors you are guaranteed are those spelled out explicitly in the language and vm specifications. There is currently no good source of entropy in those specifications. Our best strategy for getting a good source of entropy in java is to concentrate our efforts on lobbying sun to add such a source to the VM specification. Any other option is virtually guaranteed to mislead the user into thinking entropy is being generated, when in fact none is.

-Amos

Dvorak?

F.Baube(tm) <fred@moremagic.com>

Surely sendmail reeled when thusly spake Amos Elberg:

> >You could also have checks to disallow adjacent keys
> 
> There's no access in java to the layout of the keyboard,
> so this is impossible.

True, it would permit low-entropy keyboard entry from (say) a Dvorak keyboard.

Fred Baube

VMs cannot generate entropy

Amos Elberg <aelberg@wesleyan.edu> started the ball rolling with:

A couple of people have flamed me about this, and others asked for more information, so let me elaborate just a bit. A virtual machine is a correct, working implementation of java if and only if it implements exactly the behaviors set forward in the VM specification. That specification, intentionally, leaves anything that might be impossible to achieve on a particular platform open to interpretation. The API's, however, do not always make this explicit. A good example is the Thread.sleep( long ) call. The call is accurate to the millisecond. The VM does not require an implementation to have a clock accurate to the millisecond, or the ability to time threads that accurately.

Those areas that are left "open" to implementation happen, not by coincidence, to be exactly the same areas that we rely on to get entropy: the interface between the deterministic, finite state machine in the computer and the non-predictable, infinite state real world. It is exactly those properties of non-predictability and infinite granularity of state that we use to get entropy. But precisely because every machine is built differently, and has a different interface to the real world, the VM spec does not assume one in particular.

For instance, it requires that every time a key is clicked, the peer with the focus gets an event. It does not specify if those events should be handled separately, or if when keys are being pressed rapidly they should all be packaged first then sent to the component in rapid succession. It specifies that when a Thread is killed, it gets a ThreadDeathExcpetion; it does not specify exactly when this needs to occur. In most current implementations, it occurs when a call to native code returns.

As a consequence of this, any code that relies on idiosyncracies of a particular VM implementation, as all of the ideas so far put forward (and I believe all _possible_ ways of getting entropy from the user) have, will not neccessarily run on every other, or any other VM.

To respond to one flame I got, the MRJ VM is not hopelessly broken or unusable; in fact, it works quite well. It just handles mouse events in a very different way, because the OS underneath handles mouse events in a very unusual way. -Amos

Going outside Java: Using Servers and other sources

Tim Shuttleworth <tim@mcc.ac.uk> responded:

You write:
> I saw an article in  a recent issue of Science News or Scientific
> American which said that Silicon Graphics was developing a
> random number generator based on an array of six lava lamps
> and a digital camera. While I'm not sure how random any such
> arrangement could be (won't anything that isn't based on quantum
> uncertainty prove to be merely complex?), it seems to me that a
> method based on the data entered or collected rather than on the
> precise timing of the entry or collection may solve the problem
> you have described. What do you think?

I look forward to the Java Lava Extension! :^)

More seriously, I believe that the real issue here is that we require a source of randomness which is not correlated with the behaviour of the application and/or JVM. This could either be from the timing of "external" events, or data collected from "external" sources (i.e. data not deterministicly produced from our program). In either case, however, we presume that we have access to sources of information over whose behaviour is uncorrelated with the behaviour of the application. In any real-world systems, such sources surely exist (be they the time-stamps on mouse movements, or the contents of system IO buffers). However, the JVM (currently) doesn't guarantee any access to these data sources: if we happen to find one, there's no way we can rely on it in generally, because there's no contract with the Java language that says that method is going to work in all situations.

Having said that, you can go "outside" of the current Java environment if you are prepared to accept that your application depends on something other than 100% Java resources. In the case of the Lava lamps idea, how about having a server which accepts a public key from clients which wish to use the service. It grabs a picture of a lava lamp, generates a random number, signs it, encrypts it with the public key and transmits it back to the client, which decodes it, checks the signature and seeds the internal random number generator (or whatever it wants to do). [The encryption and signing are there, of course, to prevent eavesdroppers listening in, and spoofers from responding to the request. You'd also have to add some redundancy (to ensure that gibberish can't be sent back: after all, how do you recognise a spoofed random number! :^), and timestamps to prevent replay attacks (gosh this is getting awfully complicated, isn't it?)

If you haven't got a Lava lamp random number generator handy, you could write a server in C which simply made a call to the appropriate platform dependent source of randomness (e.g. /dev/random on some Unixes). In fact, using a secure protocol with an "external" server (which could, of course, run on the same machine -- provided you can guarantee this won't affect the randomness), you provide a choice in the source of randomness (if you find the server has a flaw, point the application at a new server).

The alternative, and possibly preferable, option would be for Sun to put a secure random number generator into the JVM specs. Anyone care to comment on how secure the SecureRandom seeding process is? (It looks a bit dodgy to me: the JDK docs say "It relies on counting the number of times that the calling thread can yield while waiting for another thread to sleep for a specified interval". Call me cynical, but I think that's likely to have widely varying levels of randomness on different platforms.)

Tim.

Use /dev/random on machines that have it

David Hopwood <hopwood@zetnet.co.uk>

In message Tim Shuttleworth wrote:

> If you haven't got a Lava lamp random number generator handy, you could
> write a server in C which simply made a call to the appropriate platform
> dependent source of randomness (e.g. /dev/random on some Unixes).

No need to use C to do that:

try {
    DataInputStream dis = new DataInputStream(new FileInputStream(
        "/dev/random"));
    byte[] seed = new byte[40];
        // 20 bytes is the size of the SecureRandom PRNG state; double it
        // for luck.
    dis.readFully(seed);
    // mix seed (using SHA-1) with that produced by sleep-and-count.
} catch (Exception e) {
    // have to rely on sleep-and-count method alone.
}

Cryptix 3.0.4 will probably replace the java.security.SecureRandom class, in which case it will use code similar to this.

> The alternative, and possibly preferable, option would be for Sun to put
> a secure random number generator into the JVM specs. Anyone care to comment
> on how secure the SecureRandom seeding process is? (It looks a bit dodgy
> to me: the JDK docs say "It relies on counting the number of times that
> the calling thread can yield while waiting for another thread to sleep for
> a specified interval". Call me cynical, but I think that's likely to have
> widely varying levels of randomness on different platforms.)

I think it should be reliable on Win32, Solaris with native threads, and most Unices with Green threads, providing untrusted code is not being run in the same VM. If untrusted code is being run, there's a possibility that it could interfere with the thread that is doing the count.

The PRNG used by SecureRandom is probably OK as well; SHA-1 would have to be severely broken in order for it to be feasibly attacked (more broken than MD5 is thought to be, for example).

- --

David Hopwood

Usefulness of Entered Numbers - Passwords

Bill Frantz <frantz@communities.com> :

>>...
>>random number generator based on an array of six lava lamps
>>...
>
>I think its called password security.
>-A

While we call it entropy, what we really want is unguessable numbers. It matters less that they are theoretically unguessable than that they are unguessable in practice. While the ideal source would be some quantum uncertainty generator, it is no good if Mallory can observe the same things you are observing. You probably do better using the local keyboard and mouse than by reading a perfect quantum source over a network.

Our best practical defense is to combine several sources of unguessable numbers with a cryptographicly strong combining function, (e.g. a crypto hash). Unguessable numbers have the nice property that if you combine 5 sources, 4 of which have been broken, you still get unguessable output.

The Java 1.1.3 SecureRandom function uses one source, the number of times a thread can yield in a time interval. This technique has some respectability including a paper by Steve Bellovin. The 1.1.3 implementation has some bugs which occasionally cause the function to never terminate, but there have been fixes release in later versions. The combining function is SHA, but SecureRandom keeps a pool of only 160 bits, which is a bit small for my taste.

Java - not secure against the Trojan Horse

Geoff Thorpe <geoffthorpe@rocketmail.com>

I have to admit that the study of "good random source" is not my cup of tea, but of course it's important to crypto. However, to my amateur mind, it seems that this is all getting a bit over-the-top. I believe the above, in a sense, hits the nail on the head - "external" sources. The question is; external to what?

If you are concerned about network hacks, then I think the "random" problem is easily solved - you just (cryptographically) hash up a bunch of information that is only known locally to the machine (mouse movements, processes running, a dump of lots of kernal stats, whatever). The bigger problem is if you are trying to protect against potentially insecure hardware (i.e. if an attacker has access to the machine) - in which case I think a lot of this carry-on about convoluted random sources is pointless - yes, you can use mouse-input and look at higher-order derivatives; yes, you can use lots of kernal stats and IO data. The problem is that any trojan process can use all this info too (typically) and in effect the "randomness" is busted. In his cryptlib library, Peter Gutmann has gone to the nth degree in trying to get good random data, and locking sensitive data.

I personally wouldn't trust Java to provide any kind of protection against an attack of this kind - for example there's no real protection against a "copy" of a password remaining in memory after the garbage collection has dealt with it, so who really cares about randomness beyond info not available to the network layer? As for lava lamps ...

By all means, set me straight!

Cheers, Geoff

Entropy - hard to find

Amos B. Elberg <aelberg@wesleyan.edu>

> The question is; external to what?

A computer is a deterministic machine. Worse, its a finite state machine. External to that.

 > If you are concerned about network hacks, then I think the "random"
 > problem is easily solved - you just (cryptographically) hash up a
 > bunch of information that is only known locally to the machine (mouse
 > movements, processes running, a dump of lots of kernal stats,
 

Therein lies the rub. There is an entire mathematical discipline - information theory - dedicated to figuring out how much of that information is entropy and how much redundancy. (Well, they do other things as well :P) As it turns out, its very difficult to get a lot of good entropy in the way you describe. Systems that work like you propose are possible (not in java) but are very easy to screw up. Netscape made that mistake in an early browser. Once a weak system is in place, it turns out to be relatively easy to figure out what the initial random value was. (Well, its actually quite hard, and what you do is relate some bits to others and try to eliminate possibilities, but its better than 2^n).

 > whatever). The bigger problem is if you are trying to protect against
 > potentially insecure hardware (i.e. if an attacker has access to the
 > machine) - in which case I think a lot of this carry-on about
 > convoluted random sources is pointless - yes, you can use mouse-input
 

No, you can't use mouse input in java. See the rest of the thread. You're right that there are other areas of attack in java; but poor random number selection can provide an attacker with an unneccesary, possibly easy, target.

 > I personally wouldn't trust Java to provide any kind of
 > protection against an attack of this kind - for example there's no real
 > protection against a "copy" of a password remaining in memory after
 > the garbage collection has dealt with it, so who really cares about
 > randomness beyond info not available to the network layer? As for lava
 

Why bother putting DIMMS under an electron microscope when you can decrypt something encrypted with poor random sources in a few minutes of computer time?

This is like saying "if a plane crashes into my car I'll still die, so I won't bother wearing a seat belt."

-Amos

The Big Question - balance of risks

Tim Shuttleworth <tim@mcc.ac.uk>

You write:

> Why bother putting DIMMS under an electron microscope when you can
> decrypt something encrypted with poor random sources in a few minutes of
> computer time? 

The most important question when considering the security of a system is, surely, not "is this secure" (because any system will have its weak links, be it technology or people), but rather "does this cost more to crack than the value of the information that would be revealed by cracking it". You can't build a usable system that is absolutely secure (even if it comes down to cracking it with "Rubber Hose cryptography"), because, unless you can read minds, you can't distinguish between those people who are using the system legitimately, and those people who are accessing the system for nefarious purposes (after all, most bank fraud is committed by authorised employees).

I guess the difficulty comes from the "what if" scenarios: what if someone has direct access to the memory of the machine that the JVM is implemented on (Sun's answer would, of course, be that you should use a full JavaOS based system, so that no-one can get access to the memory); what if someone can fool you into down-loading their Trojan horse code (Java's answer would be to use signed code, with a reputable key authority at the top of the tree; Java itself prevents trusted code from peeking too closely at other code on the system). The problem is that hackers don't usually try to break systems in the ways you thought they should when you designed the system (witness the Netscape problem: the protocol was sound in principle, but it wasn't the protocol that was cracked!) In one of Ross Anderson's papers, he describes how they cracked a "secure" cryptochip, by putting high-frequency spikes on the power lines, and getting it to (eventually) execute an instruction incorrectly, causing it to output all of its secret keys. The chip had tamper-proof coatings, electromagnetic doo-dahs, etc. etc., but varying the power supply: that's hitting below the belt!

The recent cracking of 56 bit RC5 is a case in point: now that it has been cracked, would you use it? I'm fortunately not in the position of having to choose, but in most cases of "low importance" data, I still wouldn't be too concerned: it took something like the equivalent of 6,000 Pentium 90s over 100 days to crack one message. I don't think *anyone* is that desperate to read my email! In practice, I'd be much less concerned with "is RC-56 secure" than "is my implementation of RC-56 secure", or "is the protocol I'm using it in secure", and even "will it be deployed in an environment where the security of the protocol is the weakest link in the chain".

Unfortunately, taking a view of the system as a whole is a messy, and largely non-mathematical business. You've got factor in things like "can people be relied upon to keep their passwords secret" (which takes us back to one of the earlier comments), and "how much is my data worth" (in the case of financial data, that may relatively easy, but how do you put a value on company secrets, or a personal reputation?). On the other hand, it doesn't do to ignore the technological side of things, either. And if you decide that random numbers are a primary weakness in your system, then you really do need something better, something which Java doesn't appear to provide at the moment. How much better (i.e. how random) is something only a system's designer can really answer. Many of the arguments that arise about the merits of a particular method of obtaining random number boil down, in some sense, to one designer requiring (or believing they require) "randomer" numbers than another.

> This is like saying "if a plane crashes into my car I'll still die, so I
> won't bother wearing a seat belt." 

Funnily enough, one of the early arguments against seat belts (I believe, promoted by the car industry, eager to cut costs) was that the sense of security provided by seat-belts would promote reckless driving, and lead to increased pedestrian casualties. There's probably a moral in there somewhere!

Tim.

Bang the Keyboard - should work

F.Baube <fred@moremagic.com>

Surely sendmail reeled when thusly spake Amos B. Elberg:

>
> Once a weak system is in place, it turns
> out to be relatively easy to figure out what the initial random value was.
> 
> No, you can't use mouse input in java. See the rest of the thread. 
> You're right that there are other areas of attack in java; but poor 
> random number selection can provide an attacker with an unneccesary, 
> possibly easy, target.

After this thread, I still think it might be reasonable to ask the user to bang in some keyboard input, and then do some simple filtering out of low-entropy sequences. (Sort of like the chimpanzees producing Shakespeare ? :-)

So that it made sense to users, the manual would say something roughly like

        "This program needs some random numbers to calculate 
         a starting point to look for a large prime number. 
         But it's a fact that this program (and you) can't 
         quite be sure how 'random' things like mouse moves 
         and file activity times are after your computer has 
         processed them.  So, type like a mad(wo)man until 
         the program says stop, and the more random your 
         keystrokes are, the better.  blah blah blah blah"

I think that after the whole ActiveX-vs-Java brouhaha, users with even just a glimmer of technical savvy might get the picture.

Fred Baube

Good sources of User-Machine Entropy

Bill Frantz <frantz@communities.com>

At 02:09 PM 1/27/98 -0500, Amos B. Elberg wrote:

>Wrong. A computer is a deterministic machine. So is a hard drive head.
>Excepting mechanical failures, all behaviors of the drive that are
>accessible from the computer, and especially the virtual machine, are
>deterministic.

The issue is not whether the computer is deterministic, but whether others, outside the computer, can determine its state. (IMHO, if you have a Trojan horse problem, you're toast.)

The computer + its user is not a deterministic machine. Amos has contended that you can't use UI events for entropy. I still don't understand. He may be saying:

>So do I. This nonsense recently about lava lamps really blow my mind. You
>can put a secure random number generator on a logic board for like $2
>using a simple microphone.

I also like the entropy available from microphones, particularly the differences between the inputs of stereo microphones. What I don't like is the idea that a Trojan horse can listen to all the conversations in the room. I have heard, but NOT tested, that the low order bit of 16 bit input cards is noisy. I can also think of a bunch of attacks on it, and not everyone has 16 bit sound input, particularly server machines.

No doubt a quantum source of entropy could be cheaply added to computer mother boards. My understanding is that the US government frowns on this kind of hardware, and in the incredibly price competitive PC mother board market, two dollars can be the difference between profit and loss. Between these two reasons, we don't have such hardware. Asking for it is fine. Expecting to get it installed on everyone's computer is dreaming.

My own personal recommendations:

For an example of some of these recommendations reduced to code, see the PGP5 randpool.c source. (Available from servers in the free world.)

With some Criticisms

Amos B. Elberg <aelberg@wesleyan.edu>

> The computer + its user is not a deterministic machine.  Amos has contended
> that you can't use UI events for entropy.  I still don't understand.  He
> may be saying:
> 
> * You can't get as much entropy from UI events as you think you can.
> * A keyboard/mouse sniffer can steal all your entropy.
> * The JVM makes no guarantees which allow you to place a lower bound on the
> amount of entropy you get from a UI event.  He has said that the Macintosh
> is particularly bad in this area, but has not provided details.

The third is closest to what I am saying. Let me try and explain it, again. In Java, you have access only to what is provided by the JVM. The JVM currently does not provide access to entropy. It's specifications for UI events are not precise enough to guarantee that sampling of UI events will provide any particular amount of entropy.

> I also like the entropy available from microphones, particularly the
> differences between the inputs of stereo microphones.  What I don't like is
> the idea that a Trojan horse can listen to all the conversations in the
> room.  I have heard, but NOT tested, that the low order bit of 16 bit input
> cards is noisy.  I can also think of a bunch of attacks on it, and not
> everyone has 16 bit sound input, particularly server machines.

An open mic placed inside the machine should provide entropy in the low order bit. There was a Scientific American article about this a few years back. Further, even if you bug the room, the sound will be different (esp. in the low order bit) at different locations in the room.

> Expecting to get it installed on everyone's computer is dreaming.

I expect that it will be on option on premium server logic boards this year, and it will trickle into workstation boards within a few years.

> * Use as many sources of randomness as you can.

Our discussion is about trying to find these.

> * Combine them with MD5 or SHA, and keep at least 1000 bits of entropy
pool.

This does little if your original source of entropy is poor. I seem to remember the open mic system getting ten bits of entropy a second.

> * When using UI events, always stir the time into the pool, as well as the
> event value.

Irrelevant if events are pooled by the OS.

> * When using keyboard events, don't count any key which is repeated in
the
> last 4 or 5 keystrokes as contributing to the entropy, but it is fine to
> stir it into the pool.

There's extensive research on methods like this. Take a look at them.

> * When using mouse events make sure that the first and second derivatives
> of the mouse position are non-zero on at least one axis before counting the
> event as contributing to the entropy.

Doesn't the effectiveness of this depend on how often mousemoved events are sent by the OS? I doubt any OS's send them with every pixel.

> For an example of some of these recommendations reduced to code, see the
> PGP5 randpool.c source.  (Available from servers in the free world.)

Yes, a good example of how you can get entropy when you have direct access to hardware.

-Amos

...but Java doesn't have a User

Amos B. Elberg <aelberg@wesleyan.edu>

Here's another way of getting at the problem. All of these ideas for getting entropy through the UI make a dangerous assumption: that the program will have a UI. They seem to all come from the point of view of encrypting e-mail and creating user keys. Well, one of the major places java is appearing is embedded devices. Another is servers. These often do not have users either in front of them, or willing to fiddle with a mouse for five minutes generating entropy. One of the places I'd like to use cryptix is for client-server communication through the next version of an app I'm writing. THe server will run inside Oracle 8.1's java vm. I don't plan on hiring someone to move the mouse around on that machine 24 hours a day.

Oh, and one class of devices almost guaranteed to be using java at some point this year already are available with hardware based entropy generation. We from Jersey call them MAC's, but they're generally known as ATM machines. There's already talk about putting java into smart cards and smart card readers, the new generation of ATM's. Where's the mouse? Where's the keyboard?

-Amos

Practically, we must have a solution

Bill Frantz <frantz@communities.com>

First of all I want to make clear that I agree with Amos,

  If JCE is to be cross platform, the entropy source problem must 
  be solved in a platform independent way.

Given that it hasn't been solved yet, and I also have products to ship, I need to look at other ways of solving the problem. I have a bit more flexibility than Amos. I can use native methods and I only have two platforms that I need to support this year.

I attacking the problem I developed the following theory: If I can get 90 bits of pure entropy, and keep it secret, then I don't need any more entropy for the life of my application (20 years). The 90 bit number comes from Blaze et.al's paper on the length of symmetric cryptographic keys.

Since I don't believe I can get pure entropy, I immediately raised the quantity to 160 bits. (A bit like an airplane manufacturer building to 150% of design strength.)

Since I don't believe I can keep my entropy secret for 20 years, I continue to gather entropy and stir it in. Since I do believe I can keep it secret for a few hours, I don't kill the performance of my application gathering this entropy.

At 06:33 PM 1/27/98 -0500, Amos B. Elberg wrote:

>Here's another way of getting at the problem. All of these ideas for
>getting entropy through the UI make a dangerous assumption: that the
>program will have a UI.

We also have the server problem. We found a way of gathering entropy on Wintel platforms using native code which seems to work. For other platforms we use the JavaSoft SecureRandom default seeding technique. Fortunately, servers don't have to startup as fast as clients.

>THe server will run inside Oracle 8.1's java vm. I don't
>plan on hiring someone to move the mouse around on that machine 24 hours a
>day.

I would start a low priority thread that uses the JavaSoft thread yield technique to periodically (re)seed the random number generator. I am much less scared of that technique now that I have spent time testing it. (However, this whole area still scares me silly.) If there are additional sources available on the hardware (e.g. /dev/random), I would start a thread that uses these.

Again, these solutions aren't cross platform, but I can ship them this year.

>> * When using mouse events make sure that the first and second derivatives
>> of the mouse position are non-zero on at least one axis before counting the
>> event as contributing to the entropy.
>
>Doesn't the effectiveness of this depend on how often mousemoved events
>are sent by the OS? I doubt any OS's send them with every pixel.

I model mouse tracking (as opposed to mouse clicks) as the system posting the current position of the mouse to the event queue on a periodic timer. In cases where the event queue is not being serviced quickly enough, some of these events may be lost. Ensuring the derivatives are not zero shows that the mouse has moved. I assume it is very difficult for people to move a mouse over an exact path, as reported by the mouse position, even if they want to. So, every mouse movement event that passes the derivative tests is scored as contributing one bit of entropy.

Again, I am fortunate enough to be able to test my supported configurations. Since some of us dream of supporting Macintosh some day, I am still interested in where Mac mouse handling is different.

In the absolutely worst case, I can use the os.name, os.arch, and os.version properties to select the best routines for the platform. (If I can afford to run them all, I will because of the way entropy sources combine.)

Problems with Threads

Amos B. Elberg <aelberg@wesleyan.edu>

> I would start a low priority thread that uses the JavaSoft thread yield
> technique to periodically (re)seed the random number generator.  I am much
> less scared of that technique now that I have spent time testing it.
> (However, this whole area still scares me silly.)  If there are additional
> sources available on the hardware (e.g. /dev/random), I would start a
> thread that uses these.

I would like to say, first of all, that I've been thinking about the idea of continuous entropy gathering in a background thread for a long time, and I believe that it is absolutely the best way of gathering entropy. On the other hand, the question of _where_ to get your entropy from, as opposed to when, remains to be solved. Further, the app may encounter an interesting problem on some platforms, especially Windows95. The rate at which threads of different priorities are given time is not specified in the VM; I seem to remember reading that there are serious problems with thread priorities in Win95, and low priority threads may not run at all until higher priority threads are asleep.

The solution I've adopted when I need background polling is to keep the priority of my bg thread normal, but have it Thread.sleep() for a specified amount of time at the end of its while(true) loop.

> Again, I am fortunate enough to be able to test my supported
> configurations.  Since some of us dream of supporting Macintosh some day, I
> am still interested in where Mac mouse handling is different.

I haven't fully explored the new MRJ2 VM yet, but just an example, MRJ1/1.5 did not send mouse moved events, and it sent mouse_enter but not mouse_exit events. Details of MRJ2 are still be researched and appearing on the MRJ listserv.

 > In the absolutely worst case, I can use the os.name, os.arch, and
> os.version properties to select the best routines for the platform.  (If I
> can afford to run them all, I will because of the way entropy sources
> combine.)

You can do that with 2 VM's, maybe with 10, but with 1000? If you can pick your VM, you're fine of course; the problem occurs when you can't.

-Amos

Hashes in random number generation

Amos B. Elberg <aelberg@wesleyan.edu>

One common thread in random number generation appears to be the use of a secure one-way hash function. Now, there is absolutely no reason why running a value through a one-way hash would _add_ any entropy. Here are the three reasons why I believe hashes are used; please let me know if there are any additional reasons to use a hash.

  1. Hashing a number guarantees that regardless the size of the input, the output will be a fixed size.
  2. Hashing a number spreads out the entropy of the original number. For instance, in ascii text there is no entropy in the high-order bit; hashing text spreads out what little entropy there is among the entire length of the hash. This makes it more difficult to predict a key made from the hash using statistical analysis of the pseudo-random source.
  3. Most applications use the same entropy repeatedly, as a random "seed". The seed is then fed into a signal generator (LSRG or whatever; I hate that acronym) to produce keys. If a single key based on that seed is broken, the entropy is recovered, and by feeding it into the same signal generator all keys based on that entropy used after the broken key are then recovered. Use of a hash makes it more difficult to recover the state of the signal generator.

I'm writing this because I've gotten the impression from some of the posts here that many people think feeding a pseudo-random number into a hash function produces a true-random number, or produces greater entropy. A hash function is not part of a random number generator; rather, it is a tool used later on in the cryptographic process to prepare a random number for use.

-Amos

More Hashes

Bill Frantz <frantz@communities.com>

Some additions:

What I do is replace one hash-output length block of the pool with a hash(the entire pool concatenated with the new entropy).

Let me summarize.

Uri Blumenthal <uri@ibm.net>

  1. Even without specialized crypto hardware, you can obtain true randomness from a generic PC computer.
  2. In order to do so, you must be able to access the (raw) hardware.
  3. A good operating system is doing it for you (hint: I'm not talking of Windows :-).
  4. Despite all of the above, nothing beats crypto iron.

Regards, Uri

Review of Summary

Amos B. Elberg <aelberg@wesleyan.edu>

> 1. Even without specialized crypto hardware, you can obtain
>    true randomness from a generic PC computer.

Without specialized crypto hardware, it is very difficult but possible to obtain entropy on a generic PC; the best methods for doing so require user interaction.

>  2. In order to do so, you must be able to access the (raw)
>     hardware.

The closer you can get to raw hardware, the better chance you will have of getting entropy.

> 3. A good operating system is doing it for you (hint: I'm
>    not talking of Windows :-).

For user interaction sources of entropy to work, arbitrary measurements of mouse position and a very precise system clock are helpfull if not required.

> 4. Despite all of the above, nothing beats crypto iron.

What is crypto iron?

-Amos

References

Ross A. Finlayson <raf@tomco.net>

Hi folks,

Thought this was interesting re: true randoms.

http://www.fourmilab.ch/hotbits/

Random numbers from radioactive decay.

Ross A. Finlayson


Cryptix Copyright © 1997 Systemics Ltd
on behalf of the Cryptix Development Team.
All rights reserved.
Cryptix is a trademark of Systemics Ltd.