-
Notifications
You must be signed in to change notification settings - Fork 1
/
csaw-ctf-2014-cryptography-200-psifer-school.html
371 lines (314 loc) · 39.3 KB
/
csaw-ctf-2014-cryptography-200-psifer-school.html
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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="utf-8">
<title>CSAW CTF 2014 - Cryptography 200 - Psifer School</title>
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<meta name="description" content="">
<meta name="author" content="Marina von Steinkirch">
<!-- Le styles -->
<link rel="stylesheet" href="./theme/css/bootstrap.dark.css" type="text/css" />
<style type="text/css">
body {
padding-top: 60px;
padding-bottom: 40px;
}
.tag-1 {
font-size: 13pt;
}
.tag-2 {
font-size: 11pt;
}
.tag-2 {
font-size: 10pt;
}
.tag-4 {
font-size: 8pt;
}
</style>
<link href="./theme/css/bootstrap-responsive.dark.css" rel="stylesheet">
<link href="./theme/css/font-awesome.css" rel="stylesheet">
<link href="./theme/css/pygments.css" rel="stylesheet">
<!-- Le fav and touch icons -->
<link rel="shortcut icon" href="./theme/images/favicon.ico">
<link rel="apple-touch-icon" href="./theme/images/apple-touch-icon.png">
<link rel="apple-touch-icon" sizes="72x72" href="./theme/images/apple-touch-icon-72x72.png">
<link rel="apple-touch-icon" sizes="114x114" href="./theme/images/apple-touch-icon-114x114.png">
<link href="./feeds/all.atom.xml" type="application/atom+xml" rel="alternate" title="chmod +x singularity.sh ATOM Feed" />
</head>
<body>
<div class="navbar navbar-fixed-top">
<div class="navbar-inner">
<div class="container-fluid">
<a class="btn btn-navbar" data-toggle="collapse" data-target=".nav-collapse">
<span class="icon-bar"></span>
<span class="icon-bar"></span>
<span class="icon-bar"></span>
</a>
<a class="brand" href="./index.html">chmod +x singularity.sh </a>
<div class="nav-collapse">
<ul class="nav">
<li class="divider-vertical"></li>
<ul class="nav pull-right">
<li><a href="./authors.html">About</a></li>
<li><a href="./archives.html"><b>Archives</b></a></li>
<li>
<a href="https://github.com/bt3gl">github
<!--<i class="icon-github-sign icon-large" ></i>-->
</a></li>
<li>
<a href="https://twitter.com/1bt337">
<!--<i class="icon-twitter-sign icon-large"></i> -->
twitter
</a></li>
<li><a href="http://bt3gl.github.io/projects_page/index.html">Bygone Playful Times
</a></li>
</ul>
</ul>
<!--<p class="navbar-text pull-right">Logged in as <a href="#">username</a></p>-->
</div><!--/.nav-collapse -->
</div>
</div>
</div>
<div class="container-fluid">
<div class="row">
<div class="span9" id="content">
<section id="content">
<article>
<header>
<h1>
<a href=""
rel="bookmark"
title="Permalink to CSAW CTF 2014 - Cryptography 200 - Psifer School">
CSAW CTF 2014 - Cryptography 200 - Psifer School
</a>
</h1>
</header>
<div class="entry-content">
<div class="well">
<footer class="post-info">
<abbr class="published" title="2014-09-21T00:20:00">
Sun 21 September 2014 </abbr>
<span class="label"> Category</span>
<a href="./category/cryptography.html"><i class="icon-folder-open"></i>Cryptography</a>
<span class="label">Tags</span>
<a href="./tag/ctf.html"><i class="icon-tag"></i>CTF</a>
<a href="./tag/csaw.html"><i class="icon-tag"></i>CSAW</a>
<a href="./tag/rot13.html"><i class="icon-tag"></i>ROT13</a>
<a href="./tag/telnet.html"><i class="icon-tag"></i>telnet</a>
<a href="./tag/socket.html"><i class="icon-tag"></i>socket</a>
<a href="./tag/vigenere.html"><i class="icon-tag"></i>Vigenere</a>
<a href="./tag/pygenere.html"><i class="icon-tag"></i>pygenere</a>
<a href="./tag/python.html"><i class="icon-tag"></i>Python</a>
</footer><!-- /.post-info --> </div>
<p>This is the first crypto-problem, and it was supposed to be the easiest one. For this reason I was expecting simple cryptographic algorithms, which turned out to be true.</p>
<p>The problem starts with the following text:</p>
<blockquote>
<p>There's no heartbleed here. Why don't we use these ciphers?</p>
<p>nc 54.209.5.48 12345</p>
<p>Written by psifertex</p>
</blockquote>
<hr />
<h2>Stage One: Caesar Cipher</h2>
<h4>Connecting to the Server</h4>
<p>We start typing the <strong>netcat</strong> command in the terminal:</p>
<div class="highlight"><pre>nc 54.209.5.48 12345
</pre></div>
<p>We get the following message back:</p>
<blockquote>
<p>Welcome to psifer school v0.002</p>
<p>Your exam begins now. You have 10 seconds, work fast.</p>
<p>Here is your first psifer text, a famous ancient roman would be proud if you solve it.</p>
<p>psifer text: <strong>wkh dqvzhu wr wklv vwdjh lv vxshuvlpsoh</strong></p>
<p>Time's up. Try again later.</p>
</blockquote>
<p>This text gives a cipher <code>wkh dqvzhu wr wklv vwdjh lv vxshuvlpsoh</code> and the hint <em>a famous ancient roman would be proud</em>. That's all we need to decipher it!</p>
<h4>Frequency Analysis</h4>
<p>The famous roman is <strong>Caesar</strong>, and <a href="http://en.wikipedia.org/wiki/Caesar_cipher">his cryptographic scheme</a> is one of the simplest possible. This cipher is also known as <strong>rotation cipher</strong>, because all we do is rotating the letters by some value (the <strong>key</strong>). A modern version of it is called <strong>ROT13</strong>, meaning <strong>rotation by 13 places</strong>. This is a simple letter substitution cipher which replaces each letter with the 13th letter after it in the alphabet. In this case, we say that the <em>key is 13</em>.</p>
<p>In our problem, we don't know the key. However there is a method to circumvent it: we can count how many times each letter appears in the text and then we use some previous knowledge about the frequency of each letter in the English words. For example, in the English language, <em>e</em>, <em>t</em>, <em>a</em>, <em>o</em>, and <em>n</em> are frequent letters while <em>z</em> or <em>v</em> are not. This means that we can analyse the frequency of each character to determine what's the most probable rotation key.</p>
<p>To count the frequency of characters in our cipher, we write a snippet that creates a counter <a href="https://docs.python.org/2/tutorial/datastructures.html#dictionaries">dictionary (hash table)</a> with all the (lowercase) characters as the dictionary's keys. Note that we could have used Python's <a href="https://docs.python.org/2/library/collections.html#collections.Counter">Counter() data-structure</a> as well. We then iterate through each character in the message, counting their frequency, and returning a sorted list of these values:</p>
<div class="highlight"><pre><span class="kn">import</span> <span class="nn">string</span>
<span class="k">def</span> <span class="nf">frequency</span><span class="p">(</span><span class="n">msg</span><span class="p">):</span>
<span class="c"># Compute the word frequencies</span>
<span class="n">dict_freq</span> <span class="o">=</span> <span class="nb">dict</span><span class="p">([(</span><span class="n">c</span><span class="p">,</span><span class="mi">0</span><span class="p">)</span> <span class="k">for</span> <span class="n">c</span> <span class="ow">in</span> <span class="n">string</span><span class="o">.</span><span class="n">lowercase</span><span class="p">])</span>
<span class="n">diff</span> <span class="o">=</span> <span class="mf">0.0</span>
<span class="k">for</span> <span class="n">c</span> <span class="ow">in</span> <span class="n">msg</span><span class="o">.</span><span class="n">lower</span><span class="p">():</span>
<span class="k">if</span> <span class="s">'a'</span><span class="o"><=</span> <span class="n">c</span> <span class="o"><=</span> <span class="s">'z'</span><span class="p">:</span>
<span class="n">diff</span> <span class="o">+=</span> <span class="mi">1</span>
<span class="n">dict_freq</span><span class="p">[</span><span class="n">c</span><span class="p">]</span> <span class="o">+=</span> <span class="mi">1</span>
<span class="n">list_freq</span> <span class="o">=</span> <span class="n">dict_freq</span><span class="o">.</span><span class="n">items</span><span class="p">()</span>
<span class="n">list_freq</span><span class="o">.</span><span class="n">sort</span><span class="p">()</span>
<span class="k">return</span> <span class="p">[</span><span class="n">b</span> <span class="o">/</span> <span class="n">diff</span> <span class="k">for</span> <span class="p">(</span><span class="n">a</span><span class="p">,</span> <span class="n">b</span><span class="p">)</span> <span class="ow">in</span> <span class="n">list_freq</span><span class="p">]</span>
</pre></div>
<h4>Deciphering the Cipher</h4>
<p>Using a <a href="http://en.wikipedia.org/wiki/Letter_frequency">well-known table of word frequency values</a>, we write a snippet that does the following:</p>
<ol>
<li>First, for each of the 26 letters, we subtract its known frequency value from the frequency obtained from our message.</li>
<li>Second, we find what is the minimum value from those subtractions. The closest value is the most probable value for the rotation key.</li>
</ol>
<div class="highlight"><pre><span class="k">def</span> <span class="nf">delta</span><span class="p">(</span><span class="n">freq_word</span><span class="p">,</span> <span class="n">freq_eng</span><span class="p">):</span>
<span class="c"># zip together the value from the text and the value from FREQ</span>
<span class="n">diff</span> <span class="o">=</span> <span class="mf">0.0</span>
<span class="k">for</span> <span class="n">a</span><span class="p">,</span> <span class="n">b</span> <span class="ow">in</span> <span class="nb">zip</span><span class="p">(</span><span class="n">freq_word</span><span class="p">,</span> <span class="n">freq_eng</span><span class="p">):</span>
<span class="n">diff</span> <span class="o">+=</span> <span class="nb">abs</span><span class="p">(</span><span class="n">a</span> <span class="o">-</span> <span class="n">b</span><span class="p">)</span>
<span class="k">return</span> <span class="n">diff</span>
<span class="k">def</span> <span class="nf">decipher</span><span class="p">(</span><span class="n">msg</span><span class="p">):</span>
<span class="c"># Decipher by frequency</span>
<span class="n">min_delta</span><span class="p">,</span> <span class="n">best_rotation</span> <span class="o">=</span> <span class="mi">20</span><span class="p">,</span> <span class="mf">0.0</span>
<span class="n">freq</span> <span class="o">=</span> <span class="n">frequency</span><span class="p">(</span><span class="n">msg</span><span class="p">)</span>
<span class="k">for</span> <span class="n">key</span> <span class="ow">in</span> <span class="nb">range</span><span class="p">(</span><span class="mi">26</span><span class="p">):</span>
<span class="n">d</span> <span class="o">=</span> <span class="n">delta</span><span class="p">(</span><span class="n">freq</span><span class="p">[</span><span class="n">key</span><span class="p">:]</span> <span class="o">+</span> <span class="n">freq</span><span class="p">[:</span><span class="n">key</span><span class="p">],</span> <span class="n">FREQ_ENGLISH</span><span class="p">)</span>
<span class="k">if</span> <span class="n">d</span> <span class="o"><</span> <span class="n">min_delta</span><span class="p">:</span>
<span class="n">min_delta</span> <span class="o">=</span> <span class="n">d</span>
<span class="n">best_rotation</span> <span class="o">=</span> <span class="n">key</span>
<span class="k">return</span> <span class="n">cipher</span><span class="p">(</span><span class="n">msg</span><span class="p">,</span> <span class="o">-</span><span class="n">best_rotation</span><span class="p">)</span>
</pre></div>
<p>Once we have the key, we just plug it back to the cipher algorithm, inverting the rotation to the other side, with <code>cipher(msg, -best_rotation)</code>. In this cipher function, we iterate through all the character in the message, checking whether it's a letter or a special character. If it is the former case we perform the following operations:</p>
<ol>
<li>We start getting the integer representing the <a href="http://en.wikipedia.org/wiki/Unicode">Unicode</a> code point of the character.</li>
<li>To get its position in the alphabet and we subtract it from the Unicode value of <em>a</em>, given by <strong>ord('a')</strong> (this is 97).</li>
<li>We add the key value to it to get the (absolute) shift position.</li>
<li>Now we need to remember that this cipher is a ring, <em>i.e</em>, adding more stuff should always lead to a <em>spot</em> within the 26 letters in the alphabet. That's why we apply a <a href="http://en.wikipedia.org/wiki/Modulo_operation">module</a> operation to this number to get the <em>relative</em> position in the letter's table.</li>
<li>Finally, we just need the value of the shift to the Unicode of <em>a</em> to get the position of the character in the cipher.</li>
<li>Remember we are using <em>-key</em>, so instead of making a new cipher we are using the same steps to rotate the cipher to the other side to recover the message.</li>
</ol>
<div class="highlight"><pre><span class="k">def</span> <span class="nf">cipher</span><span class="p">(</span><span class="n">msg</span><span class="p">,</span> <span class="n">key</span><span class="p">):</span>
<span class="c"># Make the cipher</span>
<span class="n">dec</span> <span class="o">=</span> <span class="s">''</span>
<span class="k">for</span> <span class="n">c</span> <span class="ow">in</span> <span class="n">msg</span><span class="o">.</span><span class="n">lower</span><span class="p">():</span>
<span class="k">if</span> <span class="s">'a'</span> <span class="o"><=</span> <span class="n">c</span> <span class="o"><=</span> <span class="s">'z'</span><span class="p">:</span>
<span class="n">dec</span> <span class="o">+=</span> <span class="nb">chr</span><span class="p">(</span><span class="nb">ord</span><span class="p">(</span><span class="s">'a'</span><span class="p">)</span> <span class="o">+</span> <span class="p">(</span><span class="nb">ord</span><span class="p">(</span><span class="n">c</span><span class="p">)</span> <span class="o">-</span> <span class="nb">ord</span><span class="p">(</span><span class="s">'a'</span><span class="p">)</span> <span class="o">+</span> <span class="n">key</span><span class="p">)</span> <span class="o">%</span> <span class="mi">26</span><span class="p">)</span>
<span class="k">else</span><span class="p">:</span>
<span class="n">dec</span> <span class="o">+=</span> <span class="n">c</span>
<span class="k">return</span> <span class="n">dec</span>
</pre></div>
<p>Bingo! The snippets above lead us to our first answer in this problem:</p>
<blockquote>
<p>the answer to this stage is <strong>supersimple</strong></p>
</blockquote>
<p>Netcating several times can return other similar answers such as <strong>hopeyouautomate</strong> or <strong>easypeesy</strong> or <strong>notveryhard</strong>. They are all correct.</p>
<h4>Automating the Response</h4>
<p>To advance forward, we need to send one of the above answers to the socket. However, we only <strong>have 10 seconds</strong> to do this! It's clear that we need to automate this problem with a script.</p>
<p>We can do this in many ways. In Python, for example, we can use the libraries <a href="https://docs.python.org/2/library/telnetlib.html">telnetlib</a> or <a href="https://docs.python.org/2/library/socket.html">socket</a> or even writing our <a href="https://github.com/bt3gl/CTFs-and-Hacking-Scripts-and-Tutorials/blob/master/Tutorials/Useful_Scripts/netcat.py">own netcat script</a>. We will use the former for this exploit. Let us create a telnet connection with:</p>
<div class="highlight"><pre><span class="kn">from</span> <span class="nn">telnetlib</span> <span class="kn">import</span> <span class="n">Telnet</span>
<span class="n">PORT</span> <span class="o">=</span> <span class="mi">12345</span>
<span class="n">HOST</span> <span class="o">=</span> <span class="s">'54.209.5.48'</span>
<span class="n">tn</span> <span class="o">=</span> <span class="n">Telnet</span><span class="p">(</span><span class="n">HOST</span> <span class="p">,</span><span class="n">PORT</span><span class="p">)</span>
</pre></div>
<p>In this case, socket reading can be done with <code>tn.read_until(b'psifer text: ')</code>, which reads until a given string is encountered, or <code>tn.read_all()</code>, which reads all data until EOF.</p>
<p>To write a string to the socket we do <code>tn.write(mystring.encode() + b'\n')</code>. Here, the method <a href="https://docs.python.org/2/library/stdtypes.html#str.encode">encode()</a> returns an encoded version of the string, <em>i.e</em> a translation of a sequence of bytes to a Unicode string.</p>
<p>As a side note, if we had decided to use the <a href="https://docs.python.org/2/library/socket.html">socket</a> library to create a <em>TCP socket</em>, the process would be easy as well:</p>
<div class="highlight"><pre><span class="n">s</span> <span class="o">=</span> <span class="n">socket</span><span class="p">(</span><span class="n">AF_INET</span><span class="p">,</span> <span class="n">SOCK_STREAM</span><span class="p">)</span>
<span class="n">s</span><span class="o">.</span><span class="n">connect</span><span class="p">(</span><span class="n">HOST</span><span class="p">)</span>
</pre></div>
<p>Here <code>socket.AF_UNIX, socket.AF_INET, socket.AF_INET6</code> are constants that represent the address (and protocol) families. The constants <code>socket.SOCK_STREAM, socket.SOCK_DGRAM, socket.SOCK_RAW, socket.SOCK_RDM, socket.SOCK_SEQPACKET</code>represent the socket types.</p>
<p>To read the socket stream we would use commands such as <code>s.recv(2048)</code> and for writing we could use <code>s.sendall(answer)</code>.</p>
<h4>Decrypting and Sending the Answer</h4>
<p>Now, back to our problem. After creating the telnet connection, we read whatever comes in:</p>
<div class="highlight"><pre><span class="n">tn</span><span class="o">.</span><span class="n">read_until</span><span class="p">(</span><span class="n">b</span><span class="s">'psifer text: '</span><span class="p">)</span>
</pre></div>
<p>We decode and decrypt the text, and then encode it again:</p>
<div class="highlight"><pre><span class="n">msg_in1</span> <span class="o">=</span> <span class="n">tn</span><span class="o">.</span><span class="n">read_until</span><span class="p">(</span><span class="n">b</span><span class="s">'</span><span class="se">\n</span><span class="s">'</span><span class="p">)</span><span class="o">.</span><span class="n">decode</span><span class="p">()</span><span class="o">.</span><span class="n">strip</span><span class="p">()</span>
<span class="n">dec_msg_in1</span> <span class="o">=</span> <span class="n">decipher</span><span class="p">(</span><span class="n">msg_in1</span><span class="p">)</span>
<span class="n">answer1</span> <span class="o">=</span> <span class="n">dec_msg_in1</span><span class="o">.</span><span class="n">split</span><span class="p">()[</span><span class="o">-</span><span class="mi">1</span><span class="p">]</span><span class="o">.</span><span class="n">encode</span><span class="p">()</span> <span class="o">+</span> <span class="n">b</span><span class="s">'</span><span class="se">\n</span><span class="s">'</span>
</pre></div>
<p>Finally, we send our answer to the telnet session (the same answer obtained before):</p>
<div class="highlight"><pre><span class="n">tn</span><span class="o">.</span><span class="n">write</span><span class="p">(</span><span class="n">answer1</span><span class="p">)</span>
</pre></div>
<hr />
<h2>Stage Two: Offset with Special Characters</h2>
<p>The second stage starts with the following message:</p>
<blockquote>
<p>Congratulations, you have solved stage 1. You have 9 seconds left.</p>
<p>Now it's time for something slightly more difficult. Hint, everybody knows it's
not length that matters.</p>
</blockquote>
<p>Together with the hint <em>length doesn't matter</em>, we get the following cipher (translated as a Python string variable because of the special characters):</p>
<p><code>I'lcslraooh o rga tehhywvf.retFtelh mao ae af ostloh lusr bTsfnr, epawlltddaheoo aneviedr ose rtyyng etn aini ft oooey hgbifecmoswuut!oa eeg ar rr h.u t. hylcg io we ph ftooriysneirdriIa utyco gfl oostif sp u"+'""'+"flcnb roh tprn.o h</code></p>
<p>To crack this cipher we need to deal with special characters to find the rotation shift. We proceed with the following steps:</p>
<ol>
<li>
<p>We start looping over the length of our message, where for each iteration we create a blank list with the size of the message. This is a bit <em>space-expensive</em> and it should be optimized if we needed to scale for larger problems. It's fine for our current problem.</p>
</li>
<li>
<p>We start a second loop, which will tell us about the shifts. This loop iterates again in the length of the message, this time adding the current character to the list we've created before and updating a pointer to the pacing value given in the first loop. Notice that we have a loop inside another, so this solutions has <em>O(n^2) runtime</em> and it also should be optimized for larger problems.</p>
</li>
<li>
<p>Inside this second loop, we check whether the pacing pointer is larger than the length of the message, and if this is the case, we register it in a shift counter. The former pointer receives the value of this shift. This is the end of the second loop.</p>
</li>
<li>
<p>Back to the first loop, we add all the characters so far from our list into a the message string. But when should we stop doing this? Until we make sure that had a rotation that produces real words. I tried a few of common words, and 'you' worked just fine!</p>
</li>
</ol>
<div class="highlight"><pre><span class="k">def</span> <span class="nf">solve2</span><span class="p">(</span><span class="n">msg</span><span class="p">):</span>
<span class="c"># Shift cypher, but dealing with special characters</span>
<span class="k">for</span> <span class="n">j</span> <span class="ow">in</span> <span class="nb">range</span><span class="p">(</span><span class="mi">2</span><span class="p">,</span> <span class="nb">len</span><span class="p">(</span><span class="n">msg</span><span class="p">)):</span>
<span class="n">dec_msg</span> <span class="o">=</span> <span class="p">[</span><span class="s">'0'</span><span class="p">]</span> <span class="o">*</span> <span class="nb">len</span><span class="p">(</span><span class="n">msg</span><span class="p">)</span>
<span class="n">idec_msg</span><span class="p">,</span> <span class="n">shift</span> <span class="o">=</span> <span class="mi">0</span><span class="p">,</span> <span class="mi">0</span>
<span class="k">for</span> <span class="n">i</span> <span class="ow">in</span> <span class="nb">range</span><span class="p">(</span><span class="nb">len</span><span class="p">(</span><span class="n">msg</span><span class="p">)):</span>
<span class="n">dec_msg</span><span class="p">[</span><span class="n">idec_msg</span><span class="p">]</span> <span class="o">=</span> <span class="n">msg</span><span class="p">[</span><span class="n">i</span><span class="p">]</span>
<span class="n">idec_msg</span> <span class="o">+=</span> <span class="n">j</span>
<span class="k">if</span> <span class="n">idec_msg</span> <span class="o">></span> <span class="nb">len</span><span class="p">(</span><span class="n">msg</span><span class="p">)</span> <span class="o">-</span> <span class="mi">1</span><span class="p">:</span>
<span class="n">shift</span> <span class="o">+=</span> <span class="mi">1</span>
<span class="n">idec_msg</span> <span class="o">=</span> <span class="n">shift</span>
<span class="n">dec_msg</span> <span class="o">=</span> <span class="s">""</span><span class="o">.</span><span class="n">join</span><span class="p">(</span><span class="n">dec_msg</span><span class="p">)</span>
<span class="k">if</span> <span class="s">"you"</span> <span class="ow">not</span> <span class="ow">in</span> <span class="n">dec_msg</span><span class="p">:</span> <span class="k">continue</span>
<span class="k">return</span> <span class="n">dec_msg</span>
</pre></div>
<p>After decoding this stage's cipher we get the key for the next stage, which is then sent back through the socket:</p>
<blockquote>
<p>I hope you don't have a problem with this challenge. It should be fairly straight forward if you have done lots of basic crypto. The magic phrase for your efforts is "<strong>not not wrong</strong>". For your efforts, you will get another challenge!</p>
</blockquote>
<hr />
<h2>Stage Three: Vigenere Cipher</h2>
<p>The next message lets us know that we are close to the end:</p>
<blockquote>
<p>Congratulations, you have solved stage 2. You have 9 seconds left.
Last one.</p>
</blockquote>
<p>And comes with the following cipher:</p>
<div class="highlight"><pre><span class="n">MVJJN</span> <span class="n">BQXKF</span> <span class="n">NCEPZ</span> <span class="n">WWVSH</span> <span class="n">YFCSV</span> <span class="n">JEEBB</span> <span class="n">UVRMX</span> <span class="n">HKPIE</span> <span class="n">PMMVZ</span> <span class="n">FOPME</span> <span class="n">ZQIIU</span> <span class="n">EUZZW</span> <span class="n">CGHMV</span> <span class="n">BKBTZ</span> <span class="n">BBHVR</span> <span class="n">MVTQP</span> <span class="n">ENXRM</span> <span class="n">HIRNB</span> <span class="n">WTGDZ</span> <span class="n">CFEDS</span> <span class="n">TKBBW</span> <span class="n">HBFDI</span> <span class="n">KILCM</span> <span class="n">MUUPX</span> <span class="n">WUNIN</span> <span class="n">PWPFJ</span> <span class="n">IEZTP</span> <span class="n">MVQBX</span> <span class="n">ACVKN</span> <span class="n">AEMPV</span> <span class="n">KQXAB</span> <span class="n">ZMDUD</span> <span class="n">ILISV</span> <span class="n">NHKBJ</span> <span class="n">FCIMW</span> <span class="n">HTUVR</span> <span class="n">MNNGU</span> <span class="n">KIFED</span> <span class="n">STLLX</span> <span class="n">XAOUN</span> <span class="n">YVEGV</span> <span class="n">BEXEI</span> <span class="n">BHJNI</span> <span class="n">GHXFI</span> <span class="n">FQFYV</span> <span class="n">VXZFE</span> <span class="n">FXFFH</span> <span class="n">OBVXR</span> <span class="n">MVNLT</span> <span class="n">NHUYY</span> <span class="n">FEZWD</span> <span class="n">GBKEL</span> <span class="n">SGFLM</span> <span class="n">LXBFO</span> <span class="n">NEIOS</span> <span class="n">MZHML</span> <span class="n">XAJUX</span> <span class="n">EIKWH</span> <span class="n">YNAIK</span> <span class="n">SOFLF</span> <span class="n">EEKPI</span> <span class="n">XLSDB</span> <span class="n">PNGHV</span> <span class="n">XHFON</span> <span class="n">MSFOL</span> <span class="n">VMNVX</span> <span class="n">HIRNB</span> <span class="n">XBGTF</span> <span class="n">FOEUZ</span> <span class="n">FZMAS</span> <span class="n">NZEGL</span> <span class="n">HFTPM</span> <span class="n">PDNWM</span> <span class="n">DVKCG</span> <span class="n">WHAFE</span> <span class="n">OKWXF</span> <span class="n">ZIBRQ</span> <span class="n">XCSJI</span> <span class="n">FIMVJ</span> <span class="n">EAFEK</span> <span class="n">MIRXT</span> <span class="n">PBHUC</span> <span class="n">YEEFP</span> <span class="n">MZNMP</span> <span class="n">XZBDV</span> <span class="n">EMMHM</span> <span class="n">VFTQU</span> <span class="n">ABISA</span> <span class="n">EWOMZ</span> <span class="n">NMPXZ</span> <span class="n">BDVPL</span> <span class="n">HGFWF</span> <span class="n">XISSX</span> <span class="n">RMPLB</span> <span class="n">HFRML</span> <span class="n">RHKJU</span> <span class="n">IGXPO</span> <span class="n">OKNHQ</span> <span class="n">TYFKB</span> <span class="n">BWAOS</span> <span class="n">UYKXA</span> <span class="n">OOZNG</span> <span class="n">IXRTK</span> <span class="n">IUIBT</span> <span class="n">ZFOOI</span> <span class="n">LCMMY</span> <span class="n">WEECU</span> <span class="n">FZLMF</span> <span class="n">DMVWK</span> <span class="n">CIHPT</span> <span class="n">BTPES</span> <span class="n">OXYLC</span> <span class="n">HIQII</span> <span class="n">UEUZZ</span> <span class="n">RFKIT</span> <span class="n">RZYUO</span> <span class="n">IMVFT</span> <span class="n">IWITB</span> <span class="n">ENCEP</span> <span class="n">UFFVT</span> <span class="n">XVBUI</span> <span class="n">KNAVH</span> <span class="n">IHYCM</span> <span class="n">MYWUY</span> <span class="n">YETLA</span> <span class="n">PJNHJ</span> <span class="n">MVFGF</span> <span class="n">TMGHF</span> <span class="n">ONBWL</span> <span class="n">HBKCV</span> <span class="n">EMSBT</span> <span class="n">BHJMV</span> <span class="n">FCYOI</span> <span class="n">EGJDH</span> <span class="n">HXTAB</span> <span class="n">JIVLB</span> <span class="n">GUKBX</span> <span class="n">JNBOP</span> <span class="n">NAMGU</span> <span class="n">JJNAE</span> <span class="n">MRFGY</span> <span class="n">GHBBH</span> <span class="n">FHPLB</span> <span class="n">QIIUG</span> <span class="n">HHALV</span> <span class="n">SRSNU</span> <span class="n">FKNAE</span> <span class="n">MDPVG</span> <span class="n">FMZVU</span> <span class="n">SYXBT</span> <span class="n">QUCSM</span> <span class="n">LXFJX</span> <span class="n">BMSYT</span> <span class="n">TVNMS</span> <span class="n">LIDTY</span> <span class="n">LWY</span>
</pre></div>
<p>This is a <strong><a href="http://en.wikipedia.org/wiki/Vigen%C3%A8re_cipher">Vigenere Cipher</a></strong>, which is basically several Caesar ciphers in sequence, with different shift values, given by a key-word. Finding these shifts when we don't know the key can be done by writing the alphabet 26 times in different rows. In this case, each alphabet is shifted cyclically to the left compared to the previous alphabet (26 Caesar ciphers).</p>
<p>Although we could use some <a href="http://smurfoncrack.com/pygenere/">online Vigenere cracker</a> to extract the flag from this text, we will instead write a code. We use Python's library <a href="http://smurfoncrack.com/pygenere/pygenere.php">pygenere</a>, which has the methods <code>crack_message()</code> to decipher the message and <code>crack_codeword()</code> to find the key (useful because we don't have the key). We then send our cipher to the following function:</p>
<div class="highlight"><pre><span class="k">def</span> <span class="nf">solve3</span><span class="p">(</span><span class="n">msg</span><span class="p">):</span>
<span class="n">key</span> <span class="o">=</span> <span class="n">VigCrack</span><span class="p">(</span><span class="n">msg</span><span class="p">)</span><span class="o">.</span><span class="n">crack_codeword</span><span class="p">()</span>
<span class="n">dec_msg</span> <span class="o">=</span> <span class="n">VigCrack</span><span class="p">(</span><span class="n">msg</span><span class="p">)</span><span class="o">.</span><span class="n">crack_message</span><span class="p">()</span>
<span class="n">dec_msg</span> <span class="o">=</span> <span class="n">dec_msg</span><span class="o">.</span><span class="n">replace</span><span class="p">(</span><span class="s">" "</span><span class="p">,</span> <span class="s">""</span><span class="p">)</span>
<span class="k">return</span> <span class="n">key</span><span class="p">,</span> <span class="n">dec_msg</span>
</pre></div>
<p>This will give us the <strong>key = TOBRUTE</strong> and the deciphered text. After fixing the spaces between the words, we get:</p>
<div class="highlight"><pre><span class="n">THIS</span> <span class="n">TIME</span> <span class="n">WE</span> <span class="n">WILL</span> <span class="n">GIVE</span> <span class="n">YOU</span> <span class="n">MORE</span> <span class="n">PLAINTEXT</span> <span class="n">TO</span> <span class="n">WORK</span> <span class="n">WITH</span> <span class="n">YOU</span> <span class="n">WILL</span> <span class="n">PROBABLY</span> <span class="n">FIND</span> <span class="n">THAT</span> <span class="n">HAVING</span> <span class="n">EXTRA</span> <span class="n">CONTENT</span> <span class="n">THAT</span> <span class="n">IS</span> <span class="n">ASCII</span> <span class="n">MAKES</span> <span class="n">THIS</span> <span class="n">ONE</span> <span class="n">MORE</span> <span class="n">SOLVABLE</span> <span class="n">IT</span> <span class="n">WOULD</span> <span class="n">BE</span> <span class="n">SOLVABLE</span> <span class="n">WITHOUT</span> <span class="n">THAT</span> <span class="n">BUT</span> <span class="n">WE</span> <span class="n">WILL</span> <span class="n">MAKE</span> <span class="n">SURE</span> <span class="n">TO</span> <span class="n">GIVE</span> <span class="n">LOTS</span> <span class="n">OF</span> <span class="n">TEXT</span> <span class="n">JUST</span> <span class="n">TO</span> <span class="n">MAKE</span> <span class="n">SURE</span> <span class="n">THAT</span> <span class="n">WE</span> <span class="n">CAN</span> <span class="n">HANDLE</span> <span class="n">IT</span> <span class="n">I</span> <span class="n">WONDER</span> <span class="n">HOW</span> <span class="n">MUCH</span> <span class="n">WILL</span> <span class="n">BE</span> <span class="n">REQUIRED</span> <span class="n">LETS</span> <span class="n">PUT</span> <span class="n">THE</span> <span class="n">MAGIC</span> <span class="n">PHRASE</span> <span class="n">FOR</span> <span class="n">THE</span> <span class="n">NEXT</span> <span class="n">LEVEL</span> <span class="n">IN</span> <span class="n">THE</span> <span class="n">MIDDLE</span> <span class="n">RIGHT</span> <span class="n">HERE</span> <span class="n">NORMALWORD</span> <span class="n">OK</span> <span class="n">NOW</span> <span class="n">MORE</span> <span class="n">TEXT</span> <span class="n">TO</span> <span class="n">MAKE</span> <span class="n">SURE</span> <span class="n">THAT</span> <span class="n">IT</span> <span class="n">IS</span> <span class="n">SOLVABLE</span> <span class="n">I</span> <span class="n">SHOULD</span> <span class="n">PROBABLY</span> <span class="n">JUST</span> <span class="n">PUT</span> <span class="n">IN</span> <span class="n">SOME</span> <span class="n">NURSERY</span> <span class="n">RHYME</span> <span class="n">OR</span> <span class="n">SOMETHING</span> <span class="n">MARY</span> <span class="n">HADA</span> <span class="n">LITTLE</span> <span class="n">LAMB</span> <span class="n">LITTLE</span> <span class="n">LAMB</span> <span class="n">LITTLE</span> <span class="n">LAMB</span> <span class="n">MARY</span> <span class="n">HADA</span> <span class="n">LITTLE</span> <span class="n">LAMB</span> <span class="n">WHOSE</span> <span class="n">FLEEZE</span> <span class="n">WAS</span> <span class="n">WHITE</span> <span class="n">AS</span> <span class="n">SNOW</span> <span class="n">I</span> <span class="n">DONT</span> <span class="n">WANT</span> <span class="n">TO</span> <span class="n">MAKE</span> <span class="n">THIS</span> <span class="n">HARDER</span> <span class="n">THAN</span> <span class="n">IT</span> <span class="n">NEEDS</span> <span class="n">TO</span> <span class="n">BE</span> <span class="n">IF</span> <span class="n">YOU</span> <span class="n">VE</span> <span class="n">SOLVED</span> <span class="n">A</span> <span class="n">LOT</span> <span class="n">OF</span> <span class="n">SIMPLE</span> <span class="n">CRYPTO</span> <span class="n">CHALLENGES</span> <span class="n">YOU</span> <span class="n">PROBABLY</span> <span class="n">ALREADY</span> <span class="n">HAVE</span> <span class="n">THE</span> <span class="n">CODE</span> <span class="n">AND</span> <span class="n">WILL</span> <span class="n">BREEZE</span> <span class="n">RIGHT</span> <span class="n">THROUGH</span> <span class="n">IT</span> <span class="n">IF</span> <span class="n">IT</span> <span class="n">HELPS</span> <span class="n">MOST</span> <span class="n">OF</span> <span class="n">THE</span> <span class="n">PLAINTEXT</span> <span class="n">IS</span> <span class="n">STATIC</span> <span class="n">AT</span> <span class="n">EACH</span> <span class="n">OF</span> <span class="n">THE</span> <span class="n">LEVELS</span> <span class="n">I</span> <span class="n">M</span> <span class="n">NOT</span> <span class="n">A</span> <span class="n">MASOCHIST</span> <span class="n">THE</span> <span class="n">FUNNY</span> <span class="n">THING</span> <span class="n">IS</span> <span class="n">THAT</span> <span class="n">DEPENDING</span> <span class="n">ON</span> <span class="n">WHICH</span> <span class="n">RANDOMKEY</span> <span class="n">YOU</span> <span class="n">GET</span> <span class="n">THAT</span> <span class="n">POEM</span> <span class="n">MIGHT</span> <span class="n">BE</span> <span class="n">EXACTLY</span> <span class="n">THE</span> <span class="n">RIGHT</span> <span class="n">OFFSET</span> <span class="n">TO</span> <span class="n">SUCCESSFULLY</span> <span class="n">MOUNT</span> <span class="n">AN</span> <span class="n">ATTACK</span> <span class="n">WE</span> <span class="n">LL</span> <span class="n">SEE</span> <span class="n">LITTLE</span> <span class="n">BIT</span> <span class="n">MORE</span> <span class="n">LITTLE</span> <span class="n">BIT</span> <span class="n">MORE</span> <span class="n">THERE</span><span class="p">,</span>
</pre></div>
<p>Reading it carefully give us thee last answer for the flag: <strong>NORMALWORD</strong>. Sweet!</p>
<h2>Final Words</h2>
<p>If you like this solution, take a look at my <a href="https://github.com/bt3gl/CTFs-Gray-Hacker-and-PenTesting/tree/master/CTFs_and_WarGames/2014-CSAW-CTF/cryptography/crypto-200">exploit for this problem</a>.</p>
<p><strong>Hack all the things!</strong></p>
</div><!-- /.entry-content -->
<div class="comments">
<h2>Comments !</h2>
<div id="disqus_thread"></div>
<script type="text/javascript">
var disqus_identifier = "csaw-ctf-2014-cryptography-200-psifer-school.html";
(function() {
var dsq = document.createElement('script');
dsq.type = 'text/javascript'; dsq.async = true;
dsq.src = 'http://bt3gl.disqus.com/embed.js';
(document.getElementsByTagName('head')[0] ||
document.getElementsByTagName('body')[0]).appendChild(dsq);
})();
</script>
</div>
</article>
</section>
</div><!--/span-->
</div><!--/row-->
<footer>
<address id="about">
</address><!-- /#about -->
</footer>
</div><!--/.fluid-container-->
<script src="./theme/js/jquery-1.7.2.min.js"></script>
<script src="./theme/js/bootstrap.min.js"></script>
</body>
</html>