Difference between revisions of "Signing bug"

From WiiBrew
Jump to navigation Jump to search
(→‎Technical explanation: included Korean Wii in fixes)
 
(15 intermediate revisions by 10 users not shown)
Line 1: Line 1:
== Simple explanation ==
+
The signing (also known as Trucha) bug was a bug present in earlier IOS versions that allowed the digital signatures (which show that Nintendo had approved the content in question) of software to be easily faked, which allowed the installation of software that Nintendo hadn't approved. Shortly after its widespread use appeared, it was patched; first in [[IOS37]]. This exploit was used in the original version of the [[Homebrew Channel]] installer, and is still used in many applications.
The signing (also known as Trucha) bug was a bug present in earlier IOS versions that allowed the digital signatures (which show that Nintendo had approved the content in question) of software to be easily faked, which allowed the installation of software that Nintendo had approved. Shortly after its widespread use appeared, it was patched, first in [[IOS37]]. This exploit was used in the original version of the Homebrew Channel installer, and is still used in many applications.  
 
  
== Detailed explanation ==
+
== Technical explanation ==
Here is a pseudocode implementation that shows the hash-comparison bug present in some versions of IOS:
+
Here is a simplified pseudocode implementation that shows the hash-comparison bug present in some versions of IOS:
 
<source lang=c>
 
<source lang=c>
 +
#define SHA1_LENGTH 20
 +
#define RSA_BLOCK_LENGTH 256
 +
#define PADDING_LENGTH RSA_BLOCK_LENGTH - SHA1_LENGTH
 +
 +
struct decrypted_signature {
 +
    u8 padding[PADDING_LENGTH]; // not verified
 +
    u8 sha1hash[SHA1_LENGTH];
 +
};
 +
 
struct rsa_cert {
 
struct rsa_cert {
     u32 key_id;
+
     u32 signature_type;
     char rsa_signature[1024];
+
     char rsa_signature[RSA_BLOCK_LENGTH]; // 256 bytes, 2048 bits
     char metadata[32];
+
     char unused[60];
    char content_hash[20];
 
 
};
 
};
  
int verify_cert (struct rsa_cert cert) {
+
struct tmdview {
  char *cert_hash=SHA1(cert.metadata + cert.content_hash);
+
    char issuer[0x40];
  char *sig_hash=rsa_decrypt(cert.rsa_signature, cert.key_id);
+
    // more metadata...
 +
    char content_hash[SHA1_LENGTH];
 +
    // more content records and hashes...
 +
}
  
   if (strncmp(cert_hash, sig_hash, SHA1_LENGTH) == 0) {
+
struct tmd {
     return CERT_OK;
+
    struct rsa_cert cert;
 +
    struct tmdview view;
 +
}
 +
 
 +
int verify_tmd (struct tmd stmd) {
 +
  struct decrypted_signature decrypted_sig = (struct decrypted_signature) RSA_DecryptSig(CA_public_key, stmd.cert.rsa_signature);
 +
  char sig_hash[SHA1_LENGTH] = decrypted_sig.sha1hash;
 +
  char payload_hash[SHA1_LENGTH] = SHA1(stmd.view);
 +
 
 +
   if (strncmp(payload_hash, sig_hash, SHA1_LENGTH) == 0) { // bug here!
 +
     return SIG_OK;
 
   } else {
 
   } else {
     return CERT_BAD;
+
     return SIG_BAD;
 
   }
 
   }
 
}
 
}
  
int is_a_valid_disc(struct rsa_cert cert, char *disc_hash) {
+
int is_a_valid_disc(struct tmd stmd, char *disc_hash) {
   if(memcmp(disc_hash, cert.content_hash, SHA1_LENGTH) != 0) {
+
   if(verify_tmd(stmd) == SIG_BAD) {
 
     return DISC_BAD;
 
     return DISC_BAD;
 
   }
 
   }
 
+
   if(memcmp(stmd.view.content_hash, disc_hash, SHA1_LENGTH) != 0) {
   if(verify_cert (cert) == CERT_BAD) {
 
 
     return DISC_BAD;
 
     return DISC_BAD;
  } else {
 
    return DISC_OK;
 
 
   }
 
   }
 +
 +
  return DISC_OK;
 
}
 
}
 
</source>
 
