WW2 Enigma Machine

On August 5th, 1857,

a 4,300 km 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.

Please stand by for this announcement.

Germany has invaded Poland.

And it has bombed many towns.

General mobilization has been ordered in Britain and France.

And consequently this country is at war with Germany.

Throughout the world, which is the real cause of the war

that today threatens the freedom of mankind.

(Italian words)

(Japanese words)

The Japanese has attacked Pearl Harbor Hawaii by air.

President Roosevelt has just announced.

(German words)

During World War II, 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 machine 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 the 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.

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 of the time

was called a rotor encryption machine.

We're 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 3 rotors, each with 26 numbers,

the length of the sequence before repeating is 26x26x26.

This is equivalent to having

a list of shifts 17,576 numbers long.

Understand that each rotor position

is equivalent to a location in the 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 6 ways.

Let's visualize the key space at this point.

First, we choose from 1 of 6 possible rotor orderings.

Then we select an initial position from the rotor sequence.

This gives us a key space with over a 100,000 key settings.

Remember, every machine configuration

is a point in this space.

When we select a key setting,

we're 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 II,

one of the most important encryption technologies

used by the German military was known as the Enigma.

It was an electromechanical rotor machine

invented by a German engineer at the end of the World War I.

Each rotor wheel had electrical contacts

on either side with a maze of wirings within.

So at each rotor position, there's 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 into the machine to 60.

This has 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 German confidence that the allies,

even if they have the 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 machine,

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 reused 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,

and this lead 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 crypts.

For a given messaging crypt,

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 attempts at automating the one time pad failed.

If the operators had instead rolled dice

to decide their initial rotor positions,

the starting points in the sequence

could have been uniformly distributed.

This would have prevented

the reverse engineering of the rotor wirings,

and if the Enigma allows the letters to

be encrypted to themselves,

the Bombe couldn't have taken advantage of crypts,

and this would require 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 II

could have been drastically different.