Official comment on FIPS 203 ipd: seed as decapsulation key

[Deirdre Connolly]

We propose ML-KEM uses a single 32-byte seed as decapsulation key, from which rho, sigma, and z are expanded.

This is smaller and simpler. Simpler, because we do not need to think about decapsulation key formatting or validation. In particular, it ensures that ML-KEM is MAL-BIND-K-CT and MAL-BIND-K-PK [1].

On paper, this slows down decapsulation, as (more) work from key generation has to be repeated during decapsulation. In practice, there will not be a slowdown in the majority of use cases, as implementations typically cache those computations. [2]

To make things concrete, semantically, the change can be expressed as briefly as [3]. (For readability and to stay a bit closer to implementations in practice, one can integrate the changes a bit more, as in [4].)

Some points:

1. It is tempting at this stage to use the 64-byte seed d || z implicit in the current IPD instead of a single 32-byte seed g. Unfortunately, to ensure MAL-BIND-K-PK, z cannot be a direct part of the private key.

2. In the concrete proposal, we use (rho, sigma, z) = J(g) = SHAKE-256(g). This use of SHAKE-256 does not conflict with the other two uses, as it's separated by input length [5].

An alternative is

(d, z) = SHA3-512(0x00 || g)
(rho, sigma) = SHA3-512(d)

which aligns more closely with what is done in the IPD now.

The latter has slightly higher security than the former (512 vs. 416 bits), but both are comfortably above the target security levels.

Best,

Sophie Schmieg, Deirdre Connolly, Bas Westerbaan


[1] Cf. https://eprint.iacr.org/2024/523 and https://groups.google.com/a/list.nist.gov/g/pqc-forum/c/8cNYhg23B9k/m/HK34y1CaAwAJ


[2] For decapsulation, implementations of the IPD rarely accept the decapsulation key directly. Instead, a decapsulation key has to be unpacked first, which precomputes A. Also, key generation returns an unpacked decapsulation key.

       "packed"        unpack        ready-to-use      keygen
      decaps key      -------->       decaps key     <---------  64 byte seed
     s, ek, H(ek), z               s, ek, H(ek), z, A               d, z

     [ Current use of FIPS 203 IPD in practice. ]

This two-step approach allows ephemeral users (such as browsers today) to compute A only once. For long-term keys, this allows applications to load the key once and keep A around.

The present proposal will simplify the situation to:

       "packed"     unpack=keygen    ready-to-use
      decaps key      -------->       decaps key
          g                        s, ek, H(ek), z, A

     [ Use of FIPS 203 with the proposed change in practice. ]

To be clear, we do *not* propose that FIPS 203 specifies this two-step approach. It merely should not preclude it.

[3] 1. Rename K-PKE.KeyGen to K-PKE.ExpandPrivate; remove lines 1, 2; and add rho and sigma as arguments.

2. Rename ML-KEM.KeyGen to ML-KEM.ExpandPrivate; add a 32-byte g as argument; call K-PKE.ExpandPrivate instead of K-PKE.KeyGen on line 2 passing rho and sigma; and replace line 1 by:

(rho, sigma, z) = J(g)

3. Define a new ML-KEM.KeyGen as

g <$- B^32
ek, dk = ML-KEM.ExpandPrivate(g)
return (ek, g)

4. Change ML-KEM.Decaps to take a 32-byte g as argument instead of dk. Add before line 1: _, dk = ML-KEM.ExpandPrivate(g).


[4] 1. Rename K-PKE.KeyGen to K-PKE.ExpandPrivate; remove lines 1, 2, 20, and 21; add rho and sigma as arguments; and return (^A, ^t, ^s).

2. Add a new function ML-KEM.UnpackPrivate that takes a 32-byte seed dk as argument, and acts as follows:

(rho, sigma, z) = J(dk)      // SHAKE-256
^A, ^t, ^s = K-PKE.ExpandPrivate(rho, sigma)
ek = ByteEncode_12(^t) || rho
return (^A, ^t, ^s, ek, H(ek), z)

3. Change ML-KEM.KeyGen to:

dk <$- B^32
(^A, ^t, ^s, ek, h, z) = ML-KEM.UnpackPrivate(dk)
ek = ByteEncode_12(^t) || rho
return (ek, dk)

4. Change K-PKE.Encrypt to accept ^A, and ^t directly instead of ek_PKE, removing lines 2–8.

5. Change K-PKE.Decrypt to accept ^s as argument directly instead of dk_PKE, removing line 5.

6. Change ML-KEM.Decaps to accept the shortened 32-byte dk. Replace lines 1-4 by

(^A, ^t, ^s, ek, h, z) = ML-KEM.UnpackPrivate(dk)

and pass ^s instead of dk_PKE to K-PKE.Decrypt (line 7); and ^A, ^t instead of ek_PKE to K-PKE.Encrypt (line 8).

7. Change ML-KEM.Encaps to include the lines 2–8 removed from K-PKE.Encrypt before the call to K-PKE.Encrypt, to which ^A and ^t are passed instead of ek_PKE.

