Yes! You've found a vulnerability in the vulnerability report. And we have assigned a CVE² code to it: it's CVE-(CVE-2013-2293)-2012-0001 

But unluckily I think there is a vulnerability in the that code

I will edit the original post..

Good, a new idea. Nevertheless there must be a hard limit (say 10 Mbytes) for DoS protection reasons.

That formula does not work, it just keeps rising fees.

What about this alternative:

1. fees equal or greater than the average fees of the last 50 blocks are always accepted.
(This allows any used to put whatever high fee he may want, and it's predictable)

2. fees lower than the average are passed through the CoVar test (including the highest part)
(this reduces the changes of spamming txs with almost zero fees)

The key difference is that the average is not taken for the last block, but for a number of past blocks.
I will this method Restricted-CoVar for reference.

This method looks self-healing: 
- if the 50b-average fees goes down, many more transactions with higher fees are included, then the average goes up.
- if the 50b-average goes up too much, then everybody will send lower transaction fees, and the average goes down, but not too fast, since the CoVar limits it.

Yes, the same idea. And it's a pity it passed unnoticed. I would prefer everybody writes their ideas in the Bitcoin wiki, so the common knowledge is increased.

My idea of discarding the transactions in the 10% of the highest fees before computing CoVar is sound. Obviously miners can manipulate everything, but the point is that they always act rationally, so why would they insert transactions to change the CoVar? And how much time will they invest finding the correct transactions to insert? That problem is, probably, very hard.

You are completely right. I can't promise I'll do it in the near future, but I'll start writing it down in a formal way. Also I will take into consideration block-chain statistics and the excellent critics the idea have received.

But if anyone is interested in writing this paper instead of me, be my guest.
Maybe a game-theoretic thesis can come out from this analysis.

Yes.
One solution would be to use Robust statistics, like the median instead of the mean to divide the Standard deviation. Or the Median absolute deviation divided by the median. Let's call it CoVar*. So CoVar* will work as CoVar, but won't be affected by outliers.

Here is an example of what Zeilap  sais:

Suppose the set of transaction fees available is:
1,1,1,1,1,1,1,1,1,1,1,1,2,10

Suppose the maximum CoVar is 1.

We compare two possible sets to choose, one containing 10 and another without it:

(A) 1,1,1,1,1,1,1,1,1,1,1,1,2
(B) 1,2,10


Results for A:

Sum=14.00
Mean= 1.08
Variance= 0.07
StdDev= 0.27
CoVar= 0.25

Results for B:

Sum=13.00
Mean= 4.33
Variance=16.25
StdDev= 4.03
CoVar= 0.93

So the set A pays more fees, and so it will be chosen.

I would discard the 10% percentile, as I said.

It just goes against his own interests. Why would he do that? There is no memory between blocks, so a block cannot influence the next.

Zeilap: This is getting really interesting...


This can be very easily avoided. Before calculating the CoVar, sort them by fees, and remove from the CoVar computation the transactions that in the 10% percentile that pay most.

Then you'll always be able to get the transaction into the next block: send the fee high enough to be in that percentile.

But I'm unsure if a high fee transaction would be ever discarded. I will simulate this.

We should consider the solution using CoVar I proposed. It hurts no one, and it helps a lot with SD.

Yes, as I added to the original post: it's not a solution against malicious miners. Only against selfish (and irrational)  miners that do not think about the future of Bitcoin.

Rational miners choose smaller transactions because:

1. Gives extra space to put more transactions in the block
2. Reduces the propagation time.

So there is enough incentives to include smaller txs.

A historical analysis of the block chain must be done, but I don't have the right tools to do it. (a ready to run development environment).
If would choose the maximum historical CoVar as the fixed constant (maybe probably removing the 5% highest percentile).

But this value will be clearer when you have the historical data.

Maybe someone who develops BitcoinJ or the Satoshi Client can provide us with a graph CoVar/Time ?

Maybe there is some hidden information related to SD and spamming txs there that we have overlooked.

Note that a miner could also drop transaction with very high fees in order to collect many transactions with lower fees, but I find it very rare in practice, since transactions consume block space.

I also think that even if the high-to-low fee selection algorithm is fast and greedy O(n), an optimum algorithm that maximizes fees with the dispersion restriction would be O(n^2), where n is the number of transactions to test.


 

The idea is simple, butrequires a hardfork, but is has minimum impact in the code and in the economics.

Solution: Require that the set of fees collected in a block has a maximum dispersion. Use, for example, the Coefficient of Variation (http://en.wikipedia.org/wiki/Coefficient_of_variation). If the CoVar is higher than a fixed constant, the block is invalid.

The Coefficient of variation is computed as the standard deviation over the mean value, so it's very easy to compute. (if the mean is zero, we assume CoVar=0). Note that the CoVar function does not depend of the scale, so is just what a coin with floating value requires.

This means that if there are many transactions containing high fees in a block, then free transactions cannot be included.
The core devs should tweak the transaction selection algorithm to take into account this maximum bound.

Example

If the transaction fee set is: 0,0,0,0,5,5,6,7,8,7
The CoVar is 0.85
Suppose we limit the CoVar to a maximum of 1.

Suppose the transaction fee set is: 0,0,0,0,0,0,0,0,0,10
Then the CoVar is 3.0

In this case the miner should have to either drop the "10" from the fee set or drop the zeros. Obviously the miner will drop some zeros, and choose the set: 0,10, that has a CoVar of 1.

Why it solves SD Problem?

Using this little modification, users of SatoshiDice would require to use higher fees, only if the remaining users in the community rises their fees. And miners won't be able to include an enormous amounts of spamming txs.

Why it solves the futue fee problem? (and the tragedy-of-the-commons "problem")

Because as miners are forced to keep the CoVar low, if people rises the fees to confirm faster than spamming txs, automatically smamming txs become less likely to appear in blocks.

Why it solves the block size problem?

Because if we increase the block size, miners acting irrationally won't be able to fill the block with spamming txs. Edit: This is not a solution against an attacker-miner.

Best regard,
  Sergio.

Edit: PLEASE don't confuse the acronym CoVar I used here with co-variance.

You can do it yourself! To become a contributor to the wiki you just have to send a contribution (which can be tiny of you want) to a Bitcoin address (as an Spam protection measure)

Does the wallet stores the used addresses forever, even if all the coins used by these addresses have been sent to other users?

It would be an interesting property to optionally provide forward anonymity, so if a computer is compromised by an attacker, then the attacker cannot reconstruct the transaction history based on the private keys in the wallet.

Those old private keys should be securely erased from memory and disk.

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.

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.

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.