MD5 collision visualised

On this webpage, there's an illustration showing of the evolution of the internal state in an MD5 hash collision. I really need to sit down at some point and make the effort to understand the technical details of the MD5 collision attack. Here's the reference:

• Xiaoyun Wang and Hongbo Yu, How to Break MD5 and Other Hash Functions, EUROCRYPT 2005 [7].
  

Tags: MD5 , Cryptography

Review: Digital Fortress

Dan Brown is famous as the author of The Da Vinci Code. One of his earlier efforts was Digital Fortress (available online here) a book about the NSA and codebreaking. Now, I don't mind it when writers who, when dealing with complex real-life topics, sometimes play a little fast-and-loose with the nitty-gritty details. After all, this is fiction, right? Sometimes changing details serves to improve the story. Sometimes it only matters that the author gets the broad picture across, because only geeks care about the minutiae. Well, in this novel Brown fails to get anything right; the plot is weak and contrived, the characters are ludicrous, the broad picture is incomprehensible and, yes, he gets the crypto details completely wrong.

Fortunately for me, I have a twisted sense of humour. I enjoyed reading this, solely because of the old "it's so bad it's good" thing.

So. This is a lazy review. Summary: the novel is bad, and very bad if you're crypto-savvy. Here are some choice quotes as evidence:

• If Susan’s body had been lanky and awkward as a teenager, it sure wasn’t now. Somewhere along the way, she had developed a willowy grace—slender and tall with full, firm breasts and a perfectly flat abdomen. David often joked that she was the first swimsuit model he’d ever met with a doctorate in applied mathematics and number theory.
  
• “Exactly. An algorithm that resists brute force will never become obsolete, no matter how powerful code-breaking computers get. It could become a world standard overnight.”
  Susan pulled in a long breath. “God help us,” she whispered.
  
• Enigma was history’s most famous code-writing machine—the Nazis’ twelve-ton encryption beast. It had encrypted in blocks of four. (The real Enigma weighed 12 kg - ed.)
  
• Encryption algorithms were just mathematical formulas, recipes for scrambling text into code. Mathematicians and programmers created new algorithms every day. There were hundreds of them on the market—PGP, Diffie-Hellman, ZIP, IDEA, El Gamal. TRANSLTR broke all of their codes every day, no problem. To TRANSLTR all codes looked identical, regardless of which algorithm wrote them. (and to Dan Brown, software, compression methods, key-agreement algorithms, public-key encryption schemes and block ciphers all seem identical - ed.)
  “I don’t understand,” she argued. “We’re not talking about reverse-engineering some complex function, we’re talking brute force. PGP, Lucifer, DSA—it doesn’t matter. The algorithm generates a key it thinks is secure, and TRANSLTR keeps guessing until it finds it.”
• Caesar, she explained, was the first code-writer in history. When his foot-messengers started getting ambushed and his secret communiqués stolen, he devised a rudimentary way to encrypt this directives. He rearranged the text of his messages such that the correspondence looked senseless. Of course, it was not. Each message always had a letter-count that was a perfect square—sixteen, twenty-five, one hundred—depending on how much Caesar needed to say. He secretly informed his officers that when a random message arrived, they should transcribe the text into a square grid. If they did, and read top-to-bottom, a secret message would magically appear. (Brown's just described a columnar transposition cipher. I know it's a subtle point, but Caesar actually invented what's confusingly known as the Caesar cipher, a simple substitution cipher - ed.)
  Over time Caesar’s concept of rearranging text was adopted by others and modified to become more difficult to break. The pinnacle of non computer-based encryption came during World War II. The Nazis built a baffling encryption machine named Enigma. The device resembled an old-fashioned typewriter with brass interlocking rotors that revolved in intricate ways and shuffled cleartext into confounding arrays of seemingly senseless character groupings. (It seems the only type of encryption Brown understands is transposition, but sadly none of the systems he names were transposition schemes. The Enigma didn't "shuffle cleartext", nor did the Caesar cipher. Most importantly, the rotors were made chiefly from rubber or bauxite, not brass. OK, OK, I'm nitpicking now... -ed.)
  

There's more, but I don't want to spoil them for you ;-)

