[cabfpub] Quantum Computing is now a concern.

[Fotis Loukos]

On 07/12/2016 07:30 PM, Adam Langley wrote:
> On Tue, Jul 12, 2016 at 7:57 AM, philliph at comodo.com
> <mailto:philliph at comodo.com> <philliph at comodo.com
> <mailto: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.)
> 

Hello,
I have expressed also my concerns in the past on using small ECC keys
due to the small number of qubits required to break them using a quantum
computer. I also agree that stateless signatures should be preferred if
we're looking into creating a system that will last for decades (unless
of course a new quantum algorithm that breaks preimage resistance is
created).

However, I believe that the most important issue, even more important
than software support, is choosing the correct parameters, and this
cannot be done as part of CA/B Forum.

> 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.

I will have to disagree here. I believe that most ideas for adding
turing complete languages in data resulted in zillions of security
vulnerabilities in VMs and parsers. You can find many examples out
there, just by searching CVEs.

Regards,
Fotis

> 
> 
> Cheers
> 
> AGL
> 
> 
> _______________________________________________
> Public mailing list
> Public at cabforum.org
> https://cabforum.org/mailman/listinfo/public
>