Crypto experts issue a call to arms to avert the cryptopocalypse

Crypto experts issue a call to arms to avert the cryptopocalypse.

Related article: Math Advances Raise the Prospect of an Internet Security Crisis.

-- Tom

 

Thanks for the post. More of a reason to move to ECC.

 

Yup, another reason I'm glad DNSCrypt went ECC.

ECC adoption should gradually speed up with the push to TLS 1.2

 

ECC is the same as Perfect Forward Secrecy right?
Hopefully TLS 1.2 will be in all browsers soon, and then adoption by sites will be quicker.

 

According to the OpenDNS webpage regarding DNSCrypt:

Regarding "same as" Perfect Forward Secrecy, being the same in design goal does not mean the implementation is the same. Does that mean same performance, or same security Testing the two would need to be done to determine the answers to those questions.

-- Tom

 

Did some searching, they can't be compared, Elliptic Curve cryptography is the method to obtain the goal: Forward Secrecy(AKA Perfect Forward Secrecy, but nothing is perfect: "It's also sometimes called perfect forward secrecy, but, because it is possible to decrypt the communication by breaking the session keys, it's clearly not perfect."
https://community.qualys.com/blogs/...-apache-nginx-and-openssl-for-forward-secrecy
https://community.qualys.com/blogs/securitylabs/2013/06/25/ssl-labs-deploying-forward-secrecy

 

Elliptic curves and forward secrecy are totally different things.

Crypto relies on math problems that nobody knows how to solve way faster than just trying every possible output until we can find one that works.

First, let's get back to simple college algebra:

Computing A^B (^ = power) is easy.
Computing B given A and A^B is easy as well.

Even with huge numbers, there are simple algorithms to compute these very quickly.

Now, instead of an infinite set of numbers, imagine that we only have a finite set of numbers. For example, numbers between 0 and 999. If we start at zero, and keep adding +1, when we reach 999, we "loop": 999 + 1 = 0.
We can still compute additions and subtractions: 999 + 3 = 2 and 2 - 3 = 999.
All the rules you know about these operations still work (A + B = B + A, (A+B)+C=A+(B+C), etc).
A multiplication is a sequence of additions, so if we can add, we can multiply.
A^B is B times A, so if we can multiply, we can compute that, too.
A set of 1000 elements is a pretty bad choice, but if we pick something better (I'll discuss that later), we can divide, compute n-roots, and do pretty much everything that we do with an infinite set of numbers, but with only a finite set of numbers. Let's call these sets and how they work: "groups". Almost all the traditional operations work, and work as expected.

Ok, so we can compute A^B in a group with a finite set of p elements. It's C = (A^B) mod p.

Here's the thing: in such a group, we can't efficiently compute B given C and A. The fact that things are cycling is what makes this problem very hard.
This is known as the discrete logarithm problem. In such a group, factorisation is also known to be a hard problem, again because cycling over a finite set of numbers makes traditional techniques non applicable.

Traditional public-key cryptography rely on these very problems. It's easy and fast to compute the output of a function (compute C), super hard to find one of the parameters given this output and other parameters.

Now, what about elliptic curves?

Imagine a visual representation of the numbers 1, 2, 3, 4, etc. till infinity. Good old group of integers as you learned them when you were a kid. Easy.
Imagine that there are only a finite set of numbers like that. Like, only numbers up to 30. That's even easier, you can just take a ruler. That's what's printed on it.
It's boring, linear, each step has the same visual length.
But hey, you can compute on that. To compute 2 + 3, you can just add the "size" of the segment between 0 and 2, the size of the segment between 0 and 3, put them butt-to-butt, and the total size should match the number "5" on the ruler. You can add, subtract and from there, do a lot of operations just by considering points (locations on the ruler) instead of numbers, and define how to add two points.

Now, imaging that the ruler is not a boring linear thing. It's made of super flexible rubber. You can twist it, make a knot with it, create any shape with it.
If you do that, and you try to add the distance (real, linear distance) between the 0 and the 2, and add that to the distance (real, linear distance) between the 0 and the 3, the result has nothing to do with the real distance between 0 and 5 (as written on the ruler). Like, if you make a knot, the 5 mark and the 15 mark can overlap each other (so, the distance is 0). This is nuts compared to a linear ruler.

Elliptic curves are "rulers" like that. Twisted rules. And you compute using distances between points.

Having points that overlap would actually suck for crypto (we only want one inverse per element), so we use specific shapes: elliptic and hyperelliptic curves. These have some great properties. And they are also chosen so that implementing operations on them (pretty much: computing point coordinates) can be as fast as possible.

Besides the fact that the ruler is not linear any more, crypto primitives work the same way and rely on the same set of hard problems.

Except that, because we use this non-linear curve, these hard problems are believed to be even harder to solve. Much much much harder.

This has a lot of benefits.
Elliptic-curve cryptography is hard to implement correctly, though. Furthermore, a company called Rim (remember these Blackberry phones) holds some nasty patents on elliptic-curve cryptography. Which is one of the main reason it's not widely used yet.

 

Now, on perfect forward secrecy...

The idea is that when A and B want to communicate, they agree on an ephemeral shared key, exchange data using this key, and poof, the key is not used any more, it doesn't have to be stored anywhere. One way to do that is to use the Diffie-Hellman method. This is basically about computing A^(B^C) and (A^B)^C, which is easy to compute, but requires solving the discrete logarithm problem to reverse. This can be computed over an elliptic curve, but it's not required, although it's definitely a good idea to make this more secure while using small keys.

It doesn't prevent man-in-the middle attacks. If the NSA has the secret keys, they can still decrypt and hijack everything *during the communication*.

But after the communication is over, even if they recorded it (as an encrypted stream of data), and they have the secret keys, it doesn't help, because they don't know what the ephemeral shared key was.

So, forward secrecy doesn't need elliptic curves. But you may have read that a good choice to do that when using SSL is to use something called ECDH: this is just the Diffie-Hellman key exchange using elliptic curves. Not the only choice in theory but the best choice in practive, especially since it's actually implemented in web browsers.

 

On the cryptocalypse.

Don't panic.

Remember that set of 1000 elements that we cycled over when doing arithmetic on it?

We use groups of p^n elements, so that all operations work. In particular, each element has an inverse. p is a prime number, n is a positive integer.

The breakthrough that made people describe a forthcoming "cryptocalypse" is the fact that factorisation can be done quickly when p is small. Only when p is very small.

This is a great advance in number theory, but RSA is not broken because of that.

What is actually used in modern cryptography is prime fields, i.e n = 1 and p is large.

Not a reason not to slowly shift to elliptic curve crypto, but not a reason to panic about a forthcoming cryptocalypse either.

 

Just to note that RIM (now renamed Blackberry) may put itself up for sale, so the question is whom will buy up those ECC patents, eh?

Reference: Blackberry forms committee to explore possible sale.

-- Tom

 

The following article has some interesting information on the status of ECC patents should the cryptopocalypse occur:

Math Advances Raise the Prospect of an Internet Security Crisis.

-- Tom

 

Schneier on Security: The Cryptopocalypse.

-- Tom

 

Exactly.

Just like the "Encryption is less secure than we thought" nonsense, it's basically just "non-news" overblown into a mountain: