How to compromise SatoshiDice "1dice" private keys (theoretical attack)

[Sergio_Demian_Lerner]

This is not a finished vulnerability report. I've discover a potential vulnerability in how SatoshiDice signs the result transactions (payouts). To be a real vulnerability I must assume some inner workings of SatoshiDice that I don't really know, since the server is not open source, the only way to test it would be to actually execute the attack, which is something I'm not considering. Also I assume that the Brumley/Tuveri  attack on the montgomery ladder multiplication algorithm can be adapted to the NAF (Non-Adjacent Form) multiplication algorithm of BouncyCastle. This adaptation is not direct, since the multiplication described in the paper is highly regular (does not depend on the hamming weight of the random value k) and NAF multiplication in BC is irregular. Nevertheless, for this exact reason, it is also possible that another timing attack (that exploits its irregularities) can be adapted successfully.

I present two theoretical attacks, one that can be executed if the attacker is in the same LAN and another that can be executed from any PC connected to Bitcoin regarding the hop distance to SatoshiDice.

Both attacks should be able to recover SatoshiDice's private signing keys, so all SatoshiDice funds from bets can be stolen by the attacker.


Assumptions:

1. SatoshiDice processes the bets one by one sequentially.

2. When a transaction contains many bets (outputs), they are also processed sequentially in increasing order.

3. SatoshiDice uses BouncyCastle for creating the payout transactions (Mike Hearn and others say so)

4. The attack described in the paper "Remote Timing Attacks are Still Practical" by Billy Bob Brumley and Nicola Tuveri can be adapted to the BouncyCastle default scalar ECC multiplier (org.spongycastle.math.ec.FpNafMultiplier). The attack is based on this timing side channel. Because FpNafMultiplier multiplies the number of iterations by 3, the number of leading zero bits is amplified, so the attack is more powerful than in the paper. Nevertheless, the irregularities of the algorithm implementation increases the variance, so this would be a subject of more research..

5. The timestamp retrived by the API http://src.satoshidice.com/longpoll.php has low jitter (e.g. 1 millisecond)

6. The service http://src.satoshidice.com/longpoll.php accepts at least a connection latency of 1 msec between connections, and at least 10 concurrent connections.

Attack 1 - Same LAN

For this attack, the attacker must be near SatoshiDice (1 hop) and preferably in the same LAN.
The attacker submits thousands (e.g. 10K) of very tiny bets, each one in a different transaction. Since each bet is responded by a new transaction signed by SatoshiDice, he measures the RTT and so he can measure the time it takes for each transaction to be signed. This is the collection phase. Afterwards the procedure in the Brumley paper is followed and .. . vuala!

Attack 2 - Any place in the world


The attacker also sends many bets, e.g. 10K, but his time the attacker packages two bets in a single transaction. After each transaction is sent, the attacker opens multiple connections to the service longpoll offered by Satoshi Dice with two different arguments, in two groups (This service allows to poll the outcome of specific outputs).  The first group consist of 100 request, spaced 1 msec each, to detect the exact time the first output was evaluated. The second, another 100 request, spaced 1 msec each, to detect when the second output was evaluated.

The longpoll service returns strings in the format:

 Returns:
  {
  "bets":[ ...    
  ],
  "polls":1,
  "starttime":1361422211.3701
}

Where:
 polls is the number of polls made to the SatoshiDice core engine,
 starttime is an accurate timestamp of when the first poll was made.

Since polling is done at a frequency of approximately 4 hz, responses with polls>1 should be discarded as inaccurate in time. Only the responses with polls=1 should be considered. From the responses with polls =1 , the one with lowest timestamp will mark the most accurate timing measurement t.

From the first group we get t1
From the second group we get t2.

The time taken to process output 2 is therefore (t2-t1).

These measurements are fed into the collection phase of the attack. Then the attack proceeds as shown in the paper.
It's possible to package many more bets in a single transaction to gather more information from each transaction and reduce the fees needed.
Also note that the Bitcoins used in the attack are not wasted, since most of them is returned. Only 1.9% is paid to the house.

