Hello All !

A short info: The third (unbroken) Enigma message from Stefan Krah´s M4 Message Breaking Project is broken!

More information will be published soon at the BREAKING GERMAN NAVY CIPHERS project website: http://enigma.hoerenberg.com

All the best

TBREAKER

---

-=> Breaking German Navy Ciphers - The U534 Enigma messages <=-

It would be nice to read about the methods used, let us know when the article will be available.

Here at enigma@home we went through the M4 keyspace in two blocks at over 500 restarts each, those were the workunits available from Stefan Krah's M4 server.

The message was split into two parts, now with the keys known I see that both parts were unbreakable with the method used, considering their relatively short lenght. Well maybe with extreme luck we had a slim chances.

The first block was 72 letters long starting from the beginning of the message, no (real) chances to break. With Stefan's naval dictionary, it eventually breaks after 60 thousands of restarts (average from 10 runs), so we had like 1/120 chances.

EDIT: what I wrote here previously, was partially wrong.
The first message part could be broken here with the length set at 80 or more letters, as it gives reasonable chances to break it with 500 restarts, even with the garbles in the ciphertext.

Now there is one thing that I do not understand.
The second block we ran here - called m4_wr2_msg3 - was the original text from the primary M4 server (the first block was from M4 test server). It starts at the first letter and had a length of 100, so theoretically it should have been broken. I've just checked and it easily breaks when running on a single key (unknown stecker), it should have been broken even faster on normal run, as usually the break can pop up at more than single settings. But somehow we missed the solution.

---

M4 Project homepage
M4 Project wiki

I don´t know the software core from Mr.Krah.

Some thoughts:

- The third message (plaintext) has a very low index of coincidence: 0,04495029! With such a low index, the algorithm(s) has sometimes a problem to find the right "grib" to climb correctly (even with bi and trigram scoring)

- With the first key stroke the machine produces a fast, mid and slow rotor turnover! (Key Ring Settings: ZZDG Message Key: NAQL) Maybe there is a problem within the software to handle this?!?

What do you mean with: "I've just checked and it easily breaks when running on a single key (unknown stecker)..." ?

All the best

Michael

---

-=> Breaking German Navy Ciphers - The U534 Enigma messages <=-

With the message now cracked and read, does that mean that the Enigma@home project is concluded?

Nobody has said so, so am I missing something? I thought that the project was to decrypt the M4 messages - which now seem to be all complete.

I spent some time investigating the source code of this project and my conclusion is that the first 2 breaks were simply the result of luck.

The algorithm is chaotic, the implementation is poor and very hard to understand.

According to my tests, an IC of 0,044 IS A GOOD IC. The current algorithm despises this (LOW) IC and try to find the highets IC possible.

The stecker implementation also is poor, too much fantastic and unrealistic.

INMHO participate in this project using the current software is wasting your time.


Best regards, matajan.

If I understand your post correctly, and your hillclimber breaks the message truncated to just the first 100 letters in a single hillclimb, starting from an empty plugboard, and without needing any restarts, then either your hillclimbing algorithm or the n-gram data it uses for scoring must be better than mine. (I've deliberately refrained from downloading Stefan Krah's software or source code because I wanted to try writing my own.) Since breaking the message with my bombe-plus-hillclimber program, I've done some tests with my own stand-alone hillclimber to see if it could have broken it. Even when using a version of the whole ciphertext with all the garbled letters corrected, it still fails to break the message in one hillclimb; and in 20 thousand random restarts, it only broke the message 567 times. Tests on the version of the ciphertext in Ralph Erskine's letter and on the version I used had much lower rates of success.

It is strange that your hillclimber breaks the message truncated to 100 letters now so easily, yet no solution was found in your earlier runs. I have a few questions about this:
1) Have there been any changes, either to the algorithm or to the n-gram database, between the time that the original runs on that text were done and now?
2) Was there a target score above which a decryption would automatically be flagged as a possible solution, or were the top-scoring decryptions just checked by hand?
3) Are the top results for the original runs on the 100-letter text archived somewhere? I wonder if there might have been at least a partial solution that nobody noticed.

Dan Girard

Dan Girard has pointed me to this thread. Congratulations Dan and Michael
on breaking the message!


A couple of clarifications:

1) This is what Max Domeika of the Intel compiler team has said about
enigma-suite in a private correspondence:

"The code seems pretty straightforward."


2) According to my tests, doing a single-key hillclimb on the *full* message
takes about 30 restarts on average:

./enigma -M M4 -ca -n 30 -k "B:B613:DG:OBQL" dict/00trigr.cur dict/00bigr.cur msg

Date: 2013-02-08 14:34:32
Score: 4638644
UKW: B
W/0: B613
Stecker: BQCRDIEJGHKWMTOSPXUZ
Rings: AADG
Message key: OBQL

bootklarxbeijschnoorbetwazwosibenxnovxsechsnulcbmxproviantbiszwonulxdezxbenoetigeglmeserynochviefklhrxstehemarq
ubrunobrunfzwofuhfxlagwwiejkchaeferjxnntwwwfunfyeinsfunfmbsteigendygutesiwxdvvvjrasch



Iterating over many settings gives an additional chance for partial breaks.

As I remember it, in the M4 project we allocated something like 5-10 restarts
for the *full* message before switching to 100 letter breaks (under the
assumption that letters might be missing).


So it looks like the allocated number of restarts on the full ciphertext
was simply not sufficient.

If I understand your post correctly, and your hillclimber breaks the message truncated to just the first 100 letters in a single hillclimb, starting from an empty plugboard, and without needing any restarts, then either your hillclimbing algorithm or the n-gram data it uses for scoring must be better than mine.

Nope it does not break it in a single hillclimb.
By a single run I meant 500 restarts, which was the target (I believe) on the Stefan's M4 server.
Even then, my post above is wrong.
I did further tests and the stock (unmodified) app just can't do it. Surely every now and then it breaks the first ~100 letters under 500 restarts, but that's just luck, on average it needs a lot more.

It is strange that your hillclimber breaks the message truncated to 100 letters now so easily, yet no solution was found in your earlier runs. I have a few questions about this:
1) Have there been any changes, either to the algorithm or to the n-gram database, between the time that the original runs on that text were done and now?

All the workunits were processed by apps build from unmodified Stefan's sources, and using the dictionaries supplied by M4 project.

The app I used for the first test(s) (post above) may have something stripped down or changed, it was used by the server just to get the output text from machine settings (the text is not returned with workunit).

I started a statistical run to get an accurate average number of restarts needed to break the message with a stock app, I'll wait a couple of hours for results.

2) Was there a target score above which a decryption would automatically be flagged as a possible solution, or were the top-scoring decryptions just checked by hand?

Stefan's server logged all the results which had a score within a certain % from the current best known and the log was available for everyone to read.

Back then my server had a webpage which displayed results sorted by score, with duplicates hidden, so it would be rather hard to miss a break there.
The server also sends me an email everytime a top score changes.

3) Are the top results for the original runs on the 100-letter text archived somewhere? I wonder if there might have been at least a partial solution that nobody noticed.

Not only top results, I have all the results archived (over 5 millions per each M4 run, I'm missing only those that were processed directly by M4 server) and there is no sign of the plaintext in any of them :-(

---

M4 Project homepage
M4 Project wiki

Now that you experts are around, can I again ask the question I posed upthread that has not been answered.

Is that it for the Enigma@Home project? Presumably as the messages are finally cracked there is no more to do?

I hope the project will go on! It is the only real M4 hillclimbing project with enough cpu power to break the M4. (ciphertext only attack)

You need an unbroken message? No problem:

1 VROL
2 NMKA
3 JCRS
4 AJTG
5 SJEY
6 EXYK
7 KZZS
8 HVUO
9 CTRF
10 RCRP
11 FVYP
12 LKPP
13 LGRH
14 VVBB
15 TBRS
16 XSWX
17 GGTY
18 TVKQ
19 NGSC
20 HVGF
21 VAOL
22 NMKA

Full ciphertext:

VROLNMKAJCRSAJTGSJEYEXYKKZZSHVUOCTRFRCRPFVYPLKPPLGRHVVBBTBRSXSWXGGTYTVKQNGSCHVGFVAOLNMKA


Ciphertext without indicators:

JCRSAJTGSJEYEXYKKZZSHVUOCTRFRCRPFVYPLKPPLGRHVVBBTBRSXSWXGGTYTVKQNGSCHVGF

Enigma M4 Thetis key (date: 1.May.1945 / time: 16.30 / incoming radio message / U-534)


All the best

Michael

PS: Up to now, we failed to break it...

---

-=> Breaking German Navy Ciphers - The U534 Enigma messages <=-

Hi All

- I published the original cipher message form on the "Breaking German Navy Ciphers" Project Website

- You will find there a second unbroken Enigma M4 message

Motivation: The Allies never broke Thetis during the war! It will be a challenge, because the P1030680 (VROL NMKA) is very short for a "ciphertext only" break.

Good luck!

Michael

---

-=> Breaking German Navy Ciphers - The U534 Enigma messages <=-

Thanks !

I'm setting up the server already, it's going to take a couple of hours for the M4 workunits (the server needs to know estimated runtime, and there are 3 different sizes for M4 work). I think I'll release first workunits today, first a limited batch to check the server software.

---

M4 Project homepage
M4 Project wiki

Thank you for testing the message!

I'm very excited about the results...

---

-=> Breaking German Navy Ciphers - The U534 Enigma messages <=-

Cool - I'm excited to have work again from Enigma! Still looking for my first 'high-score'. :)

---

A bit of technical info:

I've set the target # of restarts to 2000, with the standard workunit length it gives 91M workunits, which is a lot.

I hope the project won't have to go through them all.

I ran some stats today, I took first 72 letters from a dozen of broken U534 messages just to see how hard it is to hillclimb them with relatively short ciphertext.

Here are the rough number of restarts needed for two different dictionary sets: Stefan Krah's naval dict (the one supplied by M4 Project) and a freshly built dict set from known broken U534 messages:

Text ID: #restarts (naval): #restarts (U534)
1030659: 800 : 400
1030660: 70 : <10
1030661: 80 : 40
1030662: 500 : 180
1030663: 150 : 30
1030664: <10 : 20
1030665: ??? : ???
1030666: 300 : 30 (only 68 letters)
1030667: ??? : 500
1030668: ??? : ???
1030669: 130 : 60
1030671: 10 : <10
1030672: 50 : 10
1030673: ??? : ???
1030675: 4000 : 80
1030676: 20 : <10
1030679: ??? : 60
1030681: ??? : ???
1030682: 3200 : 400

The numbers are for 'single key' runs with preset settings, so in theory the number of restarts needed when going through all the settings should be even lower.
I'm considering adding a second batch with the dictionaries based on U534 text, as it seems to drop the number of restarts significantly for at least some of the texts.

---

M4 Project homepage
M4 Project wiki

Now you can read an article about the break on the BREAKING GERMAN NAVY CIPHERS project website...

Enjoy it!

All the best

Michael

---

-=> Breaking German Navy Ciphers - The U534 Enigma messages <=-