Line data Source code
1 : /* t-stutter.c - Test the stutter exploit.
2 : * Copyright (C) 2016 g10 Code GmbH
3 : *
4 : * This file is part of GnuPG.
5 : *
6 : * GnuPG is free software; you can redistribute it and/or modify
7 : * it under the terms of the GNU General Public License as published by
8 : * the Free Software Foundation; either version 3 of the License, or
9 : * (at your option) any later version.
10 : *
11 : * GnuPG is distributed in the hope that it will be useful,
12 : * but WITHOUT ANY WARRANTY; without even the implied warranty of
13 : * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 : * GNU General Public License for more details.
15 : *
16 : * You should have received a copy of the GNU General Public License
17 : * along with this program; if not, see <http://www.gnu.org/licenses/>.
18 : */
19 :
20 : /* This test is based on the paper: "An Attack on CFB Mode Encryption
21 : * as Used by OpenPGP." This attack uses a padding oracle to decrypt
22 : * the first two bytes of each block (which are normally 16 bytes
23 : * large). Concretely, if an attacker can use this attack if it can
24 : * sense whether the quick integrity check failed. See RFC 4880,
25 : * Section 5.7 for an explanation of this quick check.
26 : *
27 : * The concrete attack, as described in the paper, only works for
28 : * PKT_ENCRYPTED packets; it does not work for PKT_ENCRYPTED_MDC
29 : * packets, which use a slightly different CFB mode (they don't
30 : * include a sync after the IV). But, small modifications should
31 : * allow the attack to work for PKT_ENCRYPTED_MDC packets.
32 : *
33 : * The cost of this attack is 2^15 + i * 2^15 oracle queries, where i
34 : * is the number of blocks the attack wants to decrypt. This attack
35 : * is completely unfeasible when gpg is used interactively, but it
36 : * could work when used as a service.
37 : *
38 : * How to generate a test message:
39 : *
40 : * $ echo 0123456789abcdefghijklmnopqrstuvwxyz | \
41 : * gpg --disable-mdc -z 0 -c > msg.asc
42 : * $ gpg --list-packets msg.asc
43 : * # Make sure the encryption packet contains a literal packet (without
44 : * # any nesting).
45 : * $ gpgsplit msg.asc
46 : * $ gpg --show-session-key -d msg.asc
47 : * $ ./t-stutter --debug SESSION_KEY 000002-009.encrypted
48 : */
49 :
50 : #include <config.h>
51 : #include <errno.h>
52 : #include <ctype.h>
53 :
54 : #include "gpg.h"
55 : #include "main.h"
56 : #include "../common/types.h"
57 : #include "util.h"
58 : #include "dek.h"
59 : #include "../common/logging.h"
60 :
61 : static void
62 0 : log_hexdump (byte *buffer, int length)
63 : {
64 0 : int written = 0;
65 :
66 0 : fprintf (stderr, "%d bytes:\n", length);
67 0 : while (length > 0)
68 : {
69 0 : int have = length > 16 ? 16 : length;
70 : int i;
71 0 : char formatted[2 * have + 1];
72 0 : char text[have + 1];
73 :
74 0 : fprintf (stderr, "%-8d ", written);
75 0 : bin2hex (buffer, have, formatted);
76 0 : for (i = 0; i < 16; i ++)
77 : {
78 0 : if (i % 2 == 0)
79 0 : fputc (' ', stderr);
80 0 : if (i % 8 == 0)
81 0 : fputc (' ', stderr);
82 :
83 0 : if (i < have)
84 0 : fwrite (&formatted[2 * i], 2, 1, stderr);
85 : else
86 0 : fwrite (" ", 2, 1, stderr);
87 : }
88 :
89 0 : for (i = 0; i < have; i ++)
90 0 : if (isprint (buffer[i]))
91 0 : text[i] = buffer[i];
92 : else
93 0 : text[i] = '.';
94 0 : text[i] = 0;
95 :
96 0 : fprintf (stderr, " ");
97 0 : if (strlen (text) > 8)
98 : {
99 0 : fwrite (text, 8, 1, stderr);
100 0 : fputc (' ', stderr);
101 0 : fwrite (&text[8], strlen (text) - 8, 1, stderr);
102 : }
103 : else
104 0 : fwrite (text, strlen (text), 1, stderr);
105 0 : fputc ('\n', stderr);
106 :
107 0 : buffer += have;
108 0 : length -= have;
109 0 : written += have;
110 : }
111 :
112 0 : return;
113 : }
114 :
115 : static char *
116 0 : hexstr (const byte *bytes)
117 : {
118 : static int i;
119 : static char bufs[100][7];
120 :
121 0 : i ++;
122 0 : if (i == 100)
123 0 : i = 0;
124 :
125 0 : sprintf (bufs[i], "0x%02X%02X", bytes[0], bytes[1]);
126 0 : return bufs[i];
127 : }
128 :
129 : /* xor the two bytes starting at A with the two bytes starting at B
130 : and return the result. */
131 : static byte *
132 9 : bufxor2 (const byte *a, const byte *b)
133 : {
134 : static int i;
135 : static char bufs[100][2];
136 :
137 9 : i ++;
138 9 : if (i == 100)
139 0 : i = 0;
140 :
141 9 : bufs[i][0] = a[0] ^ b[0];
142 9 : bufs[i][1] = a[1] ^ b[1];
143 9 : return bufs[i];
144 : }
145 :
146 : /* The session key stays constant. */
147 : static DEK dek;
148 : int blocksize;
149 :
150 : /* Decode the session key, which is in the format output by gpg
151 : --show-session-key. */
152 : static void
153 1 : parse_session_key (char *session_key)
154 : {
155 : char *tail;
156 1 : char *p = session_key;
157 :
158 1 : errno = 0;
159 1 : dek.algo = strtol (p, &tail, 10);
160 1 : if (errno || (tail && *tail != ':'))
161 0 : log_fatal ("Invalid session key specification. "
162 : "Expected: cipher-id:HEXADECIMAL-CHRACTERS\n");
163 :
164 : /* Skip the ':'. */
165 1 : p = tail + 1;
166 :
167 1 : if (strlen (p) % 2 != 0)
168 0 : log_fatal ("Session key must consist of an even number of hexadecimal characters.\n");
169 :
170 1 : dek.keylen = strlen (p) / 2;
171 1 : log_assert (dek.keylen <= sizeof (dek.key));
172 :
173 1 : if (hex2bin (p, dek.key, dek.keylen) == -1)
174 0 : log_fatal ("Session key must only contain hexadecimal characters\n");
175 :
176 1 : blocksize = openpgp_cipher_get_algo_blklen (dek.algo);
177 1 : if ( !blocksize || blocksize > 16 )
178 0 : log_fatal ("unsupported blocksize %u\n", blocksize );
179 :
180 1 : return;
181 : }
182 :
183 : /* The ciphertext, the plaintext as decrypted by the good session key,
184 : and the cfb stream (derived from the ciphertext and the
185 : plaintext). */
186 : static int msg_len;
187 : static byte *msg;
188 : static byte *msg_plaintext;
189 : static byte *msg_cfb;
190 :
191 : /* Whether we need to resynchronize the CFB after writing the random
192 : data (this is the case for encrypted packets, but not encrypted and
193 : integrity protected packets). */
194 : static int sync;
195 :
196 : static int
197 65096 : block_offset (int i)
198 : {
199 65096 : int extra = 0;
200 :
201 65096 : log_assert (i >= 1);
202 : /* Make sure blocksize has been initialized. */
203 65096 : log_assert (blocksize);
204 :
205 65096 : if (i > 2)
206 : {
207 65095 : i -= 2;
208 65095 : extra = blocksize + 2;
209 : }
210 65096 : return (i - 1) * blocksize + extra;
211 : }
212 :
213 : /* Return the ith block from TEXT. The first block is labeled 1.
214 : Note: consistent with the OpenPGP message format, the second block
215 : (i=2) is just 2 bytes. */
216 : static byte *
217 65093 : block (byte *text, int len, int i)
218 : {
219 65093 : int offset = block_offset (i);
220 :
221 65093 : log_assert (offset < len);
222 65093 : return &text[offset];
223 : }
224 :
225 : /* Return true if the quick integrity check passes. Also, if
226 : PLAINTEXTP is not NULL, return the decrypted plaintext in
227 : *PLAINTEXTP. If CFBP is not NULL, return the CFB byte stream in
228 : *CFBP. */
229 : static int
230 88750 : oracle (int debug, byte *ciphertext, int len, byte **plaintextp, byte **cfbp)
231 : {
232 88750 : int rc = 0;
233 : unsigned nprefix;
234 88750 : gcry_cipher_hd_t cipher_hd = NULL;
235 88750 : byte *plaintext = NULL;
236 88750 : byte *cfb = NULL;
237 :
238 : /* Make sure DEK was initialized. */
239 88750 : log_assert (dek.algo);
240 88750 : log_assert (dek.keylen);
241 88750 : log_assert (blocksize);
242 :
243 88750 : nprefix = blocksize;
244 88750 : if (len < nprefix + 2)
245 : {
246 : /* An invalid message. We can't check that during parsing
247 : because we may not know the used cipher then. */
248 0 : rc = gpg_error (GPG_ERR_INV_PACKET);
249 0 : goto leave;
250 : }
251 :
252 88750 : rc = openpgp_cipher_open (&cipher_hd, dek.algo,
253 : GCRY_CIPHER_MODE_CFB,
254 : (! sync /* ed->mdc_method || dek.algo >= 100 */ ?
255 : 0 : GCRY_CIPHER_ENABLE_SYNC));
256 88750 : if (rc)
257 0 : log_fatal ("Failed to open cipher: %s\n", gpg_strerror (rc));
258 :
259 88750 : rc = gcry_cipher_setkey (cipher_hd, dek.key, dek.keylen);
260 88750 : if (gpg_err_code (rc) == GPG_ERR_WEAK_KEY)
261 : {
262 0 : log_info ("WARNING: message was encrypted with"
263 : " a weak key in the symmetric cipher.\n");
264 0 : rc=0;
265 : }
266 88750 : else if( rc )
267 0 : log_fatal ("key setup failed: %s\n", gpg_strerror (rc));
268 :
269 88750 : gcry_cipher_setiv (cipher_hd, NULL, 0);
270 :
271 88750 : if (debug)
272 : {
273 0 : log_debug ("Encrypted data:\n");
274 0 : log_hexdump(ciphertext, len);
275 : }
276 88750 : plaintext = xmalloc_clear (len);
277 88750 : gcry_cipher_decrypt (cipher_hd, plaintext, blocksize + 2,
278 88750 : ciphertext, blocksize + 2);
279 88750 : gcry_cipher_sync (cipher_hd);
280 88750 : if (len > blocksize+2)
281 3 : gcry_cipher_decrypt (cipher_hd,
282 2 : &plaintext[blocksize+2], len-(blocksize+2),
283 2 : &ciphertext[blocksize+2], len-(blocksize+2));
284 :
285 88750 : if (debug)
286 : {
287 0 : log_debug ("Decrypted data:\n");
288 0 : log_hexdump (plaintext, len);
289 0 : log_debug ("R_{b-1,b} = %s\n", hexstr (&plaintext[blocksize - 2]));
290 0 : log_debug ("R_{b+1,b+2} = %s\n", hexstr (&plaintext[blocksize]));
291 : }
292 :
293 88750 : if (cfbp || debug)
294 : {
295 : int i;
296 1 : cfb = xmalloc (len);
297 64 : for (i = 0; i < len; i ++)
298 63 : cfb[i] = plaintext[i] ^ ciphertext[i];
299 :
300 1 : log_assert (len >= blocksize + 2);
301 :
302 1 : if (debug)
303 : {
304 0 : log_debug ("cfb:\n");
305 0 : log_hexdump (cfb, len);
306 :
307 0 : log_debug ("E_k([C_1]_{1,2}) = C_2 xor R (%s xor %s) = %s\n",
308 : hexstr (&ciphertext[blocksize]),
309 : hexstr (&plaintext[blocksize]),
310 0 : hexstr (bufxor2 (&ciphertext[blocksize],
311 : &plaintext[blocksize])));
312 0 : if (len >= blocksize + 4)
313 0 : log_debug ("D = Ek([C1]_{3-b} || C_2)_{1-2} (%s) xor C2 (%s) xor E_k(0)_{b-1,b} (%s) = %s\n",
314 0 : hexstr (&cfb[blocksize + 2]),
315 : hexstr (&ciphertext[blocksize]),
316 0 : hexstr (&cfb[blocksize - 2]),
317 0 : hexstr (bufxor2 (bufxor2 (&cfb[blocksize + 2],
318 : &ciphertext[blocksize]),
319 0 : &cfb[blocksize - 2])));
320 : }
321 : }
322 :
323 88750 : if (plaintext[nprefix-2] != plaintext[nprefix]
324 430 : || plaintext[nprefix-1] != plaintext[nprefix+1])
325 : {
326 88746 : rc = gpg_error (GPG_ERR_BAD_KEY);
327 88746 : goto leave;
328 : }
329 :
330 : leave:
331 88750 : if (! rc && plaintextp)
332 1 : *plaintextp = plaintext;
333 : else
334 88749 : xfree (plaintext);
335 :
336 88750 : if (! rc && cfbp)
337 1 : *cfbp = cfb;
338 : else
339 88749 : xfree (cfb);
340 :
341 88750 : if (cipher_hd)
342 88750 : gcry_cipher_close (cipher_hd);
343 88750 : return rc;
344 : }
345 :
346 : /* Query the oracle with D=D for block B. */
347 : static int
348 88749 : oracle_test (unsigned int d, int b, int debug)
349 : {
350 88749 : byte probe[blocksize + 2];
351 :
352 88749 : log_assert (d < 256 * 256);
353 :
354 88749 : if (b == 1)
355 23664 : memcpy (probe, &msg[2], blocksize);
356 : else
357 65085 : memcpy (probe, block (msg, msg_len, b), blocksize);
358 :
359 88749 : probe[blocksize] = d >> 8;
360 88749 : probe[blocksize + 1] = d & 0xff;
361 :
362 88749 : if (debug)
363 0 : log_debug ("oracle (0x%04X):\n", d);
364 :
365 88749 : return oracle (debug, probe, blocksize + 2, NULL, NULL) == 0;
366 : }
367 :
368 : int
369 1 : main (int argc, char *argv[])
370 : {
371 : int i;
372 1 : int debug = 0;
373 1 : char *filename = NULL;
374 1 : int help = 0;
375 :
376 : byte *raw_data;
377 : int raw_data_len;
378 :
379 1 : int failed = 0;
380 :
381 1 : for (i = 1; i < argc; i ++)
382 : {
383 0 : if (strcmp (argv[i], "--debug") == 0)
384 0 : debug = 1;
385 0 : else if (! blocksize)
386 0 : parse_session_key (argv[i]);
387 0 : else if (! filename)
388 0 : filename = argv[i];
389 : else
390 : {
391 0 : help = 1;
392 0 : break;
393 : }
394 : }
395 :
396 1 : if (! blocksize && ! filename && (filename = getenv ("srcdir")))
397 : /* Try defaults. */
398 : {
399 1 : parse_session_key ("9:9274A8EC128E850C6DDDF9EAC68BFA84FC7BC05F340DA41D78C93D0640C7C503");
400 1 : filename = xasprintf ("%s/t-stutter-data.asc", filename);
401 : }
402 :
403 1 : if (help || ! blocksize || ! filename)
404 0 : log_fatal ("Usage: %s [--debug] SESSION_KEY ENCRYPTED_PKT\n", argv[0]);
405 :
406 : /* Don't read more than a KB. */
407 1 : raw_data_len = 1024;
408 1 : raw_data = xmalloc (raw_data_len);
409 :
410 : {
411 : FILE *fp;
412 : int r;
413 :
414 1 : fp = fopen (filename, "r");
415 1 : if (! fp)
416 0 : log_fatal ("Opening %s: %s\n", filename, strerror (errno));
417 1 : r = fread (raw_data, 1, raw_data_len, fp);
418 1 : fclose (fp);
419 :
420 : /* We need at least the random data, the encrypted and literal
421 : packets' headers and some body. */
422 2 : if (r < (blocksize + 2 /* Random data. */
423 1 : + 2 * blocksize /* Header + some plaintext. */))
424 0 : log_fatal ("Not enough data (need at least %d bytes of plain text): %s.\n",
425 0 : blocksize + 2, strerror (errno));
426 1 : raw_data_len = r;
427 :
428 1 : if (debug)
429 : {
430 0 : log_debug ("First few bytes of the raw data:\n");
431 0 : log_hexdump (raw_data, raw_data_len > 8 ? 8 : raw_data_len);
432 : }
433 : }
434 :
435 : /* Parse the packet's header. */
436 : {
437 1 : int ctb = raw_data[0];
438 1 : int new_format = ctb & (1 << 7);
439 1 : int pkttype = (ctb & ((1 << 5) - 1)) >> (new_format ? 0 : 2);
440 : int hdrlen;
441 :
442 1 : if (new_format)
443 : {
444 1 : if (debug)
445 0 : log_debug ("len encoded: 0x%x (%d)\n", raw_data[1], raw_data[1]);
446 1 : if (raw_data[1] < 192)
447 1 : hdrlen = 2;
448 0 : else if (raw_data[1] < 224)
449 0 : hdrlen = 3;
450 0 : else if (raw_data[1] == 255)
451 0 : hdrlen = 5;
452 : else
453 0 : hdrlen = 2;
454 : }
455 : else
456 : {
457 0 : int lentype = ctb & 0x3;
458 0 : if (lentype == 0)
459 0 : hdrlen = 2;
460 0 : else if (lentype == 1)
461 0 : hdrlen = 3;
462 0 : else if (lentype == 2)
463 0 : hdrlen = 5;
464 : else
465 : /* Indeterminate. */
466 0 : hdrlen = 1;
467 : }
468 :
469 1 : if (debug)
470 0 : log_debug ("ctb = %x; %s format, hdrlen: %d, packet: %s\n",
471 : ctb, new_format ? "new" : "old",
472 : hdrlen,
473 : pkttype_str (pkttype));
474 :
475 1 : if (! (pkttype == PKT_ENCRYPTED || pkttype == PKT_ENCRYPTED_MDC))
476 0 : log_fatal ("%s does not contain an encrypted packet, but a %s.\n",
477 : filename, pkttype_str (pkttype));
478 :
479 1 : if (pkttype == PKT_ENCRYPTED_MDC)
480 : {
481 : /* The first byte following the header is the version, which
482 : is 1. */
483 0 : log_assert (raw_data[hdrlen] == 1);
484 0 : hdrlen ++;
485 0 : sync = 0;
486 : }
487 : else
488 1 : sync = 1;
489 :
490 1 : msg = &raw_data[hdrlen];
491 1 : msg_len = raw_data_len - hdrlen;
492 : }
493 :
494 1 : log_assert (msg_len >= blocksize + 2);
495 :
496 : {
497 : /* This can at least partially be guessed. So we just assume that
498 : it is known. */
499 : int d;
500 : int found;
501 : const byte *m1;
502 : byte e_k_zero[2];
503 :
504 1 : if (oracle (debug, msg, msg_len, &msg_plaintext, &msg_cfb) == 0)
505 : {
506 1 : if (debug)
507 0 : log_debug ("Session key appears to be good.\n");
508 : }
509 : else
510 0 : log_fatal ("Session key is bad!\n");
511 :
512 1 : m1 = &msg_plaintext[blocksize + 2];
513 1 : if (debug)
514 0 : log_debug ("First two bytes of plaintext are: %02X (%c) %02X (%c)\n",
515 0 : m1[0], isprint (m1[0]) ? m1[0] : '?',
516 0 : m1[1], isprint (m1[1]) ? m1[1] : '?');
517 :
518 23664 : for (d = 0; d < 256 * 256; d ++)
519 23664 : if ((found = oracle_test (d, 1, 0)))
520 1 : break;
521 :
522 1 : if (! found)
523 0 : log_fatal ("Failed to find d!\n");
524 :
525 1 : if (debug)
526 0 : oracle_test (d, 1, 1);
527 :
528 1 : if (debug)
529 0 : log_debug ("D = %d (%x) looks good.\n", d, d);
530 :
531 : {
532 1 : byte *c2 = block (msg, msg_len, 2);
533 1 : byte D[2] = { d >> 8, d & 0xFF };
534 1 : byte *c3 = block (msg, msg_len, 3);
535 :
536 1 : memcpy (e_k_zero,
537 1 : bufxor2 (bufxor2 (c2, D),
538 1 : bufxor2 (c3, m1)),
539 : sizeof (e_k_zero));
540 :
541 1 : if (debug)
542 : {
543 0 : log_debug ("C2 = %s\n", hexstr (c2));
544 0 : log_debug ("D = %s\n", hexstr (D));
545 0 : log_debug ("C3 = %s\n", hexstr (c3));
546 0 : log_debug ("M = %s\n", hexstr (m1));
547 0 : log_debug ("E_k([C1]_{3-b} || C_2) = C3 xor M1 = %s\n",
548 0 : hexstr (bufxor2 (c3, m1)));
549 0 : log_debug ("E_k(0)_{b-1,b} = %s\n", hexstr (e_k_zero));
550 : }
551 : }
552 :
553 : /* Figure out the first 2 bytes of M2... (offset 16 & 17 of the
554 : plain text assuming the blocksize == 16 or bytes 34 & 35 of the
555 : decrypted cipher text, i.e., C4). */
556 3 : for (i = 1; block_offset (i + 3) + 2 <= msg_len; i ++)
557 : {
558 : byte e_k_prime[2];
559 : byte m[2];
560 2 : byte *ct = block (msg, msg_len, i + 2);
561 2 : byte *pt = block (msg_plaintext, msg_len, 2 + i + 1);
562 :
563 65085 : for (d = 0; d < 256 * 256; d ++)
564 65085 : if (oracle_test (d, i + 2, 0))
565 : {
566 2 : found = 1;
567 2 : break;
568 : }
569 :
570 2 : if (! found)
571 0 : log_fatal ("Failed to find a valid d for block %d\n", i);
572 :
573 2 : if (debug)
574 0 : log_debug ("Block %d: oracle: D = %04X passes integrity check\n",
575 : i, d);
576 :
577 : {
578 2 : byte D[2] = { d >> 8, d & 0xFF };
579 2 : memcpy (e_k_prime,
580 2 : bufxor2 (bufxor2 (&ct[blocksize - 2], D), e_k_zero),
581 : sizeof (e_k_prime));
582 :
583 2 : memcpy (m, bufxor2 (e_k_prime, block (msg, msg_len, i + 3)),
584 : sizeof (m));
585 : }
586 :
587 2 : if (debug)
588 0 : log_debug ("=> block %d starting at %zd starts with: "
589 : "%s (%c%c)\n",
590 0 : i, (size_t) pt - (size_t) msg_plaintext,
591 : hexstr (m),
592 0 : isprint (m[0]) ? m[0] : '?', isprint (m[1]) ? m[1] : '?');
593 :
594 2 : if (m[0] != pt[0] || m[1] != pt[1])
595 : {
596 0 : log_debug ("oracle attack failed! Expected %s (%c%c), got %s\n",
597 : hexstr (pt),
598 0 : isprint (pt[0]) ? pt[0] : '?',
599 0 : isprint (pt[1]) ? pt[1] : '?',
600 : hexstr (m));
601 0 : failed = 1;
602 : }
603 : }
604 :
605 1 : if (i == 1)
606 0 : log_fatal ("Message is too short, nothing to test.\n");
607 : }
608 :
609 1 : xfree (filename);
610 1 : return failed;
611 : }
|
