Older blog entries for randombit (starting at number 14)

Inverting Mersenne Twister's final transform

The Mersenne twister RNG 'tempers' its output using an invertible transformation:

unsigned int temper(unsigned int x)
   x ^= (x >> 11);
   x ^= (x << 7) & 0x9D2C5680;
   x ^= (x << 15) & 0xEFC60000;
   x ^= (x >> 18);
   return x;

The inversion function is:

unsigned int detemper(unsigned int x)
   x ^= (x >> 18);
   x ^= (x << 15) & 0xEFC60000;
   x ^= (x << 7) & 0x1680;
   x ^= (x << 7) & 0xC4000;
   x ^= (x << 7) & 0xD200000;
   x ^= (x << 7) & 0x90000000;
   x ^= (x >> 11) & 0xFFC00000;
   x ^= (x >> 11) & 0x3FF800;
   x ^= (x >> 11) & 0x7FF;

   return x;

This inversion has been confirmed correct with exhaustive search.

This is more a note to my future self than anything else; I'm cleaning out my ~/projects directory, and I can either publish this somewhere or check it into revision control (well, actually the contents of this blog are also in revision control, but no matter).

Syndicated 2009-07-21 20:40:01 from Jack Lloyd

Isn't Autoconf Supposed To Be, Well, Automatic?

Wherein I complain about things that annoy me.

While attempting to build Carrier:

$ ./configure
[many tests run, taking several minutes]
GtkSpell development headers not found.
Use --disable-gtkspell if you do not need it.
$ ./configure --disable-gtkspell
[many tests run, taking several minutes]
GStreamer development headers not found.
Use --disable-gstreamer if you do not need GStreamer (sound) support.

And iterate that six times. Would it be so hard to just carry on and inform the user that some things won't be built because the headers were not found? Without an explicit --enable-blah request, these should not be hard errors (well, IMO).

Syndicated 2009-06-22 19:04:00 from Jack Lloyd

CVE Id Assigned for GNU Classpath Vulnerability

The error in the GNU Classpath PRNG that I described last month has been assigned an identifier in the Common Vulnerabilities and Exposures list: CVE-2008-5659.

Unfortunately a new version of Classpath with a fixed PRNG still remains to be released, so it seems I'm going to have to sit on the demonstration code showing how to derive DSA private keys for a while longer. At some point it would be nice to also verify that RSA and DH keys can also be compromised, perhaps with a sexy little app that compromises SSL/TLS sessions or something along those lines, but I am currently suffering a shortage of round tuits.

Syndicated 2009-01-21 17:18:55 from Jack Lloyd

Optimizing Forward Error Correction Coding Using SIMD Instructions

Forward error correction (FEC) is a technique for handling lossy storage devices or transmission channels. A FEC code takes k blocks of data and produces and additional m blocks of encoding information, such that any set of k of the blocks is sufficient to recover the original data. One can think of RAID5 as a FEC with arbitrary k and m fixed at 1; most FEC algorithms allow wide latitude for the values that can be sent, allowing the code to be adjusted for the reliability expectations and needs of the particular channel and application. For instance, the Tahoe distributed filesystem splits stored files using k of 3 and m of 7, so as long as at least 30% of the devices storing the file survive, the original file can be recoved.

continued »

Syndicated 2009-01-19 22:35:51 from Jack Lloyd

On Syllable's /dev/random

Inspired by the recent FreeBSD arc4random vulnerability, I've been taking a look at the random number generators used by various libraries and operating systems. So far, problems in the JUCE C++ library and in the GNU Classpath PRNG have been identified. (I also checked out Mozilla's NSS, but did not spot any major flaws in that implementation.)

Syllable is a desktop OS based on AtheOS that provides what seems like a pretty decent desktop experience along with POSIX APIs and the GNU toolchain. My initial interest in the project was to get it installed under KVM and port my project botan to it.

read more »

Syndicated 2008-12-09 18:20:36 from Jack Lloyd

