Singing banana code challenge 2012

Last month the ever-cheerful James Grime (a.k.a. “singingbanana”) of the Enigma Project launched a competition where people were invited to decipher an encrypted message. The prize was a signed copy of The Code Book by Simon Singh (which is an excellent read, by the way).

The encrypted ciphertext was as follows:

VA BT LS EG OT XK PB BH CI FV GA YC QG BP UW IH QD OE DI HL CQ
YC QG BP EI LZ GA GB IZ PS AZ DQ NI CY UY EA AI UA BF BV OV QA
ZS DP QD PG QM PS WL QY DH BD TL VZ PL LW AH GZ BP IM NI KP DZ
QU DH FP CI FV RT SB BP BV XO BE BQ PG KO GE IK KO NA OS DG DG
DA OX PO GE LZ GA OP FL WU PU UT WF BV IC HF EQ SP NA UX DC BV

No information was provided about the type of code being used, except to say that it was a “classic code from history”. However, a crib was available. (A crib is piece of text that is known to be contained somewhere in the original plaintext.) The crib consisted of the phrase “extra large French fries”.

Stop here if you’d like to have a go at cracking this code by yourself. I’ll explain how I did it after the fold.

Cracking the code

The  first thing we need to know is what sort of code was used to encrypt the message. The Playfair cipher immediately came to mind since the letters are arranged in pairs (Playfair is a digraph cipher, so it encodes letters in pairs rather than individually). There is also no “J” in the ciphertext. Playfair encryption is based around the positions of letters in a 5×5 matrix, which means that J has to be combined with I to fit the 26 letters of the alphabet into the 25 cells of the matrix. Although it’s quite possible that a different cipher could have been used (e.g. Caesar shift or Vigenère), it turned out that my first guess was correct.

The second thing we need is the key used to encrypt the message. But of course, this wasn’t provided. Instead, we need to use the crib to work back through the encrypted message to figure out what the key was. If no crib is available, then you could instead try working through a list of the most common words or phrases in the target language, but this is where computer analysis would be more useful (as I will show later).

The crib “extra large French fries” can be split into pairs in two different ways:

ex tr al ar ge fr en ch fr ie s.

and

.e xt ra la rg ef re nc hf ri es

Interestingly, the first of these contains two occurrences of the pair “fr“. The only place this could fit is in the fourth line where the pair “KO” is repeated at the same interval. Let’s try using this as a starting point.

QU DH FP CI FV RT SB BP BV XO BE BQ PG KO GE IK KO NA OS DG DG
.. .. .. .. .. .. .. .. ex tr al ar ge fr en ch fr ie s. .. ..

I won’t describe all the details of Playfair encryption here, as the Wikipedia article does a perfectly good job. However, one of the rules of this cipher is that two characters from the same row or column of the 5×5 encryption matrix are encrypted by replacing them with the characters immediately to the right (if they are in the same row), or immediately below (if they are in the same column), wrapping around where necessary.

If we’ve placed the crib correctly, then the characters “ge” in the plaintext must have been encoded as “PG“. Now since G appears in both “ge” and “PG“, it follows that the encryption matrix must contain the sequence E G P running from left to right in the same row, or from top to bottom in the same column (possibly wrapping around if it goes off the end). Similarly, the pair “en” was encoded as “GE” so the matrix must also contain the sequence N E G somewhere in a row or column. Combining these two bits of information, we can say that the matrix contains some cyclical permutation of the sequence “. N E G P” in one row or column. (Note: I’m using full stops to represent unknown characters, and uppercase characters to represent parts of the ciphertext or encryption matrix. Lowercase letters represent parts of the plaintext.)

Now consider the pair “ex“, which was encoded as “BV“. If E and X lie in the same row or column, then so do B and V, so there must be a row or column containing some combination of these letters. However, it’s more likely that they don’t, in which case the fifth character that goes together with N E G and P is either V (if they occupy the same column) or B (if they occupy the same row). Let’s assume for the time being that V (or B) and X lie in an adjacent row or column. The matrix will look something like one of the following:

B N E G P       V X . . .
X . V . .       N . . . .
. . . . .       E B . . .
. . . . .       G . . . .
. . . . .       P . . . .

We also know that “al” was encrypted as “BE“. We can deduce two things from this. (1) The first of the two matrices above is completely wrong, because “BE” would be the result of encrypting “pn“. (2) The second matrix is not quite right either, because E and B cannot be in adjacent columns (otherwise the corresponding plaintext would have contained either a “b” or an “e“). This leaves us with two possible candidates for our encryption matrix (assuming our earlier assumptions were correct):

