Re: [9fans] Some arithmetic [was: Re: Sources Gone?]
Assuming SHA-1 is indeed cryptographically secure (which is the assumption made by the venti paper) Well, I read it like it was just sufficiently secure against unintended collisions. It's not intended to encrypt, but to efficiently store data. While SHA-1 is indeed not intended to encrypt, it *is* intended to be a secure hash (hence the name). In order for it to do that job, it must be computationally difficult for somebody to find colliding material. If it's easy to guess venti scores for file-system roots, that suggests that SHA-1 systematically doesn't cover certain parts of the output space. If that is true, that would be a big help for people trying to find collisions (and, hence, forge signatures). It could be that way, but a lot of people are still acting in ways which will be painful if it is. Said another way: SHA-1 is designed to be a different kind of checksum than CRC-32. CRC's are designed to defend against accidental corruption, but SHA-1 really is designed to make deliberate collisions hard. Dave Eckhardt
Re: [9fans] Some arithmetic [was: Re: Sources Gone?]
Even if venti scores are completely unguessable, using them as an authentication mechanism is a mistake, because you can't change them. It would be like having a fixed, unchangeable password assigned to your account: once the password leaked out into the world, one way or another, you'd have no way to stop anyone on the internet from masquerading as you or telling the password to others. http://www.google.com/search?q=09+f9; Russ
Re: [9fans] Some arithmetic [was: Re: Sources Gone?]
http://www.google.com/search?q=09+f9; is that a legal url? - erik
Re: [9fans] Some arithmetic [was: Re: Sources Gone?]
On Thu, 2009-02-05 at 12:41 -0500, erik quanstrom wrote: http://www.google.com/search?q=09+f9; is that a legal url? I don't think it is a legal URL, but most browsers will turn it into a legal one before issuing a GET request. Thanks, Roman. P.S. Or am I missing some kind of a joke here? ;-)
Re: [9fans] Some arithmetic [was: Re: Sources Gone?]
http://www.google.com/search?q=09+f9; is that a legal url? P.S. Or am I missing some kind of a joke here? ;-) Intentional or not, it's a very good joke. Micah
Re: [9fans] Some arithmetic [was: Re: Sources Gone?]
On Thu, 2009-02-05 at 10:22 -0800, Micah Stetson wrote: http://www.google.com/search?q=09+f9; is that a legal url? P.S. Or am I missing some kind of a joke here? ;-) Intentional or not, it's a very good joke. but...but...erik always adds that look-i-am-using-plan9-smiley to all of his jokes. i'm so confused... Thanks, Roman.
Re: [9fans] Some arithmetic [was: Re: Sources Gone?]
http://www.google.com/search?q=09+f9; is that a legal url? - erik fortune worthy :D
Re: [9fans] Some arithmetic [was: Re: Sources Gone?]
but...but...erik always adds that look-i-am-using-plan9-smiley to all of his jokes. i'm so confused... i do? i guess ya learn something every day. - erik
[9fans] Some arithmetic [was: Re: Sources Gone?]
On Wed, Feb 04, 2009 at 05:40:01PM +0900, sqweek wrote: On Tue, Feb 3, 2009 at 9:54 PM, erik quanstrom quans...@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; pgpX0q6Q0hjim.pgp Description: PGP signature
Re: [9fans] Some arithmetic [was: Re: Sources Gone?]
On Wed, Feb 04, 2009 at 11:40:51AM -0500, Nathaniel W Filardo wrote: 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 Rats, I got overly happy with exponentiation (should be 2^5, not 2^32). Correcting the error gives 2^156 operations in a year, which is more than sufficient to expect to find a root block. Management would like to apologize for the oversight. --nwf; pgpSFypMb3P06.pgp Description: PGP signature
Re: [9fans] Some arithmetic [was: Re: Sources Gone?]
Assuming SHA-1 is indeed cryptographically secure (which is the assumption made by the venti paper) Well, I read it like it was just sufficiently secure against unintended collisions. It's not intended to encrypt, but to efficiently store data.
