M4 enigma project

Still sidetracked, I’ve been looking at the M4 distributed computing project…

Here is a post to their mailing list:

From: “Archimedes Submerged”
To: m4-breakers@bytereef.org
Date: Fri, 10 Mar 2006 17:58:16 -0500
Subject: Redundant hill climbing being done
The workunits I have seen specify start and end keys with the same wheel positions and ring settings. They start with message key BAAA and end with ZZZZ. (Why not AAAA?)

The middle (second from right) wheel’s ring position is allowed to be B to Z (or B to M for wheels 6,7,8). The A position was already tried in an earlier run. Note that the server specifies the middle and right ring positions in the workunit, and the client leaves them constant. (The greek and left ring positions are always AA because there is no difference between changing the ring position and changing the message key for those, since the greek wheel never turns during encryption.)

Now, the ring position on the middle wheel has two effects. It controlls the turnover point, where the left (third from right) wheel is incremented, and it changes the labeling of the message key vs. the actual wheel position. When the starting position (message key) of the middle wheel is such that the left wheel never turns during encryption, then there is no difference between changing the middle ring and changing the middle letter of the message key.

I don’t know what order workunits are being handed out in, but certain groups of workunits include nearly duplicated effort. This occurs whenever two different workunits end up specifying identical path_lookup arrays. (The path_lookup array is constant during a hill climb. It specifies for each letter of ciphertext the permutation performed by the wheels and reflector, accounting for the turning of the wheels after each letter). Fortunately the var arrays (drawn at random) will be different, so the work is not exactly identical. (The var array specifies the order stecker changes should be tried during the hill climb). But it would be better to try all different path_lookup arrays before repeating the same ones. And it would be better to avoid trying certain path_lookup values more often than others.

When does the same path_lookup array arise in different workunits? When the workunits have the same wheel order, the same right ring setting, and similar middle ring settings, and when the turnover point of the middle wheel is not reached before the end of the ciphertext.

Note that when the middle wheel does reach the turnover point (where the left wheel turns), then if the middle wheel message keys differ by n, then n path_lookup array elements (permutations) will differ, i.e., keys B and C would give 1 permutation different, B and D 2 differences, etc. (Different permutations often give different plaintext, but for a given ciphertext, two different permutations at a given position can give the same plaintext. So just comparing plaintext letters — one value — is not the same as comparing the whole path_lookup array element — 26 values).

How could we avoid unintended repetition of the same path_lookup? There are 26 middle ring settings (13 for wheels 6,7,8), and 26 middle wheel message key letters. For each middle wheel starting position, there are 26 pairs (13 for wheels 6,7,8) of ring and message key letters which give the same wheel position but different left ring turnover points. Those pairs with the same wheel position but where the left ring turnover point comes after the end of the ciphertext are all equivalent and should only be hillclimbed once per run.

A workunit includes keys BAAA to ZZZZ, and a specified middle ring setting. There are 26 related workunits, with the same ukw, wheel order, and right ring setting, but a different middle ring setting (13 for wheels 6,7,8). The current ciphertext is 197 characters, 7 to 8 turns of the right wheel. So 18 or 19 different pairs of middle ring setting and middle ring message key letter give the same path_lookup array, out of 26. (Or 5 or 6 different pairs out of 13, for workunits with middle wheel 6,7,8). Only one workunit out of 18 or 19 should do this work. The other 17 or 18 should skip it. But we want to keep the workunits about the same amount of work.

In init_path_lookup_ALL(), if the left wheel turned, then the hillclimb should proceed. Otherwise, we need a reliable way to pick exactly one of the workunits to do the hillclimb. Well, exactly one of them comes within one step of turning the left wheel. So the decision is made in init_path_lookup_ALL(): if the left wheel turned, or if the left wheel would have turned on the next turn of the middle wheel, then the hillclimb proceeds. Otherwise the hillclimb is skipped. This distributes the work among all of the workunits in a uniform manner, because it is the message key letter, not the ring position, which determines if the left wheel turns or would have turned.