. V . X .       . V . . X
. N . . .       . N . . .
L E A B .       L E . A B
. G . . .       . G . . .
. P . . .       . P . . .

Since “ie” was encoded as “NA“, we can also add the letter I to these matrices:

. V . X .       . V . . X
. N I . .       . N . I .
L E A B .       L E . A B
. G . . .       . G . . .
. P . . .       . P . . .

Now let’s see if we can decipher some more of the message. The two candidate matrices produce slightly different results, so I’ll use asterisks to mark the places where they disagree (or where one matrix gives a result while the other doesn’t):

VA BT LS EG OT XK PB BH CI FV GA YC QG BP UW IH QD OE DI HL CQ
.e .. .. ne .. .. .e .. .. .. .e .. .. e. .. .. .. .. .. .. ..

YC QG BP EI LZ GA GB IZ PS AZ DQ NI CY UY EA AI UA BF BV OV QA
.. .. e. an .. .e .e .. .. .. .. .* .. .. l* i. .. .. ex .. ..

ZS DP QD PG QM PS WL QY DH BD TL VZ PL LW AH GZ BP IM NI KP DZ
.. .. .. ge .. .. .. .. .. .. .. .. .. .. .. .. e. .. .* .. ..

QU DH FP CI FV RT SB BP BV XO BE BQ PG KO GE IK KO NA OS DG DG
.. .. .. .. .. .. .. e. ex tr al ar ge fr en ch fr ie s. .. ..

DA OX PO GE LZ GA OP FL WU PU UT WF BV IC HF EQ SP NA UX DC BV
.. .. .. en .. .e .. .. .. .. .. .. ex .. .. .. .. ie .. .. ex

The pair “GA” crops up quite regularly in the ciphertext, and we already know that the second of the corresponding letters in the plaintext is “e“. Since “the” is a common word in English, this could correspond to the pair “he“. Let’s put that in and see what happens:

. V . X .       . V . . X
. N I . .       . N . I .
L E A B .       L E . A B
. G H . .       . G . H .
. P . . .       . P . . .

VA BT LS EG OT XK PB BH CI FV GA YC QG BP UW IH QD OE DI HL CQ
.e .. .. ne .. .. .e a. .. .. he .. .. e. .. .. .. .. .. .. ..

YC QG BP EI LZ GA GB IZ PS AZ DQ NI CY UY EA AI UA BF BV OV QA
.. .. e. an .. he .e .. .. .. .. .* .. .. l* i. .. .. ex .. ..

ZS DP QD PG QM PS WL QY DH BD TL VZ PL LW AH GZ BP IM NI KP DZ
.. .. .. ge .. .. .. .. .. .. .. .. .. .. ia .. e. .. .* .. ..

QU DH FP CI FV RT SB BP BV XO BE BQ PG KO GE IK KO NA OS DG DG
.. .. .. .. .. .. .. e. ex tr al ar ge fr en ch fr ie s. .. ..

DA OX PO GE LZ GA OP FL WU PU UT WF BV IC HF EQ SP NA UX DC BV
.. .. .. en .. he .. .. .. .. .. .. ex .. .. .. .. ie .. .. ex

In the second row, the sequence “an .. he” might possibly be “and the”. If so, “LZ” corresponds to “dt“. In both candidate matrices, we can place the “Z” in one of four possible locations. For our first candidate matrix, we obtain the following possibilities:

T V . X Z    . V . X .    . V . X .    . V . X .
. N I . .    T N I . Z    . N I . .    . N I . .
L E A B D    L E A B D    L E A B D    L E A B D
. G H . .    . G H . .    T G H . Z    . G H . .
. P . . .    . P . . .    . P . . .    T P . . Z

And for the second, we obtain the following:

T V Z . X    . V . . X    . V . . X    . V . . X
. N . I .    T N Z I .    . N . I .    . N . I .
L E D A B    L E D A B    L E D A B    L E D A B
. G . H .    . G . H .    T G Z H .    . G . H .
. P . . .    . P . . .    . P . . .    T P Z . .

Out of these eight matrices, the first looks to be the most promising. That’s because a Playfair code matrix is built by starting with letters from the keyword and then filling in with the remaining letters of the alphabet. This would imply that “T V . X Z” is actually the last row of the matrix (in fact, any cyclical permutation of the encryption matrix will work), and that the middle character must be W (making U and Y part of the keyword). So let’s rearrange things to obtain the following candidate:

. N I . .
L E A B D
. G H . .
. P . . .
T V W X Z

Based on the same reasoning let’s go ahead and put Q, R and S in between P and T

. N I . .
L E A B D
. G H . .
. P Q R S
T V W X Z

In fact, since there is no J and we already know where E, I, L and N are situated, we can also put K, M and O between H and P, and F between D and G. This may not be correct, but we can soon find out by using this matrix to decode the message:

. N I . .
L E A B D
F G H K M
O P Q R S
T V W X Z

VA BT LS EG OT XK PB BH CI FV GA YC QG BP UW IH QD OE DI HL CQ
we lx do ne fo rb re ak .. gt he .. ph er i. wa sa pl a. fa i.

YC QG BP EI LZ GA GB IZ PS AZ DQ NI CY UY EA AI UA BF BV OV QA
.. ph er an dt he ke .w or dw as .n .. .. le iw i. lk ex pt hi

ZS DP QD PG QM PS WL QY DH BD TL VZ PL LW AH GZ BP IM NI KP DZ
sm es sa ge sh or ta .i am ab o. tx oe at ia mv er .h .n gr .s

QU DH FP CI FV RT SB BP BV XO BE BQ PG KO GE IK KO NA OS DG DG
.i am go .. gt ox rd er ex tr al ar ge fr en ch fr ie sr em em

DA OX PO GE LZ GA OP FL WU PU UT WF BV IC HF EQ SP NA UX DC BV
be rt os en dt he so l. .i .n .. th ex .. gm ap ro ie .. .. ex

Well that just about wraps it up. From here it’s a trivial task to fill in the remaining letters:

U N I C Y
L E A B D
F G H K M
O P Q R S
T V W X Z

VA BT LS EG OT XK PB BH CI FV GA YC QG BP UW IH QD OE DI HL CQ
we lx do ne fo rb re ak in gt he ci ph er it wa sa pl ay fa ir

YC QG BP EI LZ GA GB IZ PS AZ DQ NI CY UY EA AI UA BF BV OV QA
ci ph er an dt he ke yw or dw as un ic yc le iw il lk ex pt hi

ZS DP QD PG QM PS WL QY DH BD TL VZ PL LW AH GZ BP IM NI KP DZ
sm es sa ge sh or ta si am ab ou tx oe at ia mv er yh un gr ys

QU DH FP CI FV RT SB BP BV XO BE BQ PG KO GE IK KO NA OS DG DG
oi am go in gt ox rd er ex tr al ar ge fr en ch fr ie sr em em

DA OX PO GE LZ GA OP FL WU PU UT WF BV IC HF EQ SP NA UX DC BV
be rt os en dt he so lu ti on to th ex ni gm ap ro ie ct by ex

Or, more legibly:

Well done for breaking the cipher! It was a Playfair cipher, and the keyword was UNICYCLE. I will keep this message short as I am about to eat. I am very hungry so I am going to order extra large French fries. Remember to send the solution to the Enigma Project. Bye!

Dictionary attack

Just for fun, I also tried cracking this code on the computer.

If the encryption key consists of a single word, then it can easily be broken by a dictionary attack. This involves attempting decryption using an exhaustive list of different keys (i.e., a dictionary). In most cases the resulting plaintext will be gibberish, but if the correct key is used then the original message will emerge. This would take forever to do on paper, but can be done by a computer in next to no time. Even without a crib, a computer could check the decrypted messages for common words and character frequencies. But with a crib it’s simple — we just get the computer to find a key that generates a plaintext containing the crib.

A quick search on Google yielded some C source code for Playfair encryption and decryption, which saved a bit of time. I added some code to fetch keys from a dictionary file and check for the crib (just the word “French”, in fact) in the resulting plaintext, and ended up with this:

/*

Playfair cryptanalysis tool

written to solve the singingbanana code challenge 2012
(http://www.youtube.com/watch?v=laCupCrZNx8)

Based on playfair.c by PC Leyland
(http://packetstormsecurity.org/files/20469/playfair.c.html)

[Task] Find the plaintext for the following code:

   VABTLSEGOTXKPBBHCIFVGAYCQGBPUWIHQDOEDIHLCQ
   YCQGBPEILZGAGBIZPSAZDQNICYUYEAAIUABFBVOVQA
   ZSDPQDPGQMPSWLQYDHBDTLVZPLLWAHGZBPIMNIKPDZ
   QUDHFPCIFVRTSBBPBVXOBEBQPGKOGEIKKONAOSDGDG
   DAOXPOGELZGAOPFLWUPUUTWFBVICHFEQSPNAUXDCBV

[Hint] The following crib is available:
   "extra large French fries"

[Method] Dictionary attack -- try every word in the
dictionary as a keyphrase, and look for the word
"French" in the resulting plaintext.

*/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/* Flags used by playfair() function */
#define ENCRYPT 1
#define DECRYPT 0

