CodeGate 2012 Quals – misc #1

CodeGate CTF 2012 - misc #1 - task description

Die Aufgabenstellung (misc #1) ist mal wieder recht unklar. Das 35mb-Zipfile zu durchsuchen würde jedenfalls in echte Arbeit ausarten. Also sehen wir uns zuerst den Text der Aufgabenstellung an und versuchen diesen zu dechiffrieren.

“Az hrb eix mcc gyam mcxgixec rokaxioaqh hrb mrqpck gyam lbamgarx oatygqh Erxtoigbqigarx Gidc hrbg gasc gr koaxd erzzcc zro i jyaqc Kr hrb ocqh rx Ockubqq ro Yrg man? Gyc ixmjco am dccqihrbgm”

Was sofort auffällt ist:
– es sind Satzzeichen vorhanden
– teilweise beginnen die “Wörter” mit Großbuchstaben
– einige Zeichenketten wiederholen sich (z.B. “hrb”)

Es liegt also nahe, dass es sich um einen Caesar-Chiffre handelt. Das testen wir an den ersten Wörtern kurz durch:

rup0rt@lambda:~$ for i in {1..25}; do caesar $i < first.plain; done
Ba isc fjy ndd hzbn
Cb jtd gkz oee iaco
Dc kue hla pff jbdp
Ed lvf imb qgg kceq
Fe mwg jnc rhh ldfr
Gf nxh kod sii megs
Hg oyi lpe tjj nfht
Ih pzj mqf ukk ogiu
Ji qak nrg vll phjv
Kj rbl osh wmm qikw
Lk scm pti xnn rjlx
Ml tdn quj yoo skmy
Nm ueo rvk zpp tlnz
On vfp swl aqq umoa
Po wgq txm brr vnpb
Qp xhr uyn css woqc
Rq yis vzo dtt xprd
Sr zjt wap euu yqse
Ts aku xbq fvv zrtf
Ut blv ycr gww asug
Vu cmw zds hxx btvh
Wv dnx aet iyy cuwi
Xw eoy bfu jzz dvxj
Yx fpz cgv kaa ewyk
Zy gqa dhw lbb fxzl

Ein normales Verschieben der Buchstaben führt also in keinem der 25 Möglichkeiten zu einem sinnvollen Ergebnis. Auch wenn der Text sehr kurz ist, führen wir zunächst eine Analyse der Buchstaben-Häufigkeiten durch.

rup0rt@lambda:~$ ./freq_analysis.pl misc1.txt | grep -i \(
         r =    17 ( 10.90 % )
         c =    16 ( 10.26 % )
         a =    14 ( 8.97 % )
         g =    14 ( 8.97 % )
         x =    10 ( 6.41 % )
         m =    10 ( 6.41 % )
         o =    10 ( 6.41 % )
         i =     9 ( 5.77 % )
         q =     9 ( 5.77 % )
         h =     8 ( 5.13 % )
         b =     8 ( 5.13 % )
         y =     6 ( 3.85 % )
         k =     5 ( 3.21 % )
         e =     4 ( 2.56 % )
         z =     4 ( 2.56 % )
         d =     3 ( 1.92 % )
         j =     2 ( 1.28 % )
         t =     2 ( 1.28 % )
         u =     1 ( 0.64 % )
         n =     1 ( 0.64 % )
         s =     1 ( 0.64 % )
         l =     1 ( 0.64 % )
         p =     1 ( 0.64 % )

Da von einem englischen Text auszugehen ist, nehmen wir die Normalverteilung der Buchstaben solcher Text zur Hilfe. Google führt uns hierher.

Letter 	Frequency 	Letter 	Frequency
e 	0.12702 	m 	0.02406
t 	0.09056 	w 	0.02360
a 	0.08167 	f 	0.02228
o 	0.07507 	g 	0.02015
i 	0.06966 	y 	0.01974
n 	0.06749 	p 	0.01929
s 	0.06327 	b 	0.01492
h 	0.06094 	v 	0.00978
r 	0.05987 	k 	0.00772
d 	0.04253 	j 	0.00153
l 	0.04025 	x 	0.00150
c 	0.02782 	q 	0.00095
u 	0.02758 	z 	0.00074

Diese Verteilung gilt es nun auf den Chiffre abzubilden. Da die Verteilung auf Grund der Kürze des Textes ungenau sein kann, hilft der Versuch häufige englische Wörter, wie “the”, “you”, “a” zu erkennen.

Da “e” der häufigste englische Buchstabe ist, suchen wir also dreistellige Wörter, die auf “r” oder “c” enden, in der Hoffnung ein “the” zu finden. Hierfür kommt nur “Gyc” in Frage. Sollte dieses Wort “the” sein, hätten wir folgende Zuordnung erhalten:
G => T
Y => H
C => E
Das probieren wir nun aus, indem wir eine Ersetzung über den gesamten Text mit dem VI durchführen. Um keine doppelten Ersetzungen zu riskieren, konvierten wir zunächst alles in Großbuchstaben und führen Substitutionen in Kleinbuchstaben durch, dazu “:%s/.*/\U&/”. Danach führen wir die obigen Ersetzungen durch mit (hier: G => T) “:%s/G/t/g”. Das Ergebnis sieht folgendermaßen aus:

“AZ HRB EIX Mee thAM MeXtIXEe ROKAXIOAQH HRB MRQPeK thAM LBAMtARX OAThtQH ERXTOItBQItARX tIDe HRBt tASe tR KOAXD ERZZee ZRO I JhAQe KR HRB Oe QH RX OeKUBQQ RO hRt MAN? the IXMJeO AM DeeQIHRBtM”

Wenn wir richtig geraten haben, sollten nun weitere Wörter erkennbar sein. Hierfür kämen in Frage:
– thAM => this(?)
– tR => to(?)
– HRB => you(?)
– I => a(?)
Die Durchführung dieser Ersetzungen mit VI liefert wiederum:

“iZ you EaX see this seXtaXEe oOKiXaOiQy you soQPeK this LuistioX OiThtQy EoXTOatuQatioX taDe yout tiSe to KOiXD EoZZee ZoO a JhiQe Ko you Oe Qy oX OeKUuQQ oO hot siN? the aXsJeO is DeeQayouts”

Der Text nimmt nun langsam Form an. Weitere Ersetzungen stechen ins Auge:
– iZ => if(?)
– EoZZee => coffee(?)
– aXsJeO => answer(?)
– …
Nachdem weitere Wörter gefunden worden, erhält man letztendlich diesen Lösungssatz:

“if you can see this sentance ordinarily you solved this quistion rightly congratulation take yout time to drink coffee for a while do you rely on redbull or hot six? the answer is keelayouts”

Also lautet die Antwort “keelayouts“.

Leave a Reply

Your email address will not be published. Required fields are marked *