[5] Recall g is 32 bytes. SHAKE-256 is used in two other places. It is used as PRF in KeyGen where it takes a 33 byte input. It is also used as J in decapsulation to compute the rejection key K-bar, where it takes the ciphertext and z as input, which is normally much longer than 33 bytes. In the degenerate case of an empty or one byte ciphertext input validation should catch the error, but even if it does not and the rejection flow is triggered, the rejection key will be J(J(g)[64:96]) for the empty ciphertext and J(J(g)[64:96] || c), for the one byte ciphertext. The first is a secure hash function of the secret key, not revealing any information on g that is not already available through rho = J(g)[32:64], the second would not reveal any information on J(sigma || counter) = J(J(g)[0:32] || counter), based on the assumption that J is a secure XOF and as such not distinguishable from a random function, where independent sections of the output are unrelatable.

[D. J. Bernstein]

Deirdre Connolly writes:
> In particular, it ensures that
> ML-KEM is MAL-BIND-K-CT and MAL-BIND-K-PK [1].

[ ... ]

> In practice, there will not be a
> slowdown in the majority of use cases, as implementations typically cache
> those computations. [2]

If there's an actual security concern with the existing (expanded) key
format, shouldn't caching keys in that format also be prohibited?

See my email dated 7 Apr 2024 13:52:59 +0200 for further questions about
this. I'm hoping for a clear statement explaining (1) how the existing
key format could lead to attacks and (2) why those attacks _wouldn't_ be
possible for keys cached in that format.

---D. J. Bernstein

[Sophie Schmieg]

The security concern is in the transmission of private keys, in the relatively unusual case of protocols that require revealing private keys under certain circumstances or accepting private keys from third parties. Keys in memory do not factor in here, as detailed in [1] and referenced in [2], since serialization is required for transmission.

[1] https://eprint.iacr.org/2023/1933

[2] https://eprint.iacr.org/2024/523

--
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/20240419141559.384922.qmail%40cr.yp.to.

--

Sophie Schmieg | Information Security Engineer | ISE Crypto | ssch...@google.com

[D. J. Bernstein]

'Sophie Schmieg' via pqc-forum writes:
> The security concern is in the transmission of private keys, in the
> relatively unusual case of protocols that require revealing private keys
> under certain circumstances or accepting private keys from third parties.

What's an example of a protocol that transmits private keys and would be
broken with private keys in Kyber's existing format but would be rescued
if the format were changed to a seed?

---D. J. Bernstein

[Filippo Valsorda]

Seed encoding is at the very least more compact (32 or 64 bytes vs. 2400 for ML-KEM-768, not insignificant) and more convenient, as it sidesteps questions such as:

• should we check H(ek) matches ek?
  
• what happens if the implementation recomputes H(ek) and it was wrong in the encoding?
  
• what's the right way to handle dkPKE coefficients being unreduced?
  

These are not necessarily security arguments (beyond the extent to which every complexity argument is implicitly a security argument), and can be trumped by security or major performance concerns.

If you have a security concern about encoding private keys as a seed, can you provide an example of a protocol that would be broken with private keys in seed format but would be rescued if the existing Kyber format was used? If you have a performance concern can you quantify it?

If you have a different concern, can you clarify it?

---D. J. Bernstein

-- 

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/20240419210427.405600.qmail%40cr.yp.to.

Attachments:

• signature.asc
  

[D. J. Bernstein]

Filippo Valsorda writes:
> If you have a different concern, can you clarify it?

Public cryptanalysts are overloaded and have a strong disincentive to
chase moving targets. This is what led to, e.g., OCB2 being standardized
with a change from OCB1 that eliminated security. It took more than ten
years for the public to notice the security failure.

The NISTPQC call for submissions allowed one moment for "small
modifications" at the end of the first round, followed by "thorough
public review of the modified algorithms during the entire course of the
second evaluation phase":

Because of limited resources, and also to avoid moving evaluation
targets (i.e., modifying the submitted algorithms undergoing public
review), NIST will NOT accept modifications to the submitted
algorithms during this initial phase of evaluation. ...

During the course of the initial evaluations, it is conceivable that
some small deficiencies may be identified in even some of the most
promising submissions. Therefore, for the second round of
evaluations, small modifications to the submitted algorithms will be
permitted for either security or efficiency purposes. ...

If modifications are submitted, new reference and optimized
implementations and written descriptions must also be provided by the
announced deadline. This will allow a thorough public review of the
modified algorithms during the entire course of the second evaluation
phase.

The call also said that there could be "a third phase of evaluation",
which would be "structured similarly". Also, for "algorithms that have
tunable parameters", the call said that NIST could select different
parameter sets after consulting with "the cryptographic community".

I don't see where these procedures allow post-selection changes to the
submitted algorithms, beyond parameter selection. Even if such changes
_are_ allowed, what neverending changes communicate to cryptanalysts is
"We don't care about your time and don't really want your input".

Meanwhile NIST's announcements indicate that NIST's patent licenses are
only for exactly what NIST ends up standardizing. The fact that _we
still don't know what that will be_ continues to deter deployment. This
is perfectly in line with the delays that DHS, NSA, and NIST started
publicly asking for three years ago---

