Like many nerds, I have an interest in cryptography rooted in the wartime exploits of codebreaker and Ur-computer scientist Alan Turing. So I’ve followed with interest IEEE Spectrum’s reporting on the burgeoning field of postquantum cryptography. These techniques are designed to frustrate even the immense potential of quantum computing, a technology light-years beyond the electromechanical bombe that Turing used to break the German Enigma cipher. I’m sure those new cryptographic methods will work just fine. But there is one encryption scheme, known even in Turing’s time, that is mathematically secure against not just quantum computers but any computer that will ever be invented: the one-time pad.
A one-time pad is a series of random letters or numbers—typically 250 digits. The sender and receiver each have a copy of the pad, which is used for both encryption and decryption, following some simple but strict rules for pen and paper. It’s a cipher in which the key changes in an utterly unpredictable way after each character. Without predictability, there’s nothing for an attacking computer to get its teeth into.
However, even the most junior codebreaker in possession of two messages encrypted with the same pad would be able to strip off the encryption and read both. It’s therefore critical to destroy each pad after you’ve used it. And it’s a bad idea to store the pad on a thumb drive or something similar, because computers and storage devices have a habit of leaving residues of data around, even after the data has been officially deleted.
The one-time pad comes with some other significant limitations. The digits have to be truly random—the numbers generated by the pseudo-random algorithms typically used by computers won’t cut it. And because you can use a given pad only once, you need a whole bunch of them if you want to send more than a single message. Plus, the pads need to be physically printed and shared by hand—you can’t send them over a network.
The random-number generator uses a collection of 74HC-series logic chips [top right] to digitize electrical noise and present it as a random byte to an Arduino Uno Minima [top left]. The generator can produce roughly one byte every 200 microseconds, and the Uno converts this into a single digit and builds up a series of 50 pads with 250 digits each, which it sends to the printer [bottom].James Provost
I decided to build a machine that makes dealing with those problems a little easier. My Pad-O-Matic is built around a CSN-A2 thermal receipt printer I’d bought on a whim a few years back. The printer is connected to the most transparent technology stack I could find: a tortured transistor, a few logic chips, and a microcontroller with about 200 lines of my code. This code does nothing more complicated than division, because if I’ve learned one thing about cryptography, it’s that unless you really know what you’re doing, trying to be a clever clogs is a recipe for failure. The Pad-O-Matic is completely stand-alone.
The thermal receipt printer in the Pad-O-Matic lets me print a whole series of pads. I still have to physically share the pads, but at least they’re in a compact roll. My correspondent and I can then tear off and destroy each pad after it’s been used.
Without predictability, there’s nothing for an attacking computer to get its teeth into.
I still needed a good source of randomness—some fundamentally unpredictable physical process to convert into equally unpredictable bits. Fortunately, that problem was already solved for me. I found a neat little battery-powered circuit from Make: magazine that relies on the electrical noise produced by forcing electrons the wrong way across a transistor’s base and emitter terminals while leaving the collector terminal unconnected. Make:’s generator is a simplified version of a circuit by Aaron Logue, but Make: fortunately has a copy of the original schematic. This uses 12 and 5 volts instead of the 18 and 5 volts used by Make:’s version, so I could use an old power supply I had that also provides enough extra current to drive the thermal printer. The original circuit also has two nice additional features for the cost of a few extra chips.
The first feature is a clean microcontroller interface. It sends one byte at a time in parallel, alerting the microcontroller every time a new byte is available. An alert is needed because the length of time needed to generate a random byte varies slightly due to the other nice feature: automatic debiasing, using four flip-flops and an XOR gate. Debiasing means that even if the electrical-noise generator tends toward, say, more 0s than 1s, the final output will be statistically balanced.
The Pad-O-Matic samples electrical noise at regular intervals to create a stream of bits. To prevent the final numbers from being biased toward those with many 0s or 1s, pairs of bits are compared. Only if they differ are they examined further, with the leading digit being passed along. Eight of these debiased bits are packed into a byte, which is then subjected to modular division to produce a random number between 0 and 9.James Provost
For my microcontroller, I finally got to use an Arduino Uno R4 Minima. Although this latest version of the beloved Uno came out about 18 months ago, I hadn’t found a project that needed it—until now. Its bigger memory—32 kilobytes of RAM versus 2 KB in the Rev3—is essential, because the Pad-O-Matic has to generate an entire series of pads—50 in my case—and hold it in memory. With 250 digits per pad, that requires over 12 KB. As the digits live only in RAM, there’s no risk of them leaving any trace of themselves behind.
The microcontroller produces digits from the incoming random bytes by first throwing away any byte with a value over 250. Then it performs modular division by 10 on each remaining byte, leaving digits in the range of 0 to 9.
I chose 50 pads per series, even though I had the memory for more, because I actually have to print one series to keep and a copy to share, and then generate and print another series and its copy: The first series is for sending messages from me to my secret correspondent, and the second series is for them to send messages to me. This eliminates the risk of accidentally using the same pad when messages cross each other. A total of 100 pads just about uses up one roll of thermal paper.
I put the whole thing in a wooden enclosure, and presto! At the press of a button, the Pad-O-Matic whirs into life, spitting out perfect—and now marginally more convenient!—cryptographic security.
Reference: https://ift.tt/mwSqT2l
No comments:
Post a Comment