Cryptography

[Mikey]

Cryptography is the practice and study of techniques for secure communication in the presence of third parties called adversaries. In recent years, quality cryptography has become widely available on the Internet due to modern web browsers and email clients. Many people use and benefit from cryptography in some way or another, but few are even aware of it, or know how it works.

This thread is for general discussion of cryptography and sharing of news articles from this sector.

 

[Mikey]

In this first post I want to dispel the myth that all cryptography can be broken in principle.

With the Snowden Affair exposing government surveillance programs, a myth was born, stating (more or less) that government agencies are all-powerful and are able to read all encrypted messages or forge cryptographic signatures on the internet. For this reason, laypeople sometimes think that cryptography is breakable in principle. However:

Modern cryptography is heavily based on mathematical theory and computer science practice; cryptographic algorithms are designed around computational hardness assumptions, making such algorithms hard to break in practice by any adversary. It is theoretically possible to break such a system, but it is infeasible to do so by any known practical means.

Computational hardness has physical implications. Computation requires energy input, and theoretical lower limits for computation have been established: See Landauer's principle and the Margolus–Levitin theorem for quantum computing. So, by increasing the difficulty of the computation, one increases the minimum energy required (electricity, heat), which may put the solution to the problem out of reach for any earthly agency.

But there is one cryptographic method that has been mathematically proven to be completely secure:

There exist information-theoretically secure schemes that provably cannot be broken even with unlimited computing power—an example is the one-time pad.

The One-time pad...

... is an encryption technique that cannot be cracked. [...] If the key is truly random, is at least as long as the plaintext, is never reused in whole or in part, and is kept completely secret, then the resulting ciphertext will be impossible to decrypt or break.

The One-time pad is not very practical because the key has to be as long as the message, and the key has to be exchanged in a secure way (e.g. from person to person in a code book, which has traditionally been done in warfare).

Different cryptographic algorithms have different properties. Some algorithms are mathematically/theoretically impossible to break (and "mathematics can't be bribed"), some are 'only' practically impossible to break, and some are of low quality that can be broken with reasonable effort by someone with enough resources.

 

[Ellipse]

I think that the way agencies deal with this "annoyance" is to corrupt the process at the root.

- By stealing keys (the Gemalto affair https://en.wikipedia.org/wiki/Gemalto)
- By buying, via proxy, companies producing hardware having to do with encryption technologies
- By defining the standard widely used for encryption
- By installing backdoors
- By keeping the control over available OS (Windows, Android, iOS) so they can access data before the encryption process, if needed. I don't know for Linux.

The last resort being the use of quantum computers to decypher.

So the One-time pad technique is perhaps useful if a lot of others precautions had been taken.

 

[Mikey]

The One-time pad (mentioned above) just serves to illustrate that some cryptography cannot be broken even by an adversary with infinite computing power. But it is not practical to use.

The so-called public-key cryptography is much easier in practice to implement, but it is still extremely hard to break in practice ("extremely hard" here means all of the world's computing power concentrated for thousands of years). If you use https:// anywhere on the internet, your browser is using this method for you without you even noticing.

The problem is as follows:

Alice and Bob, who have never met before, meet with each other for the first time, while Eve is standing right next to them and listening to their entire conversation. Thanks to special mathematical properties of some functions, Alice and Bob can establish a shared secret with each other, which they can then use the encrypt all their later conversations, even though Eve is listening to them all the time. This sounds like black magic, but it is possible mathematically.

The following video explains how it works. It is probably the simplest basic illustration of the algorithm. It uses the analogy that mixing of colored paint is very easy, while complete reversal of the mixing of colored paint (to find out the exact colors used) is extremely difficult/expensive:

http://<iframe width="560" height="...vk" frameborder="0" allowfullscreen></iframe>

 

[Mikey]

Here is a very nice and short (just 3 minutes) hands-on demonstration of how public-key cryptography works, illustrated by a physical box, locks, and keys:

http://<iframe width="560" height="...X4" frameborder="0" allowfullscreen></iframe>

 

[Mikey]

Computational hardness has physical implications. Computation requires energy input, and theoretical lower limits for computation have been established: See Landauer's principle and the Margolus–Levitin theorem for quantum computing. So, by increasing the difficulty of the computation, one increases the minimum energy required (electricity, heat), which may put the solution to the problem out of reach for any earthly agency.

This video illustrates nicely why directly breaking (proper) cryptography is "out of reach for any earthly agency":

http://<iframe width="560" height="...nY" frameborder="0" allowfullscreen></iframe>