The Boustrophedon Cipher

It's interesting to ponder that today's computers are the descendants of code-breaking machines built during WW2. For while the codes produced by devices like the Enigma Machine were indeed very complex, they were ultimately the result of a deterministic system that was predictable if enough information was known. Although the concept of using random numbers to encode messages was proposed in the late 1800s, it was the Soviets who first put this technique into practice on a large scale with their one-time use pads. It is impossible to break a code made with random numbers that are only used once, because there is only one known (the encoded message), but two unknowns (the random numbers used and the plaintext of the message). It is as though we have the equation a + b = 10 and are asked to find the exact values of a and b. That can't be done without more information. 

The tricky part is coming up with a steady supply of truly random numbers which are only used once per message. The Soviets got into trouble by reusing random numbers, which led to the US reading a number of secret messages later called the Venona Papers. The way the Soviet code worked was through mod 10 math, that is, addition and subtraction without carrying. In mod 10 math, 9 + 7 = 6 because we ignore the carried 1 and 3 - 9 = 4 because the 3 acts like 13. The Soviets used code words with 5 digits. 11111 might mean Moscow for instance. To encode this word, a random 5-digit number would be added, say 98765. That gives a ciphertext of 09876 using mod 10 addition. Decoding the message merely requires subtracting the random number.

One major weakness of this method besides the need to constantly generate random numbers is the need to publish and distribute code books, which can be captured or sold by spies. The rotor-based cipher machines used by many countries during WW2 and the Cold War had a similar weakness. If the Allies had not captured a few Enigma machines, they may not have broken the German codes as quickly as they did. If the Soviets had been more careful in the production of their pads of random numbers, their secret messages would have remained secure. For perfect security, we need a way of generating random numbers that does not require a machine or a code book. How about an equation? Are there any equations that produce truly random numbers? Such an equation would be a one-way function, and their existence is an open question in mathematics and computer science. There are equations and algorithms which are assumed, but not proven, to be one-way. All codes are intended to be 1-way functions unless a shared bit of secret information is known.  

Suppose however there is a function or algorithm which can produce truly random numbers. Furthermore, imagine that this function is simple enough to be memorized so that it never needs to be written down. All that would be necessary to create unlimited random numbers would be the memorized equation and a calculator. I will call this hypothetical encryption technique the Boustrophedon Cipher. Boustrophedon comes from a Greek phrase that means "as an ox turns" and refers to a writing method where lines are written in alternating directions, just as an ox plowing a field switches directions at the end of each furrow. 

If everyone had easy access to unbreakable codes, including all governments and militaries, the value of signals intelligence obtained by spy agencies like NSA would quickly shrink to nothing. It would be like the story of the Tower of Babel, whereby the workers were unable to finish the building project because they all suddenly began speaking different languages. The general effect would be similar to every country gaining a stockpile of nuclear weapons overnight. In a way, we already live in such a world, as the internet and the financial transactions it facilitates are made possible through various forms of encryption and hashing algorithms. Hashing algorithms are presumed to be 1-way functions, yet there is no rigorous proof that they are. When sensitive information like usernames or passwords are stored on a website, they are often stored in the form of a hash. That means two inputs get shoved into an algorithm that produces a unique and irreversible output for each unique pair of inputs. It's more secure to store a hash than a database of usernames, passwords, account numbers, etc.

Only so much military intelligence can be gleaned from metadata. For example, during the Vietnam War, the communists were able to figure out what planes the US would likely use in an air raid. If they detected a surge in radio traffic from Guam, it meant B-52 bombers would be on their way soon. If they detected similar activity from Thailand, it meant smaller aircraft like F-4s would be used. If the traffic game from somewhere out to sea, it meant Navy aircraft were preparing to take off. Since this aircraft attacked different targets, this information allowed the communists to prepare their defenses more effectively. 

In contrast, the side that can break codes gains much more insight into their enemy's plans. The US broke the Japanese codes before WW2, and that ultimately led to a great victory during the Battle of Midway. Navy code breakers were able to correctly determine that the main Japanese attack would come at Midway Island and that the other major Japanese ship movements at the same time were diversions intended to confuse and disperse the US Navy. In a similar way, the Allies learned a great deal about the German fortifications on their Atlantic Wall by reading decoded messages sent by the Japanese ambassador to Germany. He had been given several tours of the complex and sent detailed reports back to Tokyo via radio. The Axis too had some successes in code breaking. The Germans broke the code used by the US Army and so was able to read reports by Lieutenant Colonel Bonner Fellers to FDR. The information from these reports enabled the Germans to inflict thousands of casualties on Allied forces during the North Africa campaign.  

Imagine a world where no such advantage existed. Countries would be far more reluctant to fight. Under US law, encryption systems are classified as munitions and are subject to various export restrictions. Even so, if strong encryption became universal, the end result would be a more peaceful world. Nuclear weapons brought the doctrine of mutually assured destruction. Unbreakable codes would usher in an era of mutually assured secrecy and universal privacy.