'; document.writeln(my_chunk); } } // --> --> nb_es007.html : Playing with PlayFair
Playing with PlayFair
A summary of our teamwork
cipher cracker
Not Assigned
November 1999
by The Classroom *
Courtesy of Fravia's page of reverse engineering
fra_00xx
98xxxx
handle
1100
NA
PC
Something new : an essay with most of the content written on the messageboard
There is a crack, a crack in everything That's how the light gets in
Rating
(x)Beginner ( )Intermediate ( )Advanced ( )Expert

Playing with PlayFair
A summary of our team work
Written by The Classroom*


Introduction

During a couple of week, a team has been working to break the cipher contest published by nova.
In order to keep a trace of the whole work we made, I thought it would be a good idea to try to summarize and organize the many post you can find (for a limited time) on The Seeker's Classroom MessageBoard. You can also find the whole thread as text file on his Crypto Contest Info page.
You won't find the solution of the contest in this paper, because we didn't find it. But you will be able to understand the different path we followed and probably the reason why we couldn't find the solution.

Tools required


Target's URL/FTP
nova cipher contest #1

Essay

Part I : Our first thought.

As soon as we started working on this cipher contest, we quickly came up with some first guideline, which would guide us trough the rest of our journey.
The way we should try to break this cipher was agreed by everyone to be as follow :

We also had to clear some Playfair rules. Especially what happen when we 'drop' off the grid ? For example, imagine the following row of a grid : 
A B C D E
we know, from the line rule, that the encipherement of AB would be BC. But what about the encipherement of DE ?
Well, we just wrap around the grid. So DE is enciphered as EA.
Te same apply to the column rule. The last letter of a column is enciphered as the first letter of the same column.
We also wondered what those XXXX were doing at the end. But we quickly figured out they were just filler for the 5 char format used to display the crypted message. So we can suppress them without loosing information.

While discussing those 'details', we also find some 'usefull' characteristic of the Playfair algorithm.
Those are the rules we will use later to reject or accept a given position for a plaintext.

First, a letter can't encode itself. That mean, if you have a digram AB, it would never encipher as something like A? or ?B (? beeing any letter). This is due to the fact that each letter are only once in the grid and that to encipher you always do a 'shift' (letter beside, below, on the other corner, ...).

Second, the enciphering process seems to be diagonalisable. I say 'seems' cause at this point I personnaly missed something important. We discovered that, with a given grid, 2 letters will always encode in the same 2 other letters. Only the order of them can possibly change. And the process is reversible since any 2 opposite corner of a rectangle will define the other 2 corners automatically.
Let's explain this with the following rectangle : 

A B
C D
AD will encipher as BC. If we change the order of the plain digram letters, only the order of the cipher digram will change (but the letters will remain the same), DA will encipher as CB.
Also, if CB is the plain digram, it will encipher as DA and BC will encipher as AD.
This is true, but only for a rectangle. If we had a row (or a column) only the first part of this rules remain true. given, 
A B D C
AD will encipher as BC. DA will still encipher as CB . BUT, BC won't encipher as AD, neither CB will as DA. I missed that point, which have been noticed by DQ btw.

Another rule, discovered a bit later, was the fact that a letter in a plain digram can only become 1 out of 5 others letters. Those 5 letters are the 4 in the same row as the original letter and the one below it. 

? ? ? ? ?
? ? ? ? ?
x E x x x
? x ? ? ?
? ? ? ? ?
Let's say we have a plain digram E?. Well, this digram will always be enciphered in x?. The last rule we used can be defined as follow. A digram containing a given letter will always encode in a digram made of letters standing in the same row/col as the given letter. 
? ? x ? ?          ? x ? ? ?          ? ? ? ? x
? ? x ? ?          ? x ? ? ?          ? ? ? ? x
x x E x x          ? x ? ? ?          ? ? ? ? x
? ? x ? ?          x E x x x          ? ? ? ? x
? ? x ? ?          ? x ? ? ?          x x x x E
Let's say we have a digram E? (or ?E). The corresponding plain or cipher digram will be AB (A, B beeing 2 different x letters).

Once you could define a set of possible position for your crib, you have to try to construct a working grid for each one. For this purpose we invite you to read the following papers which give good example and method on how to build grids :

Part II : Applying the rules.

