Review comments 2024-05-29

[emlun]

Here are my comments after reviewing the HDK draft. This review concerns the version as of commit 06bf2131.

This is an alternative to Key Blinding for Signature Schemes [draft-irtf-cfrg-signature-key-blinding], which would require a secure cryptographic device that supports the BlindKeySign operation. These are not yet widely available at the time of writing.

ARKG also requires a novel hardware operation (ARKG-Derive-Private-Key).

Now the holder wants to have an initial document, such as an person identification document. The holder shares with the issuer a proof of possession of sk_root and a newly generated key encapsulation key pair (pk_kem, sk_kem). The issuer trusts pk_root, for example based on wallet trust evidence.

With ARKG I don't think PoP for the root key is necessary, because the trusting party can instead verify that derived keys are correctly derived by the ARKG algorithm and therefore a PoP of the derived private key is also a PoP of the root key.

Also, one important motivation for introducing ARKG to wallet solutions is to enable the wallet client to autonomously generate lots of unique keys, each to be associated with a single-use instance of a verifiable credential. If issuance of those credentials requires a signature by the private key whose public key is to be the proof key for the credential, then that undermines much of the point of introducing ARKG in the first place. Of course the issuer should authenticate the credential issuance request somehow, but it is critically important that the issuance flow not require a signature by the to-be-issued proof key.

The issuer uses key encapsulation with pk_root to share key handles kh0_j which contain the information to compute the scalars.

Note that ARKG can also be constructed using non-EC cryptograhy (so private keys are not necessary "scalars"), including PQC algorithms.

KEM: A key encapsulation mechanism [draft-bradleylundberg-cfrg-arkg], consisting of the functions:

I recently added a reference to [Shoup] for this in the ARKG draft, I suggest doing the same here.

DerivePrivateKey(sk, kh, info): Outputs sk', a blinded private key Scalar based on ARKG private seed sk = (sk_kem, sk_bl), a key handle kh, and application-specific information info.

info is an input, not output

The output keys keys of KEM MUST be the output keys of ARKG.

Is this correct? Or should this maybe be "input keys of ARKG"?

Summary: The holder proves possession of the blinded public key pk_bl in an attestation att to the reader.

pk_bl is not yet introduced?

The BlindAuthenticate function is defined as follows:

pk is not used?

Using a digital signature algorithm for proof of possession

transcript is not used?

Using threshold EC-SDSA for additive blind authentication

Requires specification of BlindVerify? So verifier can compute blinded vk from base pk?

The holder computes (pk_kem, sk_kem) = KEM.GenerateKeyPair().

Why is this needed outside ARKG? (Perhaps duplicate of #9)

KEM: ECDH as described in [draft-bradleylundberg-cfrg-arkg] Section 3.3 with the parameters crv set to G, Hash set to SHA-256 [FIPS180-4], DST_ext set to ARKG-P256ADD-ECDH.

This should use DST_ext = "ARKG-P256MUL-ECDH" instead, see also next comment

ARKG: ARKG instance as described in [draft-bradleylundberg-cfrg-arkg] with the identifier ARKG-P256MUL-ECDH, KEM as defined above, and BL with elliptic curve arithmetic as described in [draft-bradleylundberg-cfrg-arkg] Section 3.1 but with multiplicative instead of additive blinding.

We should define this ARKG-P256MUL-ECDH instance in the ARKG spec (duplicate of #7)

Using a digital signature algorithm for proof of possession

RNG unused?

Comments not related to a particular paragraph

• Why multiplicative blinding if not for Split-ECDSA? (And even then, Split-ECDSA would happen outside the scope of ARKG?) (Duplicate of #9)
• draft-bradleylundberg-cfrg-arkg seems like it should be a normative reference

[emlun]

(Sorry, I hit Ctrl-Enter too early - previous comment has been edited)

[sander]

Thank you for the thorough review @emlun!

ARKG also requires a novel hardware operation (ARKG-Derive-Private-Key).

See https://github.com/sander/hierarchical-deterministic-keys/issues/7#issuecomment-2138025616

With ARKG I don't think PoP for the root key is necessary, because the trusting party can instead verify that derived keys are correctly derived by the ARKG algorithm and therefore a PoP of the derived private key is also a PoP of the root key.

Upon issuance, the user will present a BL or ARKG public key to the issuer, along with a proof of possession of related private key (as per OpenID4VCI draft 13). Only after verifying that proof, the issuer will derive the batch of next-level PoP public keys using ARKG. If we’d omit the first proof, the issuer could not know if the BL private key is properly protected. For PID and wallet-bound QEAA this would be unacceptable.

Also, one important motivation for introducing ARKG to wallet solutions is to enable the wallet client to autonomously generate lots of unique keys, each to be associated with a single-use instance of a verifiable credential. If issuance of those credentials requires a signature by the private key whose public key is to be the proof key for the credential, then that undermines much of the point of introducing ARKG in the first place. Of course the issuer should authenticate the credential issuance request somehow, but it is critically important that the issuance flow not require a signature by the to-be-issued proof key.

Fully agreed, the issuer should not request PoP of the derived public keys. That would potentially create the usability horror that @ve7jtb mentioned.

Note that ARKG can also be constructed using non-EC cryptograhy (so private keys are not necessary "scalars"), including PQC algorithms.

Indeed, HDK as constructed now limits ARKG to the use with just EC cryptography. I expect that once WSCDs support non-EC cryptography for LoA High, we should revisit the need of HDK as a transitory scheme.

Using a digital signature algorithm for proof of possession

transcript is not used?

Addressing this awkwardness in: https://github.com/sander/hierarchical-deterministic-keys/issues/8

Using threshold EC-SDSA for additive blind authentication

Requires specification of BlindVerify? So verifier can compute blinded vk from base pk?

The verifier will not learn the base pk to achieve RP-Unlinkability. Instead, the verifier can just use PoP.Verify with the attested, blinded public key.

The other comments need to be fixed in the text:

• [x] Refer to [Shoup] for KEM
• [x] Make cryptographic dependency functions more readable with clearer distinction between inputs and outputs
• [x] Make input-output matching requirements in cryptographic dependencies less awkward (ideally resolved by #9)
• [x] Rephrase summary of “Proof of possession” summary to clarify that pk_bl is pk_root at level 0, or an ARKG-derived public key at child levels
• [x] Fix MAC-based BlindAuthenticate variable names such that proof = PoP.Authenticate(sk_root, G.ScalarMult(challenge, sk_blind), info)
• [x] Fix typo in instantiation: DST_ext = "ARKG-P256MUL-ECDH" (was ADD)
• [x] Remove RNG from the DSA-based PoP instantiation
• [x] Turn draft-bradleylundberg-cfrg-arkg into a normative reference, even if still an Internet-Draft

[emlun]

The verifier will not learn the base pk to achieve RP-Unlinkability. Instead, the verifier can just use PoP.Verify with the attested, blinded public key.

Hm, looking again at "Using threshold EC-SDSA for additive blind authentication", does this blinding method even work with ECDSA? I think something like this works for Schnorr signatures, but I don't think an ECDSA signature can be post-processed like this and remain valid (but under a new public key)?

Split-ECDSA works because before signing you replace e by e' = e * b^-1 and after replace s by s' = s * b, so (s')^-1 = (s * b)^-1 = s^-1 * b^-1, but you can't distribute the inverse like that for (s')^-1 = (s + r * b)^-1 (where r = c, b = sk_blind in the notation in this HDK section). I worked through the verification equation and got that the blinder needs to compute the blinding factor as b = d_A * k^-1, which shouldn't be possible without knowledge of the private key d_A. So how does this blinding method work?

(ARKG-Derive-Secret-Key doesn't have this problem since it indeed knows the base private key)

[emlun]

It also seems to me like the section "Using a digital signature algorithm for proof of possession" relies heavily on the specific underlying arithmetic of the DSA scheme, so the abstract interface definition for DSA doesn't seem very useful.

[sander]

The verifier will not learn the base pk to achieve RP-Unlinkability. Instead, the verifier can just use PoP.Verify with the attested, blinded public key.

Hm, looking again at "Using threshold EC-SDSA for additive blind authentication", does this blinding method even work with ECDSA? I think something like this works for Schnorr signatures, but I don't think an ECDSA signature can be post-processed like this and remain valid (but under a new public key)?

The blinding method under “Using threshold EC-SDSA for additive blind authentication” (EC-SDSA = Schnorr as standardised at ISO/IEC) indeed does not work with ECDSA. I’ve added a dedicated section “Using threshold ECDSA for multiplicative blind authentication” to mention that the spec does not include ECDSA blinding due to threshold ECDSA patent issues – SECDSA and possibly some related to threshold ECDSA.

Split-ECDSA works because before signing you replace e by e' = e * b^-1 and after replace s by s' = s * b, so (s')^-1 = (s * b)^-1 = s^-1 * b^-1, but you can't distribute the inverse like that for (s')^-1 = (s + r * b)^-1 (where r = c, b = sk_blind in the notation in this HDK section). I worked through the verification equation and got that the blinder needs to compute the blinding factor as b = d_A * k^-1, which shouldn't be possible without knowledge of the private key d_A. So how does this blinding method work?

For SECDSA, another BlindAuthenticate definition would be needed that indeed performs pre-processing and post-processing. The reader can verify blinded signatures using the blinded public key, which is sufficient for HDK.

It also seems to me like the section "Using a digital signature algorithm for proof of possession" relies heavily on the specific underlying arithmetic of the DSA scheme, so the abstract interface definition for DSA doesn't seem very useful.

The introduction and impl PoP(RNG, DSA) seemed more generally applicable, no? Two alternative possible routes to take with the spec:

• Indeed flatten this section and only specify EC-SDSA (Schnorr), possibly adding other flat sections for other DSAs
• Expand the BlindAuthenticate sections with more explanation of the problem and available solutions, potentially after extracting into a dedicated “blinded key signing” spec

[sander]

Regarding the last paragraph in my last comment: in 5ebb9be I have flattened the generic instantiation section and removed the intermediate “DSA” abstraction over ECDSA and EC-SDSA.

[sander]

I’ve resolved all pending review comments as of 07d321b. Feel free to reuse this issue or open a new one for further discussion.

[emlun]

The blinding method under “Using threshold EC-SDSA for additive blind authentication” (EC-SDSA = Schnorr as standardised at ISO/IEC)

Oh, I missed the S there in SDSA. Ok, that makes much more sense then. The "(Schnorr)" clarification in the new draft also makes this much clearer. Thanks!