[9fans] Some arithmetic [was: Re: Sources Gone?]

[Nathaniel W Filardo <nwf@cs.jhu.edu>]

[-- Attachment #1: Type: text/plain, Size: 3489 bytes --]

On Wed, Feb 04, 2009 at 05:40:01PM +0900, sqweek wrote:
> On Tue, Feb 3, 2009 at 9:54 PM, erik quanstrom <quanstro@quanstro.net> wrote:
> >> Yes, but the content isn't guaranteed to be from a single user.  In
> >> fact, venti has no clue.  Change that and it's not venti anymore.
> >
> > exactly.  but it's important to note that it's crypto hard to guess
> > somebody else's block.
> 
>  Is it? Well, to guess a specific block, obviously.
>  I'm pretty ignorant about the structures used to store trees in venti
> - would it be possible to reconstruct the block containing the root of
> a particular tree given say, /n/dump?

Presumably only if you could read all the data under /n/dump, in which case
there isn't a security risk.

>  Presumably something along the lines of "vac /n/dump/2009/0204" would
> suffice, but failing that you still don't need to guess exactly the
> block you are looking for... How long would it take to brute force a
> block of a tree (giving you references to lots of other blocks) from
> venti?

Assuming SHA-1 is indeed cryptographically secure (which is the assumption
made by the venti paper), you know only the type of the target block and no
bits of its score regardless of any partial information you know about the
block (total information obviously gives you the score).  Assuming you don't
care which block you read from the venti, and that the venti is storing K
blocks of the requisite type, the odds of you guessing the score of any
block stored is K/2^160.

If you're after data blocks and the venti is storing an exbibyte (2^60 bytes
== 2^47 8Ki blocks), I expect you'd have to take 2^113 queries to find your
first data block.

Assuming the venti is backing a fossil and has been running for 2^13 days
(roughly 22 years), there are 3*2^13 "root-like" scores stored (AFAIK: one
root for today's dump, one root of all past dumps, and one block that stores
both of these scores), so I expect you'd take 2^(147)/3 queries to find one.
Obviously some of these are more powerful than others, in terms of exposure,
so you might be relatively lucker or unluckier if you found a root block, in
which case you probably want to go buy as many lottery tickets as you can.

Given those odds, if somebody wants my vac scores, they'll break into my
office and steal the venti, or employ rubber hose cryptography.  Or maybe
SHA-1's really, really broken and has a much smaller output domain than
2^160...  in which case, somebody should write a version of venti that uses
one of the SHA2 variants or another hash.

If you need additional assurances, bear in mind that somewhere around 2^192
addition operations requires 32 years with a perfect Dyson sphere around the
sun and a thermodynamically perfect computer at 3.2K. Harnessing a typical
supernova gives 2^219 addition operations (Schneier, Applied Cryptography,
pp 158).  Assuming those figures are right, and that we lack a Dyson sphere
and there are no conveniently nearby supernovae, but that we can turn the
entire sun-facing solid angle of the earth into a similarly perfect
computer, we get 2^192/2^32*(4.5 x 10^(-10)) ~~ 2^129 addition operations in
a year (that magic number is the area of a circle with radius matching that
of the earth to the entire surface area of a sphere with radius one
astronomical unit).  That might be enough to find a data block with high
odds but not a root block under the above assumptions. :)

--nwf;

[-- Attachment #2: Type: application/pgp-signature, Size: 204 bytes --]