Subverting Backdoored Encryption

This is a really interesting research result. This paper proves that two parties can create a secure communications channel using a communications system with a backdoor. It’s a theoretical result, so it doesn’t talk about how easy that channel is to create. And the assumptions on the adversary are pretty reasonable: that each party can create his own randomness, and…

This is a really interesting research result. This paper proves that two parties can create a secure communications channel using a communications system with a backdoor. It's a theoretical result, so it doesn't talk about how easy that channel is to create. And the assumptions on the adversary are pretty reasonable: that each party can create his own randomness, and that the government isn't literally eavesdropping on every single part of the network at all times.

This result reminds me a lot of the work about subliminal channels from the 1980s and 1990s, and the notions of how to build an anonymous communications system on top of an identified system. Basically, it's always possible to overlay a system around and outside any closed system.

"How to Subvert Backdoored Encryption: Security Against Adversaries that Decrypt All Ciphertexts," by Thibaut Horel and Sunoo Park and Silas Richelson and Vinod Vaikuntanathan.

Abstract: In this work, we examine the feasibility of secure and undetectable point-to-point communication in a world where governments can read all the encrypted communications of their citizens. We consider a world where the only permitted method of communication is via a government-mandated encryption scheme, instantiated with government-mandated keys. Parties cannot simply encrypt ciphertexts of some other encryption scheme, because citizens caught trying to communicate outside the government's knowledge (e.g., by encrypting strings which do not appear to be natural language plaintexts) will be arrested. The one guarantee we suppose is that the government mandates an encryption scheme which is semantically secure against outsiders: a perhaps reasonable supposition when a government might consider it advantageous to secure its people's communication against foreign entities. But then, what good is semantic security against an adversary that holds all the keys and has the power to decrypt?

We show that even in the pessimistic scenario described, citizens can communicate securely and undetectably. In our terminology, this translates to a positive statement: all semantically secure encryption schemes support subliminal communication. Informally, this means that there is a two-party protocol between Alice and Bob where the parties exchange ciphertexts of what appears to be a normal conversation even to someone who knows the secret keys and thus can read the corresponding plaintexts. And yet, at the end of the protocol, Alice will have transmitted her secret message to Bob. Our security definition requires that the adversary not be able to tell whether Alice and Bob are just having a normal conversation using the mandated encryption scheme, or they are using the mandated encryption scheme for subliminal communication.

Our topics may be thought to fall broadly within the realm of steganography: the science of hiding secret communication within innocent-looking messages, or cover objects. However, we deal with the non-standard setting of an adversarially chosen distribution of cover objects (i.e., a stronger-than-usual adversary), and we take advantage of the fact that our cover objects are ciphertexts of a semantically secure encryption scheme to bypass impossibility results which we show for broader classes of steganographic schemes. We give several constructions of subliminal communication schemes under the assumption that key exchange protocols with pseudorandom messages exist (such as Diffie-Hellman, which in fact has truly random messages). Each construction leverages the assumed semantic security of the adversarially chosen encryption scheme, in order to achieve subliminal communication.

from https://www.schneier.com/blog/

Adding Backdoors at the Chip Level

Interesting research into undetectably adding backdoors into computer chips during manufacture: "Stealthy dopant-level hardware Trojans: extended version," also available here: Abstract: In recent years, hardware Trojans have drawn the attention of governments and industry as well as the scientific community. One of the main concerns is that integrated circuits, e.g., for military or critical-infrastructure applications, could be maliciously manipulated during…

Interesting research into undetectably adding backdoors into computer chips during manufacture: "Stealthy dopant-level hardware Trojans: extended version," also available here:

Abstract: In recent years, hardware Trojans have drawn the attention of governments and industry as well as the scientific community. One of the main concerns is that integrated circuits, e.g., for military or critical-infrastructure applications, could be maliciously manipulated during the manufacturing process, which often takes place abroad. However, since there have been no reported hardware Trojans in practice yet, little is known about how such a Trojan would look like and how difficult it would be in practice to implement one. In this paper we propose an extremely stealthy approach for implementing hardware Trojans below the gate level, and we evaluate their impact on the security of the target device. Instead of adding additional circuitry to the target design, we insert our hardware Trojans by changing the dopant polarity of existing transistors. Since the modified circuit appears legitimate on all wiring layers (including all metal and polysilicon), our family of Trojans is resistant to most detection techniques, including fine-grain optical inspection and checking against "golden chips". We demonstrate the effectiveness of our approach by inserting Trojans into two designs -- a digital post-processing derived from Intel's cryptographically secure RNG design used in the Ivy Bridge processors and a side-channel resistant SBox implementation­ -- and by exploring their detectability and their effects on security.

