3.3.1 Blocking restoration systemwide

The basic disrupter attack against our scheme is to attempt to block restoration of as many machines as possible by controlling enough of their partners: any machine which has more than $m$ attacker machines as partners will believe its backups succeed, but come restoration time will find that it is unable to recover its data because the attacker machines refuse to cooperate.

In order to attack a large number of machines (presumedly for publicity) this way, the attacker will have to swap disk space with thousands of machines. The disk storage to do this directly, however, is beyond the budget of any likely attacker. However, by using a man-in-the-middle attack, a smart attacker can appear to be storing data for thousands of machines without using any local disk space. He simply steps between pairs of partners (see Section 2.1) and passes blocks back and forth, leaving each original partner to believe the attacker is backing up its data, when in fact they are still storing each other's data. If the attacker encrypts data going one way and decrypts data going the other way, he can ensure that when he bows out the stored data will be useless to the original partners.

We can prevent such man-in-the-middle attacks by changing our block-access protocols slightly. Intuitively, the idea is to provide only the following read operation: read a completely-random block. Unlike the normal read-specified-block operation, this operation cannot be passed through: if $\cal A$ does a random read (say block $r$ is chosen) of $\cal B$, there is no way for $\cal B$ to read block $r$ from $\cal C$ efficiently because each random read he does has only a $1/s$ chance of returning block $r$. On average $\cal B$ must read $s/2$ blocks to fulfill each random-read request of $\cal A$. This means that a small number of challenges by $\cal A$ will quickly force $\cal B$ to exhaust his read quota with $\cal C$ (see Section 3.2.3), leaving him unable to answer all of the challenges.

Figure 4: The random-read protocol where $\cal A$ is reading a block from $\cal B$. Commit(-) generates a nonmalleable commitment that is revealed in step 5; it hides $r1$ from $\cal B$ until step 5 while preventing $\cal A$ from changing her mind after seeing $r2$.

This restriction, of course, must be lifted while a restoration is in progress and may be lifted systemwide periodically so that cleaners can run efficiently. Figure 4 shows one way to formalize the random-read operation into a protocol. Steps 1-5 here, modulo the inclusion of $\cal A$'s name in the commitment, are a standard variant of the flipping-coins-by-telephone protocol [2]; step 6 returns the resulting chosen block, the one at offset $r1$ xor $r2$.

We include $\cal A$'s name--either $\cal A$'s current IP address, or if that is spoofable, a public key--in the commitment in step 2 to prevent the random-number-choosing protocol itself from being passed through: If $\cal B$ simply passes the commitment along to $\cal C$, he will be caught after he reveals the commitment in step 5 and $\cal C$ sees that it does not have $\cal B$'s name in it. He is prevented from fixing up the commitment to have his name while still containing $r1$ by the non-malleability of the commitment scheme [9]. Because he is unable to pass through the choice of $r1$, he is unable to trick $\cal A$ and $\cal C$ into agreeing on the same random number.