Print

[John Hoek]

After thinking about the problems we've found to get a exploitable .xbe's, mostly to run on the newer xboxes, expecially V1.6, i thought about this newsitem form a few months ago.

http://www.rtfm.com/..._08.html#001051

Quote:

The effect of a break in SHA-1
Ed Felten has posted an interesting rumor that someone is going to announce a break in SHA-1 in the near future. Ed writes:

SHA-1 is the most popular cryptographic hashfunction (CHF). A CHF is a mathematical operation which, roughly speaking, takes a pile of data and computes a fixed size "digest" of that data. To be cryptographically sound, a CHF should have two main properties. (1) Given a digest, it must be essentially impossible to figure out what data generated that digest. (2) It must be essentially impossible to find find a "collision", that is, to find two different data values that have the same digest.

......
.....
The finding of a single collision in SHA-1 would not, by itself, cause much trouble, since one arbitrary collision won't do an attacker much good in practice.
....
....
It's definitely true that the ability to find collisions in SHA-1 would be a big deal from a cryptographic perspective, but I'm not sure it would be that big a deal from a security perspective. As Ed points out, there are two properties that a CHF is supposed to have:

1. That it's hard to find a message that generates a given digest (preimage resistance)1
2. That it's hard to find two messages that generate the same digest (collision resistance)

It turns out that the security properties of most protocols depend on property one, not property 2. For instance, in Felten's "cut-and-paste" example, the attacker needs to be able to find a second (plausible-looking) message that generates the same digest value that was originally signed. So, while from a cryptographic perspective, an easy way of finding collisions would be a disaster, the effect on most security systems would be minimal.2

Now, as Felten points out, it does sometimes happen that a partial break leads to a full break, but we're quite a ways away from that. For instance, it's known how to find collisions in MD4 (an older and weaker algorithm) for years, but as far as I know, nobody has demonstrated how to find a preimage for MD4 (though Dobbertin showed how to do it for a reduced version 7 years ago.)

All that said, if we do find a way to generate easy collisions in SHA-1 (and if someone has found even a single collision in this period of time, then it's pretty easy) we would need to start the move to some alternative algorithm pronto, just in case, especially since there's no obvious contender, other than a bunch of the longer SHA-1 variants published by NIST, which are potentially vulnerable to the same kind of attack--assuming, of course, that such an attack exists.

1 In the crypto community, preimage resistance is generally broken down into 1st preimage resistance (it's hard to find a message that generates a given digest) and second preimage resistance (it's hard to find a message that generates the same digest as a given message).

2 There are some systems which rely on collision-resistance, but it turns out to be fairly hard to exploit in those systems as well, as I explain here.
....
...unquote:


Basicly the Xbox programs are builds and signed with a SHA1 encription too.
In practice, you'll need the private key (only MS has those) to sign every .xbe.
But only the header of a .xbe is signed this way if I'm correct.  The data inside an .xbe is signed by a userkey, which calculates an unique HASH for the data inside.

So then, so far....

But i remember in the start of soft-hacking of the xbox, started by the Linux adopters, (i can't find the site and article anymore unfortunate) there was an possible solution to get our own program running by altering an existing MS signed .xbe, so that our own program sits in there (or just an unsigned .xbe's loader), but so that the calculated HASH is the same as the orginal file.

Steps:
Take an known MS signed .xbe to start with..

This basic .xbe must be signed at least,
Load_from_HDD
All_regions
a very new date, possibly at late as possible.

Put own programcode (just a booter for unsigned .xbe programs (or a .xbe in a certain location on HD) is enough) into above program, so that it fits in a (Hash calculations-)data 'blok'.

Then let some program search for correcting databytes; to place in the end of that patched blok. This as long till the calculated HASH is just the same as the original.

After this; we've a MS signed, with correct (and known) HASH, patched executable.xbe.

Advantages:
All current Xboxes can drive unsigned programs with this boot.xbe.

MS can patch the kernal in a Xbox v1.7 for instance; to 'kill' our program; but that is very tricky to do, because the original program.xbe is then also abused, and won't run anymore! (don't forget thet the HASH, MS Signing and date/sise of the file is 100% the same!)

This makes live much easier for us modders.

