Signing bug

Here is an extremely concise example of the same type of bug that existed until The June 16th, 2008 Wii Software Upgrade:

char *hash1=hash(realstuff);

invalid=strncmp(hash1,signaturehash,HASHLENGTH);

if(invalid!=0) {
 pretendItsNotAWiiDisc();
}

The bug here is that the hash can (and likely does) contain a NULL byte, (chr)0 that is. To quote from the first google hit for strncmp:

"Compares up to num characters of the C string str1 to those of the C string str2. This function starts comparing the first character of each string. If they are equal to each other, it continues with the following pairs until the characters differ, until a terminating null-character is reached, or until num characters match in both strings, whichever happens first."

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. This means that 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.

Now, it would require a signed contents that begins with a null to completely bypass the checking. Normally, that would mean a need to find an existing signed content that can be exploited. But, the hashing function has an important behavior, with only null bytes as the input, the hash is only null bytes. Given that we control all the hashed data and can safely set it all to null, we don't even need to piggyback on something that Nintendo have already signed.

tmbinc has a more thorough explanation here.