Scrubbing and Signing an Iso

Discussion in 'Wii - Hacking' started by Arch Feline, Jun 19, 2008.

Jun 19, 2008
  1. Arch Feline
    OP

    Member Arch Feline GBAtemp Regular

    Joined:
    May 7, 2007
    Messages:
    230
    Country:
    United States
    The new update, 3.3, has me terrified. My Wii has no internet connection and I do not expect it to break and need to be sent into a repair facility. I guess I have a dull life and terrify easily.

    I am wondering why the genuine signature process cannot be reverse engineered. Is it considered forgery and the legal repercussions are more threatening than those for piracy? Does the signing process take up more resources than the process to verify a signature?

    Is anyone working of substitute update patches?
     
  2. Shuny

    Member Shuny I'm in yr forum, reading yr postz

    Joined:
    Nov 15, 2006
    Messages:
    1,019
    Location:
    Somewhere in the world
    Country:
    France
    It's more complicated. Search about the RSA private / public key.

    With a public key, you can decrypt the data but not encrypt it. With a private key, you can encrypt AND decrypt the data.

    The problem is that the Wii just contains the public key, not the private.

    Or maybe I'm totally wrong.
     
  3. RyuKakashi

    Member RyuKakashi GBAtemp Fan

    Joined:
    Mar 18, 2006
    Messages:
    450
    Country:
    United States
    If things were so simple, they would have been done a while ago.
    I believe one of the first entries on hackmii.com will explain to you just how complicated this stuff is.
     
  4. Arch Feline
    OP

    Member Arch Feline GBAtemp Regular

    Joined:
    May 7, 2007
    Messages:
    230
    Country:
    United States
    How big is this number N? I am guessing that it is too big to post. Is the number more than a kilobyte long? There might be some way of divvying up the work of factoring it.

    How about someone uploading the number to GBAtemp? If enough people make random attempts to factor it, someone is going to get lucky.

    I suppose we also need a lil program that does arithmetic on long numbers. Another upload?
     
  5. Shuny

    Member Shuny I'm in yr forum, reading yr postz

    Joined:
    Nov 15, 2006
    Messages:
    1,019
    Location:
    Somewhere in the world
    Country:
    France
    What are you talking about ?
     
  6. Jacobeian

    Member Jacobeian GBAtemp Advanced Maniac

    Joined:
    May 15, 2008
    Messages:
    1,879
    Country:
    Cuba
    there is no such things as random or lucky findings, as Shuny said, look about RSA keys on wikipedia/google... you will (eventually) understand why you are thinking wrong and should let people who really know handle this kind of stuff...
     
  7. FAST6191

    Reporter FAST6191 Techromancer

    pip
    Joined:
    Nov 21, 2005
    Messages:
    21,705
    Country:
    United Kingdom
    As I understand it
    Scrubbing: The term whole disc encryption/signing you may have seen when the wii is described is somewhat of a misnomer as the junk (containing nothing of interest) space between useful files is not signed. This is replaced as this unsigned data is in all but a very small handful of cases essentially random uncompressible (by conventional/popular algorithms/techniques anyhow) garbage. In essence scrubbing is just replacing the garbage with very easy to compress 00/FF's (it gets more complex once you add in headers and whatnot but that is the basic principle).
    The key is needed to decrypt the files to figure out what to send to silicon hell and as no signing is broken all should be good still.

    Signing bug aka trucha aka crash course in cryptography:
    When the wii checks(ed?) the disc it compares the signature embedded to the signature of the files. If they match all is good but no match means disc is rejected.
    Signatures are what happens when cryptography meets hashing.
    Now hashing in the most simplistic form is the simple odd or even.
    e.g. I send you a number (46 and tell you it is even), you however get 45 which is odd and obviously not the number I sent you (of course there just as many odd as even or a 50% collision (a collision is where two files have the same hash) rate which is completely useless for just about everything but the idea can be expanded to the sums of numbers (4+6 and beyond).
    Common hashes are bytesums (used in a lot of DS save games), crc and crc 16/32...... (used just about everywhere but possible to fake quite easily so is falling out of use for anything beyond file checking where there is not much chance of someone making a matching file (this actually happened to some GBA roms late in the life of the GBA)), md5 (used in bit torrent and loads of other places) and sha1 (stronger than md5 and also used in several places).
    Sidenote rather than store the actual password for something (which can be easily read off a disc) a computer will usually just store a hash of the password so what you enter merely has to have the same hash as the original password to allow access. Naturally people made lists of all the hashes and passwords that made them (called rainbow tables if you fancy reading up) for the more common/simple hashing algorithms so your password may not be as safe as you think.

    Signatures are just a tweak on encryption to output a "hash" instead of an encrypted file.
    Encryption is usually based on "hard maths". Usually this takes the form of prime numbers (a number that can only be divided by 1 and itself to leave a natural (counting 1,2,3, etc) number) but ellipses are good as well and there are various other methods like random* numbers used like primes (factored together) and XOR (based on the boolean logic principle of XOR).
    The RSA algorithm example is good here for something slightly beyond the truly elementary examples being given out here:
    http://mathcircle.berkeley.edu/BMC3/rsa/node4.html

    *you may have seen the recent Debian linux problem where the numbers generated were not quite random thus could be guessed ( http://www.theregister.co.uk/2008/05/13/debian_openssl_bug/ )

    The simple example would be a "multiply every 4th number (starting with the first) by 2" example
    original message, call it my phone number I do not want anyone but the person I am sending it to having.
    1111,1111,1111
    "encrypted"
    2111,2111,2111

    a hash/signature could be to encrypt and then take every 4th number and send that giving
    2222

    when the person gets my message as
    2111,1111,1111
    and the signature reads
    4222 something is obviously amiss.
    Naturally I have to keep my "times 2" method secret (a concept known as security by obscurity and widely panned by cryptographers) but people could know my every 4th number hash if they liked. The holes in my scheme are blatant (1234,1234,1234 would be the same signature) but you get the idea.

    So nintendo have their signatures (what it is supposed to be and what it is now you have messed around with it).
    You may have read one of the older xbox hacks where MS used a rather bad choice of signature generating algorithm ( http://www.xbox-linux.org/wiki/17_Mistakes...ion_and_Hashing ) which had a problem being used in this way (any encryption can be used to make a signature and any signature making tool can become encryption but as my crude example above shows it is not always a good idea).
    A simple example of a bad encryption is the use of ASCII letters to make a "random" string for encryption purposes, now you count up in binary and you give letters as you go up like you did as a kid with a=1, b=2, c=3 (ASCII codepage: http://www.asciitable.co.uk/ ). Now computers are only (easily) able use 8 bits which means 2^8 or 256 combinations, 127 characters however is more than is really needed for the roman alphabet, arabic numbers and hangers on. This means every eighth bit is guaranteed to be a 0 or in other words I can drop half the possible combinations for a single character (or divide by 2 for every character in the password) which serves to rapidly reduce the amount of time needed to work out the password. You also can take some more as the first 31 are control characters and thus not used.

    That aside Nintendo managed to pick a nice algorithm to use (RSA as Shuny mentioned, again detailed nicely here: http://mathcircle.berkeley.edu/BMC3/rsa/node4.html ) but alas nintendo messed it up and used a strncmp() (tmbinc explained it all in far more detail in a rather nice post on his blog http://debugmo.de/?p=61 ) where they should have used a memcmp() (they actually made a few other mistakes all explained in the link but it boils down to that).
    For those not up to date on their C? ( http://www.cplusplus.com/reference/clibrar...ing/memcmp.html ) the former terminates when it reaches a 00 (which is usually fairly quickly owing to some nice circumstances with the use of RSA) while the latter checks the entire sum.
    This had the effect of terminating the check before it was complete (i.e. only a few bits in).
    Now guessing a signature having used a long private key is very hard but owing to some seriously clever maths you can get a match to the first few bits (you have the key which can check it but not sign it remember) fairly easily on semi powerful modern machine (i.e. yours) and as only the first few bits are needed........

    @Arch Feline a kilobyte is 8 x 1024 bits (or 8 x 1000 if you are a hard drive company). 8 is the number of bits in a byte. 8192 bits is 2^8192 possible combinations (which is a huge number of combinations: there are just under 2^25 seconds in a year so at the rate of say 1 a second you are looking at 2^8167 years). Nintendo did not use something that long as cryptography is apparently munitions ( http://rechten.uvt.nl/koops/cryptolaw/cls2.htm#co ) so it would probably be against the law not to mention complete overkill, furthermore we have the public key which is nowhere near a kilobyte long and reading the RSA link you will see it is the multiple of two numbers which would not make a smaller number.
    Basically read up on exponentials.

    edit: thanks Jacobeian for reminding me where the original explanation was.
     
  8. Jacobeian

    Member Jacobeian GBAtemp Advanced Maniac

    Joined:
    May 15, 2008
    Messages:
    1,879
    Country:
    Cuba
    wow... I think you just manage to explain everything (encryption, signature & hash concepts) in one very nice post, thanks a lot for that !

    about the signature bug, I think it's also quite well described on tmbinc's blog ("Thanks Datel" entry)
     
  9. RyuKakashi

    Member RyuKakashi GBAtemp Fan

    Joined:
    Mar 18, 2006
    Messages:
    450
    Country:
    United States
    FAST6191 for president.
     
  10. Arch Feline
    OP

    Member Arch Feline GBAtemp Regular

    Joined:
    May 7, 2007
    Messages:
    230
    Country:
    United States
    My understanding is that you need to know two primes p and q given the product. The public key given to a Wii has the product of p and q which is what I refer to as N


    Start out with the approximate square root of N. One of the factors has to be less than or equal to the square root.

    I am thinking that reverse engineering this number N is straight forward and I am thinking that providing a program that will help you randomly choose a number between 2 and the square root of N and then divides chosen number into N is straght forward.

    Most calculators are fixed length but it is not difficult to program a routine that will do a divide for arbitrarily long but finite integers.


    I am not talking the impossible when I say luck. If these down loads were provided, there would be many enthusiasts choosing many different candidate primes. No one has to check that the number is a prime. All that needs to be checked is that the chosen number divides cleanly into N.

    You are saying that this has no chance of working. Then you are being ridiculous. Truth depends on the issues not on who is saying it.

    It is not difficult or tedious to provide the number N or the program. It is something to do. I think that many members of the Wii scene have been waiting for this chance to contribute.


    Codes like this can be cracked. For an industrial or military organization it is easier to steal, bribe or sneak the answer so nobody bothers.
     
  11. FAST6191

    Reporter FAST6191 Techromancer

    pip
    Joined:
    Nov 21, 2005
    Messages:
    21,705
    Country:
    United Kingdom
    Edit it looks like I may have messed up below but only as far as it makes it slightly harder to crack. Were I to be correct my maths would be valid however/the maths is valid for the now hypothetical situation I describe. See http://debugmo.de/?p=61 for more.


    ---------------------------------------------------------

    I linked how RSA works but OK, long key RSA has been widely studied by cryptographers for many years and is recognised as one of the best encryption algorithms there is if done properly (and aside from messing up the way it is used to detect things all signs point to it being originally implemented properly).

    The key you refer to as N in your example is 32 nibbles/16 bytes long or 128 bits long. Not as extreme as 8192 mind you but still not very nice.
    Square root: sure it can ballpark a starting point.

    6.5e+38
    root = 2.56x10^19
    Still damn high numbers and given fluctuations in number of bits able to be used for either component either way are possible it is still less than easy.....

    random numbers are statistically no better than conventional add 1 (actually it would be 2 as even numbers are definitely not primes) brute force. You might get lucky sure but we are dealing with scientific random rather than the concept called random used by "the public" (scientific random is probably best defined in chemical entropy so pull out a high school (probably aimed at 16-18 year olds) chemistry book/site and it will be explained there).

    As for industrial/military do you have any idea how hard/expensive it is to get supercomputer time for legitimate reasons?

    And for the distributed option assuming everyone has the same machine (and for the sake of the order of magnitude debate that is good enough) half of a very large number is still a very large number (exponential division means you take from the "power", to divide (and thus drop the time required to the realms of the reasonable) you need to root the equation in some manner). Just for giggles 10000 enthusiasts is only just over 2^13 and getting 10000 people on the case would be a feat in an of itself)

    So possible yes but damn hard and will take a very long amount of time which is what encryption is all about. Of course if a quantum computer were to appear or a decent pattern in primes was to appear all bets are off.
     
  12. Jacobeian

    Member Jacobeian GBAtemp Advanced Maniac

    Joined:
    May 15, 2008
    Messages:
    1,879
    Country:
    Cuba
    and that's why it is more efficient (and realistic) to look for exploit and bugs in the code...

    being realistic is not ridiculous, this has nothing to do with trust ... on the other side, thinking that some script kiddies could broke the RSA IS ridiculous...
     
  13. Arch Feline
    OP

    Member Arch Feline GBAtemp Regular

    Joined:
    May 7, 2007
    Messages:
    230
    Country:
    United States
    My understanding is that you need to know two primes p and q given the product. The public key given to a Wii has the product of p and q which is what I refer to as N


    Start out with the approximate square root of N. One of the factors has to be less than or equal to the square root.

    I am thinking that reverse engineering this number N is straight forward and I am thinking that providing a program that will help you randomly choose a number between 2 and the square root of N and then divides chosen number into N is straght forward.

    Most calculators are fixed length but it is not difficult to program a routine that will do a divide for arbitrarily long but finite integers.


    I am not talking the impossible when I say luck. If these down loads were provided, there would be many enthusiasts choosing many different candidate primes. No one has to check that the number is a prime. All that needs to be checked is that the chosen number divides cleanly into N.

    You are saying that this has no chance of working. Then you are being ridiculous. Truth depends on the issues not on who is saying it.

    It is not difficult or tedious to provide the number N or the program. It is something to do. I think that many members of the Wii scene have been waiting for this chance to contribute.


    Codes like this can be cracked. For an industrial or military organization it is easier to steal, bribe or sneak the answer so nobody bothers.
     
  14. Midnight

    Newcomer Midnight Newbie

    Joined:
    May 24, 2008
    Messages:
    5
    Country:
    Singapore
    As a Computer Science degree holder, I too find it laughable that someone would even think that RSA hasn't been cracked only because military/industrial organizations have not yet bothered to do so. Anyone who's even glanced at the sheer number of research papers on these topics will know better.

    Nonetheless, I find it quite surprising that the RSA key in question is only 128 bits long (according to FAST6191). As many of you know, keys for asymmetric algorithms generally need to be much longer than keys for symmetric algorithms in order to offer an equivalent level of security. A 128 bit RSA key is very weak; today, it's not infeasible for even desktop computers to crack such a key. As a software engineer working in a defense technology firm, I'd probably risk being fired if I suggested using an RSA key of less than 1024 bits for any remotely serious use. (In fact, my organization mandates a minimum length of 2048 bits.)
     

Share This Page