Signing bug

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

struct rsa_cert {
    u32 key_id;
    char rsa_signature[1024];
    char metadata[32];
    char content_hash[20];
};

int verify_cert (struct rsa_cert cert) {
  char *cert_hash=SHA1(cert.metadata + cert.content_hash);
  char *sig_hash=rsa_decrypt(cert.rsa_signature, cert.key_id);

  if (strncmp(cert_hash, sig_hash, SHA1_LENGTH) == 0) {
     return CERT_OK;
  } else {
     return CERT_BAD;
  }
}

int is_a_valid_disc(struct rsa_cert cert, char *disc_hash) {
   if(memcmp(disc_hash, cert.content_hash, SHA1_LENGTH) != 0)  {
     return DISC_BAD;
   }

   if(verify_cert (cert) == CERT_BAD) {
     return DISC_BAD;
   } else {
     return DISC_OK;
   }
}

The bug here is that cert_hash may contain a NULL byte ('\0'). 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, 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.

tmbinc has a more thorough explanation here.