Breaking Handycipher 2

I presented the solution to the decryption challenges in the first version of Handycipher, published at version 1.3, in this post.  That solution relied on identifying the nulls deterministically, by exploiting the fact that they could not abut one another.  The author has addressed this vulnerability in his version 2.1 posting.  Essentially v2.1 uses short groups of nulls as ‘escape sequences’ after which he inserts non-colinear groups.  This is a good method of frustrating the hill climbing in my first attack, because the climber would not be able to distinguish real correlations (which it exploits) from inverse correlations.  However all this is predicated on not being able to identify the nulls.  If they can be identified, then the solver actually has available the extra information of the inverse correlations.

Although I could no longer determine the nulls deterministically, I was able to determine them stochastically.  On the (assumed) basis that they were all equally probable, I checked for uniformity of the frequencies of all the presumed null groups (there are only 142,506 possibilities).  I also checked for the lengths of the ‘null prefixes’ generated, expecting them to be uniformly distributed in range 1 to 5 – this was actually the more powerful test (I used Kolmogorov–Smirnov for both).  This fairly quickly (after setting a threshold of significance) returns one clearly separated set of nulls for each challenge message.  As before, I ran it with a sliding window to extract the (rough) location of the master key.

I now needed to temporarily remove five characters to be safe (maximum is six, but the last two are co-linear) after each null I had found, to remove the ‘distraction’ letters, and the resultant text had the properties of the v1.3 cipher and could be solved using the code I produced before.  Once a likely key is determined, the message can be tidied by running an actual v2.1 decryption algorithm against it.

There’s another interesting wrinkle : I said I assumed linearity in the lengths of null prefixes.  In fact, they are not linear, clearly having a maximum around length 2 and tailing off by length 5.  Personal correspondence with the author shows that he is randomly using the 31 five-bit patterns (excluding 0000) to select the nulls.  This would indeed produce the binomial-like distribution of lengths seen.  Desite using the wrong filter (seeking a uniform, not a binomial) the divergence from all other character sets was clear enough to detect the nulls.

All of this is facilitated by the author being generous enough to use long (500-600) character plaintexts.  However it is better to know whether a cipher is really secure, rather than just good enough for a short message.

For the record, the keys (space represented by ‘^’) and messages are :

“YUTGRE^KNS-CF?ZLOMVDPBHA.JI,WXQ”

“IT HAUNTS ME, THE PASSAGE OF TIME. I THINK TIME IS A MERCILESS THING. I THINK LIFE IS A PROCESS OF BURNING ONESELF OUT AND TIME IS THE FIRE THAT BURNS YOU. BUT I THINK THE SPIRIT OF MAN IS A GOOD ADVERSARY.  — TENNESSEE WILLIAMS THE PROVERB SAYS —  BORN LUCKY, ALWAYS LUCKY — AND I AM VERY SUPERSTITIOUS. AS A SMALL BOY I WAS NOTORIOUSLY LUCKY. IT WAS USUAL FOR ONE OR TWO OF OUR LADS, PER ANNUM, TO GET DROWNED IN THE MISSISSIPPI OR IN BEAR CREEK, BUT I WAS PULLED OUT IN A TWO-THIRDS DROWNED CONITION NINE TIMES BEFORE I LEARNED TO SWIM, AND WAS CONSIDERED TO BE A CAT IN DISGUISE. — MARK TWAIN”

“XMLUQ?,IJ.^PKVTBNSEZDYWHC-ROAGF”

“MODERNISM AS CUMMINGS AND HIS MID-TWENTIETH-CENTURY COLLEAGUES EMBRACED IT HAD THREE PARTS. THE FIRST WAS THE METHOD OF USING SOUNDS INSTEAD OF MEANINGS TO CONNECT WORDS TO THE READERS FEELINGS. THE SECOND WAS THE IDEA OF STRIPPING AWAY ALL UNNECESSARY THINGS TO BRING ATTENTION TO FORM AND STRUCTURE — THE FORMERLY HIDDEN SKELETON OF A WORK WOULD NOW BE EXUBERANTLY VISIBLE. THE THIRD FACET OF MODERNISM WAS AN EMBRACE OF ADVERSITY. IN A WORLD SEDUCED BY EASY UNDERSTANDING, THE MODERNISTS BELIEVED THAT DIFFICULTY ENHANCED THE PLEASURES OF READING.   —  SUSAN CHEEVER, THE PRINCE OF PATCHIN PLACE”

