search

apache / incubator-milagro-crypto-c

Apache milagro (Incubating)
Other
36 stars 15 forks source link

Incorrect RSA private key generation and potentials for fault attack #90

Open 1one-w01f opened 3 years ago

1one-w01f commented 3 years ago

Hi,

I recently run into a rather interesting problem. It appears to me that the RSA key generation in milagro might sometimes be incorrect, and I have no ideas to why that would be the case.

Here's the source code I prepared to illustrate the problem. For simplicity I just replaced the source code of test/test_rsa_2048.c with this. The build target I used was LINUX_64BIT_NIST256_RSA2048.

#include <stdio.h>
#include <time.h>
#include "rsa_2048.h"
#include "randapi.h"

void print_keypair(rsa_private_key_2048 *priv, rsa_public_key_2048 *pub)
{
    printf(" priv->p = ");
    FF_2048_output(priv->p,FFLEN_2048/2);
    printf("\n");
    printf(" priv->q = ");
    FF_2048_output(priv->q,FFLEN_2048/2);
    printf("\n");

    printf("\n");

    printf("  pub->n = ");
    FF_2048_output(pub->n,FFLEN_2048);
    printf("\n");

    printf("\n");

    printf("priv->dp = ");
    FF_2048_output(priv->dp,FFLEN_2048/2);
    printf("\n");
    printf("priv->dq = ");
    FF_2048_output(priv->dq,FFLEN_2048/2);
    printf("\n");
    printf(" priv->c = ");
    FF_2048_output(priv->c,FFLEN_2048/2);
    printf("\n");
}

int main(int argc, char *argv[])
{
    char m[RFS_2048],ml[RFS_2048],c[RFS_2048],s[RFS_2048];
    char p[RFS_2048/2], q[RFS_2048/2];

    rsa_public_key_2048 pub;
    rsa_private_key_2048 priv;

    octet M= {0,sizeof(m),m};
    octet ML= {0,sizeof(ml),ml};
    octet C= {0,sizeof(c),c};
    octet S= {0,sizeof(s),s};
    octet P= {sizeof(p), sizeof(p), p};
    octet Q= {sizeof(q), sizeof(q), q};

    // somehow this prime number leads to incorrect dp, which is quite weird
    OCT_fromHex(&P, "f55d1f9bde519d3d30e9a0820a0850f3a6d05efa82dcc7ef948a09834224ad6fb77ee792f53b1ee6efc0270e5e8fdd59fab40ada833df0ea69eb2f0b37d717a3fd0329280cd47525fd22970c8fd860c7be749482c42a6e16a4b5b7edf27e01214f55fd5839a11c86be6bbd8b01e5ddeef743bca59e896c1751145d4b6a9da9ed");

    OCT_fromHex(&Q,"f34e8af7a6b3b2d2906890db77f56b8c4c5a5af42bec8cacd79fc479606d85eeb641ec95aef73d0e7e24f0da9115a524d9787d573ed3a1868bff2765cc5b9e1238a7931bdd5afd51a0bd6bf93f26909fff6d93d335e6785959c14f851205ad4a8ce995e6f92e490e7a5feab2b9fcda0080bedc17fa816227f2d6034044c0c363");

    // use our choice of P and Q
    RSA_2048_KEY_PAIR(NULL,3,&priv,&pub,&P,&Q);

    print_keypair(&priv, &pub);

// ======
    printf("\n===\n\n");

    OCT_fromHex(&P, "db59a11194cb81be97715d9ea436484c7fd39cee1a71dd1e896e08cc2d91d95a2d6d561f48db72acea57450ecfd4dc5399c1f8ce7abbb8b99c92f9c7be7ab2df6990b473c5a464eaa4d34747d022e47c17b549905db305986af5970442ad54714ee7fce2c8c443da7b22f4354e105c009a8d36de733d9fb02bfbcd57803bdcfb");

    OCT_fromHex(&Q, "f6457c323b66f43fa7a20f03b01a8c09c257f7fa65c7ce6a01acd816bca4de5da7692fd82ac036ca18bcc1d36e03a9ca6c2c1cf9007c106932c946cb51acb151c5c2912369553a70ddea742bc5673baaa962f8028c5ec7f4699bffd6c7beab3c278424a15548a4fce75946784036d2a9a118698224b3f218e66d980786252c93");

    // use our choice of P and Q
    RSA_2048_KEY_PAIR(NULL,3,&priv,&pub,&P,&Q);

    print_keypair(&priv, &pub);

// === clean up ===

    RSA_2048_PRIVATE_KEY_KILL(&priv);

    OCT_clear(&M);
    OCT_clear(&ML);   /* clean up afterwards */
    OCT_clear(&C);

    return 0;
}

Which produces the following output:

priv->p = f55d1f9bde519d3d30e9a0820a0850f3a6d05efa82dcc7ef948a09834224ad6fb77ee792f53b1ee6efc0270e5e8fdd59fab40ada833df0ea69eb2f0b37d717a3fd0329280cd47525fd22970c8fd860c7be749482c42a6e16a4b5b7edf27e01214f55fd5839a11c86be6bbd8b01e5ddeef743bca59e896c1751145d4b6a9da9ed priv->q = f34e8af7a6b3b2d2906890db77f56b8c4c5a5af42bec8cacd79fc479606d85eeb641ec95aef73d0e7e24f0da9115a524d9787d573ed3a1868bff2765cc5b9e1238a7931bdd5afd51a0bd6bf93f26909fff6d93d335e6785959c14f851205ad4a8ce995e6f92e490e7a5feab2b9fcda0080bedc17fa816227f2d6034044c0c363

pub->n = e932ac92252f585b3a80a4dd76a897c8b7652952fe788f6ec8dd640587a1ee5647670a8ad4c2be0f9fa6e49c605adf77b5174230af7bd50e5d6d6d6d28ccf0a886a514cc72e51d209cc772a52ef419f6a953f3135929588ebe9b351fca61ced78f346fe00dbb6306e5c2a4c6dfc3779af85ab417371cf34d8387b9b30ae46d7a 5ff5a655b8d8455f1b94ae736989d60a6f2fd5cadbffbd504c5a756a2e6bb5cecc13bca7503f6df8b52ace5c410997e98809db4dc30d943de4e812a47553dce54844a78e36401d13f77dc650619fed88d8b3926e3d8e319c80c744779ac5d6abe252896950917476ece5e8fc27d5f053d6018d91b502c4787558a002b9283da7

priv->dp = 4c8b6ace1ba4747563b3d9f6c29e01fb968c96e116707fb4556b811f39b047aac0d7fc303650ff6a0a14e969656094a08dab8231a71c76613ae1063d87aea343b8a2146fc5b850693e1d7167ab97e063b8c383462e8394f47ff0fdb4c6d4e5872c49c2b459841670b808f68173248883f16d95c698b0dd39a5e167e840047571 priv->dq = a2345ca519cd21e1b59b0b3cfaa39d0832e6e74d729db31de5152da6404903f479814863c9fa28b45418a091b60e6e1890fafe3a29e26baf07ff6f9932e7beb6d06fb767e8e7538bc07e47fb7f6f0b1554f3b7e223eefae63bd6350361591e31b34663ef50c98609a6ea9c7726a89155ab29e80ffc56416ff73957802dd5d797 priv->c = 6f1e5e6d113bffba6e9fe60cbfd0b959f0b78fb8f71db4ab4f63147abec85beb2a982acde258672046843ce3b9f93a33ff1b25602762dfd8dbddf36e3b9815a1bf14a9dbba3d28df3dfb830fb976662cc1b41026207aa16686f49c23f93f1312ba29ef76a0c13fb03e727247b632dda5a06bf6d385da9831af4ec18d1d23df95

===

priv->p = db59a11194cb81be97715d9ea436484c7fd39cee1a71dd1e896e08cc2d91d95a2d6d561f48db72acea57450ecfd4dc5399c1f8ce7abbb8b99c92f9c7be7ab2df6990b473c5a464eaa4d34747d022e47c17b549905db305986af5970442ad54714ee7fce2c8c443da7b22f4354e105c009a8d36de733d9fb02bfbcd57803bdcfb priv->q = f6457c323b66f43fa7a20f03b01a8c09c257f7fa65c7ce6a01acd816bca4de5da7692fd82ac036ca18bcc1d36e03a9ca6c2c1cf9007c106932c946cb51acb151c5c2912369553a70ddea742bc5673baaa962f8028c5ec7f4699bffd6c7beab3c278424a15548a4fce75946784036d2a9a118698224b3f218e66d980786252c93

