Review comments 2024-07-04

[emlun]

This review concerns the version as of commit f6b592da.

From an overview perspective, the only notable problem I see is that it's still not quite clear to me how ARKG fits into this. Concretely, I don't see how HDK generates the kh inputs to HDK-Derive-Remote. Or is it that the data provider performs ARKG-Derive-Public-Key and returns kh values to the holder?

It's also not obvious to me how remote keys fit into the hierarchy, with the salts, indices etc. I'm also wondering if we make ARKG-Derive-Public-Key deterministic (as @AltmannPeter had already suggested), if it wouldn't be possible to merge HDK-Derive-Local in as a special case of HDK-Derive-Remote...? I don't really see why these would fundamentally need to be different procedures (except that the ARKG sub-procedure is currently nondeterministic, so repeat calls with the same salt/index return different results).

Some detail-level comments below:

---

• Maybe clarify what is meant by "instance" throughout the document? Wallet instance? HDK instance?

• key(bytes): Deterministically outputs a key pair (pk, sk) from a uniformly random string of Nk bytes.

  Might be better named KDF (or kdf)?

• - index, an integer between 0 and 2^32-1 (inclusive).

  Implementations may want to limit the range of index to prevent signature malleability attacks? (Maybe not relevant if HDK is only concerned with Schnorr signatures, not ECDSA?)

• def HDK-Derive-Local((pk, sk, salt), index):

  Does this mean that both salt and index act as "indexing" parameters? I.e., you could generate multiple different (pk', sk') from the same (pk, sk, index) combination? (Maybe not if (pk, sk) are restricted to a single salt value, but is that guaranteed/enforced?)

• info = "HDK-Derive-Local"

  Might this need to worry about prefix/suffix extension attacks? (i.e., escape from domain separation if this is concatenated with some other value without inserting a boundary between segments.) Maybe not applicable/addressable since the BL-* functions are abstract and thus opaque to what they do with the info value.

• def HDK-Derive-Remote(pk_device, (pk, sk, salt), kh)

  Looks like this function is abstract? In that case maybe it should be listed in the "Instance parameters" section? (Same goes for HDK-Authenticate)

• The instance authenticates the device by blindly creating proof

  Does this mean "blindly" as in creating a blinded proof? This formulation sounds to me like "blindly" means that the instance accepts input parameters without verifying that they are correct or well-formed.

• sk' = OS2IP(bytes) mod (EC-Order() - 1)

  This risks introducing bias in the key distribution unless bytes is much longer than EC-Order(). May need to explicitly call out safe ranges for Nk, or use hash_to_field which is designed for this purpose.

• sk = sk' + 1

  What's this? Why add 1?

• sk' = ARKG-Derive-Private-Key(sk_arkg, kh, "")

  I don't see anywhere how these kh are generated? (See above)

• The reader MUST NOT create an input byte string reader_data with sufficient entropy for each challenge.

  Is this meant to be "MUST NOT" or should it be "MUST"?

• pk' = EC-Add(pk_device, EC-Scalar-Base-Mult(sk_blind))

  I think sk_blind is meant to be sk'?

• Nr: 48

  Ah, this covers the bias concern above. But it's close to invisible if you don't know to look out for it, so it's probably worth calling out why this value needs to be higher than the size of the curve coordinate space.

[sander]

Thank you for the in-depth review @emlun!

From an overview perspective, the only notable problem I see is that it's still not quite clear to me how ARKG fits into this. Concretely, I don't see how HDK generates the kh inputs to HDK-Derive-Remote. Or is it that the data provider performs ARKG-Derive-Public-Key and returns kh values to the holder?

Indeed.

It's also not obvious to me how remote keys fit into the hierarchy, with the salts, indices etc. I'm also wondering if we make ARKG-Derive-Public-Key deterministic (as @AltmannPeter had already suggested), if it wouldn't be possible to merge HDK-Derive-Local in as a special case of HDK-Derive-Remote...? I don't really see why these would fundamentally need to be different procedures (except that the ARKG sub-procedure is currently nondeterministic, so repeat calls with the same salt/index return different results).

As discussed 1-1 after this comment, indeed the instance could also locally invoke ARKG-Derive-Public-Key((pk_kem, pk_bl), index) to recover a key handle.

This could simplify the design. However, in the local case we only need BL and don’t really need KEM. Do you think the overhead is worth doing it though?

• key(bytes): Deterministically outputs a key pair (pk, sk) from a uniformly random string of Nk bytes.

  Might be better named KDF (or kdf)?

The function implements in the EC case BSI TR-03111 v2 § 4.1.1 Algorithm 2 to derive RNG({1,2,...,n-1}) from RNG({0,1,2,...,2k-1}) for 2^k >= n. It seems like most KDFs do more to ensure a uniform distribution, no?

• - index, an integer between 0 and 2^32-1 (inclusive).

  Implementations may want to limit the range of index to prevent signature malleability attacks? (Maybe not relevant if HDK is only concerned with Schnorr signatures, not ECDSA?)

What would an attack scenario be in this case?

• def HDK-Derive-Local((pk, sk, salt), index):

  Does this mean that both salt and index act as "indexing" parameters? I.e., you could generate multiple different (pk', sk') from the same (pk, sk, index) combination? (Maybe not if (pk, sk) are restricted to a single salt value, but is that guaranteed/enforced?)

The idea is that (pk, sk, salt) is an HDK, generated either using HDK-Root or a HDK-Derive function. Since only the wallet instance itself will generate HDKs (others will only derive public keys), we can assume integrity of the (pk, sk, salt) parameter and use it to derive many keys with different index values.

• info = "HDK-Derive-Local"

  Might this need to worry about prefix/suffix extension attacks? (i.e., escape from domain separation if this is concatenated with some other value without inserting a boundary between segments.) Maybe not applicable/addressable since the BL-* functions are abstract and thus opaque to what they do with the info value.

I’d indeed expect any BL instance to address the prefix/suffix extension threat when processing tau and info. Would this be something to add to ARKG § 2.1?

• sk = sk' + 1

  What's this? Why add 1?

That the maximum value of sk' is EC-Order() - 2, so by this logic sk is a value within {1,...,EC-Order()-1}. The case sk = 0 would be invalid.

To do:

• [x] Make explicit that the data provider needs to apply ARKG-Derive-Public-Key.
• [x] Clarify terminology: (wallet) instance, (HDK) instantiation; one instance may apply several instantiations.
• [x] Add to “Instance parameters” section the requirement to instantiate the abstract functions HDK-Root, HDK-Derive-Remote, and HDK-Authenticate.
• [x] Rephrase “by blindly creating proof” to “by creating a blinded proof”.
• [x] Call out that Nk usually needs to be higher than the size of the curve coordinate space, to avoid maintain uniform distribution when deriving RNG({1,2,...,n-1}) from RNG({0,1,2,...,2k-1}) for 2^k >= n.
• [x] Fix typo: in “The reader MUST NOT create an input byte string” MUST NOT must be MUST.
• [x] Fix typo: in “EC-Add(pk_device, EC-Scalar-Base-Mult(sk_blind))” sk_blind must be sk'.

[sander]

2024-07-15: we will await more feedback to make the tradeoff between unifying local/remote or keeping it separate.

[emlun]

I think these concerns are now addressed. Thanks @sander!