What is End-to-End Encryption?
Last week, I noticed an option to send “secret” messages on Facebook. WhatsApp updated to a fully end-to-end encrypted version early this year. Google has declared “Allo” with optional end-to-end encryption in I/O. Apple was at court with FBI for its end-to-end encryption in February. It’s been a busy year for encryption.
In the simplest terms, end-to-end encryption is used to enable a sender and a receiver to communicate privately or confidentially on an open system. It is the inability of anybody other than the sender and the receiver to read a message there.
Why is this called end-to-end encryption? Why did Facebook come up with new option where its always on for WhatsApp? What was all the fuss about the iPhone FBI wanted access to? Why is all this so vague?
WhatsApp vs Apple vs Facebook
Before we go into details of the encryption, let’s compare the released products — WhatsApp, Apple iMessage and FaceTime, and Facebook Messenger, and the confidentiality provided by them.
In the first table, you can see the features that WhatsApp, Apple and Facebook provide. Facebook’s “Secret Conversation” is the one with least features. Apple with its iMessage, FaceTime and Siri triplet is the most feature rich one.
As we can see in the second table, features have their cost in security. An added feature means an added item to manage while providing end-to-end encryption.
History of End-to-End
So why is this referred as end-to-end encryption and not confidential messages? There is some history to this.
In computer science, students get introduced to the concept of end-to-end in the context of networking. The concept comes into play to describe two nodes communicating in a sea of nodes. How should they work together so that two particular nodes can talk?
The classic end-to-end paper[3] discusses the argument for few functionalities, such as, error control, delivery mechanism and security using encryption. Somehow “end-to-end” found its way out of the classic research paper from 1984 and into the press. End-to-end encryption should be called just encryption or confidentiality.
Instant Messaging, Once upon a Time
Some might remember the “end-to-end security” buzz during the dot com boom. So why is it resurfacing? Wasn’t that solved? Why not?
To understand this we will have to go back into the history of instant messaging or chats. Many years ago there was IRC and may be AIM in the world of IM-ing. In those days unless Alice logged in Bob couldn’t send her a message. Her messages would go away the moment she logged out. History of messages were not kept on her Windows 98 desktop. Her messages were not backed up. Unless you were IBM, you did not know what backup meant. With fewer things that was in “everybody and everything” it was easier to provide end-to-end security. As long as the network between Alice and Bob was secure the messages were secure. This was true for all the other primitive Internet applications. But yet in most cases the path between the ends was not secure. As the applications have become feature rich with search and backup, it is harder now.
Alice and Bob communicate using their phones connected over cell towers and routers, with the aid of the servers. They use services like, emojis, payments and locations within that message. To communicate privately, they need to encrypt the conversation from that very server and network they are connected over. They also need to hide it from eavesdroppers in forms of other services and apps on their phone, from bystanders and from parties, hackers or governments, actively trying to access the message.
Apple vs FBI
All I wanted to know was what was going on technically with that iPhone. I had to read five white papers and three news articles to makes some sense of this.
First, lets figure out what happens with a message on an iPhone. If Alice sends a message to Bob, on her iPhone who can read it? Here, Alice and Bob are the ends. Everybody and everything else is not an end. With end-to-end encryption, Alice and Bob have “confidentiality”. Which means they should be the only two people reading it. Now as you can see with that court case[1], this “everybody and everything” else can get tricky. While the message is being sent through the cell phone towers, the Internet and through Apple servers — it is encrypted. But then Alice and Bob save all their messages on their phones. They also back those up in the iCloud. The messages in the iCloud are encrypted, too [2]. But they were not confidential. There was a trick to accessing them. The article has the detail of the trick used. On the other hand, the messages on the phone were not accessible. The messages were encrypted on the phone’s secure storage. (The keys stayed on the phone, too.) They could only be accessed using the passcode that no one had. And the iPhone was designed to erase itself after few wrong trials.
“The file system key is stored in Effaceable Storage. Since it’s stored on the device, this key is not used to maintain the confidentiality of data; instead, it’s designed to be quickly erased on demand.” [2]
Apple deserves a credit for saying it loud that this key is not used to provide “confidentiality”. The 63-page white paper is quite an easy read. Unlike typical privacy policies that we click through, it has a contents page, block diagrams and a glossary. It refers to RFCs quite frequently.
Now, we know a little bit about end-to-end encryption for iMessages and how it was not quite enough. There are still many questions. What if it was a group chat with Carol? What if Alice sent photos to Bob? What about the calls? Who is listening to them? What about the FaceTime calls? What about the notifications about the message that pops up on the phone? Where is iCloud? Can an Apple employee read my messages on there? FBI could.
All these questions are areas of cryptography with long reading lists. Multiparty computation, database encryption, synchronous vs asynchronous communication, storage security, forward secrecy — to list some keywords related to the concerns.
I figured the answers to some those through my readings. The types of keys used for protecting different features are listed in the Apple white paper. That is usually a good hint about what kind of protocol is used. I have summarized that in the table at the beginning. I still have lot of “Why?”s, “How?”s and “Really?”s about them. But, in short I would say, I was pleasantly surprised. The security fails always make the press and we tend to forget the saved ones.
Another Case Study: WhatsApp
While reading through and searching for what Apple does for security I kept coming across WhatsApp. I had to give it some attention. WhatsApp provides end-to-end encryption for everything. They started the effort in 2013 and early 2016 they finally could say anything under their wing is encrypted. According to their security policy [5], they really mean everything unless you never upgraded your WhatsApp to the version that has end-to-end security. (Backwards portability, sigh!) It will be quite an understatement to say they are messaging like the good old times. But from a security perspective they are. They do not backup anything. They do not want to have any user data with them. Some complexities that they have to deal with with are users being offline or push notifications, groups, realtime audio and recorded video messages. Only catch is that messages are left on your device as history or old archived messages. They remain “plaintext”. This simplicity makes them less complex compared to Apple. But I would say they do encryption more smartly.
There is quite some street cred and genius involved in how they actually do it and provide “forward secrecy” and “future secrecy”. Well, it is the Open Whisper Systems that did it for WhatsApp and quite a few other big names with their “Signal Protocol”. I had to go through some hoops to figure this out. The policy posted doesn’t quite spell it out. Bunch of news articles, including, Wired[6] talks highly about Moxie Marlinspike. That lead to the protocol Signal Protocol and their website Open Whisper Systems[7]. It’s a beautiful protocol!
At this point we will assume a little bit of knowhow of basic public key cryptography. To send Bob an encrypted message Alice needs to have Bob’s key. When both Alice and Bob are online they can exchange their keys without any third-party. This is the essence of Diffie-Hellman Key Exchange. Another thing that would be nice to have is to encrypt every message with a new key. It means if the evil Eve or frantic FBI has one key they cannot use it to read older messages. This is know as forward secrecy. Off-The-Record[8] is a famous paper that shows how to exchange keys and send messages together, and continuously rekey for each message. It also has the property Open Whisper Systems refers to as future secrecy, that is the keys for future cannot be derived from an old key. They mix OTR with SCIMP used in Jabber and retain all the security properties. But wait, Alice is sending Bob a message, Bob might not be online. How does Alice get his key? Well the server preemptively stores bunch of keys for Bob. They are the pre-keys[9].
The full details of the protocol is on the website and so is the codebase. I would recommend reading about advanced ratcheting[10] for key exchange and asynchronous encryption[9] for the pre-keys.
Why doesn’t everybody use this “Signal Protocol”?
Now that you know how everything works, you might have the same question.
Short answer: it doesn’t work for them.
[Full Disclaimer, I am going to comment based on my security expertise here. I do not know what is exactly used in all the Trademarked products I mention.]
iCloud aka Online Storage
You might remember the “everything and everybody” we mentioned earlier. We can go back to Apple. Apple seems to be doing something similar to WhatsApp. But, that doesn’t protect the messages Alice wanted to backup to the iCloud. The messages were all encrypted with different keys . Where would Alice store the keys for all those encrypted message? One idea could be to encrypt the messages in the iCloud; backup with a different long-term key and give Alice the key. This means if Alice stored 5 Gigs of messages in iCloud that would be encrypted with one really strong key. But what if Alice also wanted to encrypt all her photos. Alice might have 100 Gigs of photos. What would happen if Alice loses the strong encryption key, aka her phone? Alice cannot decrypt them without the key! What if Alice gives her key to Eve and later realizes her mistake? She might want to change her key. Does this remind you of passwords and forgetting your password? Well, changing the encryption key is thousand times more pain-in-the-behind. Both for the user and the coder.
Groups
How many group threads are you on? How many did people add you on Facebook Messenger? How many on WhatsApp? Do people keep joining and leaving these groups? Do you want somebody who left the group to be able to still read the messages? That would be creepy. Every time a group membership changes, the keys need to change. Key negotiations for a group of ten people might mean getting them all to redo the whole thing in pairs. That’s about hundred pairs. What if nine of them were offline when this happened? Do you remember the pre-key step for Signal Protocol? This will eat up a big chunk of these pre-keys. Should the design now consider storing pre-keys based on number of groups user is on? The service now needs to have some estimate for the pre-keys. May be they roll out in USA first then to Asia. The estimates based on user behavior in USA might be completely inaccurate for China. What happens if chat groups grow to thousands users? For example, all the people in the arena at NBA finals? That would be millions of key negotiations. What if everybody who was watching the telecast of game were on a group?
We had mentioned earlier there is significant research in multi-party crypto. May be some other protocol would be more engineering friendly. Will it be?
Building out the Research
The OTR paper is from 2004. Yet it was not something any major players put in their messaging platforms. I am not that great at understanding the business need of things. It seems there is more attention to it this year; hence there is some business need. But apart from that I can just point out to the engineering effort required to build out the WhatsApp security according to press, aka Wired[6]. Open Whisper Systems had the whole thing already out in the world open sourced. They had a product TextSecure that was using the protocol. Yet, it took WhatsApp 15 engineers and almost a year. This was 30% of their engineering team. I would imagine adding voice calling support had taken similar effort. Its lot of work that is not bringing any money directly. But I would also like to make an analogy with distributed systems or the cloud. Having services distributed and storage distributed is a similarly intense effort. But as more and more companies just think of it as a must, there are more off-the-shelf modules to use. I would like to believe, the more you do security the easier it becomes, too.
Messaging is just the start. What if my emails were encrypted? And my searches? Why aren’t they? Well to search something the application needs to build out the search database. It needs to know what the two billion people on earth with devices searched for the most and what did they click when they searched on. When doing Artificial Intelligence or Machine Learning with less data to learn from, it doesn’t learn that well. But the beautiful part is it might. There is research on this, too. But the engineering work is not.
When will that happen? Maybe someday soon — in another decade. This is already six pages. I’ll right about those another day. I’ll have to read the papers first. The world in the meantime has moved on to Pokemon Go.
References
[1] Lev Grossman / Cupertino, Calif.March 17, 2016. Inside Apple CEO Tim Cook’s Fight With the FBI. http://time.com/4262480/tim-cook-apple-fbi-2/
[2] iOS Security Guide. May 2016. https://www.apple.com/business/docs/iOS_Security_Guide.pdf
[3] J. H. Saltzer, D. P. Reed, and D. D. Clark. 1984. End-to-end arguments in system design. ACM Trans. Comput. Syst. 2, 4 (November 1984), 277–288.
[4] Marjory S. Blumenthal and David D. Clark. 2001. Rethinking the design of the Internet: the end-to-end arguments vs. the brave new world. In Communications Policy in Transition. MIT Press, Cambridge, MA, USA 91–139.
[5] WhatsApp Encryption Overview. April 4, 2016. https://www.whatsapp.com/security/WhatsApp-Security-Whitepaper.pdf
[6] Forget Apple vs. the FBI: WhatsApp Just Switched on Encryption for a Billion People. Kade Metz. 04/05/16. http://www.wired.com/2016/04/forget-apple-vs-fbi-whatsapp-just-switched-encryption-billion-people/
[7] https://whispersystems.org/blog/
[8] Nikita Borisov, Ian Goldberg, and Eric Brewer. 2004. Off-the-record communication, or, why not to use PGP. In Proceedings of the 2004 ACM workshop on Privacy in the electronic society (WPES ‘04). ACM, New York, NY, USA, 77–84.
[9] Forward Secrecy for Asynchronous Messages. moxie0. Aug 02, 2013. https://whispersystems.org/blog/asynchronous-security/
[10] Advanced cryptographic ratcheting. moxie0. Nov 26, 2013. https://whispersystems.org/blog/advanced-ratcheting/
Trivia
- An interesting thing to note about the end-to-end paper[3] is that its been a heated topic of discussion in academia as well. The follow up paper[4] twenty years later almost completely refutes the original arguments. This week, David Clark, who is the author on both papers came on Freakonomics and spoke about the Internet. Unlike this article it has no acronyms. http://freakonomics.com/podcast/internet/
- Is local search on a Phone private? A local search means nothing is sent back to the server. But where does the “search” functionality come from? Is it a separate App? Does it have its own memory allocation? Can other apps read from that memory?
- Moxie Marlinspike. Do you think that’s a real name?
- “1984” is also the George Orwell book that introduced the concept of a connected world with no privacy or freedom.
- I went through the alphabet with the crypto characters, Alice, Bob, Carol, (Dave), Eve, FBI. This is a cryptography thing. They always talk through Alice, Bob and Eve. They also have an oracle.
