5,579
edits
Changes
Jump to navigation
Jump to search
→Detailed explanation: removed the “first Google hit” quote because that site is completely copyrighted
Line 49:
Line 49:
−To quote from the first google hit for strncmp:
−
−<blockquote>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''.</blockquote>
−
−
</source>
</source>
The bug here is that payload_hash is a binary SHA1 hash (not an ASCII string), and therefore may contain a NULL byte ('\0').
+The bug here is that payload_hash is a binary SHA1 hash (not an ASCII string), and therefore may contain a NULL byte ('\0'). strncmp compared each byte in a binary block of data, stopping when either a NULL byte is reached, or the number of characters checked reaches the size passed in. Stopping prematurely still yields a positive result if both strings have the same NULL byte. This means that when strncmp finds a NULL byte it stops comparing, '''even if there is more data after the NULL'''.
−This last part means that when strncmp 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<sup>8*SHA1_LENGTH</sup> to 2<sup>8*(bytes up to the NULL)</sup>. That is a big change if the NULL is early in the hash. If the NULL byte is at 4th byte, that means that there is a one in 2<sup>8*4</sup> chance that the hash matches (three data bytes and the final NULL, which must also match). This is an average of 4 294 967 296 attempts to produce a valid partial collision, which can be computed in under 30 minutes on a modern computer that can compute a few million hashes per second. Nintendo signatures that have these properties certainly exist.
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<sup>8*SHA1_LENGTH</sup> to 2<sup>8*(bytes up to the NULL)</sup>. That is a big change if the NULL is early in the hash. If the NULL byte is at 4th byte, that means that there is a one in 2<sup>8*4</sup> chance that the hash matches (three data bytes and the final NULL, which must also match). This is an average of 4 294 967 296 attempts to produce a valid partial collision, which can be computed in under 30 minutes on a modern computer that can compute a few million hashes per second. Nintendo signatures that have these properties certainly exist.