given those 4 main rules, we started to work on the actual contest. Our goal now was to determine valid position for the few plain text we were aware of.
Those plaintext are : 

STOP
END 
BEWAREICEWEASELS
REDPENGUINFRENZY
STOP was not very helpfull. We don't know his exact position, neither if it appear as ST OP or as ?S TO P?. Assuming that the word stop should appear more than once, we could well notice that 'stop' could not appear more than once as ST OP. Indeed, if it was the case, we should be able to find this pattern at least twice. This is not the case. So we know STOP appear 0 or 1 time as ST OP and 0 or more times as ?S TO P?

We were sure END was at the end. But how ? Two possibilities came up : 

UF BG          UF BG  <-- ciphertext
EN DX          ?E ND  <-- plaintext
In both cases we can notice that U&F should appear in the same row/col as E (3th rule).
Now comes our 2 long cribs. Let's see how they could appear if they start on a even or a odd boundary. 
BE WA RE IC EW EA SE LS
                        <-- no repeating pattern

?B EW AR EI CE WE AS EL S?
   AB ?? ?? ?? BA	<-- repeating pattern to find

RE DP EN GU IN FR EN ZY
      AB ?? ?? ?? AB    <-- repeating pattern to find

?R ED PE NG UI NF RE NZ Y?
                        <-- no repeating pattern
We can see that if beware start on an odd boundary we found the digram EW inverted 4 digram later.
As there is no position in the cipher text in which we can find the correspoding pattern, we may conclude that if BEWAREICEWEASELS is present it can only start on an even boundary.
The same apply to REDPENGUINFRENZY. If it appear in the plain text, it can only be on a odd boundary as we cannot find any pattern matching the even boundary one.

At this time we started to compile some lists of the possible position for each of those 2 cribs.
If we take into account the fact that a letter can't encode itself and the fact that BEWARE should start on a even bounday and RED should start on a odd bounday we find the following possible position for them :

For RED... (39 possibilities) :
9, 3, 5, 19, 27, 33, 37, 41, 43, 45, 47, 49, 51, 53, 69, 73, 79, 81, 83, 91, 93, 95, 97, 99, 101, 105, 107, 109, 117, 121, 125, 127, 133, 137, 139, 141, 145, 147, 149.

For BEWARE... (31 possibililities) :
4, 14, 16, 20, 26, 28, 52, 54, 64, 76, 78, 82, 84, 86, 90, 96, 102, 114, 116, 120, 122, 124, 126, 128, 132, 138, 146, 150, 154, 156, 158.

As an example, here is why position 80 is not valid for BEWARE ... : 

OL QA DF HS FZ WN AI DS     <--cipher text
BE WA RE IC EW EA SE LS     <--plain text
you can see that both the letter A and S encode themselves, what is not possible in a Playfair cipher.

That was already a good sorting, but still a lot of work if we had to try to build grids for each of those position.

One idea was to suppose that both cribs would be present in the message. If this is the case then we would have a repeating pattern. The RE of bewaRE is also present in fREnzy. So we should find the same repeating pattern 4 char after the BEWARE starting index and 11 char after the RED starting index : 

BE WA RE IC EW EA SE LS
?? ?? AB

?R ED PE NG UI NF RE NZ Y?
 ? ?? ?? ?? ?? ?? AB
As those 2 cribs may not overlap and should share the same repeating pattern, we came up with 2 possible position for BEWARE (28,76) and 2 possible position for RED (33,133).
Unfortunately, we could show that there were inconsistency when building grids for those position. But at least we knew (or should have noticed) that both cribs can't appear in the plain text.

Another idea was to reduce a bit more the number of possible position for each of our crib by applying the rule that say there can be only 8 letters in the row/col of a given letter.
As there was many 'E' in both cribs, we used the letter E and checked for each digram containing a E how many different letters there was in the corresponding cipher digram. Moreover, the END crib give us already 2 letters (U&F) beeing in this set of 8.

Unfortunately, it seems that I published this list only for BEWARE, so here is it :
14, 20, 84, 96, 114, 116, 122, 150, 154.

Here, as an example, is why the position 120 was not valid : 

