End-to-End Encryption: A Problem

Gödel’s Lost Letter and P=NP 2019-12-04

Bopuifs fodszqujpo qspcmfn.

“Unsung Entrepreneur” source

Adolph Ochs was the owner of the New York Times. In 1897 he created the paper’s slogan, “All the News That’s Fit to Print.” We at GLL would like some suggestions on our own slogan. Send us your ideas. Please no suggestion of “All the news that fits we print,” as that is already out there.

Today Ken and I wish to comment on a recent article in the NYT that was on end-to-end encryption.

The article leads by saying:

A Justice Department official hinted on Monday that a yearslong fight over encrypted communications could become part of a sweeping investigation of big tech companies.

Of course, end-to-end encryption scrambles messages so that only the sender and receiver can decode the message. Other methods are weaker: some only encrypt messages as they enter part of the network. This means that one must trust the network to keep your message secret. Thus the end-to-end method reduces the number of parties that one must trust.

In 1912, Ochs was a party to encryption that was literally end-to-end on the globe. The New York Times had bought exclusive American rights to report Roald Amundsen’s expedition to the South Pole. When Amundsen returned to Hobart, Tasmania, he sent a coded cable to his brother Leon who was acting as conduit to the Times and the London Daily Chronicle. The brother pronounced the coast clear for Amundsen to communicate directly to the papers. The stories were still quickly plagiarized once the first one appeared in the Times, and Ochs had to defend his rights with lawsuits.

The Usual Problem

There is an ongoing interest in using end-to-end encryption to protect more and more of our messages. And this interest leads to several hard problems.

The main one addressed by the NYT article is: Does this type of encryption protect bad actors? Many believe that encryption makes it impossible to track criminals. Many in law enforcement, for example, wish to have the ability to access any messages, at least on a court order. Some countries are likely to make this the law—that is, they will insist that they always can access any message. A followup NYT article described debates within Interpol about these matters.

Another Problem

The above problem is not what we wish to talk about today. We want to raise another problem.

How do we know that our messages are being properly encrypted?

We could check that our app is in end-to-end mode. The app will say “yes”. The problem is that this does not prove anything. The deeper question is how do we know that messages are correctly encrypted. Indeed.

Suppose that we are told that the message ${M}$ has been sent to another person as the encrypted message ${E(M)}$ . How do we know that this has been done? Several issues come to mind:

${\bullet }$ The app could lie. The app could for example say it is encrypting your message and it did not.

${\bullet }$ The app could mislead. The app could send an encrypted message and also send the clear message to who ever it wishes.

${\bullet }$ The app could be wrong. The app could think that the message was properly encrypted. The key, for example, could be a weak key.

${\bullet }$ The app method could be flawed. The app’s method could be incorrect. The method used might be vulnerable to non or unknown attacks.

Authenticated encryption seems to cover only part of the need. It can confirm the identity of the sender and that the ciphertext has not been tampered with. This is, however, a far cry from verifying that the encryption itself is proper and free of holes that could make it easy to figure out. Our point is also aside from problems with particular end-to-end implementations such as those considered in this 2017 paper.

Open Problems

Bopuifs fodszqujpo qspcmfn was encrypted with the simple key

$\displaystyle a \rightarrow b, b \rightarrow c, c \rightarrow d, \dots$

The point of this silly example is that it might have been encrypted by a harder method, but it was only encrypted by a trivial substitution method. Nevertheless, Google could not figure it out: