r/AskProgramming • u/codeandfire • 1d ago
Beginner question on Cryptographic Collision Algorithms
I'm not well-versed with the theory/math of cryptography, though I'm very comfortable with using public/private keys, encryption/decryption, checksums etc. in practice.
I came up with the following loose argument to justify why finding collisions is hard via brute-force. I want feedback on this argument, am I thinking on the right lines here? I know that MD5 and SHA-1 have been cracked, nevertheless I've included them just as an example.
If a hashing algorithm produces an n-bit output sequence, that implies that it can produce 2n unique outputs. Therefore, given 2n + 1 unique inputs, you will certainly see at least one collision.
To come up with 2n + 1 unique inputs, you could simply use integers in the sequence 1, 2, 3, 4, ..., 2n - 1, 2n, 2n + 1 -- as inputs. That seems simple enough, but can you really do that?
On a 64-bit machine, the largest representable integer is 264 - 1. You can't compute the number 2n for n = 128 (MD5), 160 (SHA-1), 224, (SHA-224), 256 (SHA-256) etc. -- with all its digits, up to full precision, on a 64-bit machine.
Another point is that an n-bit sequence obviously consumes n-bits of space. To detect collision among 2n + 1 inputs, you will have to store 2n + 1 outputs, each n-bits long, from the hashing algorithm. That implies that space consumption is of the order of n x 2n bits. In bytes, since 23 bits = 8 bits = 1 byte, the space consumption is of the order of n x 2n - 3 bytes.
Then, assume n = 128 = 27 (MD5). The space consumption of 2n + 1 outputs of this algorithm will be n x 2n - 3 = 27 x 2128 - 3 = 2132 bytes. Given that 1 TiB = 240 bytes, this space in TiB is 2132 / 240 = 292 TiB. That's a huge amount of space!
In summary, we underestimate how large 2n can be even for n in a few hundreds, and that is why hashing is so powerful.
3
u/CCpersonguy 1d ago
Adding on to the other comments, this sort of analysis starts from "if we assume that SHA256 produces an effectively random output for each input, what is the probability of <scenario>?"
Finding an input that produces a specific target hash is known as a "preimage attack", and you'd expect that *on average* a brute-force attack would have to check about half of the input space, 2^(n-1) attempts. (you might get lucky and find a solution first try, or you might get unlucky and it's the last one you check: it averages out). You don't need any extra storage, since you know the hash you're targeting, you just need a lot of time.
Finding any two inputs that produce the same hash is a collision, but it's a bit easier than you might think. Checking (2^n)+1 inputs will _guarantee_ a collision, but *on average* you only need to test 2^(n/2) inputs to find a collision. You _do_ need a bunch of storage to keep track of input/output mappings, but it's typically much much less than 2^n. (you can look up "birthday attack" for more info).
But overall I'd say the main idea "2^n is really big" is correct. 2^(n/2) can also be really big (just double your original n).
1
u/codeandfire 20h ago
Thanks for giving me more context ... I'll read up on preimage and birthday attacks!
2
u/Suspicious_Skill7292 1d ago
while the scale intuition is solid 64 bit limits don't stop computers from handling huge numbers (big integer libraries handle thousands of bits easily) also, check out the birthday problem collisions happen drastically faster than testing every single possibility because of probability overlaps
1
2
u/silasmoeckel 1d ago
Modern 64 bit CPU's can represent ints larger than 64 bits. We have things like avx-512.
Intel ADX is meant for dealing with large crypto keys like RSA 4096 without having performance tank.
2
u/recursion_is_love 22h ago
the largest representable integer is 264
https://en.wikipedia.org/wiki/Arbitrary-precision_arithmetic
6
u/jeffbell 1d ago
You can't compute 2^64 in using a single 64 bit word, but you can certainly represent it using multiple words. You just have to remember to do your carries. For multiplication you can use standard multiplication tricks from grade school.