Print Page - Why Can't We Get A Digital Signature?

Xbox360 Forums => Xbox 360 Hacking Forums => General Technical Hacking Discussion => Topic started by: CattyKid on December 03, 2005, 04:50:00 PM

Title: Why Can't We Get A Digital Signature?
Post by: CattyKid on December 03, 2005, 04:50:00 PM

There is something I have always wondered. In all our years of Xbox modding, we have never been able to acquire the digital signature. Is this because it is so closely guarded? If we had it, we would be able to pop in, say, a signed burned Linux disk and have it play in a stock Xbox.
So, what I'm asking is, do we have NO inside sources at MS? How many people have access to the digital signature? How exactly does it work (aka, why can't we get it off of a game disk). If we could get this, somehow, would it be a way to mod the 360?

(I realize this might be quite noob-ish, but I've always wondered about signatures)

Title: Why Can't We Get A Digital Signature?
Post by: fingolfin on December 03, 2005, 05:09:00 PM

there is currently a $100,00 dollar prize for the group that cracks the xbox main security code
http://news.zdnet.co...,2128739,00.htm
it's " funded by Michael Robertson, chief executive of Linux software company Lindows."

It would be amazing to just pop-in a linux disk and use your xbox or 360 as a PC...

Title: Why Can't We Get A Digital Signature?
Post by: lordvader129 on December 03, 2005, 06:47:00 PM

my guess is that no one at MS would have direct access to the key, and very very few would have access to a computer that signs the xbes and then put them onto a disk to be sent back to printers

the key is elegantly simple, and nigh impossible to crack

heres the deal, 2 numbers are multiplied together to make this number

20740119327258723760276023509063017138455993606274883526731955113241109007354362374128996096291046353572306742110305456946824862203867115042369878729703475765112280167498189046437794602966168812419423365196979669431929588951126804648743029387833666031765734337165949634731375592471670294246180877815104812674626967450097045005117546657068700545263064105024888769118032059917845867653040419404003684559882509195398630922824050405379620513589699993980205694266973236095772153476388267418476533663512746243310317853861946430053072890502949319703765023792161144942611323629444409600173894963797156859916567288947565058003

find those 2 numbers and you can start signing xbes

this is the key for xbox, not 360, i dont think we know even the public key for 360 yet

Title: Why Can't We Get A Digital Signature?
Post by: ShadowElitePro on December 03, 2005, 06:53:00 PM

Ive wondered this too. Now I know. I just thought no one will get it because its closley guarded.

Title: Why Can't We Get A Digital Signature?
Post by: azninvasion on December 04, 2005, 01:56:00 PM

QUOTE(lordvader129 @ Dec 4 2005, 01:54 AM)

Is that the real number or did you just make that up? I know that modern cryptography is based on the multiplication of two very very large prime numbers. Thats why primes are so important. I think that what is needed is someone to come up with a precise mathematical formula for predicting primes, and then we could really get things done.

I once had some thoughts on how we could find patterns in primes but i'm sure people have already thought of this. It has to do with encoding numbers into different bases, base-1 base-2 base-3 etc.. But instead only using the bases of the primes 2^n 3^n 5^n 7^n etc... Using this and comparing the first few multiples of primes in the different bases perhaps a pattern could be found that would speak for the rest of the primes. Then you would take a guess at the prime numbers by first looking at the length of the signature, picking a prime less than half the length of the signature and multiplying the prime by a length that is roughly half or longer, and comparing that to the answer for example for take a number of 100 bits in length, pick a prime that is less than 50 bits in length and multiply it by a certain prime such that it comes up to 100 bits in length, and you would find your most likely candidates. It would help by reducing the number by half that you need to calculate etc....

I don't know if I made any sense, but if I didn't just ignore what I said.

Title: Why Can't We Get A Digital Signature?
Post by: RadisH on December 04, 2005, 02:13:00 PM

in theory there is a possibility to find that "secure-key"? i think yes, but for find that we need year and year of calculator work.

but is some one make a tool like seti@home to use more pc linked around the world to find the key?
is possible? why not create a develop team to create that program?

Title: Why Can't We Get A Digital Signature?
Post by: crystalgeek on December 04, 2005, 02:24:00 PM

10370059663629361880138011754532

and 2

there we go sorted lol

just pasted into calculator and divided by two althou my machine freaked for bout half hour when i hit paste

Title: Why Can't We Get A Digital Signature?
Post by: CattyKid on December 04, 2005, 04:11:00 PM

Well, thanks, that actually helped me understand it much better. I appreciate it, guys, especially you, lordvader129.

Well, time for an Xbox SetiProject!

Title: Why Can't We Get A Digital Signature?
Post by: 82ross on December 04, 2005, 04:33:00 PM

QUOTE(RadisH @ Dec 4 2005, 09:20 PM)

There was one. It was even ported to the xbox itself so it could try and crack itself. I cant remember what it was called exactly Operation Project X i think.

Title: Why Can't We Get A Digital Signature?
Post by: gjm on December 04, 2005, 04:35:00 PM

I don't know the specifics of how xbox security is implemented but i'm sure it's based on public-key cryptography, running a search on that in google will give you some good stuff to read about to understand why you cant get the private key off a game disk..

It should not be computationally feasible to deduce the private key, given the corresponding public key, that's the idea behind public key cryptography..

And yeah MS must keep their private key very closely guarded otherwise i'm sure somebody would leak it

Title: Why Can't We Get A Digital Signature?
Post by: ugo on December 05, 2005, 01:39:00 AM

It looks like they restarted the project in 2003, but their site is currently down.

http://sourceforge.net/projects/opx/

Title: Why Can't We Get A Digital Signature?
Post by: RadisH on December 05, 2005, 03:05:00 AM

QUOTE

The goal of Operation Project X is to crack the 2048-bit RSA private encryption key MS uses to sign Xbox media, by using distributed computing. This key could be used by Xbox owners to run homebrew code on their machines

wow!

for xbox360 there is same project?
i think with the hype around the xbox360 if someone now open-release that program for x360 here the 99% of xbox-scene users start on his pc that programs!

Title: Why Can't We Get A Digital Signature?
Post by: InterestedHacker on December 05, 2005, 03:16:00 AM

QUOTE(crystalgeek @ Dec 4 2005, 11:31 PM)

10370059663629361880138011754532

and 2

there we go sorted lol

just pasted into calculator and divided by two althou my machine freaked for bout half hour when i hit paste

ROFLMFAO! Wondered how long it would be before someone posted something like that...

Title: Why Can't We Get A Digital Signature?
Post by: crystalgeek on December 05, 2005, 11:07:00 AM

QUOTE(InterestedHacker @ Dec 5 2005, 10:23 AM)

ROFLMFAO! Wondered how long it would be before someone posted something like that...

lol all jokes aside would it not be easier to write a simple script to figure out all the multiples of the public key and then to test them?

heres how i see the program written

N defined as 1
Public key = P
A = Number

divide P by 1 print results to "test.txt"
define A as N+N

"Divide P by A print results to "test.txt" check if whole number.
>If no Delete
>If yes Keep
then Redefine A as A + N"

Repeat all in " " till A = P

in effect dividing the public key up by every number up untill itself and saving the results, checking if it is a whole number to give al the multiples of P in effect all the possibillities of the Private Key right?

and I dont know hpow you would test each of these possibillities

but would that not work to find all the possibillities?

I'm no coder but it seems like it would work to me.....

Title: Why Can't We Get A Digital Signature?
Post by: BluhDeBluh on December 05, 2005, 11:58:00 AM

You're underestimating the sheer amount of numbers involved.

Whatsmore, it's 2 or more primes.

Title: Why Can't We Get A Digital Signature?
Post by: crystalgeek on December 05, 2005, 12:10:00 PM

i know its a lot of numbers lol, but at least it would be a start by giving us all the multiples of the public key right?

Title: Why Can't We Get A Digital Signature?
Post by: crosseye on December 05, 2005, 01:08:00 PM

The problem is that it would take a SETI like program with thousands of computers working all day for like a year or more. I still think you are underestimating the sheer volume of what you are asking. Your computer would crap out and complain of massive headache before it even got close.

Title: Why Can't We Get A Digital Signature?
Post by: VoiceOfReason on December 05, 2005, 01:47:00 PM

QUOTE(crystalgeek)

Dude, you totally need to send that to a mathematical journal and have it published. You'll be famous!

There are exactly two factors of the public key. Good luck finding them. Start your computer running your program, and someday after the stars have grown dim and the universe is crumbling to dust it might complete... but I doubt it.

QUOTE(crosseye)

Actually, you're guilty of underestimation too... by a lot.

This is a 2048-bit key, created by multiplying together two 1024-bit prime numbers. So there are 2^1024 keys to check, or about 10^308. Specificially, that's about a trillion trillion trillion trillion trillion trillion trillion trillion trillion trillion trillion trillion trillion trillion trillion trillion trillion trillion trillion trillion trillion trillion trillion trillion trillion potential keys.

Suppose your computer is able to test a trillion keys in a trillionth of a second. Your program will complete in 10^277 years. If you started it running at the Big Bang, it would be about 0.000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001% complete.

Okay, so computers will get faster. Let's take your computer, capable of checking a trillion keys in a picosecond, and make it not twice as fast, not three times as fast, not ten times as fast, not a thousand times faster, but a trillion times faster. Now your program will complete in only 10^215 years.

So we'll go with the distributed model. We'll make like SETI and get a whole bunch of computers in on the act. Let's give every one of Earth's six billion people a computer and network them all together. No, wait, that's not enough. Let's give every one of Earth's six billion people a million computers and network them all together. Let's assume this network is infinitely fast and every computer can receive and submit work units in no time at all. Now our runtime is merely 10^199 years.

Still no good, we're gonna need to call in the extraterrestrials to help. There's about 100 billion stars in the Milky Way galaxy. Let's assume that every one of them (except our own) has ten Earth-like planets, with similar population as Earth, and give every one of those little green men their own collection of a million computers and add them to our network. Now our runtime is down to a snappy 10^187 years. Of course, that's using only our galaxy. It's unknown how many galaxies are in the Universe, but let's arbitrarily say there are a billion trillion of them and add them all to our network. We'll be done in 10^166 years.

But who's to say there's only one Universe? Maybe there are several parallel Universes, and maybe we can enlist them all. Let's say that for every single proton in our universe, there's another whole Universe out there we can somehow communicate with and get them to devote every one of their resources to cracking the Xbox 360 key. That'll get the runtime down to a very manageable 10^80 years or so... which is only a billion billion billion billion billion billion billion billion billion times longer than the entire age of the Universe.

But you want your SETI-like project to complete in a year. Frankly, I'm at a loss as to how we can reduce it any further.

Someday, the problem of factoring big primes will be solved -- and that day will be a terrible day, because while you may be able to sign your own Xbox code, the security that controls everything will pretty much collapse. But until that day, forget about cracking the key. Brute force won't do it, no matter how enthusiastic you are.

Title: Why Can't We Get A Digital Signature?
Post by: VoiceOfReason on December 05, 2005, 02:25:00 PM

By the way, crystalgeek, I notice you're writing every result to a file... which would take a bit more than 10^600 bytes. Let's say that they manage to get hard drives ultraminiaturized, so you can store a trillion terabytes in a cubic nanometer. Assuming the universe has been expanding at the speed of light since the Big Bang, it now has a radius of about 20 billion light years. If it were packed completely full of these ultraminiaturized hard drives... no stars, no planets, no empty space, just hard drives... you'd have about 10^107 bytes of storage space, which is 1/1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000th of what you'd need.

Title: Why Can't We Get A Digital Signature?
Post by: gjm on December 05, 2005, 02:32:00 PM

However! The first two combinations you try, could just be the right ones..

Title: Why Can't We Get A Digital Signature?
Post by: crystalgeek on December 05, 2005, 02:33:00 PM

ok well i said im no programmer but it would work only taking twenty thousand years no worries

Title: Why Can't We Get A Digital Signature?
Post by: sn4k13s on December 05, 2005, 02:37:00 PM

lol...i was just going to say that it would take too long for all the computers in the world to calc together to solve the problem. but im sure he got the point with your examples. nice job

Title: Why Can't We Get A Digital Signature?
Post by: crystalgeek on December 05, 2005, 03:47:00 PM

well lets add two then and im sure when someone thinks of a better way of factoring prime numbers then the world will be a better place, althou as i said it WOULD work just taking forever by then no one would care anymore lol

Title: Why Can't We Get A Digital Signature?
Post by: ajouvenat on December 05, 2005, 04:02:00 PM

Don't forget to add all the time it would take to actually test each key.

Title: Why Can't We Get A Digital Signature?
Post by: lordvader129 on December 05, 2005, 05:32:00 PM

im having a hell of a time even finding a publishd list of primes to use as potential factors, i can find the 10,000 smallest, but they are all 6 digits or less, too small to be considered here, and the 5000 largest known, all of which are over 1000 digits, too big, i cant seem to find anything in the 100-500 digit range, which what i think we need to be looking at

figuring that, we'd probably have to run 2 processes simultaneously, one to calculate a new prime and one to try to divide it into the key, given that there is no discernable pattern to prime numbers even the first process will take an ungodly amount of time

after some more research i found why i cant find any lists of 100-500 digit primes, the number of primes below a certain valu eis given by a formula, for 4*10^22 the number of primes is 783,964,159,847,056,303,858 (thats the current world record) we need to know all primes to the order or 2*10^600 or so, just giving a simply unfathomable amount of possible factors

also remember an RSA key can be 2 or more primes, so even if you find a factor after all of this there still might be more, youd have to test the primality of the result to see if its actually just 2 primes and not more, if its more youd have to start over at square one (albeit with a smaller number)

and thats just for xbox1, 360 probably has an even bigger RSA key, 4096bit or even larger

Title: Why Can't We Get A Digital Signature?
Post by: CattyKid on December 05, 2005, 09:42:00 PM

Anyoen listen to Coast to Coast AM or have ever heard of Remote Viewing? Supposedly, it is real. You might be able to go to Google and type define:remote viewing.
Why don't we have a psychic remote view the digital signature for us?!

Title: Why Can't We Get A Digital Signature?
Post by: ruli00 on December 05, 2005, 10:01:00 PM

QUOTE(CattyKid @ Dec 5 2005, 11:49 PM)

From What ive read in this thread, it may be the only way.

Title: Why Can't We Get A Digital Signature?
Post by: Derrida on December 06, 2005, 01:18:00 AM

Hey, I'm absolutely in over my depth here, but if one went to MS and got an XBE signed, could it be reverse-engineered into the real thing? I mean, I know it can't be converted directly, but would it reduce factoring time by any significant amount? Or does random seeding foil that completely?

Title: Why Can't We Get A Digital Signature?
Post by: Vegita on December 06, 2005, 08:14:00 AM

QUOTE(Derrida @ Dec 6 2005, 09:25 AM)

It would basically come down to the brute forcing problem the others have already discussed.

Unless we build a quantum computer or something the brute force approach isn't feasible. The mathematics of it are very sound... much more likely there's some human error goofup somewhere that can be exploited... and seeing how the system was RUSHED... i'm sure there will be one... and that's only MS's fault.

Honestly when I read about these overheating issues it makes me think this thing was very rushed... which raises my hopes there is some simple exploit waiting for us.

Title: Why Can't We Get A Digital Signature?
Post by: Safrole on December 06, 2005, 12:33:00 PM

I agree with that. I hold hope that this "hypervisor" is not so hypervigilante. There seems to be a lot of "hype" in the name anyway. But then again I'm like a monkey looking at the space shuttle.

Maybe the M$ signing computer is just sitting in the corner of some room and they have some flunky answering the phone sign apps in their spare time.

"Hello, M$. Yes, yes it is. No he's out to lunch. I'm sorry can you hold on a minute? I'm in the middle of signing Halo3...."

Or maybe somebody at a factory in some third-world country making chips can lend a helping hand. (?)

Title: Why Can't We Get A Digital Signature?
Post by: modthebox.tk on December 06, 2005, 07:04:00 PM

I have a question.

Would they be decimals or real numbers?

with Decimals there are (I think) and infinite number of possibilites. If there are real numbers involved all you need is a couple of mathematicians together at a table for a couple of days; I mean, with real numebrs there are only so many combinations.

and if we don't know, we go with real numbers first than try the obvious decimals (square roots) and stuff like that.

it is hard to crack, but whoever made it be it Bill Gates or somebody else is a human and humans have limits to thinking.

Title: Why Can't We Get A Digital Signature?
Post by: lordvader129 on December 06, 2005, 07:06:00 PM

QUOTE(modthebox.tk @ Dec 6 2005, 08:08 PM)

you mean the factors? they ar eprime numbers (whole numbers) but i dont think you realize the scale of it, a computer cant crack it in a couple of millennia, how can a few people crack it in days? it would take weeks if not months for a few people to come up with and test just 1 possible prime factor

QUOTE

it is hard to crack, but whoever made it be it Bill Gates or somebody else is a human and humans have limits to thinking.

its not so much that its hard to crack, its that it takes a long time to crack due to sheer size of the numbers involved

im thinking of a number between 1 and 20740119327258723760276023509063017138455993606274883526731955113241109007354362
37412899609629104635357230674211030545694682486220386711504236987872970347576511
22801674981890464377946029661688124194233651969796694319295889511268046487430293
87833666031765734337165949634731375592471670294246180877815104812674626967450097
04500511754665706870054526306410502488876911803205991784586765304041940400368455
98825091953986309228240504053796205135896999939802056942669732360957721534763882
67418476533663512746243310317853861946430053072890502949319703765023792161144942
611323629444409600173894963797156859916567288947565058003, can you guess what it is?

Title: Why Can't We Get A Digital Signature?
Post by: lordvader129 on December 06, 2005, 09:09:00 PM

QUOTE

Nah, not really. Here you go, the first one's free:

90744758568471273891824362793417296786383470630768325777379673958980107083484583
12920297595915579822647903851739418727374745237510765748925595602805156100237680
00462368525803390238669274724897040728977546396982769628694962048172534622989091
90488374257959082939518841187313558210841447668297015369654192506593

That's a 1,024-bit prime number. Like I said in another post, coming up with primes is easy. Testing whether a given prime number divides a given composite number is also easy. It's the sheer number of possible candidates that makes it hard.

but did you come up with that on your own or with a a computer? lol remember modthebox wants a couple guys sitting at a table to crack this, lol

Title: Why Can't We Get A Digital Signature?
Post by: joshf on December 06, 2005, 11:29:00 PM

QUOTE(VoiceOfReason @ Dec 7 2005, 04:07 AM)

In the first place, there is an infinite number of rationals (decimals, to you.) There is also an infinite number of reals. But the number of reals is actually greater than the number of rationals. (See: Cantor's diagonalization proof.)

Okay, I just looked up Cantor's diag proof, and YOU HAVE IT BACKWARDS!!!

quote from Cantor:
...the infinity of decimal numbers is greater than the infinity of counting numbers...

Title: Why Can't We Get A Digital Signature?
Post by: VoiceOfReason on December 07, 2005, 09:47:00 AM

QUOTE(joshf @ Dec 6 2005, 10:36 PM)

Okay, I just looked up Cantor's diag proof, and YOU HAVE IT BACKWARDS!!!

Do not.

QUOTE

quote from Cantor:
...the infinity of decimal numbers is greater than the infinity of counting numbers...

That's not a quote from Cantor, it's a quote from a page about Cantor. When it says decimal numbers, it means real numbers. Few if any mathematicians would call the reals decimals (they're symbolized by a block boldface R for crying out loud.) Since modthebox.tk talked about decimals as being different from reals, I assumed that me was talking about the rationals.

"Counting numbers" means the natural numbers; the integers from 1 on up. The number of natural numbers is equal to the number of rational numbers, that is, numbers that can be expressed as a ratio... everything except for the nonrepeating transcendental numbers, like pi.

Modthebox.tk said that there were more "decimals" than reals. Whatever he meant by "decimals", he's wrong. The set of reals has the largest cardinality of any set of numbers.

Title: Why Can't We Get A Digital Signature?
Post by: lordvader129 on December 07, 2005, 09:52:00 AM

QUOTE(joshf @ Dec 7 2005, 12:36 AM)

Okay, I just looked up Cantor's diag proof, and YOU HAVE IT BACKWARDS!!!

quote from Cantor:
...the infinity of decimal numbers is greater than the infinity of counting numbers...

hes talking about reals vs rationals, your talking about decimals vs counting numbers, theres a difference

although i guess then shouldnt have used cantors proof as an argument, lol

Title: Why Can't We Get A Digital Signature?
Post by: fluffhead on December 08, 2005, 02:35:00 PM

ok let me backup for just a minute.

I've also always had a lot of questions about how signing works. the response in this thread is basically, well if you know the two magic numbers that when multipled equals this number than you can sign software.... but how does this work??? where did you get that big number??? is that number pulled from xbox disks, or xbox executable file or what??
why do I need to know the original 2 prime numbers?? why cant I just write that big number to the disk?? If i make a bit for bit copy of an xbox disk, why doesn't the signature get copied along with it??

sorry for being a newb when it comes to encryption, but i just need a more satisfying explanation.

Title: Why Can't We Get A Digital Signature?
Post by: lordvader129 on December 08, 2005, 02:45:00 PM

QUOTE

but how does this work???

http://www.muppetlab.../txt/rsa.html#0

QUOTE

where did you get that big number???

i believe it was extracted from the kernel of the xbox

QUOTE

why do I need to know the original 2 prime numbers??

see link above

QUOTE

why cant I just write that big number to the disk??

because the big number is the public key, the xbes (discs) need to be signed with the private key (the orginal primes)

QUOTE

If i make a bit for bit copy of an xbox disk, why doesn't the signature get copied along with it??

well first off you cant make a bit by bit copy of any dvd, the dvd spec prevents this

however, the signature DOES stay on the xbe of a backup, however that is not the only level of security, there is also a media check which prevents the xbe from running off anything but a retail pressed dvd-rom

if you patch the media check the signature is invalid the xbe wont run then either

the idea is if we had the private key we could patch the media check, then re-sign the patched xbe

Title: Why Can't We Get A Digital Signature?
Post by: s0ftm0d on December 08, 2005, 07:53:00 PM

I just don't understand why all this talk about the signature has came up. For the majority of people, the only reason they want the sig is to sign their pirated games, since the 360 isn't modded.

Just give it a rest, and give this thing some time, also stop worring about cracking the damn keys, IT'S NOT GOING TO HAPPEN

Title: Why Can't We Get A Digital Signature?
Post by: CattyKid on December 08, 2005, 08:00:00 PM

QUOTE(lordvader129 @ Dec 6 2005, 11:16 PM)

but did you come up with that on your own or with a a computer? lol remember modthebox wants a couple guys sitting at a table to crack this, lol

Yes, but they have laptops with Inyel Celeron Technology!

Title: Why Can't We Get A Digital Signature?
Post by: Mad_Gouki on December 11, 2005, 01:13:00 AM

QUOTE

its not so much that its hard to crack, its that it takes a long time to crack due to sheer size of the numbers involved

im thinking of a number between 1 and 20740119327258723760276023509063017138455993606274883526731955113241109007354362

37412899609629104635357230674211030545694682486220386711504236987872970347576511

22801674981890464377946029661688124194233651969796694319295889511268046487430293

87833666031765734337165949634731375592471670294246180877815104812674626967450097

04500511754665706870054526306410502488876911803205991784586765304041940400368455

98825091953986309228240504053796205135896999939802056942669732360957721534763882

67418476533663512746243310317853861946430053072890502949319703765023792161144942

611323629444409600173894963797156859916567288947565058003, can you guess what it is?

really, you only have to find one number that has the same number of digits that the square root of the public key has.

go ahead, test it out if you want. there is no simple way to crack rsa encryption but there are a lot of things that could help you, and more than likely if you found the number of digits that one of the keys has to be, just search a dvd for all the numbers that have that many digits.

im thinking that the key would be at a very early part in the dvd, if somebody looked at the lens in the dvd drive as the xbox read a non-xbox game it might shed some light as to where to look for those 2 keys.

you guys are grossly overestimating how many numbers you would need to check, you can create a seive to find just primes first, so you arent checking numbers that would result in false positives, and you can easily find the number of digits you need, i dont know how much that removes from all of the equations but i know it decreases the time to calculate a key dramatically.

like i said, you only need 1 of them. its pretty unrealistic to try but if anyone wants to just say so

i wouldnt approach it witha brute force approach, there are a few tricks you can do with math to find the approximate location of the key but still you need a big calculating program.

Title: Why Can't We Get A Digital Signature?
Post by: unspoiledpuma on December 11, 2005, 09:49:00 AM

QUOTE(adam7288 @ Dec 11 2005, 05:18 PM)

Voice of Reason - If we had quantum computing available, how long would it take?

probably a few month

The encryption is awsome!

Title: Why Can't We Get A Digital Signature?
Post by: CMB on December 11, 2005, 12:21:00 PM

QUOTE(Drunkn_Munky @ Dec 11 2005, 09:42 AM)

What we really need is a super computer like in Digital Fortress. I have $500, anyone else want to chip in?

If the Xbox checks that the 2 numbers on the DVD multiply to make that big long number, why not use that big long number and 1 as the keys?

lol, i highly doubt that would ever work as everyone was saying before. But that would be funny if we just did that. And anyways we need 2 prime numbers and if i remember correctly 1 is neither prime nor composite.

Title: Why Can't We Get A Digital Signature?
Post by: TheRandomDude on December 12, 2005, 12:46:00 AM

Alright, the only thing that confuses me now is about signing. What I believed was that the private key was built into the code using an algorithim. If this is true, and you have enough code, doesn't that make it possible to crack the private key by narrowing down what the 2 primes could possibly be? I keep on hearing about random bits of data to confuse that sort of thing, but wouldn't that wreck the signing altogeather?

Title: Why Can't We Get A Digital Signature?
Post by: VoiceOfReason on December 12, 2005, 11:35:00 AM

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

Title: Why Can't We Get A Digital Signature?
Post by: VoiceOfReason on December 12, 2005, 11:35:00 AM

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

Title: Why Can't We Get A Digital Signature?
Post by: aaaaa0 on December 12, 2005, 12:12:00 PM

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.

Title: Why Can't We Get A Digital Signature?
Post by: stinkjones on December 12, 2005, 11:57:00 PM

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

Title: Why Can't We Get A Digital Signature?
Post by: InterestedHacker on December 13, 2005, 12:57:00 AM

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

Title: Why Can't We Get A Digital Signature?
Post by: lordvader129 on December 13, 2005, 01:21:00 AM

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

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

Title: Why Can't We Get A Digital Signature?
Post by: VoiceOfReason on December 13, 2005, 08:28:00 AM

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

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.

Title: Why Can't We Get A Digital Signature?
Post by: dannym on December 13, 2005, 02:33:00 PM

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

Title: Why Can't We Get A Digital Signature?
Post by: Midri on December 13, 2005, 03:16:00 PM

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

Title: Why Can't We Get A Digital Signature?
Post by: s0ftm0d on December 13, 2005, 10:45:00 PM

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.

Title: Why Can't We Get A Digital Signature?
Post by: Keshire on December 13, 2005, 10:47:00 PM

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.

Title: Why Can't We Get A Digital Signature?
Post by: tayior7 on December 13, 2005, 10:47:00 PM

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

Title: Why Can't We Get A Digital Signature?
Post by: lordvader129 on December 13, 2005, 10:54:00 PM

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

Title: Why Can't We Get A Digital Signature?
Post by: s0ftm0d on December 13, 2005, 10:59:00 PM

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.

Title: Why Can't We Get A Digital Signature?
Post by: lordvader129 on December 13, 2005, 11:26:00 PM

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

xboxscene.org forums

Xbox360 Forums => Xbox 360 Hacking Forums => General Technical Hacking Discussion => Topic started by: CattyKid on December 03, 2005, 04:50:00 PM