Gilbert Vernam was a digital systems designer from the early 20th century. He invented the stream cipher
, what browsers often use today to encrypt messages exchanged with protected web sites. In his days, however, the mechanism of choice was the relay: an electromagnetic switch. Vernam also described the one-time pad
, and noted the danger in reusing the key stream
What, then is a Vernam cipher
? Is it a stream cipher or a one-time pad? I've seen the term used both ways.
Now we can check the source. Steve Bellovin recently blogged on Vernam's work
, and posted a PDF of Vernam's original paper
. Vernam wrote the paper for an AIEE conference (that's one of the precursors of today's IEEE - Bellovin negotiated permission to post the historic paper).
If we look at the historical description, Vernam does not restrict his cipher to the one-time pad case. Thus, a Vernam cipher in practice might - or might not - be a one-time pad. [revised 9/7/09]
The paper provides a fairly complete description of the technology. Vernam applies it to teletype traffic ("printing telegraphs") that use a "5-level code" typically punched onto a 5-row paper tape. In other words, we have a 5-bit code that encodes 32 different values. There are actually two 30-bit codes: one for letters and the other for numbers, each chosen by a distinct shift value.
Exclusive Or with Relays
Vernam implements exclusive-or
with relays, but doesn't use that term. His description is in terms of electromagnets, signals passing through holes in paper tape, and "bus-bars." There are two input tapes: one with the message and one with the key. When a particular hole is punched, the reader detects a hole and energizes the corresponding relay. This causes the relay's switch to touch the "punched" bus bar. If the hole isn't punched, then the switch touches the "unpunched" bus bar.
The device encodes or decodes by comparing the holes at corresponding locations on the message tape and the key tape. If both relays select the same bus bar (both "punched" or "unpunched") then the output is "unpunched." If the relays select different bus bars, then the output says "punched."
Repeating the Key
Vernam sees a trade off between security and convenience, and the trade-off has to do with the length of the key tape:
With the system as described above, the key tape must be at least as long as the sum of all message tapes used with it, as the messages will lose their secrecy to some extent if the key tape is used repeatedly. The use of a short repeating key may give sufficient secrecy for some uses however.
Thus, Vernam recognizes that some people may be satisfied to simply obfuscate their traffic without really encrypting it. He is very clear, however, that true security demands the use of fresh, random key tapes for all secret messages.
Thus, you can achieve one-time pad security through a careful implementation of the "Vernam cipher," but Vernam realized that not everyone would want to work that hard, or require that degree of security.
He supplies some estimates regarding the amount of key one might need for various amounts of traffic. A standard 9 inch roll of paper tape should handle about 9 hours of message traffic, at 45 words per minute.
To reduce the amount of shared key tape, Vernam proposes a refinement that becomes popular: construct two 7-foot key tapes, with one being one character shorter than the other. Make them into loops, so that they replay once they reach the end. Set them up in their own cipher machine, and use the output as the key tape input for your traffic. Vernam estimates that this gives you about 600,000 characters of key before it repeats.
William Friedman also finds his way into this story. Friedman was more-or-less the founding cryptographer for the US government's activities in cryptanalysis (a term Friedman coined). Vernam credits Friedman with improvements to the multi-tape arrangement that remind me of ideas soon to appear in rotor-based cipher machines.