The crypto-currency Monero is about to introduce a new milestone in Blockchain technology: RingCT. This is a scheme that allows using Confidential Transactions (CT) while keeping the non-interactive coin mixing typical for Monero. CT enables hiding the transaction amounts from anyone but sender and receiver while full nodes are still able to verify that input amounts are equal to output amounts. RingCT is currently not active in Monero; it is designed to be introduced as a hard fork early January.
I am a complete outsider to Monero and especially the Monero development community, but having reviewed the CT design and implementation (in libsecp256k1) extensively during my day job, I was very interested in the design decisions underlying RingCT. Very quickly I found a red flag in the ring signature scheme called ASNL used in the range proofs. This scheme is a new contribution by the paper and indeed turned out to be exploitable such that an attacker would be able to create coins from nothing. You can find the exploit code on GitHub and a detailed explanation in this post.
While writing the exploit code and preparing this blog post I learned that an anonymous person called RandomRun reported a flaw in the security proof of ASNL, which convinced the Monero devs to publish a bugfix release that switches to Borromean signatures (good call!). As a result the upcoming hard fork will not be vulnerable to this exploit. Interestingly, the error in the security proof is exactly the flip-side of the vulnerability discussed in this post.
I have the highest respect for RandomRun and parts of the Monero community. It takes an incredibly strong character to drop an 0day worth tens of millions USD. However, that the original hard fork schedule of RingCT remains unchanged despite a complete break of the system raises more than a few questions. Even more so when the author of RingCT called for more review by the end of October.
Aggregate Schnorr Non-linkable Ring Signature (ASNL)
Confidential transactions include a range proof to prevent negative amounts.
These range proofs use a generalization of ring signatures in which
the conjunction of multiple rings is proven, for example that the prover knows the discrete logarithm of
(Pk1 OR Pk2) AND (Pk1 OR Pk3) AND ...
The original CT scheme introduced Borromean signatures for that purpose which are based on rings of hashes and provide space savings when public keys appear more than once.
Instead, the RingCT paper proposes a new scheme called Aggregate Schnorr Non-linkable Ring Signature because it has “perhaps simpler security proofs” (RingCT paper).
A ASNL signature consists tuples
(P1_j, P2_j, L1_j, s2_j) for
j = 1, ..., n and
is supposed to prove that the signer knows the DL of
(P1_1 OR P2_1) AND ... AND (P1_n OR P2_n).
Let’s consider the
n = 1 case (no conjunction) informally.
The verifier checks that
H is a hash function.
- The prover knows the DL
1 2 3
- Or the prover knows the DL
1 2 3
In the case of multiple conjunctions (
n > 1), the verifier computes
LHS <- L1_1 + ... L1_n and
RHS <- s*G + H(s2_1*G + H(L1_1)P2_1)P1_1 + ... + H(s2_n*G + H(L1_n)P2_n)P1_n and checks that
LHS = RHS.
In short, this is vulnerable because you can just choose some
L1_j such that it cancels out the summand on the right hand side where both DLs of P1 and P2 are unknown.
In contrast, the “proof” of security of ASNL assumes that any adversaries knows
a*G = L1_j for all
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27