Comment by genewitch
2 days ago
Approximately how long does it take to collide a CRC naively? I'm guessing there's a trick that makes it faster, these days?
It takes my computer on a single core about 7 minutes to find a nonce for an arbitrary files sha256 to prefix the left side with 4 or 5 zeros (like bitcoin difficulty doubling). Obviously the heat death of the universe would occur trying to collide sha256 on a single core, but CRC - Gemini says it depends on the algorithm, but crc 32 should take about an hour to collide, but it didn't specify "any" or "arbitrary" collisions, but mentioned "any" right before that. So if the most probable sentence after "any collision" is a time estimate, with the logic of LLM implies that's the easier case of any collision.
I'm surprised brute force is even needed. As far as I know, CRC has absolutely no intent to be a cryptographically secure one-way function. It is purely used against unintentional corruption of data. With that in light, does it really take an hour to find a collision? Can't you construct one much quicker?
893 byte source file, python can single-threaded do ~1 million crc32 per second. It's about "10%" done with the AI's version which is nonce = 0 while true nonce +=1 crc32 (data+nonce.to_bytes) which i don't buy will actually cover the whole field, so i'll just repurpose my sha256sum bash script to use cksum and run it again - that puts arbitrary bytes, not arbitrary integers as bytes into the file.
nonces tried: 515000000 nonces tried: 516000000 Collision found with nonce: 1327202703
walltime ~12 minutes. So whoever i replied to (sorry my vision is going blurry so i don't want to breadcrumb back) was correct, modern CPUs just blow through this.
you'll note the nonce is > 2^32. Cute.
This is what AI does. This sort of crap is going to make everything feel slower. except now instead of inefficient humans making inefficient code because "hey, just scale" or "my desktop has 32 threads, why do i care about a 50ms hot loop? one of the other 31 threads can pick up slack" - now it's ... this.
i absolutely cannot believe it chose the absolute most naive way to accomplish this monumentally trivial task.
Once saw a writeup where someone figured out how to reverse the crc32 calculation… Absolutely no brute forcing needed!
Oddly, this kind of topic doesn’t get a lot of attention