[issue13703] Hash collision security issue

[Christian Heimes]

Christian Heimes <lists at cheimes.de> added the comment:

Either we are really paranoid (I know that I am *g*) or Perl's and Ruby's randomized hashing function suffer from the issues we are worried about. They don't compensate for hash(''), hash(n * '\0') or hash(shortstring).

Perl 5.12.4 hv.h:

#define PERL_HASH(hash,str,len) \
     STMT_START { \
        register const char * const s_PeRlHaSh_tmp = str; \
        register const unsigned char *s_PeRlHaSh = (const unsigned char *)s_PeRlHaSh_tmp; \
        register I32 i_PeRlHaSh = len; \
        register U32 hash_PeRlHaSh = PERL_HASH_SEED; \
        while (i_PeRlHaSh--) { \
            hash_PeRlHaSh += *s_PeRlHaSh++; \
            hash_PeRlHaSh += (hash_PeRlHaSh << 10); \
            hash_PeRlHaSh ^= (hash_PeRlHaSh >> 6); \
        } \
        hash_PeRlHaSh += (hash_PeRlHaSh << 3); \
        hash_PeRlHaSh ^= (hash_PeRlHaSh >> 11); \
        (hash) = (hash_PeRlHaSh + (hash_PeRlHaSh << 15)); \
    } STMT_END

Ruby 1.8.7-p357 st.c:strhash()

#define CHAR_BIT 8
hash_seed = rb_genrand_int32() # Mersenne Twister

    register unsigned long val = hash_seed;

    while ((c = *string++) != '\0') {
        val = val*997 + c;
        val = (val << 13) | (val >> (sizeof(st_data_t) * CHAR_BIT - 13));
    }

    return val + (val>>5);

I wasn't able to find Java's fix quickly. Anybody else?

----------

_______________________________________
Python tracker <report at bugs.python.org>
<http://bugs.python.org/issue13703>
_______________________________________