Hey! I'm David, the author of the Real-World Cryptography book. I'm a crypto engineer at O(1) Labs on the Mina cryptocurrency, previously I was the security lead for Diem (formerly Libra) at Novi (Facebook), and a security consultant for the Cryptography Services of NCC Group. This is my blog about cryptography and security and other related topics that I find interesting.

I made a simple script to check for your DH modulus. Is it long enough? Is it a safe prime?
I thought some non-cryptographers could benefit from such a tool, since usually all I have to do is fire up Sage and run some tests, but if you don't have Sage this can be tricky and annoying so...

As we all know, some things are happening in the quantum computing world. Some are saying it will never work, some are saying it will but that it will take time until large enough quantum computers could break today's crypto.

So reading this paragraph taken from the NIST document, it can make sense on why we would want to move today to post-quantum crypto:

Historically, it has taken almost 20 years to deploy our modern public key cryptography infrastructure. It will take significant effort to ensure a smooth and secure migration from the current widely used cryptosystems to their quantum computing resistant counterparts. Therefore, regardless of whether we can estimate the exact time of the arrival of the quantum computing era, we must begin now to prepare our information security systems to be able to resist quantum computing.

Let's see where is this number coming from. SSL/TLS, its protocol or its implementation, its coverage or its efficiency, has been a huge mess so far:

In 2009, 7 years ago, moxie introduced SSLStrip at Blackhat, a technique to render https completely useless without preloaded HSTS.

It's only in 2013, 3 years ago, that facebook finally made the whole app https-only just blows my mind. And that's not thinking of the myriad of companies, commerce, banks and other websites that were all accessible through http back then.

Nowdays most websites are still vulnerable to moxie's 2009 attack. Think about it, TLS is supposed to protect the communications against a passive and an active attacker on the network. In the passive case, I think it succeeded (in most cases). In the active case? Even HSTS or HPKP can still be somehow circumvented. Only browsers are fully capable of protecting us nowadays.

And this is ignoring all the horrible implementations flaws like heartbleed, the broken cert validations of browsers, the broken basicConstraints of most CAs...

1996, 20 years ago, researches recommend to switch from md5 to sha1 because of recent advances.

2013, 17 years after the recommendation, Apple finally removes its support for MD5 in certificates.

We're still in the middle of deprecating sha1, and it's a mess.

(there's also a graphical timeline made by ange: here)

Or what about the deprecation of DES? Or RC4? Or 1024 bit DH? ..

To come back to the NIST's report, here's a nice table of the impact of quantum computing on today's algorithms:

sums up pretty well what djb wrote:

Imagine that it's fifteen years from now. Somebody announces that he's built a large quantum computer. RSA is dead. DSA is dead. Elliptic curves, hyperelliptic curves, class groups, whatever, dead, dead, dead.

Contrarily to the european initiative PQCrypto, they seem to imply that they will recommend lattice-based crypto whenever their new suite B will be done. I find hard to trust any system's security proof that rely on lattice's theorical bounds because as it is known with LLL, BKZ and others: practical results are way better than these theorical limits. I don't know much about lattice crypto though, and I would you out to this paper in my to read list: Lattice-based crypto for beginners.

They agree on Hash-based signatures (which are explained in a 4 posts series on my blog), which is timy because a new version of the RFC draft for XMSS has came out, which might be the most polished hash-based signature system out there (although it is stateful unlike SPHINCS).

The paper ends on these wise words that explains how security estimation works (and has always worked):

We note that none of the above proposals have been shown to guarantee security against all quantum attacks. A new quantum algorithm may be discovered which breaks some of these schemes. However, this is similar to the state today. Although most public-key cryptosystems come with a security proof, these proofs are based on unproven assumptions. Thus the lack of known attacks is used to justify the security of public-key cryptography currently in use.

To talk about quantum computing advances, I don't know much about it but here are some notes:

Shorâ€™s algorithm (the one that breaks everything) was born on 1994.

Late 1990s, error correcting codes and threshold theorems for quantum computing. Quantum computing might be possible?

2011, "the world's first commercially available quantum computer" is released by D-Wave. I believe this angered many people because this wasn't really quantum computing.

2015, Google and NASA have D-wave computers.

To finish this blogpost, a few things I remember from last month Real World Crypto conference:

On day 3, str4d announced that they wanted to move to post-quantum algorithms for i2p (a thing like Tor). People did not receive that as a good news. I heard people quoting djb's "crypto should be boring" line.

There is definitely a skepticism in the crypto world about quantum computing, as there is a gold rush into designing new post-quantum crypto.

I have mix feelings about the UI of Signal, but watching these two videos from Moxie at different periods of TLS' life, I now have a brand new admiration for the person.

The two videos are here:

In both of them, he start talking about his sslsnif: a great tool that you can find here, written in C++ and that allows you to serve clients fallacious certs taking advantage of browsers vulnerabilities (such as not checking for basic constraints fields in the certificate chain, stop reading subject names after null bytes, etc...)

Another tools that he released, coded in python, is sslstrip. The thing takes advantage of the fact that almost no one types https:// in the address bar when navigating to a website directly. A man-in-the-middle attacker can stop the redirection to https and serve the entire website either through http or through another https website which url looks similar to the victim's website (thanks to some unicode to make it look like victimwebsite.com/something/?yourwebsite.com where yourwebsite.com is the real website being visited).

https' only purpose is to defend against man-in-the-middle attacker. Because of sslstrip, any active attacker on the network can render https completely useless. Security measures to prevent that, that I can think of, are HSTS headers, preloaded HSTS (see chrome's one) and HPKP (see Tim Taubert's blogpost.)

Both tools needs arpspoof to create the man-in-the-middle position. I've discovered another tool that seems to combine all of these tools in one (but I'm not really sure what's the difference here): bettercap. It looks good also.

Other tools I've discovered, that verify how the client's handle certificate verification: one is developed by some coworker and is called tlspretense, the other one is called x509test and seem to be pretty popular too. I have no idea how both these tools perform, I guess I will check that next time I to.

While some people would tell you to use pre-defined Diffie-Hellman parameters (rfc3526, rfc5114) so as not to mess something up during the generation (hum humsocat), others would tell you "hey, look at what happened with logjam and their hardcoded DH params!" and will point you to openssl dhparam to generate your own customized parameters.

But how does it really work? The high level code is less than 450 lines long. It's basically taking several stuff into consideration ("do you want to use 2 or 5 as a generator? No? Let's use 2 anyway!") and then using some DH_generate_parameters() function that will set up everything.

Inside of that function relies probable_prime_dh_safe() that will look for a particular kind of prime as the DH modulus: a safe prime.

A safe prime looks like this: \(2p + 1\) with \(p\) a prime as well.

Actually, we can also say that the function looks for a Sophie Germain prime, a prime \(p\) such that \(2p+1\) is also prime.

Like that you know =), safe primes are not the same as Sophie Germain prime, but they are closely related.

