The batch_gcd utility is designed to detect whether a set of RSA moduli
contains any pairs that share a common factor. This could happen, for example,
if some of the moduli were generated by the same weak entropy source.
Authors: Brandon Enright, Andrew Chi, David McGrew
The batch_gcd command line tool takes a list of hex integers on stdin (one per
line), and efficiently computes the greatest common divisor (GCD) on all pairs
of inputs. If any non-trivial common factors are found, it writes the resulting
factorizations to stdout, followed by the groups of line numbers whose moduli
share a common factor. Informational messages are written to stderr.
$ ./configure
$ make batch_gcd --dir=src
$ echo -e "29bf7\n12a15\n17b6d" | src/batch_gcd
Running batch GCD on 3 moduli.
Parallelization: 12 threads
Found 3 weak moduli out of 3.
Computing pairwise GCD for 1 moduli, estimated time: O(3 * 1)
Further found co-factors for 1 weak moduli.
Vulnerable modulus on line 1: 29bf7 has factors 133 and 22d
Vulnerable modulus on line 2: 12a15 has factors 89 and 22d
Vulnerable modulus on line 3: 17b6d has factors 89 and 2c5
Reporting which lines, if any, share a common factor.
2,3;1,2
$ echo -e "29bf7\n12a15\n17b6d" | src/batch_gcd 2> /dev/null
Vulnerable modulus on line 1: 29bf7 has factors 133 and 22d
Vulnerable modulus on line 2: 12a15 has factors 89 and 22d
Vulnerable modulus on line 3: 17b6d has factors 89 and 2c5
2,3;1,2
The batch_gcd tool is not built by default, because it depends on the GNU
Multiple Precision Arithmetic Library (GMP). To build it manually, run the
following commands from the top-level directory of the mercury source
repository.
$ ./configure
$ make batch_gcd --dir=src
$ make batch_gcd_test --dir=test # run tests (optional)
The executable will be built at the path src/batch_gcd.
This tool is designed for computing batch GCD on a very large set of integers,
using the product tree approach developed by Daniel J. Bernstein
[1] and notably implemented by Heninger
et. al
[2]
to analyze Internet scans of TLS certificates. Currently, batch_gcd can handle
up to roughly 67 million 2048-bit RSA moduli, given a machine with sufficient
memory of about 1 TB of RAM, and it automatically parallelizes the computation
across all CPU cores. The current input size limit is due to the fact that the
batch GCD algorithm multiplies all of the input together into one large integer,
and the largest single integer that GMP can represent is 2^37 bits, or about 16
GB (details
here and
here). If the input size exceeds this limit, the
tool aborts with an error message.
The tool will detect and report duplicate RSA moduli, but for the purposes of batch GCD computation and reporting of common factors, it will only use the first modulus in the set of duplicates. It will also detect and report pathological cases where one modulus divides another.
Usage:
$ batch_gcd < moduli_in_hex.txt
The tool takes no command line parameters, and the input must be exactly one hex integer per line. No blank lines or other characters are permitted. Informational messages are written to stderr.
To check for weak keys in a set of certificates, use a pipeline of the tools
cert_analyze, jq, and batch_gcd.
- Input: a file containing base64-encoded X.509 certificates, one per line.
cert_analyzeconverts the X.509 certificates to a JSON encoding for easy processing.jqextracts the RSA modulus from the JSON.batch_gcdcomputes all-pairs GCD and reports any factorizations (by line number and modulus).
Here is an example pipeline.
$ cat certs.b64 |
src/cert_analyze |
jq -rc '.subject_public_key_info.subject_public_key.modulus' |
src/batch_gcd
Here is an example output in which 12 out of 13 input certificates contained moduli which shared a common factor with another modulus.
Running batch GCD on 13 moduli.
Parallelization: 12 threads
Found 12 weak moduli out of 13.
Computing pairwise GCD for 10 moduli, estimated time: O(12 * 10)
Further found co-factors for 10 weak moduli.
Vulnerable modulus on line 1: 1e7e8ad4e9a9e9220606abe8c000eda0f107ceee2589670d92cee58f36b243092a651736cbff727dbb0ffdc15fb93726ed322db315666aaec8d718d75ff3bf6ebcad3bd79b023dac2005a8f959ccdb889c13b89661e6e2f2a92d3114748bebbb98b9b9d620ebd3686d3a152ca656631891cad253276d961a5f78401a35791fa9 has factors 38326f703d6d55184940485e16aeee14778b4cf36ebe05863863c4423e10a0f30d517b4b082cb3651e1cee7ff12c1f985d94e89ef3fba74a9314e05b5d153419 and 8ae9f0c710ed2a2c8885cad9f5757b8fb27cc95b7b89bf33ddce184822c1376cf99527e2862042dbb66313f44c4c47b6c0259e16f63f000194c4d5bbe3bb3a11
Vulnerable modulus on line 2: 1e3d8b322db4c6e0ad74b09278746658fffed7b6e2bf925ed07ac29e8bcd9be7addcdba1f0f8f744658c30abc53c07fdc29a1ab62ec95e619a9acca7d74e78f7fe7ef6dd51332c5df3415476a3a7bb1612094c81bc59c176e60a1807b66ab217061ec8e9b03da639e58f466d3b6e975ff6ff03387f6af46390a430fb486d921d has factors 38326f703d6d55184940485e16aeee14778b4cf36ebe05863863c4423e10a0f30d517b4b082cb3651e1cee7ff12c1f985d94e89ef3fba74a9314e05b5d153419 and 89c1d88b238c8a21eed66b977a8605cb72e6b69ac0cd007d63c41000e090f5c0b93aff6398269ea8fb3beb90fe785fef279d80f1fb04ad2d07cf22a87e6aaea5
Vulnerable modulus on line 4: 465b8136e852ce4f7b9b0ac7288a28e48d8c550168f1f7f2fefe50ba9e06a48b716a7db5e3226091d4d30fc437048ac881e9af0cc49e2246bbc5c903117adee00b670705004d69f1b674729d9241c79216a391c9790c1638369ce4686b01d2680baa6f9feb56ed47c7eed0f237f3997d674d7a97a193bc9a07a26b649c36d605 has factors 82bf88d173860b5084516f6f9be4c7e88920956d08b678b373190760b3bada34959d7bc631d332110c8b593022fb714dbfe64a8bcf599ebe57743c1a30d54be1 and 89c1d88b238c8a21eed66b977a8605cb72e6b69ac0cd007d63c41000e090f5c0b93aff6398269ea8fb3beb90fe785fef279d80f1fb04ad2d07cf22a87e6aaea5
Vulnerable modulus on line 5: 46f2bb0daab537a117a2e660f2f6febbf4040a15a23442f95c2f3ab69d586ca24802cb441308b8349dd4a82a018e0e61eb0d58f71050969ada441fb9825ccceb046bced8ad06e641fb802c315cbec4b58905e7fb5562bda93418bd62521dd01dc26c78bfd384e52aade80ff43fb06830cf82a4dfa2e74e7794f95d3f81b603f1 has factors 82bf88d173860b5084516f6f9be4c7e88920956d08b678b373190760b3bada34959d7bc631d332110c8b593022fb714dbfe64a8bcf599ebe57743c1a30d54be1 and 8ae9f0c710ed2a2c8885cad9f5757b8fb27cc95b7b89bf33ddce184822c1376cf99527e2862042dbb66313f44c4c47b6c0259e16f63f000194c4d5bbe3bb3a11
Vulnerable modulus on line 6: 811a9746b424a1c0ef0ceee0a31c3f3ddda5e5e5c770cd9a4bc18afc6951dc4513cc495fffbd0d5f37af5893f632960dd399183f6424ca396137d0b6475fcbd9bc12539af78f7275f77e4876fb049625abf9be0acad137a7b61ae42d0e872d8f6d2711702dbbb2b4c03982b971d6d05ee35d5353554d330cc3534929a624d8ef has factors 924f2f80458a840d2506995213e3b35a920334c68ee54936027cf03babadfe1e5ad0d6e1c78b8be50801e96f984d3224de1aa1cd318a9fe304f03e3e6ded3c73 and e1e533f46ed52aa7891d4cb8c543c7df5612841101cb3ef4fdf3501c98a64023968dc93c3fcbe8a5038bc3ffd9358dbf44b5a4e77e57d3e31d3824f513fc2e95
Vulnerable modulus on line 7: 265efca5d4be3a3a32e40d1849859ae399d7e50dcefc5ed45ac1b0afe9bde70ae998080854b602dd64688d41463b7f367b2ef07ae299ba376973ee558edd16a4e2dd2eeed798d910a13b974e6312b72807ee8e499db0ddbae0d52fd20a8669d6ba4fef474683b1f42f99dae0e9523de25d4d29f3139fddfa871c5246495a5441 has factors 43237429ca9deb90d17025d613995dfbf77f00ba2bd8b23fef9d97a535cb3ae60436fd5209170aa1ef8c8a4eb6b9c7405899494ac825f94fb4fd873776e7537b and 924f2f80458a840d2506995213e3b35a920334c68ee54936027cf03babadfe1e5ad0d6e1c78b8be50801e96f984d3224de1aa1cd318a9fe304f03e3e6ded3c73
Vulnerable modulus on line 8: 1244c3e99d517d452502fe41281e4217433f61c8aae94e02d1c92a437d6aaafce28054cabbb94108dbd19cff196fbd593b27b0c1161219b5d12e87a09fe1e2fb61ec36ae682236b871bb3f3ea193de205d3ad60b876fa0cb367ce91fabcbfbff4cd88691ac870c9d915dd731def87f37735de81155183a604e3ae38fb877294f has factors 41510eb2b4cffbc472aeca534df8f8e8c5aa0f553cde1e025a75610f10ae9db595b78f830ec239f9bfd2c2d00ae6508b4ddff8b02ae1ed7d896ec60805ed446b and 4799f8749293e39ee6af86764a84dae2e09eeb0ce218e21ad9638eeb9d2e2600211411a6509ec47fe8900adcfef49a037d560c8e2c2ed4227d4a2cda870307ad
Vulnerable modulus on line 9: 13790c6a303529cdf722e7b11a3ce8492d8d374edd0cdf9b1459617a6523c88a7d4caed55ea00d3e3afb530583a090ed5a5ba73de9ad9f6dbf9bfb09cff7fac4cddef7aa1af30dcb2d4345c3c81211e9dde9e97735f9c81f2979bff19ceac8a5f33d5f127ad47ecae4f49d911c121e04364d984663df3d276f797532a635b4d1 has factors 459f46db5baf96f8404aaf1a831f0db8aad7d93a4256e8156b2b70757a011d800c39962486ce3ba88788716e9ac581c37c140116d12e2e9abd56262a1a255635 and 4799f8749293e39ee6af86764a84dae2e09eeb0ce218e21ad9638eeb9d2e2600211411a6509ec47fe8900adcfef49a037d560c8e2c2ed4227d4a2cda870307ad
Vulnerable modulus on line 10: 3433499cb03fc8d47173942631c509ee48ac8f66c1470b2f44dce418d1a1dfba12c51f6494c707a2f65ab781fd4745752242bb276484fe90130990004fe241215e7bd0429d7f153bd706296e0672dd22ef622bdd01aacb7bd4a9d3844dbd2226214fcc3084514e943de95767ece05fae635cfae43ddb5314d12c1058e4cf8fdd has factors 4799f8749293e39ee6af86764a84dae2e09eeb0ce218e21ad9638eeb9d2e2600211411a6509ec47fe8900adcfef49a037d560c8e2c2ed4227d4a2cda870307ad and baa262e43120e54665c0cbcb3ead51b0a00819b4e91d4872d3fbe7724e03ab71bcaf8bb84c74dec96aadfcb18653a8f05393d666069923bc7b9b31363d6d6ef1
Vulnerable modulus on line 11: 11c37c626d7b698246aa3d0715433fdf70e3605bf9ba9527c75e7b49d2b0e1442d8a3ecd7861fceb055e5a7e335a308996c5a01f5bc30408c6ef11a63c808eb362b6d092299ed8d5df7adc8931f11c2312b88773398877a592503c3bd4c7f779f9f4e86f1e19c3b2fbfe1b574af6a7d08e33ffa4238cae10463fc172b0921c27 has factors 41510eb2b4cffbc472aeca534df8f8e8c5aa0f553cde1e025a75610f10ae9db595b78f830ec239f9bfd2c2d00ae6508b4ddff8b02ae1ed7d896ec60805ed446b and 459f46db5baf96f8404aaf1a831f0db8aad7d93a4256e8156b2b70757a011d800c39962486ce3ba88788716e9ac581c37c140116d12e2e9abd56262a1a255635
Vulnerable modulus on line 12: 2f9e533464cff15c387975dbd55f90e7e5fa0289b11eaebaac8c2b34862750c0d63f96153c121b3920348d5f333d32392c62e770f22644ec243e164149f324d8f471641349aed208e80ec4375197c97b6f439cf062768b24f712bc926fc5cefdaff8fe74e4fa51bc7a3c6eda9c4781351b9dcccd9e753285b521d8ff285262bb has factors 41510eb2b4cffbc472aeca534df8f8e8c5aa0f553cde1e025a75610f10ae9db595b78f830ec239f9bfd2c2d00ae6508b4ddff8b02ae1ed7d896ec60805ed446b and baa262e43120e54665c0cbcb3ead51b0a00819b4e91d4872d3fbe7724e03ab71bcaf8bb84c74dec96aadfcb18653a8f05393d666069923bc7b9b31363d6d6ef1
Vulnerable modulus on line 13: 32c1e32b3fc51c183f9060dfb63733966cc2649211fda1a567c38b42fad5b8bbc169c0134de8fde881b12ffdf89a35c4741e89749dceee1a446897353d932677466eaf0123550abd16418a5e1d6a7e33443a7eedbc100afa70edb736f1353a3d9a26bd9cbfa4119a384098952915def0c3d0507450e9f0a2dd1f607cfdc1ede5 has factors 459f46db5baf96f8404aaf1a831f0db8aad7d93a4256e8156b2b70757a011d800c39962486ce3ba88788716e9ac581c37c140116d12e2e9abd56262a1a255635 and baa262e43120e54665c0cbcb3ead51b0a00819b4e91d4872d3fbe7724e03ab71bcaf8bb84c74dec96aadfcb18653a8f05393d666069923bc7b9b31363d6d6ef1
Reporting which lines, if any, share a common factor.
1,2;8,11,12;9,11,13;8,9,10;4,5;2,4;1,5;6,7;10,12,13
-
Bernstein, D.J. "How to find the smooth parts of integers." 2004. https://cr.yp.to/papers.html#smoothparts
-
Heninger, Nadia, Zakir Durumeric, Eric Wustrow, and J. Alex Halderman. "Mining your Ps and Qs: Detection of widespread weak keys in network devices." 21st USENIX Security Symposium (USENIX Security 12), pp. 205-220. 2012. https://www.usenix.org/conference/usenixsecurity12/technical-sessions/presentation/heninger