So, is the approach to this project to run through all the possible combinations for encryption on the Engima on each message, or is it more targeted? I've been looking at the server status from time to time and wondering about the estimated project completion time. I assume that it's pretty meaningless, more like a "max possible completion time". The solution could come much sooner, no?

When hceyz72 and awgly100 are done, are there plans for another challenge?

Sorry if I'm asking silly questions, as my understanding of the Enigma (and cryptology in general) are very limited. Normally, I don't bother with cryptology or math projects, but I was intrigued by the historic connections.

---

Click Here to see My Detailed BOINC Stats

Hiya Noderaser,

There is a "Hill Climbing Algorithm" which I assume that when a high score is reached, this directs the effort towards rotor combos that would be more likely to successfully decipher the code based on the latest high score, as opposed to just trying every conceivable combination. However, I would think it's possible that this method could steer you down a blind alley if you reached a "high score" for that particular combination early, but it doesn't decipher the code that you'd waste some time plowing through the remaining combos in those favored rotor settings.

So it's a directed "follow the high score" approach, I believe, based on those likely rotor combinations. The backup plan would be the "plow through all possible rotor combinations until you hit paydirt!" approach.....;-)

TJM can correct me if I've mis-spoken.

Mike Doerner

In fact, it's more complicated than that. (obviously)

The military Enigma that was almost certainly used for this message has a plugboard (Steckerboard in German) as well as the rotors. It doesn't take all that long for a modern computer to go through all of the rotor combinations - it is the Steckerboard that is impossible to exhaustively search.

The hill-climbing algorithm works on the Steckerboard, not the rotors. Each work-unit is essentially running the hill-climbing algorithm multiple times, using a random starting position each time, on a relatively small subset of the rotor combinations. The server chooses which rotor positions each client checks (this includes the choice of rotors physically present, the ring positions, and the initial setting) in each work unit.

The hill-climbing algorithm is neither exhaustive nor determinate. However, this technique has found solutions for other messages in a reasonable amount of time - about half a dozen passes over the rotor space. The fact that it hasn't found anything after so many passes suggests, to me, that an alternative strategy would be helpful, but for the moment brute-force effort will have to suffice.

It is known that the message we're attacking now is garbled - probably the radio receiver was not very well adjusted during that part of the intercept, making it difficult for the operator to hear the signal. The two messages that were received later in the same intercept have both been cracked successfully.

Well then does this mean then that if the operator could not understand the message correctly that it will be nearly impossible to decipher...or will just take a very long time maybe. can it actually be done?

---

If it's just a character (or characters) that was written down incorrectly, we may still be able to decipher. If actual characters are missing (i.e. 4-5 missing letters), I'd think all bets are off.

Thanks for the correction on the rotors vs plugboard. Now I know why this is taking so long.....;-)

Mike Doerner

What do the WU titles awgly100/hceyz72 mean? Are they some kind of key sequence, or the first characters of the message, or...?

---

Click Here to see My Detailed BOINC Stats

AFAIK, they refer to the two halves of the message. The message was split as a way to limit the effects of the garbling, for example if letters are missing rather than merely mistranscribed.

The five letters are probably the first "group" of ciphertext - being pseudo-random they will be nearly unique - and the numbers refer to the length of the message.

The steckerboard settings for the two halves of the message should turn out to be the same. The rotor settings should also be fairly well related.

I mentioned that the cracking program does a hill-climb in the "inner loop", that is, a few per rotor setting per pass. There is another possible avenue of attack, which is to run the rotor settings in the "inner loop", and effectively delegate the hill-climbing to the server. This would allow a more sophisticated hill-climbing algorithm to be used, possibly a genetic algorithm.

There is however another possibility - that the message is double-enciphered. This was done for some special messages, such as "Captain's eyes only" stuff (see Das Boot for an example). If so, it will be extremely difficult to crack, not least because there are two separate Steckerboard settings to deal with at once.

You've peaked my curiosity.....if this message is double-enciphered, how will the 1st pass know it's found it?

Or a more basic question, how does this program know it's correctly decoded it if the output isn't in German? I'd always assumed the score was based upon the output matching German phrases.

Mike Doerner

That's precisely the problem. The cracking program *assumes* that the output of a single decryption cycle should be military German. A double-enciphered message would still look like gibberish at that point.

The one thing working in our favour, if that were the case, would be that only a fairly small number of keys were used with "Offizier" coding, which I beleive was the main form of double-encipherment. I don't know whether a record of these keys still exists, though.

Boy-oh-boy! Wouldn't that be a real brute force approach? ;-) So if we could get all the "solutions" on the 1st pass saved, then re-run them through BOINC using the "Offizier" key again would take how many years????? (Or centuries????)

So called "1940's" technology doesn't seem that "obsolete" now, considering many of the deciphered intercepts were based off of clear transmissions of the key and other essential information in order to decipher.

Mike Doerner

So, is the approach to this project to run through all the possible combinations for encryption on the Engima on each message, or is it more targeted?

Nope, it's not brute force, because total number of the possible settings is so high that it makes brute force apporoach 'out of range' even for modern supercomputers.

I've been looking at the server status from time to time and wondering about the estimated project completion time.

It's just estimated maximum runtime for each ciphertext, doesn't mean that it will be broken at the end.

When hceyz72 and awgly100 are done, are there plans for another challenge?

Ask Stefan Krah, the M4-Project admin :-D
But anyway, there are some unbroken WW2 messages on this page: http://cryptocellar.web.cern.ch/cryptocellar/bgac/* and my server has working support for 'local' (non-wrapped) ciphertexts, so we could try to attack them with Stefan's app and another set of dictionaries. One of these ciphertext was already used to test updated app templates (the one starting with KEJNQ).


