Multiplicative blinding with ARKG

[sander]

ARKG still provides additive blinding ciphersuites only, while for ECDH (and possibly ECDSA) multiplicative blinding is easier. For now I've cheated and assumed an additional “ARKG-P256mul” ciphersuite. Is it feasible and necessary to add to ARKG?

[emlun]

What do you mean by "easier"?

Is it feasible

Yes, but with the caveat that I haven't yet seen a formal security proof for this ARKG construction (I'm sure it's easy to produce, I just haven't taken the time to assemble it).

and necessary to add to ARKG?

I don't think so? As far as I'm aware, the main use case for specifically multiplicative blinding is that it's what needed for Split-ECDSA (SECDSA) - but SECDSA is a transformation that is applied outside the secure element that holds the base key (assuming the caller sends the message hash to the secure element, not the unhashed message), which is useful for backwards compatibility with existing secure hardware. But ARKG requires a new hardware operation anyway, so I see little relevance in combining SECDSA and ARKG.

Is there some other reason to prefer multiplicative blinding over additive blinding if a new hardware operation is required either way?

[sander]

What do you mean by "easier"?

For ECDH:

• In BL-Blind-Public-Key, pk_tau can be computed using ECDH(tau', pk) instead of using EC element addition. ECDH is available in Android and iOS standard libraries, while addition may require low-level cryptographic dependencies.
• In BlindAuthenticate (06bf2131eb9535d66ec5f7ec81b3d7bf52b9249c), we can compute [sk_root * sk_blind]challenge == [sk_root][sk_blind]challenge == [sk_root]ECDH(sk_blind, challenge) again just applying Android and iOS standard libraries. (Note that the definition in the draft spec has some typos as you found in https://github.com/sander/hierarchical-deterministic-keys/issues/11.)

and necessary to add to ARKG?

I don't think so? As far as I'm aware, the main use case for specifically multiplicative blinding is that it's what needed for Split-ECDSA (SECDSA) - but SECDSA is a transformation that is applied outside the secure element that holds the base key (assuming the caller sends the message hash to the secure element, not the unhashed message), which is useful for backwards compatibility with existing secure hardware. But ARKG requires a new hardware operation anyway, so I see little relevance in combining SECDSA and ARKG.

Is there some other reason to prefer multiplicative blinding over additive blinding if a new hardware operation is required either way?

My idea for HDK is to never require calling ARKG-Derive-Private-Key or its dependency BL-Blind-Private-Key within the secure cryptographic device. We only apply ARKG-Derive-Private-Key in the “Attestation issuance” use case (06bf2131eb9535d66ec5f7ec81b3d7bf52b9249c) step 3.ii, using sk_blind as a BL private key, where sk_blind is the combination of zero or more tau values.

So for HDK, no hardware operations are needed beyond the creation of a single root key for P-256 ECDH or ECSDSA, and the default operation upon that key using some pre-processing or post-processing within the general-purpose execution environment in BlindAuthenticate.

[emlun]

In BL-Blind-Public-Key, pk_tau can be computed using ECDH(tau', pk) instead of using EC element addition.

I see, I suspected something like that. Thanks! Just note that this would also require clarifying that the ECDH implementation must not apply a KDF to the shared point, and that it needs to output both the x and y coordinates, not just the x coordinate as is most common. (I don't think this is a problem for X25519/448 though)

My idea for HDK is to never require calling ARKG-Derive-Private-Key or its dependency BL-Blind-Private-Key within the secure cryptographic device.

In that case, honestly I don't think you need ARKG. :slightly_smiling_face: The point of ARKG is that it's a two-party protocol, so the spec defines what steps the two parties need to take in order to preserve the key pair relationship through the blinding transformation and without revealing the base secret key to the subordinate party. If there's only one party, that party doesn't need a protocol to agree with itself on a transformation of an unknown value. For example Split-ECDSA is a transformation performed unilaterally by just one party - just the party requesting and relaying the signature, without involvement by the party holding the private key - so there's no need for a protocol for how the private key holder should behave.

Or am I misunderstanding something? Is there somewhere in HDK where two distinct parties need to perform the same transformation without revealing the transformed value to one of them? As far as I can see, the procedure in the Attestation issuance section could just as well use just a bare KEM since the process reveals sk_blind_j to both parties.

[emlun]

the procedure in the Attestation issuance section could just as well use just a bare KEM since the process reveals sk_blind_j to both parties.

No, wait, my mistake - it doesn't reveal sk_blind_j, but it reveals sk_blind_j - sk_blind (or sk_blind_j * sk_blind^-1 in the multiplicative case) to both parties. Still, I don't quite understand the utility of using ARKG here since the issued attestation would be bound to the public key pk' = sk_blind_j * G, but sk_blind_j is not a hardware-backed private key, so if the holder wants a presentation of that attestation to be signed by a hardware-backed private key they would have to mix in a hardware-bound key part somewhere (for example using SECDSA). But then that would again change the verification key from pk' to some new public key vk != pk', so wouldn't there need to also be a protocol for how the verifier would compute the right verification key vk?

[sander]

Just note that this would also require clarifying that the ECDH implementation must not apply a KDF to the shared point, and that it needs to output both the x and y coordinates, not just the x coordinate as is most common. (I don't think this is a problem for X25519/448 though)

Good point. I thought it would easy to find y for P-256, but this would require EC element addition in itself. So to resolve this:

• [x] Find out whether Android and iOS natively support returning (x, y) from the secure cryptographic environment
• [x] Then consider replacing multiplicative blinding with additive blinding for ECDH

My idea for HDK is to never require calling ARKG-Derive-Private-Key or its dependency BL-Blind-Private-Key within the secure cryptographic device.

In that case, honestly I don't think you need ARKG. 🙂

Benefits I hope to gain from keeping the ARKG-Derive-Public-Key dependency:

• common issuer-side implementations
• common test vectors
• common interest in extending the issuance protocol for a BL+KEM construction
• CFRG review of a BL+KEM construction

Or am I misunderstanding something? Is there somewhere in HDK where two distinct parties need to perform the same transformation without revealing the transformed value to one of them?

In HDK:

1. the holder has a root (BL) key in the secure cryptographic device;
2. at each level, the holder is able to present PoP of each key;
3. the issuer and holder need to subsequently establish many child BL keys;
4. the issuer only includes those child BL keys in attestations, and not their parent BL key.

In 3, the issuer needs to be assured that the child BL key is protected using the same secure cryptographic device as the parent BL key. We achieve this by blinding. I’m aware of three approaches to determine the blinding factor τ:

• Approach 1: the holder generates τ and shares a (zero-knowledge) proof of association of τ with the parent BL public key as a base point;
• Approach 2: the issuer generates τ and shares this with the holder;
• Approach 3: the holder and issuer establish τ using KEM.

Approach 2 risks leaking τ to web infrastructure. Approach 1 is currently required in the ARF, but I don’t like the reliance on additional proofs. Approach 3 is in the current HDK draft.

So indeed I’m aiming to involve two distinct parties: the issuer and the holder. They will both learn the value τ. Does the above clarify the intention?

the procedure in the Attestation issuance section could just as well use just a bare KEM since the process reveals sk_blind_j to both parties.

No, wait, my mistake - it doesn't reveal sk_blind_j, but it reveals sk_blind_j - sk_blind (or sk_blind_j * sk_blind^-1 in the multiplicative case) to both parties.

The procedure does not provide the issuer or reader with any knowledge about sk_blind_j - sk_blind (in the additive case). Note that the user will never sign using sk_blind_j directly. Instead, the user will in the “Proof of possession” use case apply sk_blind_j as a parameter to the BlindAuthenticate function.

Still, I don't quite understand the utility of using ARKG here since the issued attestation would be bound to the public key pk' = sk_blind_j * G, but sk_blind_j is not a hardware-backed private key, so if the holder wants a presentation of that attestation to be signed by a hardware-backed private key they would have to mix in a hardware-bound key part somewhere (for example using SECDSA). But then that would again change the verification key from pk' to some new public key vk != pk', so wouldn't there need to also be a protocol for how the verifier would compute the right verification key vk?

The issued attestation will be bound to (pk', _) = ARKG-Derive-Public-Key((pk_kem_ephemeral, pk_bl_parent), info_arkg) as per the “Attestation issuance” use case step 2.iii. And pk_bl_parent is either the hardware-backed key pk_root itself, or the same key but with applied blinding.

[sander]

I’ve checked: Apple’s Secure Enclave indeed only returns the x coordinate. Indeed for several HSMs it is the same. So indeed multiplicative blinding is not “easier” for ECDH than additive.

Multiplicative blinding is also not needed for ECDSA in HDK: I’m omitting it due to patent and possibly security issues.

I’ll close the issue since the original request is resolved, but feel free to continue the discussion to ensure shared understanding of the ARKG application in HDK.

[sander]

Reopening this thread: since ECDH typically returns x coordinates only, we have no way to compute

ECDH(P, sk_device + sk_bl) = x([sk_device + sk_bl]P) = x([sk_device]P + [sk_bl]P)

outside of the WSCD without performing ECDH inside the WSCD twice, and thus possibly authenticating the user twice. With multiplicative blinding, we can compute

ECDH(P, sk_device * sk_bl) = x([sk_device * sk_bl]P) = x([sk_device][sk_bl]P) = ECDH([sk_bl]P, sk_device)

Therefore, it looks like we need multiplicative blinding in HDK.

[emlun]

Good point. I thought it would easy to find y for P-256, but this would require EC element addition in itself.

I’ve checked: Apple’s Secure Enclave indeed only returns the x coordinate. Indeed for several HSMs it is the same.

I thought briefly about this too - in theory it should indeed be easy to find the y coordinate, it's just the matter of whether it's positive or negative. But therein also lies the problem: the party computing a blinded public key [b]P (where P = [p]G) using ECDH(P, b) must choose the correct sign of y for ECDH(P, b) in order to get the correct blinded public key corresponding to the signing secret key b * p. So at least at first glance it seems like a 50% chance that the public key blinding procedure chooses the correct sign.

Unless there's some way to check which sign is correct? I had some thought that something like that might be possible...

Say you blind a public key P = [p]G with blinding factor b, using P' = ECDH(P, b) = x([bp]P). Say you always choose the positive y coordinate for P', so now you have either P' = [bp]G (correct sign) or P' = [N - bp]G (wrong sign) (because 0 = A + (-A) = [a + N-a]G = [N]G = 0).

Now say you sign something in the WSCD using private key p, and modify the signature with blinding factor b so that the signature is valid under public key [bp]G instead of [p]G. You can try verifying the signature with [bp]G. If this succeeds, then P' = [b]P and you happened to choose the correct sign for y earlier. If this fails, then P' = [N - bp]G and you can try re-blinding the signature with blinding factor -b - then the signature will instead be valid under public key [(-b)p]G = [N - bp]G = P'. So we were able to get the signature blinded with the right key without another call to the WSCD.

Does that check out?

Therefore, it looks like we need multiplicative blinding in HDK.

Fair enough!

[sander]

Indeed, it looks like we could construct a method to compute EC-Scalar-Mult with at most one WSCD call, if we have a blindable signature that can be verified using the element as public key.

As of 5f1a31d I see these use cases for such a method:

• pk = EC-Scalar-Mult(sk_bl, pk_device) in HDK-Public-Key (typo: arguments should be the other way round): the method could be applied since we can obtain a blindable signature using the device key.
• P' = EC-Scalar-Mult(reader_data, sk_bl) in HDK-Authenticate: N/A since we don’t have a blindable signature created using the private key associated with reader_data.
• BL-Blind-Public-Key for multiplicative blinding: N/A since this is only applied by the issuer, who cannot obtain a blindable signature created using the private key associated with the blinding public key.

So we need to implement elliptic curve multiplication or addition anyway on both the issuer and the holder sides. So my “ease of implementation” argument should not support a multiplicative versus additive blinding decision.

After taking another look, possibly my other “Reopening this thread” argument falls away as well. We can compute:

x([sk_device]P + [sk_bl]P) = x(pk_device + [sk_bl]P)

applying addition and scalar multiplication within the rich execution environment. _Edit: made a mistake with pk_device. Still not easy._

One new reason for multiplicative versus additive blinding could be the Proof of Association requirements (#19).