Print

[VoiceOfReason]

[quote name='adam7288' date='Dec 11 2005, 08:18 AM' post='3106392']

[aaaaa0]

Faking a digital signature just isn't going to happen. I'm going to avoid the math to make the explanation simpler.

Digital signatures work based on two cryptographic concepts called "public key encryption" and "hashing".

Public Key Encryption

The way public key encryption works is you have two keys: one called the private key, and one called the public key. Anything you encrypt with the private key can only be decrypted by the public key, and anything you encrypt with the public key can only be decrypted by the private key.

The details of the math behind why this works aren't really important for this explanation (you can find them on the web all over the place or in VoiceOfReason's excellent post), but suffice it to say a lot of very smart people have been trying to crack the math used in public key encryption for a very long time now, and no one's been able to do so in any practical manner for the key sizes in practical use today.

A common public key encryption algorithm is RSA.

Hashing

A hash function is basically a way to generate a single number that represents the contents of a file. This number is called the hash of the file. If any part of the file is changed, when the changed file is run through the hash function again, the number that is generated will be different (to a very high degree of statistical confidence). Hash functions let you detect changes in a file.

When two files have different contents but end up generating the same hash, that's called a hash collision. The strength of a hash function is the statistical likelihood of a hash collision occuring given any two files.

For example, a very weak and simple hash function is CRC32, which is used by ZIP to check for file corruption. A stronger one that people commonly use is called MD5. Even stronger hashes like SHA are probably used by xbox 360.

Digital Signatures

What a digital signature does is prove two things: that a file has not had any part of it altered since the signature was applied and that the only person that could have signed it is the person posessing the private key. A digital signature is not copy protection, it does not prevent making multiple copies of the file.

In xbox 360, you have a public key which is stored inside the x360, most likely burned directly into the XCPU somehow, which makes the public key very difficult to read out or overwrite. MS has a private key which is kept under strict lock and key in a vault somewhere.

When MS creates a game EXE, they take a hash of the file, and encrypt that hash with their private key and stick it on the end of the file. This is the digital signature.

When the xbox 360 loads the EXE, it loads the digital signature first and decrypts it with its copy of the public key. This results in the original hash of the file that was generated when the file was signed. The fact that the decryption worked means that only the person holding the private key was able to generate that signature.

Then it takes the rest of the file and runs it through the hash function again. If nothing has changed in the EXE since it was signed, then the hash stored in the certificate should match the hash the xbox just calculated. If the two hashes don't match, then the xbox knows you've tampered with the EXE and it will reject it.

So to summarize, the hash proves that the file hasn't changed, and the encryption proves that the only person that could have generated that hash is MS.

To fake a digital signature, you will need to either somehow crack or find MS's private key (very very very difficult), or you have to find a hash collision that happens to contain the modifications you need to get the xbox to run arbitrary code (very very difficult).

Neither of these two possibilities is likely to ever happen within our lifetimes, even if we got every computer in the world to try to do it.

[stinkjones]

I do believe that the preferred method would be monkeys at type writers, not quantum computers... God, Idiots! But what everyone is overlooking is the mod chip developers thirst for cash! If they're willing to break into a warehouse for SDKs, how much do you think you'ld have to give someone to steal the key? Oh, but everything is encrypted and compressed and backed up and protected... Big deal, throw it into the back of the truck and find the spot where the key for that encryption is kept.... Just keep stealing keys to encryptions encrypting keys to encryptions... How long could that take? I don't think M$ would be prepared for a full on assault of their corporate headqurters. So how many lines of defense do you think they have on their physical key? This is the M$ omission we are omitting! Corporate espionage all the way!

Oh and don't forget to take hostages along the way to get some important information, and of course bargaining power!

P.S. Sorry if this is retarded,it's really late and i hae to get up for school in a few hours.

thx

[InterestedHacker]

QUOTE(aaaaa0 @ Dec 12 2005, 09:19 PM)

Neither of these two possibilities is likely to ever happen within our lifetimes, even if we got every computer in the world to try to do it.

Excellent posts on here, hopefully these will put an end to the signature related questions.

So, my question about signatures...  

