The Short Circuit

Mike Morgan's technical journal

Bruce Schneier’s Blowfish was mentioned again on 24. This time, a character on 24 claimed that the designer of the algorithm put in a backdoor.

Blowfish is neat little encryption algorithm designed in the mid 1990s by Bruce Schneier. I first came across it in the April 1994 issue of Dr. Dobb's Journal, a magazine for working computer programmers and hobbyists.

The magazine ran an associated contest to crack blowfish, and I naively took the bait. The deadline passed without success.  But soon thereafter, I discovered a problem with the C-source code implementation: a sign extension bug.

Specifically, a key in blowfish was represented as array of char in the early C-source implementations.  A char is a type in the C language.   The C language doesn't specify whether chars are supposed to be treated as  signed or unsigned.  However, many compilers treat chars as signed by default,  unless the programmer explicitly declares or casts the char as unsigned.

Sign extension occured  during key byte concatenation when a char was bitwise ORed with a 32-bit unsigned value.  If the most significant bit of the char was a '1', then the char was automatically converted by the compilier/cpu to have 25 '1's; that is, the sign bit was extended.  For example, the char 0x83 is sign exteded to 0xFFFFFF83 on compilers treating char as signed.

The up shot was that, assuming key bytes were randomly selected values between 0 and 255, the bug had a 50/50 chance of making a 32-bit section of the key effectively 8-bits, a 25% chance of making a 32-bit section effectively 16-bits, and a 12.5% chance of making a 32-bit section effectively 24-bits.

It is important to note that this sign extension issue was not really a back door, and is certainly not an algorithm backdoor.  An algorithm back door is an usually intentional weakness in an encryption algorithm allowing those with knowledge of the weakness to more easily turn ciphertext back into plaintext, when compared to a brute force attack.

The sign extension bug is an implementation issue.  If a compiler treats char as unsigned by default, the bug would not exist even while using the early C source code implementations.

It should also be noted that Bruce Schneier immediately acknowledged the sign extension issue, and let his readers know about it as well.   From my recollection, Schneier did not write the original source code published in Dr. Dobb's--another person did that for him, based on his algorithm description.

Current reference implementations are reported to not have the sign extension bug, and test vectors have been developed and disseminated by Bruce Schneier et. al to verify that key string sign extension is not occurring in a given implementation.

It turns out that Blowfish was mentioned on 24 at least one other time.

Twofish is another algorithm that Schneier now recommends over Blowfish.

I wrote Blowfish as such an alternative, but I didn't even know if it would survive a year of cryptanalysis. Writing encryption algorithms is hard, and it's always amazing if one you write actually turns out to be secure. At this point, though, I'm amazed it's still being used. If people ask, I recommend Twofish instead.--Bruce Schneier

9 Comments »

  1. Indeed, I just watched this episode and just had to find out more (whilst the episode was still running, might I add ;P). Your blog entry was a good read and informative, thank you.

  2. Intersting backround, thanks for the read.

  3. Yes, very informative. Thanks.

  4. Is there a backdoor though? How can you be sure. Better use a one-time pad.

  5. There is no back door.

  6. Which is the best source code?

  7. 24 is so addicting. But sometimes their technical details need work. Bruce S. should consult with them.

  8. What are the best test vectors?

  9. Here are Eric Young's test vectors

RSS feed for comments on this post.

Leave a comment



© 2017 The Short Circuit | Entries (RSS) and Comments (RSS) |