Tags: Cryptography , Encryption , Digital Fortress

Permanent home for Colossus rebuild

It seems that some controversy about the future of the Colossus computer reconstruction at Bletchley Park has been resolved. Some background:

The Colossus computers were computing devices built during World War II to break high-level German teleprinter ciphers at Bletchley Park. They have a claim to being the first digital computers, but they were kept secret until the 1970s.

Tony Sale and his team have invested around 6,000 man-days over the last 10 years painstakingly constructing a functioning replica of a Colossus. The rebuild is sited in H Block at Bletchley Park, where an original Colossus was installed during WWII, and is quite an awe-inspiring bit of kit. For many people, it's the crowning exhibit at Bletchley Park.

Last year, Bletchley Park Trust decided to put H block up for sale. Quite why they did this, I don't know, but possibly to raise cash to keep the museum running. Their decision drew criticism from various quarters. One objection was that H block was of historical importance: the building is the "world's earliest purpose-built building erected specifically for electric computers". Moreover, selling H block would mean that the Colossus rebuild would have to be relocated. Tony Sale argues that moving the Colossus would be "a very complex and difficult operation and it is quite likely that Colossus would never work again." That, of course, would have been a tragedy.

Well, the news is that it seems the Colossus rebuild is now secured. I don't claim to understand the politics involved, but it seems that Bletchley Park Trust have acquired funding which means that H block will be kept, and the Colossus rebuild will be able to remain in its current position. See the press release issued today. On Sale's Codes and Ciphers Heritage Trust there's more information about H block.

Hopefully this means the Colossus rebuild will be available for viewing by the public again soon.

Tags: Cryptography, Bletchley Park, Colossus

Spooks with large hands

A one-time pad (scanned in by Marcus Ranum from a book called KGB/CIA). I want one!

Tags: Cryptography , Encryption

Visas for Chinese crypto researchers

Here's a news article on why a number of Chinese crypto researchers, including two of the discoverers of the collision attacks on SHA-1, Xiaoyun Wang and Hongbo Yu, were unable to get visas to present their work at CRYPTO 2005. Actually, it doesn't really explain why, just that they were unable, despite the intervention of NIST. Seems pretty daft to me.

I enjoyed Adi Shamir's satirical take on this at the CRYPTO rump session, where he suggested that Wang having "attacked US government systems" and having expressed a desire to "create collisions" might have contributed to the visa problems...he even got away with using a September 11 fireball picture to make his point.

Tags: Cryptography , Encryption , SHA-1

SHA-1 attack complexity reduced

At the CRYPTO 2005 Rump Session, Adi Shamir just delivered a new result on behalf of Xiaoyun Wang, Andrew Wao and Frances Wao, on SHA-1. The complexity of the best attack for finding collisions is lowered from 2⁶⁹ to 2⁶³. Shamir speculates that it might now be plausible to search for SHA-1 collisions using a distributed Internet search.

CRYPTO 2005

This year's CRYPTO 2005 starts today (14th) over in Santa Barbara, California, US, and ends on the 18th. Keep an eye out on Michael de Mare's blog (Cipher Boy) as he's threatened to blog a little from the conference.

