Hacking a Digital Photo Frame as a World Clock

So, exploiting these ideas I hacked a Kitvision digital photo frame.  Cut each of the RGB lines on the board and inserted switches (74HCT4053).  Hooked it up to an AT Mega 328P microcontroller running code derived from Peter Duffett-Smith’s Practical Astronomy with your Calculator and therefore calculated the daylight terminator across the Earth that matches a photograph of the Earth displayed on the frame.  By cutting some of the RGB signal at the right moments you get the following :

Image

The trick is to do the calculation during the flyback period, and use interrupts to do the time critical cutting of the picture.  The AT Mega has no trouble keeping up – the quantisation of the jagged terminator line is however the timing fidelity driven by the clock.

I did this in 2010.  I have forgotten some of the details – I think it was cutting the R of the RGB that got the impressive night-time effect.  I also got the eclipse shadow calculations working on a PC but was having trouble shoe-horning that into the AT Mega’s 32k code limit, so left it at that point.  This may inspire someone else.

Quincunx or Bean Machine

Made as a teaching aid for understanding distributions, this is an acrylic photograph holder (two slabs held together with magnets) milled on a CNC mill to provide channels through which small ball-bearings can fall. The milling was done with a V-shaped bit on the inner surface, which closes up to a triangular channel. At each stage, the ball-bearing can turn left or right with equal probability, and as expected, the majority land near the middle, with extreme positions very unlikely.

 

Image

See http://en.wikipedia.org/wiki/Bean_machine

Just a bit of fun.

Mach 3 and spindle speed problems

So, the Conect Cadet Plus is a BBC microcomputer-controlled CNC lathe based on a Myford ML-10.  If you’ve got the same one that I have, it has a motor controller board that looks like :

Image

If you’re trying to get it to work with Mach 3, then it will run extremely raggedly on the defaults.  A little investigation shows the following :

Image

Mach 3’s manual recommends a spindle PWM base frequency of 5-10Hz.  For this motor controller, you don’t begin to get linearity until much higher figures : I’m using 120Hz and it works well.

Hope this helps someone else.  It’s the difference between the motor barely working and working well. 

Breaking Handycipher – the method

Decryption keys

[Update – this post from 19 June 2014 applies to v1.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.]

To cut straight to the chase, the decryption keys for the challenge messages in the Handycipher paper are (with space represented by ^):

C1/M1 : “LFPTDWXCYS^UIEKVR?-QBGHO,ZNMJ.A”
C2/M2 : “GVTZBK.^WQLR?-FMD,AOPXNSJICYEUH”

and the decryptions are in my last post. Refer to that instead if you don’t want method spoilers.

Solution method.

The first point to exploit is that nulls stand as singletons and cannot abut nulls. Using this fact, a relatively simple piece of computer code can effectively determine which of the 30 characters are the five nulls, given a reasonable length of ciphertext. There are five selections from thirty = 142,506 possible groups of five nulls, and a computer can quickly (seconds) test all of them, excluding those that are impossible. For plaintext of length 506 characters (the size of the ‘challenge’ texts in the paper) experiment suggests 10 or 20 possibilities usually remain. For text of length 1000 characters, there is usually only one possibility. Interestingly the challenge texts are helpfully limited to two (for C1) or just one (for C2) possibilities, making them (presumably by chance) slightly easier to decode, albeit that, in my test examples where there are a dozen possible solutions, they are usually closely clustered – e.g. three of five letters are common to all possibilities.

The analysis is slightly complicated by the existence of a run of about 85 characters at an unknown position in the ciphertext encoded by a different cipher (and hence invalidating the characteristics sought) – this is the encoding of the key. However performing the test using a running window excluding a group of this size allows the analysis to continue (albeit taking longer). This process has the beneficial side-effect of largely locating the inserted key, which could be attacked, or simply temporarily removed to continue the analysis on the text. Compute time so far is still a few minutes at worst and could be improved.

The second exploitable point is that adjacent letters in the cipher text have a greater than random chance of being in the same row, column or diagonal as each other, although we do not know which row, column etc or whether it is a row, column or diagonal (or even whether they actually are, it is only a statistical correlation).

By using the identified nulls to delimit the text, we obtain the remaining adjacent pairs of letters. A pair of letters that appears in the list has an approximately 60% chance of lying in the same row, column or diagonal compared to a 40% chance if randomly selected. This difference can be exploited (as can the fact that a repeated pair is even more likely to be related).

A Monte-Carlo hill-climbing optimisation was now used to select the key-matrix with the maximum likelihood, based on the above assumptions about the probabilities of pairs lying in a line. Importantly experiments for the plain text size of the challenge messages (506 characters) showed that greater than 80% converged to the correct solution within a few hundred replications (hill-climb restarts), and importantly and unusually, none found a solution with a better likelihood. Hence the method is highly robust. This is important for an intermediate step in the break, where there is no other confidence that the correct avenue is being pursued.

When used in anger, on an unknown ciphertext, it is clearly unknown whether the solution is correct and exact (80+%) or wrong, but extra replications may suffice to resolve this. This has not been examined, and it might alternatively be the case that some key-text combinations do not lead to convergence, however a cipher where 80% of messages (of length 506) can be broken is broken anyway.

The optimisation can take some time – perhaps an hour for certainty.

While the solution is exact in that there is no more optimum one and the key is directly related to it, it cannot be distinguished by the Monte-Carlo analysis from certain permutations and reflections of itself. While not proven analytically, the solutions seem to be based on a reflection (or not) in the leading diagonal, then any permutation of the four rows excluding the middle one, followed by any permutation of the four likewise columns. These lead to 2 x 4! x 4! or 1,152 possibilities. This is few enough that all can be tested without determining if some should be excluded.

There are two remaining uncertainties. We know the five nulls, but not their ordering, hence there are 5! = 120 further possibilities to test. These could be ignored – the solution will likely be readable anyway if there are five characters that are permuted among themselves, but the extra work factor of 120 is not arduous for a computer and may help the computer get the right solution by improving the correlation with text.

There is a further, more significant factor. We know the key-grid (5×6 = 30 characters), or at least we know it to within 138,240 possibilities (1,152 x 120). The final key step uses the same character ordering with a space inserted somewhere as a monoalphabetic key. We have no way of knowing where this space is from the analysis so far, and, if the space is at the wrong place in the key, many characters may be wrong. However there are only 31 places for the space to be, and the computer can try all. The problem remaining now is therefore to optimise the selection of the parameters such that the result bears maximum resemblance to (English?) text, noting that spaces (a very common character) are included. We have the finite space to search of 1,152 x 120 x 31 = 4,285,440 possibilities, which, while daunting for a human, is a few minutes work for a computer. A non-exact solution (i.e. the wrong choice) is still very likely to be understandable text, merely needing final polishing.

In addition, we have removed a non-exact number of characters for the representation of the key. It is relatively easy to remove the correct number by trial and error once the solution can be read as English text, but this could be vulnerable to error – in the worst case a ‘NOT’ might either belong in a sentence or not!

An interesting exercise on an interesting cipher.

Stuart Combes

Handycipher decrypt

Breaking Handycipher

[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.

Background

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.

Stuart Combes