* DHS said not to use "any post-quantum cryptographic industry
products until standardization, implementation, and testing of
replacement products with approved algorithms are completed by
NIST";

* NSA said that "policy does not allow implementing or using
unapproved, non-standard or experimental cryptographic algorithms";

* NIST said not to allow people to "start to buy and implement
unstandard, unknown, potentially unsecured implementations before
we as a general community have agreed upon standardization"

---but it's contrary to the goal of protecting user data.

Given

* the damage that moving targets cause to security review,

* the extra damage from the interaction between moving targets and
the patent situation, and

* the call clearly specifying a procedure where any algorithm
modifications are followed by "thorough public review of the
modified algorithms" during an "entire" competition round,

it looks bad to be considering post-selection changes. It would have
been much better to just go ahead with standardizing (some) parameter
sets for the selected submissions. It's still possible to do this, and I
still recommend doing this.

But, well, clearly various changes _are_ being considered, which is what
prompts my questions about what exactly the benefits are supposed to be
of those changes. It's inappropriate to dodge such questions by asking
why the changes are problematic---this is exacerbating the procedural
problem of overloading cryptanalysts with things to review. The default
should be zero changes; people proposing changes should be doing serious
cost-benefit analyses and then asking for review of those.

NIST's round-3 report said that NIST was "confident in the security" of
Kyber and that Kyber's "overall performance ... would be acceptable for
general-use applications". Sure, there are clear arguments that it's
possible to do better---for example, compared to Kyber-1024, smaller LAC
sizes (1056-byte pk, 1424-byte ct) provide higher security margins
against known attacks---but the claimed benefits of the post-selection
Kyber changes look much smaller than that:

* There's no reduction in pk size or ct size.

* There's no increase in security margin.

* Nobody has given any examples of any attack strategies that could
be blocked by the changes. (Meanwhile it's completely clear how the
changes would _enable_ attacks via, e.g., Dual EC.)

* There's a measurable decrease in CPU cycles, and there's an
unverifiable claim that this would add up to saving an unquantified
"millions of dollars" for Google. (Last I checked, Google had an
annual revenue of three hundred billion dollars.)

If post-selection changes aren't simply barred, then a post-selection
change for alleged security reasons should at least be backed by

* analyzing what's known about the security impact of the change,

* identifying attacks that would be blocked by the change, and, as
above,

* explaining why the change is important enough to outweigh the
damage that instability causes to the review process.

I've seen suggestions that using seeds as a private-key format could
stop attacks, but so far I haven't seen any examples of attacks that
could be stopped; I haven't seen any analysis of whether seeds could
damage security; and I haven't seen any analysis of how the alleged
benefits compare to the costs of instability.

Similarly, a post-selection change for alleged performance reasons
should be backed by

* quantifying the improvement,

* comparing the improvement to the overall application costs,

* analyzing what's known about the security impact of the change,
and, as above,

* explaining why the change is important enough to outweigh the
damage that instability causes to the review process.

This seems particularly tough for a change whose only claimed benefit is
in private-key size. Private-key size is such a minor performance issue
that it didn't even show up in the call for submissions: the cost
section of the call said that NIST would evaluate "Public Key,
Ciphertext, and Signature Size" and "Computational Efficiency".

---D. J. Bernstein

[Bas Westerbaan]

   * Nobody has given any examples of any attack strategies that could
     be blocked by the changes. (Meanwhile it's completely clear how the
     changes would _enable_ attacks via, e.g., Dual EC.)

Please, do explain the attack when using a seed as a private key — it is not clear to me how that would work.

Best,

 Bas

[D. J. Bernstein]

I said "the changes" (referring to "the post-selection Kyber changes"),
not "the key-format change".

The obvious attack via Dual EC comes from NIST's change to directly
release RNG output (where Kyber instead hashed the RNG output before
releasing it). The setup is that the attacker connects to the target
system and provides a public key, and the system does enc back to that
public key. This reveals a 256-bit string from the RNG straight to the
attacker, and then https://cr.yp.to/papers.html#dualectls efficiently
reconstructs the secret RNG state.

(In environments where RNG reads are randomly aligned compared to RNG
blocks, the success probability of the fastest attack is expected to be
only 1/32, but typically the attacker can fix this by triggering other
RNG reads or by just retrying 32 times on average.)

https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.203.ipd.pdf claims that
hashing is "unnecessary" with (current, not Dual EC) "NIST-approved
randomness generation". That's wrong. https://eprint.iacr.org/2018/349
Section 7.1 breaks forward secrecy (specifically, forward deniability)
of NIST's HMAC-DRBG, whereas an extra hashing step fixes this.

---D. J. Bernstein

[Samuel Lee]

Hey folks,

Just to make sure my feedback around key confusion when using a seed as a decapsulation is not missed, adding a link to this thread.
https://groups.google.com/a/list.nist.gov/g/pqc-forum/c/Rb0nFvfFTEQ/m/lw-k7tVdBQAJ

At a minimum if a seed is considered to be a storage format for a decapsulation key there should be some clear language stating that the parameters of ML-KEM associated with the key should be maintained with the seed.

