[lamps] Re: Seed as private key for ML-DSA and ML-KEM

[Phillip Hallam-Baker <[e-mail]>]

Every time I get COVID, I seem to end up discussing RSA keygen with you. I
probably missed a step in the explanation.


It is quite a while since I wrote the code. I was very tempted to do the
optimization you suggest. However, as you point out, you need two seeds,
not one. I rejected it after being pointed to a NIST recommendation for
generating RSA key pairs.

So from the spec, I have

HKDF-Extract(salt, IKM) -> PRK
HKDF-Expand(PRK, info, L) -> OKM
info = alg + param + keyname.UTF8()


So basically, I set up a HKDF using the seed and a salt. Then use it to
churn out the parameters I need which in this case have tags 'p' and 'q'.

So having generated an initial p, you find the closest prime equal or
larger and then do that for q.


One option would be the partial optimization for p but not for q.

If we were going for the full optimization, I would generate random IKM to
generate p as above and then generate a series of q candidates from the
HKDF using the tag 'q0', 'q1',...'q<n>' until we get a prime. Then I would
insert the prime into the UDF string using the JSON-B integer encoding.

I agree it is probably unnecessary but since some of my devices are
Raspberry Pi nanos and ESP32 like things, avoiding the need to do RSA
keygen on them might actually be a win.



On Wed, Aug 21, 2024 at 5:32 PM Sophie Schmieg <[e-mail]> wrote:

> This is now very off-topic, but if you sample both p and q from the same
> seed you either would make your keygen take a lot longer (you now need to
> find seeds that produce two large primes without rejecting, expected number
> of iterations (ln(n/2))^2 instead of 2*ln(n/2)), or you would still have to
> rejection sample when expanding the seed.
>
> On Wed, Aug 21, 2024 at 1:43 PM Phillip Hallam-Baker <
> [e-mail]> wrote:
>
>> Thanks, Scott. While I would like to avoid RSA and DH, it turns out that
>> there are still a surprising number of applications which require them. And
>> if like me, your scheme is designed to connect all a user's devices
>> together and squirt the credentials they need into them, it turns out RSA
>> is still required.
>>
>>
>> Generate from a single seed appears to be what I implemented:
>>
>>
>> https://www.ietf.org/archive/id/draft-hallambaker-mesh-udf-18.html#name-rsa-key-pairs
>>
>> If I was going to implement the keygen optimization Sophie suggested, I
>> would do it by means of an additional salt to be applied to one seed but
>> not the other.
>>
>>
>> On Wed, Aug 21, 2024 at 4:24 PM Scott Fluhrer (sfluhrer) <
>> [e-mail]> wrote:
>>
>>> Actually, if we’re going to keep on using RSA (“the height of 50 year
>>> old cryptography”), I would recommend not using separate seeds for p and q,
>>> as it leaves open a possible implementation flaw.
>>>
>>>
>>>
>>> What I believe has happened in the past is that when the implementation
>>> sampled the randomness for ‘p’, the entropy was lousy, but when it sampled
>>> the randomness for ‘q’, it got better.  What happens in that case, if we
>>> generate a number of keys this way, that the keys will often have common
>>> ‘p’ values, but distinct ‘q’ values.  I believe that was exactly what
>>> happened in the ‘Mind your P’s and Q’s’ paper by Nadia.
>>>
>>>
>>>
>>> Because of this, both primes should be selected from the same seed –
>>> that way, if entropy is lousy, you’ll pick the same RSA key repeatedly –
>>> admittedly, not great, but better than the previous scenario.
>>>
>>>
>>>
>>> *From:* Phillip Hallam-Baker <[e-mail]>
>>> *Sent:* Wednesday, August 21, 2024 3:53 PM
>>> *To:* Sophie Schmieg <sschmieg=[e-mail]>
>>> *Cc:* David Benjamin <[e-mail]>; Bas Westerbaan <bas=
>>> [e-mail]>; LAMPS <[e-mail]>
>>> *Subject:* [lamps] Re: Seed as private key for ML-DSA and ML-KEM
>>>
>>>
>>>
>>> +1
>>>
>>>
>>>
>>> If we were likely to do a lot of RSA, this is vastly superior to the p/q
>>> approach because it prevents the kleptography attacks Motti Yung described.
>>> If you generate p in the normal fashion, you can generate q in such fashion
>>> that the high bits of the modulus leak the (encrypted) seed. An alternative
>>> approach is to use this scheme to compress the modulus
>>>
>>>
>>>
>>> And being reminded of that, I think we have a security reason to insist
>>> on representing the private key as the seed as opposed to the expanded
>>> private key because it means we block an ML variant of Motti's attacks. I
>>> managed to get C19 a few weeks back and still not quite up to thinking what
>>> those attacks might be but why spend time thinking about a possible attack
>>> we can easily avoid?
>>>
>>>
>>>
>>> So it has to be 4, we should reject 1 and 2 on security grounds so 3 is
>>> irrelevant.
>>>
>>>
>>>
>>>
>>>
>>>
>>>
>>>
>>>
>>> On Wed, Aug 21, 2024 at 3:24 PM Sophie Schmieg <sschmieg=
>>> [e-mail]> wrote:
>>>
>>> For completeness sake, and not to argue for it, you can extend the
>>> private key as seeds paradigm to RSA as well, without destroying
>>> performance, by rejection sampling seeds for p and q until they are both
>>> prime, and serialize the private key as seed_p || seed_q. It would give you
>>> a 64 byte RSA private key, and the expansion would skip over the most
>>> expensive part of RSA keygen without sacrificing the security
>>> gains, assuming you redo the primality check of p and q.
>>>
>>> But practically speaking, I would prefer to not touch RSA serialization.
>>>
>>>
>>>
>>> On Wed, Aug 21, 2024 at 11:04 AM David Benjamin <[e-mail]>
>>> wrote:
>>>
>>> I'm also sold on option 4.
>>>
>>> On Wed, Aug 21, 2024, 11:50 Bas Westerbaan <bas=
>>> [e-mail]> wrote:
>>>
>>> Hi all,
>>>
>>>
>>>
>>> NIST allows two formats in which private keys are stored ML-DSA and
>>> ML-KEM.
>>>
>>>
>>>
>>> 1. Seed. 32 bytes for ML-DSA; 64 bytes for ML-KEM.
>>>
>>> 2. Expanded private key. Multiple kilobytes depending on instance.
>>>
>>>
>>>
>>> An expanded private key is obtained from the seed by calling the
>>> KeyGen_internal function.
>>>
>>>
>>>
>>> In contrast to RSA, key generation for these algorithms is very fast. In
>>> fact, if you use spinning disks, then using a seed is probably faster than
>>> the expanded private key.
>>>
>>>
>>>
>>> Another advantage is that we do not need to worry about private key
>>> validation. NIST specified a few checks to perform, but there are more we
>>> could do (eg. whether the decoded coefficients of \hat{s} are bounded.)
>>>
>>>
>>>
>>> Of course a big advantage is storage space: the seeds are much smaller.
>>>
>>>
>>>
>>> Now, how do we want to proceed? I see a few options.
>>>
>>>
>>>
>>> 1. Ignore the seed as private key.
>>>
>>>
>>>
>>> 2. Allow both seed and the expanded private key.
>>>
>>>
>>>
>>> 3. Assign separate algorithm for seed-as-private-key.
>>>
>>>
>>>
>>> 4. Switch to seed as private key only.
>>>
>>>
>>>
>>> I prefer 4, and would otherwise go for 1.
>>>
>>>
>>>
>>> The downside of 2 is that it adds complexity without the gain of
>>> simplifying verification. If one only cares about size savings, then one
>>> can use seed-as-private-key without needing a portable format for it.
>>>
>>>
>>>
>>> So I'd prefer 4 and 1 second.
>>>
>>>
>>>
>>> Best,
>>>
>>>
>>>
>>>  Bas
>>>
>>> _______________________________________________
>>> Spasm mailing list -- [e-mail]
>>> To unsubscribe send an email to [e-mail]
>>>
>>> _______________________________________________
>>> Spasm mailing list -- [e-mail]
>>> To unsubscribe send an email to [e-mail]
>>>
>>>
>>>
>>>
>>> --
>>>
>>>
>>> Sophie Schmieg | Information Security Engineer | ISE Crypto |
>>> [e-mail]
>>>
>>>
>>>
>>> _______________________________________________
>>> Spasm mailing list -- [e-mail]
>>> To unsubscribe send an email to [e-mail]
>>>
>>>
>
> --
>
> Sophie Schmieg | Information Security Engineer | ISE Crypto |
> [e-mail]
>
>