*At this page you'll also find PDF document Hillclimbing the Enigma Machine which explains how the hillclimbing algorithm works: http://cryptocellar.web.cern.ch/cryptocellar/bgac/HillClimbEnigma.pdf

---

M4 Project homepage
M4 Project wiki

mdoerner wrote:

You've peaked my curiosity.....if this message is double-enciphered, how will the 1st pass know it's found it?

Double enciphered message has a header which is enciphered only once. If the header is long enough, theoretically it should be possible to hillclimb at least part of the message. But it's not that easy - hillclimbing doesn't work if the text is too short, the shorter the ciphertext is the more re-runs are usually needed to find a solution, and below 50-60 letters some of the ciphertexts are probably unbreakable. Switching from ic to bigram scoring for the first hillclimb pass helps a bit.
The hceyz72 workunits are short (72 letters), if the message is double enciphered, theoretically such a short part should be breakable, but that depends heavily on the single encrypted part length. In most difficult cases it could be shorter than 20-25 letters, which IMO would make it unbreakable for the current method.

---

M4 Project homepage
M4 Project wiki

Hi!
I've been following this project for a while, and it seems that our chances of breaking this message are getting lower and lower. The hill climbing may be still successful, but I think the project should start working on other messages. The first ones broke in a few weeks, we might wrap up some more while waiting on this one.

Hi!
I've been following this project for a while, and it seems that our chances of breaking this message are getting lower and lower. The hill climbing may be still successful, but I think the project should start working on other messages. The first ones broke in a few weeks, we might wrap up some more while waiting on this one.

I agree completely. We should add some more messages to the queue. Breaking 2-3 other ciphers would be more satisfying :-)

Why should we? It will slow down our efforts to de-cypher the current message.

---

Because if the message is severely garbled , which was acknowledged, then we might not succeed with it at all. Therefore, breaking ciphers we know to be complete will stand a better chance.

Why should we? It will slow down our efforts to de-cypher the current message.

Possibly, but not certainly.

There are two considerations.

First, there may be a problem with the message because it may have been corrupted when first transcribed. As I understand it, it is possible therefore that it might be impossible to break. Some people might be discouraged to plough on until the end and then to find there was no (positive) result.

Secondly, I crunch for this project because it interests me. That said, I recognise that there is a substantial churn in this and all other BOINC projects. Most, it seems, are more interested in the points. As a basic principle, you can encourage a person to do something and persuade him (her) to keep at it if you give regular and predictable reinforcement in the form of reward. In a case such as ours, you might encourage people to crunch longer here before flitting off to SETI or wherever if there are semi-regular outcomes in the form of messages broken. As someone pointed out here not long ago, the first couple were broken very quickly. Add the Scharnhorst message too. The present one is taking a long time and that must make it more difficult to get & keep the attention of casual crunchers.

Whether to spice the present project with other messages would result in greater overall participation, I don't know. You could run an experiment to see. For example, Einstein@Home has a sub project running in an area that is separate from, but related to, the main endeavour. That seems to work well enough, although Einstein is a much bigger undertaking. It might be possible to allocate tasks to the present project and to a separate message in a ratio of, say, 2:1 for two or three months, then review the effect on overall participation.

Just a thought.

---

"Verloren ist nur, wer sich selbst aufgibt."

That said, I recognise that there is a substantial churn in this and all other BOINC projects. Most, it seems, are more interested in the points. As a basic principle, you can encourage a person to do something and persuade him (her) to keep at it if you give regular and predictable reinforcement in the form of reward.

Oh, Big Deal! Many of the participants are either on a team or several other projects. It would be different if they were only on one or two projects (but not really). The whole reason I've gone though code optimization on 64-bit Linux is for people who stick with the project to gain more computational ground compared to the fair-weather-crunchers and speed up the whole process for everybody.

There's no reason someone couldn't get their own un-decyphered code and run it through the benchmark on their own to see how long it takes to de-cypher a message. Everything has been written for them. This message represents a particular challenge because we don't know why it's taking so long to crack. If it's really double-enciphered, we need all the 1st pass deciphered code to work on the Offizer key-space anyways.

If you aren't interested in de-cyphering the difficult messages, then go to the "Pavlov's Dog's BOINC Project".....Ring! Ring! Ring!....Here's your prize!;-)

Mike Doerner

---

Where did that come from?? Three things.

First. You won't win many arguments by resorting to cheap shots.

Secondly. You have insulted the bulk of the people who pass through the project. Their cycles are as good as yours. Without their "fair weather" contributions you'll be waiting a very long time to find out what the message says.

Thirdly. You haven't answered the question. The question was whether the project would benefit in the longer term if casual contributors had an incentive to come and to stay a little longer. It is a worthwhile idea and one that the people who run the project should take seriously.

---

"Verloren ist nur, wer sich selbst aufgibt."

Whatever.....

Point is, you introduce another message to decipher while we're working on the "difficult" message, you take away computing power. You won't draw enough people to make up for the lost cpu cycles, lengthening the project for no good reason.

When I said fair-weather BOINC'ers, I said what I meant, and I meant what I said. If your only purpose is immediate gratification, you're on the wrong project. Just like investing, "Past results do not indicate future performance." Just cuz the 1st 2 messages broke easily doesn't mean this one will happen this month, next month, next year, or possibly ever.

As for "Pavlov's Dog's BOINC Project" comment, see the immediate gratification comment above.

PS You've changed your system over to 64-bit linux for the Open64 optimized apps, right?!?!? They seem the be the fastest crunch code for Phenom 1's at least.

Mike Doerner

---