pub->n = d303aa59c3248225f2ff52e32e33cdcb797c3b501fed5e51c0189f27ef7cd614c7c4cbf2079e663b24f7ae2e9683b4878ce662d6c944196874f4a48422353303c9ad8ffd2824b4f70996ee558a89e1e98679305209a124aaf62eecd3187d2d8ee2cf5eb1b5a1b7347958aa53205b1f726856903d6a953ed72a74673c92f46f52 92b4f1c59cdb645a6afc4d0381dec80444775658c54995bf0cba58e5f90f152a557172bc040c432fe63ede5b1cf14f2f1a11d30d3a96baa24c3a3982461292be8e9db35fd088a8cbaf0e26326e630ee690368cd0a8868502e9ddb17dde45179ce7bb22b10f9deb2e3d8ddcd30ca97c9bae84ca7c3c9a13afa95de4783ea20821

priv->dp = 923bc0b66332567f0fa0e9146d7985885537bdf411a13e145b9eb0881e613b91739e396a30924c7346e4d8b48a8de837bbd6a5defc7d25d1130ca68529a721ea4660784d2e6d989c6de22f85356c9852ba78dbb593ccae659ca3ba02d71e384b89effdec85d82d3c52174d78deb592ab11b379e9a22915201d5288e50027e8a7** priv->dq = a42e52cc2799f82a6fc15f57cabc5d5bd6e54ffc43da899c011de5647dc33ee91a461fe571d579dc107dd68cf40271319d72bdfb55a80af0cc862f32367320e12e81b6179b8e26f5e946f81d2e44d271c641faac5d94854d9bbd5539da7f1cd2c502c31638db18a89a3b84502acf371bc0baf1016dcd4c10999e655a596e1db7 priv->c = b163cc8298e63ea294f20288143304adc9a555ca170e55942954773801405652d8f998da549541782bb565ff49b32ae5f6d814bf38a878c598c6307fc294a0151f2681b8a39d6ace0a732feb6cb514a03de8d92290a8f1499231a945d698c8461cde13156d9bfc5b09ca3bf0d27a770f3ab3fedb375bd4135c8dcb57f9d60881

The primes P and Q were all copied from RSA private keys generated by OpenSSL. If we use OpenSSL to check the numbers of the 2 private keys:

$ openssl rsa -in privkey.pem -noout -text
RSA Private-Key: (2048 bit, 2 primes)
modulus:
    00:e9:32:ac:92:25:2f:58:5b:3a:80:a4:dd:76:a8:
    97:c8:b7:65:29:52:fe:78:8f:6e:c8:dd:64:05:87:
    a1:ee:56:47:67:0a:8a:d4:c2:be:0f:9f:a6:e4:9c:
    60:5a:df:77:b5:17:42:30:af:7b:d5:0e:5d:6d:6d:
    6d:28:cc:f0:a8:86:a5:14:cc:72:e5:1d:20:9c:c7:
    72:a5:2e:f4:19:f6:a9:53:f3:13:59:29:58:8e:be:
    9b:35:1f:ca:61:ce:d7:8f:34:6f:e0:0d:bb:63:06:
    e5:c2:a4:c6:df:c3:77:9a:f8:5a:b4:17:37:1c:f3:
    4d:83:87:b9:b3:0a:e4:6d:7a:5f:f5:a6:55:b8:d8:
    45:5f:1b:94:ae:73:69:89:d6:0a:6f:2f:d5:ca:db:
    ff:bd:50:4c:5a:75:6a:2e:6b:b5:ce:cc:13:bc:a7:
    50:3f:6d:f8:b5:2a:ce:5c:41:09:97:e9:88:09:db:
    4d:c3:0d:94:3d:e4:e8:12:a4:75:53:dc:e5:48:44:
    a7:8e:36:40:1d:13:f7:7d:c6:50:61:9f:ed:88:d8:
    b3:92:6e:3d:8e:31:9c:80:c7:44:77:9a:c5:d6:ab:
    e2:52:89:69:50:91:74:76:ec:e5:e8:fc:27:d5:f0:
    53:d6:01:8d:91:b5:02:c4:78:75:58:a0:02:b9:28:
    3d:a7
publicExponent: 3 (0x3)
privateExponent:
    00:9b:77:1d:b6:c3:74:e5:92:27:00:6d:e8:f9:c5:
    ba:85:cf:98:c6:37:54:50:5f:9f:30:93:98:03:af:
    c1:49:8e:da:44:b1:b1:e3:2c:7e:b5:15:19:ed:bd:
    95:91:ea:4f:ce:0f:81:75:ca:52:8e:09:93:9e:48:
    f3:70:88:a0:70:59:c3:63:32:f7:43:68:c0:68:84:
    f7:18:c9:f8:11:4f:1b:8d:4c:b7:90:c6:3b:09:d4:
    67:78:bf:dc:41:34:8f:b4:cd:9f:ea:b3:d2:42:04:
    99:2c:6d:d9:ea:82:4f:bc:a5:91:cd:64:cf:68:a2:
    33:ad:05:26:77:5c:98:48:fa:fa:31:52:81:77:e1:
    f8:df:91:81:a8:b9:45:08:11:06:fd:58:bd:3d:73:
    79:9b:22:95:75:c4:f3:b2:91:01:a0:3e:e1:f0:54:
    72:b3:61:57:84:d9:24:4c:e0:ed:63:9c:77:e8:e2:
    12:ab:52:ab:dd:f4:a9:28:22:4b:6b:6f:74:b7:11:
    47:86:dd:60:71:bd:91:13:d7:87:0c:6b:52:c0:bc:
    8b:9c:10:2c:fe:32:1d:ac:35:7e:03:0e:d6:c5:80:
    04:0c:a4:1c:13:d6:b4:96:78:11:80:7e:f2:a2:25:
    98:3e:a9:f8:8d:67:fa:a4:26:20:f4:2a:4f:5b:db:
    e0:3b
prime1:
    00:f5:5d:1f:9b:de:51:9d:3d:30:e9:a0:82:0a:08:
    50:f3:a6:d0:5e:fa:82:dc:c7:ef:94:8a:09:83:42:
    24:ad:6f:b7:7e:e7:92:f5:3b:1e:e6:ef:c0:27:0e:
    5e:8f:dd:59:fa:b4:0a:da:83:3d:f0:ea:69:eb:2f:
    0b:37:d7:17:a3:fd:03:29:28:0c:d4:75:25:fd:22:
    97:0c:8f:d8:60:c7:be:74:94:82:c4:2a:6e:16:a4:
    b5:b7:ed:f2:7e:01:21:4f:55:fd:58:39:a1:1c:86:
    be:6b:bd:8b:01:e5:dd:ee:f7:43:bc:a5:9e:89:6c:
    17:51:14:5d:4b:6a:9d:a9:ed
prime2:
    00:f3:4e:8a:f7:a6:b3:b2:d2:90:68:90:db:77:f5:
    6b:8c:4c:5a:5a:f4:2b:ec:8c:ac:d7:9f:c4:79:60:
    6d:85:ee:b6:41:ec:95:ae:f7:3d:0e:7e:24:f0:da:
    91:15:a5:24:d9:78:7d:57:3e:d3:a1:86:8b:ff:27:
    65:cc:5b:9e:12:38:a7:93:1b:dd:5a:fd:51:a0:bd:
    6b:f9:3f:26:90:9f:ff:6d:93:d3:35:e6:78:59:59:
    c1:4f:85:12:05:ad:4a:8c:e9:95:e6:f9:2e:49:0e:
    7a:5f:ea:b2:b9:fc:da:00:80:be:dc:17:fa:81:62:
    27:f2:d6:03:40:44:c0:c3:63
exponent1:
    00:a3:93:6a:67:e9:8b:be:28:cb:46:6b:01:5c:05:
    8b:4d:19:e0:3f:51:ac:93:2f:f5:0d:b1:5b:ac:d6:
    c3:1e:4a:7a:54:9a:61:f8:d2:14:99:f5:2a:c4:b4:
    3f:0a:93:91:51:cd:5c:91:ac:d3:f5:f1:9b:f2:1f:
    5c:cf:e4:ba:6d:53:57:70:c5:5d:e2:f8:c3:fe:17:
    0f:5d:b5:3a:eb:2f:d4:4d:b8:57:2d:71:9e:b9:c3:
    23:cf:f3:f6:fe:ab:6b:8a:39:53:90:26:6b:68:59:
    d4:47:d3:b2:01:43:e9:49:fa:2d:28:6e:69:b0:f2:
    ba:36:0d:93:87:9c:69:1b:f3
exponent2:
    00:a2:34:5c:a5:19:cd:21:e1:b5:9b:0b:3c:fa:a3:
    9d:08:32:e6:e7:4d:72:9d:b3:1d:e5:15:2d:a6:40:
    49:03:f4:79:81:48:63:c9:fa:28:b4:54:18:a0:91:
    b6:0e:6e:18:90:fa:fe:3a:29:e2:6b:af:07:ff:6f:
    99:32:e7:be:b6:d0:6f:b7:67:e8:e7:53:8b:c0:7e:
    47:fb:7f:6f:0b:15:54:f3:b7:e2:23:ee:fa:e6:3b:
    d6:35:03:61:59:1e:31:b3:46:63:ef:50:c9:86:09:
    a6:ea:9c:77:26:a8:91:55:ab:29:e8:0f:fc:56:41:
    6f:f7:39:57:80:2d:d5:d7:97
coefficient:
    00:85:4e:43:ad:27:2d:f5:81:12:c9:84:ca:73:eb:
    bf:9a:57:8a:56:53:ff:eb:79:dc:43:a4:20:27:b5:
    5a:69:27:d7:74:65:c4:2d:83:e9:d8:ee:9e:7c:bc:
    91:6f:ed:76:2a:7b:90:24:a5:bd:ee:8a:f3:1d:38:
    d5:c1:84:0d:80:78:13:9a:3c:b0:04:7c:c7:36:cf:
    22:4d:99:25:f6:1a:42:fd:0f:48:87:09:e7:24:a5:
    c6:f3:21:40:a0:5f:22:e4:9b:37:2d:f7:f4:39:c6:
    ad:86:07:89:6b:d6:b3:8a:d5:9e:bd:be:1b:8d:e9:
    32:54:35:25:7e:4c:a4:b0:9d
$ openssl rsa -in privkey.pem -noout -text
RSA Private-Key: (2048 bit, 2 primes)
modulus:
    00:d3:03:aa:59:c3:24:82:25:f2:ff:52:e3:2e:33:
    cd:cb:79:7c:3b:50:1f:ed:5e:51:c0:18:9f:27:ef:
    7c:d6:14:c7:c4:cb:f2:07:9e:66:3b:24:f7:ae:2e:
    96:83:b4:87:8c:e6:62:d6:c9:44:19:68:74:f4:a4:
    84:22:35:33:03:c9:ad:8f:fd:28:24:b4:f7:09:96:
    ee:55:8a:89:e1:e9:86:79:30:52:09:a1:24:aa:f6:
    2e:ec:d3:18:7d:2d:8e:e2:cf:5e:b1:b5:a1:b7:34:
    79:58:aa:53:20:5b:1f:72:68:56:90:3d:6a:95:3e:
    d7:2a:74:67:3c:92:f4:6f:52:92:b4:f1:c5:9c:db:
    64:5a:6a:fc:4d:03:81:de:c8:04:44:77:56:58:c5:
    49:95:bf:0c:ba:58:e5:f9:0f:15:2a:55:71:72:bc:
    04:0c:43:2f:e6:3e:de:5b:1c:f1:4f:2f:1a:11:d3:
    0d:3a:96:ba:a2:4c:3a:39:82:46:12:92:be:8e:9d:
    b3:5f:d0:88:a8:cb:af:0e:26:32:6e:63:0e:e6:90:
    36:8c:d0:a8:86:85:02:e9:dd:b1:7d:de:45:17:9c:
    e7:bb:22:b1:0f:9d:eb:2e:3d:8d:dc:d3:0c:a9:7c:
    9b:ae:84:ca:7c:3c:9a:13:af:a9:5d:e4:78:3e:a2:
    08:21
publicExponent: 3 (0x3)
privateExponent:
    00:8c:ad:1c:3b:d7:6d:ac:19:4c:aa:37:42:1e:cd:
    33:dc:fb:a8:27:8a:bf:f3:94:36:80:10:6a:1a:9f:
    a8:8e:b8:85:2d:dd:4c:05:14:44:27:6d:fa:74:1f:
    0f:02:78:5a:5d:ee:ec:8f:30:d8:10:f0:4d:f8:6d:
    ad:6c:23:77:57:db:c9:0a:a8:c5:6d:cd:fa:06:64:
    9e:e3:b1:b1:41:46:59:a6:20:36:b1:16:18:71:f9:
    74:9d:e2:10:53:73:b4:97:34:e9:cb:ce:6b:cf:78:
    50:e5:c6:e2:15:92:14:f6:f0:39:b5:7e:47:0e:29:
    e4:c6:f8:44:d3:0c:a2:f4:e0:80:b9:38:56:88:70:
    9e:e8:1d:45:ea:eb:73:b3:f7:c9:56:dd:2b:a0:2e:
    0a:9c:24:56:6a:50:02:09:e5:93:a1:ab:11:f3:2d:
    b5:a0:66:7b:42:1c:8f:a5:ea:10:86:0b:62:c2:7e:
    2e:7f:94:a0:ff:a8:93:fb:4a:23:f2:1f:08:ea:31:
    9e:85:c1:0a:06:4a:c8:35:9c:7f:3b:3b:49:d5:34:
    be:dc:d3:d4:4d:cf:a4:0e:32:bc:6c:8d:3b:65:4a:
    4b:8a:00:c8:a1:0b:56:e4:92:0b:c1:6e:54:41:89:
    4b:a1:ea:1c:12:6d:c5:ab:ef:0f:4d:aa:10:d0:2b:
    54:63
prime1:
    00:f6:45:7c:32:3b:66:f4:3f:a7:a2:0f:03:b0:1a:
    8c:09:c2:57:f7:fa:65:c7:ce:6a:01:ac:d8:16:bc:
    a4:de:5d:a7:69:2f:d8:2a:c0:36:ca:18:bc:c1:d3:
    6e:03:a9:ca:6c:2c:1c:f9:00:7c:10:69:32:c9:46:
    cb:51:ac:b1:51:c5:c2:91:23:69:55:3a:70:dd:ea:
    74:2b:c5:67:3b:aa:a9:62:f8:02:8c:5e:c7:f4:69:
    9b:ff:d6:c7:be:ab:3c:27:84:24:a1:55:48:a4:fc:
    e7:59:46:78:40:36:d2:a9:a1:18:69:82:24:b3:f2:
    18:e6:6d:98:07:86:25:2c:93
prime2:
    00:db:59:a1:11:94:cb:81:be:97:71:5d:9e:a4:36:
    48:4c:7f:d3:9c:ee:1a:71:dd:1e:89:6e:08:cc:2d:
    91:d9:5a:2d:6d:56:1f:48:db:72:ac:ea:57:45:0e:
    cf:d4:dc:53:99:c1:f8:ce:7a:bb:b8:b9:9c:92:f9:
    c7:be:7a:b2:df:69:90:b4:73:c5:a4:64:ea:a4:d3:
    47:47:d0:22:e4:7c:17:b5:49:90:5d:b3:05:98:6a:
    f5:97:04:42:ad:54:71:4e:e7:fc:e2:c8:c4:43:da:
    7b:22:f4:35:4e:10:5c:00:9a:8d:36:de:73:3d:9f:
    b0:2b:fb:cd:57:80:3b:dc:fb
exponent1:
    00:a4:2e:52:cc:27:99:f8:2a:6f:c1:5f:57:ca:bc:
    5d:5b:d6:e5:4f:fc:43:da:89:9c:01:1d:e5:64:7d:
    c3:3e:e9:1a:46:1f:e5:71:d5:79:dc:10:7d:d6:8c:
    f4:02:71:31:9d:72:bd:fb:55:a8:0a:f0:cc:86:2f:
    32:36:73:20:e1:2e:81:b6:17:9b:8e:26:f5:e9:46:
    f8:1d:2e:44:d2:71:c6:41:fa:ac:5d:94:85:4d:9b:
    bd:55:39:da:7f:1c:d2:c5:02:c3:16:38:db:18:a8:
    9a:3b:84:50:2a:cf:37:1b:c0:ba:f1:01:6d:cd:4c:
    10:99:9e:65:5a:59:6e:1d:b7
exponent2:
    00:92:3b:c0:b6:63:32:56:7f:0f:a0:e9:14:6d:79:
    85:88:55:37:bd:f4:11:a1:3e:14:5b:9e:b0:88:1e:
    61:3b:91:73:9e:39:6a:30:92:4c:73:46:e4:d8:b4:
    8a:8d:e8:37:bb:d6:a5:de:fc:7d:25:d1:13:0c:a6:
    85:29:a7:21:ea:46:60:78:4d:2e:6d:98:9c:6d:e2:
    2f:85:35:6c:98:52:ba:78:db:b5:93:cc:ae:65:9c:
    a3:ba:02:d7:1e:38:4b:89:ef:fd:ec:85:d8:2d:3c:
    52:17:4d:78:de:b5:92:ab:11:b3:79:e9:a2:29:15:
    20:1d:52:88:e5:00:27:e8:a7
coefficient:
    00:b1:63:cc:82:98:e6:3e:a2:94:f2:02:88:14:33:
    04:ad:c9:a5:55:ca:17:0e:55:94:29:54:77:38:01:
    40:56:52:d8:f9:98:da:54:95:41:78:2b:b5:65:ff:
    49:b3:2a:e5:f6:d8:14:bf:38:a8:78:c5:98:c6:30:
    7f:c2:94:a0:15:1f:26:81:b8:a3:9d:6a:ce:0a:73:
    2f:eb:6c:b5:14:a0:3d:e8:d9:22:90:a8:f1:49:92:
    31:a9:45:d6:98:c8:46:1c:de:13:15:6d:9b:fc:5b:
    09:ca:3b:f0:d2:7a:77:0f:3a:b3:fe:db:37:5b:d4:
    13:5c:8d:cb:57:f9:d6:08:81

It can be seen that for the first RSA private key, the numbers dp and c (both styled in bold) are not right. This could be potentially dangerous when signatures are involved.

Because of the Chinese Remainder Theorem, if one uses the incorrectly computed private key to sign a message and sends the resulting wrong signature directly without first verifying it, this can lead to the so-called "fault attack" (e.g., explained here).

Continuing with the example above, if we sign the message Hello World\n using the first RSA private key:

    // somehow this prime number leads to incorrect dp, which is quite weird
    OCT_fromHex(&P, "f55d1f9bde519d3d30e9a0820a0850f3a6d05efa82dcc7ef948a09834224ad6fb77ee792f53b1ee6efc0270e5e8fdd59fab40ada833df0ea69eb2f0b37d717a3fd0329280cd47525fd22970c8fd860c7be749482c42a6e16a4b5b7edf27e01214f55fd5839a11c86be6bbd8b01e5ddeef743bca59e896c1751145d4b6a9da9ed");

    OCT_fromHex(&Q,"f34e8af7a6b3b2d2906890db77f56b8c4c5a5af42bec8cacd79fc479606d85eeb641ec95aef73d0e7e24f0da9115a524d9787d573ed3a1868bff2765cc5b9e1238a7931bdd5afd51a0bd6bf93f26909fff6d93d335e6785959c14f851205ad4a8ce995e6f92e490e7a5feab2b9fcda0080bedc17fa816227f2d6034044c0c363");

    // use our choice of P and Q
    RSA_2048_KEY_PAIR(NULL,3,&priv,&pub,&P,&Q);

    print_keypair(&priv, &pub);

    printf("Signing message\n");
    OCT_jstring(&M,(char *)"Hello World\n");
    PKCS15(HASH_TYPE_RSA_2048,&M,&C);

    RSA_2048_DECRYPT(&priv,&C,&S); /* create signature in S */

    printf("Signature= ");
    OCT_output(&S);

We get a faulty signature: s = 0xc606cf94940847b48011db1297bc1798af372bb3293e901bc1e065346f9ba1be85afc92e481870b3fe45eebe75e53a95cdeada659388cafcd88ece6ebdf039b57cb83d8119cdf589fa1b61c6ee42dbd59ac015117eb17fb4b8b577c39e42dd1a3041e471d2acf0ec2d669fcb2c85ab8b11309df32ef0a0116e2e579843467e2ee24f18f5a67148e843959df1f316fc3a483ebc9b065f52750f2863ba4a2f38fb1d6f2fa22204b2a723a76de740937438321b0102ce1ffbadbab0b0fcfd0a97f5a1f9d69fe31a4633ec70c0ad552f3be8740607194ee8ee434ca770da81e0c9fbcb02ace5838a848609443535066221ad24e7ff5da1a031fecac579645604a3b6.

If an attacker obtains this signature, and knows the choice of hash algorithm as well as the message of Hello World\n, then he/she can also compute the hash value and prepare the PKCS1v1.5 structure accordingly: r = 0x0001ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff003031300d060960864801650304020105000420d2a84f4b8b650937ec8f73cd8be2c74add5a911ba64df27458ed8229da804a26

And now the attacker can factorize the modulus n by computing GCD(s^e - r, n). In Python3:

import math

# faulty signature
s = 0xc606cf94940847b48011db1297bc1798af372bb3293e901bc1e065346f9ba1be85afc92e481870b3fe45eebe75e53a95cdeada659388cafcd88ece6ebdf039b57cb83d8119cdf589fa1b61c6ee42dbd59ac015117eb17fb4b8b577c39e42dd1a3041e471d2acf0ec2d669fcb2c85ab8b11309df32ef0a0116e2e579843467e2ee24f18f5a67148e843959df1f316fc3a483ebc9b065f52750f2863ba4a2f38fb1d6f2fa22204b2a723a76de740937438321b0102ce1ffbadbab0b0fcfd0a97f5a1f9d69fe31a4633ec70c0ad552f3be8740607194ee8ee434ca770da81e0c9fbcb02ace5838a848609443535066221ad24e7ff5da1a031fecac579645604a3b6

# precomputed PKCS1v1.5 structure
r = 0x0001ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff003031300d060960864801650304020105000420d2a84f4b8b650937ec8f73cd8be2c74add5a911ba64df27458ed8229da804a26

# modulus
n = 0xe932ac92252f585b3a80a4dd76a897c8b7652952fe788f6ec8dd640587a1ee5647670a8ad4c2be0f9fa6e49c605adf77b5174230af7bd50e5d6d6d6d28ccf0a886a514cc72e51d209cc772a52ef419f6a953f3135929588ebe9b351fca61ced78f346fe00dbb6306e5c2a4c6dfc3779af85ab417371cf34d8387b9b30ae46d7a5ff5a655b8d8455f1b94ae736989d60a6f2fd5cadbffbd504c5a756a2e6bb5cecc13bca7503f6df8b52ace5c410997e98809db4dc30d943de4e812a47553dce54844a78e36401d13f77dc650619fed88d8b3926e3d8e319c80c744779ac5d6abe252896950917476ece5e8fc27d5f053d6018d91b502c4787558a002b9283da7

# now factorize n
p1 = math.gcd(pow(s,3,n)-r, n)
p2 = n // p1

print("p=",hex(max(p1,p2)))
print("q=",hex(min(p1,p2)))

Which outputs

p= 0xf55d1f9bde519d3d30e9a0820a0850f3a6d05efa82dcc7ef948a09834224ad6fb77ee792f53b1ee6efc0270e5e8fdd59fab40ada833df0ea69eb2f0b37d717a3fd0329280cd47525fd22970c8fd860c7be749482c42a6e16a4b5b7edf27e01214f55fd5839a11c86be6bbd8b01e5ddeef743bca59e896c1751145d4b6a9da9ed q= 0xf34e8af7a6b3b2d2906890db77f56b8c4c5a5af42bec8cacd79fc479606d85eeb641ec95aef73d0e7e24f0da9115a524d9787d573ed3a1868bff2765cc5b9e1238a7931bdd5afd51a0bd6bf93f26909fff6d93d335e6785959c14f851205ad4a8ce995e6f92e490e7a5feab2b9fcda0080bedc17fa816227f2d6034044c0c363

mcarrickscott commented 3 years ago

The problem here is that p=1 mod 4 and q=3 mod 4

The Milagro code only works for primes that are 3 mod 4,and the primes it generates internally are all of this form. In general 3 mod 4 primes are easier to handle,and since half of all primes are of this form,there is no loss of generality in restricting to such primes.

The specific problem is that the function invmodp(r,a,n) only calculates the correct inverse if n is odd. Now p-1 is even, but in p=3 mod 4 case (given that e is odd) we can calculate inverse(r,a,(p-1)/2) and this will be correct. But the same trick won't work if p is 1 mod 4, as in that case (p-1)/2 will still be even. It would not be hard to fix, but probably simpler just to restrict to 3 mod 4 primes

Mike

On Sun, Mar 28, 2021 at 7:02 AM 1one.w01f @.***> wrote:

Hi,

I recently run into a rather interesting problem. It appears to me that the RSA key generation in milagro might sometimes be incorrect, and I have no ideas to why that would be the case.

Here's the source code I prepared to illustrate the problem. For simplicity I just replaced the source code of test/test_rsa_2048.c with this. The build target I used was LINUX_64BIT_NIST256_RSA2048.

include

include

include "rsa_2048.h"

include "randapi.h"

void print_keypair(rsa_private_key_2048 priv, rsa_public_key_2048 pub) { printf(" priv->p = "); FF_2048_output(priv->p,FFLEN_2048/2); printf("\n"); printf(" priv->q = "); FF_2048_output(priv->q,FFLEN_2048/2); printf("\n");

printf("\n");

printf("  pub->n = ");
FF_2048_output(pub->n,FFLEN_2048);
printf("\n");

printf("\n");

printf("priv->dp = ");
FF_2048_output(priv->dp,FFLEN_2048/2);
printf("\n");
printf("priv->dq = ");
FF_2048_output(priv->dq,FFLEN_2048/2);
printf("\n");
printf(" priv->c = ");
FF_2048_output(priv->c,FFLEN_2048/2);
printf("\n");

} int main(int argc, char *argv[]) { char m[RFS_2048],ml[RFS_2048],c[RFS_2048],s[RFS_2048]; char p[RFS_2048/2], q[RFS_2048/2];

rsa_public_key_2048 pub;
rsa_private_key_2048 priv;

octet M= {0,sizeof(m),m};
octet ML= {0,sizeof(ml),ml};
octet C= {0,sizeof(c),c};
octet S= {0,sizeof(s),s};
octet P= {sizeof(p), sizeof(p), p};
octet Q= {sizeof(q), sizeof(q), q};

// somehow this prime number leads to incorrect dp, which is quite weird
OCT_fromHex(&P, "f55d1f9bde519d3d30e9a0820a0850f3a6d05efa82dcc7ef948a09834224ad6fb77ee792f53b1ee6efc0270e5e8fdd59fab40ada833df0ea69eb2f0b37d717a3fd0329280cd47525fd22970c8fd860c7be749482c42a6e16a4b5b7edf27e01214f55fd5839a11c86be6bbd8b01e5ddeef743bca59e896c1751145d4b6a9da9ed");

OCT_fromHex(&Q,"f34e8af7a6b3b2d2906890db77f56b8c4c5a5af42bec8cacd79fc479606d85eeb641ec95aef73d0e7e24f0da9115a524d9787d573ed3a1868bff2765cc5b9e1238a7931bdd5afd51a0bd6bf93f26909fff6d93d335e6785959c14f851205ad4a8ce995e6f92e490e7a5feab2b9fcda0080bedc17fa816227f2d6034044c0c363");

// use our choice of P and Q
RSA_2048_KEY_PAIR(NULL,3,&priv,&pub,&P,&Q);

print_keypair(&priv, &pub);

// ====== printf("\n===\n\n");

OCT_fromHex(&P, "db59a11194cb81be97715d9ea436484c7fd39cee1a71dd1e896e08cc2d91d95a2d6d561f48db72acea57450ecfd4dc5399c1f8ce7abbb8b99c92f9c7be7ab2df6990b473c5a464eaa4d34747d022e47c17b549905db305986af5970442ad54714ee7fce2c8c443da7b22f4354e105c009a8d36de733d9fb02bfbcd57803bdcfb");

OCT_fromHex(&Q, "f6457c323b66f43fa7a20f03b01a8c09c257f7fa65c7ce6a01acd816bca4de5da7692fd82ac036ca18bcc1d36e03a9ca6c2c1cf9007c106932c946cb51acb151c5c2912369553a70ddea742bc5673baaa962f8028c5ec7f4699bffd6c7beab3c278424a15548a4fce75946784036d2a9a118698224b3f218e66d980786252c93");

// use our choice of P and Q
RSA_2048_KEY_PAIR(NULL,3,&priv,&pub,&P,&Q);

print_keypair(&priv, &pub);

// === clean up ===

RSA_2048_PRIVATE_KEY_KILL(&priv);

OCT_clear(&M);
OCT_clear(&ML);   /* clean up afterwards */
OCT_clear(&C);

return 0;

}

Which produces the following output:

priv->p = f55d1f9bde519d3d30e9a0820a0850f3a6d05efa82dcc7ef948a09834224ad6fb77ee792f53b1ee6efc0270e5e8fdd59fab40ada833df0ea69eb2f0b37d717a3fd0329280cd47525fd22970c8fd860c7be749482c42a6e16a4b5b7edf27e01214f55fd5839a11c86be6bbd8b01e5ddeef743bca59e896c1751145d4b6a9da9ed priv->q = f34e8af7a6b3b2d2906890db77f56b8c4c5a5af42bec8cacd79fc479606d85eeb641ec95aef73d0e7e24f0da9115a524d9787d573ed3a1868bff2765cc5b9e1238a7931bdd5afd51a0bd6bf93f26909fff6d93d335e6785959c14f851205ad4a8ce995e6f92e490e7a5feab2b9fcda0080bedc17fa816227f2d6034044c0c363

pub->n = e932ac92252f585b3a80a4dd76a897c8b7652952fe788f6ec8dd640587a1ee5647670a8ad4c2be0f9fa6e49c605adf77b5174230af7bd50e5d6d6d6d28ccf0a886a514cc72e51d209cc772a52ef419f6a953f3135929588ebe9b351fca61ced78f346fe00dbb6306e5c2a4c6dfc3779af85ab417371cf34d8387b9b30ae46d7a 5ff5a655b8d8455f1b94ae736989d60a6f2fd5cadbffbd504c5a756a2e6bb5cecc13bca7503f6df8b52ace5c410997e98809db4dc30d943de4e812a47553dce54844a78e36401d13f77dc650619fed88d8b3926e3d8e319c80c744779ac5d6abe252896950917476ece5e8fc27d5f053d6018d91b502c4787558a002b9283da7

priv->dp = 4c8b6ace1ba4747563b3d9f6c29e01fb968c96e116707fb4556b811f39b047aac0d7fc303650ff6a0a14e969656094a08dab8231a71c76613ae1063d87aea343b8a2146fc5b850693e1d7167ab97e063b8c383462e8394f47ff0fdb4c6d4e5872c49c2b459841670b808f68173248883f16d95c698b0dd39a5e167e840047571 priv->dq = a2345ca519cd21e1b59b0b3cfaa39d0832e6e74d729db31de5152da6404903f479814863c9fa28b45418a091b60e6e1890fafe3a29e26baf07ff6f9932e7beb6d06fb767e8e7538bc07e47fb7f6f0b1554f3b7e223eefae63bd6350361591e31b34663ef50c98609a6ea9c7726a89155ab29e80ffc56416ff73957802dd5d797 priv->c = 6f1e5e6d113bffba6e9fe60cbfd0b959f0b78fb8f71db4ab4f63147abec85beb2a982acde258672046843ce3b9f93a33ff1b25602762dfd8dbddf36e3b9815a1bf14a9dbba3d28df3dfb830fb976662cc1b41026207aa16686f49c23f93f1312ba29ef76a0c13fb03e727247b632dda5a06bf6d385da9831af4ec18d1d23df95

===

priv->p = db59a11194cb81be97715d9ea436484c7fd39cee1a71dd1e896e08cc2d91d95a2d6d561f48db72acea57450ecfd4dc5399c1f8ce7abbb8b99c92f9c7be7ab2df6990b473c5a464eaa4d34747d022e47c17b549905db305986af5970442ad54714ee7fce2c8c443da7b22f4354e105c009a8d36de733d9fb02bfbcd57803bdcfb priv->q = f6457c323b66f43fa7a20f03b01a8c09c257f7fa65c7ce6a01acd816bca4de5da7692fd82ac036ca18bcc1d36e03a9ca6c2c1cf9007c106932c946cb51acb151c5c2912369553a70ddea742bc5673baaa962f8028c5ec7f4699bffd6c7beab3c278424a15548a4fce75946784036d2a9a118698224b3f218e66d980786252c93

pub->n = d303aa59c3248225f2ff52e32e33cdcb797c3b501fed5e51c0189f27ef7cd614c7c4cbf2079e663b24f7ae2e9683b4878ce662d6c944196874f4a48422353303c9ad8ffd2824b4f70996ee558a89e1e98679305209a124aaf62eecd3187d2d8ee2cf5eb1b5a1b7347958aa53205b1f726856903d6a953ed72a74673c92f46f52 92b4f1c59cdb645a6afc4d0381dec80444775658c54995bf0cba58e5f90f152a557172bc040c432fe63ede5b1cf14f2f1a11d30d3a96baa24c3a3982461292be8e9db35fd088a8cbaf0e26326e630ee690368cd0a8868502e9ddb17dde45179ce7bb22b10f9deb2e3d8ddcd30ca97c9bae84ca7c3c9a13afa95de4783ea20821

priv->dp = 923bc0b66332567f0fa0e9146d7985885537bdf411a13e145b9eb0881e613b91739e396a30924c7346e4d8b48a8de837bbd6a5defc7d25d1130ca68529a721ea4660784d2e6d989c6de22f85356c9852ba78dbb593ccae659ca3ba02d71e384b89effdec85d82d3c52174d78deb592ab11b379e9a22915201d5288e50027e8a7** priv->dq = a42e52cc2799f82a6fc15f57cabc5d5bd6e54ffc43da899c011de5647dc33ee91a461fe571d579dc107dd68cf40271319d72bdfb55a80af0cc862f32367320e12e81b6179b8e26f5e946f81d2e44d271c641faac5d94854d9bbd5539da7f1cd2c502c31638db18a89a3b84502acf371bc0baf1016dcd4c10999e655a596e1db7 priv->c = b163cc8298e63ea294f20288143304adc9a555ca170e55942954773801405652d8f998da549541782bb565ff49b32ae5f6d814bf38a878c598c6307fc294a0151f2681b8a39d6ace0a732feb6cb514a03de8d92290a8f1499231a945d698c8461cde13156d9bfc5b09ca3bf0d27a770f3ab3fedb375bd4135c8dcb57f9d60881

The primes P and Q were all copied from RSA private keys generated by OpenSSL. If we use OpenSSL to check the numbers of the 2 private keys:

$ openssl rsa -in privkey.pem -noout -text RSA Private-Key: (2048 bit, 2 primes) modulus: 00:e9:32:ac:92:25:2f:58:5b:3a:80:a4:dd:76:a8: 97:c8:b7:65:29:52:fe:78:8f:6e:c8:dd:64:05:87: a1:ee:56:47:67:0a:8a:d4:c2:be:0f:9f:a6:e4:9c: 60:5a:df:77:b5:17:42:30:af:7b:d5:0e:5d:6d:6d: 6d:28:cc:f0:a8:86:a5:14:cc:72:e5:1d:20:9c:c7: 72:a5:2e:f4:19:f6:a9:53:f3:13:59:29:58:8e:be: 9b:35:1f:ca:61:ce:d7:8f:34:6f:e0:0d:bb:63:06: e5:c2:a4:c6:df:c3:77:9a:f8:5a:b4:17:37:1c:f3: 4d:83:87:b9:b3:0a:e4:6d:7a:5f:f5:a6:55:b8:d8: 45:5f:1b:94:ae:73:69:89:d6:0a:6f:2f:d5:ca:db: ff:bd:50:4c:5a:75:6a:2e:6b:b5:ce:cc:13:bc:a7: 50:3f:6d:f8:b5:2a:ce:5c:41:09:97:e9:88:09:db: 4d:c3:0d:94:3d:e4:e8:12:a4:75:53:dc:e5:48:44: a7:8e:36:40:1d:13:f7:7d:c6:50:61:9f:ed:88:d8: b3:92:6e:3d:8e:31:9c:80:c7:44:77:9a:c5:d6:ab: e2:52:89:69:50:91:74:76:ec:e5:e8:fc:27:d5:f0: 53:d6:01:8d:91:b5:02:c4:78:75:58:a0:02:b9:28: 3d:a7 publicExponent: 3 (0x3) privateExponent: 00:9b:77:1d:b6:c3:74:e5:92:27:00:6d:e8:f9:c5: ba:85:cf:98:c6:37:54:50:5f:9f:30:93:98:03:af: c1:49:8e:da:44:b1:b1:e3:2c:7e:b5:15:19:ed:bd: 95:91:ea:4f:ce:0f:81:75:ca:52:8e:09:93:9e:48: f3:70:88:a0:70:59:c3:63:32:f7:43:68:c0:68:84: f7:18:c9:f8:11:4f:1b:8d:4c:b7:90:c6:3b:09:d4: 67:78:bf:dc:41:34:8f:b4:cd:9f:ea:b3:d2:42:04: 99:2c:6d:d9:ea:82:4f:bc:a5:91:cd:64:cf:68:a2: 33:ad:05:26:77:5c:98:48:fa:fa:31:52:81:77:e1: f8:df:91:81:a8:b9:45:08:11:06:fd:58:bd:3d:73: 79:9b:22:95:75:c4:f3:b2:91:01:a0:3e:e1:f0:54: 72:b3:61:57:84:d9:24:4c:e0:ed:63:9c:77:e8:e2: 12:ab:52:ab:dd:f4:a9:28:22:4b:6b:6f:74:b7:11: 47:86:dd:60:71:bd:91:13:d7:87:0c:6b:52:c0:bc: 8b:9c:10:2c:fe:32:1d:ac:35:7e:03:0e:d6:c5:80: 04:0c:a4:1c:13:d6:b4:96:78:11:80:7e:f2:a2:25: 98:3e:a9:f8:8d:67:fa:a4:26:20:f4:2a:4f:5b:db: e0:3b prime1: 00:f5:5d:1f:9b:de:51:9d:3d:30:e9:a0:82:0a:08: 50:f3:a6:d0:5e:fa:82:dc:c7:ef:94:8a:09:83:42: 24:ad:6f:b7:7e:e7:92:f5:3b:1e:e6:ef:c0:27:0e: 5e:8f:dd:59:fa:b4:0a:da:83:3d:f0:ea:69:eb:2f: 0b:37:d7:17:a3:fd:03:29:28:0c:d4:75:25:fd:22: 97:0c:8f:d8:60:c7:be:74:94:82:c4:2a:6e:16:a4: b5:b7:ed:f2:7e:01:21:4f:55:fd:58:39:a1:1c:86: be:6b:bd:8b:01:e5:dd:ee:f7:43:bc:a5:9e:89:6c: 17:51:14:5d:4b:6a:9d:a9:ed prime2: 00:f3:4e:8a:f7:a6:b3:b2:d2:90:68:90:db:77:f5: 6b:8c:4c:5a:5a:f4:2b:ec:8c:ac:d7:9f:c4:79:60: 6d:85:ee:b6:41:ec:95:ae:f7:3d:0e:7e:24:f0:da: 91:15:a5:24:d9:78:7d:57:3e:d3:a1:86:8b:ff:27: 65:cc:5b:9e:12:38:a7:93:1b:dd:5a:fd:51:a0:bd: 6b:f9:3f:26:90:9f:ff:6d:93:d3:35:e6:78:59:59: c1:4f:85:12:05:ad:4a:8c:e9:95:e6:f9:2e:49:0e: 7a:5f:ea:b2:b9:fc:da:00:80:be:dc:17:fa:81:62: 27:f2:d6:03:40:44:c0:c3:63 exponent1: 00:a3:93:6a:67:e9:8b:be:28:cb:46:6b:01:5c:05: 8b:4d:19:e0:3f:51:ac:93:2f:f5:0d:b1:5b:ac:d6: c3:1e:4a:7a:54:9a:61:f8:d2:14:99:f5:2a:c4:b4: 3f:0a:93:91:51:cd:5c:91:ac:d3:f5:f1:9b:f2:1f: 5c:cf:e4:ba:6d:53:57:70:c5:5d:e2:f8:c3:fe:17: 0f:5d:b5:3a:eb:2f:d4:4d:b8:57:2d:71:9e:b9:c3: 23:cf:f3:f6:fe:ab:6b:8a:39:53:90:26:6b:68:59: d4:47:d3:b2:01:43:e9:49:fa:2d:28:6e:69:b0:f2: ba:36:0d:93:87:9c:69:1b:f3 exponent2: 00:a2:34:5c:a5:19:cd:21:e1:b5:9b:0b:3c:fa:a3: 9d:08:32:e6:e7:4d:72:9d:b3:1d:e5:15:2d:a6:40: 49:03:f4:79:81:48:63:c9:fa:28:b4:54:18:a0:91: b6:0e:6e:18:90:fa:fe:3a:29:e2:6b:af:07:ff:6f: 99:32:e7:be:b6:d0:6f:b7:67:e8:e7:53:8b:c0:7e: 47:fb:7f:6f:0b:15:54:f3:b7:e2:23:ee:fa:e6:3b: d6:35:03:61:59:1e:31:b3:46:63:ef:50:c9:86:09: a6:ea:9c:77:26:a8:91:55:ab:29:e8:0f:fc:56:41: 6f:f7:39:57:80:2d:d5:d7:97 coefficient: 00:85:4e:43:ad:27:2d:f5:81:12:c9:84:ca:73:eb: bf:9a:57:8a:56:53:ff:eb:79:dc:43:a4:20:27:b5: 5a:69:27:d7:74:65:c4:2d:83:e9:d8:ee:9e:7c:bc: 91:6f:ed:76:2a:7b:90:24:a5:bd:ee:8a:f3:1d:38: d5:c1:84:0d:80:78:13:9a:3c:b0:04:7c:c7:36:cf: 22:4d:99:25:f6:1a:42:fd:0f:48:87:09:e7:24:a5: c6:f3:21:40:a0:5f:22:e4:9b:37:2d:f7:f4:39:c6: ad:86:07:89:6b:d6:b3:8a:d5:9e:bd:be:1b:8d:e9: 32:54:35:25:7e:4c:a4:b0:9d

$ openssl rsa -in privkey.pem -noout -text RSA Private-Key: (2048 bit, 2 primes) modulus: 00:d3:03:aa:59:c3:24:82:25:f2:ff:52:e3:2e:33: cd:cb:79:7c:3b:50:1f:ed:5e:51:c0:18:9f:27:ef: 7c:d6:14:c7:c4:cb:f2:07:9e:66:3b:24:f7:ae:2e: 96:83:b4:87:8c:e6:62:d6:c9:44:19:68:74:f4:a4: 84:22:35:33:03:c9:ad:8f:fd:28:24:b4:f7:09:96: ee:55:8a:89:e1:e9:86:79:30:52:09:a1:24:aa:f6: 2e:ec:d3:18:7d:2d:8e:e2:cf:5e:b1:b5:a1:b7:34: 79:58:aa:53:20:5b:1f:72:68:56:90:3d:6a:95:3e: d7:2a:74:67:3c:92:f4:6f:52:92:b4:f1:c5:9c:db: 64:5a:6a:fc:4d:03:81:de:c8:04:44:77:56:58:c5: 49:95:bf:0c:ba:58:e5:f9:0f:15:2a:55:71:72:bc: 04:0c:43:2f:e6:3e:de:5b:1c:f1:4f:2f:1a:11:d3: 0d:3a:96:ba:a2:4c:3a:39:82:46:12:92:be:8e:9d: b3:5f:d0:88:a8:cb:af:0e:26:32:6e:63:0e:e6:90: 36:8c:d0:a8:86:85:02:e9:dd:b1:7d:de:45:17:9c: e7:bb:22:b1:0f:9d:eb:2e:3d:8d:dc:d3:0c:a9:7c: 9b:ae:84:ca:7c:3c:9a:13:af:a9:5d:e4:78:3e:a2: 08:21 publicExponent: 3 (0x3) privateExponent: 00:8c:ad:1c:3b:d7:6d:ac:19:4c:aa:37:42:1e:cd: 33:dc:fb:a8:27:8a:bf:f3:94:36:80:10:6a:1a:9f: a8:8e:b8:85:2d:dd:4c:05:14:44:27:6d:fa:74:1f: 0f:02:78:5a:5d:ee:ec:8f:30:d8:10:f0:4d:f8:6d: ad:6c:23:77:57:db:c9:0a:a8:c5:6d:cd:fa:06:64: 9e:e3:b1:b1:41:46:59:a6:20:36:b1:16:18:71:f9: 74:9d:e2:10:53:73:b4:97:34:e9:cb:ce:6b:cf:78: 50:e5:c6:e2:15:92:14:f6:f0:39:b5:7e:47:0e:29: e4:c6:f8:44:d3:0c:a2:f4:e0:80:b9:38:56:88:70: 9e:e8:1d:45:ea:eb:73:b3:f7:c9:56:dd:2b:a0:2e: 0a:9c:24:56:6a:50:02:09:e5:93:a1:ab:11:f3:2d: b5:a0:66:7b:42:1c:8f:a5:ea:10:86:0b:62:c2:7e: 2e:7f:94:a0:ff:a8:93:fb:4a:23:f2:1f:08:ea:31: 9e:85:c1:0a:06:4a:c8:35:9c:7f:3b:3b:49:d5:34: be:dc:d3:d4:4d:cf:a4:0e:32:bc:6c:8d:3b:65:4a: 4b:8a:00:c8:a1:0b:56:e4:92:0b:c1:6e:54:41:89: 4b:a1:ea:1c:12:6d:c5:ab:ef:0f:4d:aa:10:d0:2b: 54:63 prime1: 00:f6:45:7c:32:3b:66:f4:3f:a7:a2:0f:03:b0:1a: 8c:09:c2:57:f7:fa:65:c7:ce:6a:01:ac:d8:16:bc: a4:de:5d:a7:69:2f:d8:2a:c0:36:ca:18:bc:c1:d3: 6e:03:a9:ca:6c:2c:1c:f9:00:7c:10:69:32:c9:46: cb:51:ac:b1:51:c5:c2:91:23:69:55:3a:70:dd:ea: 74:2b:c5:67:3b:aa:a9:62:f8:02:8c:5e:c7:f4:69: 9b:ff:d6:c7:be:ab:3c:27:84:24:a1:55:48:a4:fc: e7:59:46:78:40:36:d2:a9:a1:18:69:82:24:b3:f2: 18:e6:6d:98:07:86:25:2c:93 prime2: 00:db:59:a1:11:94:cb:81:be:97:71:5d:9e:a4:36: 48:4c:7f:d3:9c:ee:1a:71:dd:1e:89:6e:08:cc:2d: 91:d9:5a:2d:6d:56:1f:48:db:72:ac:ea:57:45:0e: cf:d4:dc:53:99:c1:f8:ce:7a:bb:b8:b9:9c:92:f9: c7:be:7a:b2:df:69:90:b4:73:c5:a4:64:ea:a4:d3: 47:47:d0:22:e4:7c:17:b5:49:90:5d:b3:05:98:6a: f5:97:04:42:ad:54:71:4e:e7:fc:e2:c8:c4:43:da: 7b:22:f4:35:4e:10:5c:00:9a:8d:36:de:73:3d:9f: b0:2b:fb:cd:57:80:3b:dc:fb exponent1: 00:a4:2e:52:cc:27:99:f8:2a:6f:c1:5f:57:ca:bc: 5d:5b:d6:e5:4f:fc:43:da:89:9c:01:1d:e5:64:7d: c3:3e:e9:1a:46:1f:e5:71:d5:79:dc:10:7d:d6:8c: f4:02:71:31:9d:72:bd:fb:55:a8:0a:f0:cc:86:2f: 32:36:73:20:e1:2e:81:b6:17:9b:8e:26:f5:e9:46: f8:1d:2e:44:d2:71:c6:41:fa:ac:5d:94:85:4d:9b: bd:55:39:da:7f:1c:d2:c5:02:c3:16:38:db:18:a8: 9a:3b:84:50:2a:cf:37:1b:c0:ba:f1:01:6d:cd:4c: 10:99:9e:65:5a:59:6e:1d:b7 exponent2: 00:92:3b:c0:b6:63:32:56:7f:0f:a0:e9:14:6d:79: 85:88:55:37:bd:f4:11:a1:3e:14:5b:9e:b0:88:1e: 61:3b:91:73:9e:39:6a:30:92:4c:73:46:e4:d8:b4: 8a:8d:e8:37:bb:d6:a5:de:fc:7d:25:d1:13:0c:a6: 85:29:a7:21:ea:46:60:78:4d:2e:6d:98:9c:6d:e2: 2f:85:35:6c:98:52:ba:78:db:b5:93:cc:ae:65:9c: a3:ba:02:d7:1e:38:4b:89:ef:fd:ec:85:d8:2d:3c: 52:17:4d:78:de:b5:92:ab:11:b3:79:e9:a2:29:15: 20:1d:52:88:e5:00:27:e8:a7 coefficient: 00:b1:63:cc:82:98:e6:3e:a2:94:f2:02:88:14:33: 04:ad:c9:a5:55:ca:17:0e:55:94:29:54:77:38:01: 40:56:52:d8:f9:98:da:54:95:41:78:2b:b5:65:ff: 49:b3:2a:e5:f6:d8:14:bf:38:a8:78:c5:98:c6:30: 7f:c2:94:a0:15:1f:26:81:b8:a3:9d:6a:ce:0a:73: 2f:eb:6c:b5:14:a0:3d:e8:d9:22:90:a8:f1:49:92: 31:a9:45:d6:98:c8:46:1c:de:13:15:6d:9b:fc:5b: 09:ca:3b:f0:d2:7a:77:0f:3a:b3:fe:db:37:5b:d4: 13:5c:8d:cb:57:f9:d6:08:81

It can be seen that for the first RSA private key, the numbers dp and c (both styled in bold) are not right. This could be potentially dangerous when signatures are involved.

Because of the Chinese Remainder Theorem, if one uses the incorrectly computed private key to sign a message and sends the resulting wrong signature directly without first verifying it, this can lead to the so-called "fault attack" (e.g., explained here https://www.cryptologie.net/article/371/fault-attacks-on-rsas-signatures/ ).

Continuing with the example above, if we sign the message Hello World\n using the first RSA private key:

// somehow this prime number leads to incorrect dp, which is quite weird
OCT_fromHex(&P, "f55d1f9bde519d3d30e9a0820a0850f3a6d05efa82dcc7ef948a09834224ad6fb77ee792f53b1ee6efc0270e5e8fdd59fab40ada833df0ea69eb2f0b37d717a3fd0329280cd47525fd22970c8fd860c7be749482c42a6e16a4b5b7edf27e01214f55fd5839a11c86be6bbd8b01e5ddeef743bca59e896c1751145d4b6a9da9ed");

OCT_fromHex(&Q,"f34e8af7a6b3b2d2906890db77f56b8c4c5a5af42bec8cacd79fc479606d85eeb641ec95aef73d0e7e24f0da9115a524d9787d573ed3a1868bff2765cc5b9e1238a7931bdd5afd51a0bd6bf93f26909fff6d93d335e6785959c14f851205ad4a8ce995e6f92e490e7a5feab2b9fcda0080bedc17fa816227f2d6034044c0c363");

// use our choice of P and Q
RSA_2048_KEY_PAIR(NULL,3,&priv,&pub,&P,&Q);

print_keypair(&priv, &pub);

printf("Signing message\n");
OCT_jstring(&M,(char *)"Hello World\n");
PKCS15(HASH_TYPE_RSA_2048,&M,&C);

RSA_2048_DECRYPT(&priv,&C,&S); /* create signature in S */

printf("Signature= ");
OCT_output(&S);

We get a faulty signature: s = 0xc606cf94940847b48011db1297bc1798af372bb3293e901bc1e065346f9ba1be85afc92e481870b3fe45eebe75e53a95cdeada659388cafcd88ece6ebdf039b57cb83d8119cdf589fa1b61c6ee42dbd59ac015117eb17fb4b8b577c39e42dd1a3041e471d2acf0ec2d669fcb2c85ab8b11309df32ef0a0116e2e579843467e2ee24f18f5a67148e843959df1f316fc3a483ebc9b065f52750f2863ba4a2f38fb1d6f2fa22204b2a723a76de740937438321b0102ce1ffbadbab0b0fcfd0a97f5a1f9d69fe31a4633ec70c0ad552f3be8740607194ee8ee434ca770da81e0c9fbcb02ace5838a848609443535066221ad24e7ff5da1a031fecac579645604a3b6 .

If an attacker obtains this signature, and knows the choice of hash algorithm as well as the message of Hello World\n, then he/she can also compute the hash value and prepare the PKCS1v1.5 structure accordingly: r

0x0001ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff003031300d060960864801650304020105000420d2a84f4b8b650937ec8f73cd8be2c74add5a911ba64df27458ed8229da804a26

And now the attacker can factorize the modulus n by computing GCD(s^e - r, n). In Python3:

import math

faulty signatures = 0xc606cf94940847b48011db1297bc1798af372bb3293e901bc1e065346f9ba1be85afc92e481870b3fe45eebe75e53a95cdeada659388cafcd88ece6ebdf039b57cb83d8119cdf589fa1b61c6ee42dbd59ac015117eb17fb4b8b577c39e42dd1a3041e471d2acf0ec2d669fcb2c85ab8b11309df32ef0a0116e2e579843467e2ee24f18f5a67148e843959df1f316fc3a483ebc9b065f52750f2863ba4a2f38fb1d6f2fa22204b2a723a76de740937438321b0102ce1ffbadbab0b0fcfd0a97f5a1f9d69fe31a4633ec70c0ad552f3be8740607194ee8ee434ca770da81e0c9fbcb02ace5838a848609443535066221ad24e7ff5da1a031fecac579645604a3b6

precomputed PKCS1v1.5 structurer = 0x0001ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff003031300d060960864801650304020105000420d2a84f4b8b650937ec8f73cd8be2c74add5a911ba64df27458ed8229da804a26

modulusn = 0xf55d1f9bde519d3d30e9a0820a0850f3a6d05efa82dcc7ef948a09834224ad6fb77ee792f53b1ee6efc0270e5e8fdd59fab40ada833df0ea69eb2f0b37d717a3fd0329280cd47525fd22970c8fd860c7be749482c42a6e16a4b5b7edf27e01214f55fd5839a11c86be6bbd8b01e5ddeef743bca59e896c1751145d4b6a9da9ed * 0xf34e8af7a6b3b2d2906890db77f56b8c4c5a5af42bec8cacd79fc479606d85eeb641ec95aef73d0e7e24f0da9115a524d9787d573ed3a1868bff2765cc5b9e1238a7931bdd5afd51a0bd6bf93f26909fff6d93d335e6785959c14f851205ad4a8ce995e6f92e490e7a5feab2b9fcda0080bedc17fa816227f2d6034044c0c363

now factorize np1 = math.gcd(pow(s,3,n)-r, n)p2 = n // p1

print("p=",hex(max(p1,p2)))print("q=",hex(min(p1,p2)))

Which outputs

p= 0xf55d1f9bde519d3d30e9a0820a0850f3a6d05efa82dcc7ef948a09834224ad6fb77ee792f53b1ee6efc0270e5e8fdd59fab40ada833df0ea69eb2f0b37d717a3fd0329280cd47525fd22970c8fd860c7be749482c42a6e16a4b5b7edf27e01214f55fd5839a11c86be6bbd8b01e5ddeef743bca59e896c1751145d4b6a9da9ed q= 0xf34e8af7a6b3b2d2906890db77f56b8c4c5a5af42bec8cacd79fc479606d85eeb641ec95aef73d0e7e24f0da9115a524d9787d573ed3a1868bff2765cc5b9e1238a7931bdd5afd51a0bd6bf93f26909fff6d93d335e6785959c14f851205ad4a8ce995e6f92e490e7a5feab2b9fcda0080bedc17fa816227f2d6034044c0c363

— You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub https://github.com/apache/incubator-milagro-crypto-c/issues/90, or unsubscribe https://github.com/notifications/unsubscribe-auth/AAU3ZDS5XX6G5MYXVIHHFA3TF3A7LANCNFSM4Z5WGOQA .

1one-w01f commented 3 years ago

Thanks for the explanation, that is rather interesting. I didn't think of the reason why when I first posted the question, but it makes sense to me now.

If one plans to stick with milagro alone then it's probably going to be fine, but if one needs to integrate/interoperate with other systems/crypto libraries as I did in my case, then this might not be ideal, because the API call doesn't seem to block/warn about 1 mod 4 primes, which might increase the chance of fault attack due to oversight in API usage, as explained in my original question.

mcarrickscott commented 3 years ago

You make a fair point.

A particular solution in the context of interoperation with OpenSSL would be to copy p,q,dp, dq and c directly into the Milagro rsa_private_key structure. Then everything should work fine (and even a little faster)

(But note that since c= 1/p mod q in Milagro and 1/q mod p in OpenSSL, p and q (and dp and dq) would need to be swapped.)

Mike

On Sun, Mar 28, 2021 at 4:19 PM 1one.w01f @.***> wrote:

Thanks for the explanation, that is rather interesting. I didn't think of the reason why when I first posted the question, but it makes sense to me now.

If one plans to stick with milagro alone then it's probably going to be fine, but if one needs to integrate/interoperate with other systems/crypto libraries as I did in my case, then this might not be ideal, because the API call doesn't seem to block/warn about 1 mod 4 primes, which might increase the chance of fault attack due to oversight in API usage, as explained in my original question.

— You are receiving this because you commented. Reply to this email directly, view it on GitHub https://github.com/apache/incubator-milagro-crypto-c/issues/90#issuecomment-808910920, or unsubscribe https://github.com/notifications/unsubscribe-auth/AAU3ZDTHZ6TMHXB2TRAYPKTTF5CGLANCNFSM4Z5WGOQA .

giorgiozoppi commented 1 year ago

@mcarrickscott @1one-w01f can we close this? Is it a bug?