Signing bug

Here is a pseudocode implementation of roughly the same type of bug that existed until IOS37:

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 the hash can (and very 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.

tmbinc has a more thorough explanation here.