Create a one-time pad with a Pi
Nate Drake explains how your Pi can bring you to the very pinnacle of cryptography by exchanging messages in perfect secrecy.
Quantum Computers. Microphones so sensitive that they can record your keystrokes from yards away. Networks of zombie computers working round the clock to brute-force passwords. Government designed backdoors in code. It has never been harder to be entirely certain that any message you send can be transmitted or received in absolute secrecy.
This holy grail of cryptography has long frustrated security experts, and most people are willing to settle for using encryption programs like gpg, which, while theoretically breakable, will resist all cracking attempts long after you’re pushing up the daisies.
What if, however, there was a way to be certain that your personal emails, pictures of your pet kitten, backups of your tax returns for the past decade and so on were safe even if intercepted? Enter the One Time Pad.
THE NOTORIOUS OTP
In simplest terms, a One Time Pad is a series of random numbers which you agree upon with someone with whom you wish to communicate — usually by meeting in person and exchanging pads.
When sending a message, you first need to convert it to numbers, then add each of these numbers to the numbers in the pad. Once the recipient receives the message, they can work backwards using their copy of the pad, deducting the numbers to retrieve your original written message.
Provided that the numbers are truly random, no one else sees the pad, and the same text isn’t encoded twice with the same pad, then even the world’s fastest supercomputer couldn’t decode the message.
The strength of the encryption lies in the randomness of the pad numbers. Without knowing these, anyone who intercepted a message might see the word ‘LINUX’ encrypted as ‘OSYAJ’ but would have no way of knowing it isn’t another five letter word, like ‘CHILE’.
The One Time Pad has been kicking around in some shape or form since the 1880s but it wasn’t until 1917 that Gilbert Vernam et al formally patented a machine for automating the process. In this case, two reels of punched tape were used, one with the original message and one with the pad of random numbers.
KGB agents in the US were quick to exploit this during the Cold War, placing small pads inside hollowed-out nickels, fake walnuts and any number of dastardly hiding places.
In the 21st century, computers like Raspberry Pi lend themselves well to being carried around easily and are perfect for generating and processing One Time Pads.
But in order to understand why, it’s necessary to understand the pitfalls of the One Time Pad.
ENTROPY ISN’T WHAT IT USED TO BE...
Bruce Schneier once described the One Time Pad as “theoretically secure, but... not secure in a practical sense”. This reflects the fact that there have been times that OTPs have been broken in practice despite their theoretical security. In the 1940s, for instance, US SIGINT’s counterintelligence program Venona was able to decrypt a number of Soviet OTP messages simply because some pads had been reused.
This crypto-cardinal sin was committed because the Soviets simply couldn’t generate pads fast enough for the thousands of daily messages sent during wartime.
A similar chink is found by German codebreakers in Neal Stephenson’s Cryptonomicon. The British employ a raft of old ladies with small bingo machines to draw numbered balls to generate pads. Unfortunately, the old dears don’t always obey best practices — they fail to look away each time they draw a ball as instructed, meaning that they subconsciously select predictable numbers.
Fast forward to the 21st century and the issue hasn’t improved much. Entire books have been devoted to this subject but suffice it to say that computers generally aren’t very good at generating true randomness. Usually when it’s required, a website or program will ask you to wiggle your mouse to provide a so-called ‘noise source’ to work from.
Mostly, however, when a computer requires larger amounts of randomness, it will form a string of pseudo-random data from your entropy pool, which, while ideal for determining where the
next block will fall when you play Tetris, is less than perfect when it comes to security.
Thankfully one of the lesser known features of the Raspberry Pi is that it has its own built-in hardware random number generator, which, in combination with the rng-tools suite, can generate exactly the kind of high-quality randomness needed for an OTP.
The second obstacle faced by those using OTP has to do with key generation and distribution. The Soviets were unable to keep up with the demands of war, and in real life, the bingo machines of Britain’s little old ladies would probably end up smoking with the number of times they’d need to be churned.
Fortunately, the hardware RNG built into the Pi can generate large amounts of data in a short amount of time. For instance, a pad with 10,000 sets of five-digit random numbers can be generated in seconds by activating the hardware RNG (see Step 1 of our guide on page 99) and then entering:
$ sudo base64 /dev/hwrng | tr -dc ‘0-9’ | fold -sw 5 | head -c 10000 > bobtoaliceotp.txt
The resulting text file can then be printed out, for instance by Adafruit’s thermal printer. This printer has the advantage that, unlike most laser printers, it doesn’t record the serial number, make or model on each sheet it prints out (on this, see www.eff.org/
issues/printers). It also holds up to 15m of paper, which will be plenty for generating long messages. Using this in combination with the excellent program otp-gen, you can print off your own pads automatically at the touch of a button too (see the ‘OTP goes Thermal’ box above).
Once the reams of paper are safely printed and tucked away, next comes the issue of physically distributing pads. This is no doubt the main reason why the OTP hasn’t seen much widespread use. It’s rumoured that the red phone running between Washington and Moscow for instance is secured by an OTP, mainly because both Superpowers are wealthy and melodramatic enough to have men with dark glasses to handcuff themselves to briefcases and swap pads at regular intervals.
Of course if you have printed paper pads, it is possible to mail them to your recipient, but then your OTP would be no safer than a regular letter because it may have been intercepted and copied along the way. The same applies for using regular encryption programs like GnuPG.
The only way to be sure that your pad cannot be intercepted is to deliver it in person. Again the humble Raspberry Pi comes to the fore here because it’s extremely small and easy to carry. Upon meeting the person with whom you want to exchange messages, you can give them a copy of your Pi’s microSD card or the Pi itself.
To ensure perfect security of your messages, it’s necessary to delete pads that have previously been used. If you have printed yours out, a little tearing off and a Zippo lighter is likely to be helpful here. (Other lighters are available.) Otherwise running the shred command on the pad you just used should be enough to prevent recovery.
Both SD cards and Pis are inexpensive also, so if you really feel you have to destroy them once the pads
have changed hands, you can do this as well.
The low cost of a PI is also a great answer to another common criticism, which is that an OTP is usually very difficult to scale beyond two people exchanging messages. If you do decide to form a secret society, it may be best to designate one person to meet each member and exchange pads regularly. That person can then sit at the centre of the web and act as a clearing house for messages, forwarding them between members as need be.
Even using a Pi, however, it is still possible for pads to be intercepted, and communicating can be cumbersome. This is why it’s good to employ some best practices for your OTP.
SUPERSIZE YOUR OTP
For pen and paper OTPs, although technically it’s possible to convert each letter to numbers (A= 1, B = 2, etc) and then add them to the numbers in the pad, this can be rather cumbersome and it doesn’t allow you to send any special characters. One very easy way around this issue is to write a message on your Pi and then combine it with a block of random data using Karl Fogel’s excellent program OneTime, as explained in the walkthrough on the next page.
If you prefer going old-school, Russian spies used to use a device called a straddling checkerboard to avoid long nights struggling with walnut shells. Search online for an image of this and you’ll see that, although there’s a lot of variations, the most common letters are typically along the top row, which means they can be enciphered as a single digit. Less common letters are represented by their row and column — for example, the letter C is represented by the number 21. This also allows special characters such as 62, which switches between letters and numbers. The alphabet can be rearranged in any order you like for extra security if you wish.
Another way to save on scribble time is to borrow a trick from thrifty business owners in the 1800s by using codes for common words and expressions — to avoid having to pay for long messages, Bolton’s Telegraph Code for example uses the number 0446 to represent the classic excuse, “The cheque was sent to you in the last post.” Sadly, there is no corresponding code for, “It was like that when I got here.”
Books like Bolton’s aren’t meant to disguise the meaning of what you say, just to save time. However, if you are going to the trouble of meeting and exchanging keys with a friend, there’s no harm in deciding together your own code names for common people and places. For instance, if the members of your secret society regularly meet by a weeping willow in Hyde Park, you might decide to refer to that location as “Sweden” and to refer to each of the members using animal names. This would mean that if the decoded message “Meet me with Penguin in Sweden” is intercepted, shadowy government spooks will be left scratching their heads. As you meet
to exchange more pads, you can then decide on code names for new people and places.
Any OTP system is only as good as the security of the pads, so regardless of whether you use a computer program or paper, it’s important to destroy both the pad and your ‘plaintext’ message once you have sent a message and both the pad and the ‘ciphertext’ message once you’ve decoded any message you’ve received.
If you use the OneTime program in combination with a large file of random data — say, 1GB — the program will only use as much data as is needed to encode your files — so a 128K PDF will only be around 128K in size.
Each encoded file records the offset in bytes of those used in your pad, so your contact’s version of OneTime will be able to decode it. Drawing on one very large file, however, means you cannot delete pad data no longer in use without removing the entire file. This is why it’s best to split your large file of random data into multiple smaller chunks, which you can delete regularly.
By default, OneTime will prevent you from encoding files with the same random data. See the walkthrough below for more information on this.
OTP also doesn’t have any built-in way to make sure that the person you’re talking to is the person to whom you gave the pads. If you’re using your Pi to send and exchange messages, it’s best to use gpg to digitally sign any messages you send. If you’re using pen and paper, you can use a less secure form of Message Authentication (See ‘Max out your MAC’ on the previous page).
Finally, there is no reason that you can’t use OTPs in combination with other forms of security. For instance, you can encrypt a zip file with a ridiculously long password and send just the password via OTP instead of the whole message. In particular, the OneTime program encrypts files in text format, so you can place these files on a password-protected drive also to boost your security. Feel free to experiment and decide if this is right for you.