Skip to content

End-to-End Encryption: A Problem

December 3, 2019

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:

11 Comments leave one →
  1. December 4, 2019 11:41 am

    There also could be bugs in the program to decrypt only some of the time, or decrypt correctly some of the time. And some messaging clients will encrypt as per expected at times, but if something goes wrong will merrily transmit in clear text (somewhat akin to a mobile phone dropping to 2G), usually with no indication in the UI (due to transmission errors, mismatched versions of the clients, etc.)

    And… Google isn’t a magic decryption engine. About the only way it’d find your plain text is if someone else had the same text and encrypted it via the same method. I’m not sure what you meant by “could not figure it out”, but that’s not what a search engine does…?

    Thanks for your engaging and ongoing writing!

  2. rjlipton permalink*
    December 4, 2019 7:57 pm

    Dear dan:

    I agree that Google is not set up to be a decryption agent. It probability could in the future. I like your comment on the possibility that programs could fail some of the time. Very neat point. How about a program that 1/million gets the encryption wrong. That would still be a huge problem….hmmmm



    • December 5, 2019 9:06 am

      There is a possibility of failure for any system. 1 in a million would be a GREAT rate of failure. That’s 0.0001% meaning 99.9999% are fine. You would have a better chance that the sevice that uses the encryption in down than the encryption itself fails.

      • rjlipton permalink*
        December 5, 2019 1:05 pm

        Dear A:

        I agree. But the point is that a very low failure rate that is deliberate could be a tough attack to detect.



  3. Greg Jaxon permalink
    December 5, 2019 2:01 pm

    Zimmerman’s first open source release of PGP phone was “open” so that the app itself could be verified by inspection and reverse engineering of its compiled executable. It also supported a verification protocol that amounted to voice print re-encoding of the session key (so that man-in-the-middle attacks (via two or more sessions) would be detected.

    • rjlipton permalink*
      December 6, 2019 12:25 pm

      Dear Greg Jaxon:

      Thanks for the comment. Of course verification is important for stopping such attacks. However, I stand by the worry that there could still be issues that are possible. The main problem I see is that there is no way—perhaps—to stop all attacks that one could imagine. The central thesis in cryptology has been: trust no one. Or at least trust the fewest one must trust. The issue we raised are that end-to-end like much else is something where we must trust lots of code, lots of systems, and lots of players.

      Do you agree Greg?



  4. December 7, 2019 4:20 am

    Of course, Google’s response now is different: it finds GLL as its first hit, and the Theory of Computing blog aggregator second. But, curiously, it starts off with
    Did you mean: Boufs forza ujpo qspcmfn
    which leads to a hair salon in Gleneagles.

  5. rjlipton permalink*
    December 7, 2019 11:17 am

    Dear Peter:

    That is funny. A hair salon? Very interesting. Reminds me have a hair cut this coming Tuesday.




  6. Anonymous Coward permalink
    December 14, 2019 10:36 am

    > The app could lie

    This is why it is vitally important to only use software that is free software, with reproducible builds, and for security-related software, for normal people to only use software from trusted repositories at neutral third party projects such as Debian.

    There should never be a chance for the app to lie to you. Yes there may be things like weak keys and whatnot that the app can be better at making clear, but lying is not something we should accept from the technology in our lives.

    • rjlipton permalink*
      December 14, 2019 10:54 am

      Dear Anyonymous:

      Thanks for the cogent comment. Yes open software does have an advantage that you describe. I still worry about attacks on even this type of software.




  1. No Password Encryption | Gödel's Lost Letter and P=NP

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s