search

openpgp-pqc / draft-openpgp-pqc

Repository of the WIP draft-ietf-openpgp-pqc
Other
8 stars 3 forks source link

NIST compliance of KEM-combiner w.r.t. X25519/X448 KEM #132

Closed falko-strenzke closed 1 month ago

falko-strenzke commented 4 months ago

In https://github.com/openpgp-pqc/draft-ehlen-openpgp-nist-bp-comp/issues/10#issuecomment-2220090284 Quynh states that the current construction with a key derivation step in ECDH-KEM is not NIST compliant, which would equally affect the X25519/X448 KEM construction in this draft:

So, if we delete the step 3 in ECDH-KEM ( Set the output eccKeyShare to Hash(X || eccCipherText || eccPublicKey), then Falko's suggested KDF is NIST-compliant.

If we keep the step 3, eccKeyShare is a pseudorandom key and if eccKeyShare takes the place of X in Falko's suggested KDF, the KDF is not NIST-compliant at this point, but the KMAC-KDF mentioned above is NIST-compliant.

@QuynhDangNIST: can you provide the exact clause in the NIST standards that causes the incompliance? So far it seems to me that the using the output of Hash(X || eccCipherText || eccPublicKey) is equally fine to use as the ECC shared secret as input to the KEM combiner given by SHA3-256.

If the construction would really turn out to not being NIST compliant, we would have to change it in this draft as well.

falko-strenzke commented 4 months ago

I just want to add that from my point of view, just as I proposed here in said issue 10 of the NIST/Brainpool draft for the Weiherstrass-Curves, from my point of view the Hashing step in the X25519/X448 KEM can be dropped since we feed the public key and the ciphertext already to the key combiner KDF.

QuynhDangNIST commented 4 months ago

See Section 2 on page 2 of 56Cr2 here: https://nvlpubs.nist.gov/nistpubs/SpecialPublications/NIST.SP.800-56Cr2.pdf

Z' = Z || T. Z is a raw shared secret as specified in 56A,B&C, not a pseudorandom key. A KDF specified in 56C is used to generate pseudorandom key(s) from Z or Z'.

Right now, the KDFs in 56C are NIST-compliant only when H(counter || Z || FixedInfo) on page 14 has Z being a raw shared secret or Z' above. The situation where "counter" can be skipped was explained in my previous email.

Regards, Quynh.

From: Falko Strenzke @.> Sent: Wednesday, July 10, 2024 6:37 AM To: openpgp-pqc/draft-openpgp-pqc @.> Cc: Dang, Quynh H. (Fed) @.>; Mention @.> Subject: [openpgp-pqc/draft-openpgp-pqc] NIST compliance of KEM-combiner w.r.t. X25519/X448 KEM (Issue #132)

In openpgp-pqc/draft-ehlen-openpgp-nist-bp-comp#10 (comment)https://github.com/openpgp-pqc/draft-ehlen-openpgp-nist-bp-comp/issues/10#issuecomment-2220090284 Quynh states that the current construction with a key derivation step in ECDH-KEM is not NIST compliant, which would equally affect the X25519/X448 KEM construction in this draft:

So, if we delete the step 3 in ECDH-KEM ( Set the output eccKeyShare to Hash(X || eccCipherText || eccPublicKey), then Falko's suggested KDF is NIST-compliant.

If we keep the step 3, eccKeyShare is a pseudorandom key and if eccKeyShare takes the place of X in Falko's suggested KDF, the KDF is not NIST-compliant at this point, but the KMAC-KDF mentioned above is NIST-compliant.

@QuynhDangNISThttps://github.com/QuynhDangNIST: can you provide the exact clause in the NIST standards that causes the incompliance? So far it seems to me that the using the output of Hash(X || eccCipherText || eccPublicKey) is equally fine to use as the ECC shared secret as input to the KEM combiner given by SHA3-256.

If the construction would really turn out to not being NIST compliant, we would have to change it in this draft as well.

- Reply to this email directly, view it on GitHubhttps://github.com/openpgp-pqc/draft-openpgp-pqc/issues/132, or unsubscribehttps://github.com/notifications/unsubscribe-auth/AFTFKRBYUTIQB4WBCW7DACLZLUFFXAVCNFSM6AAAAABKUTZYRKVHI2DSMVQWIX3LMV43ASLTON2WKOZSGQYDAMZYGIZTQMQ. You are receiving this because you were mentioned.Message ID: @.***>

falko-strenzke commented 4 months ago

See Section 2 on page 2 of 56Cr2 here: https://nvlpubs.nist.gov/nistpubs/SpecialPublications/NIST.SP.800-56Cr2.pdf

@QuynhDangNIST Ist the point that if we have the hashing step in the ECDH-KEM and in the key combiner, that then we effectively do something like key = hash(hash(X || ...) || ... ), i.e., that contrary to NIST.SP.800-56Cr2 we hash twice?

QuynhDangNIST commented 4 months ago

From: Falko Strenzke @.> Sent: Wednesday, July 10, 2024 7:04 AM To: openpgp-pqc/draft-openpgp-pqc @.> Cc: Dang, Quynh H. (Fed) @.>; Mention @.> Subject: Re: [openpgp-pqc/draft-openpgp-pqc] NIST compliance of KEM-combiner w.r.t. X25519/X448 KEM (Issue #132)

See Section 2 on page 2 of 56Cr2 here: https://nvlpubs.nist.gov/nistpubs/SpecialPublications/NIST.SP.800-56Cr2.pdf

@QuynhDangNISThttps://github.com/QuynhDangNIST Ist the point that if we have the hashing step in the ECDH-KEM and in the key combiner, that then we effectively do something like key = hash(hash(X || ...) || ... ), i.e., that contrary to NIST.SP.800-56Cr2 we hash twice?

[Dang, Quynh H. (Fed)] That is not compliant with 56C. Check section 4. One-Step Key Derivation. Look at step 6 on page 14. The SHA3-256 in your suggested KDF is H.

Quynh.

- Reply to this email directly, view it on GitHubhttps://github.com/openpgp-pqc/draft-openpgp-pqc/issues/132#issuecomment-2220214824, or unsubscribehttps://github.com/notifications/unsubscribe-auth/AFTFKRCBQZF2FZ7533CESXLZLUIJPAVCNFSM6AAAAABKUTZYRKVHI2DSMVQWIX3LMV43OSLTON2WKQ3PNVWWK3TUHMZDEMRQGIYTIOBSGQ. You are receiving this because you were mentioned.Message ID: @.***>

falko-strenzke commented 4 months ago

OK, to be more precise, what we currently do is 

key = hash( counter || hash(X || ...) || ... )

But still my question is what exactly is causing the non-conformance in your view. The only deviation from 56C that I can identify is that instead of feeding X directly to the outer hash function we feed hash(X || ...). Is that reason for the incompliance that you were speaking of?

falko-strenzke commented 4 months ago

@QuynhDangNIST And a further question: will this incompliance also be given when the ECDH scheme is X25519 or X448?

QuynhDangNIST commented 4 months ago

I don't understand what part of the things I have written today is not clear to you.

I am not talking about security. I have been talking about what KDFs are NIST-compliant and what are not.

Quynh.

From: Falko Strenzke @.> Sent: Wednesday, July 10, 2024 7:26 AM To: openpgp-pqc/draft-openpgp-pqc @.> Cc: Dang, Quynh H. (Fed) @.>; Mention @.> Subject: Re: [openpgp-pqc/draft-openpgp-pqc] NIST compliance of KEM-combiner w.r.t. X25519/X448 KEM (Issue #132)

OK, to be more precise, what we currently do is

key = hash( counter || hash(X || ...) || ... )

But still my question is what exactly is causing the non-conformance in your view. The only deviation from 56C that I can identify is that instead of feeding X directly to the outer hash function we feed hash(X || ...). Is that reason for the incompliance that you were speaking of?

- Reply to this email directly, view it on GitHubhttps://github.com/openpgp-pqc/draft-openpgp-pqc/issues/132#issuecomment-2220265756, or unsubscribehttps://github.com/notifications/unsubscribe-auth/AFTFKRBQZTA67KPOKRVDQR3ZLUK5VAVCNFSM6AAAAABKUTZYRKVHI2DSMVQWIX3LMV43OSLTON2WKQ3PNVWWK3TUHMZDEMRQGI3DKNZVGY. You are receiving this because you were mentioned.Message ID: @.***>

QuynhDangNIST commented 4 months ago

Hi Falko,

I don't know for sure what specific KDF this question @.*** And a further question: will this incompliance also be given when the ECDH scheme is X25519 or X448? " was for.

In the past, NIST said that NIST planned to allow X25519 and/or X448 for ECDH. But at this moment, they are not the options in 56A.

I can talk to my group to see whether that is still in the plan. Especially, when we want people to use PQ crypto.

Regards, Quynh.

From: Falko Strenzke @.> Sent: Wednesday, July 10, 2024 7:29 AM To: openpgp-pqc/draft-openpgp-pqc @.> Cc: Dang, Quynh H. (Fed) @.>; Mention @.> Subject: Re: [openpgp-pqc/draft-openpgp-pqc] NIST compliance of KEM-combiner w.r.t. X25519/X448 KEM (Issue #132)

@QuynhDangNISThttps://github.com/QuynhDangNIST And a further question: will this incompliance also be given when the ECDH scheme is X25519 or X448?

- Reply to this email directly, view it on GitHubhttps://github.com/openpgp-pqc/draft-openpgp-pqc/issues/132#issuecomment-2220271482, or unsubscribehttps://github.com/notifications/unsubscribe-auth/AFTFKRBKE7IOEXFFXC3443DZLULHPAVCNFSM6AAAAABKUTZYRKVHI2DSMVQWIX3LMV43OSLTON2WKQ3PNVWWK3TUHMZDEMRQGI3TCNBYGI. You are receiving this because you were mentioned.Message ID: @.***>

falko-strenzke commented 4 months ago

I can talk to my group to see whether that is still in the plan. Especially, when we want people to use PQ crypto.

Maybe that can wait until we decided which way we prefer. If we remove the incompliance anyway, this would be better in my view.

falko-strenzke commented 4 months ago

Here is my summary to the problem as I understand it:

In NIST.SP.800-56Cr2, page 2 it says

derive keying material from a shared secret Z generated during the execution of a key-establishment scheme specified in ...

So the shared secret that is input to the key derivation of the key combiner will have to be

Z′ = Z || T,

where Z is the raw shared secret from the ECDH scheme and T in our case is the ML-KEM key share. Then the SHA3-based construction that we are specifying for the key combiner becomes:

SHA3-256(counter || Z || T || <other input>),

where <other input> is the public keys, ciphertexts, domain separation string, and algorithm ID. This is how it should be done according to SP.800-56C.

Now the problem that causes the non-compliance apparently is that in our current specification, we don't input Z as shown above, but instead hash(Z || ecdhCipherText || ecdhPublicKey). This additional hashing step is a formal deviation from the NIST spec.

The NIST-compliance is definitely relevant to the draft for the NIST/Brainpool curves. But since X25519/X448 is considered by NIST to receive NIST compliance as well, it has a certain relevance to the main draft as well.

The solution would be omitting the hashing step from the ECDH specification. Then we input the raw shared secret from the ECDH scheme into the key combiner as required by NIST. I don't think there can be any drawback, as the ECDH public key and ciphertext are still input as part of <other input> above.

The alternative that Quynh pointed out is to keep using KMAC. The formal difference seems to stem from the fact that in NIST.SP.800-108r1 it says that the input keys may stem from "[...] or a previous instance of key derivation as specified in this Recommendation" (p. 2) and thus allows to use KMAC with hash(Z || ...) || T as the input. That this does not equally apply to SHA3 is simply due to SP.800-108r1 not specifying SHA3 as a KDF at all.

QuynhDangNIST commented 4 months ago

Hi Falko,

From: Falko Strenzke @.> Sent: Wednesday, July 10, 2024 8:28 AM To: openpgp-pqc/draft-openpgp-pqc @.> Cc: Dang, Quynh H. (Fed) @.>; Mention @.> Subject: Re: [openpgp-pqc/draft-openpgp-pqc] NIST compliance of KEM-combiner w.r.t. X25519/X448 KEM (Issue #132)

Here is my summary to the problem as I understand it:

In NIST.SP.800-56Cr2https://nvlpubs.nist.gov/nistpubs/SpecialPublications/NIST.SP.800-56Cr2.pdf#page=10, page 2 it says

derive keying material from a shared secret Z generated during the execution of a key-establishment scheme specified in ...

So the shared secret that is input to the key derivation of the key combiner will have to be

Z′ = Z || T,

where Z is the raw shared secret from the ECDH scheme and T in our case is the ML-KEM key share. Then the SHA3-based construction that we are specifying for the key combiner becomes:

SHA3-256(counter || Z || T || ),

where is the public keys, ciphertexts, domain separation string, and algorithm ID. This is how it should be done according to SP.800-56C.

Now the problem that causes the non-compliance apparently is that in our current specification, we don't input Z as shown above, but instead hash(Z || ecdhCipherText || ecdhPublicKey). This additional hashing step is a formal deviation from the NIST spec.

[Dang, Quynh H. (Fed)] Correct. Z here is the result of the step 3 on page 49 of 56Ar3 at https://nvlpubs.nist.gov/nistpubs/SpecialPublications/NIST.SP.800-56Ar3.pdf

The NIST-compliance is definitely relevant to the draft for the NIST/Brainpool curves. But since X25519/X448 is considered by NIST to receive NIST compliance as well, it has a certain relevance to the main draft as well.

The solution would be omitting the hashing step from the ECDH specification. Then we input the raw shared secret from the ECDH scheme into the key combiner as required by NIST. I don't think there can be any drawback, as the ECDH public key and ciphertext are still input as part of above.

The alternative that Quynh pointed out is to keep using KMAC. The formal difference seems to stem from the fact that in NIST.SP.800-108r1https://nvlpubs.nist.gov/nistpubs/SpecialPublications/NIST.SP.800-108r1-upd1.pdf#page=10 it says that the input keys may stem from "[...] or a previous instance of key derivation as specified in this Recommendation" (p. 2) and thus allows to use KMAC with hash(Z || ...) || T as the input. That this does not equally apply to SHA3 is simply due to SP.800-108r1 not specifying SHA3 as a KDF at all.

[Dang, Quynh H. (Fed)] perfect recap! KMAC with hash(Z || ...) || T being the Key Derivation Key in 108.

Regards,

Quynh.

- Reply to this email directly, view it on GitHubhttps://github.com/openpgp-pqc/draft-openpgp-pqc/issues/132#issuecomment-2220386567, or unsubscribehttps://github.com/notifications/unsubscribe-auth/AFTFKRASDNVDHIVN7Y4LWTDZLUSFZAVCNFSM6AAAAABKUTZYRKVHI2DSMVQWIX3LMV43OSLTON2WKQ3PNVWWK3TUHMZDEMRQGM4DMNJWG4. You are receiving this because you were mentioned.Message ID: @.***>

falko-strenzke commented 4 months ago

There is one risk that I see for the solution using

SHA3-256(counter || <raw EC coord.> || <ML-KEM ss> || <other input>).

We agree that this will result in a NIST compliant ECDH scheme with an additional key mixed in. But I currently don't see the guarantee that this will also necessarily fulfill the future requirements by NIST for an ECDH+ML-KEM hybrid scheme. This is something that we will most likely only know once NIST's recommendations for PQ/T hybrid is specified. The other solution, namely switching back to KMAC does not have this problem, since with KMAC we receive a generic KDF according to NIST.SP.800-108r1. Thus in this case there is no limitation on where the input secrets to the KMAC-based KDF stem from.

ahuelsing commented 4 months ago

Dear all, Falko asked me to provide a comment on this.

I would like to highlight two aspects here. First, our goal is to build a "KEM-combiner", i.e., something that constructs a secure KEM from two KEMs. The initial hash of the ECDH data achieves exactly this: It turns DH into a KEM. This way, we are able to apply modular reasoning which also protects against issues stemming from replacing ECDH by some other construction.

Second, our set goal is really to construct an IND-CCA secure KEM. This is a mismatch with https://nvlpubs.nist.gov/nistpubs/SpecialPublications/NIST.SP.800-56Ar3.pdf which describes how to derive a secret key from some source of computational entropy (like a pre-master secret) where one such source is obtained via DH. Note that while the SP this does not explicitly state any security goals (at least I did not find any), the way it is written suggests that active security is not a concern here.

Regarding what we know in terms of results: We have a security proof for a KEM that is obtained by combining the data of two KEMs as is currently done in the draft (KDF(k1,c1,pk1,k2,c2,pk2) where the order does not matter if we use SHA3/SHAKE/KMAC-SHA3). This proof is in the standard model and thereby holds against quantum adversaries as well. I do not know what we can prove for the "simply hashing everything in the end" approach (KDF(DH.k, k2, DH.pk_sender, DH.pk_receiver, c2, pk2)). This will require a direct, non-modular proof for the full construction. Does NIST have any results for this? I did not see references in the SP.

Best wishes,

Andreas

wussler commented 3 months ago

Hi @QuynhDangNIST

Do we need all steps of KDF to be FIPS-compliant to achieve FIPS compliance?

If so, please let me propose a solution if I parsed correctly all the info in the thread:

Would that be compliant?

QuynhDangNIST commented 3 months ago

Hi Aron,

See below.

From: Aron Wussler @.> Sent: Thursday, July 25, 2024 7:15 AM To: openpgp-pqc/draft-openpgp-pqc @.> Cc: Dang, Quynh H. (Fed) @.>; Mention @.> Subject: Re: [openpgp-pqc/draft-openpgp-pqc] NIST compliance of KEM-combiner w.r.t. X25519/X448 KEM (Issue #132)

Hi @QuynhDangNISThttps://github.com/QuynhDangNIST

Do we need all steps of KDF to be FIPS-compliant to achieve FIPS compliance?

If so, please let me propose a solution if I parsed correctly all the info in the thread:

* We can use an SP.800-56Cr2 compliant KDF in the ECDH KDF, that is already SHA3-256(X || ecdhCipherText || ecdhPublicKey)

When X is a raw shared secret of a DH, then the KDF above is compliant with NIST for classical security. The DH must be a NIST-compliant one. When X is a ML-KEM key (it is a pseudorandom key), then it is compliant with 56C when FIPS 205 is published for PQ security. When X = X1||X2 and X1 is a ML-KEM key and X2 is another shared secret such as X25519 shared secret or another secret value, then the KDF is compliant with 56C for PQ security.

A ML-KEM key can be used directly as an encryption key or MAC key such as taking the leftmost (or rightmost) 128 bits to be an AES128 key. A ML-KEM-1024 key can be used as a AES256 key.

* We rely on SP.800-108r1 and switch to KMAC for the KEM Combiner as KMAC(K, X, 256, "KDF"), where K is the concatenated keys (?) and X are the ciphertexts and public keys?

K, the key derivation key, is a pseudorandom key such as a ML-KEM key or a Y = SHA3-256(X || ecdhCipherText || ecdhPublicKey) where X is a raw P256 ECDH shared secret.

Or, K can be ML-KEM key || Y or Y||ML-KEM key. K can be a concatenation of multiple pseudorandom keys but they must be the outputs of NIST-approved methods as currently specified in SP 800-133.

One can put X25519 shared secret in X to make the KDF compliant.

Even though technically, it is fine to use K = ML-KEM key || X25519 shared secret (or a pseudorandom key derived from it).

Regards, Quynh.

Would that be compliant?

— Reply to this email directly, view it on GitHubhttps://github.com/openpgp-pqc/draft-openpgp-pqc/issues/132#issuecomment-2250079446, or unsubscribehttps://github.com/notifications/unsubscribe-auth/AFTFKRDQ6RTEQNEQ5QLRSHDZODM5RAVCNFSM6AAAAABKUTZYRKVHI2DSMVQWIX3LMV43OSLTON2WKQ3PNVWWK3TUHMZDENJQGA3TSNBUGY. You are receiving this because you were mentioned.