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

[David Benjamin <[e-mail]>]

ASN.1 structures are for defining interchange formats, not in-memory
representations. Indeed, I expect in-memory representation of one of these
keys will often include the expanded matrix, so that repeat operations
don't need to compute it twice. These are very different use cases and we
shouldn't conflate them.

In an in-memory representation, redundant information may be a useful time
vs space trade-off to avoid computing some intermediate value multiple
times.
In an interchange format, redundant information adds complexity because now
one needs to answer silly questions like "what happens if the seed and
(partially) expanded private key are inconsistent" and check them for
consistency.

Case in point, the ECPrivateKey ASN.1 structure includes the public key,
but is optional. This has been a mess. When the public key is missing, we
need to compute it because our APIs want to have both. When the public key
is present... we *still* need to compute it to avoid getting into a
self-inconsistent state, and then need to check it. It just adds complexity.

On Thu, Aug 22, 2024 at 4:35 PM Mike Ounsworth <[e-mail]>
wrote:

> The reason for storing both seed and private key is because that’s how you
> get yourself into the trouble where you import a key (seed), expand it,
> drop the seed, and can’t export it again. The reason for a SeedAndFull is
> to give a data structure that encourages implementers to hang on to the
> seed even if they are only using the full version. Transmitting both is
> only wasteful by ~ 32 bytes.
>
>
>
> ---
>
> *Mike* Ounsworth
>
>
>
> *From:* Blumenthal, Uri - 0553 - MITLL <[e-mail]>
> *Sent:* Thursday, August 22, 2024 3:27 PM
> *To:* Mike Ounsworth <[e-mail]>; David Benjamin <
> [e-mail]>; Bas Westerbaan <[e-mail]>
> *Cc:* LAMPS <[e-mail]>
> *Subject:* Re: [EXT] [lamps] Re: [EXTERNAL] Re: Seed as private key for
> ML-DSA and ML-KEM
>
>
>
> IMHO, it does *not* make sense to send both seed *and* private key. I’m
> fully for sending/storing seed only, but don’t want to preclude “weird”
> (from y point of view) apps that insist on storing (or sending???) the
> private key itself.
>
>
>
> Thus, in your ASN.1 below, I’d kill option [2].
>
>
>
> TNX
>
> --
>
> V/R,
>
> Uri
>
>
>
>
>
> *From: *Mike Ounsworth <Mike.Ounsworth=[e-mail]>
> *Date: *Thursday, August 22, 2024 at 16:24
> *To: *David Benjamin <[e-mail]>, Bas Westerbaan <
> bas=[e-mail]>
> *Cc: *LAMPS <[e-mail]>
> *Subject: *[EXT] [lamps] Re: [EXTERNAL] Re: Seed as private key for
> ML-DSA and ML-KEM
>
> Observation: you can trivially go from seed -> full key, but not full key
> --> seed.  – at least I’m not seeing anything in FIPS 203 Algorithm 13 that
> the seed `d` is included in the decryption key `dk_pke`.
>
>
>
> As the guy whose company gets called in when people have broken their
> on-prem PKIs, if we only allow seeds in P12’s, then I foresee problems
> where an HSM company goes out of business and we need to get keys out of
> that hardware, and they chose to only store the expanded private key and so
> can’t give us the seed even if we ask nicely: now we can’t use standard
> private key transports and will have to kludge something. The point of a
> standard is to be standard – to say that you’re allowed to store the key
> expanded internally, but then you’ll be up a creek without a paddle if you
> want to export it, feels wrong.
>
>
>
>
>
> “2. Allow both seed and the expanded private key” ends up looking
> something like this:
>
> This would certainly not be the most complicated thing in RFC 5912.
>
>
>
> ML-*-PrivateKey ::= CHOICE {
>
>    seed               [0] SIZE 32 OCTET STRING,
>
>    full                  [1] OCTET STRING,
>
>    seedAndFull   [2] SeedAndFull
>
> }
>
>
>
> SeedAndFull ::= SEQUENCE {
>
>    seed   SIZE 32 OCTET STRING,
>
>    full      OCTET STRING
>
> }
>
>
>
> ---
>
> *Mike* Ounsworth
>
>
>
> *From:* David Benjamin <[e-mail]>
> *Sent:* Wednesday, August 21, 2024 1:04 PM
> *To:* Bas Westerbaan <bas=[e-mail]>
> *Cc:* LAMPS <[e-mail]>
> *Subject:* [EXTERNAL] [lamps] Re: Seed as private key for ML-DSA and
> ML-KEM
>
>
>
> I'm also sold on option 4. On Wed, Aug 21, 2024, 11: 50 Bas Westerbaan
> <bas=40cloudflare. com@ dmarc. ietf. org> 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
>
> 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]
>
>