From mboxrd@z Thu Jan 1 00:00:00 1970 Date: Wed, 4 Feb 2009 11:40:51 -0500 From: Nathaniel W Filardo To: Fans of the OS Plan 9 from Bell Labs <9fans@9fans.net> Message-ID: <20090204164051.GU7757@masters6.cs.jhu.edu> References: <52ff22213469a7c44664b00697c28256@proxima.alt.za> <7bffd90986cd11342f8d01fbd53e84e0@quanstro.net> <140e7ec30902040040m64175f7eq771bf87b38153669@mail.gmail.com> MIME-Version: 1.0 Content-Type: multipart/signed; micalg=pgp-sha1; protocol="application/pgp-signature"; boundary="Pui5YDBJbCQuJ1A1" Content-Disposition: inline In-Reply-To: <140e7ec30902040040m64175f7eq771bf87b38153669@mail.gmail.com> User-Agent: Mutt/1.5.18 (2008-05-17) Subject: [9fans] Some arithmetic [was: Re: Sources Gone?] Topicbox-Message-UUID: 95659402-ead4-11e9-9d60-3106f5b1d025 --Pui5YDBJbCQuJ1A1 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline Content-Transfer-Encoding: quoted-printable On Wed, Feb 04, 2009 at 05:40:01PM +0900, sqweek wrote: > On Tue, Feb 3, 2009 at 9:54 PM, erik quanstrom wr= ote: > >> 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. >=20 > 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 =3D=3D 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; --Pui5YDBJbCQuJ1A1 Content-Type: application/pgp-signature Content-Disposition: inline -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.9 (GNU/Linux) iEYEARECAAYFAkmJxRMACgkQTeQabvr9Tc81YwCfSXi2XK4bJFOk/C44IfI5zxHj 6W8AnioX90brqr3VH+PJVlhsBypfWbRk =kpqq -----END PGP SIGNATURE----- --Pui5YDBJbCQuJ1A1--