M4 project

Dear All, I thought you might be interested in this:

The M4 project.

I was made aware of this project by an email from David Crick on 26th
February and I looked at the M4 Message Breaking Project web site.

The project is to break and decipher some previously unbroken 1945 U
Boat messages found by Ralph Erskine in the American National Archive
(NARA) in Washington.

One of the four messages has so far been broken.

The method suggested is a brute force attack on the complete Wheel
order, Wheel starts and Steckers search space using deciphered letter
frequencies. The search space to be partitioned up on a very large
number of private PCs.

My immediate concern on reading about the attack strategy was that it
depended on "hill climbing" on Steckers.  I am not convinced that this
is possible.

When setting up the "anoraks" section on my codesandciphers.org,uk web
site in 2003, I included a page on Alan Turing's proposal in 1939 for a
cipher text only attack on German Naval Enigma. He proposed a machine
which he called "The Rack" to automatically decipher an intercepted
cipher text at all possible Wheel orders and starts, looking for a
natural language distribution of the deciphered letters. I don't think
the Rack was ever built but I constructed a virtual Rack to investigate
how good it might have been. It is on my web site.

In response to the M4 proposals I revisited the virtual Rack.

Taking Oliver Lawn's German letter frequency analysis from September
1941, I set maximum count to be the sum of the counts of E, N and X, the
minimum count to be the sum of C, Y and J.  A decipher is judged to be
significant if max > min * f.  A correct decipher gives max / min > 8 so
a factor f of 5 or 6 weeds out most of the noise.

But the problem is Steckers. Turing stated that nearly all Steckers must
be known for the Rack to work. My 2003 analysis showed it would work
with one or two wrong out of 10, but it depended on which Steckers were
wrong.

My re-visit of virtual Rack reveals the following on 3 wheel German
Army/Air Force signals.

No Steckers does not give a hit on the correct wheel order at a factor
of 4 or 5. In one instance it gave 21 wheel order hits out of 60 but not
the correct one.

I then tried EC NY XJ Steckers. Similar results. Next mid score letters
L, D, F and O. No clear advantage in revealing the correct wheel order.
But the really telling result was where the correct steckers were used,
giving a correct answer at 7 max/min ratio. On removing one Stecker, CG,
this rose to 10. With 3 Steckers removed the correct result was 6:1 but
with CG included no correct result came out.

This gives a clear indication that Stecker hill climbing probably wont
work. 

I will continue trying various Stecker starts to see if the correct
Wheel order can be revealed. If it can, then I think it still leaves
exhaustive search on Steckers, a very big job indeed.


I have updated the rack.zip file in www.codesandciphers.org.uk/anoraks/t
ools

It is not the easiest to use and I will put up a new how to use page.

regards-- 
Tony Sale