BootMii as boot2 on new Wii's

That is not the issue. The key that we lack is the signature master key.

We can encrypt data, basically, we can do everything except generate valid signatures.

Ok answer me these simple questions. Is there ANYWAY, to out of sheer luck get the key? If yes, is anyone even trying? If no, why not, what do they need to try?

Elmoreas

Yes there is, no they aren't (at least, not publicly) and they'd need a random bruteforcer i.e. a program which randomly tries all possible keys until it gets the right one. I think most people with a little programming knowledge/skill would say this is fairly easy to make, just the chances of actually getting the key that way are so slim there's not thought to be much point in bothering I think. Anyway, I don't have anywhere near the programming knowledge required to do such a thing (most advanced program I ever made calculated percentages of numbers and was about 20 lines long), or I would attempt it.

Here's how a theoretical fully-automatic bruteforcer for the Wii RSA private key works.

Step 1. Randomly generate a key.
(Recommended Step 1.5. Make sure that key hasn't been used before.)
Step 2. Encrypt some test material with that key.
Step 3. Try to decrypt that encrypted test material with the known Wii RSA public key.
Step 4. Did the process work? If not, skip to step 6.
Step 5. Is the encrypted test material, when decrypted, identical to the original test material? If so, the key has been found. Stop searching and report the discovery. If not, continue to step 6.
Step 6. The current key is not the key we are looking for. Go back to step 1.

EDIT: Just a bit of dreaming here: with a quantum computer, the source RSA primes for the keys could be recovered in, at most, 617 steps with Shor's algorithm. If we had a capable quantum computer that could go through "steps" at a rate of one per second (Editor's note: one will not exist before the Wii is very outdated, at the least), we'd have the key in less than 15 minutes.



Edited 1 time(s). Last edit at 01/23/2010 10:59PM by WikiFSX.

Quote
WikiFSX
Here's how a theoretical fully-automatic bruteforcer for the Wii RSA private key works.

Step 1. Randomly generate a key.
(Recommended Step 1.5. Make sure that key hasn't been used before.)
Step 2. Encrypt some test material with that key.
Step 3. Try to decrypt that encrypted test material with the known Wii RSA public key.
Step 4. Did the process work? If not, skip to step 6.
Step 5. Is the encrypted test material, when decrypted, identical to the original test material? If so, the key has been found. Stop searching and report the discovery. If not, continue to step 6.
Step 6. The current key is not the key we are looking for. Go back to step 1.

EDIT: Just a bit of dreaming here: with a quantum computer, the source RSA primes for the keys could be recovered in, at most, 617 steps with Shor's algorithm. If we had a capable quantum computer that could go through "steps" at a rate of one per second (Editor's note: one will not exist before the Wii is very outdated, at the least), we'd have the key in less than 15 minutes.

Sounds relatively straight forward. About that last bit: With a decent regular computer how long will it take?

A time period longer than the age of the universe.

EDIT: @The bruteforcer comment: Yes, it is.



Edited 1 time(s). Last edit at 01/23/2010 11:45PM by WikiFSX.

Would they not also need a Wii and a PC too? I know that is a stupid question but I was told earlier the Wii had nothing to do with the Privated key so I was wondering what the bruteforcer ran on the PC actually bruteforced the key out of? Thanks.

Elmoreas

Quote
WikiFSX
A time period longer than the age of the universe.

:-)

@elmoreas: The RSA public key is taken from a Wii.

Quote
WikiFSX
EDIT: Just a bit of dreaming here: with a quantum computer, the source RSA primes for the keys could be recovered in, at most, 617 steps with Shor's algorithm. If we had a capable quantum computer that could go through "steps" at a rate of one per second (Editor's note: one will not exist before the Wii is very outdated, at the least), we'd have the key in less than 15 minutes.

I've also tought about quantum computers... However, a bit offtopic here: When (and if) they build one, can nothing be securely encrypted thereafter or will we "just" need a quantum computer to encrypt it?

Quote
profetylen
I've also tought about quantum computers... However, a bit offtopic here: When (and if) they build one, can nothing be securely encrypted thereafter or will we "just" need a quantum computer to encrypt it?

Basically, modern forms of encryption can still work, but quantum computers can crack them in mere minutes or less theoretically. To defeat the quantum computer, you'd have to somehow make the key being attacked (or something else in the security system) delay the quantum computer. If you forced the quantum computer to have to take a whole second to see if it's guess is correct, then you would defeat it. Or you could use a security key a couple thousand terabytes long to defeat the quantum computer ;P



Edited 1 time(s). Last edit at 01/24/2010 03:28PM by Arikado.

Basically, a quantum computer using Shor's algorithm takes a number of steps equal to the number of digits in the source number to get prime factors.

That is, factoring 15 takes 2 steps, factoring 3,274,383,273,209,428,423,092,348, if it can be done, takes 25, etc.



Edited 1 time(s). Last edit at 01/24/2010 04:16PM by WikiFSX.

OK. Terabytes? Is it even enough? and it will take forever to check whether your terabyte-number is a prime.

Quote
elmoreas
Would they not also need a Wii and a PC too? I know that is a stupid question but I was told earlier the Wii had nothing to do with the Privated key so I was wondering what the bruteforcer ran on the PC actually bruteforced the key out of? Thanks.

Elmoreas

A Wii is not needed. Anything encrypted with the private key can then be decrypted with the common key, which is widely known. The bruteforcer would just guess the key, sign something with it, then try to decrypt it with the common key and compare to the original. It doesn't "bruteforce the key out" of anything, so to speak, it just keeps guessing till it gets it right or is stopped manually (i.e. closing the program).

Quote
profetylen
OK. Terabytes? Is it even enough? and it will take forever to check whether your terabyte-number is a prime.

With a (theoretical) quantum computer that can operate as fast as a modern computer, no, it is not.

High-speed quantum computing is basically the death of RSA.

Quote
WikiFSX

Quote
profetylen
OK. Terabytes? Is it even enough? and it will take forever to check whether your terabyte-number is a prime.

With a (theoretical) quantum computer that can operate as fast as a modern computer, no, it is not.

High-speed quantum computing is basically the death of RSA.

The death of all encryption not encrypted with a quatum computer too? In the case, kinda the death of safe communication through internet, I mean you can't do safe bank transfers and such stuff?

Well, really, encryption is still safe as long as you can't get either key. If you can get either key in any encryption scheme at that point, both keys would be compromised.

"Death of RSA" is somewhat misleading. RSA would simply become little more effective than, say, AES.



Edited 2 time(s). Last edit at 01/24/2010 06:37PM by WikiFSX.

@WikiFSX: Aha! Thanks for explaining!



Edited 1 time(s). Last edit at 01/24/2010 07:24PM by profetylen.

On new Wiis, you cannot install bootmii as boot2. hackmii is smart and removes the option when it detects newer wiis.

Quote
syncmii
On new Wiis, you cannot install bootmii as boot2. hackmii is smart and removes the option when it detects newer wiis.

I'm pretty sure we all know that.