[tahoe-dev] Fwd: On the value of "proofs"...

[zooko]

The following mail is from Ron Rivest to the SHA-3 working group and  
has to do with proofs of security in crypto, and it refers to some  
other recent work which has to do with particle physics, but the  
basic argument is one of two basic arguments that I have been wanting  
to make about Tahoe reliability estimates.

The chance that we made a significant mistake in our priors or in our  
math is much greater than 10^-9.  Therefore, if our estimate tells us  
that there is less than a 10^-9 chance of accidentally losing a file,  
we should not rely on that estimate.  It can be considered only an  
upper-bound on the reliability.

The other basic argument is that failure probability of tahoe servers  
are not independent of each other.  In the current allmydata.com  
production grid all servers are under the same ownership and the same  
operational control.  This means that there are several people who  
could singlehandedly destroy all the files on all the servers.  Of  
course none of them are the sort of people who are prone to flying  
into a drunken rage and destroying servers, but any failure analysis  
of the allmydata.com production grid which assumes that servers fail  
independently should be considered only an upper-bound on the  
reliability -- if the math says that the chance of losing a file is  
10^-9, then remember that the actual reliability is determined by the  
chance that one of those people will go into a drunken rage or  
otherwise make a big mistake, which is greater than 10^-9.

The same argument applies to a friendnet.  Suppose you deploy a Tahoe  
grid with 3-out-of-10 encoding and with one server in each of ten  
households of your extended family.  That's awesome!  It is extremely  
robust.  But it isn't 10^-9 robust -- the chance that 8 of those  
servers will get hit by the same virus or trojan horse in the same  
weekend is much higher than 10^-9.

Regards,

Zooko

Begin forwarded message:

> From: "Ronald L. Rivest" <rivest at mit.edu>
> Date: January 28, 2009 18:49:33 PM MST
> To: Multiple recipients of list SHA-3
> Subject: On the value of "proofs"...
>
>
> There is an interesting post on slashdot regarding the value of  
> "proofs":
>    http://science.slashdot.org/article.pl?sid=09/01/28/2247228
> regarding this recent posting:
>    http://arxiv.org/abs/0810.5515
>
> The authors are discussing the value of a "proof" that the LHC  
> (Large Hadron Collider) won't destroy the earth.  But their  
> arguments can be applied to any situation where one is trying upper  
> bound the (low) probability of a potential catastrophe.
>
> For example, their arguments could be applied to the adoption of a  
> new cryptosystem or hash algorithm.
>
> The authors argue (correctly) that such probability estimation (at  
> least from a Bayesian point of view) should take into consideration  
> the possibility (probability) that the proof itself is based on a  
> bad theory, or uses a model that is not correctly based on the  
> theory, or contains a mistake in a calculation based on the model.   
> Particularly when the probability of such errors is larger than the  
> final estimated probability itself.  If you're predicting that the  
> LHC has 10**-9 chance of destroying the earth, by using an argument  
> that has say a 10**-5 chance of containing an as yet undiscovered  
> error, what is the "real" probability of the LHC destroying the earth?
>
> Those of us supporting the use of "security proofs" are well aware  
> that proofs sometimes contain flaws; that is a fact of life.
>
> (At least with a bad cryptosystem the worst that could happen might  
> be, say, the collapse of the financial system, something far more  
> familiar and less catastrophic than falling into a man-made black  
> hole. :-) :-( )
>
> Skepticism towards "security proofs" is of course the right  
> attitude...
>
> The paper cited makes some suggestions (e.g. have independent teams  
> coming up with relevant proofs) that could be adapted to the  
> development of cryptosystems, to increase one's confidence in the  
> claims "proven".
>
> But the fact that proofs are sometimes flawed doesn't mean that one  
> shouldn't try to create them, any more than one would want to try  
> to design a bridge without doing the relevant stress calculations.  
> These are useful tools in building confidence in a design...
>
> Anyway, I recommend reading the cited paper; it does have relevance  
> to our situation in considering candidates for the AHS...
>
> Cheers,
> Ron Rivest