[9fans] Venti and the hash / public key in plan9

[9fans] Venti and the hash / public key in plan9

[Lluís Batlle]

Hi... I've been reading the papers about Venti. There is an
explanation about the low probability of the repetition of a hash
string in a normal-sized nowadays hard disk. Anyway I've don't
understood what does Venti do when a hash is found in the stored
blocks, and the contents of the blocks are different (the
low-probability case). I imagine there is some code which does not
give a data-loss... Can someone give a small explanation about that?

And also about public key management in plan9 for (at least) 9p
connections. I've seen in the paper regarding Security that there's
used only Shared-key authentication (p9sk1). Maybe there's something
new in the actual distribution of plan9.

I'd like there to be dates in the plan9 papers... :)

Thanks! (I'm quite new in using plan9/inferno)

Re: [9fans] Venti and the hash / public key in plan9

[Russ Cox]

> Hi...  I've been reading the papers about Venti.  There is an
> explanation about the low probability of the repetition of a hash
> string in a normal-sized nowadays hard disk.  Anyway I've don't
> understood what does Venti do when a hash is found in the stored
> blocks, and the contents of the blocks are different (the
> low-probability case).  I imagine there is some code which does not
> give a data-loss...  Can someone give a small explanation about that?

It responds to the write RPC with an error.

> And also about public key management in plan9 for (at least) 9p
> connections.  I've seen in the paper regarding Security that there's
> used only Shared-key authentication (p9sk1).  Maybe there's something
> new in the actual distribution of plan9.

p9sk1 is only an authentication protocol.  

Some 9P sessions are encrypted using TLS/SSL.
We just match the SHA1 hash of the remote public key against
a local list of okayed hashes.  There is no attempt to 
delve into the whole key hierarchy.  This is discussed
in the Security paper.

Russ

Re: [9fans] Venti and the hash / public key in plan9

[Lluís Batlle]

2006/2/6, Russ Cox <rsc@swtch.com>:
> > Hi...  I've been reading the papers about Venti.  There is an
> > explanation about the low probability of the repetition of a hash
> > string in a normal-sized nowadays hard disk.  Anyway I've don't
> > understood what does Venti do when a hash is found in the stored
> > blocks, and the contents of the blocks are different (the
> > low-probability case).  I imagine there is some code which does not
> > give a data-loss...  Can someone give a small explanation about that?
>
> It responds to the write RPC with an error.
So what should manage that error? The application? Maybe it try a
different write size?
In fact there should be another application layer between 9p and the
RPC for venti, isn't it? (which?)

>
> > And also about public key management in plan9 for (at least) 9p
> > connections.  I've seen in the paper regarding Security that there's
> > used only Shared-key authentication (p9sk1).  Maybe there's something
> > new in the actual distribution of plan9.
>
> p9sk1 is only an authentication protocol.
>
> Some 9P sessions are encrypted using TLS/SSL.
> We just match the SHA1 hash of the remote public key against
> a local list of okayed hashes.  There is no attempt to
> delve into the whole key hierarchy.  This is discussed
> in the Security paper.
Ok, I'll keep on reading it (I didn't finish).
>
> Russ
>
Thanks a lot!

Re: [9fans] Venti and the hash / public key in plan9

["Nils O. Selåsdal"]

Lluís Batlle wrote:
> 2006/2/6, Russ Cox <rsc@swtch.com>:
>>> Hi...  I've been reading the papers about Venti.  There is an
>>> explanation about the low probability of the repetition of a hash
>>> string in a normal-sized nowadays hard disk.  Anyway I've don't
>>> understood what does Venti do when a hash is found in the stored
>>> blocks, and the contents of the blocks are different (the
>>> low-probability case).  I imagine there is some code which does not
>>> give a data-loss...  Can someone give a small explanation about that?
>> It responds to the write RPC with an error.
> So what should manage that error? The application? Maybe it try a
> different write size?
> In fact there should be another application layer between 9p and the
> RPC for venti, isn't it? (which?)
Isn't the probability of such hash collisions "pretty" low ?
(lower than the probability of hardware errors passing through
undetected )

Re: [9fans] Venti and the hash / public key in plan9

[Ronald G Minnich]

Lluís Batlle wrote:
> 2006/2/6, Russ Cox <rsc@swtch.com>:
> 
>>>  Anyway I've don't
>>>understood what does Venti do when a hash is found in the stored
>>>blocks, and the contents of the blocks are different (the
>>>low-probability case).  I imagine there is some code which does not
>>>give a data-loss...  Can someone give a small explanation about that?
>>
>>It responds to the write RPC with an error.
> 
> So what should manage that error? The application? Maybe it try a
> different write size?
> In fact there should be another application layer between 9p and the
> RPC for venti, isn't it? (which?)

Lluis, in a system like this, if two blocks have the same hash, they are 
by definition the same. It therefore makes no sense to say 'what if the 
data is different'. The data is not, from the viewpoint of venti. So a 
write of a block with hash X, when a block of hash X already exists in 
venti, is an error. It's the same data. So you get an error on the write 
RPC.

So your real question is, 'what if a block B' has the same hash as a 
block B? What does venti do?" It returns B, not B', as it should. That's 
the underlying rule. That's one reason you want a long hash, with a good 
design :-)

Now, let's see if I got this right :-)

ron

Re: [9fans] Venti and the hash / public key in plan9

[uriel]