Serious Weakness in GNU Classpath/gcj PRNG; DSA keys are compromised

XKCD #221

GNU Classpath is an open source implementation of the Java class libraries used by gcj, the GNU Compiler for Java. One component of the Java library is JCE, the Java Cryptography Extensions (so called because originally it was not bundled with the JVM due to United States export restrictions), which provides the basic crypto features one would expect (ciphers, hashing, signatures) for Java applications.

For many RNG purposes, including creating private keys, DSA k values, and SRP session ids, GNU Classpath uses gnu.crypto.security.util.PRNG.

This PRNG uses a hash function, which by default is SHA-1 though others can be used instead. It is initialized with a random seed, and then values are generated by the recurrence

V(0) = H(seed)
V(i) = H(seed || V(i-1))

The PRNG has an interface allowing the addition of new seed material at a later time, for instance a GUI application might seed it with mouse click event information.

Unfortunately there are two problems with how this PRNG is used in Classpath that in combination cause serious problems. One is a convention where each object, most of the time, gets its own PRNG. It seems that it is possible in some but not all cases to override the PRNG to be used, and there seem to be at least three different conventions for how to do it in Classpath. A representative example, from the RSA key pair generator code:

  /** The optional {@link SecureRandom} instance to use. */
  private SecureRandom rnd = null;

  /** Our default source of randomness. */
  private PRNG prng = null;


  private void nextRandomBytes(byte[] buffer)
    if (rnd != null)

  private PRNG getDefaultPRNG()
    if (prng == null)
      prng = PRNG.getInstance();

    return prng;

This class will use nextRandomBytes to choose starting points for the RSA p and q values. Note that all access to the prng itself is private, so an application developer cannot, for instance, add new seed data to the PRNG.

The other problem is that by default the only seed used in gnu.crypto.security.util.PRNG is the current timestamp in milliseconds. This can be extended by setting a property named "gnu.crypto.prng.md.seed", but I could not find out much more about this because it does not seem to be used by any code at all within Classpath.

Many cryptographic algorithms require a source of cryptographically secure random numbers. For instance, DSA requires choosing a new random 160-bit integer k for each signature that is generated. If this k value is ever revealed, the private key is immediately compromised, since it is equal to (((s*k) - H(m)) * r-1) mod q (using the notation from FIPS 186). Since GNU Classpath (in effect) chooses k values by simply hashing the current timestamp in milliseconds with SHA-1, it is quite simple to search for and find k.

Experiments confirmed that the output of gnu.crypto.security.util.PRNG, as it is returned by PRNG.getInstance(), is easily guessable using only the local clock as the starting point for the search. This usage matches exactly how this class is used throughout the GNU Classpath source.

There are less than 235 millisecond values in a year, which puts an upper bound on the security of any keys generated by this RNG, assuming an attacker can guess the year, which seems a reasonably safe bet. Even a decade contains barely 238 milliseconds. These values are far less than even the toughest export restrictions the United States ever imposed, which were typically 40 to 56 bits of security.

Classpath contains a number of other RNGs including gnu.crypto.security.util.CSPRNG, which seems (at least at first glance) to be somewhat safer. I would recommend adding additional seed material, which would probably be sufficient, except it seems in many cases that is not even possible. Unfortunately since g.c.s.u.PRNG's use is hardcoded in nearly everywhere, it may be difficult for applications to switch.

Update 2008-12-08: I've confirmed that the private half of a DSA keypair can be derived from the public key and a single signature/message pair, simply starting with a guess of the time the signature was generated. This basically means that every DSA key which has been used in an application compiled with gcj or using GNU Classpath/GNU crypto is (or at least can easily be, at any time) compromised. Based on the CVS history, it appears this flaw was originally introduced in GNU Crypto about 6 years ago, and was then imported into Classpath without alteration.

I've entered a bug report for Classpath describing the problem, but no response yet. After this is resolved (hopefully soon), I'll post the private key derivation code for examination.

An example vulnerable application is DSASigGen.java, which uses only the normal stock Java/JCE API calls to generate a random DSA key, sign an empty string (the exact value doesn't matter, as long as the message is known), and prints the public key and signature (the private key is printed to stderr by the Java code, just so I could confirm that the search code was in fact finding the correct key).

(motoko)$ gcj --version
gcj (Gentoo 4.3.2 p1.2) 4.3.2
Copyright (C) 2008 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO

(motoko)$ gcj --main=DSASigGen DSASigGen.java
(motoko)$ ./a.out > pubkey_and_sig
Private key is 286340495355822070335047169143648712734886086939
(motoko)$ cat pubkey_and_sig
308201b83082012c ... [(DSA public key truncated for readability / not screwing up formatting)]
(motoko)$ g++ -O2 find_dsa_key.cpp -lbotan -o find_dsa_key
(motoko)$ time ./find_dsa_key < pubkey_and_sig
Found private key 286340495355822070335047169143648712734886086939

real    0m0.716s
user    0m0.634s
sys     0m0.054s

Update #2: According to the Wikipedia entry, other JVMs including Kaffe and JikesRVM use GNU Classpath. I have not checked if they are vulnerable (Kaffe is not building on my machine), but the odds are good. This may be a bigger issue than I first thought.

Update #3: I should emphasize that while DSA keys are the easiest target of this flaw, it is quite likely that all private keys (RSA, DSA, Diffie-Hellman, etc) generated by Classpath can be easily found, simply by guessing PRNG seeds and running through the key generation procedure until a private key corresponding to the known public key is produced.

Syndicated 2008-12-06 16:11:56 from Jack Lloyd

The More Things Change...

"Anyone who considers arithmetic methods of producing random digits is, of course, in a state of sin." - John von Neumann, 1951

On an Ubuntu forum I caught a reference to a C++ library called JUCE, which is one of those all-inclusive C++ libraries along the lines of POCO or GNU Common C++. One thing I noticed was that it includes a few cryptographic operations, including RSA key generation, so I decided to take a peek at the latest release as of this writing, 1.46.

Tracing through the code, we find the primes for the RSA keys are created by calling Primes::createProbablePrime, which generates a random starting point and then uses a sieve to find the nearest prime number. The random starting point is chosen on line 131 of juce_Primes.cpp, using BitArray::fillBitsRandomly. This function in turn calls Random::getSystemRandom() to actually get random data. So far so good.

From the name "getSystemRandom", I assumed this would in turn use an OS specific RNG like /dev/random on Linux/OS X or CryptGenRandom on Windows. So you can imagine my horror to find that JUCE's 'system RNG' is a linear congruential generator, seeded with the constant value 1:

static Random sysRand (1);

Random& Random::getSystemRandom() throw()
    return sysRand;

There are flaws at multiple levels here.

read more »

Syndicated 2008-12-05 16:54:47 from Jack Lloyd

Thanksgiving 2008 Recipe Wrapup

Amanda and I made Thanksgiving dinner pretty much from scratch this year, and happily everything turned out very well!

Honey Brined Turkey

I picked up a 10 lb turkey from Dipaolo turkey farm. Initially we had planned on brining the whole bird, using a recipe from epicurious, but we did not have a pan large enough to submerge the carcass. So the day before Thanksgiving I found myself dismembering a raw turkey, which is quite a bit more exhausting than carving it after cooking! Then again, how often do you have the chance to snap a turkey's spinal column with your bare hands? Opportunity of a lifetime, I'm telling ya.

We decided to brine the dark meat in the legs and wings, and bake the breast meat separately in citrus and rosemary. The brinng worked spectacularly well, easily the most tender flavorful turkey I have ever had, but sadly the breasts came out dry. At one point we had discussed wrapping them in prosciutto prior to baking to help keep them moist, but in the rush it was forgotten.

Bacon Apple Stuffing

A stuffing recipe with bacon and apples? OK! I went heavy on the thyme (from the windowbox plant) and sage. The bread (along with the beans and whatever else we did not get from Greenmarket) was from Fairway, the best-est grocery story in NYC). The only complaint I had with the stuffing was that the apple flavors were mostly lost. If I try this recipe again, I'll probably double the amount of apple and cut it into larger pieces, to help it survive the long bake time.

