Page 9 of 22
A drug dealer claims that the police leaned him over an 18th floor balcony and threatened to kill him if he didn’t give up his password. One of the policemen involved corroborates this story.
This is what’s known as “rubber-hose cryptanalysis,” well-described in this xkcd cartoon.
New paper: “Surreptitiously Weakening Cryptographic Systems,” by Bruce Schneier, Matthew Fredrikson, Tadayoshi Kohno, and Thomas Ristenpart.
Abstract: Revelations over the past couple of years highlight the importance of understanding malicious and surreptitious weakening of cryptographic systems. We provide an overview of this domain, using a number of historical examples to drive development of a weaknesses taxonomy. This allows comparing different approaches to sabotage. We categorize a broader set of potential avenues for weakening systems using this taxonomy, and discuss what future research is needed to provide sabotage-resilient cryptography.
EDITED TO ADD (3/3): News article.
I missed this paper when it was first published in 2012:
“Neuroscience Meets Cryptography: Designing Crypto Primitives Secure Against Rubber Hose Attacks”
Abstract: Cryptographic systems often rely on the secrecy of cryptographic keys given to users. Many schemes, however, cannot resist coercion attacks where the user is forcibly asked by an attacker to reveal the key. These attacks, known as rubber hose cryptanalysis, are often the easiest way to defeat cryptography. We present a defense against coercion attacks using the concept of implicit learning from cognitive psychology. Implicit learning refers to learning of patterns without any conscious knowledge of the learned pattern. We use a carefully crafted computer game to plant a secret password in the participant’s brain without the participant having any conscious knowledge of the trained password. While the planted secret can be used for authentication, the participant cannot be coerced into revealing it since he or she has no conscious knowledge of it. We performed a number of user studies using Amazon’s Mechanical Turk to verify that participants can successfully re-authenticate over time and that they are unable to reconstruct or even recognize short fragments of the planted secret.
Here’s an IDEA-variant with a 128-bit block length. While I think it’s a great idea to bring IDEA up to a modern block length, the paper has none of the cryptanalysis behind it that IDEA had. If nothing else, I would have expected more than eight rounds. If anyone wants to practice differential and linear cryptanalysis, here’s a new target for you.
Appelbaum, Poitras, and others have another NSA article with an enormous Snowden document dump on Der Spiegel, giving details on a variety of offensive NSA cyberoperations to infiltrate and exploit networks around the world. There’s a lot here: 199 pages. (Here they are in one compressed archive.)
Paired with the 666 pages released in conjunction with the December 28 Spiegel article (compressed archive here) on NSA cryptanalytic capabilities, we’ve seen a huge amount of Snowden documents in the past few weeks. According to one tally, it runs 3,560 pages in all.
Hacker News thread. Slashdot thread.
EDITED TO ADD (1/19): In related news, the New York Times is reporting that the NSA has infiltrated North Korea’s networks, and provided evidence to blame the country for the Sony hacks.
EDITED TO ADD (1/19): Also related, the Guardian has an article based on the Snowden documents that GCHQ has been spying on journalists. Another article.
Der Spiegel published a long article today on the NSA’s analysis capabilities against encrypted systems, with a lot of new documents from the Snowden archive.
I’m not going to have time to look at this for a few days. Describe anything interesting you find—with links to the documents—in the comments.
EDITED TO ADD (10/28): This is in conjunction with a presentation by Laura Poitras and Jake Appelbaum at the Chaos Communication Congress.
EDITED TO ADD (1/14): Matthew Green’s comments on the documents. And the Poitras/Appelbaum talk is on YouTube.
This talk (and paper) describe a lattice-based public-key algorithm called Soliloquy developed by GCHQ, and a quantum-computer attack on it.
News article.
Jim Sanborn has given the world another clue to the fourth cyphertext in his Kryptos sculpture at the CIA headquarters.
The NSA recently declassified a report on the Eurocrypt ’92 conference. Honestly, I share some of the writer’s opinions on the more theoretical stuff. I know it’s important, but it’s not something I care all that much about.
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 zSpritz:
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.
Sidebar photo of Bruce Schneier by Joe MacInnis.