gh-ARMmbed/mbed-crypto

Watch

Fork 0

Unable to import an RSA keypair with P=Q=0 #189

New issue

Closed

opened 2019-07-25 10:55:57 -05:00 by userMF2 · 8 comments

userMF2 commented

2019-07-25 10:55:57 -05:00

(Migrated from github.com)

Description

Hello everyone,
First of all sorry for all the mistake(s) that you will find in the following part, but english is not my first language.

I'm currenlty trying to do a RSA sign with the function RSA_PKCS1v15_Sign and it seem that i came accross an issue in psa_import_key.
To be more accurate, this issue is in the function pk_parse_key_pkcs1_der. (see at the end for the complete path to this function)

After all imports (in my case i have only the parameters n, d and e), the function call mbedtls_rsa_complete. This function is trying to find p and q. Until here nothing wrong.

And now for the strange part :), in mbedtls_rsa_deduce_primes (the function call by mbedtls_rsa_complete) the first line is a check:
if( P == NULL || Q == NULL || P->p != NULL || Q->p != NULL )
but just before (in pk_parse_key_pkcs1_der), the mbedtls_rsa_import_raw is initialising P->p and Q->p to something not NULL, so i got MBEDTLS_ERR_MPI_BAD_INPUT_DATA everytime.

And here is my issue.

Maybe my code is wrong, i'm pretty confident about it, but i'm open to every sugestions and comments...

path:
RSA_PKCS1v15_Sign
->psa_import_key
->psa_import_key_into_slot
->psa_import_rsa_key
->mbedtls_pk_parse_key
->pk_parse_key_pkcs1_der
->mbedtls_rsa_complete
->mbedtls_rsa_deduce_primes

Have a good day,
Best regards,

userMF

Issue request type

[ ] Question
[ ] Enhancement
[x] Bug

### Description Hello everyone, First of all sorry for all the mistake(s) that you will find in the following part, but english is not my first language. I'm currenlty trying to do a RSA sign with the function RSA_PKCS1v15_Sign and it seem that i came accross an issue in psa_import_key. To be more accurate, this issue is in the function pk_parse_key_pkcs1_der. (see at the end for the complete path to this function) After all imports (in my case i have only the parameters n, d and e), the function call mbedtls_rsa_complete. This function is trying to find p and q. Until here nothing wrong. And now for the strange part :), in mbedtls_rsa_deduce_primes (the function call by mbedtls_rsa_complete) the first line is a check: if( P == NULL || Q == NULL || P->p != NULL || Q->p != NULL ) but just before (in pk_parse_key_pkcs1_der), the mbedtls_rsa_import_raw is initialising P->p and Q->p to something not NULL, so i got MBEDTLS_ERR_MPI_BAD_INPUT_DATA everytime. And here is my issue. Maybe my code is wrong, i'm pretty confident about it, but i'm open to every sugestions and comments... path: RSA_PKCS1v15_Sign ->psa_import_key ->psa_import_key_into_slot ->psa_import_rsa_key ->mbedtls_pk_parse_key ->pk_parse_key_pkcs1_der ->mbedtls_rsa_complete ->mbedtls_rsa_deduce_primes Have a good day, Best regards, userMF  ### Issue request type  [ ] Question [ ] Enhancement [x] Bug

gilles-peskine-arm commented

2019-07-25 11:10:05 -05:00

(Migrated from github.com)

Hi userMF,

What exact version of Mbed Crypto are you using?

Can you please attach a sample key that causes this problem?

Note that psa_import_key is not guaranteed to work if the key only contains {n,e,d}. See the description of psa_export_key for exactly what is required. That being said, it should currently work, because psa_import_key calls mbedtls_pk_parse_key which supports several different formats. But we do not guarantee that it will keep working in the future.

Hi userMF, What exact version of Mbed Crypto are you using? Can you please attach a sample key that causes this problem? Note that `psa_import_key` is not guaranteed to work if the key only contains {n,e,d}. See the description of `psa_export_key` for exactly what is required. That being said, it should currently work, because `psa_import_key` calls `mbedtls_pk_parse_key` which supports several different formats. But we do not guarantee that it will keep working in the future.

ciarmcom commented

2019-07-25 11:11:50 -05:00

(Migrated from github.com)

Internal Jira reference: https://jira.arm.com/browse/IOTCRYPT-837

*Internal Jira reference: https://jira.arm.com/browse/IOTCRYPT-837*

userMF2 commented

2019-07-26 02:57:49 -05:00

