-
- [Voiceover] On August 5th, 1857,
-
a 4,300 kilometer-long cable was laid
-
across the Atlantic Ocean.
-
It provided a link between
Britain and the Americas,
-
further strengthening their
social and economic alliances.
-
Now information could be represented as
-
a pattern of electrical
pulses and sent across
-
the world almost instantaneously.
-
Stock tickers and money transfers -
-
these were commercial applications
invented by Western Union
-
which ushered in a new era
of global communication.
-
- [Radio] Stand by for this announcement.
-
Germany has invaded Poland
and has bombed many times.
-
General mobilization has been ordered
-
in Britain and in France.
-
- [Voiceover] And
consequently, this country
-
is at war with Germany.
-
- [Voiceover] ...which is
the real cause of the war
-
that today threatens
the freedom of mankind.
-
(shouting in Italian)
-
(speaking in Japanese)
-
- [Voiceover] The Japanese have attacked
-
Pearl Harbor, Hawaii by air,
-
President Roosevelt has just announced.
-
(shouting in German)
-
- [Voiceover] During
World War Two, Germany,
-
Italy, and Japan were far
outnumbered by the allies.
-
Their only conceivable path to victory
-
was the ability to launch
widespread surprise attacks.
-
So the goal of encryption
technology was to
-
automate the one-time pad
using an encryption machine.
-
Ideally, this machine would
accept an input letter,
-
apply a random shift, and
output the encrypted letter.
-
However, all machines
follow the same principle.
-
They begin in some initial
configuration known as a state,
-
they accept some input,
they do an operation
-
with the input, and then
they produce an output.
-
The operation from initial
state to final state
-
is always predictable and repeatable.
-
So the goal was to
produce identical machines
-
that output a scrambled
sequence of shifts,
-
which took a long time to repeat.
-
(mechanical ticking)
-
Therefore, Alice and Bob could generate
-
an identical shift sequence as follows:
-
First they need to
share identical machines
-
and agree on an initial position,
-
which is defined as the key setting.
-
Then they align their
machines to the same position,
-
and finally cycle through
the identical operations
-
to achieve identical sequences.
-
Now the state-of-the-art
technology at the time
-
was called a rotor encryption machine.
-
We are all familiar with
the mechanical process
-
of an odometer, which takes a long time
-
to finally repeat its cycle.
-
Now imagine we scramble the numbers
-
on the wheels of the odometer.
-
When it ticks forward, a
new shift could be generated
-
by adding up each number on the rotors.
-
This is the rough idea behind
rotor encryption machines.
-
For example, the message,
"Attack Northwest"
-
would be encrypted as follows.
-
Notice how a new shift is used
-
at each position in the message.
-
With three rotors, each with 26 numbers,
-
the length of the
sequence before repeating
-
is 26 times 26 times 26.
-
This is equivalent to
having a list of shifts
-
17,576 numbers long.
-
Understand that each rotor position
-
is equivalent to a
location in this sequence.
-
The initial machine state
is known as the key setting,
-
and the collection of
all possible key settings
-
defines the key space.
-
This key space increases
if the number of ways
-
to initially configure
the machine increases.
-
For example, if the
rotors can be rearranged
-
then the order can be
selected in six ways.
-
Let's visualize the key
space at this point.
-
First we choose from one of
six possible rotor orderings,
-
then we select an initial
position from the rotor sequence.
-
This give us a key space with
over 100,000 key settings.
-
Remember, every machine configuration
-
is a point in this space.
-
When we select a key
setting, we are selecting
-
a starting point in this space,
-
which then determines the
rest of the shift sequence.
-
Give away the key setting
-
and you give away the entire sequence.
-
The security of rotor machines depends on
-
both the size of this key space
-
and the randomness of the key setting.
-
During World War Two,
one of the most important
-
encryption technologies used by the
-
German military was known as the Enigma.
-
It was an eletro-mechanical rotor machine
-
invented by a German engineer at
-
the end of World War One.
-
Each rotor wheel had electrical
contacts on either side
-
with a maze of wirings within.
-
So at each rotor position,
-
there was an electrical
path from every input letter
-
to every output letter.
-
When the rotor advanced,
an entirely new path
-
was defined for each letter.
-
During the war, they continually tried to
-
increase the key space of the Enigma
-
in order to make it stronger.
-
For example, some changes
they made were to add
-
a fourth rotor wheel and
increase the number of
-
possible rotors you could
put in the machine to 60.
-
This had the effect of massively
increasing the key space.
-
Near the end of the war,
-
the Enigma could be set up in over
-
150 million, million, million ways.
-
Guessing the key setting which
was used for a given message
-
was about as likely as
guessing the outcome
-
of 26 dice rolls.
-
This gave the Germans
confidence that the Allies,
-
even if they had a copy of the Enigma,
-
could never check all
possible key settings.
-
For two parties to
communicate using the Enigma,
-
it required that they first
shared the daily key settings.
-
This allowed them to align their machines
-
to the same position.
-
This protocol changed over
and over during the war,
-
but generally involved
distributing key sheets
-
in advance to all operators.
-
Each day, the operator would
cut off the daily settings
-
and this would tell them
the daily configuration
-
of their machines, such
as what rotors to use
-
and the order of the rotors.
-
This key setting was then
to be destroyed after use.
-
However, one vital step
was left to the operator.
-
They were to select a
random initial position
-
of each rotor before communication began.
-
And a very simple mistake was made
-
by some fatigued operators.
-
We make this exact same mistake every time
-
we set a bike lock combination,
-
because we tend to rotate the cylinders
-
only a few clicks from the initial state,
-
or we reuse a common password.
-
This destroyed the uniform distribution
-
of the initial rotor position,
-
and after repeated observations,
-
it allowed the Allies to reverse engineer
-
the rotor wirings completely.
-
The second major error was a design error,
-
not a procedural one.
-
The Enigma was designed
so that an input letter
-
would never encrypt to itself.
-
So given an encrypted letter, such as L,
-
You can now eliminate
the possibility that L
-
was the original letter.
-
What they thought was a strength
-
was actually a weakness in design.
-
(water dripping)
-
And this led to a code breaking machine,
-
initially designed by the Poles
-
and later improved by the
British-American effort.
-
The Bombe was multiple Enigma
rotors chained together,
-
allowing it to rapidly test
different key settings.
-
It took advantage of the
fact that common words
-
were known to be in the original message,
-
such as weather.
-
And these came to be known as cribs.
-
For a given message in crib,
-
the Bombe could scan through all possible
-
rotor positions and
orders in order to find
-
possible key settings
in a matter of minutes.
-
This machine allowed the Allies to read
-
German commands within
hours of them being issued.
-
It was a fatal blow to
their combat strategy,
-
as the Allies could
anticipate their next move.
-
One fact remains:
-
This initial attempt at automating
-
the one-time pad failed.
-
If the operators had instead rolled dice
-
to decide their initial rotor positions,
-
the starting point in the sequence
-
could have been uniformly distributed.
-
This would have prevented
the reverse engineering
-
of the rotor wirings.
-
And if the Enigma allowed
letters to be encrypted
-
to themselves, the bombe could not
-
have taken advantage of cribs.
-
And this would've required the Allies to
-
check the entire key space,
-
which was impossible even
with the fastest computer.
-
Repetition reduced the key space.
-
Otherwise, the outcome of World War Two
-
could've been drastically different.