Emergency!!!!

Welcome to Crypto. We hope you enjoy your visit.

You're currently viewing our forum as a guest. This means you are limited to certain areas of the board and there are some features you can't use. If you join our community, you'll be able to access member-only sections, and use many member-only features such as customizing your profile, sending personal messages, and voting in polls. Registration is simple, fast, and completely free.

Join our community!

If you're already a member please log in to your account to access all of our features:

Emergency!!!!; CRC32 - need help :(
Topic Started: Feb 16 2006, 01:04 PM (274 Views)
cows	Feb 16 2006, 01:04 PM Post #1
Advanced Member Posts: 91 Group: New Members Member #20 Joined: October 10, 2005	Hi guys - I have recently been involved in a little 'crypto' club thingey where we are given a code to crack and we need to crack them as soon as... I have been given a hash - and believe it to be CRC32 but i can find no piece of software or any help for how to crack it manually. Brute forcing has not helped and a dictionary attack hasn't worked. I am pretty sure that it is not MD-5, 4 or 2 as they didn't find anything while brute forcing. Can anyone help?? Thankyou very much - in advance Cows
	Everything is possible, The impossible just takes longer If we do not know what a particle is doing then it is allowed t do everything possible simultaneously. "Anyone who can contemplate Quantum Mechanics without getting dizzy, didn't understand it."


Donald	Feb 16 2006, 02:12 PM Post #2
Elite member Posts: 454 Group: Trusted Member Member #8 Joined: September 2, 2005	They want you to "crack" a hash? As in just find a collision?



insecure	Feb 16 2006, 04:01 PM Post #3
Elite member Posts: 381 Group: Trusted Member Member #10 Joined: September 9, 2005	Thank goodness you asked that. I was beginning to think I was going nuts. How on earth does one crack a hash? But a collision is another matter. I never actually bothered to read up on CRC-32, but presumably it has a 32-bit output, in which case it shouldn't be too big a deal to find a collision.



Guest	Feb 25 2006, 11:06 AM Post #4
Unregistered	Ok - i understand that it is impossible to crack a hash - and yes it does have a 32 bit output - but how do i go about finding a collision - as i have never tried to do it before. Thanks Cows
Unregistered


cows	Feb 25 2006, 11:06 AM Post #5
Advanced Member Posts: 91 Group: New Members Member #20 Joined: October 10, 2005	Sorry - that was me ^
	Everything is possible, The impossible just takes longer If we do not know what a particle is doing then it is allowed t do everything possible simultaneously. "Anyone who can contemplate Quantum Mechanics without getting dizzy, didn't understand it."


insecure	Feb 25 2006, 11:48 AM Post #6
Elite member Posts: 381 Group: Trusted Member Member #10 Joined: September 9, 2005	If you simply want to find two different bitstreams that lead to the same hash, and you don't care what hash it is, then just generate bitstreams at random, and hash them. Store the results in some kind of associative container (e.g. a binary tree or a - well, a hash table! - or whatever), and check for dups every time you store. Assuming you generate a different bitstream for each test (because obviously the same bitstream will generate the same hash, which is a trivial collision of no interest), the probability of the first two bitstream hashes not colliding is (2^32-1)/2^32, or 0.999999999767, and so the probability of a collision is 0.000000000233. Pretty low. But the probability of getting no collisions in the first three hashes is (2^32-1)(2^32-2)/2^64, or 0.999999999301, so the probability of a collision is 0.000000000699. The probability of no collisions for four randomly-selected bitstream hashes is (2^32-1)(2^32-2)(2^32-3)/2^96, or 0.999999998603, giving the probability of a collision as 0.000000001397. As you can see, the probabilities are low, but climbing faster than you might have expected. This is the so-called "birthday paradox" in action. Two streams: p =0.000000000233 Three streams: p = 0.000000000699 Four streams: p = 0.000000001397 Five streams: p = 0.000000002329 Six streams: p = 0.000000003493 Seven streams: p = 0.000000004890 Eight streams: p = 0.000000006320 Nine streams: p = 0.000000008382 Ten streams: p = 0.000000010478 As you can see, this is nothing like* a straight line! It climbs extremely steeply. In just ten random collisions, we've polished off something like two orders of magnitude! You might reasonably ask how many random bitstreams you must test before finding a collision. Well, that's kinda hard to answer. You know for sure that you'll get a collision after at most 2^32 tests, but you may well get a collision long before that. For example, if you do just 77164 tests, you are 50% likely to find a collision. And if you do 198892 random tests, you can be 99% sure of having found a collision. That may sound like a lot of tests, but 200,000 is a LOT less than 4,000,000,000, right? If, on the other hand, you want to find a collision with a particular hash, that's a harder challenge. The most obvious way is brute-force, but on average you'll have to do 2^31 tests before you find a collision, which isn't pleasant. Whether there are cleverer ways to find a collision depend on the exact nature of the CRC32 hash algorithm, which is something I've never bothered to look up.



1 user reading this topic (1 Guest and 0 Anonymous)


« Previous Topic · General · Next Topic »