Educated Guesswork

« Skiing Royal Gorge | Main | Protecting against dictionary attacks »

March 28, 2005

The Secret Service's key cracking operation

WaPo has an interesting article about the distributed computation network (called Distributed Networking Attack (DNA)) the Secret Service uses to break encryption. There are two interesting pieces of information in this article:

First, even with a big network of computers, brute-forcing a reasonable-sized cryptographic key is totally out of reach. The Secret Service uses quite a clever dictionary attack strategy to speed things up:

In each case in which DNA is used, the Secret Service has plenty of "plaintext" or unencrypted data resident on the suspect's computer hard drive that can provide important clues to that person's password. When that data is fed into DNA, the system can create lists of words and phrases specific to the individual who owned the computer, lists that are used to try to crack the suspect's password. DNA can glean word lists from documents and e-mails on the suspect's PC, and can scour the suspect's Web browser cache and extract words from Web sites that the individual may have frequented.

"If we've got a suspect and we know from looking at his computer that he likes motorcycle Web sites, for example, we can pull words down off of those sites and create a unique dictionary of passwords of motorcycle terms," the Secret Service's Lewis said.

The second interesting thing is that the FBI isn't using a dedicated computing infrastructure; DNA runs on ordinary employee's workstations when they're idle. Obviously, that saves money, but it has interesting privacy implications. The way you run an attack like this is by doing what's called trial decryption. Each computer in the network has the ciphertext and to test a candidate key, you decrypt the ciphertext and look to see if the plaintext is plausible (e.g., it looks like it's ASCII text rather than random garbage.) But here's the thing: the workstation which actually correctly guesses the key now has the plaintext as well.¹ The way you deal with this is by giving the worker machines a very small fragment of the file, say less than 100 bytes. Then, when the worker machine decrypts the chunk, they don't get the entire file. There's some indication that they do that now, but it's not entirely clear:

In the meantime, the agency is looking to partner with companies in the private sector that may have computer-processing power to spare, though Lewis declined to say which companies the Secret Service was approaching. Such a partnership would not endanger the secrecy of their operations, Lewis said, because any one partner would be given only tiny snippets of an entire encrypted message or file

This is an important consideration even if the only computers are operated by FBI employees. The "fragment" fix works fine if you have big files which you can independently decrypt and verify parts of. This is pretty much true for most modern encryption systems, but some of the techniques that crypto engineers talk about to resist brute force (e.g., compression ²) could force you to decrypt the entire file, making this a serious privacy issue. And of course these are some of the techniques you might want to use to counter this kind of search network.

^1. Note that there is at least one special case. If you're encrypting something like an RSA private key, that has internal structure and you can test whether you have the correct key without ever seeing the actual plaintext.
^2. Note that standard compression algorithms have a fixed header which makes detecting successful decryption easy, but you can design compression systems which don't have this property.

UPDATE: Florian Weimer points out that it's the Secret Service, not the FBI as I originally wrote. Fixed... I think...

Posted by ekr at March 28, 2005 9:33 PM | Filed under:

Comments

Posted by: Florian Weimer at March 29, 2005 9:14 AM

Posted by: Nathan Zook at March 29, 2005 2:08 PM

Posted by: Wim L at April 1, 2005 1:45 PM