I think it would be better if key generation was additionally slightly tweaked s.t. given seed reuse across different ML-KEM flavors, the resulting decapsulation keys are unrelated.

Best,

Sam

[Bas Westerbaan]

Thanks for bumping that up Sam.

I agree that there should be a warning that a seed should only be used for a particular instance of ML-KEM. More generally, the user should know that the keys and ciphertexts being processed are intended to be, say, ML-KEM-768, and they shouldn't go by size alone.

I am not opposed to the domain separation you propose to key generation, as it is essentially free in this case, but I also don't want to push it: there is no end to the technical countermeasures we'd have to put in place if we are to account for all possible confusions.

Best,

 Bas

--

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/14c75610-3feb-4fc0-b0bf-5cf746ce1a00n%40list.nist.gov.

[Sophie Schmieg]

I agree with Bas here, domain separation is essentially free and a nice hardening measure, and in general the algorithm and its parameters should be considered part of the key material in any case, there are many vulnerabilities if one violates this principle, to the point that https://www.howmanydayssinceajwtalgnonevuln.com/ keeps track of the number of days of just one specific variant of this problem (JWT using alg=none) and rarely reaches the 356 day mark. Hashing in the algorithm identifier and parameter choices is a nice way of enforcing that the algorithm and parameters are being kept with the key. Now if we could retrofit this to AES and its many modes...

To view this discussion on the web visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/CAMjbhoWc2tZFy_syc8qEYMDd8o0-W-v%2BabX3c3HMQbVk2XUofg%40mail.gmail.com.

[Perlner, Ray A. (Fed)]

Dear all,

 

We are interested in hearing feedback from others regarding Sam’s suggestion to add domain separation early in key generation for ML-KEM (and, while not stated, ML-DSA), as described in: https://groups.google.com/a/list.nist.gov/g/pqc-forum/c/5CT4NC_6zRI/m/QZ7jLXEiCAAJ

 

Such a change would provide an inexpensive means to protect implementations from seed reuse across different algorithms and parameter sets and we are considering including this in the final versions of FIPS 203 and FIPS 204. The lines we would modify correspond to line 2 of Algorithm 12 in draft FIPS 203 and line 2 of Algorithm 1 in draft FIPS 204. The modification in each case would be to append to the input of the Hash/XOF a short string specific to the parameter set.

 

If you have thoughts on this, we’d appreciate it soon, as we are very close to finalizing the content of the FIPS.

 

Thanks everyone!

 

Ray Perlner (NIST PQC team)

To view this discussion on the web visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/CAEEbLAbr4R%3DQ%3DoUZ_P-O%3DxrHy__RAn-%2B5HcFZWYEG1ojms0N5A%40mail.gmail.com.

[Blumenthal, Uri - 0553 - MITLL]

I support adding domain separation.

 

Thanks

-- 

V/R,

Uri

 

 

From: 'Perlner, Ray A. (Fed)' via pqc-forum <pqc-...@list.nist.gov>
Date: Friday, May 17, 2024 at 10:38
To: Sophie Schmieg <ssch...@google.com>, Bas Westerbaan <b...@cloudflare.com>
Cc: Samuel Lee <samue...@microsoft.com>, pqc-forum <pqc-...@list.nist.gov>, D. J. Bernstein <d...@cr.yp.to>
Subject: [EXT] RE: [pqc-forum] Official comment on FIPS 203 ipd: seed as decapsulation key

Dear all, We are interested in hearing feedback from others regarding Sam’s suggestion to add domain separation early in key generation for ML-KEM (and, while not stated, ML-DSA), as described in: https: //groups. google. com/a/list. nist. gov/g/pqc-forum/c/5CT4NC_6zRI/m/QZ7jLXEiCAAJ

ZjQcmQRYFpfptBannerStart

This Message Is From an External Sender This message came from outside the Laboratory.

ZjQcmQRYFpfptBannerEnd

To view this discussion on the web visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/DM6PR09MB48551A50F88DF01ECBE02D989CEE2%40DM6PR09MB4855.namprd09.prod.outlook.com.

[Simon Hoerder]

Hi all,

linking keys to algorithms and security levels / domain parameters is
important, no question. For keys stored as seed that's even more the
case than usual.

My first concern is that "domain separation" is usually a more generic
feature where people people / protocols / ecosystems can define all kind
of additional domains including a "valid for ML-KEM-512-768-1024 and
ML-DSA-... and ..." domain later. (I hope that never happens, just
playing devil's advocat.) I'd rather have a mechanism that links the key
seed strictly to the algorithm and security level without options for
people to get creative later. I assume that's what everyone is talking
about but I wanted to be clear about it.

My second concern is whether key storage formats and linking the key to
the algorithm and security level should be part of FIPS 203 and FIPS 204
or whether it's better to add it to documents that describe key
management policies already. I guess it depends a bit how NIST wants to
implement it and how much freedom developers get to choose between key
storage formats. Does NIST intend to make it a CAVP topic or will it be
a CMVP topic?

Best,
Simon

