Java Cryptography

Keyboard Timing

In this section, I’ll develop an alternate method of seeding a SecureRandom. This method is based on measuring the timing of keyboard events, a method that has been used for years in PGP (Pretty Good Privacy, a popular cryptography application). The basic idea is to measure the time between successive keystrokes using a fast timer (a resolution of 1 millisecond or better is preferable). For each keystroke, one or two low-order bits of timing information will appear random. Take as many bits as you need to seed your PRNG. Even a very good, very consistent typist will probably not be able to type with millisecond precision, which means the seed bits are truly random.

This method does require that the user type data for a few seconds, which is not particularly user friendly. In contrast, the self-seeding algorithm in SecureRandom has no impact on your user interface, except that it will hang up your application for a few seconds the first time it is run. The method presented here, however, is under your control.

Seeder

The Seeder class listens to KeyEvents and builds up a seed value of a certain length. When the seed is completed, Seeder will fire off an ActionEvent. Seeder doesn’t care where the keyboard events come from; it just implements the KeyListener interface. We’ll make Seeder part of the oreilly.jonathan.util package, so that we can easily use it later.

package oreilly.jonathan.util;

import java.awt.AWTEventMulticaster;
import java.awt.event.*;

public class Seeder
    implements KeyListener {

Internally, Seeder stores the seed value in a byte array, called mSeed. An integer, mBitIndex, serves as the current bit index. The mDone member variable indicates whether the Seeder is done gathering seed bits. Seeder also keeps track of the last key character it received. It rejects repeating keys because the timing of repeated keys may be predictable, and this would mess up our supposed random seed value. Seeder uses an ActionListener member variable to keep track of who gets notified when seed generation is complete. And finally, a Counter member variable keeps track of the object that measures the time between keyboard events. You’ll see the Counter class later.

protected byte[] mSeed;
  protected int mBitIndex;
  protected boolean mDone;
  protected char mLastKeyChar;
  protected ActionListener mListenerChain;
  protected Counter mCounter;

Seeder has only one constructor, which accepts the number of bytes of seed that are to be generated. The constructor simply calls the reset() method, which initializes the Seeder.

  public Seeder(int seedBytes) { reset(seedBytes); }
  
  public void reset(int seedBytes) {
    mSeed = new byte[seedBytes];
    mBitIndex = seedBytes * 8 - 1;
    mDone = false;
    mLastKeyChar = '\0';
    mListenerChain = null;
    mCounter = new Counter();
  }

The following methods provide useful information about the Seeder:

  public byte[] getSeed() { return mSeed; }
  public int getBitLength() { return mSeed.length * 8; }

Internally, the mBitIndex member variable counts down to zero. The getCurrentBitIndex() method actually returns a value that counts up from zero to getBitLength() .

  public int getCurrentBitIndex() {
    return mSeed.length * 8 - 1 - mBitIndex;
  }

Objects that wish to be notified when the seed is generated will register and unregister using addActionListener() and removeActionListener() . These calls are handled using the static methods of AWTEventMulticaster .

  public void addActionListener(ActionListener al) {
    mListenerChain = AWTEventMulticaster.add(mListenerChain, al);
  }
  
  public void removeActionListener(ActionListener al) {
    mListenerChain = AWTEventMulticaster.remove(mListenerChain, al);
  }

As a KeyListener, Seeder is notified of key press and release events. A matched key press and release is transmitted as a “typed” key. Seeder filters out repeated keys and calls grabTimeBit() for the events we receive in keyTyped().

  package oreilly.jonathan.util;

public class Counter
    implements Runnable {
  protected boolean mTrucking;
  protected int mCounter;
  
  public Counter() {
    mTrucking = true;
    mCounter = 0;
    Thread t = new Thread(this);
    t.start();
  }
  
  public void run() {
    while (mTrucking){
      mCounter++;
      try { Thread.sleep(1); }
      catch (InterruptedException ie) {}
  }
}  
  
  public void stop() { mTrucking = false; }
  public int getCount() { return mCounter; }
}

Pitfalls

Two issues governed the design of Seeder:

Timing is tricky

Counter runs in its own thread, but without knowing how Java threads work in detail, we can’t be sure that there might be some regularity in the values that Counter returns to Seeder. Originally I wrote this class to use the value of the system clock instead of a value from Counter. On my Windows 95 machine, however, the system clock (as returned by System.currentTimeMillis()) had a resolution of only 10 ms, which I felt was too coarse for comfort. I use Counter instead because it has a higher resolution than the system clock. Note, however, that this is really a variation on the thread-timing method that Sun uses as the default SecureRandom seed generation process.

Repeated keys are dangerous

The timing of repeated keys is very regular. Seeder dodges this trap by explicitly filtering out repeated keys. But are there other traps like this lurking in the Seeder class? Could you produce even timing by quickly alternating two keys? Does the keyboard device itself have some coarse interval for generating key events, so that you might be able to type faster than the keyboard could process the events?

How can you tell if Seeder’s results are truly random? There are many statistical tests for randomness, but even data that passes these tests may not be random. For interesting discussions on the mathematics and philosophy of random numbers, try these resources:

http://random.mat.sbg.ac.at/

This site, hosted at the University of Salzburg, contains information on random number generators and tests for random numbers, as well as links to literature and other web sites on randomness.

http://www.cs.berkeley.edu/~daw/netscape-randomness.html

This site contains a no-nonsense list of links to papers, source code, and hardware specifications relating to random numbers.

http://lavarand.sgi.com/

For a lighter look at random numbers, try this cartoonish site. It describes how Lava Lites^® can be used to generate random numbers.

Without a review of Seeder’s design by security professionals, and without statistical analysis of its output, you shouldn’t trust Seeder too much. It does demonstrate the basic principle of gathering random bits from timed events, however. You could modify this class to gather timing information from other sources as well, like the mouse. If you use more sources of supposedly random events, you’re more likely to get a truly unpredictable stream of data.