/* Dictionary file (plain text file containing one word per line) */
#define DICTIONARY_FILE "/usr/share/dict/words"

/* Max length of word in dictionary (to avoid memory overflows) */
#define MAXLEN 100

#define CIPHERTEXT "VABTLSEGOTXKPBBHCIFVGAYCQGBPUWIHQDOEDIHLCQ" \
                   "YCQGBPEILZGAGBIZPSAZDQNICYUYEAAIUABFBVOVQA" \
                   "ZSDPQDPGQMPSWLQYDHBDTLVZPLLWAHGZBPIMNIKPDZ" \
                   "QUDHFPCIFVRTSBBPBVXOBEBQPGKOGEIKKONAOSDGDG" \
                   "DAOXPOGELZGAOPFLWUPUUTWFBVICHFEQSPNAUXDCBV"
#define CRIB "FRENCH"

/* Prototype for PC Leyland's function */
void playfair (int dir, char *key, char *pt, char *ct);

int main(int argc, char **argv)
{
   FILE *dict;
   char *key;
   char cipher[] = CIPHERTEXT;
   char *plain;
   char *t;
   int tries = 0;
   int matches = 0;

   plain = (char*)malloc(sizeof(cipher));
   key = (char*)malloc(MAXLEN * sizeof(char));

   /* Open the dictionary file */

   dict = fopen(DICTIONARY_FILE, "r");
   if (!dict)
   {
      /* Get name of program from argv[0], skipping path information */
      if (t = strrchr(argv[0], '/')) t++;
      else t = argv[0];

      /* Report error and abort */
      fprintf(stderr, "%s: Can't open dictionary %s\n", t, DICTIONARY_FILE);
      return 1;
   }

   /* Try decrypting the message by using each word in the dictionary as */
   /* a cipher key. Keep a record of the number of attempts and sucesses */

   printf("Initiating search...\n");
   while (fgets(key, MAXLEN, dict))
   {
      /* Remove trailing line break */
      for (t = key; *t; t++)
      {
         if (*t == '\n' || *t == '\r') *t = '\0';
      }

      /* Skip empty lines */
      if (*key == '\0') continue;

      tries++;

      /* Use this word as the decryption key */
      playfair(DECRYPT, key, cipher, plain);

      /* Now look for the crib in the decrypted plaintext */
      if (strstr(plain, CRIB))
      {
         /* Hurrah! The plaintext contains the crib we were looking for */
         matches++;

         /* Change key to uppercase */
         for (t = key; *t; t++) *t = toupper(*t);

         /* Show matched key and corresponding plaintext on screen */
         printf(">>> Possible match for key '%s':\n%s\n", key, plain);
      }
   }

   /* Finish up */

   fclose(dict);
   printf("Finished searching\n(%d hit(s) out of %d attempts)\n", matches, tries);

   return 0;
}

/* ================== Code by PC Leyland follows ================== */

/* Playfair encryption and decryption */

/*
   All non-alphabetics in the input text are silently ignored, as is
   the final odd character if any.  Converting the keyword to the
   keysquare is done in the traditional manner of dropping repeats and
   completing the square with unused letters in alphabetical order,
   despite its relative insecurity.  Hey, this is a toy cipher!
   Anyway, you can always give a keyword of 26 letters in your desired
   order.  The direction of en/decryption is seet by dir: >0 means
   encrypt, <=0 means decrypt.  The input text is always *pt, the
   output is *ct.  The code has been written for transparency more
   than efficiency.  I repeat, this is a toy cipher.

   Copyright (c) 1994 by PC Leyland, pcl@ox.ac.uk

   Permission is granted to make any use of this code as you feel
   fit,as long as you give me credit for writing it and do not blame
   me for any bugs you may introduce.  I take no responsibility
   whatsoever for any bugs I may have introduced.

*/

