Known Algorithm Attack: Caesar Reloaded

Question

Most of the puzzles here revolve around an unknown algorithm attack. That is, you are given an enciphered piece of text and asked to decode it (and often given a series of hints which describe how the enciphering was done), or you are given a set of plaintexts and enciphered texts and asked to describe the manner in which the text was enciphered. In this puzzle, you will be asked to do something different. I will describe a custom cipher, and give an implementation, and then ask you to decode an enciphered text. Hopefully, if nothing else, you'll learn a bit more about cryptographic weaknesses.

Just so you are sure, any method of deciphering the text is fine. If you want to write a program to bruteforce the cipher, go ahead. With that in mind, let's begin...

Part 0: A Basic Caesar Cipher

Unless you've been living under a rock, you'll know about the basic Caesar cipher. But for those of you who like living under rocks, here's a basic rundown of how it works (note that the method may seem convoluted, but it's useful for later):

Start with your plain text.

Attack at sundown, when the enemy isn't looking.

Then remove all spaces and punctuation (this is not strictly necessary, but we'll do it anyways)

ATTACKATSUNDOWNWHENTHEENEMYISNTLOOKING

Decompose the text into numbers, A=0, B=1, ...Z=25:

0 19 19 0 2 10 0 19 18 20 13 3 14 22 13 22 7 4 13 19 7 4 4 13 4 12 24 8 18 13 19 11 14 14 10 8 13 6

Choose a numeric key between 1 and 25; we'll choose 7. Then add the key to each number and take the result modulo 26, that is, if the number exceeds 26, subtract 26 until it's smaller than 26 (e.g. If you have 30, then 30 modulo 26 is 30-26 is 4).

7 0 0 7 9 17 7 0 25 1 20 10 21 3 20 3 14 11 20 0 14 11 11 20 11 19 5 15 25 20 0 18 21 21 17 15 20 13

Then convert back to letters:

HAAHJRHAZBUKVDUDOLUAOLLULTFPZUASVVRPUN

To decrypt, you do the same, except you subtract the numeric key. That said, this cipher is very easy to break. To prove it, here's a challenge:

Challenge^* 0: Decode the following:

SQUIQHMQIDEJQLUHOWEETSHOFJEWHQFXUH

_{* Note that this is a gross misuse of the word 'challenge'.}

Part 1: Keyed Caesar

Now we've got that out of the way, let's get on to something more interesting. The problem with a Caesar is that it's too easy to bruteforce. Once you know it's a Caesar cipher, you can easily check all the possibilities. So let's fix that, by introducing a longer key. In part 0, we had a single numeric key that was applied to every letter. What we're going to do is have a group of keys and apply them in turn. For example, if we had the keys 4, 19 and 8, we would shift the first letter 4 places, the second 19, the third 8, the fourth 4, and so on. In this way, one can not simply check all the possibilities^**, and a more elegant approach is needed to crack the cipher.

_{** Well, you could check all the possibilities, but that would be really boring.}

Here are three implementations of this cipher in different languages. If you can't program, or don't program in any of these languages, don't worry: The implementations are heavily commented, so just read the comments.

• PHP Implementation
• Javascript Implementation
• Python Implementation

However, this is still a weak cipher, and you can prove it by decoding the following:

Challenge 1.1: Length 2 Key

QGUUEBBADCJDJSEEIJEPLAHUWKEZRASWKOUEJEIWBIEOJPXAIIQAQOQJENCWBYQAIWHYYLXAHWDZOKKYQJIPYHBXHQJAVKHYUPXASKCXYJQPYKDXKPYBOKKOEHLATPXEIWDWBUJESWBHOUEQQNUZEEDCMABHRASWKOUPXAIWCAJASDDEGQUYQJRAQLFHYATPEXHAQGJDYOSEFDUNMEJDQJOGUUBADCJDXAHAIOEIUIENUPUTJPXAGQYYAXHKMJVKNFKIFATKLAHPXABWPUTKW

Challenge 1.2: Length 6 Key

EWEVDKHHVYEKIKELPNUWXXGRAOYFXOMESNMDAZXAXXQVXPTUFRQTDAMSSBGPUVABMDRREFBJSDXMAAYRYMANTHXHKEODRWEAFWIKLBUOPXWLDLQTKEXBABMDQAGETIMWMHGLALRMLZAQXUXHUHZXTSAUHHYEFWLHNCTWLXMNGWLBLPTDXBMLDRJXLOQVXATPMSPTNOUEPXXTOXWXBOMVEMBORDGMHNKVYULPUWYMXBAUTXKBAUQTGYQWLTMYAQGXIPUVSYVKGUWXVKYSPXMANXRDUUMQCLMNQWGAHBFKIBFWSLRTMEAQLHPAHHVBMEEEYGDPTDXATOEXVOBRQGZBKPGDPERQZFLTGCQGJKHIIKIGBPIDWYBNEWTKHLAVIWGAMUPRAWXIEVXJFXVRTCAECVTQEWMVFWPPIGMKUWWIKAEHRMBJODVGTPURRBGOFDGDHRQUJEHSEYMEXAJFYLXOEWEVDKHHVYEKIOSOXOGVMGZXUJAHKZEOMDXQZGIFHJEWVTMEHHRXLOMQHNGLDRTHKPURRTUHQQILLWEDVXLQXWMMPNUWILEEWHEFXJFDPEREXOTXKOAQABMDMWLXLWGUYLMDMWKHMIQWLBGGUQKIXNTDTLLPMFOHOADIPHPOBRYMLWXOGETOEHWHYLGIJXKUMESNMEFVQHKWXYMZHNIHPELQDHMMAWEVSFXDAZJHNJPWLXYKDWMMNZQWSXGZGUIHNNAQKHBJSKYFBHUDXBHJMQHWBOORQYHNFDXMAATDRWLKRLXLIWFVMXLXGWXAXHMUKXKLALRMBOFKEMLPMFOHOADIPHPSDLXXLWXRXHYHAQKLMWFHQXGPEWLTMIQDRIKWOWMVTHXBRHMDUQKPAWFVWGXWWBMLMDMWMMVKZVXKNYFVXAHOQVXTMAYHRMLEZVYVAWIDCMAWFLXGXRQUSVVQDVXHBPEUITWADVXHTJMOCSXPTHQTGWXBWBLSAXPWTHYRWMVADWEBGHKLRWBYMWIMAWFVXTVGAYIKYHAZWPXWDVXATPUWWTEEHLRZUKPKMLTPFYEHYLQDGXTJPQSGOEAOIGVAOOITKHKLXLEEHLRZBJMZSKEZAIQTDANHPBXRQZMMABXRAXKOMQHUXHXVEGWHQSVXVDMXRLTJPPEZBYRUSZLSUWLYNJZBPBMPXHLTMONDGDBJFKIKXWXZSKEZFKIPAKXHSYLPMFOHOADIPHPONUYMBOTZSKEZHLIPFWKSIKAWBVFXXTBUILLAPLRHGAELQIEAIRVWMDMWAHKZUVWTWEEPPXMIQHBIEWUQAXFQEWAHKGFRKXMDQUXHWKXHSNMWOHVUBYOUMMBYUVQHYOFDGDHRQUJEHSMQHBMOBKEETJJRJVKWLBVTWEODPBLIAUMXGPQGHBLYUSPXLSTDXVTJKRYWHPAKIEIBAUWMTNFHVLRKGPMZAPIDRMMKBOEGMIMUOXKOFKEMWARLRXMDQOMFBPERJPAWFLWKTRUQKTGZIKEMBOZRXBIADVSGTHXBHXKEHHKKXWFVEMBORDGMBKZLRWHEZJXATPERVMHBFKMGZXQFENLAUWQTROQHQTMBUUWMMDMWABMDUQELAKDWTXKEAGSYMEYHWMTYWRZXKBXRALEEQVABEHNHIQIKEHHTGZFKIMKQFKGTGXQVTKXWPZLXGSQGILVAZGXHWAFDMELDAZIOXNIHWXXPTDXBMORXRVMEAQEKBAERJMXJDHZXKOQWLXGKDPEEINAFILLKRLRMXNBUIMTPURRMAWFLWMAAKYEENAFKINGOMLHHOADWLXLWUGXAXKNVGNKAAYIKMDQFPXTN

Challenge 1.3: Unknown Length Key (<= 7)

OGRKHXFTLEUHKWZSFKLYKBLAQUOMZRTJZNNZFPDNZBUATOOGAEOTVQEXFGPYEMXWETJGCHTMXOFEPNNRCJEHVTHMKCKSLKAGMEUVTWXOGZIXAAUSFKHYBFKHTUHBGONXPBKOLQEKUAWGZIXUYKBKJJNBMUBAXTJGZIXIGUMXWETKNOGSBDEAMBLJVJFWNVBFUUEKNTNXGCHQGNPPPUKJKYUUJVABLMTJTABZAFUSMKBRTBOAZBLYBUMTOJNBMUBAVLAJOMEHVQFEUQXBBJGNFBNZUUBRNZJHJVQOHSVZDTJOKITNQZPKAFOTMOYOEBJTOOTSVZURVVTHXNQOTLEAMQALBXXAWGKWXNYGOZQNMFIABVMXHBBFMKUGUXKAZIBOLKBKEIKCXAAMVBHGEPYPUOTFUFKMYEAZIXLNYUXOCKDBWYRZUAPGVLALUVDJBCGKKZZIXXBZUHIBLZHQENBVGRXIXWEZUAWGEPNNTOWXJYGOZQNMFYNNSFPKEQMBXEGSRPRDUXZVZPKDBYUBJTKOOEEUOFAAZFKCBTPFEPQFRXBGSWOGGOWEAMEXOXKUVEFYPHKBSVVDOKUMAEZITJJNBMAIKSGKBHSNXOOTAPUKZKAYKBKJVTHUQGVMXWFKSXOVYUCQFZMXPGNFFBVXTMHRGSGOBSFMDVTHTJLZIBJTZPZAGNPHGRJPGPBZIXLBZFGPVGMHBCXPZNNSNBJTGOWPUKORKHIBGKSLFKPBYIHSGNFFPUKUKQRRJZDGRBMAEOGPDNZUAALXFEANXOBJTOTMNHRZLKGKSKEORFMDRTUAALCJEHXKFICRZUBJTYUNYXGOWWFQZHQJNFMDRXUAAEKTTJRGTBAECBRPUKOTJQUOEUGNFGUBADTJHTMXWFNZHQEZSXWGOTXKAVVKASAOVPVUOTHCXPZNNSNBJTUSAUTKOBYZGDKKFUSPDNZFOAEGMLKLUVKACXPUWORZGKGZIXKARZINBMSTIZKSMDRHFZEATFKEFZBEGVTHMKZGORLEUHKWZSFKORYQXYVGMEUVTPGHVTFYKEANLWEKQKKOGCEUZGLBJTYJFEYGSLJVJFKAZGSDORDDXLGZIXUEKTTUVTHMDNZUAAVXPPJSGWHNVZFEWAMVTCRRJUNNXZYNNSFPKEQUXTGKEBPBXIHOGOOZAABJKKASFGPVYUAAOKTMAIGIADUNIAOBTPPPUKCXCVTOXNVYSXWYRZVKALVLAQZIXUEKSXLRGUXZYEUHHQZITPGNFBNTOWXJPNPBYRUGMKBRTBOFUNXDBCUXNEOCEARBFGPUUVZDGNFRORKNMKOKEHEAMPDSVZIBPNZUAAZUNXJGHVMAIKOPKEYFXRRXZLKPGMEAQKYIAEZJLNRIPFIRTEBJTGEBBSKSXJGYFMKSZPHHFZPEANXOPDBOTKETNUPDNZTAKHREMDREEHJRDU

Part 2: Hardened Keyed Caesar

The Keyed Caesar was a step in the right direction, but it's still reasonably easy to crack, because of certain weaknesses (no, I won't reveal the answer to part 1 in part 2!). So we're going to harden it some more. The Hardened Keyed Caesar will feature a global increment. This means that the nth letter of the plaintext will get shifted k*n places, where k is the global increment. So if your global increment was 2, the first letter would get shifted 2 placed on top of how it's shifted by the key, the second letter 4, and so on. This makes the cipher much more resilient to certain attacks.