> Lluís Batlle wrote:
>> 2006/2/6, Russ Cox <rsc@swtch.com>:
>>>> Hi...  I've been reading the papers about Venti.  There is an
>>>> explanation about the low probability of the repetition of a hash
>>>> string in a normal-sized nowadays hard disk.  Anyway I've don't
>>>> understood what does Venti do when a hash is found in the stored
>>>> blocks, and the contents of the blocks are different (the
>>>> low-probability case).  I imagine there is some code which does not
>>>> give a data-loss...  Can someone give a small explanation about that?
>>> It responds to the write RPC with an error.
>> So what should manage that error? The application? Maybe it try a
>> different write size?
>> In fact there should be another application layer between 9p and the
>> RPC for venti, isn't it? (which?)
> Isn't the probability of such hash collisions "pretty" low ?
> (lower than the probability of hardware errors passing through
> undetected )

I think I heard someone quote Rob as saying something like: "lower
than the probability that all the atoms in one half of the universe
would get up all at the same time and move to the other side of the
universe"

If someone knows the exact quote please email it to me.

uriel

Re: [9fans] Venti and the hash / public key in plan9

[Ronald G Minnich]

uriel@cat-v.org wrote:

> I think I heard someone quote Rob as saying something like: "lower
> than the probability that all the atoms in one half of the universe
> would get up all at the same time and move to the other side of the
> universe"

right, but lest we lose track, don't forget the importance of the hash 
you pick. You could pick one with considerably higher probability.

Here's one: odd parity.

Of course, calling that a 'hash' is probably not justifiable :-)

ron

p.s. Of course, believers in homeopathy might not believe in Venti, not 
sure.

Re: [9fans] Venti and the hash / public key in plan9

[andrey mirtchovski]

---copy/paste---
> Still, the knowledge that collisions have a probability
> of occuring is slightly unsettling. What are the statistics
> regarding probability of collisions in the venti, anyways?

Extremely low.  It's much more likely the disk will spontaneously
levitate first.

	- Dan C.

---copy/paste---

> A 160-bit hash (assuming "strong" hashing) has a 50% probabilty of
> collisions after 2^80 entries. Google "birthday paradox" for the math.

While you make the 2^80 entries, we'll keep ourselves busy worrying
about something else.

	Sape

---end---

Re: [9fans] Venti and the hash / public key in plan9

[Lluís Batlle]

Haha :) Thanks. I got it.

It's hard for me to not to write code for handling those low-priority
cases. If the probability is such low, I understand. :)

on the other hand... is the block size (write/read block size) fixed
(to 8k?) in Venti?
I feel like I read somewhere in the Venti paper that that block size
is of length chooseable from the application.

(I'm not English native, so I hardly would say that I understand
clearly an explanation in English. :)

2006/2/6, Ronald G Minnich <rminnich@lanl.gov>:
> uriel@cat-v.org wrote:
>
> > I think I heard someone quote Rob as saying something like: "lower
> > than the probability that all the atoms in one half of the universe
> > would get up all at the same time and move to the other side of the
> > universe"
>
> right, but lest we lose track, don't forget the importance of the hash
> you pick. You could pick one with considerably higher probability.
>
> Here's one: odd parity.
>
> Of course, calling that a 'hash' is probably not justifiable :-)
>
> ron
>
> p.s. Of course, believers in homeopathy might not believe in Venti, not
> sure.
>

Re: [9fans] Venti and the hash / public key in plan9

[Russ Cox]

Venti is just a block storage server.
It accepts blocks ranging in size from 0 bytes to 56kB.  
The application can use whatever block size it likes. 
8k is typical.  When I back up file systems I use the 
underlying file system block size.

The current Venti server (in Plan 9) does check when you
write a block, if it hashes to an existing block, that the two
are the same.  My newer Venti server (in Plan 9 from User Space)
does not do this, which is faster.

All this discussion about things more likely than two
random blocks having the same hash is amusing, but
there is a serious point no one has brought up.  
All the math depends on blocks chosen randomly.  An adversary
might actually come up with two blocks with the same
hash, not by random search but by being very clever.

Some researchers in China recently claimed to have 
a program that generate two different blocks with the same
MD5 hash (and I think there is one for SHA1 too, that takes
longer).  I ran the MD5 program for a while on my laptop but
it did not finish.  Maybe I just got unlucky (there is still a
little randomness).  It was supposed to be able to finish
in something like 45 minutes and I ran it overnight.

I don't know whether their approach generates two 
blocks of the same length.  I do know that if they are
trying to match a pre-existing hash they do so by adding
padding in the form of some kind of comment.  For example,
they could start with a PDF that said "Buy 1M shares of X",
change the Buy to Sell, and then insert some comments in
the PDF to make the hash of the new document the same
as the hash of the original document and thus the old
signature would work for the new document.  This is bad
and will be worse as computers get faster, and various 
people are worried about how to switch to SHA256.

I am not worried.  If there is some adversary using
your Venti system, there are simpler attacks they could
use to render it inoperable (like fill it up).  I am happy to
assume that the Venti clients are playing nicely.
If, at some point in the future, it was really a problem,
the types that Venti stores with each block would allow
a Venti server to be "transcoded" into a different hash
function pretty easily.  (Of course, the clients would have
to be informed of the new hashes of their root blocks.)

Russ

Re: [9fans] Venti and the hash / public key in plan9

[Joel Salomon]

On 2/6/06, andrey mirtchovski <mirtchovski@gmail.com> wrote:
> ---copy/paste---
> > Still, the knowledge that collisions have a probability
> > of occuring is slightly unsettling. What are the statistics
> > regarding probability of collisions in the venti, anyways?
>
> Extremely low.  It's much more likely the disk will spontaneously
> levitate first.
>
>         - Dan C.

So, not for use near Infinite Improbability Engines.  That should be
documented somewhere…  ;)

--Joel