(Not to mix up with strong prime as well, which are just primes that have some properties.)

Another important thing: the function returns a safe probable primes. That is a function that has not been mathematically proven to be a prime (but is close enough).

To do that, first a random number is generated. Then a test called the Miller-Rabin test is applied to the random number a number of time. The more you run the test and the more certainty you get that it is a prime, if the test ever fail you know for sure that the number is not a prime (so a composite) and you need to regenerate a new random number and start again with the tests.

How many times should you apply this test? Enough time so that if everyone tried to generate primes every second for the lifespan of earth we would still have low chances to find a false positive (a composite number passing X tests of Miller-Rabin). The numbers used in OpenSSL come from the table 4.4 in the Handbook of Applied Cryptography.

(To make the test faster a bunch of small primes are first tested as divisors, then some trial divisions follow.)

From a high level, here's what a PRNG is supposed to look like:

you start with a seed (if you re-use the same seed you will obtain the same random numbers), you initialize it into a state. Then, every time you want to obtain a random number, you transform that state with a one-way function \(g\). This is because you don't want people to find out the state out of the random output.

You want another random number? You first transform the state with a one way function \(f\): this is because you don't want people who found out the state to be able to retrieve past states (forward secrecy). And then you use your function \(g\) again to output a random number.

Mersenne Twister (MT) is like that, except:

your first state is not used to output any random numbers

a state allows you to output not only one, but 624 random numbers (although this could be thought as one big random number)

the \(g\) function is reversible, it's not a one-way function, so MT it is not a cryptographically secure PRNG.

With more details, here's what MT looks like:

the \(f\) function is called "twist", the \(g\) function is called "temper". You can find out how each functions work by looking at the working code on the wikipedia page of MT.

The socat thingy created some interest in my brain and I'm now wondering how to build a NOBUS (Nobody But Us) backdoor inside Diffie-Hellman and how to reverse it if it's not a proper NOBUS.

Ways to do that is to imagine how the DH non-prime modulus could have been generated to allow for a backdoor. For it to be a NOBUS it should not easily be factorable, but for it to allow a Pohlig-Hellman attack it must have a B-smooth order with B small enough for the adversary to compute the discrete log in a subgroup of order B.

If you go on the github repository you will see an already working proof of concept that explains each of the steps (generation, attack)

This proof of concept underlines one of the ways the malicious committer could have generated the non-prime modulus \(p = p_1 p_2\) with both \(p_i\) primes such that \(p_i - 1\) are smooth. The attack works, but I'm thinking about ways of reversing such a non-prime modulus that would disable the NOBUS property of the backdoor. Spoiler alert: Pollard's p-1 factorization algorithm.

Anyway, if you're interested in contributing to that research, or if you have any comments that could be useful, please shoot me a message =)