Update: The CRYPTO rump session will be webcast this year, starting on Tuesday August 16th at 7:00pm Pacific (which I believe is GMT-7 in Daylight Savings Time, so that's 3.00am on the 17th of August British Summer Time).

Update 2: Slight change, apparently. It now starts at 7:30pm Pacific Daylight Time (3.30am BST). It'll be in Apple's Quicktime format, with a 300kb bitrate.

Tags: Cryptography , Encryption

Cryptoogle

Cryptoogle is not the world's first search engine for dead people; it's not even a Google project. Instead, it's a rather fun idea for encryption. The idea is that you encrypt information with a password that's a valid Google search term. A Blowfish key is generated from the search results, and is used to encrypt the plaintext.

So why do this? I'm not sure, really. The author argues that, because Google's search results change, the key will automatically expire at some point in the future. He also claims that this prevents dictionary attacks because an adversary is limited with the number of Google queries which can be made.

Well, there are much better ways of doing this sort of thing, of course, and deriving your secret key from information pulled over the insecure Internet is certainly not a workable strategy, but I thought it was a fun idea anyway.

Tags: Cryptography , Encryption

Court case falls apart because of MD5 insecurities

According to a post on the cryptography mailing list, an Australian court threw out a case against an (allegedly) speeding motorist because the speed camera images were secured using MD5. The defence argued that MD5 was a "discredited piece of technology". Indeed, the MD5 hash function was shown to have a weakness last August when a team of Chinese researchers announced that there was a practical method to generate collisions.

But it's not totally clear what's going on here. One possibility is that the speed cameras digitally sign the evidence, or more specifically, the MD5 hash of the evidence. To tamper with the evidence, you'd need to mount a second preimage attack, but, as far as I'm aware, nobody's come up with a way of doing this.

Another possibility is that the camera simply prepends the evidence with the MD5 hash, which provides no integrity guarantees, but that's got nothing to do with the security of MD5 per se.

Still, there's a great quote from the defence lawyer Denis Mirabilis: "People have shown it [the algorithm] has been hacked and it's open to viruses."

Update: Slashdot have just covered this.

Tags: Cryptography , MD5

US crypto export rules

Apparently, in the US you have to declare a national state of emergency in order to continue on with various export restrictions on cryptography (Bruce Schneier informs us). I don't really care, to be honest. I'm just glad to be living in the great United Kingdom, an enlightened nation where the government doesn't have any draconian cryptography laws.

New chief spook

The NSA have a new director, a Keith B. Alexander. He started work on the 1st of August, and he is the sixteenth director since NSA was created in 1952. The agency rotate the directorship amongst the Army, Navy and Air Force; Alexander is US Army, while his predecessor, Michael Hayden, was from the US Air Force.

One-time pads on paper tape in 2005!

While browsing Dirk Rijmenants blog, I came across a link to Austrian company Mils Electronic. This company sells encryption products that implement one-time pads and proprietary ciphers; ring any warning bells? Well, rather than making any judgments on the company or their products, I thought I'd mention a few facts that distinguish this company from a stereotypical OTP snake-oil vendor.

First, they were founded in 1946, and have been doing one-time pads ever since. Second, they seem to be pitching their products at governments. Third, amongst other things, their random number generator can output to a...wait for it...5-channel paper tape puncher (pictured above left).

5-channel paper tape -- as in, pretty much the same one-time pad implementation Gilbert Vernam patented in 1919. I'm flabbergasted. Who's still using this stuff? I reckon you'd need a little over 4 meters for each kilobyte of information you encrypt.

The BID list

British government crypto devices seem to all be assigned a BID code, one for each type of device. Because I'm a geek, I went and Googled and chucked together a list of BID codes together with any info about these devices I could find, although the details of most of them remain classified. I like the codenames, too -- they sound very mysterious and cloak-and-dagger, names like ALBERCOR, CRUCIBLE, NOREEN and, er, KITCHENMAID. Hmm, maybe not so cool after all ;-)

If anyone has any more info on BID devices, let me know.

All Hackers Need To Know About Elliptic Curve Cryptography

In what's been touted as the "last ever" issue of hacker-zine Phrack, released at the beginning of this month, there's an article overviewing elliptic-curve cryptography together with a sample implementation. Written by the shadowy "f86c9203", it overviews a little bit of basic algebra and outlines a couple of key-agreement protocols. "Rootkits and backdoors seem to be interesting applications", claims the article, although it's not quite clear what great benefit ECC brings to your average black hat over conventional public-key crypto...I guess it just sounds cool, right?

ECRYPT Stream Cipher Project

The ECRYPT Stream Cipher project is a project run by ECRYPT (an EU programme for cryptology and watermarking) to identify "new stream ciphers that might become suitable for widespread adoption". It guess this will be something a little like the Advanced Encryption Standard (AES) competition, but for stream ciphers rather than block ciphers (and they're just evaluating the designs, and not selecting a single standard). The call for primitives was first issued in November 2004, and they received a whopping 34 designs by the deadline last April. Some famous(ish) names have submitted or co-submitted designs, including Joan Daemen (MOSQUITO), Eli Biham (Py), Bruce Schneier (Phelix) and Daniel J. Bernstein (Salsa20).

Eli Biham and Jennifer Seberry note that their submission "Py" is pronounced "Roo, a shorthand for Kangeroo". This is because it's written in the Cyrillic alphabet, apparently. Ah..hah. A worthy attempt to carry on the recent tradition for bizarrly-named and unpronounceable cryptographic primitives, then.

The project has advertised for four "profiles" of stream ciphers that they're looking for, distinguishing between those that perform well on hardware and software, and those that include authentication built-in and those that do not.

It's going to take a while, though. By July 2006, they'll be selecting a subset of the designs as finalists, with the project due to complete in January 2008. Still, it looks like it'll be a lot of fun, with researchers finding flaws with each other's ciphers. There's a discussion forum and a list of papers.

If you're lucky, I might blog a little about each of the designs -- won't that be a treat?

sci.crypt problems

The cryptography newsgroup sci.crypt appears to be having a few problems. In Google Groups, the very useful archive of past messages has vanished, and on my ISP's news server, the group doesn't even appear in the list of groups. According to one post, "sci.crypt is under massive attack, there are lots of forged cancel messages." Sounds unpleasant, although quite how cancel messages work — and how they might be forged — remains a mystery to me!

But even when working normally, sci.crypt is afflicted with a fairly poor signal-to-noise ratio; the good stuff is often buried under the copious output of trolls, cranks and flamewar participants...typical Usenet, really. An alternative that's worth checking out is the cryptography forum on the Security Forums website. One of those PHP-powered bulletin-board things, it seems to have some useful discussions and helpful regulars willing to answer newbie questions (without biting their heads off à la sci.crypt).

Review: M-209 simulator by Dirk Rijmenants

I've finally got round to trying out Dirk Rijmenants' M-209 simulator. The M-209 (right) was a portable cipher machine used by the US in World War II (and afterwards), and was originally designed by Swedish engineer Boris Hagelin (even more info here).

For me, the M-209 (and related Hagelin machines which use the same mechanism) is quite possibly the most fascinating crypto machine ever made. Part of the appeal is that it's completely mechanical (unlike the Enigma machine, which was both mechanical and electrical in operation). From the outside, an M-209 appears to be a rather boring, green, lunchbox-shaped tin, but inside there's a fiendish array of pinwheels, gears, cogs, lugs, bars and other bewildering mechanical components. Maybe I'm just unduly scared by moving parts (I'm a CompSci/Maths person), but these machines certainly look how you'd want your cipher machine to look if you were trying to dissuade the enemy from even starting an attempt to crack your codes.

Appearances can be deceiving, of course, and the truth is that the M-209 was not particularly secure, and certainly less so than Enigma. In WWII, the Germans were reading M-209 traffic, although the machines were used only for low-level tactical communications. The machines were also used by the US in the Korean war, and devices using the same sort of "pin-and-lug" mechanism stayed in use even into the 1970s in various parts of the world.

Anyway, getting back to the simulator: if you want to tinker with this piece of cryptographic history, and if you don't fancy shelling out the USD$1000-4000 for which antique M-209's typically exchange hands on eBay, this excellent freeware software emulation of the machine (left) is the next best thing (for Windows only, sadly). Dirk wasn't content merely to reproduce the cryptographic operation of the device (which is more-or-less a simple stream cipher), but has painstakingly copied the appearance and construction of the M-209, even down to the screws. To operate, you have to turn the various (on-screen) knobs and handles, and the output is printed on (on-screen) tape, just like the real thing. Stuart Savory has tested the machine's output against that of a museum's M-209 and found them to be compatible. Being so faithful to the original has an inevitable downside, however, as the M-209 isn't a particularly intuitive device to operate, and you'd probably need to do some reading first if you're not already familiar with the machine. Besides the help files, another option would be to watch the original US Army M-209 training video.

Dirk has also created an excellent Enigma simulator in the same vein, and I'm looking forward to what he comes up with next!