void playfair (int dir, char *key, char *pt, char *ct)
{
   char *alph = "ABCDEFGHIKLMNOPQRSTUVWXYZ";
   char keycopy[25], pt0, pt1;
   char *ptcopy = ct;
   int i, j, k, lk, lp, rpt0, rpt1, cpt0, cpt1;
   int alphabet [25], row[25], col[25];

   for (i = 0; i < 25; i++) alphabet[i] = -1;

   lk = strlen (key);
   j = 0;
   for (i = 0; i < lk; i++)
   {
      k = toupper (key[i]);
      if (!isalpha (k)) continue;
      if (k == 'J') k = 'I';
      k = strchr (alph, k) - alph;
      if (alphabet[k]   != -1) continue;  /* Repeat char */
      alphabet[k] = j;
      keycopy[j++] = alph[k];
   }
   for (i = 0; i < 25; i++)
   {
      if (alphabet[i] == -1)
      {
         alphabet[i] = j;
         keycopy[j++] = alph[i];
      }
   }
   for (i = 0; i < 25; i++)
   {
      row[i] = alphabet[i] / 5;
      col[i] = alphabet[i] % 5;
   }
/*
 * Copy plain text, stripping out non-alphabetics and converting to
 * uppercase.  Use ct as the buffer, but will use ptcopy as the name.
 */
   j = 0;
   lp = strlen (pt);

   for (i = 0; i < lp; i++)
      if (isalpha (pt[i]))
         ptcopy [j++] = toupper (pt[i]);
   lp = j;

   if (lp & 1)
   {     /* Odd length plaintext.  Warn and truncate */
      fprintf (stdout,
               "Odd number of characters in pt -- ignoring last.\n");
      lp--;
   }

   ptcopy[lp] = '\0';

   for (i = 0; i < lp; i += 2)
   {
      pt0 = strchr (alph, ptcopy[i]) - alph;
      pt1 = strchr (alph, ptcopy[i+1]) - alph;
      cpt0 = col[pt0];
      cpt1 = col[pt1];
      rpt0 = row[pt0];
      rpt1 = row[pt1];

      if (pt0 == pt1)
      {
         if (dir > 0)
         {
            ct[i] = ct[i+1] = keycopy[(cpt0 + 5 * rpt0 + 1) % 25];
         }
         else
         {
            ct[i] = ct[i+1] = keycopy[(cpt0 + 5 * rpt0 + 24) % 25];
         }
      }
      else
      if (rpt0 == rpt1)
      {
         if (dir > 0)
         {
            ct[i] = keycopy[(cpt0+1) % 5 + 5 * rpt0];
            ct[i+1] = keycopy[(cpt1+1) % 5 + 5 * rpt1];
         }
         else
         {
            ct[i] = keycopy[(cpt0+4) % 5 + 5 * rpt0];
            ct[i+1] = keycopy[(cpt1+4) % 5 + 5 * rpt1];
         }
      }
      else
      if (cpt0 == cpt1)
      {
         if (dir > 0)
         {
            ct[i] = keycopy[cpt0 + 5 * ((rpt0 + 1) % 5)];
            ct[i+1] = keycopy[cpt1 + 5 * ((rpt1 + 1) % 5)];
         }
         else
         {
            ct[i] = keycopy[cpt0 + 5 * ((rpt0 + 4) % 5)];
            ct[i+1] = keycopy[cpt1 + 5 * ((rpt1 + 4) % 5)];
         }
      }
      else
      {
         ct[i] = keycopy[cpt1 + 5 * rpt0];
         ct[i+1] = keycopy [cpt0 + 5 * rpt1];
      }
   }
}

(Download C source file)

Note: If you want to try compiling this yourself, you’ll need to make sure DICTIONARY_FILE points to a valid word list. On Mac OS X and most *nix systems, /usr/share/dict/words or /usr/dict/words ought to work.

On my rather old and creaky iMac, this only took about four seconds to churn its way through almost a quarter of a million keys and produce the following result:

Initiating search...
>>> Possible match for key 'UNICYCLE':
WELXDONEFORBREAKINGTHECIPHERITWASAPLAYFAIRCIPHERANDTHEKEYWORDWASUNICYCLE
IWILLKEXPTHISMESSAGESHORTASIAMABOUTXOEATIAMVERYHUNGRYSOIAMGOINGTOXRDEREX
TRALARGEFRENCHFRIESREMEMBERTOSENDTHESOLUTIONTOTHEXNIGMAPROIECTBYEX
Finished searching
(1 hit(s) out of 234936 attempts)

If you recompile the program using “and the” as a crib, it works just as well. This is the sort of phrase that could have been guessed even if no crib had been provided.