On 17/05/2024 16:38, 'Perlner, Ray A. (Fed)' via pqc-forum wrote:
> Dear all,
>
> We are interested in hearing feedback from others regarding Sam’s
> suggestion to add domain separation early in key generation for ML-KEM
> (and, while not stated, ML-DSA), as described in:

> https://groups.google.com/a/list.nist.gov/g/pqc-forum/c/5CT4NC_6zRI/m/QZ7jLXEiCAAJ <https://groups.google.com/a/list.nist.gov/g/pqc-forum/c/5CT4NC_6zRI/m/QZ7jLXEiCAAJ>

>
> Such a change would provide an inexpensive means to protect
> implementations from seed reuse across different algorithms and
> parameter sets and we are considering including this in the final
> versions of FIPS 203 and FIPS 204. The lines we would modify correspond
> to line 2 of Algorithm 12 in draft FIPS 203 and line 2 of Algorithm 1 in
> draft FIPS 204. The modification in each case would be to append to the
> input of the Hash/XOF a short string specific to the parameter set.
>
> If you have thoughts on this, we’d appreciate it soon, as we are very
> close to finalizing the content of the FIPS.
>
> Thanks everyone!
>
> Ray Perlner (NIST PQC team)
>

> *From:* 'Sophie Schmieg' via pqc-forum <pqc-...@list.nist.gov>
> *Sent:* Wednesday, May 15, 2024 1:46 PM
> *To:* Bas Westerbaan <b...@cloudflare.com>
> *Cc:* Samuel Lee <samue...@microsoft.com>; pqc-forum

> <pqc-...@list.nist.gov>; D. J. Bernstein <d...@cr.yp.to>

> *Subject:* Re: [pqc-forum] Official comment on FIPS 203 ipd: seed as

> https://groups.google.com/a/list.nist.gov/g/pqc-forum/c/Rb0nFvfFTEQ/m/lw-k7tVdBQAJ <https://groups.google.com/a/list.nist.gov/g/pqc-forum/c/Rb0nFvfFTEQ/m/lw-k7tVdBQAJ>

> <mailto: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/14c75610-3feb-4fc0-b0bf-5cf746ce1a00n%40list.nist.gov <https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/14c75610-3feb-4fc0-b0bf-5cf746ce1a00n%40list.nist.gov?utm_medium=email&utm_source=footer>.

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

> <mailto: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/CAMjbhoWc2tZFy_syc8qEYMDd8o0-W-v%2BabX3c3HMQbVk2XUofg%40mail.gmail.com <https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/CAMjbhoWc2tZFy_syc8qEYMDd8o0-W-v%2BabX3c3HMQbVk2XUofg%40mail.gmail.com?utm_medium=email&utm_source=footer>.

>
>
> --
>
>
> Sophie Schmieg | Information Security Engineer | ISE

> Crypto |ssch...@google.com <mailto:ssch...@google.com>

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

> <mailto: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/CAEEbLAbr4R%3DQ%3DoUZ_P-O%3DxrHy__RAn-%2B5HcFZWYEG1ojms0N5A%40mail.gmail.com <https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/CAEEbLAbr4R%3DQ%3DoUZ_P-O%3DxrHy__RAn-%2B5HcFZWYEG1ojms0N5A%40mail.gmail.com?utm_medium=email&utm_source=footer>.

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

> <mailto: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/DM6PR09MB48551A50F88DF01ECBE02D989CEE2%40DM6PR09MB4855.namprd09.prod.outlook.com <https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/DM6PR09MB48551A50F88DF01ECBE02D989CEE2%40DM6PR09MB4855.namprd09.prod.outlook.com?utm_medium=email&utm_source=footer>.

[John Mattsson]

D. J. Bernstein wrote:

>OCB2 being standardized with a change from OCB1 that eliminated security. It took more than ten years for the public to notice the security failure. 

 

I think that is an excellent example of why paywalled algorithm standards like ISO should be considered cybersecurity risks and avoided like the plague.

 

Cheers,

John Preuß Mattsson

[Blumenthal, Uri - 0553 - MITLL]

Totally agree with John here. 

Regards,

Uri

On May 17, 2024, at 11:34, 'John Mattsson' via pqc-forum <pqc-...@list.nist.gov> wrote:



D. J. Bernstein wrote: >OCB2 being standardized with a change from OCB1 that eliminated security. It took more than ten years for the public to notice the security failure. I think that is an excellent example of why paywalled algorithm

ZjQcmQRYFpfptBannerStart

This Message Is From an External Sender

This message came from outside the Laboratory.

 

ZjQcmQRYFpfptBannerEnd

D. J. Bernstein wrote:

--

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/GVXPR07MB9678C67F98B6350AFAA8ED3F89EE2%40GVXPR07MB9678.eurprd07.prod.outlook.com.

[D. J. Bernstein]

I wrote:
> Public cryptanalysts are overloaded and have a strong disincentive to

> chase moving targets. This is what led to, e.g., OCB2 being standardized

> with a change from OCB1 that eliminated security. It took more than ten
> years for the public to notice the security failure.

'John Mattsson' via pqc-forum writes:
> I think that is an excellent example of why paywalled algorithm
> standards like ISO should be considered cybersecurity risks and
> avoided like the plague.

