Revising FAQ questions on hybrid modes

[Moody, Dustin (Fed)]

NIST has received a lot of questions about “hybrid modes” which combine a post-quantum cryptographic algorithm with an algorithms currently standardized by NIST.  Our FAQ questions and answers relating to this topic are available at:

https://csrc.nist.gov/Projects/post-quantum-cryptography/faqs

 

We are considering a revision of these questions and answers, and wanted to solicit feedback from the community.  The revised text is below.  Please let us know of any comments or suggestions, either here on the pqc-forum or by contacting us at pqc-co...@nist.gov. 

 

Dustin Moody

NIST PQC team

 

Is it possible for a hybrid key-establishment mode to be validated according to FIPS 140?

A hybrid key establishment mode is defined here to be a key-establishment mechanism using two or more cryptographic components. Assume that one of the components of the hybrid mode is a NIST-approved cryptographic scheme - for example, a discrete-logarithm based scheme as specified in NIST SP 800-56A or an integer-factorization scheme as specified in SP 800-56B and the other components can be post-quantum cryptography schemes. A hybrid key-establishment scheme derives keying material from the multiple key-establishment schemes in such a way that the derived keys remain secure if at least one of the key-establishment schemes is secure.

 

Assume that the value Z is a shared secret generated within a NIST-approved cryptographic scheme, and a value T is generated or distributed through other scheme(s), for example, a key as output by a KEM. The following are the different ways to insert the value T in the key-derivation procedure producing a hybrid mode that is permitted by current NIST standards, a.k.a. standards developed for the "pre-quantum" period, in FIPS mode:

1. For a one-step key-derivation method as specified in SP 800-56C, T may be included in the (optional) FixedInfo field, for example as part of the SuppPrivInfo described in SP 800-56A and SP 800-56B. 
2. In any of the key derivation methods specified, one-step or extraction-then-expansion, in SP 800-56C, the value T may be included in the salt field.

Additionally, NIST plans to incorporate a cleaner, and therefore preferable, hybrid key establishment construction in a future revision of SP 800-56C:

3. In any of the key derivation methods specified in SP 800 - 56C, the revision would permit a concatenation of Z and T, that is, Z ← Z||T  to be used as the “shared secret”. This would require the insertion of T into the coding for the scheme and the FIPS 140 validation code may need to be modified.

Is it possible for a dual signature to be validated according to FIPS 140?

A dual signature consists of two (or more) signatures. Assume that one signature is generated with a NIST-approved signature scheme as specified in FIPS 186. Another signature can be generated using a different scheme, e.g., one that is not currently specified in NIST standards. The dual signature is valid if and only if both (or all) signatures are valid.  FIPS 140 validation can only validate a part of the dual signature that is currently approved by NIST.

The format of a dual signature is out of scope for FIPS 140 validation. It is up to the application to specify how to parse signatures and verify them separately. 

Are a hybrid key-establishment mode and dual signatures recommended by NIST as a long-term solution?

No. NIST continues to believe that the long-term solution to the threat of quantum computers or any other unknown attacks is to provide strong standards for post-quantum public key cryptography through the on-going process. A decision needs to be made for each specific application as to whether it can afford the implementation cost and performance reduction of a hybrid mode for key establishment or the use of dual signatures. However, NIST will accommodate the use of a hybrid key-establishment mode and dual signatures in FIPS 140 validation when suitably combined with a NIST-approved scheme. 

 

 

[Markku-Juhani O. Saarinen]

Hi,

Cryptography textbooks traditionally use the term "hybrid cryptosystem" to mean either (1) a combination of public key encryption algorithm with a symmetric cipher (KEM+DEM in modern terms) or (2) a combination of a hash function (message digest) with a signature algorithm. This is what I learned at school and would like to continue teaching. So I would try to avoid repurposing the "hybrid" term to also mean a composite of two different asymmetric algorithms.

The current PQC PKI working document in the IETF Secdispatch group discusses "composite keys and signatures" rather than "hybrid signatures".  https://tools.ietf.org/html/draft-ounsworth-pq-composite-sigs-01

So a "dual signature" in the FAQ would seem to add to the confusion. Those who were alive in the 1990s remember that this term was used for a different purpose in the SET protocol (essentially a single RSA signature of two different message hashes -- workable due to RSA's message recovery). It still exists with this meaning in some glossaries.

ps. The "composite" terminology has won favour in some industry quarters due to the fact the related IPR is being made available with significantly more permissive licensing terms (see section 7.2 of above internet draft) than ISARA's "non-critical extension" hybrid certificate patents (https://datatracker.ietf.org/ipr/3290/). This additional meaning to the word "composite" will hopefully pass. I'm not a legal expert but this will may significantly affect the path that the post-quantum transition takes when it comes to PKI and signatures. NIST may want to comment on this in their FAQ as well.

Cheers,

- markku

Dr. Markku-Juhani O. Saarinen <mj...@pqshield.com> PQShield, Oxford UK.

[Dan Brown]

Hi Dustin and PQC Forum,

 

Assume cryptosystems A and B have probabilities at most a and b of future (or hidden) attacks. Assume that A and B are independent.  The hybrid AB should have probability at most ab of a future attack (not counting implementation fault attacks). If both a and b are very low, then ab should be much lower than min(a,b), i.e. security assurance of (perfectly implemented) AB is much higher than A or B.

 

It remains to estimate a and b.

 

A simplistic back-of-the-envelope model, based on the Poisson point process, can formally estimate a and b (albeit derived from other estimates and assumptions).   Unfortunately, any half-reasonable estimates in this model produce rather high values for a and b, e.g., at least 0.9, which weakens the argument above for hybrid. 

 

A four-pager about this model https://eprint.iacr.org/2019/1465

 

There ought to be better ways to reasonably estimate a and b, hopefully resulting in quite low values for a and b, to better support the benefit of hybrid.  Or, maybe a sophisticated model would suggests that aiming for hybrid is bad because spreads the cryptanalysis too thinly?

 

Best regards,

 

​Dan

--
You received this message because you are subscribed to the Google Groups "pqc-forum" group.
To unsubscribe from this group and stop receiving emails from it, send an email to pqc-forum+...@list.nist.gov.
To view this discussion on the web visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/CH2PR09MB39744DAE15E3139EA24E6815E5600%40CH2PR09MB3974.namprd09.prod.outlook.com.

---

This transmission (including any attachments) may contain confidential information, privileged material (including material protected by the solicitor-client or other applicable privileges), or constitute non-public information. Any use of this information by anyone other than the intended recipient is prohibited. If you have received this transmission in error, please immediately reply to the sender and delete this information from your system. Use, dissemination, distribution, or reproduction of this transmission by unintended recipients is not authorized and may be unlawful.