These are different messages from the v1.3 paper, although the first is again prefaced by the same known plaintext as discussed in the paper.

Advertisements

Encrypting to known text with Tunny

There are several references on the web to the Bletchley cryptanalysts managing to set up a Tunny (Lorenz SZ40) cipher machine to encrypt the standard test phrase : “NOW IS THE TIME FOR ALL GOOD MEN TO COME TO THE AID OF THE PARTY” into the start of the Wordsworth ode “I WANDERED LONELY AS A CLOUD THAT FLOATS ON HIGH OER VALES AND H”, thereby surprising a visitor during a demonstration.  To my knowledge, nowhere on the web is this feat explained, and this post attempts to rectify the situation by reverse engineering the problem.  It’s a fascinating little exercise and worth trying yourself. At face value the ability to do this transformation at all seems surprising.  Tunny uses standard teleprinter characters, i.e. an alphabet with 32 characters (5 holes/bits), and XORs the plaintext with a keystream to produce a given piece of ciphertext (i.e. uses the original Vernam cipher, as envisaged for a teleprinter).  For text of length n, the relevant keystream to achieve the feat will be one of the 32^n that exist. Since there are approximately 1.6×10^19 start positions (also the cycle length) for the 12 wheels, it would seem unlikely that the correct stream could possibly exist for texts of length greater than about 13 characters, never mind the chance of actually finding the right one.  However this calculation is of the correct form for the feat using the fixed wheels of Enigma, whereas Tunny had configurable wheels, each allowing a character by character configuration of the bit to use in the XOR (i.e. whether it is 0 or 1) via cams on the wheels, one per wheel position. Although this configuration would now make matters easy if the wheels were infinitely large, the smallest wheel in Tunny repeated after 23 steps (with one step per character encoded) and even the largest encoding wheel repeats after 59 steps.  The sample text above is 64 characters.  The problem looks tricky. At this point the basic structure of Tunny needs to be explained.  This explanation is derived from the book Colossus by B Jack Copeland and others.  Tunny uses twelve wheels, each with a number of steps per rotation co-prime to all other wheels, allowing a long period before repetition of the wheel state.  There is one of the cams referred to above for every wheel step.  The twelve wheels comprise two groups of five wheels and a control (‘motor’) pair.  Any given character of the 32 available is represented by five bits and encrypted by a further five keystream bits.  The five keystream bits are based on the XOR of the two groups of five wheels.  For the next character, the first group of five wheels (known as Chi wheels) would move on one position.  The second group (Psi wheels) might move on one position, dependent on the pattern from the control pair, but if they do move, they all move together. The two control (Mu) wheels had periods of 61 and 37, with the first always moving, and the second moving if the first had the cam set at the current position.  The Psi wheels move if the second control wheel has its relevant cam set. A diagram of the process is as follows: Tunny

Clearly the XOR between the Chi and Psi wheels means they are individually paired, with each pair affecting a given bit of the five in the teleprinter tape.  The wheel with the shortest period (23) referred to above is a Chi wheel, and is paired with (i.e. affects the same bit as) the longest period Psi wheel, of period 59.  This pattern is standard : the Chi and Psi wheels are paired in reverse order of length.  Specifically the (Chi, Psi) pairs are (23,59), (26,53), (29,51), (31,47) and (41,43). As noted, the Chi moves on every occasion so, while we may freely set all the cams on the Chis (and hence encode from arbitrary text to any other arbitrary text) for the first 23 characters, after that the first Chi starts to repeat; and the next starts to repeat three characters after that.  Hence after 23 characters, unless we are lucky enough to need a repeat, we will need to invoke the pattern on the Psis as a modifier.  Clearly the XOR nature of the relationship means the modifiers can still create all possible patterns (until the psi wheels themselves start to repeat). If we are only looking at the first pair, the sequence can be extended freely to 23 + 59 characters, i.e. 82 characters.  However since the Psis all move together, we are actually limited by a different constraint – effectively the shortest Psi wheel (43) dominates matters, after the shortest Chi wheel (23)) starts it rotating.  The sequence for which we have freedom to dictate the mapping is 66 (i.e. 23 + 43) characters, just over the length (64) of “NOW IS THE TIME FOR ALL GOOD MEN TO COME TO THE AID OF THE PARTY” with spaces included, as they are encrypted too.

