Re: [CFRG] NSA vs. hybrid

[Soatok Dreamseeker <[e-mail]>]

Hi Dan,

On Sat, Nov 13, 2021, 8:54 AM D. J. Bernstein <[e-mail]> wrote:

> Blumenthal, Uri - 0553 - MITLL writes:
> > Using Dan's terminology: you want P chain of trust - ask for it, you
> > want Q chain of trust - request that. In the unlikely case of wanting
> > both - get both, AFAICT, the overhead would be small.
>
> Google's CECPQ1 experiment and the Google-Cloudflare CECPQ2 experiment
> both combined P (ECC) with Q (the post-quantum option). The motivation
> was clearly stated, and applies verbatim to signatures too:
>
>    The post-quantum algorithm might turn out to be breakable even with
>    today's computers, in which case the elliptic-curve algorithm will
>    still provide the best security that today’s technology can offer.
>    Alternatively, if the post-quantum algorithm turns out to be secure
>    then it'll protect the connection even against a future, quantum
>    computer.
>
> The post-quantum situation since then hasn't become _less_ scary. We've
> seen almost every NISTPQC submission losing security, often so much as
> to be declared broken. Exciting new attacks are appearing, and the study
> of post-quantum implementation failures is in its infancy. Why would it
> be unlikely for people to want to combine post-quantum crypto with ECC?
>
> If the answer is that NSA's declaration of confidence is influential:
> This is where it would be valuable for CFRG to advise ECC integration
> into all post-quantum deployments for the foreseeable future.
>
> > And you expect P+Q certificates to be validated correctly?
>
> I agree that certificate validation is a mess. This is why, regarding
> the mechanisms for doing both P and Q, I'd expect that having a new
> signature system _internally_ combining P+Q is safer than changing the
> certificate-validation logic. I'm puzzled by NSA's unexplained
> statements to the contrary. See also Mike's message.
>
> > In practice, large PKI that have multiple intermediary CAs, will
> > likely have separate CAs for P and Q certs.
>
> Why? If a CA is interested in offering Q certificates, why would it not
> want to provide
>
>    * the extra security value of offering P+Q certificates (which are
>      practically the same size as Q certificates) plus
>
>    * the extra compatibility value of offering P certificates?
>
> For the RSA->ECC upgrade there's (1) a stable ECC security picture and
> (2) clear performance reasons to not have the ECC signatures accompanied
> by RSA signatures. For the post-quantum upgrade, the story is reversed:
> the post-quantum security picture isn't stable, and keeping ECC as a
> security layer has low cost.
>
> ---Dan
>
> _______________________________________________
> CFRG mailing list
> [e-mail]
> https://www.irtf.org/mailman/listinfo/cfrg


Coming from the world outside of academic cryptography, I expect more logic
bugs from software trying to validate separate P-chains and Q-chains than
with an additional, unified, P+Q signature scheme.

Additionally, why can't we define a unified mode that generates both
keypairs from a single random secret? i.e.

primary_seed := randombytes_buf(64) // store this

ed25519_seed := hash_sha512256(PREFIX_PREQUANTUM || primary_seed)

pq_seed := hash_sha512256(PREFIX_POSTQUANTUM || primary_seed)

ed25519_keypair := crypto_sign_seed_keypair(ed25519_seed)

pq_keypair := pqcrypto_sign_seed_keypair(pq_seed)

This turns a 512-bit secret into two distinct 256-bit seeds. For ed25519,
this can be the unclamped sk. For PQ, it can be a seed for a DRBG used to
generate the (sk, pk) pair.

Even if you can break ECC and recover the secret key, you would also need
to be able to preimage attack SHA512 from only half of its output. The
input being 512 bits is chosen to have a birthday bound at the 256-bit
security level.

Why would we do this? Because specifying a higher-level composite protocol
for signatures makes it less likely that implementors will get it wrong.

>
>