VS SF ZY LU NF FX LK TG    <-- cipher text
BE WA RE IC EW EA SE LS    <-- plain text
If we list the letter beeing in the same row/col as E, we have : VS ZY NF (F)X LK. We can also add the 2 letters (UF) found thanks to the END. This give a total 10 differents letters, what is not possible.

Unfortunately again, we could not build a fully working grid for none of those position. I think it's at that time that we started to become sort of depressed :) And so we started to figure weird tricks they may be used to make this cipher harder than it look. For example, we thought the words making up the cribs may be splitted all over the plain text (like BEWARE STOP .... ICE STOP ..... WEASELS...). We also thought they may appear 'reversed' (BEWAREICEWEASELS would appear as 'SLESAEWECIERAWEB') and other silly thought i don't remember (I say silly now, cause we know the solution:)

Soon after, we wondered if it would be possible that only the REDPENGUINFRENZY crib appear. Indeed, if the agent was under duress, he could have easily said to his prison master that REDPENGUINFRENZY is his recognition code (which it's not, actually), but he would get into serious trouble if he had to sell -to that same prison-master- 2 'funny' codes. So we started working on our lovely penguins.

We went thus back to our list of possible position and tried to reduce it to a minimum. From the previous list, we could quickly reject some of them for obvious reason (same cipher digrams not corresponding to same plain digrams).
Unfortunately, once again we could not build a full working grid for any of them. And, now that we know the solution, we know that the right position (83) was in our list :(

Part III : Endless road.

Anyway, at that time, we were not only depressed but also under pressure because of the deadline coming soon. So we started to try to get something out of the frequencies of the letters and digrams.
We noticed that the most frequent letter in the cipher text were L & F. As the most frequent letters in english text is E, we assumed that E, L & F should stand on the same row. This is due to the fact that a plain text letter have more chance to encode as a letter standing on the same line than a letter standing on the same column. We also noticed some frequent digrams in the cipher (LO, DL, AR, ...). Those frequent digrams most problably correspond to frequent digram in the plain text. Once again, we could find out some probabilities about english text (especially appendix E of the army field manual). The problem was how to 'link' the right frequent english digram with the right cipher digram ... I won't write everything we tried, mostly because i could explain only my attempt, but not much came out from this. The only fact we were almost sure was the presence on the same row of the letters E,F & L.
In my humble opinion, I don't think we could ever find the solution working only with the probabilities of the letters. The main reason of this is that the text length was too short to give significant information about the probabilities of the different digrams. But I have to say that, even if it did not brought a solution, I discovered a complete new way of tackling ciphers thanks those letters probabilities. In the case you have no cribs, this is the only way of working, beside brute forcing of course.

Final Notes
Before closing this writing, I would like to say a few positive words about our work. Even if we did not found the solution, I would like to show that we were not so far from it. first, the position at which REDPENGUINFRENZY appear in the solution was one of our 'possible position'. Second, we came to the conclusion that it was not possible that both codes (BEWARE.. and RED..) were in the plain text. This is true. We also were convinced that BEWAREICEWEASELS was not in the plaintext. This is true too. Maybe we should have worked a bit more with that REDPENGUINFRENZY. Moreover, there is a post of Dan where he give the correct position for RED.... Unfortunately, he could not come to a valid grid with it.
Also, I'd like to try to answer one of The Seeker's frequent question :) ... Why could the controller of the agent not decode his message ? Well, I suppose this is probably due to the fact that our agent should have normally build his grid in a row by row way, but he didn't. He build it in the spiral way.
Personnaly, I think I couldn't build a valid grid for the same reason, I was thinking to a row-by-row grid and not to anything else. Mea Culpa.

I wish to thank all the people working in this team for sharing their knowledge, for their kindness in helping each other, for the way we could make this not only an interesting work, but also a funny game.

team members :
In no order of importance, respects goes to Princess, CSativa, Dan, DQ, G, Jeff, Mersenne, Shade, The Seeker, Tx, Laurent. All apologies if I forgot someone.

Ob Duh

I wont even bother explaining you that you should BUY this target program if you intend to use it for a longer period than the allowed one. Should you want to STEAL this software instead, you don't need to crack its protection scheme at all: you'll find it on most Warez sites, complete and already regged, farewell, don't come back.
choose your way out:

redFravia's (frozen) homepage redThe Seeker's homepage redThe javascript workshop redWhat's new