(Migrated from github.com)

Hi,
My bad, i forgot to put the sha1: 521dbc67da
and according to gitk it is from 2019/04/17 and it should be mbedcrypto-1.0.0.

Here are the keypair that cause my issue:
Modulus (n): size 128 bytes
0xa56e4a0e701017589a5187dc7ea841d156f2ec0e36ad52a44dfeb1e61f7ad991d8c51056ffedb162b4c0f283a12a88a394dff526ab7291cbb307ceabfce0b1dfd5cd9508096d5b2b8b6df5d671ef6377c0921cb23c270a70e2598e6ff89d19f105acc2d3f0cb35f29280e1386b6f64c4ef22e1e1f20d0ce8cffb2249bd9a2137

Private Exponent (d) : size 128 bytes 0x33a5042a90b27d4f5451ca9bbbd0b44771a101af884340aef9885f2a4bbe92e894a724ac3c568c8f97853ad07c0266c8c6a3ca0929f1e8f11231884429fc4d9ae55fee896a10ce707c3ed7e734e44727a39574501a532683109c2abacaba283c31b4bd2f53c3ee37e352cee34f9e503bd80c0622ad79c6dcee883547c6a3b325

Public Exponent (e): 0x010001, size 3

The pcks1 structure pass to psa_import_key:
0x3082012002810100028180a56e4a0e701017589a5187dc7ea841d156f2ec0e36ad52a44dfeb1e61f7ad991d8c51056ffedb162b4c0f283a12a88a394dff526ab7291cbb307ceabfce0b1dfd5cd9508096d5b2b8b6df5d671ef6377c0921cb23c270a70e2598e6ff89d19f105acc2d3f0cb35f29280e1386b6f64c4ef22e1e1f20d0ce8cffb2249bd9a213702810301000102818033a5042a90b27d4f5451ca9bbbd0b44771a101af884340aef9885f2a4bbe92e894a724ac3c568c8f97853ad07c0266c8c6a3ca0929f1e8f11231884429fc4d9ae55fee896a10ce707c3ed7e734e44727a39574501a532683109c2abacaba283c31b4bd2f53c3ee37e352cee34f9e503bd80c0622ad79c6dcee883547c6a3b325028100028100028100028100028100

Have a good day,
Best regards,

userMF

Hi, My bad, i forgot to put the sha1: 521dbc67dabf5f5dc2ad8148b6f01662805caac7 and according to gitk it is from 2019/04/17 and it should be mbedcrypto-1.0.0. Here are the keypair that cause my issue: Modulus (n): size 128 bytes `0xa56e4a0e701017589a5187dc7ea841d156f2ec0e36ad52a44dfeb1e61f7ad991d8c51056ffedb162b4c0f283a12a88a394dff526ab7291cbb307ceabfce0b1dfd5cd9508096d5b2b8b6df5d671ef6377c0921cb23c270a70e2598e6ff89d19f105acc2d3f0cb35f29280e1386b6f64c4ef22e1e1f20d0ce8cffb2249bd9a2137` Private Exponent (d) : size 128 bytes `0x33a5042a90b27d4f5451ca9bbbd0b44771a101af884340aef9885f2a4bbe92e894a724ac3c568c8f97853ad07c0266c8c6a3ca0929f1e8f11231884429fc4d9ae55fee896a10ce707c3ed7e734e44727a39574501a532683109c2abacaba283c31b4bd2f53c3ee37e352cee34f9e503bd80c0622ad79c6dcee883547c6a3b325` Public Exponent (e): `0x010001`, size 3 The pcks1 structure pass to `psa_import_key:` `0x3082012002810100028180a56e4a0e701017589a5187dc7ea841d156f2ec0e36ad52a44dfeb1e61f7ad991d8c51056ffedb162b4c0f283a12a88a394dff526ab7291cbb307ceabfce0b1dfd5cd9508096d5b2b8b6df5d671ef6377c0921cb23c270a70e2598e6ff89d19f105acc2d3f0cb35f29280e1386b6f64c4ef22e1e1f20d0ce8cffb2249bd9a213702810301000102818033a5042a90b27d4f5451ca9bbbd0b44771a101af884340aef9885f2a4bbe92e894a724ac3c568c8f97853ad07c0266c8c6a3ca0929f1e8f11231884429fc4d9ae55fee896a10ce707c3ed7e734e44727a39574501a532683109c2abacaba283c31b4bd2f53c3ee37e352cee34f9e503bd80c0622ad79c6dcee883547c6a3b325028100028100028100028100028100` Have a good day, Best regards, userMF

gilles-peskine-arm commented

2019-07-26 05:27:57 -05:00

(Migrated from github.com)

Summary

The key is not valid according to PKCS#1, and Mbed Crypto does not recognize this particular extension of the PKCS#1 format. How did you produce this key? We may add this feature for interoperability, but it is not a bug.

Do note, however, that the PSA Cryptography API specification only promises to support one canonical representation, which is the DER encoding of the PKCS#1 format (without optional parts). Right now Mbed Crypto allows many other formats, but we are actually planning to remove this ability (I don't know when) to decrease the code size. So I recommend that you arrange to pass input with P and Q.

Detailed analysis

How did you obtain the pkcs1 structure? It declares a length of 0x0120 = 288 bytes, but only 287 bytes follow. If I replace 30820120… by 3082011f…, the ASN.1 structure is well-formed (it isn't a valid RSAPrivateKey as we'll see below, and it doesn't follow DER, but it's valid ASN.1) and I do observe the failure of mbedtls_rsa_deduce_primes.

The ASN.1 structure declares P and Q as having the value 0 using the encoding 028100. This is not DER, since it has a non-minimal length encoding: DER would be 020100. This is not the source of the problem, though: the behavior I describe below is the same with 020100.

mbedtls_asn1_get_mpi produces an MPI which has the value 0, but encoded as having one limb. In mbedtls_rsa_complete, pq_missing is set to true because P and Q are both zero. So it calls mbedtls_rsa_deduce_primes, which complains because P and Q have a limb (they happen to be zero, but with a non-canonical internal representation).

I see two potential issues here:

Maybe mbedtls_asn1_get_mpi should produce {s=1, n=0, p=NULL} when the input is zero, rather than allocating one limb to match the number of source digits. However this is not clear-cut to me: mbedtls_asn1_get_mpi could skip leading zeroes, but this may lead to new side channels where the number of leading zeroes is more visible through timing than before.
There's an inconsistency between the checks in mbedtls_rsa_deduce_primes and the checks in mbedtls_rsa_complete: complete() tests for numerical zero whereas deduce_primes() wants an empty bignum (which is the canonical internal representation for zero). I'd rate that as a low-priority maintenance issue rather than a bug since this should mostly not happen: when mbedtls_rsa_complete has to complete P and Q, those should be empty (which happens to be interpreted as zero) and not some arbitrary representation of zero.

All of this is triggered by prime1=0 and prime2=0 in an RSAPrivateKey. But PKCS#1 specify RSAPrivateKey with “prime1 is the prime factor p of n” and “prime2 is the prime factor q of n”. It doesn't state that these may be 0 in which case they need to be reconstructed from D.

Mbed Crypto already supports calculating P and Q from D (and then always calculates DP, DdQ and U from the others). We could make it recognize that when P=Q=0 when parsing a key, it should treat them as missing. But that would be for added interoperability rather than to comply with PKCS#1.

