Changes

This last part means that if it finds a NULL byte, it stops comparing, '''even if there is more data after the NULL'''.

This last part means that if it finds a NULL byte, it stops comparing, '''even if there is more data after the NULL'''.

This reduces the effective length of the hash to the number of bytes before the NULL byte, and the difficulty of finding a hash collision is reduced from 2^(HASHLENGTH*8) to 2^(bytes before the null * 8). That is a big change if the NULL is early in the hash. Assuming the NULL is at the 5th byte, that means that there is a one in 2^(4*8) chance that the hash matches, or one in 4 294 967 296, fairly computable within a reasonable time frame on a current computer that can try a few million hash inputs each sec.

This reduces the effective length of the hash to the number of bytes before the NULL byte, and the difficulty of finding a hash collision is reduced from 2^(HASHLENGTH*8) to 2^(bytes before the null * 8). That is a big change if the NULL is early in the hash. Assuming the NULL is at the 4th byte, that means that there is a one in 2^(4*8) chance that the hash matches (three data bytes and the final NULL, which must also match). This is one in 4 294 967 296, fairly computable within a reasonable time frame on a current computer that can try a few million hash inputs each sec. Nintendo signatures that have these properties certainly exist.

 

Furthermore, since we can brute force both the SHA-1 hash of the content (by changing unused bytes) and the SHA-1 that results after decrypting (because Nintendo doesn't check the padding), all we have to do is brute force the first byte in both places. This only requires about 256 RSA decryptions and 256 SHA-1 sums, both of which can be computed in a fraction of a second. Furthermore, due to the mathematical properties of RSA, a zero input results in a zero output. All we have to do is zero out the signature and get a guaranteed result of all zeroes, regardless of what certificate is being used to decrypt. This reduces the time needed to build a fake signature to about 256 short SHA-1 sums, which can be done in mere milliseconds. The actual number of sums required can vary (and could theoretically be infinite), since SHA-1 behaves like a random number generator. This is why having to try a couple thousand times isn't uncommon, and why changing a single byte when bruteforcing is not sufficient.

tmbinc has a more thorough explanation [http://debugmo.de/?p=61 here].

tmbinc has a more thorough explanation [http://debugmo.de/?p=61 here].