Nearly one year ago, on November 15th 2015, I released the 1.0 version of nom, the fast parser combinators library I wrote in Rust. A lot happened around that project, and I have been really happy to interact with nom users around the world.
There is a very weird part of web applications, where all the nice abstractions and syntax reasoning go wrong, at the interface between the code and a database. At best, there is a leaky abstraction of the database with an ORM, and you have to think about what methods to apply to get the underlying SQL query you need, at worse, you write queries and deserialize manually.
This happens because at one point, applications needed to manipulate more data than their host’s memory could handle. This required a good abstraction over storage, efficient data walking algorithms and fine tuned caching. This also required thousands of hours of engineering, to get a database that is at least bearable to use. Since so much work was put in those databases, you might as well implement as many features as possible, to reuse all this fine engineering.
To work efficiently with these data warehouses and offload a part of the selection work from the application, query languages inspired from logic programming were invented. Basically, they make it easy to work with relations: entity/attribute/value triplets like RDF, or tabled data. Those query language are voluntarily not Turing complete: they do not include loops, negation or unbounded recursion. This helps a lot in optimizing the queries.
Unfortunately, this query language is the barrier between an application and its data. Instead of reasoning about what is in memory, the code must be transformed to load data from the database through a query, deserialize it, compute, reserialize data and put it in the database. Even worse, for efficiency’s sake, some developers push more and more logic to the database, with even more complex queries, views and stored procedures.
What if we could reason directly on a cluster of data as if it was already in the memory? I do not want to create a structure from a deserialized row, change a value then put that row “where id = $myId”. I want to access a structure that is already there in memory, and change the value directly (or clone it and change my index, but that talk is for another blog post).
“No, you cannot access directly data that is not already in your memory”. Sure I can. We already have powerful tools for that. L1 and L2 caches are using that principle, to load data from the RAM and make it available faster to the CPU. Memory mapped file can be lazily loaded page by page in the virtual memory. Imagine loading data lazily from the network, in your address space… Nowadays, we can index data on 64 bits, enough to address the whole world!
“But this totally breaks your security model”. No, it does not. First, most database clusters already assume they’re running on a trusted network. Second, since I see the cluster as a part of my hardware, I think adding a MMU to the lot would work quite well.
“It does not work, because of concurrent accesses”. This already happens in databases, and this is where their powerful query language gets things wrong: if you have a powerful way to access multiple rows at the same time, you have to lock huge parts of the database at once in a transaction to run your mutating query. For virtual memory, we have a lot of interesting tools. Memory pages can be read-write or read-only. Locking through mutexes or Software Transactional Memory could also be implemented at a cluster’s scale. But concurrency is a hard problem, that is often better solved through good data architecture. Immutable data, colocating related data, append-only datastructures, all work as well in memory as on a networked cluster.
This is of course a very big gap to jump, from our traditional databases to a total abstraction in memory, but I think it is an interesting alternative to consider.
There is another model to consider here, one that is currently adopted by large distributed databases: since an application cannot do all the work by just loading data in its memory space, let’s push code onto the data, and run a Turing complete query language on the cluster. This is actually the same kind of model, with worker threads running on your data while you wait for a “work done” message, but you still need to interface your app with the query language. Maybe someday I’ll be able to send a compiled function to run on a cluster.
All in all, the big tools that people built to fight the inefficiencies of yesterday’s technology have to be questioned today. By removing the complex abstractions and their obsolete limitations, we could obtain powerful and simple model to write our future code.
Following the previous article, people have asked me what I would consider as a good secure system, and others asked me to review their app, so I think it will be interesting to expose my process when studying those projects.
The most important point I look for in a project is the threat model. This is the document that will explain for whom the project was created, who are the adversaries, what they are trying to obtain, and which of these threats you are addressing.
Without that document, I cannot know if you considered all the possible actors, and I must infer it from the protocol, which is relatively easy, but my view of the threat model might not correspond to what you expected.
With a good threat model, I can know right away what is your target market (ex: sexting for teens, or secure reporting for journalists in war environments), see if your users will understand the implications, if it will need training, and more importantly, if your system can be safe for that context.
You cannot create a project and say that it will solve all of the privacy problems with some magical crypto algorithm, against all adversaries, even the state actors. I would prefer a useful tool for a niche with real and well defined needs.
As you have probably seen, the secure messaging space is already very crowded. If you come up with a new solution to an already solved problem, you need to justify it. Why didn’t you improve an existing project? Couldn’t you adapt someone else’s code, add a better UI?
the NIH syndrome is at the heart of innovation, so I am not against it. But in the case of crypto applications, it might be a good idea to employ already existing (and already audited) code, instead of writing a whole new protocol or algorithm from scratch.
Otherwise, if you are working on an unsolved problem, or improving on current solutions, be prepared to justify it, and a lot, if you employ unusual systems. I am not telling you to avoid funny stuff like Pailler’s cryptosystem, PIR or pairing based cryptography. Just be aware that people will ask you about these.
That part is fundamental: if you are providing a new protocol or algorithm, you should publish it and ask for review before you start coding and get users. I am not advising you to start up LaTeX and write a paper in ACM format. Just explaining your system on a webpage is fine. The crypto community is full of nice people that will be able to point out if there is any problem (and if you use the academic way of publishing, you might even profit from other people’s funding to get reviews :p).
Some said that the crypto community is full of bitter people eager to hit any new project, following the whole Telegram debacle. That tends to happen when you make a big announcement to get users, telling that it will solve any security problem, and dismiss the opinions of experts, without having asked for review previously.
Note that some of those experts have worked for years on a project before even thinking of communicating about it. As examples, check out Briar, Pond or Cryptosphere: those are quiet but interesting projects. They are not trying to get a lot of users quickly or profit from the post Snowden panic. They have been at it for a long time.
So, publish, ask for review, fix flaws, publish again, fix stuff, and repeat again and again. That is the smartest way to spend your time and money on your project. Once everything is developed and deployed, you will have a hard time trying to plug the holes.
Once we get in the technical stuff, the protocol design is interesting to get a high level view of what you want to achieve. I’ll ask questions like:
- Is it server centric or P2P? (note: a network of server introduces routing, but is not P2P)
- Does it include authentication?
- Is it encrypted end to end?
- How do you protect against DoS?
- Is it versioned? Do you allow for protocol version negotiation? Are the algorithms negotiated?
- Can you revoke keys or identities?
Often, the protocol show what you want to achieve with your system, and it is often answering more threats than the crypto algorithms themselves. A good way to present your protocols is to use diagrams and present the message contents.
Do not insist on algorithms at this point: use general words to describe the primitive you need, like authenticated cipher, public key, key derivation function, MAC. You might change the algorithms later, so stating the properties you need will help reviewers understand what you want to achieve.
A specific note on server VS peer to peer: it is a very understandable feeling for geeks that P2P architectures look better, because they’re decentralizing everything, etc. But they can introduce other problems (like hole punching or sybil attacks), and in some case, you will not be able to avoid servers (for message routing and retries, for mobile systems, etc). Both types of systems are fine, just be aware of their shortcomings.
Cryptographic algorithms are not enough, you need to apply them correctly. I will have no pity if you say you use “military grade AES 256 encryption” but do not know what is a block cipher mode or Encrypt-Then-MAC. A lot of ugly details can hide here, so do not try to be clever, use battle tested systems:
- add a separate authentication layer to Diffie-Hellman key exchanges
- use an authenticated encryption mode
- use RSA-OAEP instead of PKCS1 padding
- know well if you need a nonce, an unpredictable number or a time based ID
This is one of the parts where crypto experts will ask annoying questions, because a lot of bugs come from there. They can also propose better solutions (safer, more performant, etc), so listen to them.
If you are employing an unusual scheme here, be prepared to justify it. It might be ok for you, but if the design looks weird to cryptographers, that will raise alarms. Your scheme could be safe, but if it has never been proven right, you are taking a risk, and your users will take that risk too. Is it worth it? Hint: your weird design should provide a unique property that no other algorithm has.
Choice of algorithms
Yes, I do not worry about algorithms until I am already deep in the system. It is not that hard to make correct choices there. Just listen to the recent attacks (ie, avoid RC4) choose large enough keys, choose correct elliptic curves.
Every algorithm has parameters that you need to get right, so be sure to document yourself on your algorithm choices:
- AES-CBC needs an initialization vector, but AES-CTR uses an incremented nonce
- RSA needs a good exponent
- Some elliptic curves work better for some operations
Even if you choose dubious algorithms, if your protocol was well designed, you will be able to move to better algorithm. Be careful with algorithm negotiation, though, a lot of smart people were bitten before.
This is probably the part that I will skip, because I do not have the time nor the funding to audit thoroughly the code of every new projects. I will often grep a bit through the code, look for some important points, but this is not something that should be done quickly. This is where the protocol review shows its limits.
Even with a good design, a lot of vulnerabilities can be present in a flawed implementation. Crypto projects should undergo a careful audit like the one Least Authority performed recently on Cryptocat. And that is why you should not communicate about your project before it has been reviewed.
There are things you should always look for in your software projects:
- encrypting data at rest: if you worry about stolen data, know that a mobile phone or laptop can be stolen
- random number generation: you should use a CSPRNG, with a good source, and probably some user or device specific data
- data backup: is it possible? is it safe?
- software updates: are they downloaded from a secure source? Are the updates verified?
- Do you use public key pinning?
- How long are they private keys stored as plaintext in memory?
The implementation details are as important as the whole protocol. You can have a good protocol, but a small error in the code could greatly affect your users. Nevertheless, specifying your protocol is useful, because people can provide better implementations, or make it interoperate with other software. Having other implementations is a good thing: you will not control those versions, but they will be able to construct cool stuff around your system, and make a part of your PR.
this part is more and more important, because we have been able to create safe systems for years, but often at the price of usability. The user experience of crypto apps needs a lot of innovation, and I’ll follow closely any interesting idea in that space: onboarding experience, useful alerts, user decision making, etc. People should be able to understand when there is a security problem.
I’ll state it once more: if you create a new crypto software, you HAVE to make it easy to use and understand. Some complexity is acceptable, but it must be compensated by documentation (with screenshots, etc) or training.
There are two others that I could think of, but they do not matter that much.
The first is the team. I have been accused of making fun of Telegram for waving around their team of PhDs, but the truth is that I was hopeful: a team full of smart people can come up with interesting design and solve complex problems. If they do not deliver on that, I could be less indulgent. That does not mean I will think less of people without big diplomas. I know too many smart people that dropped out of school to make that mistake. Ultimately, the important thing to judge is the design.
The last parameter is attitude. It is normal to be defensive when someone else reviews your work, but that does not justify denial and dishonesty. People are often taking time off of their job to study your system, so they will be quick and get to the point. If you do not answer or refuse to explain your decisions, it will smell fishy. Even more if you did not ask for a review before communicating about your project. But it does not matter that much. If you are humble and quick to answer, people may help you out of good will, but if you anger cryptographers, you may just have won a free thorough audit😀
Disclaimer: this post is now very old and may not reflect the current state of Telegram’s protocol. There has been other research in the meantime, and this post should not be used for your choice of secure messaging app. That said, on a personal note, I still think Telegram’s cryptosystem is weird, and its justifications are fallacious. If you want a recommendation on secure messaging apps: use a system based on the Axolotl/Signal protocol. It is well designed and has been audited. Signal and WhatsApp are both using that protocol, and there are others.
Here is the second entry in our serie about weird encryption apps, about Telegram, which got some press recently.
According to their website, Telegram is “cloud based and heavily encrypted”. How secure is it?
Very secure. We are based on a new protocol, MTProto, built by our own specialists, employing time-tested security algorithms. At this moment, the biggest security threat to your Telegram messages is your mother reading over your shoulder. We took care of the rest.
(from their FAQ)
Yup. Very secure, they said it.
So, let’s take a look around.
Available technical information
Their website details the protocol. They could have added some diagrams, instead of text-only, but that’s still readable. There is also an open source Java implementation of their protocol. That’s a good point.
About the team (yes, I know, I said I would not do ad hominem attacks, but they insist on that point):
The team behind Telegram, led by Nikolai Durov, consists of six ACM champions, half of them Ph.Ds in math. It took them about two years to roll out the current version of MTProto. Names and degrees may indeed not mean as much in some fields as they do in others, but this protocol is the result of thougtful and prolonged work of professionals
(Seen on Hacker News)
They are not cryptographers, but they have some background in maths. Great!
So, what is the system’s architecture? Basically, a few servers everywhere in the world, routing messages between clients. Authentication is only done between the client and the server, not between clients communicating with each other. Encryption happens between the client and the server, but not using TLS (some home made protocol instead). Encryption can happen end to end between clients, but there is no authentication, so the server can perform a MITM attack.
Basically, their threat model is a simple “trust the server”. What goes around the network may be safely encrypted, although we don’t know anything about their server to server communication, nor about their data storage system. But whatever goes through the server is available in clear. By today’s standards, that’s boring, unsafe and careless. For equivalent systems, see Lavabit or iMessage. They will not protect your messages against law enforcement eavesdropping or server compromise. Worse: you cannot detect MITM between you and your peers.
I could stop there, but that would not be fun. The juicy bits are in the crypto design. The ideas are not wrong per se, but the algorithm choices are weird and unsafe, and they take the most complicated route for everything.
The protocol has two phases: the key exchange and the communication.
The key exchange registers a device to the server. They wrote a custom protocol for that, because TLS was too slow and complicated. That’s true, TLS needs two roundtrips between the client and the server to exchange a key. It also needs x509 certificates, and a combination of a public key algorithm like RSA or DSA, and eventually a key exchange algorithm like Diffie-Hellman.
Telegram greatly simplified the exchange by requiring three roundtrips, using RSA, AES-IGE (some weird mode that nobody uses), and Diffie-Hellman, along with a proof of work (the client has to factor a number, probably a DoS protection). Also, they employ some home made function to generate the AES key and IV from nonces generated by the server and the client (server_nonce appears in plaintext during the communication):
- key = SHA1(new_nonce + server_nonce) + substr (SHA1(server_nonce + new_nonce), 0, 12);
- IV = substr (SHA1(server_nonce + new_nonce), 12, 8) + SHA1(new_nonce + new_nonce) + substr (new_nonce, 0, 4);
Note that AES-IGE is not an authenticated encryption mode. So they verify the integrity. By using plain SHA1 (nope, not a real MAC) on the plaintext. And encrypting the hash along with the plaintext (yup, pseudoMAC-Then-Encrypt).
The final DH exchange creates the authorization key that will be stored (probably in plaintext) on the client and the server.
I really don’t understand why they needed such a complicated protocol. They could have made something like: the client generates a key pair, encrypts the public key with the server’s public key, sends it to the server with a nonce, and the server sends back the nonce encrypted with the client’s public key. Simple and easy. And this would have provided public keys for the clients, for end-to-end authentication.
About the communication phase: they use some combination of server salt, message id and message sequence number to prevent replay attacks. Interestingly, they have a message key, made of the 128 lower order bits of the SHA1 of the message. That message key transits in plaintext, so if you know the message headers, there is probably some nice info leak there.
The AES key (still in IGE mode) used for message encryption is generated like this:
The algorithm for computing aes_key and aes_iv from auth_key and msg_key is as follows:
- sha1_a = SHA1 (msg_key + substr (auth_key, x, 32));
- sha1_b = SHA1 (substr (auth_key, 32+x, 16) + msg_key + substr (auth_key, 48+x, 16));
- sha1_с = SHA1 (substr (auth_key, 64+x, 32) + msg_key);
- sha1_d = SHA1 (msg_key + substr (auth_key, 96+x, 32));
- aes_key = substr (sha1_a, 0, 8) + substr (sha1_b, 8, 12) + substr (sha1_c, 4, 12);
- aes_iv = substr (sha1_a, 8, 12) + substr (sha1_b, 0, 8) + substr (sha1_c, 16, 4) + substr (sha1_d, 0, 8);
where x = 0 for messages from client to server and x = 8 for those from server to client.
Since the auth_key is permanent, and the message key only depends on the server salt (living 24h), the session (probably permanent, can be forgotten by the server) and the beginning of the message, the message key may be the same for a potentially large number of messages. Yes, a lot of messages will probably share the same AES key and IV.
Edit: Following Telegram’s comment, the AES key and IV will be different for every message. Still, they depend on the content of the message, and that is a very bad design. Keys and initialization vectors should always be generated from a CSPRNG, independent from the encrypted content.
Edit 2: the new protocol diagram makes it clear that the key is generated by a weak KDF from the auth key and some data transmitted as plaintext. There should be some nice statistical analysis to do there.
Edit 3: Well, if you send the same message twice (in a day, since the server salt lives 24h), the key and IV will be the same, and the ciphertext will be the same too. This is a real flaw, that is usually fixed by changing IVs regularly (even broken protocols like WEP do it) and changing keys regularly (cf Forward Secrecy in TLS or OTR). The unencrypted message contains a (time-dependent) message ID and sequence number that are incremented, and the client won’t accept replayed messages, or too old message IDs.
Edit 4: Someone found a flaw in the end to end secret chat. The key generated from the Diffie-Hellman exchange was combined with a server-provided nonce:
key = (pow(g_a, b) mod dh_prime) xor nonce. With that, the server can perform a MITM on the connection and generate the same key for both peers by manipulating the nonce, thus defeating the key verification. Telegram has updated their protocol description and will fix the flaw. (That nonce was introduced to fix RNG issues on mobile devices).
Seriously, I have never seen anyone use the MAC to generate the encryption key. Even if I wanted to put a backdoor in a protocol, I would not make it so evident…
To sum it up: avoid at all costs. There are no new ideas, and they add their flawed homegrown mix of RSA, AES-IGE, plain SHA1 integrity verification, MAC-Then-Encrypt, and a custom KDF. Instead of Telegram, you should use well known and audited protocols, like OTR (usable in IRC, Jabber) or the Axolotl key ratcheting of TextSecure.
For the first article in the new post serie about “let’s pick apart the new kickstarted secure decentralized software of the week”, I chose SafeChat, which started just two days ago. Yes, I like to hunt young preys :p
A note, before we begin: this analysis is based on publicly available information at the time of writing. If the authors of the project give more information, I can update the article to match it. The goal is to assert, with what little we know about the project, if it is a good idea to give money to this project. I will only concentrate on the technical parts, not on the team itself (even if, for some of those projects, I think they’re idiots running with scissors in hand).
What is SafeChat?
Open source encryption based instant messaging software
SafeChat is a brilliantly simple deeply secure instant messaging system for mobile phones and computers
SafeChat is an instant messaging software designed by Commercial Free. There is no real indication about who really works there, and where the company is based, except for David Crawford, who created the Kickstarter project and is based in Montreal in Canada.
Note that SafeChat is only a small part of the services they want to provide. Commercial Free will also have plans including an email encryption service (no info about that one) and cloud storage.
Available technical information
There is not much to see. They say they are almost done with the core code, but the only thing they present is some videos of what the interaction with the app could be.
Apparently, it is an instant messaging application with Android and iOS applications and some server components. Session keys are generated for the communication between users. They will manage the server component, and the service will be available with a yearly subscription.
It seems they don’t want to release much information about the cryptographic components they use. They talk about “peer to peer encryption” (lol) which is open source and standard. If anyone understands what algorithm or protocol they refer to, please enlighten me. They also say they will mix in some proprietary code (so much for open source).
I especially like the part about NIST. They mock NIST, telling that they have thrown “all standard encryption commonly used today out the window”. I am still wondering what “open source and standard peer to peer encryption” means.
The iOS and Android applications will apparently provide direct communication between users. I guess that from their emphasis on P2P, but also from the price they claim: $10 per user per year would be a bit small to pay for server costs if they had to route all the messages.
P2P communication between phones is technically feasible. They would probably need to implement some TCP hole punching in their solution, but it is doable.
Looking athe the video, it seems there is a key agreement before communication. I do not really like the interaction they chose to represent key agreement (with the colors and the smileys). There are too many different states, while people only need to know “are we safe now?”
I am not sure if there is a presence protocol. The video does not really show it. If there is no presence system, are messages stored until the person is online? Stored on the server or on the client? Does the server notify the client when the person becomes available?
By bringing together existing theories of cryptography and some proprietary code to bind them together, we are making a deeply encrypted private chatting system that continues to evolve as the field of cryptography does.
Yup, I really feel safe now.
Joke aside, here is what we can guess:
- session keys for the communication between users. I don’t know if it is a Diffie-Hellman based protocol
- no rekeying, ie no perfect forward secrecy
- no info on message authentication or integrity verification
- I am not sure if the app generates some asymmetric keys for authentication, if there is trust on first use, or whatever else
- the server might not be very safe, because they really, really want to rely on German laws to protect it. If the crypto was fully managed client side, they would not care about servers taken down, they could just pop another somewhere.
There could be a PKI managed by Commercial Free. That would be consistent with the subscription model (short lived certificates is an easy way of limiting the usage of a service).
Now, we can draw the rough threat model they are using:
What we want to do is make it impractical for an organization to snoop your communications as it would become very hard to find them and then harder still to decrypt them.
Pro tip: a system with a central server does not make it hard to find communications.
- phone thief: I don’t think they use client side encryption for credentials and logs. Phone thiefs and forensics engineers won’t have a real problem there
- network operator: they can disrupt the communication, but will probably not be able to decrypt or do MITM (I really think the server is managing the authentication part, along with setting up the communication)
- law enforcement: they want to rely on German laws to protect their system. At the same time, they do not say they will move out to Germany to operate the system. If they stay in Canada, that changes the legal part. If they use a certificate authority, protecting the server will be useless, because they can just ask the key at the company.
- server attacker: the server will probably be Windows based (see the core developer’s skills). Since that design is really server centric, taking down the server might take down the whole service. And attacking it will reveal lots of interesting metadata, and probably offer MITM capabilities
- nation state: please, stop joking…
Really, nothing interesting here. I do not see any reason to give money to this project: there is nothing new, it does not solve big problems like anonymous messaging, or staying reliable if one server is down. Worse, it is probably possible to perform a MITM attack if you manage the server. Nowadays, if you create a cryptographic protocol with client side encryption, you must make sure that your security is based on the client, not the server.
Alternatives to this service:
- Apple iMessage: closed source, only for iOS, encrypted message, MITM is permitted for Apple by the protocol, but “we have not architected the server for this”. Already available.
- Text Secure by OpenWhisperSystems: open source, available for iOS and Android, uses SMS as a transport protocol, uses OTR (Off the Record protocol) to protect the communication, no server component. Choose Text Secure! It is really easy to use, and OTR is well integrated in the interface.
Every week, I hear about a new secure software designed to protect your privacy, thwart the NSA/GCHQ and save kittens. Most of the time, though, they’re started by people that are very enthusiastic yet unskilled.
They tend to concentrate directly on choosing algorithms and writing code, instead of stepping back and thinking a bit about what they want to develop.
Sure, they probably spent some time saying things like:
- that piece of data should absolutely be encrypted
- users will all have key pairs to authenticate themselves
- we should use AES, that’s the safest choice (what are theses “modes” you’re talking about?)
That is not how you design a protocol. That is not how you design a software using encryption. And that is not how you will design the next secure distributed social network.
To design your system, you need three things:
- a good threat model
- theoretical tools addressing the threats
- algorithms implementing these theoretical tools
As you see, most of the projects only have the third item, and that’s insufficient to design a correct system. If you don’t have a good threat model, you don’t have a good mental model of your users and attackers, their means and their objectives. If you don’t have the theoretical tools, you will try to shoehorn your favorite algorithm on the problem without knowing if it really fits (example: using hash algorithms to store passwords :p).
So, in this post, I’ll provide those (simplified) theoretical definitions. You will probably recognize some of them.
High level view
First, you need to forget notions like “privacy”, use any of these terms to describe the properties you want to achieve:
- authentication: you can recognize which entity you are communicating with
- authorization: the entity cannot get access to data it has no permission on (note that it is different from authentication)
- confidentiality: the data should not be readable by an entity that has no permission on it (it can be protected by crypto, but also by policies in the code)
- integrity: unauthorized modification of the data can be detected and marked as invalid
- non repudiation: an entity cannot deny it has executed an action
- deniability: an entity _can_ deny it has executed an action
Ok, now that we have some basic properties, let’s apply them: think for a long time about the actors of the system (users, malicious users, admins, sysadmins, random attacker on the network, etc), what authorizations they have, what they should not get access to, what data moves on the network and between whom.
You should now have a very basic threat model and a rough overview of your system or protocol: you know what part of the network communications should be confidential, you know where you would need to authenticate.
You will now need some ideas about the type of attacks that could happen to your system, because you probably did not think of everything. Separate your systems in logical parts (like “client”, and “server”, etc), observe them, and observe how they communicate.
Here are some security properties that will be useful when you will try to choose algorithms later:
- Random oracle: a system that answers deterministically every question with a random answer from its answer space. You cannot predict what it will answer, but if you send the same question twice, it will answer the same both times.
- Perfect secrecy: for any two plaintext messages of same size, an attacker cannot distinguish which plaintext maps to which ciphertext. Basically, the adversary learns nothing from the ciphertext only.
- Semantic security: same thing as perfect secrecy, except what the adversary learns on the plaintext is negligible. example: One Time Pad
those properties can be tested by creating a “game”, where the attacker tries to guess information on the data:
- IND-CPA (indistinguishability under the chosen plaintext attack) test: the adversary can generate as many ciphertexts as he wants. Then, he chooses two messages m0 and m1 of same length, those messages are encrypted, and one of the ciphertexts is sent back to him. The adversary should not be able to guess which message was used to generate that ciphertext (note that this is just one way of testing for CPA, there are many other schemes, some with stronger properties)
- IND-CCA (indistinguishability under the chosen ciphertext attack): the attacker can get the decryption of arbitrary ciphertexts, but should not, from this, be able to decrypt any other ciphertext.
Here are some common attack types that can be applied to crypto protocols. The list is not exhaustive, and covers only crypto attacks: there are many more ways to attack a system.
- Replay attacks: the attacker has observed some valid (encrypted or not) data going on the wire, and tries to send it again. Obviously, it should not be accepted
- MITM (Man In The Middle): the attacker can observe and modify live data running between two actors of the system. In the worst case, the attacker should not be able to forge valid data, decrypt data, or impersonate one of the users. In the best case, it should be detectable.
- Oracle attack: when an algorithm or protocol has a part that can act as an oracle (can be asked something and give answer, like a server), an attacker could exploit flaws in the algorithm to get useful information on the data (then the oracle is not a random oracle). Timing attacks are part of this type of attack. See also padding oracle attacks, or the recent BREACH attack on TLS.
- Offline attack: the attacker got access to some encrypted data (on the wire, or by accessing a disk somewhere), stored it, and tries to decrypt it for an amount of time
You should now have a better view of the system: what are the parts of the system that need protection, what attacks they must resist, and what properties they should have.
That means we can go to the next part: choosing the tools to implement the solution.
General cryptographic functions
No, we will not choose algorithms right now. That would be too easy😀
We will choose from a list of cryptographic constructions that implement some of the security properties of the system, and combine them to meet all the needed properties:
- Secure Pseudo Random Function: function from spaces K (keys) and X (message) to Y (other message space). The basic definition is that if you choose randomly one of these functions (like choosing randomly a k from K), its output will appear totally random (testable with IND-CPA).
- Pseudo Random Permutation: this is a PRF where X and Y are the same space. It is bijective (every y from Y maps to exactly one x from X, and every y is an output of the function), and there exists an efficient inversion function for it (from Y to X). Example: AES (in ECB, which is unsafe for common use)
- Message Authentication Code: defines a pair of algorithms. One of them takes a key k and a message m and outputs a code c. The other algorithm takes k, m, c and outputs True or False. An attacker should not be able to forge a valid c without knowing k. A PRF could be used to construct a MAC system. A hash function too. Example: HMAC
- Authenticated encryption: an encryption function (with semantic security under the CPA) where the attacker cannot forge new ciphertexts that decrypt correctly. Example: AES-GCM.
- Hash function: collision resistance (cannot find different messages m1, m2 so that H(m1) == H(m2), with different collision levels). Not easily invertible. Usually, they are fast. Example: SHA2.
- Trapdoor function: a function that is easy to compute, for which finding its inverse is hard, unless you have specific information. (secure under IND-CCA). examples: RSA, DSA.
- Zero knowledge proof: a way to prove something to the other party in a communication, without giving her any info, except the proof.
There are a lot of other constructions, depending on your needs, from low level algorithms like the Diffie Hellman key exchange to higher level protocols like OTR. Again, the constructions will depend on the security properties.
Choosing the algorithms
Can we do it now? YES! But there are rules. You must not choose an algorithm because it’s hype or because someone said so in an old book. Basically, you choose algorithms that implement the properties you need (like authenticated encryption), and you choose the parameters of the algorithm (key size, exponent, elliptic curve) depending on the strength you need. Basically, a key size can define how much time encrypted data should remain impossible to decrypt. Those parameters also define the performance of the algorithm. Don’t choose them without consulting experts, or you will face problems similar to those encountered by the projects that used low RSA exponents (it looks good from a performance standpoint, but it introduces very bad security).
Am I done now?
Nope. We have only define some very high level parts. Creating a protocol implies a lot of thoughts on:
- how you establish the communications
- protocol negotiation (version, algorithms, etc)
- key exchange
- nonce usage
- storing sessions
- handling lost connections
- closing the connection
As you can see, designing a protocol involves a lot more than choosing a few algorithms. Note that this was only a very rough overview of what you would need to create a safe system. And we did not even start coding!
So, if you want to build the next privacy protecting system, please talk to experts. They don’t necessarily want to make you feel bad. They just have a lot of formal tools and the experience needed to see what will not work.
I often play with group messaging ideas, and recently, an interesting perspective came to me, about the relation between these messaging systems and the constraints of the CAP theorem.
What is the CAP theorem?
Small theoretical background here, feel free to skip if you already know what it is about
Otherwise known as Brewer’s theorem, indicates that three properties are important in distributed systems:
- Consistency (all nodes see the same data)
- Availability (every request receives a response)
- Partition tolerance (the system still works through network splits or node failure)
The CAP theorem tells us that a distributed cannot have the three properties at the same time. It is not really a “two out of three” like most people tend to say, but more of a compromise you have to make. Some examples:
- in traditional databases systems (with a master-slave model), consistency and availability are high (all nodes can answer with th same data), but partition tolerance is weak because the master is a SPOF.
- in a fully distributed database (no master model), availability is high (all the nodes can answer), partition tolerance is high (a subset of the cluster could act as the whole database), but consistency is weak (data must be replicated to all the relevant nodes, and that can take time, so the nodes may not see the same data at the same time)
- in Bitcoin, the consistency is good (all nodes must agree to the same block chain) and partition tolerance is good (for downloading the block chain), but availability is weak for writing, because a new transaction must first propagates to a large enough set of nodes, then a block must be calculated for the transaction to be stored
As you can see, you can shape those properties depending on how you want your system to behave. Maybe you want fast reads, or fast writes, or very strong replication, etc.
Group messaging constraints
This has always been a challenge. Traditionally, chat systems follow a client-server model, where the server redistributes all the messages. As we saw previously, that is bad against partition problems. The usual solution is to have multiple servers talking with each other, as we can see in IRC or XMPP.
For a fully distributed messaging system (if we forget for a moment all the nasty NAT problems), communication becomes a routing problem: making sure the nodes get all the messages fast enough and in the right order. If you’re building a distributed Twitter, it’s not really a problem, but for an interactive chat system, this becomes really hard. You can try to send your messages directly to all the users in the chat room, but as more people join, sending and receiving all the messages takes more and more time, and so, you sacrifice availability and a bit of consistency (you will not necessarily receive all the messages).
Group messaging crypto
The group messaging problems seemed hairy? Let’s add crypto in the mix, just for fun! What security properties would we want to add to a messaging system?
- Authentication: every user knows with whom he is talking
- Confidentiality: an external observer cannot see the content of a message
- Tampering proof: users can detect when a message has been modified and reject them
- Perfect forward secrecy: compromising one key does not compromise the whole conversation or past conversations
There are others that we could want, but let’s just concentrate on these ones for now. We can separate the messaging in two phases: the discovery, and the transport. The discovery is when nodes begin talking to each other, authenticating each other, establishing session keys, managing key rotation, etc. Note that discovery can happen at any time, as a new node can appear after a long time. The transport is about sending messages safely and verifying messages.
I think we can assume that, once all the nodes have authenticated themselves and agreed on session keys, the transport is the easy part. Whatever the underlying transport system (broadcast, XMPP, SMTP, etc), once you can send, receive and verify messages, everything is easy.
The interesting part is the discovery. That is where the similarity with a distributed system is evident. You want a lot of nodes to start communicating with each other, you want to propagate information to all the nodes (like session keys), you must handle nodes that go up or down, and clusters splitting.
That’s where the CAP theorem is useful to understand the constraints of the system.
Group authentication is an availability and partition problem: if you cannot start the communication until all the nodes have authenticated each other, you are vulnerable to slow or failing nodes.
Tampering proof is a consistency problem: all the nodes must know the same signature keys to agree on whether a message is correct or not.
Confidentiality is a consistency and partition problem: if you must reach consensus on a group-wide session key, you have to wait for all the nodes to get the new key (consistency). That happens a lot if you want perfect forward secrecy, where you must change keys regularly. Moreover, in case of partition, the different groups will agree to different keys, and a conflict will appear once the split is over.
As you can see, a security model can help you choose which tools (cryptographic or not) you will use to ensure the safety of the system, but with the distributed system theory, you will be able to predict and recognize the behaviour of the system.
Let’s see how some more or less known system handle that:
GPG and email
GPG+email is, at its heart, a secure group messaging system. If we analyze its properties, wen can see that it is very good against partition: SMTP handles splits quite well, it can resend messages if they did not pass, or store them for a few days until the next server is up.
For availability, it doesn’t fare very well at high loads if you want to encrypt messages, because you need to encrypt for every host. You cannot take advantage of SMTP’s architecture to reduce the load.
It also has very bad consistency. If you want every node to agree on the keys of each user, you have to do one to one offline meetings between each of the participants. In practice, users make a tradeoff here, so the security assumption is not completely true.
Multi party off the record messaging
There is a paper you can read about MP OTR, which builds on the previous OTR algorithm to provide secure multi party communication. That protocol relies on a heavy setup phase where all the nodes authenticate each other and generate a group encryption key.
This model will fare quite well once consensus has been reached: all the nodes know the ephemeral signature keys and the group encryption key.
Unfortunately, in case of a user joining or leaving the chatroom, the whole shutdown and setup process must happen, making the chatroom unavailable in the meantime.
What about yours?
I see a lot of new projects appearing lately, with the intention to “fix” chat systems or social networks by building a “secure” distributed system. Unfortunately, most of them do not have a serious background in security or distributed systems. The subject of this article, the CAP theorem, is a very small part of the way we think about distributed systems: people have been researching on the subject for years. Similarly, cryptography and protocols have improved a lot lately.
So, if you are building one of these, take your time, forget the hype, read up a bit about the theory, and think about your model before you make your technological choices. Please don’t repeat the worst mistakes.