Here's the implementations:

• PHP Implementation
• Javascript Implementation
• Python Implementation

"Hang on", you say, "in a real situation this would be on large chunks of text, and I'd know a bit about the context. The shortness of the challenges add artificial difficulty!". And you'd be right; that's why, for the next challenges, I'll provide a pastebin of a LARGE chunk of text encrypted by this cipher. I'll even tell you what it's about!

Challenge 2.1: Length 2 Key Plus Increment

A military guidebook.

Challenge 2.2: Unknown Length Key (<= 7) Plus Increment

A famous novel.

What more can I say? Happy cracking!

Answer 1

Challenge 0

CAESAR WAS NOT A VERY GOOD CRYPTOGRAPHER
Letters shifted by 16 positions in the alphabet.

Found by brute force.

Challenge 1.1

A KEY OF LENGTH TWO IS NOT VERY GOOD BECAUSE IT IS ALMOST THE SMAE AS A NORMAL CAESAR CIPHER, AND YOU CAN STILL BRUTE-FORCE THE COMBINATION. BUT IF YOU SOLVED THIS ANALYTICALLY YOU ARE DOING WELL, BECAUSE THE SAME TECHNIQUE CAN BE APPLIED TO BREAK THIS CIPHER WITH ANY KEY LENGTH. HERE'S SOME MORE TEXT: THE QUICK BROWN FOX JUMPED OVER THE LAZY DOG.
Key of (16,22).