</source>
 
      
 
      
The bug here is that cert_hash 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'''.
To quote from the first google hit for strncmp:
+
 
 +
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.
 +
 
 +
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 (by changing the signature randomly, which is possible because Nintendo doesn't check the fixed padding in the decrypted RSA signature), all we have to do is brute force both until the first byte of the hash is zero. This only requires about 256 RSA decryptions and 256 SHA-1 sums, both of which can be computed in a fraction of a second.
  
"Compares up to num characters of the C string str1 to those of the C string str2.
+
The process can be simplified further by taking advantage of the mathematical properties of RSA. Given the signature ''m'', and the public key (''e'', ''n''), the decrypted signature is calculated as ''m''<sup>''e''</sup> mod ''n''. A zero signature (''m'' = 0) always results in a zero result, regardless of the values of ''e'' and ''n'' (that is, regardless of the certificate that is used to check the signature). All we have to do is zero out the signature and get a guaranteed result of all zeroes. This reduces the time needed to build a fake signature to an average of 256 short SHA-1 sums, which can be done in mere milliseconds. The actual number of attempts 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.
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'''.
+
tmbinc has a more thorough explanation [https://debugmo.de/2008/03/thank-you-datel/ here].
  
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.
+
This bug was first fixed in [[IOS37]]. A month later, Korean consoles were released with [[IOS40]] and above having this fixed. The fix was backported to [[IOS30]] and [[IOS31]] in the [[3.3]] update, and all remaining [[IOS]]es except [[IOS16]] had it fixed in [[3.3rev03]]. IOS16 was stubbed in [[4.0]].
  
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.
+
== iQue strncmp ==
 +
Interestingly, the iQue version of libc implements strncmp the way memcmp is meant to be implemented.{{ref|https://discord.com/channels/269333940928512010/420029476634886144/891424985409814558 (server invite: https://discord.gg/ZdqEhed)}} While the hash checking itself used memcmp, this suggests that Nintendo had legitimate confusion over the difference between strncmp and memcmp even before the Wii was released.
  
tmbinc has a more thorough explanation [http://debugmo.de/?p=61 here].
+
== References ==
 +
{{references}}
  
This bug was first fixed in [[IOS37]]. As of the [[System Menu 3.3|3.3 update]] the fix had spread to IOS30 & 31, and by [[23 Oct Updates|Oct 23, 2008]] it was in all but one IOS. This [[IOS16|last IOS]] was fixed with the [[System Menu 4.0|4.0 update]].
+
[[Category:Exploits]]
 +
[[Category:IOS Exploits]]

Latest revision as of 00:15, 14 October 2021

The signing (also known as Trucha) bug was a bug present in earlier IOS versions that allowed the digital signatures (which show that Nintendo had approved the content in question) of software to be easily faked, which allowed the installation of software that Nintendo hadn't approved. Shortly after its widespread use appeared, it was patched; first in IOS37. This exploit was used in the original version of the Homebrew Channel installer, and is still used in many applications.

Technical explanation

Here is a simplified pseudocode implementation that shows the hash-comparison bug present in some versions of IOS:

#define SHA1_LENGTH 20
#define RSA_BLOCK_LENGTH 256
#define PADDING_LENGTH RSA_BLOCK_LENGTH - SHA1_LENGTH

struct decrypted_signature {
    u8 padding[PADDING_LENGTH]; // not verified
    u8 sha1hash[SHA1_LENGTH];
};

struct rsa_cert {
    u32 signature_type;
    char rsa_signature[RSA_BLOCK_LENGTH]; // 256 bytes, 2048 bits
    char unused[60];
};

struct tmdview {
    char issuer[0x40];
    // more metadata...
    char content_hash[SHA1_LENGTH];
    // more content records and hashes...
}

struct tmd {
    struct rsa_cert cert;
    struct tmdview view;
}

int verify_tmd (struct tmd stmd) {
  struct decrypted_signature decrypted_sig = (struct decrypted_signature) RSA_DecryptSig(CA_public_key, stmd.cert.rsa_signature);
  char sig_hash[SHA1_LENGTH] = decrypted_sig.sha1hash;
  char payload_hash[SHA1_LENGTH] = SHA1(stmd.view);

  if (strncmp(payload_hash, sig_hash, SHA1_LENGTH) == 0) { // bug here!
     return SIG_OK;
  } else {
     return SIG_BAD;
  }
}

int is_a_valid_disc(struct tmd stmd, char *disc_hash) {
   if(verify_tmd(stmd) == SIG_BAD) {
     return DISC_BAD;
   }
   if(memcmp(stmd.view.content_hash, disc_hash, SHA1_LENGTH) != 0)  {
     return DISC_BAD;
   }

   return DISC_OK;
}

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 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 28*SHA1_LENGTH to 28*(bytes up to the NULL). 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 28*4 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.

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 (by changing the signature randomly, which is possible because Nintendo doesn't check the fixed padding in the decrypted RSA signature), all we have to do is brute force both until the first byte of the hash is zero. This only requires about 256 RSA decryptions and 256 SHA-1 sums, both of which can be computed in a fraction of a second.

The process can be simplified further by taking advantage of the mathematical properties of RSA. Given the signature m, and the public key (e, n), the decrypted signature is calculated as me mod n. A zero signature (m = 0) always results in a zero result, regardless of the values of e and n (that is, regardless of the certificate that is used to check the signature). All we have to do is zero out the signature and get a guaranteed result of all zeroes. This reduces the time needed to build a fake signature to an average of 256 short SHA-1 sums, which can be done in mere milliseconds. The actual number of attempts 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 here.

This bug was first fixed in IOS37. A month later, Korean consoles were released with IOS40 and above having this fixed. The fix was backported to IOS30 and IOS31 in the 3.3 update, and all remaining IOSes except IOS16 had it fixed in 3.3rev03. IOS16 was stubbed in 4.0.

iQue strncmp

Interestingly, the iQue version of libc implements strncmp the way memcmp is meant to be implemented.[1] While the hash checking itself used memcmp, this suggests that Nintendo had legitimate confusion over the difference between strncmp and memcmp even before the Wii was released.

References

1. https://discord.com/channels/269333940928512010/420029476634886144/891424985409814558 (server invite: https://discord.gg/ZdqEhed)