Randomness in cryptography – the devil’s in the details

Kiwicon opened with a software engineering talk which was intensely focused – a case study of a single-line bug in a single source file in a single module in a 70MBbyte programming language distro.

The talk, by Kiwi-turned-Northern-Californian coder Geoff Cant, was entitled The Erlang SSH story: from bug to key recovery. Geoff works for ngmoko:), a platform for building social networking interactions into your online games. (The smiley is part of the company name.)

Erlang – short for Ericsson Language, or in remembrance of Danish mathematician Agner Krarup Erlang, depending on whom you ask – is an open-source programming language developed by Ericsson in Sweden.

Erlang isn’t widely known – unlike, say, Java, C, Perl and Python – but it has been enthusiastically embraced by many companies which run server farms handling huge numbers of users at the same time: Facebook, for example, and Geoff’s own employer, ngmoko:).

Forking or threading webservers like Apache and IIS aren’t the way to roll your own 100,000-users-at-the-same-time web platform. Erlang is. That’s because it was created specifically to help you build massively concurrent systems distributed over many servers.

But I digress, albeit only mildly.

The bug Geoff zoomed in on was this:

It may not look like much, but the problem exists in line 467. This is the core of the random number generator for Erlang’s SSH server. Generally speaking, cryptographic routines need high-quality random numbers – bunches of bytes, e.g. for one-time session keys, which simply cannot be guessed in advance, or reconstructed later.

High-quality random numbers are hard for computers to generate. After all, computers are supposed to be algorithmic and determininstic devices. They aren’t supposed to be capable of whimsy or inconsistency.

And the Erlang library function random:uniform/1 is entirely devoid of whimsy. It’s a simple pseudo-random number generator that is predictable and repeatable by design. As the manual itself points out, “this random number generator is not cryptographically strong. If a strong cryptographic random number generator is needed for example crypto:rand_bytes/1 could be used instead.”

Using this function in the Erlang SSH server was a tiny bug, easily fixed. But it had potentially massive consequences, as Geoff demonstrated in his talk.

From an SSH client – remotely and without authentication – he was able to predict the supposedly-secret pseudo-random sequence used by the server. As a result, he could extract enough key material to decode not just the current session, but also any past and future sessions with the same server. In short, the lack of randomness leaked the keys to the castle.

The bug is now fixed, as shown in the code diff below. Just remember: if you’re writing cryptographic code, you must use the right tools for the job. The devil really is in the details.