www.BrettDaniel.com

Most Midwestern geohashing points fall in corn or soybean fields. Yesterday's point for the Danville, Illinois graticule was different. It fell near an interesting wooded area, and the return trip passed an amazing quarry. See the trip report for the full story.

Java's java.util.Random class is used to produce a sequence of pseudo-random numbers. As part of a recent recreational programming project, I needed to copy a given Random object such that both the original and copy produced the same sequence of values. While hacking together a quick-and-dirty solution, I learned some interesting facts about the implementation of the Random class.

The usual way to ensure that two Random objects produce the same sequence of values is to supply the same seed values to two new instances.

long seed = ...;
Random r1 = new Random(seed);
Random r2 = new Random(seed);

However, in this particular project I had no control over the instantiation of the Random object, and I could not access the original seed. Ideally, the Random class would provide a getSeed method that one could use to create a new object, but Java's implementation does not. This omission is particularly strange since the class stores the value but hides it in a private member variable.

The seed is stored as a java.util.concurrent.atomic.AtomicLong for thread safety. A new seed value is XOR'd with a constant multiplier and truncated to 48 bits before being stored.

public class Random ... {
    ...
    private final AtomicLong seed;
    private final static long multiplier = 0x5DEECE66DL;
    private final static long mask = (1L << 48) - 1;
    ...
    synchronized public void setSeed(long seed) {
        seed = (seed ^ multiplier) & mask;
        this.seed.set(seed);
        ...
    }
}

The class perturbs the seed in this way to increase the period of the generator. That is, Random will produce a sequence of values that does not repeat for a very long time. How long? This analysis by a University of Utah mathematics professor says, "the period of the returned values should be 2^48, which is better than the 2^32 of most 32-bit generators."

But why does it use the magic number 0x5DEECE66D? The analysis says it was chosen simply because researchers determined empirically that it produces a sequence of values satisfying various randomness tests [1, 2, 3]. Also, the same number and algorithm is used in C's nrand48 function.

The rand48() family of functions generates pseudo-random numbers using a linear congruential algorithm working on integers 48 bits in size. The particular formula employed is r(n+1) = (a * r(n) + c) mod m where the default values are for the multiplicand a = 0x5deece66d = 25214903917 and the addend c = 0xb = 11. The modulo is always fixed at m = 2 ** 48. r(n) is called the seed of the random number generator.

Thus, my project could XOR the field value with 0x5deece66d to recover the current seed.

It is easy to get the value of the private variable using reflection. (To be clear, this breaks the entire concept of encapsulation, and I emphatically discourage this kind of fragile reflection in production code. Nevertheless, it worked well enough for a small personal project.)

public long getCurrentSeed(Random random) throws Exception {
    // Access private field to get the seed
    Field seedField = random.getClass().getDeclaredField("seed");
    seedField.setAccessible(true);
    AtomicLong seedFieldValue = (AtomicLong) seedField.get(random);
    // Unperturb the seed from the magic multiplier
    return seedFieldValue.get() ^ 0x5DEECE66DL;	
}

Then, one can use this seed to create a copy of the original Random object.

Random original = ...
Random copy = new Random(getCurrentSeed(original));

Calling the next* methods on either object will produce the same sequence of values. Exactly what my project needed.

Two-factor authentication is a security procedure that verifies a user's identity using two pieces of information: one that a person knows (such as a secret password) and another provided by something he or she has (such as an ID card). Recently, VeriSign released an an iPhone application that provides a one-time password, enabling two-factor authentication on "40 web sites that are part of the VIP Network, including eBay, PayPal and AOL".

Two-factor authentication using a mobile device is an excellent idea. People rarely leave the house without their mobile phone, and as smart phones become more widespread, such an application could remove the need for easily-misplaced security tokens. But why just 40 websites? What the press release does not mention is that since VeriSign is an OpenID identity provider, the iPhone application can provide two-factor authentication for any site that accepts an OpenID login.

Fortunately, there is no reason why this kind of two-factor authentication must be tied to VeriSign. MyOpenID provides a service called CallVerifID that verifies identity with a call to one's mobile phone. The only thing still missing (as far as I am aware) is an open-source implementation independent of any third-party service.

Therefore, I make the following request to the LazyWeb. I use phpMyID on this website, making it my OpenID identity provider. It should be possible to make this simple application accept a second authentication factor provided by a mobile phone application. Any takers?