A diagram may help :

Tunny2

For defined, rather than arbitrary, text one could achieve slightly longer encodings by exploiting the fact that, if by chance the right keystream is ready, the Psi wheel advance can be deferred.  However with a 1 in 32 chance of the keystream being right for the next character, the expansion of 66 characters by this method is limited. For carefully chosen text one might be able to achieve even longer conversions, but I would suspect not much longer (other than for trivial self-similar copies).  An exercise, perhaps, for the reader. To make things work, we therefore need 23 occasions where the Chi wheel dominates the solution (i.e. can be freely set) and on the remaining 41 occasions the Psi wheel is the one freely set. In terms of a practical implementation, one might proceed with a known (arbitrary) Psi wheel setting and set the cams on the Chi wheels for the first 23 characters such that they perform the desired XOR function at this known Psi wheel setting, ensuring that the Psis do not move for 23 characters (i.e. first 22 cams of mu61 are unset).  The next cam of mu61 should be set, and no further cams need be set.  Note that mu61 will have started to repeat just before character 64, but repeats unset cams.  The single set cam should move mu37 into a position where its own cam is set.  This means that the Psis start (and continue) to move after the 23rd character.  The now moving Psis now dictate the pattern – especially for the 23 wheel, which is immediately repeating its Chi sequence – the Psis must be set to XOR-out the effect of the original Chi sequence.  Overall this pattern (23 with Psi static, followed by 41 with Psi moving) is probably the simplest solution, but meets the aim.  Were the five cams for the first Psi setting to be set to a pattern, rather than all unset, the pattern less obviously encode the start of the text on the wheels. The wheel setting, proceeding from the left, with ‘x’ indicating a set cam are as follows :

Chi wheels

Wheel of size 41 ...x..x.x.........xxxx...................

Wheel of size 31 x..xx..x...xx..x....x.x........

Wheel of size 29 .x.x.xx.x...x..x.x..x.x......

Wheel of size 26 xx..xx.x.x..x...xxx.......

Wheel of size 23 .x.....xx...xx.xxx...xx

Motor wheels

Wheel of size 37 .x...................................

Wheel of size 61 .....................x.......................................

Psi wheels

Wheel of size 43 ....x...xx..x..x......x.xxxx...xx.x.....xx.

Wheel of size 47 .x..x.......x.xxx...xx.x..xx....xx....xxx......

Wheel of size 51 ....x..x.x.x..xxxx.xx...x.x...x.x.xx..xxxx.........

Wheel of size 53 .xx..x.xx..x.x.x...xxxx.x..xxx.x..xx.xxx.............

Wheel of size 59 ..x.x....xxxx..xxxx.x.x.x..x..x.x.x.x..x.x.................

and this, if my implementation of Tunny is correct, changes between: I WANDERED LONELY AS A CLOUD THAT FLOATS ON HIGH OER VALES AND H NOW IS THE TIME FOR ALL GOOD MEN TO COME TO THE AID OF THE PARTY Note that the motor advance was subject to ‘limitations’ in later models (SZ42A and SZ42B) which changed the pattern slightly.  It is not considered that this changes the above analysis in a material way – i.e. the basic ideas are constant.  Some limitations were dependent on the plain text and would however affect the ability to define an arbitrary transformation. As far as I can tell my implementation of Tunny is correct, but I would welcome any observations or corrections.   The code, in Java, is Tunny.   It is a .docx because of WordPress limitations. You will need to copy it via the clipboard to a text file named Tunny.java.