[jose] Re: Algorithm identifiers for pre-hashing in two-party signing?

[Emil Lundberg <[e-mail]>]

Thank you Orie -


> I don't know if it's valid to say use -9 (or -7) but skip the hash step

Agreed, which is why I'm asking about what would be a reasonable way to
express it.

If you pass { to_be_signed, extra_info }, and then the end result is
> consistent with applying the alg, that seems fine to me... I think
> that's what you are aiming for.

Yes, this is what we're aiming for. The "but skip the hash step" variant of
the algorithm is indeed nonsensical on its own, it's only meaningful if
used in combination with the "hash step" already applied.

This seems to be more of an API issue than a protocol issue.

Yes. These algorithm identifiers should not appear in protocols between
signer and verifier, only in protocols between "digest preprocessor" and
"digest-less signer" which together make up the "signer" role (but each is
useless without the other).

I realize now that I probably didn't make it clear that the idea here is
that this is meant to be a public API between separate entities, like a
website developer and a security key manufacturer. That's why we clearly
need to define the separation of steps so that both parties can agree on
which steps are which party's responsibility. None of this would be needed
if these were all internal implementation details within a single entity.

The API you are hoping for is:
> ph_sign(key_identifier, hash_algorithm_already_applied,
> signature_algorithm_but_without_applying_hash,
> to_be_signed_and_already_hashed)
> [...]
> Does this match what you expected?

Yes, something to that effect. What we want is for this to work:

# User chooses message to sign
1. message_to_sign = "Queen Alice decrees that Bob be knighted"


# Client software pre-hashes the message
2. message_prehash = SHA256(message_to_sign)


# Cryptographic hardware resumes from step 2 of the ECDSA signature
algorithm
# Id is the identity function: Id = x => x
3. sig = ECDSA.Sign(Hash = Id, M = message_prehash, d = alice_private_key)


# Verifier software does not know or care about the prehash
4. valid = ECDSA.Verify(M = message_to_sign, (r, s) = sig, Q =
alice_public_key)


and analogously for other algorithms... but again, the problem is precisely
that "analogously" is ill-defined in general. It's obvious enough for
ESP256 since there's really only one way to separate the hash from the rest
of the algorithm, but for HashML-DSA for example I can think of at least 3
ways to split up the steps of HashML-DSA.Sign. Again noting that steps (2)
and (3) are computed by different entities, which is why we need some way
to declare exactly how the split is made.

There is a real risk of confusion if you sometimes use alg to mean "the
> full algorithm" and sometimes "the algorithm without the hash part".

Agreed, which is why we don't want to use -7 or -9 for this, for example.
That would work if we could define for this particular API that the
algorithm identifier always means "the algorithm without the hash part",
but again this doesn't work in general.

There is no "without the hash part" for Ed25519, but there is for Ed25519ph.

Agreed. Ed25519 simply won't be compatible with this API, but Ed25519ph can
be. Same for ML-DSA and HashML-DSA.

This strengthens the argument Mike made that we should consider fully
> specified pre hashed variants for fully specified signing algorithms... we
> need to be able to distinguish them.

I'm glad to hear it! I reduced the mockup document to just the parts
relevant to this discussion, and extended the explanations a bit. Please
take another look and see if this seems like a reasonable approach:
https://yubico.github.io/arkg-rfc/cose-two-party-sign-algs/draft-bradleylundberg-cfrg-arkg.htmlhttps://yubico.github.io/arkg-rfc/cose-two-party-sign-algs/draft-bradleylundberg-cfrg-arkg.html
<https://yubico.github.io/arkg-rfc/cose-two-party-sign-algs/draft-bradleylundberg-cfrg-arkg.html>

Cheers,

Emil Lundberg

Staff Engineer | Yubico <http://www.yubico.com/>




Den tors 3 okt. 2024 kl 21:06 skrev Orie Steele <[e-mail]>:

> As soon as I hit send I realized this part is wrong:
>
> kid, -16, -9, tbs_bytes_hashed_with_sha256
> kid, -44, -50, tbs_bytes_hashed_with_sha512
> kid, TBD_for_shake, -51, tbs_bytes_hashed_with_shake_256(details)
>
> The first one is SHA-256 with ECDSA using P-256 and SHA-256 but without
> the hash part applied.
> The second is SHA-512 with Ed25519 there is no hash part to not apply here.
> The third is SHAKE with Ed448, there is no hash part to not apply here.
>
> There is a real risk of confusion if you sometimes use alg to mean "the
> full algorithm" and sometimes "the algorithm without the hash part".
>
> There is no "without the hash part" for Ed25519, but there is for
> Ed25519ph.
>
> This strengthens the argument Mike made that we should consider fully
> specified pre hashed variants for fully specified signing algorithms... we
> need to be able to distinguish them.
>
> OS
>
> On Thu, Oct 3, 2024 at 1:57 PM Orie Steele <[e-mail]>
> wrote:
>
>> Ahh, I see.
>>
>> I don't know if it's valid to say use -9 (or -7) but skip the hash
>> step... skipping the hash step makes the algorithm you are calling not -7
>> or -9.
>>
>> If you pass { to_be_signed, alg } and then apply only part of the alg,
>> you are applying a different algorithm.
>>
>> If you pass { to_be_signed, extra_info }, and then the end result is
>> consistent with applying the alg, that seems fine to me... I think
>> that's what you are aiming for.
>>
>> This seems to be more of an API issue than a protocol issue.
>>
>> The API you are hoping for is:
>>
>> ph_sign(key_identifier, hash_algorithm_already_applied,
>> signature_algorithm_but_without_applying_hash,
>> to_be_signed_and_already_hashed)
>>
>> In the case of ESP256 an invocation would be:
>>
>> kid, -16, -9, tbs_bytes_hashed_with_sha256
>>
>> throw if the hash algorithm length doesn't match tbs bytes length
>> throw if the key does not support the signing algorithm (both the hash
>> and the signature part need to be checked)
>>
>> It's easy to imagine this working with ESP256 / ESP384...
>>
>> For Ed25519ph, you could use:
>>
>> kid, -44, -50, tbs_bytes_hashed_with_sha512
>>
>> For Ed448ph, you could use:
>>
>> kid, TBD_for_shake, -51, tbs_bytes_hashed_with_shake_256(details)
>>
>> Does this match what you expected?
>>
>> We would not need to register new signing algorithms unless there was no
>> (fully specified) signing algorithm registered that was compatible with a
>> registered hash algorithm.
>> We would need to register new hash algorithms, for any ph variant that
>> required hashing with some unregistered algorithm (like the shake example
>> above).
>>
>> We could establish a registry of cose algorithm pairs for use with pre
>> hashing, for example:
>>
>> TBD_3, -16, -9 for ESP256 with SHA-256 PH
>> TBD_4, -44, -50 for Ed25519 with SHA-512 PH
>> ...
>>
>> This would allow you to compress the 2 parameters to the api into a
>> single parameter... These could be registered as separate algorithms, and
>> it would avoid the "signature_algorithm_but_without_applying_hash"
>> awkwardness.
>> It also gives you the ability to commit the signature to the hash
>> algorithm used, in the case the algorithm identifier is in the protected
>> header (required in JOSE, optional in COSE).
>>
>> Perhaps it is worth a few extra registrations to achieve safer and easier
>> to use APIs for pre hashing in JOSE and COSE.
>>
>> OS
>>
>>
>>
>> On Thu, Oct 3, 2024 at 1:00 PM Emil Lundberg <[e-mail]> wrote:
>>
>>> Yes, the ARKG draft is in CFRG. I just put the "two-party signing
>>> algorithm identifiers" mockup there to have an easy way to show the idea,
>>> the rest of the document outside sections 5.3 and 5.2 are unrelated to this
>>> discussion.
>>>
>>> If you don't want domain separation, then you simply need to identify
>>>> registered algorithms,
>>>
>>>
>>> For the keys and the resulting cryptograms, yes. But that's not what my
>>> question was about.
>>>
>>> [...] where you can do the pre hash part separate from the signing part.
>>>
>>> [...]
>>>
>>> [...] but be careful, this does not generalize to other COSE digital
>>>> signature schemes, like Ed25519 / EdDSA.
>>>
>>>
>>> This is what I'm asking about - or, more precisely, how to communicate
>>> where the separation happens between "pre hash part" and "signing part".
>>> Like you point out, there's no way to describe that generically, especially
>>> since some algorithms like PureEdDSA and ML-DSA *can't* be separated
>>> like that.
>>>
>>> If you ask some remote kms / device for a key reference that can do "pre
>>>> hash with -16, sign with -7, on kty 1, with curve 1", you could get back a
>>>> key identifier which could resolve to a "almost fully specified cose key"
>>>
>>>
>>> I think you misunderstood the idea. What we want to express is rather
>>> "please sign this with -9, but I have already hashed it with -16, so please
>>> skip the hash step". The usual COSE/JOSE algorithm identifiers - whether
>>> fully specified or not - don't (and shouldn't) express this division of
>>> labour during signing, they only express what procedure a verifier should
>>> use to verify the resulting signature. The question is whether the mockup I
>>> linked seems like a good way to express "please skip the hash step" during
>>> signature generation.
>>>
>>> Emil Lundberg
>>>
>>> Staff Engineer | Yubico <http://www.yubico.com/>
>>>
>>>
>>>
>>>
>>> Den tors 3 okt. 2024 kl 19:11 skrev Orie Steele
>>> <[e-mail]>:
>>>
>>>> If you don't want domain separation, then you simply need to identify
>>>> registered algorithms, where you can do the pre hash part separate from the
>>>> signing part.
>>>>
>>>> Beware of the forgery potential if the hash function is broken in the
>>>> future.
>>>>
>>>> ESP256 is a good example of this.
>>>>
>>>> SHA-256 (message) -> ... -> ECDSA using P-256
>>>>
>>>> You might also consider
>>>> https://datatracker.ietf.org/doc/draft-ietf-cose-key-thumbprint/
>>>> Although it looks like you may need the kid parameter as part of the
>>>> ARKG construction...
>>>>
>>>> Without fully specified algorithms, you can still accomplish this, but
>>>> you need to manage the parameters as follows:
>>>>
>>>> cose_hash_alg: -16 / sha-256 /
>>>>
>>>> cose_key_sign_alg: -7 / ES256 (ECDSA with SHA-256 prehash on ANY CURVE)
>>>> /
>>>> cose_key_kty: 2 / EC2 /
>>>> cose_key_crv: 1 / P-256 /
>>>>
>>>> If you ask some remote kms / device for a key reference that can do
>>>> "pre hash with -16, sign with -7, on kty 1, with curve 1", you could get
>>>> back a key identifier which could resolve to a "almost fully specified cose
>>>> key" (an api could error if you asked for pre hash with -16 (SHA-256) but
>>>> sign with -35 (ES384) for example):
>>>>
>>>> / cose key / {
>>>>  / kid /  2 : h'4741579f...e6cc42ef', / maybe computed from the
>>>> thumbprint draft above /
>>>>  / kty /  1 : 2, / EC2 /
>>>>  / alg /  3 : -7, / -9 for ESP256 (either way -16 pre hash is implied) /
>>>>  / crv / -1 : 1, / P-256 /
>>>>  / x   / -2 : h'c7282bcb...3328dd7d',
>>>>  / y   / -3 : h'e37ad72f...31f6edc2',
>>>>  / d   / -4 : h'88aa8624...b8ce1856', / only if its exportable /
>>>> }
>>>>
>>>> In this example, both -7 or -9 (requested assignment for ESP256) imply
>>>> pre-hash with -16 .... but be careful, this does not generalize to other
>>>> COSE digital signature schemes, like Ed25519 / EdDSA.
>>>>
>>>> The key blinding stuff you have in Section 3.1 feels like it belongs in
>>>> a CFRG document.
>>>>
>>>> I wonder if it's possible to get ARKG to work while colliding on
>>>> existing kty or kid assignments.
>>>>
>>>> You could introduce some structure to kid (which is bstr / tstr) to
>>>> accomplish this: (ARKG params (including kty stuff if needed) + (normal
>>>> thumbprint)
>>>>
>>>> Interesting draft.
>>>>
>>>> OS
>>>>
>>>>
>>>>
>>>>
>>>>
>>>> On Thu, Oct 3, 2024 at 11:39 AM Emil Lundberg <[e-mail]> wrote:
>>>>
>>>>> Hi Mike and Orie, thank you for your replies (see Orie's reply on
>>>>> GitHub
>>>>> <https://github.com/w3c/webauthn/pull/2078#issuecomment-2364535837>).
>>>>> I've now had some time to digest them (pun intended) and consider how to
>>>>> proceed.
>>>>>
>>>>> I agree that distinct algorithm identifiers seems like a suitable
>>>>> solution for this. I mocked up an outline of the idea, including a few
>>>>> examples of what this might look like for a couple of algorithms, which you
>>>>> can see here for the time being:
>>>>> https://yubico.github.io/arkg-rfc/cose-two-party-sign-algs/draft-bradleylundberg-cfrg-arkg.html#name-temporary-cose-algorithms-f
>>>>> (This address is temporary, we'll move the draft somewhere more
>>>>> appropriate when the ideas are more mature)
>>>>> The relevant section is "5.3. TEMPORARY: COSE algorithms for two-party
>>>>> signing", but it also lightly ties into the preceding section "5.2. COSE
>>>>> key reference types" for things like the *ctx* parameter in
>>>>> HashML-DSA.
>>>>> Perhaps this better illustrates what we're trying to do.
>>>>>
>>>>> As noted in the introduction section, this is subtly different from
>>>>> COSE Hash Envelope (CHE), for example, if I understood CHE correctly. We
>>>>> deliberately want to *avoid* domain-separating these signatures, and
>>>>> avoid an additional protocol-level hash layer. The hope is to be able to
>>>>> generate signatures that look the same as usual, and verify the same as
>>>>> usual, but without having to send the entire original message to the
>>>>> cryptographic hardware that holds the private key. These algorithm
>>>>> identifiers therefore wouldn't appear on signature structures or keys, as
>>>>> those would still be tagged with the existing identifier for the usual
>>>>> signature (verification) algorithm.
>>>>>
>>>>> This would enable our WebAuthn raw signing extension to output
>>>>> signatures that can be fed into existing verifiers, without needing to
>>>>> adapt those verifiers and cryptographic protocols to accomodate a
>>>>> protocol-level prehash. This also enables structuring the extension such
>>>>> that the WebAuthn Relying Party and authenticator (e.g., security key) can
>>>>> negotiate a two-party signature algorithm without needing the WebAuthn
>>>>> client (browser) to support it - the client just passes the data through.
>>>>>
>>>>> Please have a look at the mockup link above. Does this (and the
>>>>> related COSE_Key_Ref idea) seem like a reasonable approach?
>>>>>
>>>>> Emil Lundberg
>>>>>
>>>>> Staff Engineer | Yubico <http://www.yubico.com/>
>>>>>
>>>>>
>>>>>
>>>>>
>>>>> Den ons 25 sep. 2024 kl 00:29 skrev Michael Jones <
>>>>> [e-mail]>:
>>>>>
>>>>>> Thanks for writing, Emil.  Here are my thoughts.
>>>>>>
>>>>>>
>>>>>>
>>>>>> I would not suggest trying to generically extend the JOSE and COSE
>>>>>> signing structures with additional parameters, such as creating a signing
>>>>>> request data structure.  It would be much simpler and more aligned with how
>>>>>> JOSE and COSE work to define new algorithm identifiers for the additional
>>>>>> needed functionality.  These should go into the existing registries for
>>>>>> JOSE
>>>>>> <https://www.iana.org/assignments/jose/jose.xhtml#web-signature-encryption-algorithms>
>>>>>> and COSE
>>>>>> <https://www.iana.org/assignments/cose/cose.xhtml#header-algorithm-parameters>
>>>>>> .
>>>>>>
>>>>>>
>>>>>>
>>>>>> As you probably already know, pre-hash algorithm identifiers for
>>>>>> Ed25519 and Ed448 are not currently registered for JOSE
>>>>>> <https://www.iana.org/assignments/jose/jose.xhtml#web-signature-encryption-algorithms>
>>>>>> or COSE
>>>>>> <https://www.iana.org/assignments/cose/cose.xhtml#header-algorithm-parameters>.
>>>>>> I suggest creating them in a new specification.  I’d be glad to collaborate
>>>>>> on writing that with you if you’d like.  Other needed pre-hash algorithm
>>>>>> identifiers could also be created in the new spec.
>>>>>>
>>>>>>
>>>>>>
>>>>>> Mike Prorock and Orie Steele, it’s relevant to know whether you
>>>>>> intent to extend to register both pre-hash and non-pre-hash algorithm
>>>>>> identifiers in draft-ietf-cose-dilithium.  Your thoughts?
>>>>>>
>>>>>>
>>>>>>
>>>>>> Emil, I am glad that you are working on the signing extension for
>>>>>> WebAuthn.  I certainly support that work.
>>>>>>
>>>>>>
>>>>>>
>>>>>>                                                                 Best
>>>>>> wishes,
>>>>>>
>>>>>>                                                                 --
>>>>>> Mike
>>>>>>
>>>>>>
>>>>>>
>>>>>> *From:* Emil Lundberg <emil=[e-mail]>
>>>>>> *Sent:* Friday, September 20, 2024 9:51 AM
>>>>>> *To:* cose <[e-mail]>; [e-mail]
>>>>>> *Subject:* [jose] Algorithm identifiers for pre-hashing in two-party
>>>>>> signing?
>>>>>>
>>>>>>
>>>>>>
>>>>>> Hi COSE and JOSE WGs,
>>>>>>
>>>>>> I'm currently working on an extension to WebAuthn
>>>>>> <https://github.com/w3c/webauthn/pull/2078> [1] for signing
>>>>>> arbitrary data. The current draft uses `COSEAlgorithmIdentifier`s to
>>>>>> negotiate what signature algorithm to use, and the same
>>>>>> `COSEAlgorithmIdentifier` is also emitted in generated `COSE_Key`s to
>>>>>> communicate the signature algorithm to the signature verifier.
>>>>>>
>>>>>> However, for several reasons we want the caller of this signing API
>>>>>> to pre-hash the data to be signed before passing it into the extension. The
>>>>>> question then is: how should we communicate, _generically_, which steps of
>>>>>> the signing algorithm are performed in advance by the caller and which are
>>>>>> performed by the WebAuthn authenticator?
>>>>>>
>>>>>> In some cases the division is fairly obvious. For example, ESP256
>>>>>> <https://www.ietf.org/archive/id/draft-ietf-jose-fully-specified-algorithms-05.html>
>>>>>> [2] hashes the input only once, so it's obvious that the caller performs
>>>>>> the hash and the WebAuthn authenticator interprets the input as a raw P-256
>>>>>> scalar. Ed25519ph
>>>>>> <https://www.rfc-editor.org/rfc/rfc8032#section-5.1> [3] hashes the
>>>>>> input once without the key and then hashes the digest again with the key,
>>>>>> so clearly only the first hash can be performed by the caller (and Ed25519
>>>>>> is impossible to implement in this way).
>>>>>>
>>>>>> But for other algorithms it's less obvious - for example, for
>>>>>> HashML-DSA <https://csrc.nist.gov/pubs/fips/204/final> [4], the
>>>>>> caller could compute only PH_M and submit PH_M and the hash OID into the
>>>>>> signing API, or the caller could compute M' and submit only M' into the
>>>>>> signing API (I think the former is clearly preferable, but the point is
>>>>>> that both options exist). Similarly for RSASSA-PSS
>>>>>> <https://www.rfc-editor.org/rfc/rfc8017#section-9.1.1> [5], should
>>>>>> the caller submit `mHash` or `EM`? This "division of labour" between the
>>>>>> caller and the WebAuthn authenticator needs to be defined somehow.
>>>>>>
>>>>>> So, that is my question: how should we define and communicate this
>>>>>> division of labour?
>>>>>>
>>>>>> - Is there some way we can do it generically, without defining any
>>>>>> new algorithm identifiers?
>>>>>> - Should we define new algorithm identifiers for "pre-hashing for
>>>>>> two-party signing" in some existing registry?
>>>>>> - Should we define a new registry of algorithm identifiers?
>>>>>> - Should we define some new "signing request" data structure, which
>>>>>> can describe whether and how data is pre-hashed (perhaps similar to COSE
>>>>>> Hash Envelopes
>>>>>> <https://cose-wg.github.io/draft-ietf-cose-hash-envelope/draft-ietf-cose-hash-envelope.html#name-hash-envelope-cddl>
>>>>>> [6]?)?
>>>>>> - Other options?
>>>>>>
>>>>>> Any insight and guidance on this would be much appreciated. Of course
>>>>>> I'm also happy to elaborate on anything that is unclear. Thank you.
>>>>>>
>>>>>>
>>>>>> [1]: https://github.com/w3c/webauthn/pull/2078
>>>>>> [2]:
>>>>>> https://www.ietf.org/archive/id/draft-ietf-jose-fully-specified-algorithms-05.html
>>>>>> [3]: https://www.rfc-editor.org/rfc/rfc8032#section-5.1
>>>>>> [4]: https://csrc.nist.gov/pubs/fips/204/final
>>>>>> [5]: https://www.rfc-editor.org/rfc/rfc8017#section-9.1.1
>>>>>> [6]:
>>>>>> https://cose-wg.github.io/draft-ietf-cose-hash-envelope/draft-ietf-cose-hash-envelope.html#name-hash-envelope-cddl
>>>>>>
>>>>>>
>>>>>> *Emil Lundberg*
>>>>>>
>>>>>> Staff Engineer | *Yubico* <http://www.yubico.com/>
>>>>>>
>>>>>>
>>>>>>
>>>>>
>>>>
>>>> --
>>>>
>>>>
>>>> ORIE STEELE
>>>> Chief Technology Officer
>>>> www.transmute.industries
>>>>
>>>> <https://transmute.industries>
>>>>
>>>
>>
>> --
>>
>>
>> ORIE STEELE
>> Chief Technology Officer
>> www.transmute.industries
>>
>> <https://transmute.industries>
>>
>
>
> --
>
>
> ORIE STEELE
> Chief Technology Officer
> www.transmute.industries
>
> <https://transmute.industries>
>