From: “Archimedes Submerged”
To: m4-breakers
Date: Fri, 10 Mar 2006 19:24:39 -0500
Subject: re: Redundant hill climbing being done
diff -ur enigma-suite-0.73.1-orig/cipher.c enigma-suite-0.73.1/cipher.c
— enigma-suite-0.73.1-orig/cipher.c 2006-01-18 11:06:35.000000000 -0500
+++ enigma-suite-0.73.1/cipher.c 2006-03-10 19:11:07.000000000 -0500
@@ -144,8 +144,11 @@

/* initialize lookup table for paths through scramblers, models H, M3 */
-void init_path_lookup_H_M3(const Key *key, int len)
+/* returns true if this hillclimb was or will be done on another
+ message key setting */
+int init_path_lookup_H_M3(const Key *key, int len)
{
+ int skip_hillclimb = 1;
int i, k;
int c;

@@ -191,6 +194,7 @@
if (m_offset == m_turn || m_offset == m_turn2) {
p3 = 1;
p2 = 1;
+ skip_hillclimb = 0; /* this path_lookup array is unique */
}

r_offset++;
@@ -219,13 +223,19 @@
path_lookup[i][k] = c;
}
}
–
+ if (m_offset+1 == m_turn || m_offset+1 == m_turn2) {
+ skip_hillclimb = 0; /* this m_mesg is the one which climbs this hill */
+ }
+ return skip_hillclimb;
}

/* initialize lookup table for paths through scramblers, all models */
-void init_path_lookup_ALL(const Key *key, int len)
+/* returns true if this hillclimb was or will be done on another
+ message key setting */
+int init_path_lookup_ALL(const Key *key, int len)
{
+ int skip_hillclimb = 1;
int i, k;
int c;

@@ -274,6 +284,7 @@
if (m_offset == m_turn || m_offset == m_turn2) {
p3 = 1;
p2 = 1;
+ skip_hillclimb = 0; /* this path_lookup array is unique */
}

r_offset++;
@@ -304,7 +315,10 @@
path_lookup[i][k] = c;
}
}
–
+ if (m_offset+1 == m_turn || m_offset+1 == m_turn2) {
+ skip_hillclimb = 0; /* this m_mesg is the one which climbs this hill */
+ }
+ return skip_hillclimb;
}

diff -ur enigma-suite-0.73.1-orig/cipher.h enigma-suite-0.73.1/cipher.h
— enigma-suite-0.73.1-orig/cipher.h 2006-01-18 11:06:35.000000000 -0500
+++ enigma-suite-0.73.1/cipher.h 2006-03-10 19:07:13.000000000 -0500
@@ -4,8 +4,8 @@
#include “stdio.h”
#include “key.h”

-void init_path_lookup_H_M3(const Key *key, int len);
-void init_path_lookup_ALL(const Key *key, int len);
+int init_path_lookup_H_M3(const Key *key, int len);
+int init_path_lookup_ALL(const Key *key, int len);
double dgetic_ALL(const Key *key, const int *ciphertext, int len);
void en_deciph_stdin_ALL(FILE *file, const Key *key);

diff -ur enigma-suite-0.73.1-orig/hillclimb.c enigma-suite-0.73.1/hillclimb.c
— enigma-suite-0.73.1-orig/hillclimb.c 2006-01-18 11:06:35.000000000 -0500
+++ enigma-suite-0.73.1/hillclimb.c 2006-03-10 19:15:15.000000000 -0500
@@ -152,15 +152,19 @@
/* initialize path_lookup */
switch (m) {
case H: case M3:
– init_path_lookup_H_M3(&ckey, len);
+ action = init_path_lookup_H_M3(&ckey, len);
break;
case M4:
– init_path_lookup_ALL(&ckey, len);
+ action = init_path_lookup_ALL(&ckey, len);
break;
default:
+ action = 0;
break;
}
–
+ /* init_path_lookup…() returns true if this hillclimb
+ was or will be done on another message key
+ setting */
+ if (action) continue;

/* ic score */
bestic = icscore(ckey.stbrett, ciphertext, len);