Print

[SharkUW]

nope. that's a no-go

You gotta look at everything.
To put it simply, if we could generate a filler sequence to satisfy a checksum then we could already generate checksums.

[VoiceOfReason]

My God! You're a genius!

None of the people who developed and standardized SHA-1 even considered this. When they developed an algorithm for secure message digests, it never even occurred to them that maybe somebody might try to "add a series of numbers" to a message to get it to hash to a desired digest value. What a bunch of morons, huh? I mean, here they were, designing a standard for secure signatures, and they didn't bother making it computationally infeasible to come up with collisions. What were they thinking?

Go ahead and do it. Make your homebrew code, then "add a series of numbers" to make it hash to a desired signature. I'm sure it'll be easy. Then, when you're done, go ahead and break all the security on digitally-signed Internet traffic, and the digital signatures the U.S. government places on critical messages. It's all the same problem. It'll be a piece of cake, I bet.

[Mezmiro]

Well if the checksum algorithm even allows collisions, which I doubt it will allow any if any at all, the number of identical checksums that could be generated from different executables would be very small, very very small, like, really small. It's a thought, but I'm sure the spec of the algorithm to compute the checksums wouldn't allow such convenient collisions to occur.

But you know, if you want to analyze the checksum algorithm and try to scan through it, then by all means. You might find something interesting, but it will take a while.

[MacDennis]

QUOTE(artbj @ Apr 1 2006, 08:20 PM)

What about making an algorithm for calculating the checksum in an executable ( the same way as with RSA)

It isn't a checksum but it's a 2048-bit digital signature. Before you ask, no you can't calculate it. No you can't brute force it.

[Drunkn_Munky]

I've got a better idea, why don't we just make our own Xbox 360?

Or even.. make a DVD drive that reads & writes EXACT copies of Xbox games.

Or... ok, I'm out of sarcastic ideas now. I'll shut up.

[VoiceOfReason]

QUOTE(Mezmiro @ Apr 2 2006, 06:59 PM)

Well if the checksum algorithm even allows collisions, which I doubt it will allow any if any at all

It does; any message digest algorithm ("checksum" is a misnomer here) must allow collisions. This is obvious if you think about it: SHA-1 produces a 160-bit digest, which means there are 2^160 possible different digests.  2^160 is a very very large number, but it's infinitesimal next to the total number of possible messages.

QUOTE

the number of identical checksums that could be generated from different executables would be very small, very very small, like, really small.

Well, actually, it's infinite But that doesn't mean it's easy to find collisions. In fact, it's extremely difficult.

QUOTE

But you know, if you want to analyze the checksum algorithm and try to scan through it, then by all means. You might find something interesting, but it will take a while.

Rather like saying that if I tried, I might find a cure for cancer, but it will take awhile. Hey, there's no harm in trying to find an easy way to generate SHA-1 collisions. But the finest mathematical minds in the world are working on the problem (and thus far have failed); it's unlikely that any of us could add anything to their efforts. But if we did, we'd be a lock for an Abel Prize.

That being said, SHA-1 is vulnerable to attack. The feasibility of finding SHA-1 collisions is much, much higher than that of cracking RSA keys. The U.S. government has decreed that SHA-1 should be phased out in favor of the longer-digest variants collectively known as SHA-2 by the next decade. This doesn't mean that you can expect custom-signed Xbox 360 executables anytime soon; it means that NSA mathematicians expect that enemy governments equipped with powerful supercomputer clusters might be able to break signatures on critical national security documents after investing a mere several hundred thousand processor-years.

If that's not clear, here's an analogy. Suppose you, paranoid that sneak thieves might break into your house and steal your treasured collection of Beanie Babies, exactly replicate the setup they've got at Fort Knox on your home: dogs, armed guards, biometrics, foot-thick titanium steel vault doors, etc. Then the government decides that it'd be safest to upgrade the security at Fort Knox a notch. This doesn't mean that you suddenly need to be paranoid that a two-bit hood with a bobby pin is now a threat to your Beanies. You're probably still fine. And SHA-1 collision generation will probably remain well outside of the reach of the general public until long after we're all playing our Xbox 72000VRs with the cerebral interface.