Alice, Bob and Mallory

Breaking simple ciphers

Posted by Jonas Elfström Wed, 16 Sep 2009 18:19:00 GMT

The last few days I've happened to stumble over a couple of ciphers and I just couldn't help myself from trying to break them.

The Lost Symbol

Dan Brown has a new book coming out and part of the promotion is this cipher text "AOFACFSOA FSZWBEIC EIOA ZOHSFWQWOA OQQSDW". The WQW, QQ and three of the words ending with an A made me believe we could be dealing with a substitution cipher and maybe even a Caesar cipher, the most simple of them all.

As usual my tool of choice was Ruby and in this case the splendid Interactive Ruby Shell.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

$ irb
>> s="AOFACFSOA FSZWBEIC EIOA ZOHSFWQWOA OQQSDW"
=> "AOFACFSOA FSZWBEIC EIOA ZOHSFWQWOA OQQSDW"
>> def caesar(text,n)
>>   alphas=('A'..'Z').to_a*2
>>   text.tr('A-Z', alphas[n..n+26].join)
>> end
>> 1.upto(25) do |n| puts "%2d. %s" % [n, caesar(s,n)] end
 1. BPGBDGTPB GTAXCFJD FJPB APITGXRXPB PRRTEX
 2. CQHCEHUQC HUBYDGKE GKQC BQJUHYSYQC QSSUFY
 3. DRIDFIVRD IVCZEHLF HLRD CRKVIZTZRD RTTVGZ
 4. ESJEGJWSE JWDAFIMG IMSE DSLWJAUASE SUUWHA
 5. FTKFHKXTF KXEBGJNH JNTF ETMXKBVBTF TVVXIB
 6. GULGILYUG LYFCHKOI KOUG FUNYLCWCUG UWWYJC
 7. HVMHJMZVH MZGDILPJ LPVH GVOZMDXDVH VXXZKD
 8. IWNIKNAWI NAHEJMQK MQWI HWPANEYEWI WYYALE
 9. JXOJLOBXJ OBIFKNRL NRXJ IXQBOFZFXJ XZZBMF
10. KYPKMPCYK PCJGLOSM OSYK JYRCPGAGYK YAACNG
11. LZQLNQDZL QDKHMPTN PTZL KZSDQHBHZL ZBBDOH
12. MARMOREAM RELINQUO QUAM LATERICIAM ACCEPI
13. NBSNPSFBN SFMJORVP RVBN MBUFSJDJBN BDDFQJ
14. OCTOQTGCO TGNKPSWQ SWCO NCVGTKEKCO CEEGRK
15. PDUPRUHDP UHOLQTXR TXDP ODWHULFLDP DFFHSL
16. QEVQSVIEQ VIPMRUYS UYEQ PEXIVMGMEQ EGGITM
17. RFWRTWJFR WJQNSVZT VZFR QFYJWNHNFR FHHJUN
18. SGXSUXKGS XKROTWAU WAGS RGZKXOIOGS GIIKVO
19. THYTVYLHT YLSPUXBV XBHT SHALYPJPHT HJJLWP
20. UIZUWZMIU ZMTQVYCW YCIU TIBMZQKQIU IKKMXQ
21. VJAVXANJV ANURWZDX ZDJV UJCNARLRJV JLLNYR
22. WKBWYBOKW BOVSXAEY AEKW VKDOBSMSKW KMMOZS
23. XLCXZCPLX CPWTYBFZ BFLX WLEPCTNTLX LNNPAT
24. YMDYADQMY DQXUZCGA CGMY XMFQDUOUMY MOOQBU
25. ZNEZBERNZ ERYVADHB DHNZ YNGREVPVNZ NPPRCV

Take a closer look at row 12.

MARMOREAM RELINQUO QUAM LATERICIAM ACCEPI

I found Rome a city of bricks and left it a city of marble. - Google tells me it's Augustus.

The code is not the most clear I've written but if you read Ruby in your sleep you can skip this part.

('A'..'Z') is a range in Ruby. Another, maybe more obvious, example of a range is (0..7).

.to_a could be read as to_array and unsurprisingly it converts a range to an array. (0..7).to_a will create [0, 1, 2, 3, 4, 5, 6, 7]

The operator * for arrays appends n copies of the array. Thus [0,1,2]*2 will create [0,1,2,0,1,2].

String#tr works the same way as the Unix command tr, it translates the characters in the string according to the from and to parameters.

At last .join converts the array to a string.

The recruiting agency

A government agency responsible for signals intelligence is hiring. Among the qualifications they are looking for is the ability to break a certain cipher. I will not publish their cipher here but instead one of my own, constructed in the same way as theirs.

"VGhpcyBpcyBleGNsdXNpdmUgZm9yIHlvdSwgb3I/IGMNR0d
LCkZPXgpTRV8K\nTENEQ1lCCkhfXgpoT1NFRElPCkNZCksKSE9eXk
9YCklYU1peRU1YS1pCT1gK\nXkJLRAp5SUJET0NPWAQ="

1
2
3
4
5

$ irb
>> require 'base64'
>> cipher = "VGhpcyBpcyBleGNsdXNpdmUgZm9yIHlvdSwgb3I/IGMNR0dLCkZPXgpTRV8K\nTENEQ1lCCkhfXgpoT1NFRElPCkNZCksKSE9eXk9YCklYU1peRU1YS1pCT1gK\nXkJLRAp5SUJET0NPWAQ="
>> decoded=Base64.decode64(cipher)
=> "This is exclusive for you, or? c\rGGK\nFO^\nSE\nLCDCYB\nH^\nhOSEDIO\nCY\nK\nHO^^OX\nIXSZ^EMXKZBOX\n^BKD\nyIBDOCOX\004"

So it's Base64 but to no surprise it didn't end there. The "This is exclusive for you, or?" hinted at XOR so I tried XORing the text with 0-255.

1
2
3
4
5
6
7
8

>> code=decoded[31..decoded.length].split(//)
>> File.open('xor.txt','w') { |file|
?>   0.upto(255) {|n|
?>     file.write(n.to_s + " ")
>>     code.each {|c| file.write( (c[0]^n).chr ) }
>>     file.write("\n\n")
>>   }
>> }

A quick look in the file told me that XORing with 42 was the solution.

Now you know how to break two of the most simple cipher methods. Use the knowledge wisely. :)