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 de mod φ(n) ≡ 1. 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[1] 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[2]).
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.
Shenanigans
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[3] 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.
Serialization
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 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.
| 1 | import re |
| 2 | import sys |
| 3 | import gmpy2 |
| 4 | import base64 |
| 5 | import hashlib |
| 6 | |
| 7 | from functools import reduce |
| 8 | |
| 9 | from OpenSSL import crypto |
| 10 | |
| 11 | from pyasn1.type.univ import Sequence, SequenceOf, Integer |
| 12 | from pyasn1.type.namedtype import NamedType, NamedTypes, OptionalNamedType |
| 13 | from pyasn1.codec.der.encoder import encode as der_encode |
| 14 | |
| 15 | def product(items): |
| 16 | return reduce(lambda x, y: x * y, items) |
| 17 | |
| 18 | class RSAError(ValueError): |
| 19 | pass |
| 20 | |
| 21 | # https://tools.ietf.org/html/rfc8017#appendix-A.1.2 |
| 22 | class OtherPrimeInfo(Sequence): |
| 23 | componentType = NamedTypes( |
| 24 | NamedType('prime', Integer()), |
| 25 | NamedType('exponent', Integer()), |
| 26 | NamedType('coefficient', Integer()) |
| 27 | ) |
| 28 | |
| 29 | class OtherPrimeInfos(SequenceOf): |
| 30 | componentType = OtherPrimeInfo() |
| 31 | |
| 32 | class RSAPrivateKey(Sequence): |
| 33 | componentType = NamedTypes( |
| 34 | # Version ::= INTEGER { two-prime(0), multi(1) } |
| 35 | NamedType('version', Integer()), |
| 36 | NamedType('modulus', Integer()), |
| 37 | NamedType('publicExponent', Integer()), |
| 38 | NamedType('privateExponent', Integer()), |
| 39 | NamedType('prime1', Integer()), |
| 40 | NamedType('prime2', Integer()), |
| 41 | NamedType('exponent1', Integer()), |
| 42 | NamedType('exponent2', Integer()), |
| 43 | NamedType('coefficient', Integer()), |
| 44 | OptionalNamedType('otherPrimeInfos', OtherPrimeInfos()) |
| 45 | ) |
| 46 | |
| 47 | # instantiate private key given public exponent and list of primes |
| 48 | def __init__(self, e, primes): |
| 49 | super().__init__() |
| 50 | |
| 51 | if len(set(primes)) != len(primes): |
| 52 | raise RSAError('Cannot compute CRT coefficents with repeat primes') |
| 53 | |
| 54 | primes = [2] + primes |
| 55 | |
| 56 | # compute modulus |
| 57 | n = product(primes[1:]) |
| 58 | |
| 59 | primes_minus_one = [x - 1 for x in primes] |
| 60 | phi = product(primes_minus_one[1:]) |
| 61 | |
| 62 | if gmpy2.gcd(e, phi) != 1: |
| 63 | raise RSAError('e and phi(n) are not coprime') |
| 64 | |
| 65 | # compute private exponent |
| 66 | d = int(gmpy2.invert(e, phi)) |
| 67 | |
| 68 | exponents = [d % x for x in primes_minus_one] |
| 69 | |
| 70 | coefficients = [None] * len(primes) |
| 71 | # inv q mod p |
| 72 | coefficients[2] = int(gmpy2.invert(primes[2], primes[1])) |
| 73 | for i in range(3, len(primes)): |
| 74 | # inv product(r[1] ... r[i-1]) mod r[i] |
| 75 | coefficients[i] = int(gmpy2.invert(product(primes[1:i]), primes[i])) |
| 76 | |
| 77 | # base set of rsa private key values |
| 78 | self['modulus'] = n |
| 79 | self['publicExponent'] = e |
| 80 | self['privateExponent'] = d |
| 81 | self['prime1'] = primes[1] |
| 82 | self['prime2'] = primes[2] |
| 83 | self['exponent1'] = exponents[1] |
| 84 | self['exponent2'] = exponents[2] |
| 85 | self['coefficient'] = coefficients[2] |
| 86 | |
| 87 | # add values for additional primes if needed |
| 88 | if (len(primes) - 1) > 2: |
| 89 | self['version'] = 1 |
| 90 | otherPrimeInfos = OtherPrimeInfos() |
| 91 | for i in range(3, len(primes)): |
| 92 | info = OtherPrimeInfo() |
| 93 | info['prime'] = primes[i] |
| 94 | info['exponent'] = exponents[i] |
| 95 | info['coefficient'] = coefficients[i] |
| 96 | otherPrimeInfos.setComponentByPosition(i - 3, info) |
| 97 | |
| 98 | self['otherPrimeInfos'] = otherPrimeInfos |
| 99 | else: |
| 100 | self['version'] = 0 |
| 101 | |
| 102 | @property |
| 103 | def der(self): |
| 104 | return der_encode(self) |
| 105 | |
| 106 | @property |
| 107 | def pem(self): |
| 108 | b64 = base64.b64encode(self.der).decode() |
| 109 | b64 = '\n'.join(b64[i:i+64] for i in range(0, len(b64), 64)) |
| 110 | return '-----BEGIN {text}-----\n{b64}\n-----END {text}-----\n'.format( |
| 111 | b64=b64, |
| 112 | text='RSA PRIVATE KEY' |
| 113 | ) |
| 114 | |
| 115 | if __name__ == '__main__': |
| 116 | e = int(sys.argv[1]) |
| 117 | primes = list(map(int, sys.argv[2:])) |
| 118 | sys.stdout.write(RSAPrivateKey(e, primes).pem) |
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.
| 1 | --- openssl-1.1.1c.orig/crypto/rsa/rsa_locl.h |
| 2 | +++ openssl-1.1.1c/crypto/rsa/rsa_locl.h |
| 3 | @@ -10,7 +10,7 @@ |
| 4 | #include <openssl/rsa.h> |
| 5 | #include "internal/refcount.h" |
| 6 | |
| 7 | -#define RSA_MAX_PRIME_NUM 5 |
| 8 | +#define RSA_MAX_PRIME_NUM 64 |
| 9 | #define RSA_MIN_MODULUS_BITS 512 |
| 10 | |
| 11 | typedef struct rsa_prime_info_st { |
| 12 | --- openssl-1.1.1c.orig/crypto/rsa/rsa_mp.c |
| 13 | +++ openssl-1.1.1c/crypto/rsa/rsa_mp.c |
| 14 | @@ -111,5 +111,5 @@ int rsa_multip_cap(int bits) |
| 15 | if (cap > RSA_MAX_PRIME_NUM) |
| 16 | cap = RSA_MAX_PRIME_NUM; |
| 17 | |
| 18 | - return cap; |
| 19 | + return RSA_MAX_PRIME_NUM; |
| 20 | } |
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
It works!
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.