1 /* t-stutter.c - Test the stutter exploit.
2 * Copyright (C) 2016 g10 Code GmbH
4 * This file is part of GnuPG.
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.
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.
16 * You should have received a copy of the GNU General Public License
17 * along with this program; if not, see <https://www.gnu.org/licenses/>.
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.
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.
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.
38 * How to generate a test message:
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
46 * $ gpg --show-session-key -d msg.asc
47 * $ ./t-stutter --debug SESSION_KEY 000002-009.encrypted
56 #include "../common/types.h"
59 #include "../common/logging.h"
62 log_hexdump (byte *buffer, int length)
66 fprintf (stderr, "%d bytes:\n", length);
69 int have = length > 16 ? 16 : length;
71 char formatted[2 * 16 + 1];
74 fprintf (stderr, "%-8d ", written);
75 bin2hex (buffer, have, formatted);
76 for (i = 0; i < 16; i ++)
84 fwrite (&formatted[2 * i], 2, 1, stderr);
86 fwrite (" ", 2, 1, stderr);
89 for (i = 0; i < have; i ++)
91 if (isprint (buffer[i]))
98 fprintf (stderr, " ");
99 if (strlen (text) > 8)
101 fwrite (text, 8, 1, stderr);
103 fwrite (&text[8], strlen (text) - 8, 1, stderr);
106 fwrite (text, strlen (text), 1, stderr);
107 fputc ('\n', stderr);
118 hexstr (const byte *bytes)
121 static char bufs[100][7];
127 sprintf (bufs[i], "0x%02X%02X", bytes[0], bytes[1]);
131 /* xor the two bytes starting at A with the two bytes starting at B
132 and return the result. */
134 bufxor2 (const byte *a, const byte *b)
137 static char bufs[100][2];
143 bufs[i][0] = a[0] ^ b[0];
144 bufs[i][1] = a[1] ^ b[1];
148 /* The session key stays constant. */
152 /* Decode the session key, which is in the format output by gpg
153 --show-session-key. */
155 parse_session_key (char *session_key)
158 char *p = session_key;
161 dek.algo = strtol (p, &tail, 10);
162 if (errno || (tail && *tail != ':'))
163 log_fatal ("Invalid session key specification. "
164 "Expected: cipher-id:HEXADECIMAL-CHRACTERS\n");
169 if (strlen (p) % 2 != 0)
170 log_fatal ("Session key must consist of an even number of hexadecimal characters.\n");
172 dek.keylen = strlen (p) / 2;
173 log_assert (dek.keylen <= sizeof (dek.key));
175 if (hex2bin (p, dek.key, dek.keylen) == -1)
176 log_fatal ("Session key must only contain hexadecimal characters\n");
178 blocksize = openpgp_cipher_get_algo_blklen (dek.algo);
179 if ( !blocksize || blocksize > 16 )
180 log_fatal ("unsupported blocksize %u\n", blocksize );
185 /* The ciphertext, the plaintext as decrypted by the good session key,
186 and the cfb stream (derived from the ciphertext and the
190 static byte *msg_plaintext;
191 static byte *msg_cfb;
193 /* Whether we need to resynchronize the CFB after writing the random
194 data (this is the case for encrypted packets, but not encrypted and
195 integrity protected packets). */
204 /* Make sure blocksize has been initialized. */
205 log_assert (blocksize);
210 extra = blocksize + 2;
212 return (i - 1) * blocksize + extra;
215 /* Return the ith block from TEXT. The first block is labeled 1.
216 Note: consistent with the OpenPGP message format, the second block
217 (i=2) is just 2 bytes. */
219 block (byte *text, int len, int i)
221 int offset = block_offset (i);
223 log_assert (offset < len);
224 return &text[offset];
227 /* Return true if the quick integrity check passes. Also, if
228 PLAINTEXTP is not NULL, return the decrypted plaintext in
229 *PLAINTEXTP. If CFBP is not NULL, return the CFB byte stream in
232 oracle (int debug, byte *ciphertext, int len, byte **plaintextp, byte **cfbp)
236 gcry_cipher_hd_t cipher_hd = NULL;
237 byte *plaintext = NULL;
240 /* Make sure DEK was initialized. */
241 log_assert (dek.algo);
242 log_assert (dek.keylen);
243 log_assert (blocksize);
246 if (len < nprefix + 2)
248 /* An invalid message. We can't check that during parsing
249 because we may not know the used cipher then. */
250 rc = gpg_error (GPG_ERR_INV_PACKET);
254 rc = openpgp_cipher_open (&cipher_hd, dek.algo,
255 GCRY_CIPHER_MODE_CFB,
256 (! sync /* ed->mdc_method || dek.algo >= 100 */ ?
257 0 : GCRY_CIPHER_ENABLE_SYNC));
259 log_fatal ("Failed to open cipher: %s\n", gpg_strerror (rc));
261 rc = gcry_cipher_setkey (cipher_hd, dek.key, dek.keylen);
262 if (gpg_err_code (rc) == GPG_ERR_WEAK_KEY)
264 log_info ("WARNING: message was encrypted with"
265 " a weak key in the symmetric cipher.\n");
269 log_fatal ("key setup failed: %s\n", gpg_strerror (rc));
271 gcry_cipher_setiv (cipher_hd, NULL, 0);
275 log_debug ("Encrypted data:\n");
276 log_hexdump(ciphertext, len);
278 plaintext = xmalloc_clear (len);
279 gcry_cipher_decrypt (cipher_hd, plaintext, blocksize + 2,
280 ciphertext, blocksize + 2);
281 gcry_cipher_sync (cipher_hd);
282 if (len > blocksize+2)
283 gcry_cipher_decrypt (cipher_hd,
284 &plaintext[blocksize+2], len-(blocksize+2),
285 &ciphertext[blocksize+2], len-(blocksize+2));
289 log_debug ("Decrypted data:\n");
290 log_hexdump (plaintext, len);
291 log_debug ("R_{b-1,b} = %s\n", hexstr (&plaintext[blocksize - 2]));
292 log_debug ("R_{b+1,b+2} = %s\n", hexstr (&plaintext[blocksize]));
299 for (i = 0; i < len; i ++)
300 cfb[i] = plaintext[i] ^ ciphertext[i];
302 log_assert (len >= blocksize + 2);
306 log_debug ("cfb:\n");
307 log_hexdump (cfb, len);
309 log_debug ("E_k([C_1]_{1,2}) = C_2 xor R (%s xor %s) = %s\n",
310 hexstr (&ciphertext[blocksize]),
311 hexstr (&plaintext[blocksize]),
312 hexstr (bufxor2 (&ciphertext[blocksize],
313 &plaintext[blocksize])));
314 if (len >= blocksize + 4)
315 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",
316 hexstr (&cfb[blocksize + 2]),
317 hexstr (&ciphertext[blocksize]),
318 hexstr (&cfb[blocksize - 2]),
319 hexstr (bufxor2 (bufxor2 (&cfb[blocksize + 2],
320 &ciphertext[blocksize]),
321 &cfb[blocksize - 2])));
325 if (plaintext[nprefix-2] != plaintext[nprefix]
326 || plaintext[nprefix-1] != plaintext[nprefix+1])
328 rc = gpg_error (GPG_ERR_BAD_KEY);
333 if (! rc && plaintextp)
334 *plaintextp = plaintext;
344 gcry_cipher_close (cipher_hd);
348 /* Query the oracle with D=D for block B. */
350 oracle_test (unsigned int d, int b, int debug)
354 log_assert (blocksize + 2 <= sizeof probe);
355 log_assert (d < 256 * 256);
358 memcpy (probe, &msg[2], blocksize);
360 memcpy (probe, block (msg, msg_len, b), blocksize);
362 probe[blocksize] = d >> 8;
363 probe[blocksize + 1] = d & 0xff;
366 log_debug ("oracle (0x%04X):\n", d);
368 return oracle (debug, probe, blocksize + 2, NULL, NULL) == 0;
372 main (int argc, char *argv[])
376 char *filename = NULL;
384 for (i = 1; i < argc; i ++)
386 if (strcmp (argv[i], "--debug") == 0)
388 else if (! blocksize)
389 parse_session_key (argv[i]);
399 if (! blocksize && ! filename && (filename = getenv ("srcdir")))
402 parse_session_key ("9:9274A8EC128E850C6DDDF9EAC68BFA84FC7BC05F340DA41D78C93D0640C7C503");
403 filename = xasprintf ("%s/t-stutter-data.asc", filename);
406 if (help || ! blocksize || ! filename)
407 log_fatal ("Usage: %s [--debug] SESSION_KEY ENCRYPTED_PKT\n", argv[0]);
409 /* Don't read more than a KB. */
411 raw_data = xmalloc (raw_data_len);
417 fp = fopen (filename, "r");
419 log_fatal ("Opening %s: %s\n", filename, strerror (errno));
420 r = fread (raw_data, 1, raw_data_len, fp);
423 /* We need at least the random data, the encrypted and literal
424 packets' headers and some body. */
425 if (r < (blocksize + 2 /* Random data. */
426 + 2 * blocksize /* Header + some plaintext. */))
427 log_fatal ("Not enough data (need at least %d bytes of plain text): %s.\n",
428 blocksize + 2, strerror (errno));
433 log_debug ("First few bytes of the raw data:\n");
434 log_hexdump (raw_data, raw_data_len > 8 ? 8 : raw_data_len);
438 /* Parse the packet's header. */
440 int ctb = raw_data[0];
441 int new_format = ctb & (1 << 7);
442 int pkttype = (ctb & ((1 << 5) - 1)) >> (new_format ? 0 : 2);
448 log_debug ("len encoded: 0x%x (%d)\n", raw_data[1], raw_data[1]);
449 if (raw_data[1] < 192)
451 else if (raw_data[1] < 224)
453 else if (raw_data[1] == 255)
460 int lentype = ctb & 0x3;
463 else if (lentype == 1)
465 else if (lentype == 2)
473 log_debug ("ctb = %x; %s format, hdrlen: %d, packet: %s\n",
474 ctb, new_format ? "new" : "old",
476 pkttype_str (pkttype));
478 if (! (pkttype == PKT_ENCRYPTED || pkttype == PKT_ENCRYPTED_MDC))
479 log_fatal ("%s does not contain an encrypted packet, but a %s.\n",
480 filename, pkttype_str (pkttype));
482 if (pkttype == PKT_ENCRYPTED_MDC)
484 /* The first byte following the header is the version, which
486 log_assert (raw_data[hdrlen] == 1);
493 msg = &raw_data[hdrlen];
494 msg_len = raw_data_len - hdrlen;
497 log_assert (msg_len >= blocksize + 2);
500 /* This can at least partially be guessed. So we just assume that
507 if (oracle (debug, msg, msg_len, &msg_plaintext, &msg_cfb) == 0)
510 log_debug ("Session key appears to be good.\n");
513 log_fatal ("Session key is bad!\n");
515 m1 = &msg_plaintext[blocksize + 2];
517 log_debug ("First two bytes of plaintext are: %02X (%c) %02X (%c)\n",
518 m1[0], isprint (m1[0]) ? m1[0] : '?',
519 m1[1], isprint (m1[1]) ? m1[1] : '?');
521 for (d = 0; d < 256 * 256; d ++)
522 if ((found = oracle_test (d, 1, 0)))
526 log_fatal ("Failed to find d!\n");
529 oracle_test (d, 1, 1);
532 log_debug ("D = %d (%x) looks good.\n", d, d);
535 byte *c2 = block (msg, msg_len, 2);
536 byte D[2] = { d >> 8, d & 0xFF };
537 byte *c3 = block (msg, msg_len, 3);
540 bufxor2 (bufxor2 (c2, D),
546 log_debug ("C2 = %s\n", hexstr (c2));
547 log_debug ("D = %s\n", hexstr (D));
548 log_debug ("C3 = %s\n", hexstr (c3));
549 log_debug ("M = %s\n", hexstr (m1));
550 log_debug ("E_k([C1]_{3-b} || C_2) = C3 xor M1 = %s\n",
551 hexstr (bufxor2 (c3, m1)));
552 log_debug ("E_k(0)_{b-1,b} = %s\n", hexstr (e_k_zero));
556 /* Figure out the first 2 bytes of M2... (offset 16 & 17 of the
557 plain text assuming the blocksize == 16 or bytes 34 & 35 of the
558 decrypted cipher text, i.e., C4). */
559 for (i = 1; block_offset (i + 3) + 2 <= msg_len; i ++)
563 byte *ct = block (msg, msg_len, i + 2);
564 byte *pt = block (msg_plaintext, msg_len, 2 + i + 1);
566 for (d = 0; d < 256 * 256; d ++)
567 if (oracle_test (d, i + 2, 0))
574 log_fatal ("Failed to find a valid d for block %d\n", i);
577 log_debug ("Block %d: oracle: D = %04X passes integrity check\n",
581 byte D[2] = { d >> 8, d & 0xFF };
583 bufxor2 (bufxor2 (&ct[blocksize - 2], D), e_k_zero),
586 memcpy (m, bufxor2 (e_k_prime, block (msg, msg_len, i + 3)),
591 log_debug ("=> block %d starting at %zd starts with: "
593 i, (size_t) pt - (size_t) msg_plaintext,
595 isprint (m[0]) ? m[0] : '?', isprint (m[1]) ? m[1] : '?');
597 if (m[0] != pt[0] || m[1] != pt[1])
599 log_debug ("oracle attack failed! Expected %s (%c%c), got %s\n",
601 isprint (pt[0]) ? pt[0] : '?',
602 isprint (pt[1]) ? pt[1] : '?',
609 log_fatal ("Message is too short, nothing to test.\n");