non-fake signing for content instalation idea

a simple solution would to get Nintendo's private key! (like the solution is "to kill the Batman")

I remember that in order to get Nintendo's private key, that either Nintendo would give it away (NOT likely), a disgruntled employee would leak it( also not likely, but then we would just have to wait) or we could brute force it (more feasible)

So here is my idea... we have A LOT of people using wiibrew, we could code an app that would try and brute force find Nintendo's private key. If enough of us used the app, we could get it done in much less time. to prevent overlapping, the app could connect to a server and would receive instructions on where to start testing, and after it finishes those, it would connect again to get new instructions. I know I could just let the app run whenever I am not using my Wii... then, in the eventuality that someone finds it, it would send a message with the private key to team twiizers and maybe do a congratulations bit on the person's screen, like in Windows solitaire or something, haha...

besides the few stupid puns, I am serious..this could be quite feasible I think.

I had also contemplated the distributed computing approach; although I think you'd still be talking several years to crack the key, by which time most people will probably be on Wii2 or whatever it will be called

I suppose if we could add it in the background of the HBC ;-) so while you're browsing your apps as well as a full processor version. Get desktops involved too...

Quite feasible. That's why all modern day security is based on RSA, and uses similar-length keys.
[en.wikipedia.org]

Oh, and the PPC Gekko is nowhere near fast enough for brute force like this.
We're talking about brute forcing 2048 or 4098 bits. If you read that article, it says 512bit keys are factorable in a few weeks on common hardware. We're talking about 2048 bits means 2^(2048-512) more possibilities to bruteforce. If you follow Moore's law, which *generally* gives that computers will be twice as fast every 1.5 years, then we'll be able to bruteforce 2048 bit keys just about as fast as those 512bit keys in (1.5)(2048-512) years, or 2304 years.

And, of course: <pepsima1> we'll have quantum computers before then

Short answer: "No."



Edited 1 time(s). Last edit at 01/05/2009 06:10PM by tona.

I was also thinking of integrating it into the HBC, whodares.

2304 years divided by an approximate 2 (because it is very unlikely that the final key we try is the right one) is
1152.

divided by the number of Homebrew users times 2 (if they use their PCs too) =

less than a year probably...

No, no no. what tona said. :-)

We will be able to do it at that speed in 2304 years != It will take 2304 years.
It's closer to 2^2304 years to do it at the current speed. Find a calculator that will tell you that.

Edit: And once again, the Wii is not anywhere near the speed of computers they're talking about for "a few weeks" computation.



Edited 1 time(s). Last edit at 01/05/2009 06:52PM by tona.

Let's assume we can break a 512bit key in about one week. This time will be doubled for each additional bit the key contains since we need to test all possibilities for the first 512bits again when we set the 513th bit to one.
The time it takes to bruteforce a key of arbitrary length n therefore is about 2^(n-512) weeks. We divide this by 52 since a year has about that much weeks. That yields the following results:
>>> 2**(2048-512) / 52
46352162056173703626540703962082963709847947075878633679993750751254949838303
90770517471200206434710891247627463246163053581571113067227548018486515174566
63741387180650312543225150399599554134553239527526420734626461028049597038290
28103598501913614711496454641198089954412949140031104392534503153226651353276
326329023492152751042923299283816347703453612517326802209466989935512138106058
919324487984274240504749862267282807134856266217776946788208788553083448398L
Good luck...



Edited 1 time(s). Last edit at 01/05/2009 07:00PM by svpe.

You could always try the random key approach, and hope you get lucky early on. hehe

I'm sure you could apply some heuristics that would reduce the amount of time slightly. Like, it's probable that the most significant bit is 1. And, since we're dealing with primes, the least significant bit is also going to be 1.
Even if we run through a list of only prime numbers, it's going to take a while.

And as for your distributed search plan, realize that you'd need (number_of_years_svpe_posted) computers doing it for a year to check all of those.

Actually, if you look at the 25C3 event on MD5 collisions, they have a rig of 200 PS3's cracking the MD5 :-)

Quote
whodares
Actually, if you look at the 25C3 event on MD5 collisions, they have a rig of 200 PS3's cracking the MD5 :-)

yeah, I saw that too, I was trying to find the post of that again to link to here.

