-
Notifications
You must be signed in to change notification settings - Fork 3
/
pa5.html
604 lines (541 loc) · 34.2 KB
/
pa5.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
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd">
<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
<meta name="viewport" content="width=device-width, initial-scale=1, shrink-to-fit=no">
<link href="https://cdn.jsdelivr.net/npm/[email protected]/dist/css/bootstrap.min.css" rel="stylesheet"
integrity="sha384-1BmE4kWBq78iYhFldvKuhfTAU6auU8tT94WrHftjDbrCEXSU1oBoqyl2QvZ6jIW3" crossorigin="anonymous">
<script src="https://cdn.jsdelivr.net/npm/[email protected]/dist/js/bootstrap.bungle.min.js"
integrity="sha384-ka7Sk0Gln4gmtz2MlQnikT1wXgYsOg+OMhuP+IlRH9sENBO0LRn5q+8nbTov4+1p"
crossorigin="anonymous"></script>
<title>CSE 127 - PA5: Cryptography</title>
<style>
img {
padding: 0;
display: block;
margin: 20px 0;
max-height: 100%;
max-width: 600px;
}
body {
padding-top: 20px;
padding-bottom: 50px;
}
.tab {
margin-left: 40px;
}
td {
text-align: center;
font-family: monospace;
}
</style>
</head>
<body class="d-flex flex-column">
<main role="main" class="flex-shrink-0">
<div class="container">
<div class="row">
<div>
<h1>PA5: Cryptography <span class="text-muted courseyear"><small>Spring 2022</small></span></h1>
<div class="alert alert-primary" role="alert">
<b> Total Points: 20</b><br>
<b> Due: Wednesday, June 1st at 11:59pm</b>
</div>
<div class="md-content">
<p>This is a group project; you can work in a team of size at most four and submit one
project per team. You are not required to work with the same partner(s) on every project.
You and your partner(s) should collaborate closely on each part.</p>
<p>You have two late days that you may use to turn in work past the
deadline over the entire quarter. A late day is a contiguous 24-hour
period. Both you and your partner(s) will be charged for every late day
that you use, and you both must have late days to use them. These
late days are intended to cover your extension needs for usual
circumstances: brief illness, busy with other classes, interviews,
travel, extracurricular conflicts, and so on. You do not need to ask
permission to use a late day.</p>
<p>The code and other answers you submit must be entirely your team's
own work. You may discuss the conceptualization of the project and the
meaning of the questions, but you may not look at any part of someone
else’s solution or collaborate with anyone other than your
partner. You may consult published references, provided that you
appropriately cite them (e.g., with program comments).</p>
<p>Solutions must be submitted to Gradescope.</p>
<hr>
<h2 id="overview">Introduction</h2>
<p>In this project, we'll start by investigating Vigenere ciphers, then
move on to investigating vulnerabilities in widely used
cryptographic hash functions, including length-extension attacks and collision
vulnerabilities, and an implementation vulnerability in a popular digital
signature scheme.</p>
<hr>
<h2 id="index">Index</h2>
<ul>
<li><a href="#part-1-vigenere-ciphers">Part 1: Vigenere Ciphers</a></li>
<li><a href="#part-2-length-extension">Part 2: Length extension</a></li>
<li><a href="#part-3-md5-collisions">Part 3: MD5 collisions</a></li>
<li><a href="#part-4-rsa-signature-forgery">Part 4: RSA signature forgery</a></li>
<li><a href="#5-writeup">Part 5: Writeup</a></li>
</ul>
<hr>
<h2 id="part-1-vigenere-ciphers">Part 1: Vigenere Ciphers (4 points)</h2>
<p>For this problem, solve by hand or write a program (perhaps in Python).</p>
<p>You can read about how the Vigenere cipher works <a href="https://en.wikipedia.org/wiki/Vigen%C3%A8re_cipher#Description">on
Wikipedia</a>.
Vigenere ciphers can be generally deciphered using Kasiski Examination, which is
discussed on the wikipedia page.</p>
<p>You can find some ciphertext produced with the Vigenere cipher under a certain
key on Gradescope as the assignment "PA5: Ciphertext".</p>
<p>We also provided sample code for decrypting ciphertext <a href="assets/decrypt.py">sample decryption code here</a>.</p
<p>Encrypting a plaintext letter with a key letter <code>A</code> results in no change, encrypting
with a key letter <code>B</code> results in an increment by one place in the alphabet, encrypting with key letter <code>C</code>
results in an increment by two places, etc.
Also assume that the original plaintext contains only uppercase letters (A-Z)
and no spaces or punctuation.</p>
<p>For example, encrypting the plaintext: ATTACKATDAWN with the key: BLAISE results in the following ciphertext:</p>
<table>
<tr>
<td>Plaintext: </td>
<td>A</td>
<td>T</td>
<td>T</td>
<td>A</td>
<td>C</td>
<td>K</td>
<td>A</td>
<td>T</td>
<td>D</td>
<td>A</td>
<td>W</td>
<td>N</td>
</tr>
<tr>
<td>Key: </td>
<td>B</td>
<td>L</td>
<td>A</td>
<td>I</td>
<td>S</td>
<td>E</td>
<td>B</td>
<td>L</td>
<td>A</td>
<td>I</td>
<td>S</td>
<td>E</td>
</tr>
<tr>
<td>Ciphertext: </td>
<td>B</td>
<td>E</td>
<td>T</td>
<td>I</td>
<td>U</td>
<td>O</td>
<td>B</td>
<td>E</td>
<td>D</td>
<td>I</td>
<td>O</td>
<td>R</td>
</tr>
</table>
<p>The goal for this part of the assignment is to figure out what key was used to encrypt your ciphertext.</p>
<p><strong>What to submit</strong> A text file named <code>vigenere.key</code> containing your key. </p>
<p><em>Historical note</em>: In November 2019, it was discovered that the security company
Fortinet was using "XOR encryption with a static key" in some products, which
is similar to a Vigenere cipher and has similar (lack of) security properties.
<a href="https://seclists.org/bugtraq/2019/Nov/38">https://seclists.org/bugtraq/2019/Nov/38</a></p>
</div>
<hr>
<h2 id="part-2-length-extension">Part 2: Length extension (4 points)</h2>
<p>For many applications, you should use MACs such as HMAC-SHA256 instead of plain
cryptographic hash functions (e.g., MD5, SHA-1, or SHA-256) because hashes, also
known as digests, do not provide security against an attacker who can control or modify the hash value. What we
really want is something that behaves like a pseudorandom function, which HMAC and other MAC functions
are constructed to behave like and hash functions alone do not.</p>
<p>One difference between hash functions and pseudorandom functions is that a collision-resistant hash function
may still be subject to <em>length extension</em>. Many common hash functions use a
design called the Merkle-Damgard construction. Each is built around a
<em>compression function</em> <em>f</em> and maintains an internal state <em>s</em>, which is
initialized to a fixed constant. Messages are processed in fixed-size blocks
by applying the compression function to the current state and current block to
compute an updated internal state, i.e., s_{i+1} = f(s_i, b_i). The result
of the final application of the compression function becomes the output of the
hash function.</p>
<p>A consequence of this design is that if we know the hash of an <em>n</em>-block
message, we can find the hash of longer messages by applying the compression
function for each block b_{n+1}, b_{n+2}, ... that we want to add. This
process is called length extension, and it can be used to attack many
applications of hash functions.</p>
<h3 id="experimenting">Experimenting</h3>
<p>To experiment with this idea, we'll use a Python implementation of the MD5 hash
function, though SHA-1 and SHA-256 are vulnerable to length extension in the
same way. You can <a href="assets/pymd5.py">download the <code>pymd5</code> module here</a> and
learn how to use it by running <code>pydoc pymd5</code>. To follow
along with these examples, run Python in interactive mode and run the command
<code>from pymd5 import md5, padding</code>.</p>
<p>Consider the string "Use HMAC, not hashes". We can compute its MD5 hash by
running:</p>
<pre><code>
from pymd5 import md5, padding
m = "Use HMAC, not hashes"
h = md5()
h.update(m)
print(h.hexdigest())
</code></pre>
<p>or, more compactly,</p>
<div class="codehilite"><pre><span></span><span class="nb">print</span><span class="p">(</span><span class="n">md5</span><span class="p">(</span><span class="n">m</span><span class="p">)</span><span class="o">.</span><span class="n">hexdigest</span><span class="p">())</span>
</pre></div>
<p>The output should be <code>3ecc68efa1871751ea9b0b1a5b25004d</code>.</p>
<p>MD5 processes messages in 512-bit blocks, so internally, the hash function
pads <em>m</em> to a multiple of that length. The padding consists of the bit 1,
followed by as many 0 bits as necessary, followed by a 64-bit count of the
number of bits in the unpadded message. (If the 1 and the count won't fit in
the current block, an additional block is added.) You can use the function
<code>padding(count)</code> in the <code>pymd5</code> module to compute the padding that will be
added to a <em>count</em>-bit message.</p>
<p>Even if we didn't know <em>m</em>, we could compute the hash of longer messages of the
general form <code>m + padding(len(m)*8) + suffix</code> by setting the initial internal
state of our MD5 function to <code>MD5(m)</code>, instead of the default initialization
value, and setting the function's message length counter to the size of <em>m</em>
plus the padding (a multiple of the block size). To find the padded message
length, guess the length of <em>m</em> and run <code>bits = (length_of_m +
len(padding(length_of_m * 8))) * 8</code>.</p>
<p>The <code>pymd5</code> module lets you specify these parameters as additional arguments
to the <code>md5</code> object:</p>
<div class="codehilite"><pre><span></span><span class="n">h</span> <span class="o">=</span> <span class="n">md5</span><span class="p">(</span><span class="n">state</span><span class="o">=</span><span class="n">bytes</span><span class="o">.</span><span class="n">fromhex</span><span class="p">(</span><span class="s2">"3ecc68efa1871751ea9b0b1a5b25004d"</span><span class="p">),</span> <span class="n">count</span><span class="o">=</span><span class="mi">512</span><span class="p">)</span>
</pre></div>
<p>Now you can use length extension to find the hash of a longer string that
appends the suffix "Good advice". Simply run:</p>
<pre><code>
x = "Good advice"
h.update(x)
print(h.hexdigest())
</code></pre>
<p>to execute the compression function over <em>x</em> and output the resulting hash.
Verify that it equals the MD5 hash of <code>m.encode("utf-8") + padding(len(m)*8) + x.encode("utf-8")</code>. In Python 3, we need to convert <code>m</code>
and <code>x</code> from strings to bytes so that we can add these to the
padding, which is a <code>bytes</code> type.
Notice that, due to the length-extension property of MD5, we didn't need to know
the value of <code>m</code> to compute the hash of the longer string - all we needed to
know was <code>m</code>'s length and its MD5 hash.</p>
<h3 id="conduct-a-length-extension-attack">Conduct a length extension attack</h3>
<p>Length extension attacks can cause serious vulnerabilities when people
try to construct something like a MAC by using <em>hash(secret
|| message)</em> using a hash function like MD5, SHA1, or SHA2, that is vulnerable to length extension.
(SHA3, unlike SHA-256, SHA1, and MD5, uses a different construction and is not vulnerable to length extension attacks, so <em>SHA3(secret || message)</em> <i>is</i> a secure MAC. This is why cryptography is hard.)</p>
<p>The National Bank of CSE 127, which is not up-to-date on
its security practices, hosts an API that allows its client-side applications
to perform actions on behalf of a user by loading URLs of the form:</p>
<p><code>http://bank.cse127.ucsd.edu/pa5/api?token=6c256f4a53dd0068b2d82306d9c09d1c&user=george&command1=ListSquirrels&command2=NoOp</code></p>
<p>where <code>token</code> is MD5(<em>user's 8-character password</em> || <code>user=...</code> <em>[the rest of
the decoded URL starting from user= and ending with the last command]</em>).</p>
<p>Using the techniques that you learned in the previous section and without
guessing the password, apply length extension to create a URL ending with
<code>&command3=UnlockAllSafes</code> that would be treated as valid by the server API.</p>
<p><em>Note</em>: Because of its bad security practices, the National Bank of CSE 127 has
taken down its website. So you'll have to use gradescope to test if your attack
URL would work.</p>
<p><em>Hint</em>: You might want to use the <code>quote()</code> function from Python's <code>urllib.parse</code>
module to encode non-ASCII characters in the URL.</p>
<p><em>Historical fact</em>: In 2009, security researchers found that the API used by
the photo-sharing site Flickr suffered from a length-extension vulnerability
almost exactly like the one in this exercise.</p>
<p><strong>What to submit</strong> A Python 3.x script named <code>len_ext_attack.py</code> that:</p>
<ol>
<li>Accepts a valid URL in the same form as the one above as a command line argument.</li>
<li>Modifies the URL so that it will execute the <code>UnlockAllSafes</code> command as the user.</li>
<li>Prints the new URL to the command line.</li>
</ol>
<p>You should make the following assumptions:</p>
<ul>
<li>
<p>The input URL will have the same form as the sample above, but we may change the
server hostname and the values of <code>token</code>, <code>user</code>, <code>command1</code>, and <code>command2</code>.
These values may be of substantially different lengths than in the sample.</p>
</li>
<li>
<p>The input URL may be for a user with a different password, but the length of the
password will be unchanged.</p>
</li>
</ul>
<p>You can base your code on the following example:</p>
<pre><code>
import sys, urllib.parse
from pymd5 import md5, padding
url = sys.argv[1]
# Your code to modify url goes here
print(new_url)
</code></pre>
<hr>
<h2 id="part-3-md5-collisions">Part 3: MD5 collisions (4 points)</h2>
<p>MD5 was once the most widely used cryptographic hash function, but today it is
considered dangerously insecure. This is because cryptanalysts have discovered
efficient algorithms for finding <em>collisions</em>---pairs of messages with the
same MD5 hash value.</p>
<p>The first known collisions were announced on August 17, 2004 by Xiaoyun Wang,
Dengguo Feng, Xuejia Lai, and Hongbo Yu. Here's one pair of colliding messages
they published:</p>
<p>Message 1:</p>
<pre><code>
d131dd02c5e6eec4693d9a0698aff95c 2fcab58712467eab4004583eb8fb7f89
55ad340609f4b30283e488832571415a 085125e8f7cdc99fd91dbdf280373c5b
d8823e3156348f5bae6dacd436c919c6 dd53e2b487da03fd02396306d248cda0
e99f33420f577ee8ce54b67080a80d1e c69821bcb6a8839396f9652b6ff72a70
</code></pre>
<p>Message 2:</p>
<pre><code>
d131dd02c5e6eec4693d9a0698aff95c 2fcab50712467eab4004583eb8fb7f89
55ad340609f4b30283e4888325f1415a 085125e8f7cdc99fd91dbd7280373c5b
d8823e3156348f5bae6dacd436c919c6 dd53e23487da03fd02396306d248cda0
e99f33420f577ee8ce54b67080280d1e c69821bcb6a8839396f965ab6ff72a70
</code></pre>
<p>Copy the above hex strings into file1.hex and file2.hex.
Convert each group of hex strings into a binary file.
(On Linux, run <code>xxd -r -p file.hex > file</code>.)</p>
<ol>
<li>What are the MD5 hashes of the two binary files? Verify that they're the same.
(<code>openssl dgst -md5 file1 file2</code>)</li>
<li>What are their SHA-256 hashes? Verify that they're different.
(<code>openssl dgst -sha256 file1 file2</code>)</li>
</ol>
<h3 id="3a-generating-collisions-yourself">3a. Generating collisions yourself</h3>
<p>In 2004, Wang's method took more than 5 hours to find a collision on a desktop
PC. Since then, researchers have introduced vastly more efficient collision
finding algorithms, and found a collision for SHA1 as well, though that attack is not yet efficient enough to give as an undergraduate assignment. You can compute your own MD5 collisions using a tool
written by Marc Stevens that uses a more advanced technique.</p>
<p>You can download the <code>fastcoll</code> tool here:</p>
<p><a href="http://www.win.tue.nl/hashclash/fastcoll_v1.0.0.5.exe.zip">http://www.win.tue.nl/hashclash/fastcoll_v1.0.0.5.exe.zip</a>
(Windows executable)</p>
<p>or</p>
<p><a href="http://www.win.tue.nl/hashclash/fastcoll_v1.0.0.5-1_source.zip">http://www.win.tue.nl/hashclash/fastcoll_v1.0.0.5-1_source.zip</a>
(source code)</p>
<p>If you are compiling <code>fastcoll</code> from source, you can compile
using this <a href="assets/fastcoll_Makefile">makefile</a>. You will also need to
have installed the Boost libraries. On Ubuntu, you can install using <code>apt-get
install libboost-all-dev</code>. On OS X, you can install Boost via the <a href="http://brew.sh">Homebrew
package manager</a> using <code>brew install boost</code>.</p>
<ol>
<li>
<p>Generate your own collision with this tool. How long did it take?
(<code>time ./fastcoll -o file1 file2</code>)</p>
</li>
<li>
<p>What are your files? To get a hex dump, run <code>xxd -p file</code>.</p>
</li>
<li>
<p>What are their MD5 hashes? Verify that they're the same.</p>
</li>
<li>
<p>What are their SHA-256 hashes? Verify that they're different.</p>
</li>
</ol>
<p><strong>What to submit</strong> Write your answers in <code>writeup.txt</code>. This file will also be
used for part 5. </p>
<h3 id="3b-a-hash-collision-attack">3b. A hash collision attack</h3>
<p>The collision attack lets us generate two messages with the same MD5 hash and
any chosen (identical) prefix. Due to MD5's length-extension behavior, we can
append any suffix to both messages and know that the longer messages will also
collide. This lets us construct files that differ only in a binary "blob" in
the middle and have the same MD5 hash, i.e. <em>prefix</em> || <em>blobA</em> || <em>suffix</em>
and <em>prefix</em> || <em>blobB</em> || <em>suffix</em>.</p>
<p>We can leverage this to create two programs (shell scripts) that have identical
MD5 hashes but wildly different behaviors. We're using shell scripts, but this
could be done using a program in almost any language. Put the following two
lines into a file called <code>prefix</code>:</p>
<pre><code>
#!/bin/bash
cat << "EOF" | openssl dgst -sha256 > DIGEST
</code></pre>
<p>and put these four lines (starting with a blank line) into a file called <code>suffix</code>:</p>
<pre><code>
EOF
digest=$(cat DIGEST | sed 's/(stdin)= //' )
echo "The sha256 digest is $digest"
</code></pre>
<p>Now use <code>fastcoll</code> to generate two files with the same MD5 hash that both begin
with <code>prefix</code>. (<code>fastcoll -p prefix -o col1 col2</code>.) Then append the suffix to both
(<code>cat col1 suffix > file1.sh; cat col2 suffix > file2.sh</code>). Verify that <code>file1.sh</code>
and <code>file2.sh</code> have the same MD5 hash but generate different output.</p>
<p>Extend this technique to produce another pair of programs, <code>good</code> and <code>evil</code>, that
also share the same MD5 hash. One program should execute a benign payload: echo
or print <code>"I mean no harm."</code> The second should execute a pretend malicious payload:
echo or print <code>"You are doomed!"</code></p>
<p><strong>What to submit</strong> Two scripts, <code>good</code> and <code>evil</code>, that have the same MD5 hash, have
different SHA-256 hashes, and print the specified messages.</p>
<hr>
<h2 id="part-4-rsa-signature-forgery">Part 4: RSA signature forgery (4 points)</h2>
<p>A secure implementation of RSA encryption or digital signatures requires a
proper padding scheme. RSA without padding, also known as <em>textbook RSA</em>,
has several undesirable properties. For example, it is trivial for an attacker
with only an RSA public key pair <em>(n,e)</em> to produce a mathematically valid
message, signature pair by choosing an <em>s</em> and returning <em>(s^e, s)</em>.</p>
<p>In order to prevent an attacker from being able to forge valid signatures in
this way, RSA implementations use a padding scheme to provide structure to the
messages that are encrypted or signed. The most commonly used padding scheme
in practice is defined by the PKCS #1 v1.5 standard, which can be found at
<a href="https://tools.ietf.org/html/rfc2313">https://tools.ietf.org/html/rfc2313</a>.
The standard defines, among other things, the format of RSA keys and signatures
and the procedures for generating and validating RSA signatures.</p>
<h3 id="4a-validating-rsa-signatures">Validating RSA signatures</h3>
<p>You can experiment with validating RSA signatures yourself. Create a file called
<code>key.pub</code> that contains the following RSA public key:</p>
<pre><code>
-----BEGIN PUBLIC KEY-----
MFowDQYJKoZIhvcNAQEBBQADSQAwRgJBALB8X0rLPrfgAfXMW73LjKYb5V9QG5LU
DrmsA9CAittsLvh2c082wHwVyCIiWQ8S3AA/jfW839sFN4zAZkW2S3cCAQM=
-----END PUBLIC KEY-----
</code></pre>
<p>You can view the modulus and public exponent of this key by running:</p>
<pre> <code>openssl rsa -in key.pub -pubin -text -noout</code> </pre>
<p>Create a file containing only the text <code>CSE 127 rul3z!</code>.</p>
<pre> <code>echo -n 'CSE 127 rul3z!' > message</code> </pre>
<p>The following is a base64-encoded signature of the file <code>message</code> using the public
key above.</p>
<pre> <code> RaHHC2E0qm1sauuhlV3KBGiaTb5IGmaaNFQn22ykTSu88EIBkBG48gjiamc3l+4HJYUwpZDefcT2dLPyaOHA/w== </code> </pre>
<p>Convert this signature into a binary file:</p>
<pre> <code>base64 -d -i sig.b64 > sig</code> </pre>
<p>Now verify the signature against the file you created.</p>
<pre> <code>openssl dgst -sha1 -verify key.pub -signature sig message</code> </pre>
<p>We can also use basic math operations in Python to explore this signature further.
Remember, RSA ciphertexts, plaintexts, exponents, moduli, and signatures are actually
all integers.</p>
<p>Open a Python shell and run the following commands to import the signature as an integer:</p>
<pre><code>
from Crypto.PublicKey import RSA
from Crypto.Hash import SHA
signature = int(open('sig', 'rb').read().hex(), 16)
</code></pre>
<p>Next, import the public key file that you created earlier:</p>
<pre><code>pubkey = RSA.importKey(open('key.pub').read())</code></pre>
<p>The modulus and exponent are then accessible as <code>pubkey.n</code> and <code>pubkey.e</code>, respectively.
Now reverse the signing operation and examine the resulting value in hex:</p>
<pre><code>"{:0128x}".format(pow(signature, pubkey.e, pubkey.n))</code></pre>
<p>You should see something like <code>'0001fffff ... 22c1422dac3c4e5fdd87040b3fb156acd3d83d1f'</code>
Verify that the last 20 bytes of this value match the SHA-1 hash of your file:</p>
<pre><code>SHA.new(b"CSE 127 rul3z!").hexdigest()</code></pre>
<h3 id="4b-pkcs-1-v15-signature-padding">PKCS #1 v1.5 signature padding</h3>
<p>The signed value you examined in the previous section had been padded using the
PKCS #1 v1.5 signature scheme. PKCS #1 v1.5 padding for RSA signatures is
structured as follows: one <code>00</code> byte, one <code>01</code> byte, some
<code>FF</code> bytes, another <code>00</code> byte, some special ASN.1 bytes denoting
which hash algorithm was used to compute the hash digest, then the bytes of the
hash digest itself. The number of <code>FF</code> bytes varies such that the size
of <em>m</em> is equal to the size of the RSA key.</p>
<p>A <em>k</em>-bit RSA key used to sign a SHA-1 hash digest will generate the following
padded value of <em>m</em>:</p>
<pre><code>
00 01 FF...FF 00 3021300906052B0E03021A05000414 XX...XX
^^^^^^^ ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ ^^^^^^^
k/8 - 38 bytes wide || 20-byte SHA-1 digest
ASN.1 "magic" bytes
</code></pre>
<p>When PKCS padding is used, it is important for implementations to verify that
every bit of the padded, signed message is exactly as it should be. It is
tempting for an implementer to validate the signature by first stripping off
the <code>00 01</code> bytes, then some number of padding <code>FF</code> bytes, then
<code>00</code>, and then parse the ASN.1 and verify the hash. If the
implementation does not check the length of the <code>FF</code> bytes and that the
hash is in the least significant bits of the message, then it is possible for
an attacker to forge values that pass this validation check.</p>
<p>This possibility is particularly troubling for signatures generated with <em>e =
3</em>. If the length of the required padding, ASN.1 bytes, and hash value is
significantly less than <em>n^{1/3}</em> then an attacker can construct a cube root
over the integers whose most significant bits will validate as a correct
signature, ignoring the actual key. To construct a "signature" that will
validate against such implementations, an attacker simply needs to construct an
integer whose most significant bytes have the correct format, including the
hashed message, pad the remainder of this value with zeros or other garbage
that will be ignored by the vulnerable implementation, and then take a cube
root over the integers, rounding as appropriate.</p>
<h3 id="4c-constructing-forged-signatures">Constructing forged signatures</h3>
<p>The National Bank of CSE 127 has a website that its employees
use to initiate wire transfers between bank accounts. To authenticate each
transfer request, the control panel requires a signature from a particular
2048-bit RSA key:</p>
<pre><code>
-----BEGIN PUBLIC KEY-----
MIIBIDANBgkqhkiG9w0BAQEFAAOCAQ0AMIIBCAKCAQEAqtMbmgeGOL5l+sylkG5C
AgAmCmCXmN/KNFuIJaF1cxKMoiZzlqew3DVNF+Xs5rkFkzrflw2MVLY8SQl/qyRO
yHNy68OVwXeAbSIyY/8reUh2AXTm013HVS+LvI6yVOgQ4AwvfbuAPQ4B+nYbkK9G
wgHczJrChPMOaZz7yMBBwwEeonqdeNkuAyAsM/E7UmxCsR3FdMF3vuARLY/+7UJx
wDMFO1LMt5zOrQtK3AKiT4GTv4orBMAZ159ocBawpq6Z5emuI6opGavxLrjTlQgG
KagUNHhQXnQ/+pX6wPuMzWVv21z6L6m3Fbm/bWpyLteftEO7d+vMS8HTDzFQgjN2
bwIBAw==
-----END PUBLIC KEY-----
</code></pre>
<p>Unfortunately, this
control panel is running old software that has not been patched to fix the
signature forgery vulnerability.</p>
<p>Using the signature forgery technique described above, produce an RSA signature
that validates against the National Bank of CSE 127 site.</p>
<p><em>Historical fact:</em> This attack was discovered by Daniel Bleichenbacher, who
presented it in a lightning talk at the rump session at the Crypto 2006
conference. His talk is described in this mailing list posting:
<a href="https://www.ietf.org/mail-archive/web/openpgp/current/msg00999.html">https://www.ietf.org/mail-archive/web/openpgp/current/msg00999.html</a>.
At the time, many important implementations of RSA signatures were discovered
to be vulnerable to this attack, including OpenSSL. In 2014, the Mozilla
library NSS was found to be vulnerable to this type of attack:
<a href="https://www.mozilla.org/security/advisories/mfsa2014-73">https://www.mozilla.org/security/advisories/mfsa2014-73/</a>.</p>
<p><strong>What to submit</strong> A Python 3.x script called <code>bleichenbacher.py</code> that:</p>
<ol>
<li>Accepts a double-quoted string as command-line argument.</li>
<li>Prints a base64-encoded forged signature of the input string.</li>
</ol>
<p>We have provided a Python library, <code>roots.py</code>, that
provides several useful functions that you may wish to use when implementing
your solution. You can <a href="assets/roots.py">download the library here</a>. Your program
may assume that PyCrypto and <code>roots.py</code> are available, and may use standard
Python libraries, but should otherwise be self-contained.</p>
<p>In order to use these functions, you will have to import <code>roots.py</code>. You
may wish to use the following template:</p>
<pre><code>
from Crypto.PublicKey import RSA
from Crypto.Hash import SHA
from roots import *
import sys
message = sys.argv[1]
# Your code to forge a signature goes here.
# some example functions from roots
root, is_exact = integer_nthroot(27, 3)
print(integer_to_base64(root).decode())
</code></pre>
<hr>
<h2 id="5-writeup">5. Writeup (4 points)</h2>
<ol>
<li>
<p>With reference to the construction of HMAC, explain how changing the design
of the API in <a href="#conduct-a-length-extension-attack">Part 2</a> to use <code>token=HMAC(_user's password_)(user=...)</code> would avoid
the length extension vulnerability.</p>
</li>
<li>
<p>Briefly explain why the technique you explored in 3b poses a danger
to systems that rely on digital signatures to verify the integrity of programs
before they are installed or executed. Examples include Microsoft Authenticode
and most Linux package managers. (Assume that these systems sign MD5 hashes of
the programs.)</p>
</li>
<li>
<p>Since 2010, NIST has specified that RSA public exponents must be at least
2^16 + 1. Briefly explain why Bleichenbacher's attack would not work for these
keys.</p>
</li>
<li>
<p>Remember to also add your answer to 3a in the writeup</p>
</li>
</ol>
<p><strong>What to submit</strong> Write your answers in <code>writeup.txt</code>.</p>
<h2 id="submission-checklist">Submission Checklist</h2>
<p>Submit the following to gradescope:</p>
<ul>
<li><p><code>vigenere.key</code> (for part 1)</p></li>
<li><p><code>len_ext_attack.py</code> (for part 2)</p></li>
<li><p><code>good</code> and <code>evil</code> (for part 3b)</p></li>
<li><p><code>bleichenbacher.py</code> (for part 4)</p></li>
<li><p><code>writeup.txt</code> </p></li>
</ul>
</div>
</div>
</div>
</main>
</body>
</html>