Entries Tagged "cryptography"

Page 22 of 56

Spritz: A New RC4-Like Stream Cipher

Last week, Ron Rivest gave a talk at MIT about Spritz, a new stream cipher by him and Jacob Schuldt. It’s basically a redesign of RC4, given current cryptographic tools and knowledge.

RC4 is an example of what I think of as a too-good-to-be-true cipher. It looks so simple. It is so simple. In classic cryptographic terms, it’s a single rotor machine. It’s a single self-modifying rotor, but it modifies itself very slowly. Even so, it’s very hard to cryptanalyze. Even though the single rotor leaks information about its internal state with every output byte, its self-modifying structure always seems to stay ahead of analysis. But RC4 been around for over 25 years, and the best attacks are at the edge of practicality. When I talk about what sorts of secret cryptographic advances the NSA might have, a practical RC4 attack is one of the possibilities.

Spritz is Rivest and Schuldt’s redesign of RC4. It retains all of the problems that RC4 had. It’s built on a 256-element array of bytes, making it less than ideal for modern 32-bit and 64-bit CPUs. It’s not very fast. (It’s 50% slower than RC4, which was already much slower than algorithms like AES and Threefish.) It has a long key setup. But it’s a very clever design.

Here are the cores of RC4 and Spritz:

RC4:

1: i = i + 1
2: j = j + S[i]
3: SWAP(S[i];S[j])
4: z = S[S[i] + S[j]]
5: Return z

Spritz:

1: i = i + w
2: j = k + S[j + S[i]]
2a: k = i + k + S[j]
3: SWAP(S[i];S[j])
4: z = S[j + S[i + S[z + k]]]
5: Return z

S is an 8-bit permutation. In theory, it can be any size, which is nice for analysis, but in practice, it’s a 256-element array. RC4 has two pointers into the array: i and j. Spritz adds a third: k. The parameter w is basically a constant. It’s always 1 in RC4, but can be any odd number in Spritz (odd because that means it’s always relatively prime to 256). In both ciphers, i slowly walks around the array, and j—or j and k—bounce around wildly. Both have a single swap of two elements of the array. And both produce an output byte, z, a function of all the other parameters. In Spritz, the previous z is part of the calculation of the current z.

That’s the core. There are also functions for turning the key into the initial array permutation, using this as a stream cipher, using it as a hash function, and so on. It’s basically a sponge function, so it has a lot of applications.

What’s really interesting here is the way Rivest and Schuldt chose their various functions. They basically tried them all (given some constraints), and chose the ones with the best security properties. This is the sort of thing that can only be done with massive computing power.

I have always really liked RC4, and am happy to see a 21st-century redesign. I don’t know what kind of use it’ll get with its 8-bit word size, but surely there’s a niche for it somewhere.

Posted on October 27, 2014 at 9:55 AM • View Comments

iPhone Encryption and the Return of the Crypto Wars

Last week, Apple announced that it is closing a serious security vulnerability in the iPhone. It used to be that the phone’s encryption only protected a small amount of the data, and Apple had the ability to bypass security on the rest of it.

From now on, all the phone’s data is protected. It can no longer be accessed by criminals, governments, or rogue employees. Access to it can no longer be demanded by totalitarian governments. A user’s iPhone data is now more secure.

To hear US law enforcement respond, you’d think Apple’s move heralded an unstoppable crime wave. See, the FBI had been using that vulnerability to get into people’s iPhones. In the words of cyberlaw professor Orin Kerr, “How is the public interest served by a policy that only thwarts lawful search warrants?”

Ah, but that’s the thing: You can’t build a backdoor that only the good guys can walk through. Encryption protects against cybercriminals, industrial competitors, the Chinese secret police and the FBI. You’re either vulnerable to eavesdropping by any of them, or you’re secure from eavesdropping from all of them.

Backdoor access built for the good guys is routinely used by the bad guys. In 2005, some unknown group surreptitiously used the lawful-intercept capabilities built into the Greek cell phone system. The same thing happened in Italy in 2006.

In 2010, Chinese hackers subverted an intercept system Google had put into Gmail to comply with US government surveillance requests. Back doors in our cell phone system are currently being exploited by the FBI and unknown others.

This doesn’t stop the FBI and Justice Department from pumping up the fear. Attorney General Eric Holder threatened us with kidnappers and sexual predators.

The former head of the FBI’s criminal investigative division went even further, conjuring up kidnappers who are also sexual predators. And, of course, terrorists.

FBI Director James Comey claimed that Apple’s move allows people to “place themselves beyond the law” and also invoked that now overworked “child kidnapper.” John J. Escalante, chief of detectives for the Chicago police department now holds the title of most hysterical: “Apple will become the phone of choice for the pedophile.”

It’s all bluster. Of the 3,576 major offenses for which warrants were granted for communications interception in 2013, exactly one involved kidnapping. And, more importantly, there’s no evidence that encryption hampers criminal investigations in any serious way. In 2013, encryption foiled the police nine times, up from four in 2012­—and the investigations proceeded in some other way.

This is why the FBI’s scare stories tend to wither after public scrutiny. A former FBI assistant director wrote about a kidnapped man who would never have been found without the ability of the FBI to decrypt an iPhone, only to retract the point hours later because it wasn’t true.

We’ve seen this game before. During the crypto wars of the 1990s, FBI Director Louis Freeh and others would repeatedly use the example of mobster John Gotti to illustrate why the ability to tap telephones was so vital. But the Gotti evidence was collected using a room bug, not a telephone tap. And those same scary criminal tropes were trotted out then, too. Back then we called them the Four Horsemen of the Infocalypse: pedophiles, kidnappers, drug dealers, and terrorists. Nothing has changed.