### Summary The key is not valid according to PKCS#1, and Mbed Crypto does not recognize this particular extension of the PKCS#1 format. How did you produce this key? We may add this feature for interoperability, but it is not a bug. Do note, however, that the [PSA Cryptography API specification](https://armmbed.github.io/mbed-crypto/html/from_doxygen.html#c.psa_export_key) only promises to support one canonical representation, which is the DER encoding of the PKCS#1 format (without optional parts). Right now Mbed Crypto allows many other formats, but we are actually planning to remove this ability (I don't know when) to decrease the code size. So I recommend that you arrange to pass input with P and Q. ### Detailed analysis How did you obtain the pkcs1 structure? It declares a length of `0x0120` = 288 bytes, but only 287 bytes follow. If I replace `30820120…` by `3082011f…`, the ASN.1 structure is well-formed (it isn't a valid RSAPrivateKey as we'll see below, and it doesn't follow DER, but it's valid ASN.1) and I do observe the failure of `mbedtls_rsa_deduce_primes`. The ASN.1 structure declares P and Q as having the value 0 using the encoding `028100`. This is not DER, since it has a non-minimal length encoding: DER would be `020100`. This is not the source of the problem, though: the behavior I describe below is the same with `020100`. `mbedtls_asn1_get_mpi` produces an MPI which has the value 0, but encoded as having one limb. In `mbedtls_rsa_complete`, `pq_missing` is set to true because P and Q are both zero. So it calls `mbedtls_rsa_deduce_primes`, which complains because `P` and `Q` have a limb (they happen to be zero, but with a non-canonical internal representation). I see two potential issues here: * Maybe `mbedtls_asn1_get_mpi` should produce `{s=1, n=0, p=NULL}` when the input is zero, rather than allocating one limb to match the number of source digits. However this is not clear-cut to me: `mbedtls_asn1_get_mpi` could skip leading zeroes, but this may lead to new side channels where the number of leading zeroes is more visible through timing than before. * There's an inconsistency between the checks in `mbedtls_rsa_deduce_primes` and the checks in `mbedtls_rsa_complete`: complete() tests for numerical zero whereas deduce_primes() wants an empty bignum (which is the canonical internal representation for zero). I'd rate that as a low-priority maintenance issue rather than a bug since this should mostly not happen: when `mbedtls_rsa_complete` has to complete P and Q, those should be empty (which happens to be interpreted as zero) and not some arbitrary representation of zero. All of this is triggered by `prime1=0` and `prime2=0` in an RSAPrivateKey. But [PKCS#1](https://tools.ietf.org/html/rfc8017#appendix-A.1.2) specify `RSAPrivateKey` with “prime1 is the prime factor p of n” and “prime2 is the prime factor q of n”. It doesn't state that these may be 0 in which case they need to be reconstructed from D. Mbed Crypto already supports calculating P and Q from D (and then always calculates DP, DdQ and U from the others). We could make it recognize that when P=Q=0 when parsing a key, it should treat them as missing. But that would be for added interoperability rather than to comply with PKCS#1.

userMF2 commented

2019-07-26 06:41:30 -05:00

(Migrated from github.com)

Hello again,

How did you produce this key?

Well, i got it from a STMicroelectronic example on RSA and in their example, they don't give any P or Q. They only give n, d and e :( .
https://www.st.com/en/embedded-software/x-cube-cryptolib.html
(It is located in Project/STM32_Cryptographic_Examples/RSA/RSA_Signature)

My first goal, was to do a Sign operation with those data and mbed-crypto, but, of what i understand so far, i can't.

Do you know if is it even possible ?

How did you obtain the pkcs1 structure?

I create it from scratch with the data that i got. And also, by looking in the code to know what i needed to have to use the function. (because i tryied following wikipedia on DER but got bad result with the format)

This explain why the size is not good ...

Have a good day,
Best regards,

userMF

Hello again, > How did you produce this key? Well, i got it from a STMicroelectronic example on RSA and in their example, they don't give any P or Q. They only give n, d and e :( . [https://www.st.com/en/embedded-software/x-cube-cryptolib.html](url) (It is located in **Project/STM32_Cryptographic_Examples/RSA/RSA_Signature**) My first goal, was to do a Sign operation with those data and mbed-crypto, but, of what i understand so far, i can't. Do you know if is it even possible ? > How did you obtain the pkcs1 structure? I create it from scratch with the data that i got. And also, by looking in the code to know what i needed to have to use the function. (because i tryied following wikipedia on DER but got bad result with the format) This explain why the size is not good ... Have a good day, Best regards, userMF

gilles-peskine-arm commented

2019-07-26 07:04:27 -05:00

(Migrated from github.com)

Ok, I see. So Mbed Crypto can work with such a key, but you would need to import it using lower-level APIs: mbedtls_pk_setup with MBEDTLS_PK_RSA, then get the mbedtls_rsa_context with mbedtls_pk_rsa, and call mbedtls_rsa_import(rsa_ctx, N, NULL, NULL, D, E) then mbedtls_rsa_complete.

We currently don't have plans to support this through the psa_xxx API. One way to convert it would be to use mbedtls_xxx APIs as above to import it, then mbedtls_pk_write_key_der to output a key that psa_import_key supports.

Ok, I see. So Mbed Crypto can work with such a key, but you would need to import it using lower-level APIs: `mbedtls_pk_setup` with `MBEDTLS_PK_RSA`, then get the `mbedtls_rsa_context` with `mbedtls_pk_rsa`, and call `mbedtls_rsa_import(rsa_ctx, N, NULL, NULL, D, E)` then `mbedtls_rsa_complete`. We currently don't have plans to support this through the `psa_xxx` API. One way to convert it would be to use `mbedtls_xxx` APIs as above to import it, then `mbedtls_pk_write_key_der` to output a key that `psa_import_key` supports.

👍 1

userMF2 commented

2019-07-26 07:14:01 -05:00

(Migrated from github.com)