Home > Groovy > Hashcode, Adler, CRC collisions in action!

Hashcode, Adler, CRC collisions in action!

February 17, 2010 Leave a comment Go to comments

If you want to see String’s hashcode, CRC32 or Adler32 colliding (producing same results for different Strings) – run this Groovy script:

import java.util.zip.Adler32
import java.util.zip.CRC32
import java.util.zip.Checksum

def checksum( String s, Class<? extends Checksum> c ) {
    Checksum cs = c.newInstance();
    cs.update( s.getBytes(), 0, s.size())
    cs.getValue()
}

assert checksum( "194.153.241.7", Adler32.class ) == 
       checksum( "64.229.15.206", Adler32.class )
assert checksum( "maxtnt05-489.phlpa.fast.net", CRC32.class ) == 
       checksum( "bzq-218-115-93.red.bezeqint.net", CRC32.class ) 
assert "adsl-67-64-91-128.dsl.austtx.swbell.net".hashCode() == 
       "h98s18a80n47.user.nortelnetworks.com".hashCode()

// A combination of two?

assert checksum( "/ongoing/pie/0.2/?N=D?N=A?N=A?N=A?D=A?S=A?M=A", Adler32.class ) == 
       checksum( "/ongoing/pie/0.2/?N=D?M=A?S=A?D=A?N=A?N=A?N=A", Adler32.class )
assert           "/ongoing/pie/0.2/?N=D?N=A?N=A?N=A?D=A?S=A?M=A".hashCode() == 
                 "/ongoing/pie/0.2/?N=D?M=A?S=A?D=A?N=A?N=A?N=A".hashCode()

Those functions aren’t supposed to generate unique numbers, of course (that’s what we have strong hash functions for).

Just thought I’d like to publish some of those collisions ..

Advertisements
Categories: Groovy Tags: , , , ,
  1. David Turner
    March 15, 2010 at 15:38

    CRC algorithms tend to make poor hashcode algorithms (on strings, at any rate). I did a bit of research recently and discovered that, on a dictionary of English words, CRC-32 produces roughly twice as many collisions as does Dan Bernstein’s djb2 algorithm. A hand-waving explanation for this is that CRCs try to reduce entropy, while hashing algorithms try to maximize entropy. http://www.cse.yorku.ca/~oz/hash.html has some classic algorithms that are well worth keeping in the toolbox.

    • March 15, 2010 at 15:42

      This is very helpful, delicious-ed the link. Thank you!

  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: