ML-KEM: usage of seed for key pair generation

[Stephan Mueller]

Hi,

FIPS 203 section 3.3 allows the storing of the seed data used for the ML-
KEM.KeyGen_internal in lieu of the actual key pair itself. The ML-KEM key pair
can be re-constructed from that seed using the ML-KEM.KeyGen_internal at a
later time.

Algorithm 19 defines ML-KEM.KeyGen requiring the generation of 2 random
numbers for d and z, each having 32 bytes in lines 1 and 2. I.e. this is the
seed that is allowed to be stored in lieu of the actual key pair (or the
decapsulation key at least).

Section 3.3 defines that the term "m <- B^32" as used in lines 1 and 2 of
Algorithm 19 specifies the generation of 32 bytes generated from the RBG.

This implies that the standard requires the seed to be ultimately requiring 64
bytes of data from the RBG.

The question I would have is the following: Considering section 3.3 the RBG
security strength is 128/192/256 bits for ML-KEM 512/768/1024, can the
aforementioned generation of 64 bytes of data from an RBG be replaced with
generating the security strength size data from the RBG and using an approved
KDF (SP800-108 / SP800-56C) to enlarge the data to the requested size of 64
bytes?

If yes, that would imply that the actual seed to be stored is only of the
security strength size of the used ML-KEM instead of 64 bytes.

The basis for the argument is that the output of the RBG is min(security
strength, generated data size). Considering that for ML-KEM the seed data is
always strictly larger than the security strength of the RBG, the resulting
data is still only having the RBG security strength. Thus, the data
"stretching" from the security strength to the ML-KEM seed size
cryptographically is requivalent if that stretching comes from the RBG or from
a KDF. Naturally, this implies that the used KDF has the same or higher
security strength than the used RBG.

Ciao
Stephan

[Tony Arcieri]

On Wednesday, August 28, 2024 at 8:20:09 AM UTC-6 Stephan Mueller wrote:

The question I would have is the following: Considering section 3.3 the RBG
security strength is 128/192/256 bits for ML-KEM 512/768/1024, can the
aforementioned generation of 64 bytes of data from an RBG be replaced with
generating the security strength size data from the RBG and using an approved
KDF (SP800-108 / SP800-56C) to enlarge the data to the requested size of 64
bytes?

I believe that was explored in section 3.3 of https://eprint.iacr.org/2024/523.pdf

"The serialization format of the private key can in general be seen as a cache of the output of KeyGen under a given seed. If deserialization instead recomputed the whole private key via the initial seed, computing a malformed private key would be impossible. This option is also the only option to obtain MAL-BIND-K-PK, as long as z is not drawn independently of the rest of the seed. Unfortunately, this would require further modification of ML-KEM, computing σ, ρ, and z from a single seed being used in a KDF instead of, as is currently done, using two separate seeds."

[Stephan Mueller]

Am Freitag, 6. September 2024, 14:53:44 GMT-5 schrieb Phillip Hallam-Baker:

Hi Phillip,

> OK so here is the attack I am considering:
>
> 1) Consider a sealed HSM that generates a series of public keypairs for
> different purposes.
>
> 2) HSM has a 256 bit internal primary seed s which is used to generate
> seeds in combination with a counter sn = KDF (seed, count++)
>
> 3) HSM generates the private key first and then creates a series of public
> keys from random noise seeds until it finds one that matches the criteria
> that if you take an HMAC of the public key using a 'recovery secret' value
> r, the first 8 bits of the result match one byte in the seed s, and the
> next 8 are the byte 0_000xxxxx where xxxxx gives the location of the byte
> in the seed. This will typically take 65K attempts.
>
> So the attacker simply watches and waits for public keys to be published.
> Each time a key is published, they first check to see if it has the signal
> flag saying it is a recovery secret and if so, they have a candidate byte
> in the seed.
>
> Each byte leaked from the seed reduces the search space by 8 bits. If the
> HSM is being used to generate 50 keys, the search space will be
> sufficiently reduced to make an attack possible.

Thank you for sharing this. But my concern is slightly different, considering
that FIPS 203 explicitly says the seed must come from an RBG and not from a
plain KDF which provides seed data for different ML-KEM keys.

My concern is more along the lines what FIPS 203 says: a fresh random number
is to be generated from an RBG each time a new key pair is created. However,
instead of wanting to store the key pair or the private key, storing the seed
is allowed. All I am asking is whether instead of storing 64 bytes from an
RBG, I can store 32 bytes from an RBG and expand the 32 bytes to 64 bytes
using a KDF to regenerate the one given key pair the seed applies to.

Ciao
Stephan

[Phillip Hallam-Baker]

Yes, and I just improved on my attack so I can do the same thing if there is a 32 byte key expanded to 64 bytes..!

[Deirdre Connolly]

> I am asking is whether instead of storing 64 bytes from an
RBG, I can store 32 bytes from an RBG and expand the 32 bytes to 64 bytes
using a KDF to regenerate the one given key pair the seed applies to.

I would also really like this to be a supported/compliant way to store seeds and expand the keys from them.

--
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/2098567.mTc0TySc1m%40tauon.atsec.com.

[Blumenthal, Uri - 0553 - MITLL]

Count me in on this. 

—

Regards,

Uri