Found by brute force with the aid of the javascript implementation.

Challenge 1.2

STACKOVERFLOW HAS WRITTEN VOLUMES ABOUT HOW THE BEST WAY TO MAKE A POINT IS WITH FOAMING AT THE MOUTH, RHETORIC, AND LETTERS FILLED PRIMARILY WITH EXCLAMATION POINTS. DON'T BELIEVE A WORD OF IT, THOUGH. THE TRUTH IS THAT IT PROFESSES THAT A PLAUSIBLE EXCUSE IS A SATISFACTORY SUBSTITUTE FOR PERFORMANCE. THAT CONCEPT IS OF COURSE COMPLETE BUNK BY ANY STRETCH OF THE IMAGINATION; HOWEVER IT IS BUNK THAT HAS SURVIVED VIRTUALLY UNCHANGED FROM WHEN IT WAS FIRST PROPOSED NEARLY HALF A CENTURY AGO BY CAUSTIC MADMEN TO ITS PRESENT INCARNATION IN STACKOVERFLOW'S VILE EXCUSES. STACKOVERFLOW LOVES USING BIG WORDS LIKE 'UNDEMONSTRATIVENESS' AND 'UNPROPORTIONABLENESS'. AS A RESULT, IT WRITES LIKE A MENTALLY ILL PERSON WITH A THESAURUS. THAT GOT ME THINKING: PERHAPS STACKOVERFLOW SPOUTS ALL CLASSES OF PUFFERY ABOUT ITS MORAL VIGOR. WELL, SURE, IT HAS SOMEHOW FOUND THE FORTITUDE TO ENDURE OUR ONGOING HUMILIATION AND DISCOMFORT AT THE HANDS OF ITS PATSIES. BUT THE LARGER POINT IS THAT STACKOVERFLOW WRITES A LOT OF LONG STATEMENTS THAT MEAN PRACTICALLY NOTHING. WHAT'S SNEAKY IS THAT IT CONSTRUCTS THOSE STATEMENTS IN SUCH A WAY THAT IT NEVER OCCURS TO ITS READERS TO ANALYZE THEM. ANALYSIS WOULD ALMOST CERTAINLY INDICATE THAT STACKOVERFLOW SWEARS THAT ITS A LIVING BODHISATTVA OF PEACE AND NONVIOLENCE; CLEARLY IT'S LIVING IN A WORLD OF MAKEBELIEVE WITH FLOWERS AND BELLS AND LEPRECHAUNS AND MAGIC FROGS WITH FUNNY LITTLE HATS. BACK IN THE REAL WORLD, THE WHOLE OF STACKOVERFLOW'S BRUTISH WORLD-VIEW MAY PERHAPS BE EXPRESSED IN ONE SIMPLE WORD. THAT WORD IS 'SADISM'. LET ME EXPLAIN. WE MUST WORK TOGETHER TO DOLE OUT ACERBIC CRITICISM OF STACKOVERFLOW AND ITS PHALANX OF CRAZY RADICALISM-ORIENTED DISCIPLES. WHAT CAN YOU DO TO HELP? FOR STARTERS, YOU MIGHT WANT TO PLANT MARKERS THAT DEFINE THE LIMITS OF WHAT IS RAVING AND WHAT IS NOT. I PERSONALLY DERIVE GREAT SATISFACTION IN DOING THAT SORT OF THING, BECAUSE IT MAY SEEM AT FIRST THAT WITHIN A SHORT PERIOD OF TIME STACKOVERFLOW'S LIES WILL BE EXPOSED AND THE TRUTH CAN BE SPREAD. WHEN WE DESCEND TO DETAILS, HOWEVER, WE SEE THAT ITS FUNCTIONARIES OFTEN REVERSE THE NORMAL PROCESS OF INTERPRETATION: THAT IS, THEY VALUE THE UNSAID OVER THE SAID, THE OBSCURE OVER THE CLEAR.

