Re: [GNUnet-developers] addHostWithSKEY fux0red?

[Christian Grothoff]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Hi Igor.

Yes, you're definitely right, the code was a mess. I've cleaned it up in CVS 
(which should hopefully reduce this problem). Let me briefly sketch how it is 
supposed (!) to work.

Every node has a connection table (128 slots). Every host-identity is hashed 
into the table to find the slot that gnunetd would use to store the 
connection information. If two nodes hash into the same slot in the table, 
gnunetd can never connect to both nodes simultaneously. And yes, this means 
we may start rejecting connections even if we're connected to less than 128 
nodes. But it makes the lookups in that table much, much faster -- and 
assuming there are lots of nodes available, the table will fill up eventually 
anyway.

There are 3 ways a node may start to establish a connection. 
a) the node has an empty slot (timed out, never used, etc.) and knows another
    node that would fit (hash-wise) in that slot. Then the node sends out an
    SKEY message and thereby initiates the 3-way handshake. This is done
    in connection.c::scanForHosts(slot-number).
b) the node receives an SKEY. Note that in this case, we MUST first check that
    the slot is not already busy with a *different* node. If it is, we have to 
    reject the key exchange. The reason is, that an adversary could otherwise 
    have an easy way to ensure that a node is only connect to nodes that the
    adversary controlls (by sending SKEY messages that correspond to all
    slots). So if there is an active connection, addHostWithSKEY must
    *drop* the key on the floor. Since 'addHost' checks if there is a life
    connection, we now tell it not to 'force' replacing an active connection
    with the new one.
c) some code invokes 'connection.c::unicast' to send a message to a specific
    node and -- unlucky as we may be -- we aren't connected anymore. In this
    case, we may *want* to drop a life connection in favor of that connection
    (note that this is of course a security problem (see b), it must be hard
    for an adversary to trick us into calling unicast on a node that we're not
    connected to; I'm aware that in the current code it may not be hard
    enough). Anyway, if we're sure that we really want to drop pre-exisiting
    connections on that slot, use 'force == YES' in the call to 'addHost'.

The whole thing is complicated by the fact that two nodes may *simultaneously* 
decide to initiate a key exchange. The question here is, which key to use and 
which request to drop. This is resolved by adding a timestamp to both keys 
and dropping the earlier key. Note that Igor is right that we may have 
compared apples with oranges (a timestamp from connection with node A 
(previous connection) with a timestamp from a connection with node B (new 
connection)), so 'shutdownConnection' now re-sets the timestamp to 0, which 
should do the trick.

Christian

On Wednesday 07 August 2002 02:41 pm, Igor Wronsky wrote:
> Hello all. I kept receiving
>
> WARNING: key exchange failed: addHostWithSKEY returned SYSERR
>
> announcements. This is because keeping CONNECTION_buffer_ as e.g.
> 64 slots doesn't guarantee 64 hosts at this point, because not
> even the 10 or so current hostids distribute evenly in the used
> hostid->slotid hashing scheme. There is collisions. :( The main
> problem with this is the warnings that confuse the user without
> any hint what might be wrong or what could be done. Technically,
> one option would be to keep overflow lists and keep track
> with variables that the amount of connections is not exceeded.
>
> Note that in the long run this is not a problem, because if/when
> the global host amount exceeds the buffer size, it will
> eventually begin to be possible to get all slots filled.
>
> Actually, the problem is something else. While
> examining this and looking at sessionkey.c/addHostWithSKEY(),
> I couldn't help but wonder at its operation (look
> at the code while reading this):
>
> suppose lookforhost(hostId) returns NULL. This
> means addHost(hostId) will be called. This cannot fail.
> The next if(be == NULL) will never evaluate as true.
> Also, the !hostIdentityEquals() check later on is
> redundant because both addHost and lookForHost keep
> sure of this. This means only "be->created > created"
> will matter. Now, this is the phase that causes the
> warning mentioned above. This is a bit odd, because
> be->created is related to the old host, because "be"
> was *only partly* written over by addHost(). Why
> compare "created" of two different hosts? Besides,
> now returning at this phase with SYSERR leaves the "be"
> record partly rewritten by the new host! Isn't
> the entry now inconsistent?
>
> Another question is, why we allow addHost to overwrite
> the old host at all? Suppose lookForHost failed because
> the host in the slot didn't have same identity, not
> because the slot was empty. The old host in that slot
> might be perfectly fine. Why are we overwriting it? Won't
> the overwritten old host now rewrite this host once
> it sends an SKEY? how harmful this oscillation is?
>
> I might be wrong, but my nose sends me signals of anomalies.
>
>
> Igor
>
>
>
>
>
>
> _______________________________________________
> GNUnet-developers mailing list
> address@hidden
> http://mail.gnu.org/mailman/listinfo/gnunet-developers
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.0.6 (GNU/Linux)
Comment: For info see http://www.gnupg.org

iD8DBQE9UwbM9tNtMeXQLkIRAuCMAJ9bRFtZm6EH/nJNgex4J4vKkVmAywCdFkN2
JJELIbNyeXA0oD52GrvgURQ=
=e4Rn
-----END PGP SIGNATURE-----