Secure Resilient Systems and Technologies

MIT Lincoln Laboratory

On Sep 6, 2024, at 16:51, Deirdre Connolly <durumcr...@gmail.com> wrote:



> I am asking is whether instead of storing 64 bytes from an RBG, I can store 32 bytes from an RBG and expand the 32 bytes to 64 bytes using a KDF to regenerate the one given key pair the seed applies to. I would also really like this to

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/CAFR824yj9Tc3-8TbTTqmxVqeK7jYNPKkSHJNGEbU9KAKcFWFmg%40mail.gmail.com.

[Tony Arcieri]

On Fri, Sep 6, 2024 at 2:51 PM Deirdre Connolly <durumcr...@gmail.com> wrote:

I would also really like this to be a supported/compliant way to store seeds and expand the keys from them.

It seems like the one tricky detail here is the exact DRBG used to expand a "short seed".

--

Tony Arcieri

[Deirdre Connolly]

KDF? 

[Deirdre Connolly]

One of the SHAKEs is probably good

[Orie Steele]

HKDF with sha256? 

https://datatracker.ietf.org/doc/html/rfc5869

Is there some known attack when d / z are expanded from each other? 

Is that what's being discussed here?

--

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/CAFR824xp0friNgn4LM%3D0Ef8T3ciQ2WAp%2BL-Gwa4XEFj%3DSA6F2w%40mail.gmail.com.

[Phillip Hallam-Baker]

I don't see that as being at all hard. It pretty much has to be SHAKE256 because that is what we are using in the rest of the code.

[

[Phillip Hallam-Baker]

On Fri, Sep 6, 2024 at 5:34 PM Orie Steele <or...@transmute.industries> wrote:

HKDF with sha256? 

https://datatracker.ietf.org/doc/html/rfc5869

Is there some known attack when d / z are expanded from each other? 

Is that what's being discussed here?

Kind of. I started thinking up some kleptographic attacks and I could keep on doing that. But 'PHB can't think of an attack right now' is not exactly a great test. I am being a bit distracted by a series of indictments dropping on some very very bad people I played a part in identifying as such seven years ago.

We could argue about just how likely it is someone finds a way to manipulate the noise mask or we can just shut them down completely.

Stopping a key generator leaking internal state through the public key is much harder. But minimizing the number of degrees of frob is probably going to make attempts to partition the system so as to block the attacks a lot easier.

Of course, this whole class of attacks is one that I address for ECC algorithms in the Mesh through use of threshold key generation.It is quite easy to generate two separate private keys and combine them so that the resulting combination public key does not leak internal state. Which means two devices have to be compromized.

 

[Phillip Hallam-Baker]

I think we need to go for rigid construction of all private keys with a one way digest between a single input seed and the private key values. Not just for ML-KEM, ML-DSA and such, we should go back and fix RSA which has some really fun channels for kleptography.

I am not sure that allowing the use of two seeds instead of one gives an attacker sufficient leverage to make an attack feasible. But it certainly allows them to leak information from inside the HSM and if multiple public keys are being generated, they can leak 16 bits at a time without too much overhead.

Lets just stamp it out.

--

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/058b1499-9fef-449e-8cde-ee2184beecd2n%40list.nist.gov.

[Phillip Hallam-Baker]

OK so here is the attack I am considering:

1) Consider a sealed HSM that generates a series of public keypairs for different purposes. 

2) HSM has a 256 bit internal primary seed s which is used to generate seeds in combination with a counter sn = KDF (seed, count++)

3) HSM generates the private key first and then creates a series of public keys from random noise seeds until it finds one that matches the criteria that if you take an HMAC of the public key using a 'recovery secret' value r, the first 8 bits of the result match one byte in the seed s, and the next 8 are the byte 0_000xxxxx where xxxxx gives the location of the byte in the seed. This will typically take 65K attempts.

So the attacker simply watches and waits for public keys to be published. Each time a key is published, they first check to see if it has the signal flag saying it is a recovery secret and if so, they have a candidate byte in the seed.

Each byte leaked from the seed reduces the search space by 8 bits. If the HSM is being used to generate 50 keys, the search space will be sufficiently reduced to make an attack possible.

So generate the seeds using an extra SHAKE, its the obvious solution.

[Tony Arcieri]

On Fri, Sep 6, 2024 at 2:10 PM Stephan Mueller <smue...@chronox.de> wrote:

But my concern is slightly different, considering
that FIPS 203 explicitly says the seed must come from an RBG and not from a
plain KDF which provides seed data for different ML-KEM keys.

My concern is more along the lines what FIPS 203 says: a fresh random number
is to be generated from an RBG each time a new key pair is created. However,
instead of wanting to store the key pair or the private key, storing the seed
is allowed. All I am asking is whether instead of storing 64 bytes from an
RBG, I can store 32 bytes from an RBG and expand the 32 bytes to 64 bytes
using a KDF to regenerate the one given key pair the seed applies to.

Can NIST offer any guidance here? Is there any approved construction for expanding a 32-byte "short seed" into 64-bytes? Particularly in a way where the 32-byte seed can be persisted and expanded as needed? Would this be against the usage requirements of a DRBG due to the need to persist the "short seed", and if so, what would be an approved construction to use?

--

Tony Arcieri