Print

[shakaru]

Well, a night of insomia during heat made me come up with a few ideas that might make cracking this code somewhat possible. Now please remember this is only a theroy and also I am possibly very wront so please point out flaws if you see them.

As some people here know, the xbox uses RSA 2048 for its copy protection in conjunture with a sha-1 sum. The RSA code is a product of two large prime numbers (#1 * #2 = Xbox key)
If you visit http://www.xbox-linu...tboverview.html you will see the giant number sitting there.
Now what I was thinking was this. As long as I can remeber there has been a tittle passed around from university to university about finding the largest prime number and the winner holds the tittle untill the next largest is found. As result, all over the net there is a compleate list of prime numbers floating around. As result I  came up with some ways to cut this list down the drastically cut down time. If we can incorperate theses ideas, will it cut down on the time it would take to crack?

1) The key in the xbox kernal is 617 digest long. Remove all prime numbers from the list that are more than 617 (While multiplying two 616 long prime numbers will cross the thresehold, this is just the safe point)

2) Get someone to make a small program that will omit calculations bassed on the following.
    A) The prime numbers are put into a list.
    #1 is multiplied by a randomly selected number. If the number is greater than 617 digets, the program will move down the list lets say 50 numbers. If the number is still greater, it will move down the list another 50, but if its to less than 617 didgets it will move up 25. If after that it is greater again, if will move down 13. See how it works.
    The program will do this with each prime number on the list.
The next part is for the soft guys.
    C) making a RSA factoring program like The Neo Xbox Project, a client is made but unlike most clients, it works in two ways. The user can select to either have the program do what is described in section B above, or factor the already compleated list. If the chose the first option, the client will download a list of already compleated prime list, and the client will take over from their. Then the list will be uploaded back to a website and be compiled again.
    If the chose the second option, the clien would still download the latest list, but factor the numbers that are still on the list

I know this is alot of work, but I have a dream. I dont care if Gates is at the unvailing of Xbox360 or what ever. I want to hear him weap when all xbox's can enjoy the glory of XBMC without a chip.

So.....what do you think

[DaddyJ]

QUOTE(shakaru)

I want to hear him weap when all xbox's can enjoy the glory of XBMC without a chip.

We're doing this already!    

[cmiz]

yeah....i'm using UXE and nkpatcher10 and XBMC is my default dashboard...

i like the idea of your newton raphson esque approach to the problem, the only thing is that it could be any of the numbers within the given set, so skipping around could potentially miss it and cause the program to run for a veeeeery long time.

also, i'm not sure if you realize just how many numbers there are....theres a lot....and i dunn where we'd get a list of all of the primes we'd need.

[Flame2k]

sounds like a good plan however cmiz has a point with missing the number :S

[shakaru]

@cmiz
The aproach I used to see ways of what numbers could be eliminated was based in simple terms like this.
If Im looking for a number between 1 and 5, I wouldnt need 8.
So if the number we are looking for is > 617 didgets long, there is no need to take number of the list from there.
Also, as to how many prime numbers there are, to date the number is

