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