[chord] Chord and hardness assumptions

[Derrick Coetzee]

Hi, I was recently reading the Chord paper at http://www.sigcomm.org/sigcomm2001/p12-stoica.pdf and a particular point confused me: section 4.2 claims that a uniform distribution of keys and nodes is justified by the assumption that cryptographic hash functions cannot be inverted; but to break the system, it suffices to find a way of generating keys that hash into a small range of the identifier space. One really straightforward and general way to do this is to generate random keys and discard the ones that don't hash into the desired range. It's also possible that any particular cryptographic hash function may possess a weakness that allows the generation of keys more likely to map into a particular range (for example, an attack that fixes some of the high order bits); but that range would still be large enough that this wouldn't facilitate inversion. So it seems like a stronger assumption is needed than the standard ones. This paper has been around a while now and I'm sure you've gotten this question before - is there another publication discussing this limitation? Thanks for any information.
--
Derrick Coetzee
Microsoft Research Operating Systems Group developer

-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://amsterdam.lcs.mit.edu/pipermail/chord/attachments/20080702/0900e55f/attachment.htm