Strong encryption has been around for years. Both Apple’s FileVault and Microsoft’s BitLocker encrypt the data on computer hard drives. PGP encrypts e-mail. Off-the-Record encrypts chat sessions. HTTPS Everywhere encrypts your browsing. Android phones already come with encryption built-in. There are literally thousands of encryption products without back doors for sale, and some have been around for decades. Even if the US bans the stuff, foreign companies will corner the market because many of us have legitimate needs for security.

Law enforcement has been complaining about “going dark” for decades now. In the 1990s, they convinced Congress to pass a law requiring phone companies to ensure that phone calls would remain tappable even as they became digital. They tried and failed to ban strong encryption and mandate back doors for their use. The FBI tried and failed again to ban strong encryption in 2010. Now, in the post-Snowden era, they’re about to try again.

We need to fight this. Strong encryption protects us from a panoply of threats. It protects us from hackers and criminals. It protects our businesses from competitors and foreign spies. It protects people in totalitarian governments from arrest and detention. This isn’t just me talking: The FBI also recommends you encrypt your data for security.

As for law enforcement? The recent decades have given them an unprecedented ability to put us under surveillance and access our data. Our cell phones provide them with a detailed history of our movements. Our call records, e-mail history, buddy lists, and Facebook pages tell them who we associate with. The hundreds of companies that track us on the Internet tell them what we’re thinking about. Ubiquitous cameras capture our faces everywhere. And most of us back up our iPhone data on iCloud, which the FBI can still get a warrant for. It truly is the golden age of surveillance.

After considering the issue, Orin Kerr rethought his position, looking at this in terms of a technological-legal trade-off. I think he’s right.

Given everything that has made it easier for governments and others to intrude on our private lives, we need both technological security and legal restrictions to restore the traditional balance between government access and our security/privacy. More companies should follow Apple’s lead and make encryption the easy-to-use default. And let’s wait for some actual evidence of harm before we acquiesce to police demands for reduced security.

This essay previously appeared on CNN.com

EDITED TO ADD (10/6): Three more essays worth reading. As is this on all the other ways Apple and the government have to get at your iPhone data.

And an Washington Post editorial manages to say this:

How to resolve this? A police “back door” for all smartphones is undesirable—a back door can and will be exploited by bad guys, too. However, with all their wizardry, perhaps Apple and Google could invent a kind of secure golden key they would retain and use only when a court has approved a search warrant.

Because a “secure golden key” is completely different from a “back door.”

EDITED TO ADD (10/7): Another essay.

EDITED TO ADD (10/9): Three more essays that are worth reading.

EDITED TO ADD (10/12): Another essay.

Posted on October 6, 2014 at 6:50 AM • View Comments

The Security of al Qaeda Encryption Software

The web intelligence firm Recorded Future has posted two stories about how al Qaeda is using new encryption software in response to the Snowden disclosures. NPR picked up the story a week later.

Former NSA Chief Council Stewart Baker uses this as evidence that Snowden has harmed America. Glenn Greenwald calls this “CIA talking points” and shows that al Qaeda was using encryption well before Snowden. Both quote me heavily, Baker casting me as somehow disingenuous on this topic.

Baker is conflating my stating of two cryptography truisms. The first is that cryptography is hard, and you’re much better off using well-tested public algorithms than trying to roll your own. The second is that cryptographic implementation is hard, and you’re much better off using well-tested open-source encryption software than you are trying to roll your own. Admittedly, they’re very similar, and sometimes I’m not as precise as I should be when talking to reporters.

This is what I wrote in May:

I think this will help US intelligence efforts. Cryptography is hard, and the odds that a home-brew encryption product is better than a well-studied open-source tool is slight. Last fall, Matt Blaze said to me that he thought that the Snowden documents will usher in a new dark age of cryptography, as people abandon good algorithms and software for snake oil of their own devising. My guess is that this an example of that.

Note the phrase “good algorithms and software.” My intention was to invoke both truisms in the same sentence. That paragraph is true if al Qaeda is rolling their own encryption algorithms, as Recorded Future reported in May. And it remains true if al Qaeda is using algorithms like my own Twofish and rolling their own software, as Recorded Future reported earlier this month. Everything we know about how the NSA breaks cryptography is that they attack the implementations far more successfully than the algorithms.

My guess is that in this case they don’t even bother with the encryption software; they just attack the users’ computers. There’s nothing that screams “hack me” more than using specially designed al Qaeda encryption software. There’s probably a QUANTUMINSERT attack and FOXACID exploit already set on automatic fire.

I don’t want to get into an argument about whether al Qaeda is altering its security in response to the Snowden documents. Its members would be idiots if they did not, but it’s also clear that they were designing their own cryptographic software long before Snowden. My guess is that the smart ones are using public tools like OTR and PGP and the paranoid dumb ones are using their own stuff, and that the split was the same both pre- and post-Snowden.

Posted on August 19, 2014 at 6:11 AM • View Comments

The Simple Trick that Will Keep You Secure from Government Spies

Last week, the German government arrested someone and charged him with spying for the US. Buried in one of the stories was a little bit of tradecraft. The US gave him an encryption program embedded in a—presumably common—weather app. When you select the weather for New York, it automatically opens a crypto program. I assume this is a custom modification for the agent, and probably other agents as well. No idea how well this program was hidden. Was the modified weather app the same size as the original? Would it pass an integrity checker?

Related: there is an undocumented encryption feature in my own Password Safe program. From the command line, type: pwsafe -e filename

Posted on July 7, 2014 at 1:51 PM • View Comments

1 … 20 21 22 23 24 … 56

Sidebar photo of Bruce Schneier by Joe MacInnis.