Sweet Potato Stuffed with Blue Cheese wrapped in HAM

While I was tending to the gravy, Amanda made stuffed sweet potatoes wrapped in prosciutto, based on a recipe from what we're eating. One factor we did not anticipate was that the potatoes did not really soften up much during their time in the oven, despite the claims of the recipe. We had pulled them out of the boiling water a bit ahead of them being completely finished, thinking they would soften further in the oven, but the potatoes that were not soft all the way through after boiling remained a bit tough post-bake.

String Beans and Bacon

Serious Eats had a recipe for string beans with bacon and chestnuts had sounded great, until we realized exactly how much work preparing chestnuts is. The recipe has using "bottled peeled roasted whole chestnuts", but being the DIY types we picked up whole fresh chestnuts from Greenmarket and set to work. How hard could it be? To prepare chestnuts, Joy of Cooking recommended cutting an X in the side of each nut and boiling them for 5 minutes. Then peel off the shells - which we found an incredibly time consuming task, and exhausting for the fingers! Now that the chestnuts are peeled, they can be cooked, which is done by boiling them (again) for 30-40 minutes, then baking them for an hour. We got about halfway through the shelling process and realized there was just no way we had the time to devote to doing this with so many other dishes still up in the air. So we aborted on the chestnuts, but the string beans were fresh and the bacon was good quality, so I think everyone was still happy with the results.

Sweet Potato Rolls

The rolls were made with mashed sweet potatoes, using a recipe from pinch my salt. These were a huge hit. I had been worried the sweet potato would dominate but instead it just gives a slight flavoring to the yeast rolls. The ones that were left unfrozen (but bagged) unfortunately turned moldy after only a few days, probably due to the egg and sugar. Fortunately I have at least half a dozen still in the freezer...

Sweet potato, pecan/date, and icebox pies

For desert we made sweet potato, pecan and date, and icebox pies. I was a bit dubious of the pie crust recipe thekitchn had, but for heavy pie fillings like these the extra density of the crust worked. (The Oreo crust of the icebox pie was pretty tasty too)

The cranberry sauce, gravy, and mashed potatoes were consumed without ever being photographed. Very sad.

So, was the meal worth 12+ hours of cooking over two days? Ummm... YES! But once a year seems about right to me.

Syndicated 2008-12-03 22:16:00 from Jack Lloyd

Switching to Pyblosxom, and a colophon

Until recently I had been using on bitbashing blosxom, a minimalist blog system which stores each entry as a flat file on disk. My existing workflow relies heavily on tools like emacs for editing and merging and monotone for revision control, and it is nice to have a blog system that plays well with these other tools, rather than using, say, a MySQL database as the storage layer and an AJAX widget as editor. However over time blosxom has seemed less and less maintained, and I started looking for alternatives.

Today I switched to pyblosxom, which started as a clone of blosxom, and still has much the same philosophy, but seems to have many advantages and useful features as compared to blosxom. A description of the upgrade process along with a site colophon are after the jump.

read more »

Syndicated 2008-11-21 00:53:31 from Jack Lloyd

Robot packs will hunt 'non-cooperative' humans

A new Pentagon project proposal for a "Multi-Robot Pursuit System" will allow soldiers and police to "search for and detect a non-cooperative human".

Syndicated 2008-10-25 19:46:21 from Jack Lloyd

5 older entries...

New Advogato Features

New HTML Parser: The long-awaited libxml2 based HTML parser code is live. It needs further work but already handles most markup better than the original parser.

Keep up with the latest Advogato features by reading the Advogato status blog.

If you're a C programmer with some spare time, take a look at the mod_virgule project page and help us with one of the tasks on the ToDo list!