Theoretical definitions for crypto wannabes

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 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:

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:

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.

Common attacks

Security properties

Here are some security properties that will be useful when you will try to choose algorithms later:

Security tests

those properties can be tested by creating a "game", where the attacker tries to guess information on the data:

Attack patterns

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.

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 :D

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:

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:

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.