Giblit Proposal

Some Guy amichrisde at
Sat Jan 3 18:16:14 UTC 2004

Ok so if we insist on consistency only at the endpoints, then is a chance a tagged(corrupted) cell
can be used by adversaries to see if two nodes are on the same tunnel.

If we have consistency checks every hop, then the cells will shrink going through the circuit
possibly giving away to nodes where they are in a circuit.  This may be fought with lots of
padding of cells to have them shrink more eratically.  That's pain though.

I've got fun proposal.  Let me know if anyone has been down this path already.
-----Dirty checking -----
Let's include on other field in a cell, called a giblit which is encripted as a cell pass along a
circuit independently.

Now if a cell doesn't pass the hard test where it matches a strong hash.  Then it must pass a
dirty test based on the giblit g.

This dirty test might be something like "the first 4 bits of g have to match the first 4 of
hash(rest_of_cell+symetic_key)".  In this case the probablity of passing the test randomly is 2^-4
or 1/16th.

So a tagged message would only have a 1/16th chance to make it another hop before being
identified, and raising alarm bells or at least being dropped.

So how does one calculate g.  Well it's kind of a hash cash problem.  Say your tunnel is 4 nodes
including you.  It doesn't have to pass the dirty test at your node, or the endpoint.  So that
only leaves two nodes where the test has to be done.  So you pick numbers that will pass on the
first node, see what they encript into and if that passes.  So if the test were to match the first
12 bits.  It'd take about 1024 hashes and encripts, which should take way less than a second.

Now if the first node and the last node were evil.  The first node could try to send the last one
junk.  There would only be a 1/1024 chance of that getting there ok compromising the tunnel, but
there'd be a 1023/1024 chance that the next node would notice it was junk and maybe report the
first adversarial node and break the circuit.

It becomes exponentially harder as the tunnel gets longer to generate the giblit.  The good news
is in longer circuits nodes will have more chances to pick up on a bad cell.  It seems to balance
out in the end.

The only thing I'm worried about is an evil user generating cells which fail to pass to get
innocent nodes in trouble.  Maybe this trick should only be used to limit tagging attacks, perhaps
in combination with some cover tag messages.

Yes? No? Maybe?


Gesendet von Yahoo! Mail -
Logos und Klingeltöne fürs Handy bei

More information about the tor-dev mailing list