455042511 (http://www.prime-numbers.org/)

We are only removing from the list numbers that are upwards of the public key value. technically 3*really large number here, could even  be the key, while it is unlikely.
Also the skiping proccess dosent "Skip" anything
It works on a the same princliple of higher/lower. Lets say bob has picked the number 134. His friend July guess the number 84 and bob reply's "higher". On her second guess she choses 158 to which bob says "Lower".
Eventually the number is found.
As I said before, the program I was thinking of starts off with a list of all the prime numbers with a didget count less than 617 (the total number of didgets in the Xbox RSA public key).
The key is A*B=C. We know the C value having it be the public key. So we need to find value A and B.
In the program, it would try to find the value using this method. Vaule A is a random selection made by the machine off the list, while value B is the first number on the list and C beign the RSA code key. The program perfroms A*B=C and if the C value is greater than 617 didgets long, it will stab in the dark a number on the list lower than the one chosen untille it it finds one that A*B<617 didgets. Then it will guess between its that number and the one previous in the fasion of the example of Bob and July above. If then it cant find A*B=C it will remove value A from the list thus making sure that the A value dose not reapear on either the A or B sides of the equaison.
Also by haveing no prime numbers on the list that contain more than 617 didgets, the number of options is dramatically droped. Right now I am trying to find out how many opitions there are in that fasion but my guess are somewhere around 5000000 or 1/8 of the total number of prime numbers known.

Correction. What I was going to say above and forgot is that also there is no known way from even the first 5000000 primes to even work in A*B=C and for the top 1.5 trillian to work as well.

[shakaru]

I just noticed something. What are the odds of two RSA-2048 keys equaling 617 digets? Both the one in the xbox and the one in their crypto challenge are that lenght.

[triggernum5]

I love that show..  Too bad its too intelligent and well made to get signed for more seasons..
Did anybody else recognize Doogie Howser?

[wrayal]

Of course, all these facts are well known! Doesn't stop you trying though . So, rather than just throwing discouragement, I have somthing else that might help.
To be considered "secure", the two factors are generally regarded as having to be within "x" bytes of each other (can't remember the figure off the top of my head). Outside this range, even with 2048 bit keys, brute force starting 2,3,5,7,11.... becomes a semi-viable option. The ideal way to do this is, well, if the key is 617 digits long, assuming it is not a perfect square, they are going to be either side of it's root. It's root is going to be about 308/309 digits long. So, using whatever method you want, find the primes going down from the highest 309 digit prime. Hell, eratosthenes sieve anyone?

Now, ^^ is an "improvement". Go look at mersenne.org - there are far more advanced methods. And trust me, good crackers know far in advance of what we are discussing here, and still 2048 bit RSA is considered uncrackable....short of breaking the discrete log problem, but whatever. Just my bit

Wrayal

[cmiz]

i'm sorry if you guys thought i was trying to discourage this, i certainly think it would be cool if you guys went for it and you have my support/whatever help i can offer. i was just trying to throw out a general warning before you guys started off with a system like that. unless you have a general idea of where the intercept is, bouncing around within a set of numbers can get very risky. i actually wrote something one time to solve for intercepts and sometimes the numbers would just work out where it would get tossed around so much and not hit the right area that it would almost take as long as just cranking it out with the brute force method.

i wouldn't like the idea of a brute force method though, but unless you have some sort of way of guessing what the next number might be, it's hard to dynamically sort it out. i'm sure there's a way to do it, i just can't think of any off the top of my head. good luck on it though, if i think of anything useful i'll certainly tip you guys off.

perhaps it would be best to write out a program first to cut down the pool of primes before even getting into finding products...if wrayal is correct about the difference of bits, that would be a good place to start.

[triggernum5]

When I prove Riemann's hypothethis it'll be easy as pie..  Just kidding, proofs and have a love/hate relationship and we aren't on speaking terms right now..

[luther349]

well sha-1 has been cracked even thow its not puplic yet. so we whont even need to crack the rca. with sha cracked you can hijack a aruldy sighned file and add your own lttle expolite to it. we just have to wait for the sha crack methed to come out to the genral crackers.

[triggernum5]

It hasn't been cracked, a minor weakness in the algorythm was discovered.. Finding a collision still has roughly the same probability of happening as picking the winning atom in the universe..

[bourke]

Small problem - doesn't RSA use keys that are 'probably prime' i.e. it doesn't know they are prime - they are just likely primes?

In that case you may miss the numbers even if you do test every single known prime!

[triggernum5]

Actually, if the number is not prime, it can be reduced to a smaller prime and a multiplier..  Just weakens the key overall..  Thing is, there are alot of numbers out there, and alot of them are prime (absolutely speaking)..  One thing I can guarantee however is that many prime numbers are kept under the same kind of security as the keys that are made from them..

[shakaru]

As we speek I am reciving some assitance from an old professor I had. Apperently most universitys have a record of all prime numbers, yet the list its self is all set to powers and such (not really a math guy my self) so what is happening right now is that we are trying to get the numbers written in plain decimal diget form so that we know where we can cut the list.
Also I was told that the most recent prime number find was in the 7mill diget range. He belives that any prime numbers under 617 digets are around 20 years old and that there has to be somewhere that holds the records.

IMO, the key to cracking this is that all keys = 617 digets. This limits the number of combanations even more greatly.

Here is some other info that maybe usful.

40% of number 1-10 are primes, while only 25% of 1-100 are primes. The total number of primes drops more and more in some sort of curve. See below



Now accroding to http://www.mersenne.org/, there have been two breakthroughs in factoring numbers. While they are still using a distributed attack to factor numbers, new algarythms have droped the time involved from days to hours on certain functions.

What I belive we need is to find someone who has a great deal of programing knowlage and incorperating theses algarthyms (if we can find them) to work in our favor.