1
$\begingroup$

I'm trying to implement Floyd's cycle finding algorithm on SHA256 function. I think I understood the method used to find cycles but what bothers me is how to properly feed the repeated hashing function.

Let's say I hash string "abc".
What I will get as a result is : "ba7816bf8f01cfea414140de5dae2223b00361a396177a9cb410ff61f20015ad"

As I understood this is a 256-bit (32-byte) output so it could be chunked as:
ba 78 16 bf 8f 01 cf ea 41 41 40 de 5d ae 22 23 b0 03 61 a3 96 17 7a 9c b4 10 ff 61 f2 00 15 ad where each chunk could be represented as individual character.

So my question is should I feed the next Hash function with the raw result with 32-byte or with the string:
"ba7816bf8f01cfea414140de5dae2223b00361a396177a9cb410ff61f20015ad"
which I suppose has 64-byte.



Additionally, if I were only to check first 4-bytes for the collision, what should be fed to the hashing function in this case?

$\endgroup$
2
$\begingroup$

We usually use raw bytes, because this doesn't require extra step (convert hex to string). But technically speaking any representation will allow you to find a cycle (just a different one).

When talking about shortened-hash cycles, same rules apply: we usually use raw bytes just cut to desired length or we fill rest of hash with zeros, because that requires least steps to complete. But you can use anything that will cut entropy to desired value.

| improve this answer | |
$\endgroup$
1
$\begingroup$

No matter how good your implementation is, it is totally improbable that it will succeed to find a cycle for SHA-256; that is expected to require more than $2^{128}$ hashes. You want to implement Floyd's cycle finding algorithm on SHA-256 reduced somehow; perhaps, to its lower 32 to 80 bits; the later will still require significant work.

Back to the question: you should feed the hash function with the transformation by an injective function $F$ of the fraction of the output of SHA-256 for which you want to find a collision. The simplest and mathematically most natural $F$ is identity, but it is perfectly fine to use another, like: expression as lowercase hexadecimal in ASCII. The choice of $F$ (and its output domain) determines the structure of the colliding inputs to the hash that will be found.

If you want to find a collision in the first 4 bytes of SHA-256, you can use identity and hash the first 4 bytes of the previous hash (which might be messy in languages that manipulate hashes as hexadecimal strings, or/and where hashed strings can not contain the byte with value 0, or/and do not use always-8-bit characters); or hash the first 8 characters of the expression as lowercase hexadecimal in ASCII of the hash. In the former case you'll (most likely) find a partial collision for two 4-byte inputs; in the later case, that will be for two 8-character ASCII strings with each character in 0123456789abcdef; in both cases, their hashes will coincide in their first 4 bytes (first 8 characters of the expression as hexadecimal). The expected/average number of hashes is the same, and with optimized code expected/average execution time is comparable (but time to find a collision for a given starting point vary significantly).

Note: there can be a rare exception where Floyd's cycle finding algorithm gets back at the starting point; this can be turned to a collision rather than a failure by choosing the starting point outside of the output domain of $F$. abc works for collision in the first 4 bytes, and either $F$ discussed above.

By choosing an appropriate $F$, you can decide the nature of the colliding strings. It is for example easy to make them plausible English text: just use an injective function from 4-byte values to plausible English text.

| improve this answer | |
$\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.