The goal of this protocol is for Bob to get Alice to perform a Diffie-Hellman key exchange blindly, such that when the unblinded value is returned, Alice recognizes it as her own, but can’t distinguish it from others (i.e. similar to a blind signature).
Alice:
A = a*G
return A
Bob:
Y = hash_to_curve(secret_message)
r = random blinding factor
B'= Y + r*G
return B'
Alice:
C' = a*B'
(= a*Y + a*r*G)
return C'
Bob:
C = C' - r*A
(= C' - a*r*G)
(= a*Y)
return C, secret_message
Alice:
Y = hash_to_curve(secret_message)
C == a*Y
If true, C must have originated from Alice
I unearthed this protocol from a seemingly long forgotten cypherpunk mailing list post by David Wagner from 1996 (edit: perhaps not as forgotten as I thought, as Lucre is an implementation of it). It was devised as an alternative to RSA blinding in order to get around the now-expired patent by David Chaum. As in all ecash protocols, the secret_message
is remembered by Alice
in order to prevent double spends.
One benefit of this scheme is that it's relatively straightforward to perform in a threshold setting (only requires curve multiplication). One downside is that validation is more involved than simply checking a signature, as this step requries repeating the Diffie-Hellman Key Exchange.
The protocol also has one additional weakness that can be addressed. Bob can't be certain that C'
was correctly generated and thus corresponds to a*B'
. Alice can resolve this by also supplying a discrete log equality proof (DLEQ), showing that a
in A = a*G
is equal to a
in C' = a*B'
. This equality can be proven with a relatively simple Schnorr signature, as described below.
(These steps occur once Alice returns C')
Alice:
r = random nonce
R1 = r*G
R2 = r*B'
e = hash(R1,R2,A,C')
s = r + e*a
return e, s
Bob:
R1 = s*G - e*A
R2 = s*B'- e*C'
e == hash(R1,R2,A,C')
If true, a in A = a*G must be equal to a in C' = a*B'
Thanks to Eric Sirion, Andrew Poelstra, and Adam Gibson for their helpful comments.
I'd like to introduce a doubt which make me reflect on a cunning exploitation of the malleability in the protocols, a subtle deception that could be seen as a type of 'blinding' attack.
Our protagonist, Bob, craftily manipulates his own blinding factor in a Diffie-Hellmann key exchange. He creates a seemingly valid but illegitimate token pair, which can then pass through the protocol undetected. This undermines the protocol's intent, potentially leading to inflation of token supply.
Scenario: Bob (Attacker)
Choose$x'$ and $r'$ such that $Y' + r'G = Y + rG \implies Y' = Y + (r - r')G$
This equation means that for a specific difference$(r - r')$ , Bob can compute an $x'$ which will result in a $hashToCurve(x') = Y'$ that is equal to $Y + (r - r')G$ .
Given:
$$B' = Y' + r'G$$
Substitute$Y'$ :
$$B' = Y + (r - r')G + r'G $$
Bob manages to create a$B'$ that is actually equal to the legitimate $B$ , but derived from a different secret $x'$ . He sends $B'$ to Alice.
Alice:
$$C' = aB' $$
Alice sends$C'$ back to Bob.
Bob:
$$C = C' - r'A $$
$$C = aY' $$
$$C = a \cdot hashToCurve(x') $$
Bob returns$C$ and $x'$ as the token pair.
Alice:
$$Y' = hashToCurve(x') $$
$$C = aY' $$
If true,$C$ must be a valid Alice signature. But in this case, $C$ was created by Bob manipulating the protocol to create a $C$ that appears legitimate but corresponds to an illegitimate $x'$ . This attack is successful because of the commutative property of addition in the elliptic curve group, allowing Bob to choose an $r'$ that makes his illegitimate $B'$ indistinguishable from a legitimate $B$ .
This scenario emphasizes the importance of ensuring Bob can't manipulate his random blinding factor$r$ in a way that lets him forge a seemingly valid $B'$ and the corresponding token pair $(x', C)$ .
Indeed, this scenario reveals the critical necessity of mitigating Bob's ability to manipulate his random blinding factor$r$ , thereby averting him from forging a seemingly legitimate $B'$ and corresponding token pair $(x', C)$ .
There are several potential strategies to counter this attack. These are, however, not without their trade-offs and should be analyzed considering the specific requirements of your system:
Use of Commitment Schemes: Before the key exchange, Bob could be required to commit to his secret and blinding factor using a cryptographic commitment scheme. Later, when the protocol has been executed, he can reveal the secret and blinding factor. Alice can then verify that the values match the commitment. This way, Bob cannot change his values midway through the protocol. However, this might introduce an additional complexity and require multiple rounds of communication.
Cryptographic Nonces: Bob's blinding factor could be generated as a cryptographic nonce that follows a specific rule set or pattern that Alice can verify without knowing the exact value of the nonce. However, this could potentially reduce the randomness of the blinding factor and hence weaken security, if not done carefully.
Secure Randomness Generation: Ensuring that Bob uses a securely generated random blinding factor could make it computationally unfeasible for Bob to find an alternative pair$(x', r')$ that gives a legitimate-looking $B'$ . However, it might be challenging to enforce this in practice.
Zero-Knowledge Proofs: Bob could provide a zero-knowledge proof that shows he generated$B'$ according to the protocol, without revealing his secret or blinding factor. Implementing zero-knowledge proofs can be complex and might require additional computational resources.
UPDATE
I’ve tried to calculate the probability of finding a correct pair (x’, r’) to exploit this attack. While it’s indeed not computationally feasible to find the value of x’ it might be very important to ensure that both the value 'x' and the blinding factor 'r' are chosen from a space of a big enough size. For example if 'x' is constrained to be the utf-8 encoding of a small word as “test”, an attacker has a much easier task in trying to manipulate it to perform the attack. Anyway, after carefully evaluating and reflecting on the feasibility of such attack, I agree with what you guys said. It’s indeed almost impossible. It’s been interesting to delve deeper into this type of attack. 🙏