[cabfpub] Quantum Computing is now a concern.

Adam Langley agl at google.com
Tue Jul 12 16:30:53 UTC 2016


On Tue, Jul 12, 2016 at 7:57 AM, philliph at comodo.com <philliph at comodo.com>
wrote:

> It is thus imperative that the industry develop a strategy to address the
> impending risk of Quantum Cryptanalysis and in particular look at
> strategies for deploying Quantum Resistant Cryptography (QRC).
>
> Right now, we do not have any public key algorithm that is QR. Symmetric
> algorithms have their exponential work factors halved. So WF128 becomes a
> breakable WF64. We need to go to 256 keys for acceptable security.
>
> There is active research on QRC but there isn’t an acceptable public key
> algorithm right now and even if one is found it is quite possible that
> patent encumbrances will prevent it being deployed proactively.
>
> What we do have is Lamport Signatures and those are QR but have the severe
> disadvantage that they can only be used once.
>
> So as a countermeasure, it would behoove us to begin distribution of
> ‘emergency roots’ that make use of Lamport Signatures. The best way to do
> this would be to add a pair of SHA2-512 and SHA3-512 digests to each root
> cert. These would be the fingerprints of a Merkle Tree of Lamport Public
> Signature keys. That way we would have trust roots predistributed that
> would allow us to bootstrap a new trust system should that prove necessary.
>
> Browser providers and CAs would both need to deploy the emergency roots.
> Browser providers would also need to develop strategies for making use of
> them. They would need to be able to use their own emergency root to
> validate updates to their code distribution infrastructure.
>

I agree that we do not have a great post-quantum, public-key signature
scheme available yet and that hash-based signatures are a good idea in some
contexts.

Did you envision that software would start supporting these signatures
immediately? If so, then any certificate chains that take advantage of that
would have to be hash-based from top to bottom because that's the only PQ
primitive that would be supported. You've also specified a stateful
signature scheme were doing things like moving a CA key from one HSM to
another, or installing a leaf certificate on multiple servers, compromises
the private key. (And that's assuming that there exist any HSMs that
support hash-based signatures, which I don't think is the case.)

If software isn't going to support it immediately then I don't see the
point in putting these hashes in root certificates. A software update to
verifiers would be needed and, if you can do that, then you can add
hash-based roots at the same time anyway.

So I think that PKI roots are the wrong place to be focusing. It's
software-update keys that are really the roots of trust, and those keys
should be seriously looking at using hash-based signatures, even today.
But, stateful
<https://tools.ietf.org/html/draft-irtf-cfrg-xmss-hash-based-signatures-06>
signatures
are very fragile, so stateless <https://sphincs.cr.yp.to/> ones are to be
much prefered. (That's not to say that stateful schemes are useless
because, at the very least, they generally form the core of stateless
schemes.)

For software that cannot be updated we would want to start the process of
rolling something out ASAP but we have a problem: stateless hash-based
signatures work, but at ~40KB per signature, it's not clear that they would
be viable for a full chain. So if you really want to be deploying software
today that's going to work for decades, you have to start thinking about
certificates that specify their own verification algorithm as code for a VM
or something.


Cheers

AGL
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.cabforum.org/pipermail/public/attachments/20160712/f05851a6/attachment-0003.html>


More information about the Public mailing list