[Cryptography] Post Quantum Crypto

[Philipp Gühring]

Hi,

2 years ago, I stumbled across news from D-Wave and took a few days to
investigate their technology, 
quantum computers in general and their specific impact on cryptography, on
theory and on practice.
I came to the conclusion that it´s highly likely that quantum computers
will become a serious threat for ECC, RSA, and DH.

Reasoning: There were 2 different open questions:
Does it work at all that quantum computers can break crypto, and is it
possible to scale it up enough?
>From my point of view, the possibility was demonstrated by IBM in 2001,
and the scalability was demonstrated by D-Wave in the recent years.
Combining both possibility and scalability into one product is a third
challenge, but I do not see any real blockers why this should be
impossible anymore.

It seems that some people now agree with my results from two years ago.
  
The next question was about the timeframe. I expected a high likelyhood
for Quantum computer being able to attack within 5 years.
  
Then the next question was about the impact. It seemed to me that quantum
computers will likely destroy ECC first (because it´s keys are far too
short), 
Diffie-Hellman and RSA later on.
But the exact points of time when the necessary inventions to break them
will come hard to predict, especially for the future ;-)
So Signing, PublicKey-Encryption and Key-Agreement are all affected and we
need replacements.

So I started to look around for replacements algorithms. 
What I found was a handful of academic algorithms for signing and
encryption, where most of them were unsuitable for practical use. 
(unrecyclable One-time-signatures, too large keys, too slow, ...)
The most promising algorithm I found was NTRU, which had variants for
Signing and Encryption (NTRUencrypt + PassSign are the current ones).
(I will write NTRU instead of NTRUencrypt+PassSign from now on, since most
of the things also apply to PassSign)
NTRU has a long history of repeatedly getting broken theoretically and
getting improved/fixed theoretically. 
So it is properly maintained, algorithm-wise for far more than a decade.
I took some time to audit the reference implementation, dust it off, make
sure that it compiles again and works according to the specs, found a few
minor bugs and sent pull requests that were happily accepted.
https://github.com/NTRUOpenSourceProject/ntru-crypto
But I think it still needs a lot of love and care for engineering it into
an integrated practical solution that we can use the large-scale internet
to rely on.

But I couldn´t find any suggestions for Post-Quantum Key-Agreement algorithms.

So I thought about the requirements Diffie-Hellman fulfills, found an
inspiring post on the crypto mailinglist and developed a concept for a
replacement algorithm, based in a modular fashion on an encryption
primitive and something like a hash.
I named it NTRU Key Exchange, but later on I realized that it should also
work with any other encryption primitives underneath.

