Compliant KEM Combiner

[bencemali]

In NIST's guidelines for key derivation (see https://nvlpubs.nist.gov/nistpubs/SpecialPublications/NIST.SP.800-56Cr2.pdf) in section 2 they specify an approved method for combining a compliant secret with auxiliary shared secret like so:

In addition to the currently approved techniques for the generation of the shared secret Z as
specified in SP 800-56A and SP 800-56B, this Recommendation permits the use of a “hybrid”
shared secret of the form Z′ = Z || T, a concatenation consisting of a “standard” shared secret Z that
was generated during the execution of a key-establishment scheme (as currently specified in [SP
800-56A] or [SP 800-56B]) followed by an auxiliary shared secret T that has been generated using
some other method. The content, format, length, and method used to generate T must be known
and agreed upon by all parties that will rely upon the derived keying material, as well as by any
agents trusted to act on their behalf.

The present combiner in this draft doesn't include the secret from an approved method first in the input of the KDF:

Combiner(ct1, ss1, ct2, ss2, fixedInfo) =
KDF(counter || ct1 || ss1 || ct2 || ss2 || fixedInfo, outputBits)

We suggest moving either ss1 or ss2 to the beginning of the input to the KDF since concatenating any auxiliary secret to a compliant secret will result in a compliant key when feeding it to a compliant KDF. Even better, if we choose the classical key to be at the beginning (ss2 in the proposed combinations) it would mean that this construction would be considered compliant by NIST even if used with a non-standardized/compliant post-quantum algorithm.

The fixed counter value was added to in this draft to be compliant, but in the nist specification the counter must be followed by the compliant secret. In this specification ct1 is not a compliant secret, so this doesn't seem to be a good solution.

[ounsworth]

Thank you for the comment! That is an interesting point.

Earlier versions of this draft had exactly that: the shared secrets before the ciphertexts. We received feedback that we should swap the order so that it is more friendly to embedded devices: the device will have access to the ciphertext first, and only later will it have access to the shared secret, so if it can stream the ciphertext into the combiner hash function, then it does not need to keep the ciphertext in memory.

Regardless, if this change makes it impossible to FIPS-certify this under SP 800-56Cr2 (or the r3 that is coming to explicitly allow these hybrids), then that could be a more important consideration.

I will ask a contact at NIST.

[ounsworth]

LAMPS discussion thread about this:

https://mailarchive.ietf.org/arch/msg/spasm/yHFJkBs5qhQ0PIXP4NPK1vC9DAs/

[ounsworth]

Conclusion of the LAMPS discussion is:

[Dang, Quynh H. (Fed)] The above is not compliant with 56C. it needs to be KDF(counter || ss1 || ss2 || ciphertexts).