Um, how is the ISO paywall supposed to have made even the slightest
difference in the OCB2 security failure? OCB2 was published years before
ISO standardized it. The fact that it was standardized was also public.

---D. J. Bernstein

[John Mattsson]

Hi,

I have not looked into MALBIND-K-CT and MAL-BIND-K-PK but this seems similar/related to the work Tobias Hemmert et al. did on how to prevent backdoored public keys in LWE and (Classic) McEliece systems [1-2].

[1] https://eprint.iacr.org/2022/1381

[2] https://eprint.iacr.org/2022/362

 

Perlner, Ray A. (Fed) wrote:

>We are interested in hearing feedback from others regarding Sam’s suggestion to add domainseparation early in key generation for ML-KEM (and, while not stated, ML-DSA), as described in: >https://groups.google.com/a/list.nist.gov/g/pqc-forum/c/5CT4NC_6zRI/m/QZ7jLXEiCAAJ

 

I like the suggestion by Samuel Lee to slightly tweak the key generation. That seems better than prepending the seed with a code point byte.

Cheers,
John

[Perlner, Ray A. (Fed)]

 

Hi all,

 

Due to the generally positive feedback we’ve received for domain separating KeyGen for different parameter sets of ML-KEM and ML-DSA, we plan to introduce domain separation in the final drafts of FIPS 203 and FIPS 204.

 

Thus, we plan to change line 2 of Algorithm 12 in draft FIPS 203 to:

(ρ,σ) ← G(d || k)

 

• here the module dimension is interpreted as a single byte (i.e. an integer in the range 0 to 255) with the numerical value 2, 3, or 4.

 

And we plan to change line 2 of Algorithm 1 in draft FIPS 204 to:

(𝜌, 𝜌′, 𝐾) ∈ 𝔹³² × 𝔹⁶⁴ × 𝔹³² ← H(𝜉||IntegerToBytes(𝑘, 1)||IntegerToBytes(ℓ, 1), 128)

 

• here the spec defines an explicit function to encode the module dimensions k and \ell as single bytes (this is the same encoding used by FIPS 203, but an explicit conversion function was already defined elsewhere in the internal working draft for FIPS 204 for domain separation between pure and prehash variants, so we plan to use it here as well).

 

Best,

[Paul Duncan]

Hi Ray,

I like these changes to FIPS 203 and FIPS 204. My feedback from last
week didn't make it past the spam filter, but keeping the length of the
identifiers short (a couple of bytes) is good, and using a one byte
suffix to indicate the ML-KEM parameter set and a two byte suffix to
indicate the ML-DSA parameter set provides implicit algorithm
separation.

Questions:

1. Does FIPS 205 need a similar modification to it's seed handling? I
don't know enough about SLH-DSA, but from a cursory examination it looks
like the answer is "no".

2. Is this going to be the intention for future standards as well? I'm
assuming the answer is "yes".

3. Would there be value in making the algorithm separation explicit
rather than implicit by adding an single byte prefix to the seed suffix
which indicates the algorithm?

For example, for ML-KEM-512 the seed suffix with the prefix might be
"0x00 0x02" and for ML-DSA-44 the seed suffix with the prefix byte might
be "0x01 0x04 0x04", with 0x00 indicating ML-KEM and 0x01 indicating
ML-DSA, respectively.

(The rational behind adding an explicit algorithm identifier byte is to
make it easier to use a seed suffix in future parameter sets or
standards without having to worry about colliding identifiers).

Thanks,

* 'Perlner, Ray A. (Fed)' via pqc-forum (pqc-...@list.nist.gov) wrote:
>
>
> Hi all,
>
>
>
> Due to the generally positive feedback we’ve received for domain
> separating KeyGen for different parameter sets of ML-KEM and ML-DSA, we
> plan to introduce domain separation in the final drafts of FIPS 203 and
> FIPS 204.
>
>
>
> Thus, we plan to change line 2 of Algorithm 12 in draft FIPS 203 to:
>
> (ρ,σ) ← G(d || k)
>
>
>

> o here the module dimension is interpreted as a single byte (i.e. an

> integer in the range 0 to 255) with the numerical value 2, 3, or 4.
>
>
>
> And we plan to change line 2 of Algorithm 1 in draft FIPS 204 to:
>

> (𝜌, 𝜌′, 𝐾) ∈ 𝔹^32 × 𝔹^64 × 𝔹^32 ← H(𝜉||IntegerToBytes(𝑘,
> 1)||IntegerToBytes(ℓ, 1), 128)
>
>
>
> o here the spec defines an explicit function to encode the module

> dimensions k and \ell as single bytes (this is the same encoding used
> by FIPS 203, but an explicit conversion function was already defined
> elsewhere in the internal working draft for FIPS 204 for domain
> separation between pure and prehash variants, so we plan to use it
> here as well).
>
>
>
> Best,
>
>
>
> Ray Perlner (NIST PQC team)
>
>
>

> --
> 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/DM6PR09MB4855D7840BE8CC4D8D796A2E9CF52%40DM6PR09MB4855.namprd09.prod.outlook.com.



--
Paul Duncan <pa...@pablotron.org>
https://pablotron.org/

