netdev - Re: ipv4: Simplify ARP hash function.

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite for Android: free password hash cracker in your pocket

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <CAL1RGDWTfchzBSv9rbgfg5DWvqB-Gi-RBpzDPGRUg96fNcf4Bw@mail.gmail.com>
Date:	Fri, 8 Jul 2011 13:44:42 -0700
From:	Roland Dreier <roland@...estorage.com>
To:	David Miller <davem@...emloft.net>
Cc:	johnwheffner@...il.com, mj@....cz, netdev@...r.kernel.org
Subject: Re: ipv4: Simplify ARP hash function.

>> Doesn't seem to matter much -- this is now equivalent to
>>
>>       a = key ^ dev->ifindex
>>        return (a ^ (a >> 8) ^ (a >> 16) ^ (a >> 24))           // (1)
>>             ^ (rnd ^ (rnd >> 8) ^ (rnd >> 16) ^ (rnd >> 24))   // (2)
>>
>> where again the attacker controls (1), and (2) is a constant.

> Right, but how can you attack it?  Show me how you can grow
> a hash chain of arbitrary length by modulating the key in
> a deterministic way.

Well, if two things hash to different buckets with the full hash
function, then they already hashed to different buckets without
the extra randomness.  So why bother with hash_rnd?

The answer is that you have to mix hash_rnd into the hash
in a nonlinear way, so that an attacker can't know if two values
end up in the same bucket or not.

With your hash function, the attacker can just compute the
hash (without hash_rnd) for all the values of key ^ ifindex
and then use all the values that end up in the same bucket.

 - R.
--
To unsubscribe from this list: send the line "unsubscribe netdev" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html