Older blog entries for randombit (starting at number 17)

Programming trivia: 4x4 integer matrix transpose in SSE2

The Intel SSE2 intrinsics has a macro _MM_TRANSPOSE4_PS which performs a matrix transposition on a 4x4 array represented by elements in 4 SSE registers. However, it doesn't work with integer registers because Intel intrinsics make a distinction between integer and floating point SSE registers. Theoretically one could cast and use the floating point operations, but it seems quite plausible that this will not round trip properly; for instance if one of your integer values happens to have the same value as a 32-bit IEEE denormal.

However it is easy to do with the punpckldq, punpckhdq, punpcklqdq, and punpckhqdq instructions; code and diagrams ahoy.

continued »

Syndicated 2009-10-08 21:53:12 from Jack Lloyd

The Case For Skein

After the initial set of attacks on MD5 and SHA-1, NIST organized a series of conferences on hash function design. I was lucky enough to be able to attend the first one, and had a great time. This was the place where the suggestion of a competition in the style of the AES process to replace SHA-1 and SHA-2 was first proposed (to wide approval). This has resulted in over 60 submissions to the SHA-3 contest, of which 14 have been brought into the second round.

Of the second round contenders, I think Skein is the best choice for becoming SHA-3, and want to explain why I think so.

continued »

Syndicated 2009-10-08 19:22:12 from Jack Lloyd

Speeding up Serpent: SIMD Edition

The Serpent block cipher was one of the 5 finalists in the AES competition, and is widely thought to be the most secure of them due to its conservative design. It was also considered the slowest candidate, which is one major reason it did not win the AES contest. However, it turns out that on modern machines one can use SIMD operations to implement Serpent at speeds quite close to AES.

continued »

Syndicated 2009-09-09 19:02:08 from Jack Lloyd

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

8 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!