[Update – this post from 19 June 2014 applies to version 1.3 of the Cipher – the 20th April 2014 publication. Find that on the IACR archive. The original link now (July 2014) points to version 2.1, which has been updated in the light of this attack method.]
Well, after about 10 days, not full time, I have successfully broken the challenge messages in Handycipher (see http://eprint.iacr.org/2014/257.pdf for the cipher itself). I will do a second post on the method, but for now, the decoded messages are :
M1 : “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 AND NOW THIS I BELIEVE THAT READING AND WRITING ARE THE MOST NOURISHING FORMS OF MEDITATION ANYONE HAS SO FAR FOUND. BY READING THE WRITINGS OF THE MOST INTERESTING MINDS IN HISTORY, WE MEDITATE WITH OUR OWN MINDS AND THEIRS AS WELL. THIS TO ME IS A MIRACLE. — KURT VONNEGUT”, and
M2 : “THIS WINE-SHOP KEEPER WAS A BULL-NECKED, MARTIAL-LOOKING MAN OF THIRTY, AND HE SHOULD HAVE BEEN OF A HOT TEMPERAMENT, FOR, ALTHOUGH IT WAS A BITTER DAY, HE WORE NO COAT, BUT CARRIED ONE SLUNG OVER HIS SHOULDER. HIS SHIRT-SLEEVES WERE ROLLED UP, TOO, AND HIS BROWN ARMS WERE BARE TO THE ELBOWS. NEITHER DID HE WEAR ANYTHING MORE ON HIS HEAD THAN HIS OWN CRISPLY-CURLING SHORT DARK HAIR. HE WAS A DARK MAN ALTOGETHER, WITH GOOD EYES AND A GOOD BOLD BREADTH BETWEEN THEM. GOOD-HUMOURED LOOKING ON THE WHOLE…”, a quotation from A Tale of Two Cities.
The proposed pen-and-paper cipher, Handycipher, is available at http://eprint.iacr.org/2014/257.pdf. It uses a method whereby 31 plaintext characters (the capitals as well as , . – ? and space) are encoded in a 30 character ciphertext alphabet (space does not appear in ciphertext). Between one and five characters encode each plaintext character, based on a binary encoding between 1 and 31 (0b00001 and 0b11111) and there are additional null separators. Of the 30 characters, 25 are involved in encoding symbols and 5 are reserved as null separators.
The cipher is homophonic, encoding most characters with twelve different groups of letters, further obfuscated by having their ordering randomly selected. Characters represented by the single binary digits, corresponding to decimal 1, 2, 4 , 8 and 16, can only be encoded in five ways (the reason relates to the need, on decryption, to identify the row, column or diagonal in order to indicate where the bit sits in sequence – this cannot be done with a singleton point which, without the constraint that it is a column, would be ambiguous). The twelve ways are based on different rows, columns or diagonals of the 5×5 grouping of the non-null characters. The homophonic nature of the cipher leads to text expansion of an average factor of 2.58, although this is both key- and message-dependent. The cipher employs randomness to select the homophone, and hence identical messages under identical keys will still encipher differently. The text expansion means that messages can still decode uniquely.
This is an interesting cipher, with some cunning features e.g. use of binary position representation; obfuscation by random ordering of bits; encryption of spaces and some punctuation; low error-propagation; and the dual key (with/without space in different parts of the cipher). The latter strengthens it, although ultimately the weakness of the cipher is that different parts can be attacked sequentially. The low error-propagation, desirable in a hand cipher, contributes to the attack below.
There is one ambiguity in the specification of Handycipher (v1.3). It could be read to suggest there is an even chance of encoding a character as a row, column, diagonal or first inserting a null. In fact (based on decoding the supplied example), where allowed by the rules, there is an equal chance of encoding a character as each row, column, diagonal or inserting a single null. Since there are five rows, five columns and two diagonals, the odds between them are 5:5:2:1.
The ‘core’ cipher is augmented by a method for having a message key, itself encoded by the core cipher and master key, embedded at a pseudo-random location in the message. Attacking this is the fourth challenge in the paper, as yet unsolved (at least by me).
To avoid any spoiler, the method I used will be in a following post. However anyone attempting to decode C1 should note it is incorrectly stated (although still soluble) in the original paper.
I believe the correct statement of C1 is :
MN.ED FTZBV DTSJR HKV.L CHRCH YGMKV EHSRX UCAUS CAVIZ JM.BV SCH.O HVMYP GXQCS
,GBOQ HFBKT PFBSZ WYPO- FTD?X ZECVL YSCIM NJZHS JEXZW TDF?, YUSXM VYSJH TEXZQ
H.CEJ SRGQB SRHZB S-ZEX CSH.C D?O.U YMGXC YFPTO QACAB GOMU? OCBRK ,NJ.E WMZJ.
-?VKT FLDVB D,HBQ G.NJ, KNCOH BW?J. ZMAOG BTJHS DTFPI DFTZI U?.,O JNM-J HSNKC
TFCNB WU?DO .SHJ. ONFEK UHVCI YGSH. UOLXB UO.FK NYCFN DLTFU .?ITH SJQGH AUCSN
ZAQLZ X-XQE FTRHS NHK?R YPCKE SJHXZ LEQHL C.?.H BOVN. MVDSQ XEIJN .?VK, OUFDT
EIZQE LO?U- .JNOC YU,JT GVYSH JAEGP VMCYX SUEBH ORTJW CYPMO D.URK FTDK? FLVKP
LFTUC S?EVY CKHBO VYMR? K-VWD PLTV? KBHQO FDPT. OURWQ GHOVK R,XQZ NJR?C NKJTZ
SVKAR ?KNZ, G?RKI LPF-Z LEXQU SXCJN .BOG, HBUCS O?UD. CSUGV PCXLC ?VDFT CNBKF
VZTVR KPMCB LDTPF JTK?P FTLHC .TDFQ LZNBF U.O,V ,SYCL DFTBZ DSKVR NJOU, JMNU?
OZSBM JCYUM WN?VK FNKCB SVDNJ FDTAY MPVGO BQHVZ USCLX ZQYPT PSBZE -XSUY VSZCH
JN.VM YR?K, UYXBH G-.KV ?GVYA LSRH. CHAVT JHRUX J-Q-X SMTJF BJ-WS OGDVN E,IA-
QKBJH -VTZW HBJRH WDMIO P,QCV OXJFC VNEOV HBEJ- ?E.WK .USXN JEOLZ VIQC, SYCR-
QZXOQ VRKLH .CVZV YUCOH QBYSX IQXZN MJ.ZL QXZ.M QXZO? L.K?V -?FPD R?KEH RTCBN
VYPGM -E?-? OUZQX V-YSU XHSR. UOCKF LCKRW KZQXP MYGCF -KC.D AFPDA JN,MV GPNKC
HSTJQ GHMGY OLCD. XCYHB -U.O- NZWHU CSDVS EXQWO GJSR- ?QGOB HKUYC LCZSD BR?KS
UCXY- GYPMZ XUDLD TFBSV YMGHQ GOUXC YS-FT .OUBS LCQXZ WQNCK FBI.D ZQXOK EXE-L
DFTA. MGVPY BSZGO QSZO. UNFHV CBGHO Q-GOK V?SJH TGQHU CS?QZ ELBKC XZQBK Z.YCU
ESZVN .JZDB VTFUO .QB,H ,USCV THRJG HB,OB HFLPU DWHSE W.UON M.SCX UKSVB -.ZA?
UOTF? -KNCE R?KHT RWCBN SRT,Y MV,HO BQYUJ N-U.O EZXNC BFZBS LHV.N M.FT? LX.LK
?NFCY GM,YS WBKCW MGYQB GVRKU Y.U?V ,ZEXL QKMNJ RK?SY DPFKT JRHCN BQBEX UXGYM
XCQED .OUMG YSDVR JSOBQ HRJ,C BO.U- HTJSR IDOU. -RJU. OEHRT J,CSY EXZJT ,OUH.
CTSHR JIQXB HOJMR SHNWM BGHQ. CHENB FKU.? TFQZX VQB.U OXYCN JM,YM G?U.Q XDTFA
ZLXQE NJ.CX YVMYQ O?KRV ESNHG BPGYV W.NJ- MYGBD Z.HLI SUC?V RKXE. DKJN. PQBIC
XUSIT JSH?U OVDBW CY?
I can also say my method did not need the hints in the paper – specifically it did not rely on the known plaintext part of C1.