Juncture, United States — April 16, 2012 11:09 pm

The End of Cryptanalysis?

By

Juncture is a joint project between the HPR and the Harvard College Tech Review dedicated to the highest quality writing at the intersection of government and technology.

——————————————————————————

Cryptography once helped the United States win World War II and the Cold War, but today it could be preventing us from accessing important troves of data like Osama bin Laden’s hard drives.

In 1940, William Friedman and his team cracked Japan’s PURPLE system. During subsequent decades, the secretive National Security Agency, or NSA, led the Soviet Union in making and breaking codes. But after the so-called “crypto wars” of the 1990s, the U.S., under pressure from privacy advocates and others, allowed the use of strong cryptography for commercial purposes, effectively ending the NSA’s monopoly.

Last year, American special forces found bin Laden’s hard drives in his compound. It has not been publicly disclosed whether they were encrypted, or, if so, how. But if, as some have speculated, they were encrypted with the algorithm Advanced Encryption Standard-256, they may be useless to our nation’s intelligence agencies. “We don’t know whether bin Laden or other al-Qaeda members used AES-256, but it’s certainly possible,” reported NewScientist. “Last year the organisation supposedly published a magazine called Inspire that contained an article on using a piece of encryption software known as Asrar al-Mujahideen 2.0, which uses AES-256 along with other encryption methods.” The Register adds: “Given bin Laden’s well-founded paranoia, he probably used encryption to prevent outsiders from reading the contents of his computer….It’s unknown if bin Laden used “Mujahideen Secrets,” as the program is known…Mujahideen Secrets may offer 256-bit AES and 2048-bit asymmetrical encryption.”

AES, published in 1998, was named the U.S. government standard after a contest, and implementations of it are publicly available. It is a block cipher, which means it works by repeatedly applying mathematical transformations to scramble a secret message so thoroughly that it no longer resembles its original form. With a secret key, a sender can use AES to encrypt a message, and a recipient with the same key can use the algorithm to decrypt it. AES is expected by many to be unbreakable for years to come. When and if it is broken, a stronger algorithm will quickly follow in its place.

“If you’re doing encryption on the drive properly, meaning you’ve done your research, looked at the solutions, you follow best practices, have a strong key, and don’t have a weak passphrase, then it will probably never be decrypted. Because drive encryption done properly is extremely difficult, it ends up being a brute-force problem,” HBGary security firm founder Greg Hoglund told Information WeekThe Register reports that instead of Mujahideen Secrets bin Laden may have used the more “reputable” encryption programs PGP or GnuPG, which are publicly available and have stood up to rigorous scrutiny from American security experts.

However, Hoglund suggested that bin Laden’s information may still be vulnerable. Some of bin Laden’s drives may not have been encrypted. Even if all had been, Hoglund said, strong encryption is so difficult to implement that the drives may have not been encoded correctly, leaving opportunities for American analysts. The Register suggests that the programmers behind Mujahideen Secrets may have made errors: “Given the program’s small and insular user base, it wouldn’t be surprising if the software authors made crucial mistakes that even they don’t know about.” In addition, American analysts might make progress by cracking weak passwords or paying attention to the physical traces left on drives. According to Information Week, “Even if a hard drive employs encryption, if the drive is still mounted, then it’s vulnerable. Furthermore, if the team can take physical memory RAM snapshots of a live device, this can help crack any encryption.” The Register adds that flash drives “are dangerously hard to purge of data, making thumb drives a good starting point.”

Though American intelligence agencies can often work around powerful cryptographic algorithms like AES when they are improperly applied, the strong encryption systems publicly available today force the NSA to make greater use of larger quantities of less critical data. For example, the NSA now intercepts huge quantities of international cell phone and Internet communications, hoping to glean clues about terrorist networks. Storing and interpreting this huge mass of data poses a difficult challenge. Unfortunately, the ready availability of cryptographic algorithms forces the U.S. intelligence agencies to cast a wider net and compromise the privacy of Americans.

To better process the huge amounts of data it collects, the NSA is now building a massive complex in Bluffdale, Utah, as veteran NSA historian James Bamford writes in this month’s Wired. Interestingly, Bamford quotes a government official who claims that the NSA made an “enormous breakthrough several years ago” in cryptography. It seems that the NSA will use the storage capacity and supercomputers of the Bluffdale facility to employ its new technique to decrypt large numbers of messages. Bamford writes: “The upshot, according to this official: ‘Everybody’s a target; everybody with communication is a target.’”

Does this mean the NSA has cracked AES? Security expert Bruce Schneier does not believe so:

My guess is that…they don’t have a cryptanalytic attack against the AES algorithm that allows them to recover a key from known or chosen ciphertext with a reasonable time and memory complexity. I believe that what the ‘top official’ was referring to is attacks that focus on the implementation and bypass the encryption algorithm: side-channel attacks, attacks against the key generation systems (either exploiting bad random number generators or sloppy password creation habits), attacks that target the endpoints of the communication system and not the wire, attacks that exploit key leakage, attacks against buggy implementations of the algorithm, and so on. These attacks are likely to be much more effective against computer encryption.

Referring to the RSA public-key cryptosystem widely used for Internet commerce, Schneier adds: “Another option is that the NSA has built dedicated hardware capable of factoring 1024-bit numbers. There’s quite a lot of RSA-1024 out there, so that would be a fruitful project.”

Schneier’s opinion is highly respected, so it seems likely that the NSA has not discovered a new attack on the AES algorithm itself. It is probable that the U.S. government will find it difficult to break such codes for the foreseeable future. The only way it could gain an advantage would be to manage a major breakthrough, and then keep it secret for a substantial amount of time, which itself would be difficult.

Americans, even privacy advocates, should not rejoice because the government cannot access their encrypted information. During the 1990s “crypto wars” after the end of the Cold War, when advanced cryptographic algorithms first spread widely, America faced few threats. Today, the stakes in the fight against terrorism are high enough that any progress by the NSA in cryptanalysis—perhaps allowing it to access bin Laden’s hard drives, if they were encrypted with AES—could do much to prevent future attacks.

custom writing