The moral is that this kind of technique is very difficult to detect.

from https://www.schneier.com/blog/

Two New Papers on the Encryption Debate

Seems like everyone is writing about encryption and backdoors this season. "Policy Approaches to the Encryption Debate," R Street Policy Study #133, by Charles Duan, Arthur Rizer, Zach Graves and Mike Godwin. "Encryption Policy in Democratic Regimes," East West Institute. I recently blogged about the new National Academies report on the same topic. Here’s a review of the National Academies…

Seems like everyone is writing about encryption and backdoors this season.

I recently blogged about the new National Academies report on the same topic.

Here's a review of the National Academies report, and another of the East West Institute's report.

EDITED TO ADD (3/8): Commentary on the National Academies study by the EFF.

from https://www.schneier.com/blog/

The "Extended Random" Feature in the BSAFE Crypto Library

Matthew Green wrote a fascinating blog post about the NSA’s efforts to increase the amount of random data exposed in the TLS protocol, and how it interacts with the NSA’s backdoor into the DUAL_EC_PRNG random number generator to weaken TLS….

Matthew Green wrote a fascinating blog post about the NSA's efforts to increase the amount of random data exposed in the TLS protocol, and how it interacts with the NSA's backdoor into the DUAL_EC_PRNG random number generator to weaken TLS.

from https://www.schneier.com/blog/

More on Kaspersky and the Stolen NSA Attack Tools

Both the New York Times and the Washington Post are reporting that Israel has penetrated Kaspersky’s network and detected the Russian operation. From the New York Times: Israeli intelligence officers informed the NSA that, in the course of their Kaspersky hack, they uncovered evidence that Russian government hackers were using Kaspersky’s access to aggressively scan for American government classified programs…

Both the New York Times and the Washington Post are reporting that Israel has penetrated Kaspersky's network and detected the Russian operation.

From the New York Times:

Israeli intelligence officers informed the NSA that, in the course of their Kaspersky hack, they uncovered evidence that Russian government hackers were using Kaspersky's access to aggressively scan for American government classified programs and pulling any findings back to Russian intelligence systems. [Israeli intelligence] provided their NSA counterparts with solid evidence of the Kremlin campaign in the form of screenshots and other documentation, according to the people briefed on the events.

Kaspersky first noticed the Israeli intelligence operation in 2015.

The Washington Post writes about the NSA tools being on the home computer in the first place:

The employee, whose name has not been made public and is under investigation by federal prosecutors, did not intend to pass the material to a foreign adversary. "There wasn't any malice," said one person familiar with the case, who, like others interviewed, spoke on the condition of anonymity to discuss an ongoing case. "It's just that he was trying to complete the mission, and he needed the tools to do it.

I don't buy this. People with clearances are told over and over not to take classified material home with them. It's not just mentioned occasionally; it's a core part of the job.

More news articles.

from https://www.schneier.com/blog/

ISO Rejects NSA Encryption Algorithms

The ISO has decided not to approve two NSA-designed block encryption algorithms: Speck and Simon. It’s because the NSA is not trusted to put security ahead of surveillance: A number of them voiced their distrust in emails to one another, seen by Reuters, and in written comments that are part of the process. The suspicions stem largely from internal NSA…

The ISO has decided not to approve two NSA-designed block encryption algorithms: Speck and Simon. It's because the NSA is not trusted to put security ahead of surveillance:

A number of them voiced their distrust in emails to one another, seen by Reuters, and in written comments that are part of the process. The suspicions stem largely from internal NSA documents disclosed by Snowden that showed the agency had previously plotted to manipulate standards and promote technology it could penetrate. Budget documents, for example, sought funding to "insert vulnerabilities into commercial encryption systems."

More than a dozen of the experts involved in the approval process for Simon and Speck feared that if the NSA was able to crack the encryption techniques, it would gain a "back door" into coded transmissions, according to the interviews and emails and other documents seen by Reuters.