Key of [12,3,4,19,19,22]

Found by performing frequency analysis and choosing the keys which maximize the sum of the frequencies of E,T,A and O in the decrypted text.

Challenge 1.3

For each keylength 1 to 7, I computed the most likely value of the first part of the key by maximizing the sum of E,T,A, and Os as in Challenge 1.2. This maximum of sums I call maxEtao. Then, normalize maxEtao for each key length so they can be compared, and the results are as below:

keylen  maxEtao * keylen / 7
1       46.57142857142857
2       47.42857142857143
3       47.142857142857146
4       46.285714285714285
5       90
6       46.285714285714285
7       53

It seems very likely that the keylength is 5 since this will generate the most E, T, A, and Os on average.

Now perform the same frequency analysis as in Challenge 1.2 and the answer will be

IF YOU'RE A PROGRAMMER PLEASE DON'T DENIGRATE WHAT A BEGINNER IS CURRENTLY LEARNING UNLESS YOU'RE WILLING TO PERSONALLY INVEST THE ENORMOUS AMOUNT OF TIME TO ENSURE THAT THEY LEARN WHAT YOU WANT THEM TO LEARN JUST MAKING A SNIDE DRIVE BY REMARK ABOUT HOW THEIR CHOICE OF LANGUAGES OR TOOLS ISN'T AS COOL AS WHAT YOU USE WILL LIKELY DRAIN THEIR MOTIVATION. I KNOW IT CAN BE HARD TO RESIST SLIDING IN A WITTY ZINGER DISSING PHP OR WHATEVER LANGUAGE PEOPLE LOVE TO HATE ON THIS YEAR IVE BEEN GUILTY OF THIS MYSELF IN THE PAST ESPECIALLY BECAUSE YOU KNOW FROM THE BOTTOM OF YOUR HACKER HEART THAT YOUR GIVEN LANGUAGE, FRAMEWORK, LIBRARY, TEXT EDITOR, HOSTING ENVIRONMENT, ERGONOMIC KEYBOARD, STANDING DESK ETC. IS SOOOO MUCH BETTER THAN WHATEVER NOOB RUBBISH THEY'RE LEARNING BUT PLEASE RESIST JUST LET THEM FIRST LEARN SOMETHING ANYTHING TO GET HOOKED ONTO THE POTENTIAL OF PROGRAMMING AND THEN YOU CAN OFFER TO SHOW THEM THE TRUE LIGHT LATER. IF WHAT THEY'RE LEARNING IS TRULY SO TERRIBLE THEN THEY WILL KEEP GETTING STUCK AND ASK YOU WHETHER THERE'S AN EASIER WAY. THEN AND ONLY THEN YOU CAN UNLEASH YOUR TREATISE ON PURE FUNCTIONAL PROGRAMMING OR HYGENIC MACROS OR WHATEVER. ALSO YOU'RE PROBABLY NOT THE ONLY PROGRAMMER THE BEGINNER IS TALKING TO MANY PROGRAMMERS ESPECIALLY IN ONLINE FORUMS ARE PROBABLY MAKING SIMILAR SNIDE REMARKS EXCEPT THEY'RE SAYING THAT THEIR OWN FAVORITE LANGUAGE, LIBRARY, FRAMEWORK, TEXT EDITOR, HOSTING ENVIRONMENT IS THE BEST EVAHHHHHHH. SO NOW THE BEGINNER IS REALLY CONFUSED, THEY'RE REPEATEDLY TOLD THAT THEIR GIVEN CHOICE OF TOOLS IS SOMEHOW TERRIBLE EVEN THOUGH THEY SEEM TO BE DOING OK WITH IT AT THE MOMENT, BUT EVEN WORSE EVERY SO CALLED EXPERT IS RECOMMENDING A DIFFERENT SET OF TOOLS TO LEARN. WHO IS RIGHT WHAT SHOULD THEY DO NEXT?

