🪂0xPARC StealthDrop: Nondeterministic Nullifier

Book an audit with Zokyo

Summary

Related Vulnerabilities: 1. Under-constrained Circuits, 2. Nondeterministic Circuits

Identified By: botdad

StealthDrop requires users post a nullifier on-chain when they claim an airdrop. If they try to claim the airdrop twice, the second claim will fail. However, ECDSA signatures were used as the nullifier and these signatures are nondeterministic. Therefore different signatures were valid nullifiers for a single claim and users could claim an airdrop multiple times by sending the different valid signatures.

Background

In order to claim an airdrop, users must post a nullifier on-chain. If the nullifier is already present on-chain, the airdrop will fail. The nullifier is supposed to be computed in a deterministic way such that given the same input parameters (the user’s claim in this case), the output nullifier will always be the same. The initial nullifier generation process required users to sign a particular message with their ECDSA private key. The resultant signature is the nullifier that they need to post on-chain when claiming an airdrop.

The Vulnerability

ECDSA signature validation is nondeterministic - a user can use a private key to sign a message in multiple ways that will all pass signature verification. When users create the SNARK to claim an airdrop, they use the nullifier as a public input. The SNARK circuit enforces that the nullifier is a valid signature. Since the users can create multiple valid signatures with the same key and message, they can create multiple proofs with different nullifiers. This allows them to submit these separate proofs and claim an airdrop multiple times.

The Fix

Instead of only constraining signature validation in the SNARK circuit, constraints must also be added on the signature creation process so that the signatures are deterministic. This was originally left out because in order to constrain the signature creation process, the private key is needed as a private input. The StealthDrop team wanted to avoid involving the private key directly. However, due to the vulnerability described, the private key is needed in the circuit to make the signature creation process deterministic.

Conclusion:

The summary provides a brief on a vulnerability discovered in the "StealthDrop" system. This system aimed to ensure users could only claim an airdrop (free distribution of tokens/coins) once, by using a unique identifier called a "nullifier." The problem arose because the chosen nullifier, an ECDSA signature, could be generated in different valid forms, thus allowing users to claim an airdrop multiple times.

1. Nullifier: This is a unique identifier. In the context of StealthDrop, it is used to determine if a user has already claimed an airdrop. If the nullifier has been used (i.e., is already on-chain), the user can't claim the airdrop again.

2. ECDSA as Nullifier: StealthDrop decided to use the ECDSA signature of a user as their nullifier. When a user wanted to claim an airdrop, they would sign a specific message with their private key, and this signature would serve as the nullifier.

3. The Vulnerability: ECDSA, by nature, is nondeterministic. This means that the same message signed with the same private key can produce different, but all valid, signatures. This is problematic because each of these different signatures can be used as a distinct nullifier, allowing a user to claim multiple airdrops when they should only be allowed one.

4. SNARK and Nullifier: SNARK is a cryptographic proof system. When a user claims an airdrop in StealthDrop, they provide a SNARK proof using their nullifier as a public input. The SNARK system then checks if the nullifier is a valid signature (among other things). However, since a user can create many valid signatures for the same message with the same private key, they can generate many proofs with different nullifiers. This allows them to bypass the intended restriction and claim the airdrop multiple times.

5. The Fix: To rectify the vulnerability, the process to create signatures (nullifiers) must be made deterministic (i.e., always produce the same output for the same input). To achieve this determinism, the private key of the user must be involved in the creation process. Initially, StealthDrop didn't want to use the private key directly due to privacy/security concerns, but it became essential to prevent the exploit.

In simple terms, the system wanted to use signatures as unique identifiers to prevent users from claiming freebies more than once. However, because the type of signature they chose can be made to look different even when coming from the same user, some users could claim multiple freebies. To stop this from happening, the signature creation process needed to be adjusted to always produce the same signature for the same user, which required incorporating the private key directly into the system.

Why are ECDSA (Elliptic Curve Digital Signature Algorithm) nondeterministic?

ECDSA (Elliptic Curve Digital Signature Algorithm) is nondeterministic due to one of its components in the signature generation process: a random value $�k$. If this random value changes, even if the message and the private key remain the same, the resulting signature will be different.

Let's go through the basic workings of ECDSA:

Step 1: You have a message that you want to sign.

Step 2: You choose a random number $k$ and compute the point $(x1​,y1​)$ that is $k$ times the standard generator point $G$ on the elliptic curve. The value $x1​$ becomes part of your signature.

Step 3: You compute the other part of the signature, $s$, using $x1​$, $k$, your private key $d$, and the hash of the message $H(M)$.

Step 4: Your signature for the message $M$ is $(x1​,s)$.

If you change $k$ and redo the signature process for the same message with the same private key, $x1​$ will be different because the point on the curve will be different. Consequently, $s$ will also be different because it's based on $x1​$. This will yield a completely different signature $(x1​,s)$ for the same message.

Example: Let's simplify this with a hypothetical scenario:

1. Alice wants to sign the message "Hello".

2. Alice chooses a random number $k=5$ and gets $x1​=10$ (the numbers here are completely fictional for simplicity).
3. Alice computes $s$ and gets $s=20$.
4. Alice's signature for "Hello" with $k=5$ is $(10,20)$.

Now, if Alice chooses a different $k$, say $k=7$, she might get $x1​=15$ and $s=25$. Her signature for "Hello" with $k=7$ is $(15,25)$.

Both signatures $(10,20)$ and $(15,25)$ are valid for the message "Hello" signed by Alice, even though they are different.

In a real-world scenario, deterministic ECDSA has been proposed (and is used in some systems like Bitcoin) where $k$ is not purely random but is derived deterministically from the message and the private key, ensuring the same signature for the same message every time.

References

1. 0xPARC Twitter Thread Explanation