Hacking a Digital Photo Frame as a World Clock

By exploiting these ideas I hacked a Kitvision digital picture frame to make it into a Daylight Clock.

By showing a pre-existing map image and cutting the RGB signal at the right moments (using code derived from Peter Duffett-Smith’s Practical Astronomy with your Calculator) you get the following (which looks better than in the photograph) :

ClockResult

The trick is to do the calculation during the flyback period, and use interrupts to do the time critical cutting of the picture.  In addition to the Digital Picture Frame, the project uses just two ICs : an ATMega328 clocked at 16MHz (mainly needing the 32k of program space for the calculation of the sunset/terminator line) and a video switch chip (analog multiplexer) 74HC4053.  The AT Mega has no trouble keeping up – the quantisation of the jagged terminator line is however due to the timing fidelity driven by the clock.

The result can be compared with an online solution.  Note that the time shown in the picture was added by the camera and is BST (GMT+1).

Essentially the Photo Frame shows a map of the world and the ATMega decides which parts should be dark and light and controls the analog multiplexer to switch between the frame’s picture and black. Serendipitous stray coupling between the signals gives the ‘moonlight’ effect of the dark!

The frame used was a Kitvision. Models DPF7SIK or DPF7BKK (respectively Silver and Black) are 7 inch digital photograph frames with 480 x 234 pixel displays. Depending on the model they can access 8MB or 20MB files, with SD/MMC/MS CARD and USB interfaces.

Although all sharing the above model numbers, the internal components differ. Notably certain models (all of those operating at 5V that I have bought) have convenient pads on the circuit boards allowing video signals to be extracted. The one model with a 12V supply was entirely different internally, with no easy access to the signals. Externally the 12V model is distinguished by 4 buttons on the back, rather than 6 buttons on the top and is also the only model to allow the 20MB files.

In addition to convenient access, 5V is of course also convenient to link to TTL logic and to provide power for a microcontroller. Although the three 5V DPF7xxK that I have bought all have different display models, the circuit board is common. Although one of the three also had a different display ribbon connector (while the other two were physically and electrically interchangeable), the circuit board is common – with solder pads for either ribbon, the other being left unconnected.  The circuit board from the rear looks like:

KitvisionBoard

All pads are visible, although the +5V supply label is just out of shot – the pad is to the top left of the ribbon connector. Those of interest are :

Pad Signal Wire Description
5VP +5V Purple +5V
GND 0V Black Ground
VR Red Red Analog RGB – RED
VG Green Green Analog RGB – GREEN
VB Blue Blue Analog RGB – BLUE
VCOM RGB common Brown Square wave to provide common level for RGB signals (presumably zero DC offset)
CLK Clock Grey Pixel clock ~10MHz square wave
STV Start Vertical Orange Pulses before 1st display line, at about 55Hz
CKV Vertical clock Yellow Pulse at new horizontal line, about 15.6kHz
OEV or STH? Output enable vertical White Returns screen to default in interval – allows DC to stabilise.

The image below shows the connections to the pads on the rear (left hand side) and the front (right hand side).  On the front, the RGB connections are made to one end of a SMD capacitor’s pad after the capacitor was removed (achieved by snipping with pliers).  The whole is later held in place with epoxy.  Effectively the 4053 switch replaces the capacitor.

Connections

By using an ATMega328, one can connect the STV pulse direct to the INT0 input (PD2) which will trigger an interrupt routine whenever the display is about to refresh (rising pulse).  As can be seen, the routine can set the display row number to zero, and also rely on the signal to increment an accurate clock (JulianFract is a time variable which runs from 0.0 to 1.0 over 24 hours).  STVHZ is about 60Hz. This means there is ~17ms for all horizontal lines to be painted – which would allow 262 lines at 64μs per line (see below). The display has only 232 lines allowing some spare time (~2ms).

STV pulse width (while high) is measured at ~6.4μs; the manual seems to have 64μs. Curious.

AVR C Interrupt code for the vertical pulse is:

ISR(INT0_vect) // Highest priority. Used for STV - Vertical start pulse
{
// STV measured at ~6.4 us width high pulse approx every 17ms i.e. 60Hz
// STV line is ORANGE and connected to INT0 - PD2 on Atmega8/328
row=0; // Measured at 1.75us at 16MHz
Now.JulianFract+=(1.0/(24.0*60.0*60.0*STVHZ));
}

The CKV pulse can be connected to INT1 and will trigger whenever a new row is about to start. The CKV signal looks like :

CKV

CKV is low for about 52μs, during which there are 480 pixels of about 94ns each (48μs total). CKV is high for ~12μs, during which there is ‘flyback’.  Hence the period is about 64μs, i.e. 15,625Hz.

The signal can be used to control what we display. In this example the idea is that any given row will display either some day, followed by night, followed by day – or the reverse (Night-Day-Night); with special cases all day or all night.

We have previously (outside the interrupt) calculated two array of values, two values for each row. One signifies the point at which darkness should start, and the other the point at which the day should start. Whichever is smaller dictates the starting point – i.e. to draw day-night-day specify the -night-day part which implies the initial day- part.

VCOM looks like this (the even square wave) and switches polarity at every STH pulse (i.e. for alternate rows) as shown.

VCOMandSTV

The AVR C code for processing rows is:

ISR(INT1_vect) // Second priority. Used for CKV - New row
{
uint8_t i,t3;
// CKV measured as 3V p2p. Square wave with approx 1:4 mark to space
// Measured 12us mark; 52 us space, 64us period = 15.6kHz
// CKV line is YELLOW and connected to INT1 - PD1 on Atmega8/328

// Original picture shows when PORTC 0..2 are HIGH

// Note that it is quicker to use PORTC = 0x07 and PORT C = 0;
// than PORTC |= (0x07) and PORT C &= ~(0x07)
// Logical to do this because we know we're not using the rest of PORT C
// and timing is crucial

row++;

t1=t1s[row]; // Copy to fixed variable to avoid repeating row index
t2=t2s[row]; // calculation – consistent speed

// Use -Os for this speed

if (t1 < t2) // Day-Night-Day
{
if ((t1+1) == t2) // Immediate Day
{
PORTC = RGB;
return;
}
PORTC = RGB;
t3 = t2 - t1;
_delay_us(US_DELAY_LHS);

for (i=1;i<t1;i++) __asm("nop"); // Delay
PORTC = BLACK;
for (i=1;i<t3;i++) __asm("nop"); // Delay
PORTC = RGB;
}
else

[Similar code for Night-Day-Night]

I also got the extra code to display eclipse shadow calculations working on a PC but was having trouble shoe-horning that into the AT Mega’s 32k code limit, so that remains a work in progress.

Advertisements

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