[John Hoek]

And this is the proof that HASH checking at collision level is even possible by handcalculation!  

Quote:Toledo. It's a bad day for all kinds of hash functions. There was a paper posted on the IACR ePrint site that contains collisions for full MD5, MD4, HAVAL, and full RIPEMD (which was probably the prime competition for SHA-1.) THey assert that finding collisions in MD4 is trivial enough to be done by hand calculation! The method is not described, and I have not verified that the collisions are valid.Unquote:


The .PDF paper can you read at:

http://eprint.iacr.org/2004/199.pdf

[John Hoek]

Orginal breaking newspost i found on Slashdot:

http://slashdot.org/...2&tid=1&tid=218

[PedrosPad]

QUOTE (John Hoek @ Sep 22 2004, 11:01 AM)

THey assert that finding collisions in MD4 is trivial enough to be done by hand calculation! The method is not described.

Interesting post John.  Shame the technique is still undisclosed.  

QUOTE

But i remember in the start of soft-hacking of the xbox, started by the Linux adopters, (i can't find the site and article anymore unfortunate) there was an possible solution to get our own program running by altering an existing MS signed .xbe, so that our own program sits in there (or just an unsigned .xbe's loader), but so that the calculated HASH is the same as the orginal file.

For those interested, I think this is what John is refering to http://www.xbox-linu...tboverview.html (section "1.2. SHA1 hash").

[John Hoek]

That's what i searched for....
Thanks PedroPad.  

Maybe we can combine our efforts into this hacking method.
Once we could have a signed program of our selves; MS
can't do anything against it anymore.  

If we manage, we take it on CNN primetime news!  

[ldots]

It's a nice idea and something the xbox-linux guys have put some effort and thinking into. I'm sure they would love a linux loader that boots from a DVD on an unmodded box - and so would I  

But where should we start when an attack against SHA1 is not yet public, I wouldn't know  
We have to wait and see...

[PedrosPad]

QUOTE (ldots @ Sep 22 2004, 07:17 PM)

I'm sure they would love a linux loader that boots from a DVD on an unmodded box.

Making an XBOX boot disk would have additional challenges, but an HDD XBE would be useful for UDE type stuff.

[John Hoek]

basicly this is the method from xbox-linux quoted:
1.2. SHA1 hash
The second way would be to take an already signed XBE and modify it. Because the signature itself only signs the header, it would be possible to modify the sections in the XBE. For this task we could modify anything except the header itself. So the sections need to have the same size and the sameSHA1 hash as before.

To reach this goal there are these two possibilities:

(a) Create a section that does all we want it to do and search a fitting signed XBE. Then we copy our section to a section in the XBE, where our section should be smaller than the XBE's original section. After that we would have to padd the section till its original size, so that the sha1 hash gets the same as before.