[David A. Cooper]

In both FIPS 203 and FIPS 204 the key pair is deterministically generated from a single 32-byte random value. (FIPS 203 uses two 32-byte random values, but the second value (z) is not used in computing the public key). As this seed is much shorter than the expanded versions of the private keys, both documents allow for just the seed to be stored and for the private key to be regenerated from the seed as needed.

It is our understanding that formats for storing and transmitting private keys bind the private keys to the algorithms and parameter sets with which they are used. So, the risk of parameter set confusion appears to be small. However, given the simplicity of including domain separation into FIPS 203 and FIPS 204, and the positive feedback received for it, NIST decided to include this in the final version of these standards.

In FIPS 205, the private key consists of three randomly generated values (SK.seed, PK.seed, and SK.prf), and a fourth value that is computed from SK.seed and PK.seed (PK.root). While there would be security risks if the same SK.seed and PK.seed were used with two different parameter sets, introducing domain separation would involve more of a change to FIPS 205 than it did to FIPS 203 or FIPS 204.

With SLH-DSA the stored or transmitted version of the private key should include all four values. Before a system uses a key pair it should either regenerate PK.root and check the result against the stored value or generate and verify a signature. Either method will ensure that the parameter set being used is the same as the one used to generate the key pair.

[Robin Larrieu]

Dear all,

From what I understand from the last message regarding FIPS 203 and FIPS-204, the standards are going to document two encodings:
- an expanded version with the serialized secret vectors (among other things)
- a compact version with just a seed
If this is the case, I think it could be useful to make conversions possible in both directions. Compact to expanded is easy (just replay the key generation), but the other way around is not possible as of now, so may I suggest to include the seed in the expanded version of the private key as well ?

Regarding FIPS 205 (SLH-DSA), the "address" included in each hash computation already provides some form of domain separation. If domain separation between parameter sets is deemed important enough, it seems to be not that much of a change to include a parameter set identifier inside this address. At least I would prefer this rather than imposing key management practices that are different for SLH-DSA and ML-DSA, for crypto-agility reasons (the pure- v.s. prehash- distinction already imposes a special treatment specific to FIPS algorithms, but I would expect to at least be uniform across FIPS algorithms)

Currently, there are 4 bytes reserved for the address type (1 byte in the sha2 version), which can only take the values 0 to 6. So there is room, for example:
- in the shake version, use 2 bytes for the parameter set identifier, and 2 bytes for the the address type
- in the sha2 version, use 4 bits for the parameter set identifier, and 4 bits for the address type
This is sufficient to differentiate all 12 parameter sets, without changing the total size of the address. Considering there is already inherent domain separation between 128/192/256 security levels (seeds have a different size), and between sha2 and shake variants (different hash functions), using a single bit to distinguish between "s" and "f" parameter sets could even be sufficient; this would leave room for the possible future "few signatures per keypair" parameter sets.

Alternatively, the signature generation can produce the root of the hypertree as a byproduct (in FIPS 205 / Algorithm 11 - ht_sign, replace "return SIG_HT" by "return root, SIG_HT"). Then it is easy to check that root matches PK.root, and destroy the signature + return an error if not. This check can be done for each signature with negligible cost, which avoids the proposed key management constraint.

Best regards,
Robin Larrieu

To view this discussion on the web visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/2859dfe2-67a1-4b81-9939-10cb39b112b2%40nist.gov.

[Samuel Lee]

I agree with Robin that ideally the expanded decapsulation key blobs for ML-KEM should contain the private seed (and similar for ML-DSA), to avoid having 3 forms of key object (private key w/ private seed,  private key w/out private seed, and public key).

It is a weird and easily avoidable detail with the proposed ML-KEM API, that if someone imports a key from a decapsulation key blob they cannot export it as a private seed.

No comment on the SLH-DSA part as I have not dug into that spec.

Best,

Sam

[Guillaume Endignoux]

On Monday, June 3, 2024 at 11:08:24 PM UTC+2 Samuel Lee wrote:

I agree with Robin that ideally the expanded decapsulation key blobs for ML-KEM should contain the private seed (and similar for ML-DSA), to avoid having 3 forms of key object (private key w/ private seed,  private key w/out private seed, and public key).

It is a weird and easily avoidable detail with the proposed ML-KEM API, that if someone imports a key from a decapsulation key blob they cannot export it as a private seed.

A problem with storing both the private seed and the expanded values in the same object -- and transmitting this object between programs -- is that it introduces ambiguity in the representation.

In particular, what happens when the expanded values don't match the seed? What should receiving programs do?

1. Use the object as is without validation, in which case some program A may directly use the expanded values while program B would recompute them from the seed, leading to A and B having incompatible views of the key.

2. Recompute the values from the seed to validate that the expanded values are indeed consistent.

This is what David referred to for SLH-DSA as "Before a system uses a key pair it should either regenerate PK.root and check the result against the stored value or generate and verify a signature".

Except that the wording "it should" doesn't preclude systems that (IMO incorrectly) don't do this check.

