Project C-43: A Final Piece of Public-Key Cryptography History
This finally explains what James Ellis was talking about in “The Possibility of Non-Secret Encryption” when he dropped a tantalizing hint about wartime work at Bell Labs.
Entries Tagged "cryptography"
Page 26 of 55
The Problems with CALEA-II
The FBI wants a new law that will make it easier to wiretap the Internet. Although its claim is that the new law will only maintain the status quo, it’s really much worse than that. This law will result in less-secure Internet products and create a foreign industry in more-secure alternatives. It will impose costly burdens on affected companies. It will assist totalitarian governments in spying on their own citizens. And it won’t do much to hinder actual criminals and terrorists.
As the FBI sees it, the problem is that people are moving away from traditional communication systems like telephones onto computer systems like Skype. Eavesdropping on telephones used to be easy. The FBI would call the phone company, which would bring agents into a switching room and allow them to literally tap the wires with a pair of alligator clips and a tape recorder. In the 1990s, the government forced phone companies to provide an analogous capability on digital switches; but today, more and more communications happens over the Internet.
What the FBI wants is the ability to eavesdrop on everything. Depending on the system, this ranges from easy to impossible. E-mail systems like Gmail are easy. The mail resides in Google’s servers, and the company has an office full of people who respond to requests for lawful access to individual accounts from governments all over the world. Encrypted voice systems like Silent Circle are impossible to eavesdrop on—the calls are encrypted from one computer to the other, and there’s no central node to eavesdrop from. In those cases, the only way to make the system eavesdroppable is to add a backdoor to the user software. This is precisely the FBI’s proposal. Companies that refuse to comply would be fined $25,000 a day.
The FBI believes it can have it both ways: that it can open systems to its eavesdropping, but keep them secure from anyone else’s eavesdropping. That’s just not possible. It’s impossible to build a communications system that allows the FBI surreptitious access but doesn’t allow similar access by others. When it comes to security, we have two options: We can build our systems to be as secure as possible from eavesdropping, or we can deliberately weaken their security. We have to choose one or the other.
This is an old debate, and one we’ve been through many times. The NSA even has a name for it: the equities issue. In the 1980s, the equities debate was about export control of cryptography. The government deliberately weakened U.S. cryptography products because it didn’t want foreign groups to have access to secure systems. Two things resulted: fewer Internet products with cryptography, to the insecurity of everybody, and a vibrant foreign security industry based on the unofficial slogan “Don’t buy the U.S. stuff—it’s lousy.”
In 1993, the debate was about the Clipper Chip. This was another deliberately weakened security product, an encrypted telephone. The FBI convinced AT&T to add a backdoor that allowed for surreptitious wiretapping. The product was a complete failure. Again, why would anyone buy a deliberately weakened security system?
In 1994, the Communications Assistance for Law Enforcement Act mandated that U.S. companies build eavesdropping capabilities into phone switches. These were sold internationally; some countries liked having the ability to spy on their citizens. Of course, so did criminals, and there were public scandals in Greece (2005) and Italy (2006) as a result.
In 2012, we learned that every phone switch sold to the Department of Defense had security vulnerabilities in its surveillance system. And just this May, we learned that Chinese hackers breached Google’s system for providing surveillance data for the FBI.
The new FBI proposal will fail in all these ways and more. The bad guys will be able to get around the eavesdropping capability, either by building their own security systems—not very difficult—or buying the more-secure foreign products that will inevitably be made available. Most of the good guys, who don’t understand the risks or the technology, will not know enough to bother and will be less secure. The eavesdropping functions will 1) result in more obscure—and less secure—product designs, and 2) be vulnerable to exploitation by criminals, spies, and everyone else. U.S. companies will be forced to compete at a disadvantage; smart customers won’t buy the substandard stuff when there are more-secure foreign alternatives. Even worse, there are lots of foreign governments who want to use these sorts of systems to spy on their own citizens. Do we really want to be exporting surveillance technology to the likes of China, Syria, and Saudi Arabia?
The FBI’s short–sighted agenda also works against the parts of the government that are still working to secure the Internet for everyone. Initiatives within the NSA, the DOD, and DHS to do everything from securing computer operating systems to enabling anonymous web browsing will all be harmed by this.
What to do, then? The FBI claims that the Internet is “going dark,” and that it’s simply trying to maintain the status quo of being able to eavesdrop. This characterization is disingenuous at best. We are entering a golden age of surveillance; there’s more electronic communications available for eavesdropping than ever before, including whole new classes of information: location tracking, financial tracking, and vast databases of historical communications such as e-mails and text messages. The FBI’s surveillance department has it better than ever. With regard to voice communications, yes, software phone calls will be harder to eavesdrop upon. (Although there are questions about Skype’s security.) That’s just part of the evolution of technology, and one that on balance is a positive thing.
Think of it this way: We don’t hand the government copies of our house keys and safe combinations. If agents want access, they get a warrant and then pick the locks or bust open the doors, just as a criminal would do. A similar system would work on computers. The FBI, with its increasingly non-transparent procedures and systems, has failed to make the case that this isn’t good enough.
Finally there’s a general principle at work that’s worth explicitly stating. All tools can be used by the good guys and the bad guys. Cars have enormous societal value, even though bank robbers can use them as getaway cars. Cash is no different. Both good guys and bad guys send e-mails, use Skype, and eat at all-night restaurants. But because society consists overwhelmingly of good guys, the good uses of these dual-use technologies greatly outweigh the bad uses. Strong Internet security makes us all safer, even though it helps the bad guys as well. And it makes no sense to harm all of us in an attempt to harm a small subset of us.
This essay originally appeared in Foreign Policy.
Another WWII Message Decoded
It’s a really interesting code and story. (The first link has the most detailed information about the code and the cryptanalysis.)
NSA Cryptography Course
This article, from some internal NSA publication, is about Lambros Callimahos, who taught an intensive 18-week course on cryptology for many years and died in 1977. Be sure to notice the great redacted photo of him and his students on page 17.
Last Battle-of-Midway Cryptanalyst
The last cryptanalyst at the Battle of Midway, Rear Admiral Donald “Mac” Showers, USN-Ret, passed away 19 October 2012. His interment at Arlington National Cemetery at Arlington, Virginia, will be Monday, April 15, at 3:00. The family made this a public event to celebrate his life and contributions to the cryptologic community.
Nice Security Mindset Example
A real-world one-way function:
Alice and Bob procure the same edition of the white pages book for a particular town, say Cambridge. For each letter Alice wants to encrypt, she finds a person in the book whose last name starts with this letter and uses his/her phone number as the encryption of that letter.
To decrypt the message Bob has to read through the whole book to find all the numbers.
And a way to break it:
I still use this example, with an assumption that there is no reverse look-up. I recently taught it to my AMSA students. And one of my 8th graders said, “If I were Bob, I would just call all the phone numbers and ask their last names.”
In the fifteen years since I’ve been using this example, this idea never occurred to me. I am very shy so it would never enter my mind to call a stranger and ask for their last name. My student made me realize that my own personality affected my mathematical inventiveness.
I’ve written about the security mindset in the past, and this is a great example of it.
Apple's iMessage Encryption Seems to Be Pretty Good
The U.S. Drug Enforcement Agency has complained (in a classified report, not publicly) that Apple’s iMessage end-to-end encryption scheme can’t be broken. On the one hand, I’m not surprised; end-to-end encryption of a messaging system is a fairly easy cryptographic problem, and it should be unbreakable. On the other hand, it’s nice to have some confirmation that Apple is looking out for the users’ best interests and not the governments’.
Still, it’s impossible for us to know if iMessage encryption is actually secure. It’s certainly possible that Apple messed up somewhere, and since we have no idea how their encryption actually works, we can’t verify its functionality. It would be really nice if Apple would release the specifications of iMessage security.
EDITED TO ADD (4/8): There’s more to this story:
The DEA memo simply observes that, because iMessages are encrypted and sent via the Internet through Apple’s servers, a conventional wiretap installed at the cellular carrier’s facility isn’t going to catch those iMessages along with conventional text messages. Which shouldn’t exactly be surprising: A search of your postal mail isn’t going to capture your phone calls either; they’re just different communications channels. But the CNET article strongly implies that this means encrypted iMessages cannot be accessed by law enforcement at all. That is almost certainly false.
The question is whether iMessage uses true end-to-end encryption, or whether Apple has copies of the keys.
Another article.
Skein Collision Competition
Xkcd had a Skein collision competition. The contest is over—Carnegie Mellon University won, with 384 (out of 1024) mismatched bits—but it’s explained here.
New RC4 Attack
This is a really clever attack on the RC4 encryption algorithm as used in TLS.
We have found a new attack against TLS that allows an attacker to recover a limited amount of plaintext from a TLS connection when RC4 encryption is used. The attacks arise from statistical flaws in the keystream generated by the RC4 algorithm which become apparent in TLS ciphertexts when the same plaintext is repeatedly encrypted at a fixed location across many TLS sessions.
The attack is very specialized:
The attack is a multi-session attack, which means that we require a target plaintext to be repeatedly sent in the same position in the plaintext stream in multiple TLS sessions. The attack currently only targets the first 256 bytes of the plaintext stream in sessions. Since the first 36 bytes of plaintext are formed from an unpredictable Finished message when SHA-1 is the selected hashing algorithm in the TLS Record Protocol, these first 36 bytes cannot be recovered. This means that the attack can recover 220 bytes of TLS-encrypted plaintext.
The number of sessions needed to reliably recover these plaintext bytes is around 230, but already with only 224 sessions, certain bytes can be recovered reliably.
Is this a big deal? Yes and no. The attack requires the identical plaintext to be repeatedly encrypted. Normally, this would make for an impractical attack in the real world, but http messages often have stylized headers that are identical across a conversation—for example, cookies. On the other hand, those are the only bits that can be decrypted. Currently, this attack is pretty raw and unoptimized—so it’s likely to become faster and better.
There’s no reason to panic here. But let’s start to move away from RC4 to something like AES.
Really Clever TLS Attack
This is an extremely clever man-in-the-middle timing attack against TLS that exploits the interaction between how the protocol implements AES in CBC mode for encryption, and HMAC-SHA1 for authentication. (And this is a really good plain-language description of it.)
Sidebar photo of Bruce Schneier by Joe MacInnis.