The attack can take between a 4 hours and 1 day depending on the number of tries per second. It's not necessary that the transaction get into the block, since SatoshiDice work on 0 confirmations.

Possible Solutions

- Code a multiplication algorithm protected from timing attacks, such as the one in the last version of OpenSSL.

OR

- Remove the decimals from the timestamp field. Leave only 1 second accuracy.
- Delay a random number of milliseconds before sending each payout transaction.
- Accept transactions with 1-confirmation
- Delay the response of the longpoll service a random number of milliseconds.


Best regards,
 Sergio.

[dust]

- Delay a random number of milliseconds before sending each payout transaction.
- Delay the response of the longpoll service a random number of milliseconds.

Adding a random delay does not prevent timing attacks.  With a large enough sample, statistical analysis can see through the random noise.

[Sukrim]

Probably relevant: http://www.youtube.com/watch?v=1q1u8Bq1l6g

[Mike Hearn]

The SD source is open, actually, at least some of it is. See fireducks clone of bitcoinj.

It doesn't surprise me that Bouncy Castle is open to timing attacks and upgrading to a better crypto implementation, away from BC, has been on my todo list for a long time. It's only a matter of time until somebody loses money either due to weak RNGs or timing attacks on ECDSA using some kind of software (maybe not bcj but something, perhaps even custom hardware wallets). SD is hosted in Amazon AWS so getting a computer on the same LAN segment is probably not very difficult.

My preferred long term solution to this is for the Bitcoin world to switch to ed25519, the reference implementations of which are both simple, fast and timing attack resistant. They're also resistant to various other exotic things like branch prediction attacks.

In the shorter term, making bitcoinj use a better crypto library like OpenSSL or NaCL is the way to go. It will unfortunately complicate distribution and the build for the Android app, but that can't be avoided. I'd prefer NaCL but it seems it doesn't support the signing mode we need, so it may be that OpenSSL wins again It may be possible to extract the ECDSA code from OpenSSL into a minimal library so we don't end up with conflicts against other versions of OpenSSL that may be loaded into the address space.

[Peter Todd]

- Delay a random number of milliseconds before sending each payout transaction.
- Delay the response of the longpoll service a random number of milliseconds.

Adding a random delay does not prevent timing attacks.  With a large enough sample, statistical analysis can see through the random noise.

Bingo.

The right solution is to send packet on a fixed schedule. Batch outgoing payout transactions and periodically, say every 100ms for Satoshidice, send all the batched transactions out in random order. Because the sends now happen on a fixed schedule, all timing information with a resolution less than the schedule is destroyed completely.

This idea can be done by a totally different computer too. For instance you can put the scheduler in a separate Bitcoin node, or even as a separate router box that applies the fixed schedule to every IP packet.

Sukrim's video mentions a slight variant of the fixed schedule, pad to max, at 22:17. He calls it slow and inefficient, but in the case of Satoshidice a fixed 100ms delay would be perfectly acceptable.

[jl2012]

Is it possible to retrieve the private key of MtGox green address in the same way?

[Sergio_Demian_Lerner]

- Delay a random number of milliseconds before sending each payout transaction.
- Delay the response of the longpoll service a random number of milliseconds.

Adding a random delay does not prevent timing attacks.  With a large enough sample, statistical analysis can see through the random noise.

Yes I knew that, but the attack is much more inefficient..
My point was that the right solution was to fix the signature algorithm.

I also like jl2012 idea of time slots.

[Sergio_Demian_Lerner]

One of the interesting things about this timing attack is that it can be executed from many hops away, which is very rare. The fact that SD provides the service to timestamp with fine granularity signature verifications is the source of the headache. A classical defense is to send the result messages in time slots, but in this case such defense would be pointless because of the published timestamps which mark the beginning of each signing operation.

Regarding BouncyCastle multiplication algorithms, the implementations are so clear and readable that I think they can be easily modified to prevent timing attacks, using the OpenSSL code and others papers as reference.

[Mike Hearn]

That'd certainly be an alternative. I tend to think though that it's better to get onto the implementation that security researchers tend to patch when new attacks come out. OpenSSL is ugly as sin but it's got a lot of support.