( Find an attack against sha1. There have been attacks against md5 that did the following: You have a message A with a hash md5(A). The attack produced a new message B with md5(=md5(A). Perhaps there is a easy way to modify single bytes so you get the same sha1 hash.

Remember, America's National Security Agency (NSA) designed the SHA1 algorithm. Do you really think that it doesn't have any exploitable loopholes?

Have: sha1 function (provided by Franz Lehner, see CVS: cromwell/sha1.c)

Need: a section that does what we want

Need: a attack against SHA1

Need: (Distibuted) Brute Force programm to pad section till the hash matches

Posibility:

If we have the section and the program, we would need people sharing there CPU load.
unquote:


At my knowledge at this moment only a few Linux adapters are still working on this matter. Unfortunate we see very little progress from them. But the priciple stays.

What should we do?
1) Programming a small .xbe loader is the most easy part.
It has to do the following at least:
- start to enable HDD partition F: and G: (if last one is available)
- then execute the first .xbe into the root.
 this .xbe could be Evox, PBLMetoo, XBMC, Avalaunch etc.
- if clock is not set well after booting up, execute original msdash.xbe to set it again.

This way we can use our_own.xbe as the main loader after kernal boots; or use it like UDE, EEE or other methods. Also MS can update dash.xbe alltimes may possible, but those programs CAN'T detect that there is another custom dash.xbe placed, because everything is the same. sise, hashing, MS signing etc. as the original file....


Let's call this hack now:  BillyGate.s.xbe    


Second:
We must put above programcode into a MS signed program.xbe.
make the same section the same length with random numbers to fill out after the code.


Thirth:
Make a small program that runs on PC (maybe like distributed networking, to get ik sooner done...) and calculate a HASH1 collision.  The needed formulas are above almost full described, but need tuning for sha1.


place correctionbytes into above patched program.
done!


////
We should take our times to read as much about cryptografy and learn, learn, learn. Maybe Rmental can help us out.  He is already a pro in this matters...  

[RiceCake]

You'd have to be one lucky bastard to find holes in that hash check to get what your looking for.

Back when Opx was in production this was talked about with little results.

Dunno though. All I know is you'd need to change the media flags to burn it, and whatever to make the thing boot other XBE's.

[PedrosPad]

QUOTE (John Hoek @ Sep 22 2004, 08:38 PM)

Thirth: Make a small program that runs on PC (maybe like distributed networking, to get ik sooner done...) and calculate a HASH1 collision.  The needed formulas are above almost full described, but need tuning for sha1.

Quote from http://www.mail-arch...m/msg02554.html (talking about cracking SHA0 - which, I assume, is simpler than SHA1).......

QUOTE

The computation was performed on TERA NOVA (a 256 Intel-Itanium2 system developped by BULL SA, installed in the CEA DAM open laboratory TERA TECH). It required approximatively 80 000 CPU hours. The complexity of the attack was about 2^51.

I wouldn't hold ya breath for this one.

[John Hoek]

?
RiceCake. You don't get it right now, he?!  I try to explain more. Even for me it's difficult to understand.....

The problem is NOT the MS signing with the private MS key itself.
We don't have it, and even don't need it with those method.
MS signed only the HEADER info of a program file.  The header describes
which version, date, where from the program may boot from (DVD, HDD etc.), regio(s) and the main user-HASH.  this userhash is needed to decrypt the data inside the program; packed within sections.

We just don't do the known way; patch the header, because then we must resign with the MS key, which we don't have.  
because of this, we need to start with an MS_signed.xbe program, wich includes ALL_Regions and Load_from_HDD at least.  Those are easy to found (MSdash.xbe, xboxonline.xbe for instance, etc.)

The programcode into the sections itself is SHA-1 hashed with the userkey.
The MS key isn't important anymore for this! That's important to understand!
So, when we alter programcode in one of those sections; WITH exactly the same length in bytes as the original part, then we could place it right there instead....

But the biggest problem there is; that those part is checked with SHA-1 userkey.
And because we changed code; the calculated HASH is NOT ok anymore,.... BUT:

It seems that with computing algoritmes the same HASH could be reproduced using OTHER DATA as the ORIGINAL DATA. This is possible, because it's possible to calculate so called collisions. Better to know; The calculated HASH shouldn't even been  100% ok as the original, because not all bits are checked with the protocol!

And those last part is the most important to know and understand!
At this knowledge it's in practice much more easyer to find a collision HASH, which would be Verified as OK by MS kernal.


So i hope this clears the fuss about this a bit  

[John Hoek]

QUOTE (PedrosPad @ Sep 22 2004, 08:56 PM)

Quote from http://www.mail-arch...m/msg02554.html (talking about cracking SHA0 - which, I assume, is simpler than SHA1)....... John Hoek Archived User Jr. Member Posts: 84 Sha1 Hash Cracking Algoritm Another quote I found: Report from Crypto 2004 Here's the summary of events from last night's work-in-progress session at the Crypto conference. [See previous entries for backstory.] (I've reordered the sequence of presentations to simplify the explanation.) Antoine Joux re-announced the collision he had found in SHA-0. One of the Chinese authors (Wang, Feng, Lai, and Yu) reported a family of collisions in MD5 (fixing the previous bug in their analysis), and also reported that their method can efficiently (2^40 hash steps) find a collision in SHA-0. This speaker received a standing ovation, from at least part of the audience, at the end of her talk. Eli Biham announced new results in cryptanalyzing SHA-1, including a collision in a reduced-round version of SHA-1. The full SHA-1 algorithm does 80 rounds of scrambling. At present, Biham and Chen can break versions of SHA-1 that use up to about 40 rounds, and they seem confident that their attacks can be extended to more rounds. This is a significant advance, but it's well short of the dramatic full break that was rumored. Where does this leave us? MD5 is fatally wounded; its use will be phased out. SHA-1 is still alive but the vultures are circling. A gradual transition away from SHA-1 will now start. The first stage will be a debate about alternatives, leading (I hope) to a consensus among practicing cryptographers about what the substitute will be. Topic(s): Security Posted by Edward W. Felten at 09:23 AM | permanent link | Followups (16) 2^40 possibilities to calculateinstead of 2^80.....   Keeps perspective here... RiceCake Archived User Hero Member Posts: 788 Sha1 Hash Cracking Algoritm Yeah I'm not an idiot. Your basically looking to edit the filestructure to have the same SHA1 hash as whats in the header. But to end up with what? A big pile of fucked up code? I'd say the odds of editing the file after finding a SHA1 problem to any actual advantage is 1:10000. Edit: If this hack works you should call it the Rwfw hack, for RiceCake was fucking wrong. I'm that confident this won't work. But if you really wanna go about hacking this a distributed effort is what's required. I can host a site if you really want to attempt this. fghjj Archived User Sr. Member Posts: 288 Sha1 Hash Cracking Algoritm So do I understand correctly, if someone breaks SHA-1 like MD5, it is possible to take a SHA-1 hash and a block of data (with length of one of the sections of the retail .xbe you "use") and have an algorithm calculate what "useless junk" you must fit in the block of data to make them match? Anyway I just wanted to say: goed bezig John Hoek Print Pages: [1] 2 3 4 « previous next » xboxscene.org forums > OG Xbox Forums > No-Modchip Hacks (exploits) > XBE Exploits > Sha1 Hash Cracking Algoritm   SMF 2.0.19 | SMF © 2021, Simple Machines

[John Hoek]

Another quote I found:

Report from Crypto 2004
Here's the summary of events from last night's work-in-progress session at the Crypto conference. [See previous entries for backstory.] (I've reordered the sequence of presentations to simplify the explanation.)

Antoine Joux re-announced the collision he had found in SHA-0.

One of the Chinese authors (Wang, Feng, Lai, and Yu) reported a family of collisions in MD5 (fixing the previous bug in their analysis), and also reported that their method can efficiently (2^40 hash steps) find a collision in SHA-0. This speaker received a standing ovation, from at least part of the audience, at the end of her talk.

Eli Biham announced new results in cryptanalyzing SHA-1, including a collision in a reduced-round version of SHA-1. The full SHA-1 algorithm does 80 rounds of scrambling. At present, Biham and Chen can break versions of SHA-1 that use up to about 40 rounds, and they seem confident that their attacks can be extended to more rounds. This is a significant advance, but it's well short of the dramatic full break that was rumored.

Where does this leave us? MD5 is fatally wounded; its use will be phased out. SHA-1 is still alive but the vultures are circling. A gradual transition away from SHA-1 will now start. The first stage will be a debate about alternatives, leading (I hope) to a consensus among practicing cryptographers about what the substitute will be.

Topic(s): Security
Posted by Edward W. Felten at 09:23 AM | permanent link | Followups (16)


2^40 possibilities to calculateinstead of 2^80.....   Keeps perspective here...

[RiceCake]

Yeah I'm not an idiot.

Your basically looking to edit the filestructure to have the same SHA1 hash as whats in the header.

But to end up with what? A big pile of fucked up code?

I'd say the odds of editing the file after finding a SHA1 problem to any actual advantage is 1:10000.

Edit: If this hack works you should call it the Rwfw hack, for RiceCake was fucking wrong. I'm that confident this won't work.

But if you really wanna go about hacking this a distributed effort is what's required. I can host a site if you really want to attempt this.

[fghjj]

So do I understand correctly, if someone breaks SHA-1 like MD5, it is possible to take a SHA-1 hash and a block of data (with length of one of the sections of the retail .xbe you "use") and have an algorithm calculate what "useless junk" you must fit in the block of data to make them match?

Anyway I just wanted to say: goed bezig John Hoek