In case (2), storing and transmitting the expanded values is superfluous as they are re-computed anyway, which not only incurs performance overhead (more bytes to transmit the pre-expanded values) but also introduces more complexity in the system, as there is now a new error type to handle when the values are inconsistent with the seed.

My take is that we'd be better off with a single unambiguous portable representation between systems (and I support using a single private seed for that), and leaving systems the possibility of using an expanded format of their own choosing within their own boundaries (be it expanded values in RAM within a single program, or possibly in some persistent storage in cases where performance really justifies it and that said persistent storage is within well-delimited boundaries of the system).

To make things more concrete, the current draft for ML-DSA defines a format for private keys that is neither reduced to a seed nor fully expanded, as some values (e.g. the secret vectors s1, s2) are already expanded (although bit-compressed) while others are not (the matrix is still described by its seed rho).

In some cases (where enough RAM is available), a more optimal internal representation would be to store the fully expanded matrix in NTT form, and the s1 and s2 vectors in NTT form as well (the signing procedure doesn't use them in non-NTT form).

In other cases (such as embedded systems [1, 2]), re-computing each row of the matrix on the fly may be preferable to reduce memory usage, so an internal representation would use rho for the matrix.

In practice there is a whole spectrum of trade-offs, and standardizing that the expanded form of the private key is (rho, K, tr, s1, s2, t0) is making a choice on that spectrum, which optimizes for specific use cases (namely: keep key generation fast by only storing values that are strictly necessary to compute the public key, but also drop the expanded matrix and compress the secret values because we can afford a few KB but not a few dozen KB).

Best,

Guillaume

[1] https://eprint.iacr.org/2022/1225

[2] https://github.com/google/OpenSK/tree/hybrid-pqc/third_party/dilithium

[Robin Larrieu]

Let me just expand/clarify my thought process.
David Cooper (NIST) wrote earlier "As this seed is much shorter than the expanded versions of the private keys, both documents *allow* for just the seed to be stored and for the private key to be regenerated from the seed as needed."
The keyword "allow" seems to indicate that NIST considers standardizing both formats, and it is not clear which one would be the primary portable format. I am fine with either, but the general consensus seems to be that "just the seed" is better. Nonetheless, NIST may have good reasons to keep the current expanded format as well; an example you mentioned on another thread (https://groups.google.com/a/list.nist.gov/g/pqc-forum/c/9nVfHKtid-k/m/_yx6wkytBQAJ) would be for testing. Indeed, specially hand-crafted private keys make it easier to exercise corner cases, but the seed for such keys may not be known or not exist at all.
For instance, the "seed" format could be the primary portable format, and the current "expanded" format could be a "suggested internal representation that implementations may/should/whatever support for extensive CAVP testing".

My point was that *if both formats are going to be documented in the standard*, back and forth conversions should be possible, so the seed should be included in the expanded format. More generally, I would say that the primary portable key format (whatever it is) should be recoverable from any implementation-defined internal format.

[D. J. Bernstein]

'Guillaume Endignoux' via pqc-forum writes:
> My take is that we'd be better off with a single unambiguous portable
> representation between systems (and I support using a single private seed
> for that), and leaving systems the possibility of using an expanded format
> of their own choosing within their own boundaries (be it expanded values in
> RAM within a single program, or possibly in some persistent storage in
> cases where performance really justifies it and that said persistent
> storage is within well-delimited boundaries of the system).

Outside HSMs etc., I'm not sure how software would figure out that its
private keys _aren't_ being sent (legitimately) between systems.

A NAS box, for example, is another computer running a networked file
system. If a program stores a private key on a NAS---which doesn't have
to be explicit; swapping can put any program into this situation---then
its data is being sent between systems.

Maybe "between systems" is intended to have an exception for data that
the first system encrypts only to itself, not readable by the second
system? But this exception doesn't work if, e.g., a program is in a VM
being migrated from one system to another; the whole point is for the
second system to start running the software.

The exception also doesn't work for programs split into network
microservices. A remote procedure call is supposed to be running on
another system. Programs have all sorts of complicated data structures
sent via RPC, including all sorts of confidential data. In principle one
can imagine a type system forcing all private-key formats to be
converted to a single format for RPC, but realistically this is going to
have all sorts of exciting failure cases unless those other formats end
up being basically eliminated---visible only for temporary variables
inside a few cryptographic subroutines.

If the only issues at hand are performance questions of decompression
time vs. uncompressed space, programmers will make their own decisions.
But my understanding is that the push to use seeds is being driven by
recent claims of some sort of security risk of expanded key formats. It
remains unclear to me (1) what the security risk is supposed to be and
(2) why this risk is triggered by some keys and not others.

---D. J. Bernstein

[Bobby McGee]

This thread's a bit tedious, so here's a summary

Seed pros:

1. "Proves" the key is well-formed

2. Short

Seed cons:

1. Needs to be expanded

2. No context

3. Can't easily find seeds that produce interesting test cases

Expanded pros:

1. Ready to use

2. Easier to manipulate (say for testing edge cases)

Expanded cons:

1. Apparently doesn't bind the implicit rejection key or something (I didn't read "Unbindable Kemmy Schmidt"), allows some form of tampering?

2. Big