perhaps I am using the wrong terminology (but I also do not know much about digital security)
isn't brute force checking just randomly trying a bunch of numbers?

How many characters is Nintendo's key? is it only numbers or characters too?

The MD5 collision stuff was only possible due to weaknesses in MD5 itself.



Edited 1 time(s). Last edit at 01/06/2009 12:58AM by comex.

Without meaning to be condescending, please go read a good book on crypto before trying to speculate on breaking cryptosystems. I highly recommend Applied Cryptography, which is surprisingly readable, and pretty cheap to find used: Applied Cryptography on Amazon.com.

If you want to modify data covered by a TMD, you have three choices:

* Discover the 2048-bit private RSA key, which is probably stored in a locked room inside of a Hardware Security Module

* Calculate the 2048-bit private key by some means

* Find a collision (not any collision, but one of 2 or 3 specific collisions) in SHA1

svpe's math isn't quite right -- there are faster attacks than brute-force attacks to calculate the private part of an RSA keypair, given the public key. They involve factoring very large numbers, and the complexity of those algorithms doesn't quite double with each additional bit. Still, it's considered computationally infeasible. see e.g. http://www.rsa.com/rsalabs/node.asp?id=2004

The presentation at 25C3 took advantage of a known weakness in MD5. SHA1 was developed, in part, to avoid that kind of weakness.

Quote
bushing
* Discover the 2048-bit private RSA key, which is probably stored in a locked room inside of a Hardware Security Module

* Calculate the 2048-bit private key by some means

Are the keys hexadecimal (I'm assuming they are)?

This question doesn't make sense - hexadecimal is just a representation of a number in base 16.

2048-bit keys can be represented as:

- 2048 binary digits
- 617 decimal digits
- 512 hexadecimal digits
- 256 ISO8859-1 characters
- An 8x8 RGBA image
- 1/64 seconds of 128kbit/s MP3 audio

(The numbers might be wrong, but hopefully you get the picture - keys are just data, you can represent this data however you like, including in hex...)

For the part with the heuristics: Forget it.

Yes, you are dealing with primes.
Yes, they are big.
No, the private key does not have to be a prime.

In fact the public exponent e is 65537 most of the time and you need a private exponent d so that e*d is congruent to 1 modulo (p-1)*(q-1), where p and q are two large primes. This means d can be as large as (p-1)*(q-1), so forget brute force. Knowing (p-1)*(q-1) is equal to knowing p and q.

Good news: The primes are stored in both the private and the public key.
Bad news: I lied. Only the product of them is stored. To get (p-1)*(q-1) from p*q you need to know p or q.

When dealing with numbers that large there are no “rainbow tables” of primes. I think it is faster to try out a number, if you've guessed one, than to first test if it is prime. In fact you would never really test if it's a prime but test if it's probably a prime a few times.

Long story short: Forget it.

P.S: You can write the keys alphanumeric, hexadecimal or in hieroglyphs. They still will be random bits. And by random i mean random as in radioactive decay, not as in least significant bit of your mouse movement.

Thank you for clearing that up joedj. Im still relatively new to this.

Does anybody know how licensed developers test their games?

I doubt Nintendo would give them the private key, and I would imagine the test platform would still implement the security (in order to prove it meets the security standard). The only way I can think of, is that the development machines have a different "Nintendo" key, and they get that private key (knowing it would be useless to non-development Wii's).

BTW - My MD5 reference was purely about using distributed computing in consoles, and not comparing MD5 to RSA and SHA1.



Edited 1 time(s). Last edit at 01/06/2009 12:01PM by whodares.

Quote
whodares
The only way I can think of, is that the development machines have a different "Nintendo" key, and they get that private key (knowing it would be useless to non-development Wii's).

Yes, this is standard practice when doing development on embedded systems -- you have a "development" keypair vs a "production" keypair. There is a bit in the "Starlet" OTP that specifies which one a Wii will accept, I believe.

Quote

BTW - My MD5 reference was purely about using distributed computing in consoles, and not comparing MD5 to RSA and SHA1.

It was a poor choice of comparison, because MD5 is uniquely vulnerable.

ahh, this is all a very interesting read...

I might get that book you linked, bushing...