I have understood the principles for ages now, and I understand why we cannot obtain the private key.  But, and I am sure this has already been thought of...  Is it possible to approach the problem from another angle, say for example, if we get the public key (no easy task) first, then work out how to read the file, extract / check it's hash and sig.  Then, if we find a really really tiny file, and write some code that could try and produce a signature to match what the original was?  I know it's a brute force hack again, but if the file is small enough, wouldn't there be more chance of this type of attack working?

Heres another idea...

What about if we could compare the signatures of two or more files, is there any way we could use the differences between signatures, compared to say CRC32 signature, or some other point if reference?

I suppose the final thing is to just flip the bit that says the signature is OK, within the kernel / TSOP?, or is the signature more involved?  Then again, I bet the kernel is signed

[lordvader129]

QUOTE

I know it's a brute force hack again, but if the file is small enough, wouldn't there be more chance of this type of attack working?

a brute force attack is a brute force attack is a brute force attack, regardless of the size of the files you attempt to sign, or the length of code your executing to test a signature, the sheer size of the numbers you you have to work with is prohibitive for a brute force attack

QUOTE

What about if we could compare the signatures of two or more files, is there any way we could use the differences between signatures, compared to say CRC32 signature, or some other point if reference?

well i think part of the problem here is an original point of reference, we dont have an unsigned xbe/xex that we know is 100% bit by bit identical to a signed xbe/xex save for the signature, without this, we dont even know where we are looking for the signature, im sure theres more too it as well, but its late and im tired, lol

QUOTE

I suppose the final thing is to just flip the bit that says the signature is OK, within the kernel / TSOP?, or is the signature more involved? Then again, I bet the kernel is signed

well thats the entire idea behind the hacked bios for xbox, evox m8 is essentially retail 5838 thats hacked to ignore signatures, media checks, HD locking and other things

the problem with 360 wont be making a hacked bios (once we get a retail kernel to hack up or some source code to build one on) it will be getting it loaded past the hypervisor

QUOTE

I do believe that the preferred method would be monkeys at type writers, not quantum computers... God, Idiots! But what everyone is overlooking is the mod chip developers thirst for cash! If they're willing to break into a warehouse for SDKs, how much do you think you'ld have to give someone to steal the key? Oh, but everything is encrypted and compressed and backed up and protected... Big deal, throw it into the back of the truck and find the spot where the key for that encryption is kept.... Just keep stealing keys to encryptions encrypting keys to encryptions... How long could that take? I don't think M$ would be prepared for a full on assault of their corporate headqurters. So how many lines of defense do you think they have on their physical key? This is the M$ omission we are omitting! Corporate espionage all the way!

Oh and don't forget to take hostages along the way to get some important information, and of course bargaining power!

P.S. Sorry if this is retarded,it's really late and i hae to get up for school in a few hours.

thx

trouble is here that modchip devs have no more interest in seeing the private key released than MS does, if it were released there wouldnt be any need for modchips anymore, just sign your backups and play them, even on Live

custom dash? sure, just sign it and use a signed evox boot cd to FTP it your HD

HD upgrade? no problem, use the signed evox boot CD to copy your eeprom, then lock the HD on a PC and use the now famous signed evox boot cd to set up a signed bios loader or kernel patcher and your signed dashboard

modchip devs would probably go into the business of selling homebrew apps rather than free distribution, which would simply lead to a homebrew piracy scene, lol

[VoiceOfReason]

QUOTE(InterestedHacker @ Dec 13 2005, 12:04 AM)

Is it possible to approach the problem from another angle, say for example, if we get the public key (no easy task) first

It's certainly not trivial, but it isn't that difficult either. The public key is just that, public. No effort needs to be made to hide it.

QUOTE

then work out how to read the file, extract / check it's hash and sig.  Then, if we find a really really tiny file, and write some code that could try and produce a signature to match what the original was?

Nope. Message digest algorithms produce digests of the same length for any message (up to the maximum size the algorithm can handle) so a signature for a 5-byte file will be indistinguishable from the signature of a 5-terabyte file.

QUOTE

I know it's a brute force hack again, but if the file is small enough, wouldn't there be more chance of this type of attack working?

Nope. You can try signing every possible file up to, say, 20 bytes (which would take a very long time; any higher and it becomes as computationally infeasible as brute-forcing RSA) and the chances of a collision are negligible.

QUOTE

What about if we could compare the signatures of two or more files, is there any way we could use the differences between signatures, compared to say CRC32 signature, or some other point if reference?

