How to Prevent the Random Number Bug in Debian OpenSSL in Other Implementations

As probably the entire hacker community has heard by now, there was a bug recently discovered in Debian's OpenSSL implementation that crippled the random number generator. For background, see Schneier's Coverage, Slashdot's Coverage, Debian's Announcement, Ubuntu's Announcement, and a Cartoon.

On the surface, this just looks like a stupid mistake by one Debian maintainer. But if you look at the details, it's not that obvious. Here one of the two lines in question, within md_rand.c

MD_Update(&m,buf,j); /* purify complains */

This function seeds the cryptographically secure pseudo-random number generator, which then generates important things like cryptographic keys. The security of a cryptographic key is solely in the difficulty of an attacker to guess the value (like a house key's tumbler positions), and if it is predictable, there is no security. The maintainer removed this line because the Purify and Valgrind tools complained about uninitialized data.

Truthfully, if I were in the same position as a maintainer, there's a good chance I might have commented out these lines too. Code analysis tools are very useful in helping to maintain high code quality, and crippling these tools also has consequences. The right action is not always obvious, and when you go through hundreds of lines of code it's easy to forget the significance of a single line like this.

The fundamental issue with random number generators (RNGs) is that they are infamously difficult to test. A standard software regression test takes a known input to a program and checks for a known output. RNGs aren't like that -- at least when used with good seeds. A good seed never repeats and cannot be tested against known answers. Instead, you have to perform statistical tests on several samples from the seed source (examples: DIEHARD, NIST's RNG suite).

This problem is much more widespread than people think. This is also a very common problem in embedded systems. Many instantiations of SSL don't properly seed their RNG. This won't cause the system to fail, testers won't ever catch it, and customers won't complaint. So from the vendor perspective, there's really no incentive to make it work. Most of the engineers adding OpenSSL don't know much about cryptography, and often won't know to or even bother to hook up a seed. Some systems don't have a good way to generate this seed.

Even NIST' Computer Security Division (the owner of FIPS 140-2, a major cryptographic standard for government agencies) has mostly washed their hands of this problem. FIPS 140-2 used to include statistical tests on the entropy (i.e, 'randomness') source used to create the seed, but now the only requirement is that the vendor justify a certain entropy level.

To solve this problem, I think that OpenSSL (and other SSL implementations) needs to add some kind of sanity check to the seed to make sure this mistake doesn't happen again. Here's a rough outline of this test:

1. During OpenSSL's initialization, immediately collect several samples from the seed source. The number depends on the constraints of the system, but NIST's old FIPS 140-2 statistical test collected 20,000 bytes, which is a reasonable number.
2. Run simple statistical tests on these samples (see FIPS 140-2 for an example) and make sure the entropy source is reasonable.
3. Store the first 100 bytes or so of this sample set in non-volatile memory, (e.g, hard disk, flash), and keep a history of several thousand of these initial samples. Discard the other samples (don't use them as part of the real seed)
4. Run another statistical test on the series of first samples. If there is a correlation between these samples (i.e,. the values tend to be the sample after initialization), then fail with a big obnoxious error that you'd hope no distribution maintainer or embedded software engineer would miss.
   

This test would have caught the bug in questions because the same seed would likely have occurred across power cycles. The default for this seed is the process ID, which by default is at most 32,768. According to the birthday paradox, you will on average see a duplicate random number in the range 1 to N after roughly the square root of N samples. In this case, the square root of 32,768 is 181. Someone would have seen the horrible error message by then.

Caveat: Make sure that the files that store these seeds are properly protect from access and modification. If the entropy source is poor, it's possible to leak information about the rest of the system, or even give hints as to what the subsequent seed will be as used by the real random number generator.

When it comes to security, you really can't rely on people to catch these kinds of mistakes through code reviews. You need to have good tools to automatically catch this. Unfortunately, making the tools is difficult, which is why we still mostly rely on code reviews.

Although code reviews are better than nothing, and in this case, it sounds like even a code review would have helped...

Can Firefox keyconfig fix Home/End buttons in textboxes?

In poking around a little further with the problem of creating custom key mappings in Firefox for Mac, I found the plugin named keyconfig (see forum discussion). The plugin seems reasonable on the surface, but it's not actively supported, and its web presence is poor. The best article I found was here on random($foo). Unfortunately, the shortcuts it includes seem to be just for navigating, and not for text edit boxes. I suspect it's possible to add custom code to make keyconfig do what Starry Hope's Firefox keyfixer does -- remap the home/end keys to go to the beginning/end of the current line -- but I couldn't find out how without a lot of poking around.

Keyfixer is a patch utility that modifies the Firefox configuration file named platformHTMLbindings.xml (kept inside the zip file named /Applications/Firefox.app/Contents/MacOS/chrome/toolkit.jar) with the appropriate key board shortcuts. For example, these are the lines that change Home/End to go to the beginning/end of the current line instead of top/bottom of current edit window.

<!-- Additions to fix home/end -->
<handler event="keypress" keycode="VK_HOME" command="cmd_beginLine"/>
<handler event="keypress" keycode="VK_END" command="cmd_endLine"/>
<handler event="keypress" keycode="VK_HOME" modifiers="shift" command="cmd_selectBeginLine"/>
<handler event="keypress" keycode="VK_END" modifiers="shift" command="cmd_selectEndLine"/>

The question I have is whether similar changes are possible within the keyconfig firefox plugin. If this is possible, it would be much easier to maintain because you have to uninstall Firefox keyfixer before upgrading firefox.

I see a lot of potential in keyconfig because it's a firefox plugin, and is something that should be in Firefox anyways, but right now I can't make it work better than the keyfixer patch.

Ada beats Colossus in Cipher Challenge

I caught this article on Slashdot about an Ada program beating Colossus in a challenge to quickly decrypt messages from the Lorenz SZ42 cipher. The Ada program took 46 seconds versus what Colossus (the World War II machine in Bletchley Park that cracked German messages) solved in about three and a half hours.

Ada has me very fascinated because I'm interested in programming languages that lend themselves to computational correctness and high execution speed. I haven't used Ada, but I tend to hear good things about it, and would like to try using it next time I start a project. I'm particularly interested in how it would help programs that use cryptography and that are going through a Common Criteria evaluation.

According to the TIOBE Index, as of May 2008, Ada is sitting at #17 with 0.431% popularity and a rating of 'B'. From that point of view it doesn't look like the hottest thing out there, but it has Objective-C (Mac's darling) way out-ranked. Objective-C is #47 with 0.083% popularity, which makes me wonder if it's worth learning for writing Mac OS X Widgets. Fortunately, Mac's Xcode provides some good hooks for Python (#7, 4.6% popularity) and Ruby (#10, 2.85%)...

Fixing Home and End Keys on Firefox 3 for Mac OS X

[Update: Keyfixer 0.4 is now available; see new blog post]

Since I'm a heavy gmail user, I make significant use of the editor window in my web browser. Ever since moving to a Macbook as my primary computer, I've been struggling with re-learning the Mac navigation key shortcuts. Since I still use Windows a lot, I decided to instead reconfigure the Mac shortcuts to emulate Windows shortcuts.

This strategy worked well, except for in Firefox, which doesn't respect the Mac DefaultKeyBinding.dict file. For Firefox 2, I solved this problem by running Keyfixer as published by Starry Hope. Unfortunately, this stopped working for me when I updated to Firefox 2.0.0.14. I switched to Safari for a while, but Safari's other bugs and "features" started to annoy me. I wanted my Firefox back.

After digging into what Keyfixer does, I've put together an updated version 0.3 that should work for Firefox 2.0.0.14 and Firefox 3.0 beta 5 (tested on Mac OS X 10.5.2). The new solution performs patches instead of straight copies of the keymapping xml file, so I'm hoping it is more robust against future changes in Firefox.

Click here to get Firefox Keyfixer 0.3.

Compared to version 0.2, this new version has the following updates:

• Support for both Firefox 2 and 3 (versions on or after May 2008)
• Running the program twice will uninstall the patch. This is useful when performing upgrades (Firefox won't upgrade if Keyfixer has been applied -- you have to remove it first)
• PageUp and PageDown now moves the cursor instead of just moving the screen. This is more consistent with Firefox on Windows.

As a side note, it looks like there was an intention in Firefox to follow standard Mac behavior by mapping Command-Left Arrow and Command-Right Arrow to move the cursor to the beginning and end of line, respectively. However, this doesn't seem to work (at least when using gmail). I'm interested to know if anyone else has seen this issue, because it's a bug.

If you have any problems or questions with this version, please drop a comment and I'll see what I can do to help!