Re: Another history question was Re: Tunny and SIGABA

From: John A. Malley (102667.2235_at_compuserve.com)
Date: 06/09/03 

Date: Sun, 08 Jun 2003 22:26:07 -0700

Michael Amling wrote:

> Don Chiasson wrote:
>
>>
>> A story I read said that at one stage a new wheel had just been
>> introduced and the codebreakers were stymied. The suspicion was that
>> early messages were test messages and one of the codebreakers noticed
>> that the letter X (or some other, it matters not) did not occur. She
>> hypothesized that the message sender was simply repeatedly pressing the
>> X key. This proved enough to solve the new wheel. (Can't remember where
>> I read this, it may have been "Enigma: the battle for the code" by
>> Sebag-Montefore or perhaps "Battle of Wits" by Budiansky.)
>
>
> It's not in Battle of Wits.
>
> --Mike Amling
>

It's in "Decrypted Secrets, Methods and Maxims of Cryptology" by F.L.
Bauer, (ISBN ), Chapter 22 "Concluding Remarks", section 22.2.3 on page
413 in the first edition:

"As well as the linguist Hilary Hinsley nee Brett-Smith and the
linguistically versed mathematician Shaun Wylie, there were also people
with a kind of abstract ability for pattern finding, which in Bletchley
Park supported Banburisms (Section 19.6.4.3): the chess champion Hugh
Alexander and the formally gifted Germanic philologist Mavis Batey nee
Lever. Her abilities can be illustrated by the fact that she noticed one
day the absence of the letter L in a long fragment of ENIGMA ciphertext.
To notice this was already unheard of. But she also concluded that there
was a long filling with plaintext /l/. This lead to the determination of
the setting, to a break, and to the victory of the British fleet over
the Italian on March 28, 1941, near Cape Matapan on the Greek coast."

Truly equally (if not more!) interesting is the connection between this
anecdote and the notion of the Left-or-Right distinguishability of
ENIGMA as a ciphersystem!

Left-or-Right distinguishability is a concrete security notion (see "A
Concrete Security Treatment of Symmetric Encryption: Analysis of the DES
Modes of Operation", M.Bellaire, A. Desai, E. Jokiph, P. Rogaway).
Consider two different experiments involving an encryption scheme and a
pair of plaintexts (x,y). We pick a key at random from the key space.
We offer an Adversary oracle access to our encryption scheme, and let
her give us any pair of (x,y) she chooses. We will do the following.
In experiment 1, the Adversary feeds her choice of (x,y) to the oracle,
and it gives her x encrypted with k : E_k(x). In experiment 2, the
Adversary feeds her choice of (x,y) to the oracle, and it gives her y
encrypted with k : E_k(y). Either experiment uses our randomly selected
key k.

Now here's the test. We pick the key at random, and then flip a coin and
give the Adversary experiment 1 on heads and experiment 2 on tails. Now
if she can tell with non-negligible probability (better than 1/2 by
some factor polynomial in some security factor like the bit length of
the key), then she can distinguish when we are encrypting the left
string or the right string. Since this is a concrete security notion, we
limit our Adversary to some total number of queries on the same oracle,
and some total plaintext length, and some time t to do all of this.

The best she can do is her Left-Or-Right Advantage

    lr E_a(left(.,.)) E_a(right(.,.))
  Adv = Pr[ a <-r K: A = 1 ] - Pr[ a <-r K: A = 1 ]
    A

for some time t, #queries q totaling at most u bits in length.

With a little more work, we should be able to show ENIGMA had low
Left-Or-Right security for reasonable values of #queries, time and
plaintext length in bits. Mavis Batey was such an Adversary!

Take two characters ( a and b ) and makes two equal length strings of
length n, so x = a^n (meaning a concatenated n times) and y = b^n. Take
an ENIGMA machine, any key (rotor settings, rotors, etc) and encrypted x
or y on a coin flip. If the ciphertext output contains a single a then
we know the string is y, because ENIGMA never mapped a character to
itself! And if we find a single b in the ciphertext we know the string
was x, for the same reason. I've not done the math to determine what the
probability of a showing up when we encipher y, or b when we encipher x,
but I'm certain the probability must tend to one for some reasonable
length n of plaintext.

John A. Malley
102667.2235@compuserve.com