|
|
|
|
|
|
The Vernam Cipher is based on the principle that the plain text of
a message is 'mixed' with random text from a One Time Pad (OTP).
Because the resulting cipher text is still truely random, it can
safely be sent over the air, without the risk of being deciphered
by an interceptor.
At the receiving end, the same OTP is used to 'unmix' the random
text from the cipher text, which results in the
original plain text.
One only has to guarantee that the OTP is safe, that there are only
two copies of it, and that both copies are destroyed immediately
after use.
The above became possible after the introduction of digital telegraphy,
also known as Teletype,
or Telex.
With teletype, each character is substituted by a digital 5-bit code,
often represented by the 5 holes in a punched paper tape that was
commonly used with telex machines. Digital codes can also be represented
by a series of '1's and '0's, where 1 represents the presence of
a hole and 0 represents the absense of a hole.
This was called the Baudot code.
The OTP was recorded onto a punched paper tape, which was called the key,
or One Time Tape (OTT).
The cipher text was generated by applying the logical
XOR operation (Exclusive-OR)
to the plain text
and the key.
The advantage of using the XOR operation is that it can be undone
with the same operation. In other words: XOR-ing the cipher text
with the key,
would result in the plain text.
In mathematics, the XOR operation is called modulo-2 addition.
In this case, the individual bits of the plain text are XOR-ed
with the key. The resulting bit will only be '1' if the two
input bits are different; if they are equal, the result will be '0'.
Let's asume that the letter A is represented by (11000) and that
B is represented by: (10011). A bit-wise XOR operation would then
yield (01011) which, in the Baudot table, is the letter 'G'.
|
The principle of the Vernam Cipher is perhaps easier explained by
looking at a message stored on a punched paper tape. In the example
below, we want to transmit the word HELLO which is stored on the
plain text tape.
We also have a pre-recorded key tape, with a series of random
characters; in this case the sequence AXHJB.
The contents of the plain text tape are now XOR-ed with the
contents of the key tape.
The result (KMIVE) is a truely random series of characters which
we've stored on the cipher tape.
| |
|
Mixing of the plain text and the key
|
Now let us see what happens if we repeat this operation on the
resulting cipher tape. In the illustration below,
the cipher tape is on the left. It is XOR-ed with a copy of the
original key tape.
The result is the original plain text.
| |
|
Mixing of the cipher text and the key
|
The process of XOR-ing text and key is often
called mixing, and the cipher machines that use the Vernam principle,
are therefore often called mixers or
mixer machines.
|
The above procedure is 100% safe if, and only if, the following
conditions are met:
- There are only two copies of the key-tape,
- Both sides of the communication path have the same tape,
- The key-tape is used only once,
- The key-tape is destroyed immediately after use,
- The key-tape contains truely random characters.
If any of the above criteria is not met, the cipher will become
less secure. This means, for example, that in a battlefield,
sufficient supply of key-tapes have to be prepaired well in
advance of a transmission. If you are communicating
with a station several thousands of kilometers away, it will be
very difficult to supply new key-tapes on a regular basis.
In practice, distribution of key tapes always was a big problem,
resulting in many violations of the above rules. In some cases
a key tape was used more than once, or was inserted the other
way around (i.e. starting at the end). There were even cases
where an operator would take a piece of key tape and use it
as an endless loop, by joining both ends with a piece of cellotape.
|
Although the OTP was, and still is, the only cipher that is
totally secure, many systems based on the Vernam Cipher were
replaced by cipher systems that used a pseudo-random key
generator with a very long cipher period. If both ends of the
communication link configure their pseudo-random key
generators identically, the Vernam principle can still be
applied.
With this method, the configuration of the pseudo-random generator
has become the key
or seed, which is potentially much shorter that the
message itself. Such a short key produces far less distribution
problems, but also results in a reduced security of the cipher.
It all depends on secrecy and the strength of the key.
|
|
|
Generating OTP key tapes (OTT)
|
 |
|
|
It is also very important to consider how key tapes were made.
The cipher is only 100% safe, if the key tape contains truely
random characters. That would be the case if the tape was filled
with noise from, say, a diode or an empty radio channel.
In practice, however, military organisations often used
pseudo-random number generators for the creation of the key tape.
The simple fact that such a generator is pseudo-random,
makes the cipher less secure. There is always the danger that
a potential enemy finds out what algorithm is used to generate
the pseudo-random sequence; either by mathematical methods or
by espionage.
|
The Vernam Cipher is named after Gilbert Sandford Vernam (1890-1960)
who, in 1917, invented the stream cipher and later co-invented the
OTP. His patent (US 1310719) was issued in 1919 and is, according to
the NSA, perhaps one of the most important in the history of cryptography.
|
|
|
Modern use of the Vernam Cipher
|
|
|
|
The Vernam Cipher can also be applied to modern computer systems.
Instead of the 5-bit word of a teletype system, computers use 8-bit
or even longer words. The principle, however, remains the same.
The XOR operation is still at the heart of many crypto-algorithms
today.
|
|
|
Examples of Mixer machines
|
|
|
|
|
|