Key is [6,1,19,22,13]

Challenge 2.1

I LAYING PLANS SUN TZU SAID THE ART OF WAR IS OF VITAL IMPORTANCE TO THE STATE IT IS A MATTER OF LIFE AND DEATH
...
WHEN YOU SURROUND AN ARMY LEAVE AN OUTLET FREE DO NOT PRESS A DESPERATE FOE TOO HARD SUCH IS THE ART OF WARFARE

Key of [4,6], increment of 20.

Found by the same analysis as Challenge 1.2, but with an effective keylength of 3.

For Challenge 2.2, please refer to the excellent answer by kasperd.

Answer 2

I consider challenges 0 through 2.1 as training exercises for those who haven't tried this sort of challenge before. So I jumped straight to challenge 2.2.

I dusted off an old piece of code which I wrote more than a decade ago to break a Vigenère cipher and let it make an attempt at challenge 2.2. I had it try all possible key lengths from 1 through 400, and it told me the most likely key length was:

130

But hey, that's more than 7. Was my code wrong? Not really, challenge 2.2 isn't a Vigenère cipher. However by interpreting the output slightly different, I can deduce that the key length must be:

5

The reason I got a different key length is that the number I got first is the product of

5 (the actual key length) and 26 (the period introduced by the increment)

Thus I can deduce that the increment must be an odd number because otherwise

the increment period could only have been 13 and the key length would have had to be 10, which is more than the promised maximum of 7

For each index in the overall period I identified the most frequent character in the cipher text. I then looked at every

5th position

and I noticed that the most frequent letter mostly jumps one position backwards in the alphabet each time I move forward. Thus I can deduce that the additional increment must be

5

because

5 (increment) * 5 (key length) = 25

and that explains the step one character backwards in the alphabet each time. And by knowing a bit of math (or by trial and error), one can find that it is the only possible increment with that property.

Assuming the most frequent letter is E, I then get the shifts for the first five positions to be:

15 8 16 23 18

Combining those shifts with the increment, the start of the text decrypts to:

CHAPTER I MR JONES OF THE MANOR FARM HAD LOCKED THE HEN HOUSES FOR THE NIGHT BUT WAS TOO DRUNK TO REMEMBER

(I have inserted some spaces in the decrypted text to aid readability)

And the last part of the text decrypts to

WITHOUT FURTHER ARGUMENT THAT THE MILK AND THE WINDFALL APPLES AND ALSO THE MAIN CROP OF APPLES WHEN THEY RIPENED SHOULD BE RESERVED FOR THE PIGS ALONE