[Cryptography] 1023 nails in the coffin of 1024 RSA...

Viktor Dukhovni cryptography at dukhovni.org
Sat Oct 4 16:20:20 EDT 2014


On Sat, Oct 04, 2014 at 12:08:42PM -0700, ianG wrote:

> He claimed:
> 
>     The bug originates in this lines of rsa_gen.c:
> 
>     117 bitsp=(bits+1)/2;
>     118 bitsq=bits-bitsp;
> 
>     the main problem being that the rounding of 1025 isn't downwards but
> upwards, resulting in bitsp= 513 and bitsq=511, which, supposedly, later
> on the code and due to compiler optimizations, causes the bug.

This is plainly wrong for 1024-bit moduli, in the example below, p and q
are respectively:

    00d71a4e9865d1cdcdd8e6e4cbc5309971e52c121efee4a080a7d11af6fa7096e18470cbef6034c096b4170133d9edb45bd90a2906b34f58bf66278ed1dba8ffad
    00d26e1e81fde36b9daec7acbee3279b70d00fe771b65dbf8786f2f006621d4b517e5970801b517be34b7c483678ac99cfa9b22b075bde85a6d069dce9ef53a3f9

both are consist of 128 nibbles after the initial 00 to ensure that
the number is unsigned, the high nibble of both is "d", so both
are 512 bit numbers.

    $ openssl genrsa 1024 2>/dev/null | openssl rsa -text
    Private-Key: (1024 bit)
    modulus:
	00:b0:d0:1b:69:17:cd:68:1f:f9:d1:9e:82:a0:eb:
	9f:18:76:0d:32:53:5d:2f:e9:44:4f:1e:d7:03:02:
	13:7e:42:94:c5:2d:03:83:1f:07:82:50:07:f8:d3:
	cb:91:6d:62:9a:a5:9a:22:1f:41:f6:37:f5:f1:07:
	8a:b6:3c:28:a4:cc:b6:61:31:da:c7:00:a4:f7:1b:
	db:ef:f6:c2:89:b0:8a:53:ba:bc:db:f0:50:f8:18:
	c3:ac:42:7b:e0:69:63:e3:f1:88:b3:43:b4:56:ab:
	11:7a:ec:27:5a:ee:18:0a:0c:57:ed:e4:e6:d6:a6:
	60:5d:04:e7:ed:aa:42:d6:45
    publicExponent: 65537 (0x10001)
    privateExponent:
	00:a4:8e:6a:94:5a:a4:bf:1d:d3:61:76:06:d9:41:
	b1:66:10:a8:a3:87:d6:98:ba:9e:ea:8c:27:4c:13:
	68:94:ff:de:79:cc:35:12:99:94:61:81:9e:89:c4:
	84:17:2b:18:b4:19:1f:e4:55:f7:0b:f2:75:21:08:
	05:df:29:0a:21:1a:a2:b0:24:0e:9b:2b:31:97:34:
	be:22:9e:e2:73:5e:c5:ce:3f:e8:99:6f:15:68:13:
	fd:e7:d7:ef:18:dd:dd:6e:0f:26:f9:86:9a:f1:a1:
	6d:aa:89:59:29:20:e2:26:0d:28:15:fb:4f:e7:33:
	86:ea:b6:5c:86:05:e8:cd:41
    prime1:
	00:d7:1a:4e:98:65:d1:cd:cd:d8:e6:e4:cb:c5:30:
	99:71:e5:2c:12:1e:fe:e4:a0:80:a7:d1:1a:f6:fa:
	70:96:e1:84:70:cb:ef:60:34:c0:96:b4:17:01:33:
	d9:ed:b4:5b:d9:0a:29:06:b3:4f:58:bf:66:27:8e:
	d1:db:a8:ff:ad
    prime2:
	00:d2:6e:1e:81:fd:e3:6b:9d:ae:c7:ac:be:e3:27:
	9b:70:d0:0f:e7:71:b6:5d:bf:87:86:f2:f0:06:62:
	1d:4b:51:7e:59:70:80:1b:51:7b:e3:4b:7c:48:36:
	78:ac:99:cf:a9:b2:2b:07:5b:de:85:a6:d0:69:dc:
	e9:ef:53:a3:f9
    exponent1:
	7d:d8:30:3f:4c:e2:90:2b:6c:48:b9:76:d5:e8:f6:
	fd:01:7c:e5:25:29:2f:0d:0f:f8:1e:88:4e:12:7b:
	28:6a:cc:17:49:d8:c4:4a:58:9a:52:c6:5a:b7:c1:
	3a:26:98:cd:c3:f9:f8:a7:93:36:72:d4:0b:34:ad:
	66:7b:db:09
    exponent2:
	1e:2b:53:8c:67:8e:17:7b:bf:f7:38:b9:15:70:34:
	44:f4:4f:93:6b:26:2e:42:ab:77:99:94:f8:15:51:
	05:df:65:32:05:83:18:67:92:4f:80:1f:0d:6b:61:
	d9:bd:23:9c:bc:c2:96:87:81:5b:c0:12:d9:5a:a6:
	df:7d:2a:61
    coefficient:
	35:76:a3:29:95:ef:ee:98:a0:0e:3a:2e:5c:41:c0:
	0f:9c:4d:48:f0:92:06:72:d9:47:36:8a:9f:89:41:
	0f:4f:27:a7:c3:22:f7:ea:22:44:94:a8:20:84:73:
	f0:f9:a9:3b:63:70:c8:b7:d8:21:9b:64:65:67:92:
	29:09:71:91
    writing RSA key
    -----BEGIN RSA PRIVATE KEY-----
    MIICXAIBAAKBgQCw0BtpF81oH/nRnoKg658Ydg0yU10v6URPHtcDAhN+QpTFLQOD
    HweCUAf408uRbWKapZoiH0H2N/XxB4q2PCikzLZhMdrHAKT3G9vv9sKJsIpTurzb
    8FD4GMOsQnvgaWPj8YizQ7RWqxF67Cda7hgKDFft5ObWpmBdBOftqkLWRQIDAQAB
    AoGBAKSOapRapL8d02F2BtlBsWYQqKOH1pi6nuqMJ0wTaJT/3nnMNRKZlGGBnonE
    hBcrGLQZH+RV9wvydSEIBd8pCiEaorAkDpsrMZc0viKe4nNexc4/6JlvFWgT/efX
    7xjd3W4PJvmGmvGhbaqJWSkg4iYNKBX7T+czhuq2XIYF6M1BAkEA1xpOmGXRzc3Y
    5uTLxTCZceUsEh7+5KCAp9Ea9vpwluGEcMvvYDTAlrQXATPZ7bRb2QopBrNPWL9m
    J47R26j/rQJBANJuHoH942udrsesvuMnm3DQD+dxtl2/h4by8AZiHUtRfllwgBtR
    e+NLfEg2eKyZz6myKwdb3oWm0Gnc6e9To/kCQH3YMD9M4pArbEi5dtXo9v0BfOUl
    KS8ND/geiE4SeyhqzBdJ2MRKWJpSxlq3wTommM3D+finkzZy1As0rWZ72wkCQB4r
    U4xnjhd7v/c4uRVwNET0T5NrJi5Cq3eZlPgVUQXfZTIFgxhnkk+AHw1rYdm9I5y8
    wpaHgVvAEtlapt99KmECQDV2oymV7+6YoA46LlxBwA+cTUjwkgZy2Uc2ip+JQQ9P
    J6fDIvfqIkSUqCCEc/D5qTtjcMi32CGbZGVnkikJcZE=
    -----END RSA PRIVATE KEY-----

It is also far from clear how having p/q ~ 4 rather than p/q ~ 1
would help the attacker.  IIRC on the contrary having p and q too
close to each other (sharing too many top bits) is known to be
problematic.

> He is neither going to report it to the developers, nor publish
> anything.

I have a simple proof of the Goldbach conjecture and the Riemann
hypothesis.  I like his approach, so I'm not going to publish
either.

-- 
	Viktor.


More information about the cryptography mailing list