Exploiting Low Order Generators in One-Time Ring Signatures

Last week the Monero team disclosed a major bug in CryptoNote based cryptocurrencies (reddit thread) which could be used to create “create an infinite amount of coins”. Monero itself was quietly fixed in February (release, pull request) and the since then every user syncing the blockchain from scratch validates that it was never exploited in Monero. However, it was used in CryptoNote based shitcoin ByteCoin to create about 700 million coins out of thin air.

There are already a few good explanations of the bug, for example at the Monero StackExchange and the modern crypto mailing list. This article gives additional background about the signature scheme and the properties of the curve that allowed this bug to slip in.

Apart from the value at stake, this bug is interesting because it shows the risks of breaking a specialized cryptosystems such as Ed25519 apart and apply the parts in other contexts. Ed25519 is designed for plain cryptographic signatures and the curve it is based on is used in CryptoNote to implement one-time ring signatures. In contrast to a regular signature scheme, one-time ring signatures using the curve require that part of the signature does not generate a small subgroup. Ensuring this is necessary when using curves with a cofactor. CryptoNote did not do that.

A Problem With Monero’s RingCT

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.

EDIT: The Monero community reacted to this article (see reddit) but they didn’t like its style. Also, they got the timeline of the discovery of the bug wrong.

Data-Driven De-Anonymization in Bitcoin

Slides

Abstract

We analyse the performance of several clustering algorithms in the digital peer- to-peer currency Bitcoin. Clustering in Bitcoin refers to the task of finding addresses that belongs to the same wallet as a given address. In order to assess the effectiveness of clustering strategies we exploit a vulner- ability in the implementation of Connection Bloom Filtering to capture ground truth data about 37,585 Bitcoin wallets and the addresses they own. In addition to well-known clustering techniques, we introduce two new strategies, apply them on addresses of the collected wallets and evaluate precision and recall using the ground truth. Due to the nature of the Connection Bloom Filtering vulnerability the data we collect is not without errors. We present a method to correct the performance metrics in the presence of such inaccuracies. Our results demonstrate that even modern wallet software can not protect its users properly. Even with the most basic clustering technique known as multi- input heuristic, an adversary can guess on average 68.59% addresses of a victim. We show that this metric can be further improved by combining several more sophisticated heuristics.

Read full thesis

Exploiting CSGOJackpot’s Weak RNG

CSGOJackpot is a gambling website where players bet and win Counter Strike Go ‘skins’ (weapon textures). Because these items can only be found by playing a lot of CSGo, they are quite rare and valuable,
and can be exchanged for example in Steam’s own Marketplace. What is fascinating about CSGOJackpot and initially captured my attention is the sheer amount of value that is gambled away. On average, more than 20,000$ are thrown into the pots per hour.

TL;DR: CSGOJackpot is a node.js app that uses Math.random() to determine the winning ticket. Of course, it’s not cryptographically secure and trivial to predict the next number given two outputs of the random number generator. I did not try to profit from this vulnerability but for the lulz I set up a twitch stream and revealed the next winning percentage in exchange for a drawing of Gabe Newell. See the submission gallery and a recording of the stream.

EDIT: There was quite some discussion about this issue on /r/GlobalOffensive.

EDIT 2: This vulnerability does not exist anymore in CSGOJackpot and I don’t know a similar site which is vulnerable.

Bitcoin Seeder DoS Vulnerability

The DNS parser of the Bitcoin Seeder was vulnerable to a denial of service attack. A specially crafted DNS request could trigger infinite recursive function calls that lead to a stack overflow. See the exploit. The vulnerability was fixed in commit 11e935b.