Wednesday, April 07, 2010

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 we need super computer time

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.


Matt Weir said...

There are a lot of things about this whole incident that made me go "huh". For example, how were they able to get the encrypted file, but not the password? If the file was the result of a whistle-blower you would expect that the whistle-blower would give out the password as well. Another other option is that this file was a result of a lost laptop/usbdrive or a hacked computer. That starts getting really interesting...

Also why was Wiki-Leaks so interested in that particular encrypted file? I doubt they put the effort forward to decrypt every encrypted document they stumble across, (if so, that opens up some DoS possibilities). Could it be the results of a bad filename for the encrypted document? For example Collateral_Damage_Investigation.enc Another option I heard is that the file was referenced to in a Word document that was released with the encrypted file, but I haven't been able to come up with any collaborating evidence for that theory beyond some guy on the internet said it...

This site claims to have the original encrypted file, which might be encrypted using Open SSL AES

The potential for BS/hoax is high though, as it wouldn't be too hard to re-encrypt the file, (or another file for that matter), and promote it to bring in additional site traffic.

The head of WikiLeaks said here that it took them several million guesses to crack the password:

Unfortunately I don't have much confidence that what he said was accurate about the number of guesses since most people throw the word million around to mean "a lot". I won't comment on the rest of the video beyond ... painful to watch. People are treating this whole incident like a rorschach test and seeing what they want to see.

I hate to say it but I don't think we'll get beyond the "speculating on the internet" phase of answering these questions, since I doubt anybody who has firsthand knowledge of this incident, either the DoD who I would assume have knowledge about how the file was encrypted, or the WikiLeaks staff, will answer questions about it.

Robert Graham said...

The DoD has given us every reason to believe that the video is authentic.

However, the details about the decryption do seem odd. Possible explanations are that their spokesmen just understand the details. Another possible explanation is that they are distorting the details to protect the source.

Or maybe they are hyping this to encourage donations.

It's impossible to tell which.

Matt Weir said...

I agree. I'm not questioning the authenticity of the posted video, just the "encrypted video", that the site proposes to have, since either A)Wikileaks gave them the encrypted documented, B)The original source leaked it to multiple sites, or C) They took the publicly available video, encrypted it, and are lying their butts off. My hunch is C, though once again, I have nothing to back that up.

What I'm waiting for is the next round of people pretending to have helped decrypt the video to start speaking up. Trying to figure out what happened is like reading Henry James's "Turn of the Screw". As you pointed out in your original post, there's no neutral/objective source in this case.

Sergey Zak said...

Master-spies might use multilayered (3D, cubed) chips, like the one developed in 1999 (Aspex Linedancer).
And then you're SOL. And then - who knows why they let the cat out (128b SSL export restrictions removed)...
A classic example of moving back into physical security - those who "have something", may "know something".
I am only speculating, of course :)