How did Wikileaks decrypt the video?

Now that I'm reading mainstream press on the incident, I notice some people asking what Wikileaks means by its claims that it somehow broke the encryption.

The answer is "nothing much". There are two types of encryption: serious, and casual. If the file were seriously encrypted, then Wikileaks would not be able to break it, no matter how much computing power they had. On the other hand, if the file were casually encrypted, then it could be broken by a desktop computer in an hour.

A typical example of casual encryption is WinZip. One of the options is to encrypt your file using a password. I use this sort of encryption all the time. If I want to send sample computer viruses to other security researchers, I’ll zip them up with the password "infected" so that the e-mail virus scanners won’t block them (and to inform the recipient to take care).

It’s easy to crack this encryption. There are lots of zip-cracking packages out there that will attempt to decrypt the file by trying all the words in a dictionary. E-mail gateways don’t do this because they can afford to spend an hour trying to crack a single file, nor do they want to delay e-mail that long. But this doesn’t mean the file is seriously "secure".

I could instead choose to be serious about encrypting the zip file. I could choose a longer password like "7dh73hdHkLe)dn@hn!xoq3%axhgGK:V3tgh(kjg%3fjkfQl[" and AES encryption, and feel confident that even the master spies in the government would not be able to decrypt the file, not even with their billions of dollars of computing power. The only way to break this sort of password is if somebody leaks it -- in which case it's even easier to decrypt than using a dictionary of common passwords.

The important thing about cracking such encryption is that the problem is exponential. A 12-character password is not twice as hard to decrypt as a 6-character password -- it is instead a trillion times harder. If a single computer can decrypt a 6-character password in an hour, then it would take that same computer 100-million years to crack a 12-character password. An 18-character password would be a trillion time more difficult than even that. If you pick a long password, with random characters, and correctly encrypt something, then no amount of compute power will be able to crack it.

Wikieleaks says:

Have encrypted videos of US bomb strikes on civilians http://bit.ly/wlafghan2 we need super computer time http://ljsf.org/

I can’t imagine what this means. Either they have the power to decrypt now, or no amount of donations will buy enough compute power. The boundary between these two extremes is vanishingly thin.

To the right is a picture of the exponential growth of passwords containing 100 possible characters. As you can see, the graph appears to go straight up. Short passwords can easily be cracked by a desktop computer, but after the graph shoots up, all the super computers combined won't be able to crack them. There is only tiny bit in between where a super computer can crack the password, but a desktop cannot.

If they wanted to decrypt the video, they could simply post the file as-is. White-hats like me might find a way to bypass the encryption (e.g. if they used the insecure CRC32 encryption in older zip files rather than the new AES). Or, black-hat hackers with million-node botnets can run a distributed cracking program that would provide more super computer power than donations to Wikileaks could ever buy. Even if they didn’t want to post the entire file, the first few kilobytes would likely be enough.

UPDATE: But aren't there a lot of research papers that use need super computers, such as the cracking of MD5 certificates last year? Yes, but that's a different problem. Research is by definition on the bleeding edge. Whatever they do is impractical a few years ago, and doable on a desktop a few years hence.

UPDATE: Wired confirms the guess that the file was in an encrypted ZIP file.