Nope. Message digest algorithms are designed to be secure against such attacks. Here's an example, from Wikipedia:

SHA1("The quick brown fox jumps over the lazy dog") ==
 "2fd4e1c67a2d28fced849ee1bb76e7391b93eb12"

SHA1("The quick brown fox jumps over the lazy cog") ==
 "de9f2c7fd25e1b3afad3e85a0bd17d9b100db4b3"

Two different strings. Same length. Differ by only one bit. But the digests are completely different. No similarity at all. If you can deduce anything meaningful by comparing those two digests, you're a better man than I.

Now, this is not to say that existing message digest algorithms will never be broken. I believe there's already a practical way of finding collisions for MD5, and SHA-1 will probably be there in the next decade. That's why NIST has announced plans to decertify SHA-1 in favor of the multiple flavors of SHA-2 by 2010. Then we'll be back into huge multiples of the age of the universe territory.

Edit: I'm a bit behind the times. Researchers have devised an algorithm that can generate SHA-1 collisions in about 2^69 operations, which is at the very limit of practicability... with a big cluster of heavy iron. Even so, the would-be cracker has a problem. Just because he can generate (after several hundred CPU-years) a hash collision doesn't mean that the collision will be useful for anything. To put it in the context of the Xbox, it doesn't do you any good to find a file that you can affix an existing signature to if the file consists of gibberish that would cause the console to immediately crash anyway.

[dannym]

I was wondering. How does the RSA key compare to the DES key?

Going back to the SETI like project for the xbox 360 when the DES key was deciphered under the DESCHALL project the were computing seven billion keys per second or 10^9 keys per second.
On one day alone more than 600 trillion, 10^12 keys were searched.
The average time for finding a DES key is approximately 3.5 days.
On peak they had over 78,000 unique IP addresses working on the project.

Hell you can even make a worm, trojan or virus to do the work on people's machines without the knowledge of the machine user. But that would be unethical.

Danny

[Midri]

The thing I never understood about finding primes is, a lot of people (I am sure the people that actully calculate primes know this.) do not relise that all primes end with 1, 3, 7, or 9. That cuts down GREATLY on the numbers you have to calculate on... and primes have an odd liner ness to them, at least the low ones http://img487.images...erprimes0op.png

[s0ftm0d]

Seriously, the only this thread has done lately is really piss me off.  Are people that retarded to not pay attention to VoiceOfReason, or whats the deal.  Every fact he is saying is correct, yet there are 10 year olds out there crying that they will crack it.

This is the problem with American now, dumb fucking kids.

[Keshire]

Quantum Theory can get pretty whacky. Especially when you start observing your results.

One key compnent of building a quantum computer was recently discovered I beleive.

I'd look up the links. But I'm too lazy.

[tayior7]

ive been reading this thread for a while now... and cant exactly understand why so many people are trying to explain "their" method for cracking the private key.  the key was not made to be cracked. and i sure hundreds of people (people smarter than the majority of us) have tryed to crack a 2048 bit key, with absolutely no success. i think that VoiceOfReason does a very good job explaining this.



Face it.  It will not be done. (especialy in the lifetime of this console!).

EDIT:  s0ftm0d, im glad to see im not the only one getting irratated

[lordvader129]

the only possiblity of the key being cracked is by sheer blind luck, IE, the first number tested by your brute force program just happens to be the right one (ill leave it to VoR to post the statistical odds of that happening, lol)

as such, i dont believe brute force hacking should be abandoned entirely, a project similar to SETI@Home could be used to work on it

naturally this shouldnt be relied on, and no one should be surprised if and when nothing comes of it

[s0ftm0d]

Haha, good job lordvader, just from that post we are going to get 5 more pages from kids with their reasons why it will be cracked tomorrow.

[lordvader129]

QUOTE(s0ftm0d @ Dec 14 2005, 12:06 AM)

Haha, good job lordvader, just from that post we are going to get 5 more pages from kids with their reasons why it will be cracked tomorrow.

hmm, maybe i should say it will be cracked tomorrow if i win the lottery the next 5 weeks in a row...hell i probably got a better chance of winning the lottery every week for a year, megamillions and powerball both, lol

maybe ill just close the thread before it gets stupid again, lol