Re: [COSE] IANA COSE assignments

[Ilari Liusvaara <[e-mail]>]

On Fri, Jan 29, 2021 at 03:01:31PM +0000, Göran Selander wrote:
> Thanks Ilari!
> 
> Good input, some questions inline.
> 
> On 2021-01-28, 18:37, "[e-mail] on behalf of Ilari Liusvaara" <[e-mail]> wrote:
> 
>     On Thu, Jan 28, 2021 at 09:17:56AM +0000, Göran Selander wrote:
>     >  
>     > Hi all,
>     > 
>     > I'm one of the designated experts for the IANA registry of COSE
>     > algorithms and I need some guidance from the WG.
>     > 
>     > 1. Current IANA assignments and instructions for COSE algorithms [1]
>     > intentionally bundles certain parameters whereas others are not
>     > bundled.
>     > 
>     > For example, all COSE registrations of ECDH include key derivation,
>     > but ECDH algorithm and elliptic curve are not bundled. Section 6.3.1.
>     > states:
> 
>     Here, things get bit more complicated with Wei25519/Wei448.
> 
>     These curves have h!=1 (unlike every past elliptic curve in COSE, which
>     all have h=1), so it makes sense to multiply at the end by h in order
>     to guard for attacks with small subgroups ("co-factor ECDH").
> 
>     However, RFC8152 defers to RFC6090 for ECDH, and RFC6090 assumes that
>     h=1. However, RFC8152 also species the output encoding per curve, so
>     one could specify special output encoding that multiplies by h before
>     encoding in order to take h into account. This should give co-factor
>     ECDH on the new curves without defining any new algorithms.
> 
> [GS] This sounds a good way forward. Anyone has a preference for how
> to document that? That output encoding supporting h!=1 cofactor is
> potentially of general applicability and would complement
> draft-ietf-cose-rfc8152bis-algs so I assume it should be reviewed by
> the COSE WG.

Just to be clear, that is just for the shared secret, not the public
points.

As formulas:

output(X) = encodex(h*X)
decode(encode(X)) = X.

ka=output(a*decode(encode(b*G))=output(a*b*G)=encodex(h*a*b*G)=
encodex(h*b*a*G)=output(b*a*G)=output(b*decode(encode(a*G))=kb

Which is cofactor ECDH with output being x coordinate only. Which should
still work even if either or both sides mess up the sign (e.g., not
bothering to recover it from ladder).

> 
>     > As another example, ECDSA is bundled with a hash function (see table
>     > 1) but not  with the elliptic curve, see Section 2.1:
> 
>     This is the way ECDSA is traditionally done in specifications.
> 
>     For ease of correct implementation, one wants as little information
>     associated with the message (ideally none) that can contradict the
>     information in the key. JOSE is well-known for vulnerabilities arising
>     from implementations using information from message over information
>     from the key. And then some folks misdiagnosed this as problem with
>     algorithm agility.
> 
>     The most well-known protocol to not do things the traditional way is
>     TLS 1.3. However, I think this is in order to simplify negotiation,
>     which is not appliciable to COSE. It definitely does not make
>     implementations easier (many implementations probably do not check
>     proper curve matching, which fortunately does not cause security
>     issues).
> 
> 
>     The new curves might be paired with SHAKE128 or SHAKE256, but those
>     could be handled (modulo a nasty implenentation trap) by defining
>     ECDSA with SHAKE128 and ECDSA with SHAKE256 algorithms.
> 
>     As to what that nasty implementation trap is: With the new curves,
>     how the hash is converted into input z is different for SHA-2 and
>     SHA-3 (including SHAKE). With traditional curves, that conversion is
>     the same for SHA-2 and SHA-3.
> 
> [GS] OK, so in that case we may add two more (ECDSA +hash) code points,
> which could then be used with other curves. But that would require a
> description of the different input z. Can that input be generally
> described for a large range of curves or is there a need to change this
> specification whenever a new curve is defined?

And another clarification, since SHAKE is a XOF, the output length needs
to be specified. Usual choices are 256 for SHAKE128 and 512 for
SHAKE256 (these are the minimum lengths to max out the collision
resistance).

One thing to note that different descriptions use different notation
here:

- "SEC 1: Elliptic Curve Cryptography" uses e.
- Wikipedia uses z.
- FIPS 186-4 does not have relevant parts.
- FIPS 186-5 draft uses e.
- IEEE 1363 uses f.
- I can't check what X9.62 uses (paywall).
- RFC6090 uses h(M)

... So might want to use "e" instead of "z".

And what happens here follows from the following rules:

1) Take first up to ceil(log2(n)) bits of hash (n is the order of the
   curve basepoint). This is by ECDSA specification.
2) If one needs to take partial octet, take the least significant bits.
   The bit order is by SHA-3 specification.
3) The (partial) octets are decoded as big-endian integer. Not taken
   bits do not contribute. This is by ECDSA specification.

(If SHA-2 was used instead, the rule #2 would say most signficant bits
instead, by SHA-2 specification. If one takes a look at SHA-3/SHAKE
software implementation, one sees everything is little-endian and
lanes are reversed, as this is a handy trick to not have to bitswap
bytes (which is slow). In contrast, SHA-2 implementations are just
big-endian).


As example, W448 with SHAKE256 (512 bits).

1) Take first 446 bits of hash. This is 55 complete octets (indexes
   0 to 54 inclusive), and 6 leftover bits.
2) The 6 leftover bits come from 6 least significant bits of 56th
   octet (index 55).
3) The 56 groups, first 55 being full 8 bits and the last one being
   only six are decoded as big-endian integer. Due to the two missing
   bits, the 55th octet (index 54) is 64s.


As to why this does not come up with P-256 (secp256k1) and P-384:
ceil(log2(n)) is multiple of 8, and hash length is multiple of 8,
so one never ends up taking a partial octet.

And for P-521 the reason is different. ceil(log2(n)) is so big (521)
that all bits of hash end up being taken.


I also took a look at libnettle source to discover how it handles
this. It takes the message to sign as hash value, with no reference
to hash function used and uses the following algorithm:

1) Decode the full hash as big-endian integer.
2) If ceil(log2(n)) is greater than hash length, shift right by the
   difference.

... Which would take the most significant bits of any partial octet
(like for SHA-2).

> 
>     > But then there are exceptions, like ES256K [2] which bundles
>     > signature algorithm, hash function and elliptic curve. 
> 
>     I view that a past mistake.
> 
> [GS] Do I understand right that you think we should have used
> algorithm -7 and curve 8 instead of algorithm -47 only?
> 
> ES256 		-7 	ECDSA w/ SHA-256 	
> secp256k1 	8 	EC2 	SECG secp256k1 curve
> ES256K 		-47 	ECDSA using secp256k1 curve and SHA-256

Right.



-Ilari