0
$\begingroup$

Is it possible to create a program to find the collision of 2 different messages with the same first 32 bits using sha1 hashing? I tried using a while loop, but it ran endlessly as though no match were found. I am doing this in Java. These 2 messages must contain "abc123".

My while logic is adding a number to the end of the string, but it fails.

Below is my sha1 hashing (let's just call it) pseudo-code:

public static String sha1Hashing (String message) {
    String sha1 = "";
    StringBuffer sb = new StringBuffer();
    try {
        MessageDigest mDigest = MessageDigest.getInstance("SHA1");
        byte[] result = mDigest.digest(message.getBytes());

        for (int i = 0; i < result.length; i++) {
            sb.append(Integer.toString((result[i] & 0xff) + 0x100, 16).substring(1));
        }
    } catch(NoSuchAlgorithmException e) {
        e.printStackTrace();
    }
    //return first 32 char
    sha1 = sb.toString().substring(0,32);
    return sha1;
}
$\endgroup$
  • 5
    $\begingroup$ I don't believe that the above hashing function actually returns the first 32 bits of the SHA-1 hash; it looks like it returns more; that'd explain a failure to find a partial collision. This question might be better suited for stackexchange, as it's a question about programming, and not cryptography. $\endgroup$ – poncho Apr 15 '16 at 13:38
  • 2
    $\begingroup$ That code is just completely wrong. You're not altering the message at all, and I don't see you comparing 32 bits either. First decompose your problem and generate multiple methods for each part. Test these separately. Then combine them to to create the code. For instance, the comparison of the 4 bytes can be separated out. So can the generation of the messages and - of course - the creation of the hash. $\endgroup$ – Maarten Bodewes Apr 15 '16 at 13:47
4
$\begingroup$

To find a collision it would be best to perform a birthday attack (as I already commented below the question).

You could use abc123 as prefix and then append a counter (using any encoding), creating the message to hash. Then you'd calculate a hash over the message and take the first 4 bytes. You'd create a map using the 4 byte hash as key (e.g. encoded as hexadecimals) and the message.

Now you simply add these key / value pairs until you find a duplicate key. In that case you print out the current message and the message in the map, and - of course - the hash collision that you found.

Because of the birthday problem you'd expect to find a match in less than a second and minimal memory use.


Proof:

Found match: abc123_owlstead_1255 and abc123_owlstead_59131 -> 992156E0
That took approximately 430 milli seconds 

Note that if you post this as an answer, the word "owlstead" should raise some questions and google will quickly find this answer. So I would not copy paste this answer if I were you.

$\endgroup$
  • $\begingroup$ Is there an efficient way to find a match for the entire hash and not just the first 4 bytes? $\endgroup$ – Cole Feb 25 '17 at 3:41
  • $\begingroup$ Not for a secure, collision resistant hash, but in this case SHA-1 is not a secure hash. I'm not sure if you would call that "efficient" though. $\endgroup$ – Maarten Bodewes Feb 25 '17 at 10:59
  • $\begingroup$ Re last line: I still catch myself correcting some of my old comments due to that owl… ;) $\endgroup$ – e-sushi Feb 25 '17 at 16:11
0
$\begingroup$

It is possible to find 2 strings with the same first 32 bits sha1. For example, the first 32 bits of the sha1 of the hex strings 616263313233bffa0000 and 616263313233e6280100 are both e5c993e0. You can use a birthday attack. substring(0,32) gives you the first 32 bytes. You want the first 32 bits or the first 8 bytes. You should use substring(0,8).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.