Note: You are viewing this blog post without the intended style information, which may result in formatting issues.
Sometimes hacking requires doing things that, while possible to do with some algorithm, simply aren’t supported by any existing implementation. Usually for good reason. A good example of this that I’ve run into in the past is needing to initialize a hash algorithm with a specific state. There’s really not any reason to do this unless you’re trying to execute a length extension attack, and with the exception of HashPump (which was written specifically for that use case) I’m not aware of any library that supports it. I recently ran into this with problem with RSA.
A Quick Review of RSA Keys
RSA private keys consist of:
- n, the composite modulus
- e, the public exponent
- d, the private exponent
- some other values that can be ignored for now
In order to find d, φ(n) must first be computed by subtracting one from each of the prime factors of n and taking their product. Next d is calculated using the extended Euclidean algorithm to find the modular multiplicative inverse of e with respect to φ(n), such that e⋅φ(n) mod ≡ 1 is satisfied. For the math to work out, e cannot share any factors with φ(n). The security of RSA relies on it being infeasible to find d without the prime factors of n. In practice, keys are normally generated by picking two random prime numbers of similar length, using 65537 for e, and computing everything else from there.
Readers already familiar with RSA may be wondering why I haven’t mentioned the customary names for the primes factors of n — p and q. That is because RSA works just fine with more than two primes. There was an offhand reference to this in the original RSA patent:
In alternative embodiments, the present invention may use a modulus n which is a product of three or more primes (not necessarily distinct).
So-called “Multi-Prime RSA” allows faster computations with a given modulus size, but as far as I can tell it’s never seen much use. There’s been some interest as a performance optimization since CAs started requiring a minimum modulus size of 2048 bits, but wide support for ECDSA (which is much faster for private key operations) has relegated it to obscurity.
In my previous post, “Stupid Certificate Tricks”, I showed how to create an RSA key with custom parameters in order to embed data in a certificate. That was a relatively simple case — PyCryptodome has RSA.construct() which allows a key to be instantiated with arbitrary values for the modulus n, public exponent e, private exponent d, first prime p, and second prime q. Having to compute n and d even though they can be derived from the other three values is a mild annoyance, but in the end not a big deal. Unfortunately the API doesn’t allow specifying a third or further primes, which I found myself needing to do.
When I went to research possible solutions, I made several surprising discoveries. First, support for multi-prime RSA had been added to Go’s standard library in 2011. Second, PKCS#1 defined serialization of such keys in version 2.1, which was released in 2002. Finally, OpenSSL added support in version 1.1.1.
At this point, I was gritting my teeth a bit because like many TLS related data formats, RSA private keys use ASN.1. I like dealing with ASN.1 about as much as I like dealing with XML, which is to say, not at all. A bit of searching turned up pyasn1 which made things tolerable. To make the ASN.1 serialization work, all I had to do was translate the definitions from RFC 8017 into Python and write a bit of code to compute all of the derived values given a public exponent and list of primes.
With that out of the way, I generated a key and tried to use it with OpenSSL. It did not work.
$ ./mprsa.py 16209469334791745752099089153245209595938905391366915442843655311870250775988478962443242925129138403268309023495340941270951066230818482657126058912138893504120575530462325274587 223 373 505511 62264393819 692091200694401 48054446430444121028200972020533400162078125396018622197185481602069377646593949231788063528654342806608883936083928621453549454859416361204853853702948393735291252921874962603428963373263708172690458493327748172536543917708281204835129658881247320770314746942732710565970028734766695760731222427123603048615247949771446031873465256836264652436820606092660156412961641977084159217469138549478995858415013921 > multi.key $ openssl req -new -batch -key multi.key -out multi.csr -subj '/CN=test' 139698227354952:error:0D0DC006:asn1 encoding routines:ASN1_item_sign_ctx:EVP lib:crypto/asn1/a_sign.c:224:
This somewhat confusing error message seems to be the result of some hard coded limits in OpenSSL. It won’t work with keys having more than five primes at all, and has further restrictions in some cases depending on key size. Fortunately, it was trivial to patch these limits out.
After installing a patched OpenSSL package, I tried again.
$ openssl req -new -batch -key multi.key -out multi.csr -subj '/CN=test' $ openssl x509 -signkey multi.key -in multi.csr -req -days 999 -out multi.crt Signature ok subject=CN = test Getting Private key $ openssl verify -CAfile multi.crt multi.crt multi.crt: OK $ openssl rsa -noout -text -in multi.key RSA Private-Key: (1472 bit, 6 primes) modulus: 00:aa:98:6c:52:74:cf:48:d3:13:3c:5d:42:35:c2: e0:d7:f2:62:ef:41:e5:bc:bc:bb:d5:44:28:b4:c2: 51:52:3e:80:b4:92:17:e2:e0:e6:34:de:f5:37:95: 7c:78:70:7a:71:a2:00:64:9f:7a:15:e0:d0:73:9e: b7:95:70:45:c8:6b:0f:01:2b:48:9a:97:2e:f2:78: e4:19:14:8f:53:82:59:5c:5d:7c:a7:fc:02:a5:a4: 03:3a:7a:d7:40:e4:fc:6b:aa:e7:6f:a9:a9:2d:78: 8e:33:c6:0b:c0:a6:b9:32:3e:47:a0:53:8d:91:45: 2d:bd:72:ed:48:49:b6:5d:98:8d:f7:cd:2d:6b:2f: a5:02:96:b3:92:e6:77:11:52:6b:8a:f0:70:85:ba: ab:e2:73:58:6b:da:4b:21:84:7f:9f:05:b0:06:6f: 9e:f8:83:24:31:f1:b7:95:6a:5c:32:22:14:2c:47: 09:40:40:cb:bf publicExponent: 01:00:01:b7:02:e0:7a:d7:1c:d6:8e:e8:4a:58:f7: 92:eb:c8:db:27:0b:0d:d2:25:61:27:18:1f:c2:1c: db:6f:38:46:92:3d:dc:a2:d3:e7:a2:76:8b:28:56: bd:25:97:c1:4d:43:c7:5d:d0:27:68:91:d3:b2:c5: 98:0e:d6:57:c6:3e:a2:ba:a8:70:94:6b:30:77:db privateExponent: 00:8c:ea:a5:ac:1a:12:53:1b:28:5b:75:0a:85:cb: d0:4b:48:2c:cb:c3:16:bf:72:10:c0:6b:eb:8e:2b: 1a:63:d3:d2:3f:4e:ac:72:04:8a:83:cc:e8:a8:05: e4:76:04:aa:64:3a:02:90:fa:f4:d2:6d:dc:5b:a7: ff:8e:a1:d9:6f:81:8a:56:d8:dc:cd:b0:64:ff:5f: 73:b0:9d:fb:8b:72:91:39:e3:7f:84:5c:c3:d1:6e: 4a:f0:be:7e:d0:40:31:e2:06:5f:5c:72:74:88:9b: ff:6c:1a:2e:1e:b4:b6:3c:9f:32:57:5c:96:10:67: c3:a6:7b:06:44:a3:ca:4a:2d:d4:76:f3:98:9e:61: f5:6e:55:8e:fa:d6:26:e8:b8:5d:d6:4a:9f:21:21: 60:fc:59:d5:d6:cc:58:c1:9d:9f:89:d0:b3:f1:ad: b2:3d:d9:d0:45:b0:c1:3d:46:5e:e8:86:68:bb:02: 5d:ce:5c:ac:53 prime1: 223 (0xdf) prime2: 373 (0x175) exponent1: 205 (0xcd) exponent2: 319 (0x13f) coefficient: 168 (0xa8) prime3: 505511 (0x7b6a7) exponent3: 201953 (0x314e1) coefficient3: 141986 (0x22aa2) prime4: 62264393819 (0xe7f3f405b) exponent4: 34891590717 (0x81fb36c3d) coefficient4: 15148084064 (0x386e56b60) prime5: 692091200694401 (0x275740a2b6881) exponent5: 552465485917523 (0x1f676e509ed53) coefficient5: 78237913099958 (0x47282f04aeb6) prime6: 7d:25:8e:35:a8:57:b2:4b:8c:56:6b:67:85:e0:bd: 03:61:a8:9c:ab:50:dc:a2:25:61:0f:c8:af:7d:0f: 51:f3:24:11:26:3c:e9:2f:0f:c7:1e:9b:96:7e:d3: e0:56:38:1e:48:de:df:11:e6:bf:8e:86:8a:3a:d8: d4:ec:9b:a9:7e:b7:f2:84:0e:c3:f3:3c:e7:bb:69: fd:6e:db:1e:07:58:35:ae:de:b1:e6:82:12:61:73: 87:18:e7:e8:d5:31:0f:59:f1:05:b7:32:21:ef:cd: 28:6c:56:4e:fa:be:67:02:c2:2a:ed:24:8c:8d:56: d5:12:ee:49:05:74:a3:ac:7d:d1:01:07:25:c2:ff: ba:07:10:f5:26:14:41:07:8b:c8:e7:fc:96:d2:81: 24:b6:3b:a5:7d:ae:15:f5:34:b9:73:b5:af:05:70: 5e:69:d0:21 exponent6: 54:7c:0f:4c:e7:e2:e5:2e:9d:54:dd:25:cf:39:f5: ca:a4:3a:90:a7:69:87:de:ad:9c:e8:be:e8:98:60: b0:22:0c:50:f3:74:25:9a:e4:04:b2:19:56:74:95: ed:0c:65:c2:a9:4b:dc:f2:87:d1:b3:59:c6:9f:28: 88:a8:0a:85:61:53:46:90:b1:3c:14:9f:d4:33:b3: b0:05:27:a0:9c:93:c7:65:30:76:d7:59:01:8d:f1: b8:6d:c2:b4:34:1d:10:67:ef:b9:d0:f1:64:62:d9: 8f:78:8a:f2:fc:84:9b:55:dd:dd:b6:a7:e3:21:df: 00:9c:03:4c:89:0a:66:52:4f:0d:ae:d4:cc:2d:79: 5b:81:f6:4a:bb:82:c8:bc:5c:51:fc:9f:91:d3:6f: ec:0e:43:af:98:3f:90:bb:8b:db:bd:de:b6:6e:04: c3:bc:73:93 coefficient6: 4a:9c:ed:70:1f:c7:4b:f4:0b:e0:32:a5:db:f5:07: 13:88:25:e9:c0:21:16:a2:09:5d:a6:db:00:c9:b2: 5e:63:90:b7:a1:0f:aa:60:ed:39:fd:3a:2b:ab:21: c9:c8:d6:ab:e0:40:e9:29:fa:b4:84:11:6a:a8:f2: 2f:b6:27:6b:5e:50:1a:4b:55:74:83:51:7c:83:91: bf:ce:46:ee:30:76:68:21:71:a3:9d:cd:04:54:41: 24:98:5e:a4:61:c5:0f:b5:5a:24:f8:d1:3a:39:21: ce:af:a8:33:e0:0a:ee:dd:7d:21:b5:e6:e8:f8:32: 5d:59:d9:09:5e:62:53:82:0c:e8:df:21:76:35:fe: 47:d8:9e:56:e7:a5:2f:45:d2:e0:25:21:1e:da:63: ec:be:fa:f3:47:a0:0a:1b:7b:42:6c:9e:0f:b3:91: 83:f6:38:3f
One thing I did notice when testing is that when using keys with particularly small primes, I’d sometimes get errors about “no inverse”. I’m not entirely sure of the cause, but I was able to get around it by retrying operations a few times.
|||In hex, 65537 is |
|||Practical implementations of RSA use optimizations based on the Chinese remainder theorem which do require the primes factors of n to be distinct.|
|||I originally used PyCrypto, but that project is no longer maintained. PyCryptodome was created to be a mostly drop-in replacement for it.|