# Secure communication through CIA-infected devices

## The problem

WikiLeaks recently published documents detailing CIA attacks on common smartphone operating systems, including those on Samsung, Google, and Apple devices. WhatsApp and other “secure messaging apps,” it turns out, are not secure at all. The reason is that if the phone OS is itself compromised, nothing on the phone can be secure. It doesn’t matter how good your app’s encryption is—if the CIA can read everything on my phone, then that includes unencrypted plaintext and private encryption keys.

The situation appears hopeless. For one thing, our devices are not secure. Furthermore, who’s to say the cell phone companies won’t voluntarily give the government your data, even if the operating systems themselves are fixed? If you want secure communication, it seems the only way to do it is to build your own cell phone, and then build your own network of cell towers.

## My solution

Sending secure messages over untrusted channels is basically a solved problem. Encrypt the message with RSA and sign it with DSA, for example. (These, and similar algorithms, will probably be broken by quantum computers. But as far as we know, that hasn’t happened yet.)

What makes the situation more interesting is that the broadcasting device itself can no longer be trusted. So, where does that leave us? Assuming I can’t patch the phone, I need a new device.

The new device would:

• randomly generate keys
• accept plaintext input from a keypad
• encrypt messages with a private key
• decrypt messages with a public key

Since we still want to use the phone to send and receive public keys and encrypted messages (ciphertext), we would need to transmit these back and forth between the phone and the device. I drew a schematic:

Fig. 1 By hiding the plaintext and private key from CIA malware on Samsung and Apple devices, we can broadcast messages securely from these infected devices.

There are a few points you’d have to consider to make this thing work. After all, if they can hack my smartphone, why can’t they hack this thing?

First, it would have to be completely open-source from the circuitboard up. That way, anybody could check for security vulnerabilities on their own.

Second, it would have to be simple. This way, a single user could understand the entire system and convince himself that there were no holes. Security flaws emerge when a product becomes too complicated for an individual engineer to understand in its entirety. You can’t hack a toaster! But you can hack an operating system, because it’s got a lot of “moving parts.”

Third, you would have to ensure that the encrypting device could not be infected via the connection to the smartphone. I would be wary of complex protocols like USB. In fact, one could go so far as to send and receive information over the headphone jack. (Microphone for output; left or right channel for input; ground for ground.) That way, you know that only data bits are being sent, not commands or metadata or any other crap. Unless I am mistaken, the only potential vulnerability would be buffer overflow attacks—and you can avoid those if you’re careful.

# Quantum Bitcoin mining

There has been some writing done about the implications of quantum computing to Bitcoin, the most popular peer-to-peer cryptocurrency. Here is the story:

• To send an amount to Bob, Alice digitally signs the message “Alice gives money to Bob” and sends it out to miners. But the Elliptic Curve Digital Signature Algorithm (ECDSA) is broken by a version of Shor’s algorithm. Now anybody with a large enough quantum computer can forge Alice’s digital signature. This is the part of the story that gets the most attention.
• SHA-256 hashes are used to timestamp previous blocks, and also in mining new blocks. Classically, it takes on the order of 2256 operations to invert an SHA-256 hash. Grover’s algorithm takes that down to about 2128. That’s still a large number, so SHA-256 is not generally considered “broken” by quantum algorithms.

Fig. 1 The real part of the ℓ = 4, m = 3 spherical harmonic. This is what I picture when I hear the word “quantum.”

It’s tempting to end the story there, and some writers do. But it doesn’t end there! While SHA-256 is not “broken” by Grover’s algorithm, Bitcoin mining is made much faster. That’s because the Bitcoin proof-of-work is not inverting an SHA-256 hash, but rather, finding any one of many possible inputs producing a hash less than a threshold t.

(I encourage you to read the original paper. It’s very accessible, and most of the second-hand summaries fall severely short. For the record, the original paper requires a certain number of leading zeros instead of a threshold t. They’re not strictly equivalent, but they’re similar. The Bitcoin Wiki indicates that the actual network uses the threshold.)

The threshold changes periodically to keep the block generation rate roughly constant. For a particular t, though, there are t possible outputs that are less than that value. Thus, the fraction of possible outputs satisfying the requirement is t/2256. The input parameter that must be varied to produce these zeros in the hash is called the nonce, and it consists of 32 bits. The function we’re interested in isn’t one-to-one, then, but I’ll assume it’s fairly uniform. Then there are about t 232–256 nonces constituting a valid proof-of-work. That could be a lot more than just one, which there would be if we were trying to break SHA-256 altogether.

In fact, there is a modified version of Grover’s algorithm in the case where there are multiple special inputs. Say there are N possible inputs and we want to find any of the m special ones. That takes $O(\sqrt{N/m})$ iterations (so long as m/N is very small, according to Mermin). That comes out to $O(\sqrt{2^{256}/t}).$

That is a big deal! Note in particular that there appears to be no dependence on the size of the nonce. As of the time of writing, the current mining difficulty is about 238, which corresponds to a threshold of 2256–32–38 = 2186. So the number of operations comes down to about 235, which is something like 34 billion. For comparison, the classical number of hashes required is the square of that.

Punchline: A full-scale quantum computer may be able to mine Bitcoin tens of billions times faster than GPUs.

Implications: Unlike ECDSA, SHA-256 does not need to be replaced entirely in post-quantum cryptocurrencies. The hash-based crypto puzzle will still be a useful proof-of-work, but the difficulty parameter must be increased to the point where classical computers can no longer compete. Grover search brings the current O(270) down to O(235). So if everybody had a quantum computer and we wanted to keep the O(270) runtime for quantum computers, we might require t = 2116. At that threshold, a classical computer working on the same problem would face O(2140) hashes, which as I mentioned above is tens of billions times more than are required today.