After I wrote it down
(http://www2.futureware.at/PostQuantum/NTRU%20Key%20Exchange.pptx), I
searched again and suddendly I found a new paper about another concept for
a Post-Quantum Diffie-Hellman replacement, which was also based on NTRU
and is called NTRU KE, 
which is similar protocol-wise, but far more complex and it required more
parameters that need to be defined.

So now I had proposals for Signing, Encryption and Key-Aggreement, all the
necessary primitives for a whole crypto-stack, and I turned my attention
to the crypto markets.

I quickly thought through the OpenPGP and the Bitcoin market, and came to
the conclusion that a migration should be easy for those market, and does
not need much design effort. 
Implement new algorithms, deploy them, create new keys, migrate from the
old keys to the new keys.

But for SSL/TLS I found a bigger problem:
All the things around it are heavily designed for having just one single
public key algorithm, 
and it does not contain any upgrading, transitioning or migration
mechanisms for the public key algorithms.
Without those, we have a chicken-and-egg-and-henn problem between the
clients, the servers, and the certificate authorities.
Practically, the servers would have to wait for deploying new Post-Quantum
certificates until their last client at the othere end of the internete
has finally implemented the new algorithms.
On the large public internet, for larger websites and systems this means
something around 10 years of delay, because some users only upgrade when
the hardware breaks down (embedded systems), 
and the supply chain from algorithm developers to cryptostack developers
to crypto applications to distributions to distributors to end-users takes
it´s time.

So the big problem that I saw is that quantum computers will likely
destroy our crypto within 5 years, and we likely need 10 years to migrate
to a new solution. Ouch.

The other problem is that sophisticated attacks by the crypto analyst
community on new Post-Quantum algorithms will only start to happen when
they are widely used.
(Could you guys and girls be a bit more pro-active please?)
But we want to know now which of those algorithms are good to be widely
deployed.

So I started to think about how we can do a large-scale migration of the
SSL universe.

My idea was that I wanted to make sure that by adding Post-Quantum
algorithms we do not lower the security level below the Pre-Quantum level
we had with RSA-only certificates.
So if in one year someone invents a new attack against NTRU, I don´t want
to have downgraded the security level like we did with reintroducing RC4
after the BEAST attack (if I remember correctly).
So the idea is to have both RSA+NTRU for the forseeable future(e.g. 10
years), until we decide that RSA really does not help anymore and NTRU has
been vetted enough that we can trust it alone as our only public key
algorithm.
Then we could drop RSA, and switch to NTRU-only.
(I am talking only about NTRU here. If some other algorithm comes up that
prooves to be better, I don´t mind replacing NTRU with it. NTRU just looks
like the most promising candidate from a practical perspective to me)
And I want opportunistic Post-Quantum protection, so as soon as both the
browser(client) and the server support the new PostQuantum algorithms,
they should be protected from Quantum attacks.
To achieve that, we either need 2 different certificates, or one
certificate that contains both RSA and NTRU.

I believed that handling 2 different certificates will be too complex
(errorprone) and therefore too costly for the users. 
And for commercial CAs you would have to buy 2 certificates instead of one... 
And then we would have to have twice as many root certificates, ... and
most root certificate list vendors already have limits on the number of
root certificates per certificate authority (3 if I remember correctly).
It´s already hard for users to generate 1 keypair, get a certificate for
it, install the certificate correctly, asking them to do that twice will
make it less likely for them to succeed.

So I was looking for a solution to integrate both RSA and NTRU into a
single certificate.

I started by developing a concept to integrate a second key and signature
into a X.509 certificate in a downwards compatible way, called "Additional
Public Key" APK.
http://www2.futureware.at/PostQuantum/AdditionalKeyDraft.txt

So old browsers/clients still see a normal valid RSA certificate, and can
ignore the NTRU addons.
And new browsers have a RSA+NTRU certificate, and can check both. So we
don´t loose security and we add Quantum Protection.

Then for the CA (and Sub-CA) certificates, I developed a concept to also
have an additional signature in the certificate.
So now we can have a complete certificate chain, where every link in the
chain has double strength for new systems and downwards compatibility for
existing systems.

So with these concepts we can opportunistically activate Post-Quantum
protection for SSL/TLS.

But there are still a lot of things that need to be done.

We need TLS ciphersuites that make use of the Additional keys. 
I already have high-level ideas how those ciphersuites should look like,
but I haven´t figured out the details and implemented them yet.
For example we need a PKCS#12 extension so that you can backup and
transfer your keys.
(We need to enhance the PKCS#11 API,...)
And we will have to figure out a lot of other details, bits and blobs, and
engineer a good solution for it all.
I think that we will need 2 of the big SSL/TLS stack vendors to join this
project and commit themselves to get it prototyped

Unfortunately about a year ago I got distracted from this project, and
didn´t pursued it further since then, partly because I had the feeling
that I couldn´t convince others about the importance of this project back
then.
(And recently one of them came back to me and asked me to publish about
all my experience from 2 years ago now)

These are the documents and presentations I was working on back then:
http://www2.futureware.at/PostQuantum/
I am thinking about preserving them at that location for historical
reasons, and creating new working copies elsewhere if I decide to continue
with this project.

Recently the NTRU guys developed a new TLS extension concept to start
bring NTRUencrypt into TLS in a opportunistic way (in with RSA), which is
a good first step on the long way to fully protect SSL/TLS:
https://tools.ietf.org/html/draft-whyte-qsh-tls13-01
https://tools.ietf.org/html/draft-whyte-qsh-tls12-00
(It heard that the first one got implemented in WolfSSL, if anyone wants
to play around with it)

I think a lot of help is needed to migrate from Pre-Quantum to Post-Quantum.
If you have a clue about lattice maths, number theory, ... then please
take a deep look at NTRU, PassSign and the other PostQuantum algorithms on
the table and my NTRU Key Exchange proposal, try to find further holes in
it, search the weaknesses that have not been thought of yet. 
And validate NTRU and the others in a structured way against all the
attacks that were used against other public key cryptography algorithms.
And please try to attack it in a completely new way.
If you are good in auditing sourcecode, please audit the reference
implementations and other implementations (Tim Buktu´s).
If you know about implementation attacks side-channel attacks, then please
help to secure the PostQuantum algorithms against them.
If you are good in testing, please setup a big Post-Quantum crypto
interoperability testing lab.
If you have experience in developing Wireshark plugins, please develop
Wireshark decoders for the NTRU certificates and the new ciphersuites.
If you run a certificate authority, please join the existing projects to
develop Post-Quantum mechanisms and provide your knowledge and experiences
about the demands and requirements from the CA point of view. 
(2 years ago I had the feeling that the academic world did not understand
those market forces very well, and designed systems that were not
compatible with the processes in the industry)

Another thing I am missing is a Post-Quantum SRP replacement. If anyone
has any ideas how to achieve that, please let me/us know.

If you know any other Post-Quantum algorithms that should be considered,
please let me know. We should have at least one alternative to NTRU in
preparation in case it fails unexpectedly.

If you find a way to proof that NTRU is safe against Quantum computers,
please publish it. (It´s currently assumed, but not proven yet)
If you find a way to proof that NTRU will be broken by Quantum computers,
please publish it as well.

If you think that I should start again to invest my time into this
project, please let me know. (Sometimes I need some motivation ;-)

I hope I didn´t forget too much, perhaps you will find some more
information in the papers and presentations I wrote (link above).

I would like to thank a number of people for their discussions, ideas,
suggestions.

Best regards,
Philipp

PS: And please don´t forget the most important point regarding crypto: You
can it, but when you break it, you have to fix it!