"I don't trust the designers," Israeli delegate Orr Dunkelman, a computer science professor at the University of Haifa, told Reuters, citing Snowden's papers. "There are quite a lot of people in NSA who think their job is to subvert standards. My job is to secure standards."

I don't trust the NSA, either.

from https://www.schneier.com/blog/

Proof that HMAC-DRBG has No Back Doors

New research: "Verified Correctness and Security of mbedTLS HMAC-DRBG," by Katherine Q. Ye, Matthew Green, Naphat Sanguansin, Lennart Beringer, Adam Petcher, and Andrew W. Appel. Abstract: We have formalized the functional specification of HMAC-DRBG (NIST 800-90A), and we have proved its cryptographic security — that its output is pseudorandom — using a hybrid game-based proof. We have also proved that…

New research: "Verified Correctness and Security of mbedTLS HMAC-DRBG," by Katherine Q. Ye, Matthew Green, Naphat Sanguansin, Lennart Beringer, Adam Petcher, and Andrew W. Appel.

Abstract: We have formalized the functional specification of HMAC-DRBG (NIST 800-90A), and we have proved its cryptographic security -- that its output is pseudorandom -- using a hybrid game-based proof. We have also proved that the mbedTLS implementation (C program) correctly implements this functional specification. That proof composes with an existing C compiler correctness proof to guarantee, end-to-end, that the machine language program gives strong pseudorandomness. All proofs (hybrid games, C program verification, compiler, and their composition) are machine-checked in the Coq proof assistant. Our proofs are modular: the hybrid game proof holds on any implementation of HMAC-DRBG that satisfies our functional specification. Therefore, our functional specification can serve as a high-assurance reference.

from https://www.schneier.com/blog/

Alternatives to Government-Mandated Encryption Backdoors

Policy essay: "Encryption Substitutes," by Andrew Keane Woods: In this short essay, I make a few simple assumptions that bear mentioning at the outset. First, I assume that governments have good and legitimate reasons for getting access to personal data. These include things like controlling crime, fighting terrorism, and regulating territorial borders. Second, I assume that people have a right…

Policy essay: "Encryption Substitutes," by Andrew Keane Woods:

In this short essay, I make a few simple assumptions that bear mentioning at the outset. First, I assume that governments have good and legitimate reasons for getting access to personal data. These include things like controlling crime, fighting terrorism, and regulating territorial borders. Second, I assume that people have a right to expect privacy in their personal data. Therefore, policymakers should seek to satisfy both law enforcement and privacy concerns without unduly burdening one or the other. Of course, much of the debate over government access to data is about how to respect both of these assumptions. Different actors will make different trade-offs. My aim in this short essay is merely to show that regardless of where one draws this line -- whether one is more concerned with ensuring privacy of personal information or ensuring that the government has access to crucial evidence -- it would be shortsighted and counterproductive to draw that line with regard to one particular privacy technique and without regard to possible substitutes. The first part of the paper briefly characterizes the encryption debate two ways: first, as it is typically discussed, in stark, uncompromising terms; and second, as a subset of a broader problem. The second part summarizes several avenues available to law enforcement and intelligence agencies seeking access to data. The third part outlines the alternative avenues available to privacy-seekers. The availability of substitutes is relevant to the regulators but also to the regulated. If the encryption debate is one tool in a game of cat and mouse, the cat has other tools at his disposal to catch the mouse -- and the mouse has other tools to evade the cat. The fourth part offers some initial thoughts on implications for the privacy debate.

Blog post.

from https://www.schneier.com/blog/

The US Senate Is Using Signal

The US Senate just approved Signal for staff use. Signal is a secure messaging app with no backdoor, and no large corporate owner who can be pressured to install a backdoor. Susan Landau comments. Maybe I’m being optimistic, but I think we just won the Crypto War. A very important part of the US government is prioritizing security over surveillance….

The US Senate just approved Signal for staff use. Signal is a secure messaging app with no backdoor, and no large corporate owner who can be pressured to install a backdoor.

Susan Landau comments.

Maybe I'm being optimistic, but I think we just won the Crypto War. A very important part of the US government is prioritizing security over surveillance.

from https://www.schneier.com/blog/