chiark - git - mdw - become/blob - src/blowfish.c

   1 /* -*-c-*-
   2  *
   3  * $Id: blowfish.c,v 1.5 1998/01/12 16:43:48 mdw Exp $
   4  *
   5  * Blowfish encryption routines
   6  *
   7  * (c) 1998 Mark Wooding
   8  */
   9
  10 /*----- Licencing notice --------------------------------------------------*
  11  *
  12  * This file is part of `become'
  13  *
  14  * `Become' is free software; you can redistribute it and/or modify
  15  * it under the terms of the GNU General Public License as published by
  16  * the Free Software Foundation; either version 2 of the License, or
  17  * (at your option) any later version.
  18  *
  19  * `Become' is distributed in the hope that it will be useful,
  20  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  21  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  22  * GNU General Public License for more details.
  23  *
  24  * You should have received a copy of the GNU General Public License
  25  * along with `become'; if not, write to the Free Software Foundation,
  26  * Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
  27  */
  28
  29 /*----- Revision history --------------------------------------------------*
  30  *
  31  * $Log: blowfish.c,v $
  32  * Revision 1.5  1998/01/12 16:43:48  mdw
  33  * Include required header files.  Fix copyright date.
  34  *
  35  * Revision 1.4  1997/12/08 15:29:50  mdw
  36  * Formatting fixes.  Very boring.
  37  *
  38  * Revision 1.3  1997/08/07 09:42:58  mdw
  39  * Fix address of the FSF.
  40  *
  41  * Revision 1.2  1997/08/04 10:24:20  mdw
  42  * Sources placed under CVS control.
  43  *
  44  * Revision 1.1  1997/07/21  13:47:53  mdw
  45  * Initial revision
  46  *
  47  */
  48
  49 /*----- Header files ------------------------------------------------------*/
  50
  51 /* --- ANSI headers --- */
  52
  53 #include <stdio.h>
  54 #include <stdlib.h>
  55 #include <string.h>
  56
  57 /* --- Local headers --- */
  58
  59 #include "config.h"
  60 #include "blowfish.h"
  61 #include "utils.h"
  62
  63 /*----- Define the initial S-box values -----------------------------------*/
  64
  65 #include "blowfish-sbox.h"
  66
  67 /*----- Useful macros -----------------------------------------------------*/
  68
  69 /* --- The Blowfish round function --- *
  70  *
  71  * This is why I like this cipher.  The round function is microscopic.  And
  72  * very fast.
  73  */
  74
  75 #define ROUND(L, R, K)                                                  \
  76   ((L) ^= k->p[K],                                                      \
  77    (R) ^= ((((k->s0[((L) >> 24) & 0xFF]) +                              \
  78               k->s1[((L) >> 16) & 0xFF]) ^                              \
  79               k->s2[((L) >>  8) & 0xFF]) +                              \
  80               k->s3[((L) >>  0) & 0xFF]))
  81
  82 /*----- Main code ---------------------------------------------------------*/
  83
  84 /* --- @blowfish_encrypt@ --- *
  85  *
  86  * Arguments:   @const blowfish_key *k@ = pointer to key block
  87  *              @const void *from@ = block to encrypt from
  88  *              @void *to@ = block to encrypt to
  89  *
  90  * Returns:     ---
  91  *
  92  * Use:         Encrypts a block using the Blowfish algorithm.
  93  */
  94
  95 void blowfish_encrypt(const blowfish_key *k, const void *from, void *to)
  96 {
  97   uint_32 l, r;
  98   const unsigned char *f = from;
  99   unsigned char *t = to;
 100
 101   /* --- Extract left and right block halves --- */
 102
 103   l = load32(f + 0);
 104   r = load32(f + 4);
 105
 106   /* --- Now run the round function on these values --- */
 107
 108   ROUND(l, r,  0);
 109   ROUND(r, l,  1);
 110   ROUND(l, r,  2);
 111   ROUND(r, l,  3);
 112   ROUND(l, r,  4);
 113   ROUND(r, l,  5);
 114   ROUND(l, r,  6);
 115   ROUND(r, l,  7);
 116   ROUND(l, r,  8);
 117   ROUND(r, l,  9);
 118   ROUND(l, r, 10);
 119   ROUND(r, l, 11);
 120   ROUND(l, r, 12);
 121   ROUND(r, l, 13);
 122   ROUND(l, r, 14);
 123   ROUND(r, l, 15);
 124
 125   /* --- Final transformation --- */
 126
 127   l ^= k->p[16];
 128   r ^= k->p[17];
 129
 130   /* --- Store the encrypted value --- */
 131
 132   store32(t + 0, r);
 133   store32(t + 4, l);
 134 }
 135
 136 /* --- @blowfish_decrypt@ --- *
 137  *
 138  * Arguments:   @const blowfish_key *k@ = pointer to key block
 139  *              @const void *from@ = block to decrypt from
 140  *              @void *to@ = block to decrypt to
 141  *
 142  * Returns:     ---
 143  *
 144  * Use:         Decrypts a block using the Blowfish algorithm.
 145  */
 146
 147 void blowfish_decrypt(const blowfish_key *k, const void *from, void *to)
 148 {
 149   uint_32 l, r;
 150   const unsigned char *f = from;
 151   unsigned char *t = to;
 152
 153   /* --- Extract left and right block halves --- */
 154
 155   l = load32(f + 0);
 156   r = load32(f + 4);
 157
 158   /* --- Now run the round function on these values --- */
 159
 160   ROUND(l, r, 17);
 161   ROUND(r, l, 16);
 162   ROUND(l, r, 15);
 163   ROUND(r, l, 14);
 164   ROUND(l, r, 13);
 165   ROUND(r, l, 12);
 166   ROUND(l, r, 11);
 167   ROUND(r, l, 10);
 168   ROUND(l, r,  9);
 169   ROUND(r, l,  8);
 170   ROUND(l, r,  7);
 171   ROUND(r, l,  6);
 172   ROUND(l, r,  5);
 173   ROUND(r, l,  4);
 174   ROUND(l, r,  3);
 175   ROUND(r, l,  2);
 176
 177   /* --- Final transformation --- */
 178
 179   l ^= k->p[1];
 180   r ^= k->p[0];
 181
 182   /* --- Store the decrypted value --- */
 183
 184   store32(t + 0, r);
 185   store32(t + 4, l);
 186 }
 187
 188 /* --- @blowfish__qcrypt@ --- *
 189  *
 190  * Arguments:   @const blowfish_key *k@ = pointer to a key block
 191  *              @uint_32 *p@ = pointer to block to mangle
 192  *
 193  * Returns:     ---
 194  *
 195  * Use:         Mangles a block using the Blowfish algorithm.
 196  */
 197
 198 static void blowfish__qcrypt(blowfish_key *k, uint_32 *p)
 199 {
 200   uint_32 l = p[0], r = p[1];
 201
 202   /* --- Run the round function --- */
 203
 204   ROUND(l, r,  0);
 205   ROUND(r, l,  1);
 206   ROUND(l, r,  2);
 207   ROUND(r, l,  3);
 208   ROUND(l, r,  4);
 209   ROUND(r, l,  5);
 210   ROUND(l, r,  6);
 211   ROUND(r, l,  7);
 212   ROUND(l, r,  8);
 213   ROUND(r, l,  9);
 214   ROUND(l, r, 10);
 215   ROUND(r, l, 11);
 216   ROUND(l, r, 12);
 217   ROUND(r, l, 13);
 218   ROUND(l, r, 14);
 219   ROUND(r, l, 15);
 220
 221   /* --- Output transformation --- */
 222
 223   l ^= k->p[16];
 224   r ^= k->p[17];
 225
 226   /* --- Store the new values --- */
 227
 228   p[0] = r;
 229   p[1] = l;
 230 }
 231
 232 /* --- @blowfish__buildKey@ --- *
 233  *
 234  * Arguments:   @blowfish_key *k@ = pointer to a key block to set up
 235  *
 236  * Returns:     ---
 237  *
 238  * Use:         Sets up the P-array and S-boxes once a key has been mixed
 239  *              into the P-array.  Use a local copy of the Blowfish
 240  *              encryption routine, to avoid penalising the main code too
 241  *              much with having to veneer onto a general args-in-words
 242  *              function, and to avoid me messing about with transforming
 243  *              values backwards and forwards between char arrays and
 244  *              integers.
 245  */
 246
 247 static void blowfish__buildKey(blowfish_key *k)
 248 {
 249   uint_32 b[2] = { 0, 0 };
 250   int i;
 251
 252   /* --- First, run through the P-array --- */
 253
 254   for (i = 0; i < 18; i += 2) {
 255     blowfish__qcrypt(k, b);
 256     k->p[i] = b[0];
 257     k->p[i + 1] = b[1];
 258   }
 259
 260   /* --- Now do the S-boxes --- */
 261
 262   for (i = 0; i < 256; i += 2) {
 263     blowfish__qcrypt(k, b);
 264     k->s0[i] = b[0];
 265     k->s0[i + 1] = b[1];
 266   }
 267
 268   for (i = 0; i < 256; i += 2) {
 269     blowfish__qcrypt(k, b);
 270     k->s1[i] = b[0];
 271     k->s1[i + 1] = b[1];
 272   }
 273
 274   for (i = 0; i < 256; i += 2) {
 275     blowfish__qcrypt(k, b);
 276     k->s2[i] = b[0];
 277     k->s2[i + 1] = b[1];
 278   }
 279
 280   for (i = 0; i < 256; i += 2) {
 281     blowfish__qcrypt(k, b);
 282     k->s3[i] = b[0];
 283     k->s3[i + 1] = b[1];
 284   }
 285 }
 286
 287 /* --- @blowfish_setKey@ --- *
 288  *
 289  * Arguments:   @blowfish_key *kb@ = pointer to key block to fill
 290  *              @void *k@ = pointer to key data
 291  *              @size_t sz@ = length of data in bytes
 292  *
 293  * Returns:     ---
 294  *
 295  * Use:         Expands a key which isn't represented as a number of whole
 296  *              words.  This is a nonstandard extension, although it can be
 297  *              used to support 40-bit keys, which some governments might
 298  *              find more palatable than 160-bit (or 448-bit!) keys.
 299  */
 300
 301 void blowfish_setKey(blowfish_key *kb, const void *k, size_t sz)
 302 {
 303   int i, j, l;
 304   const unsigned char *p = k;
 305   uint_32 a;
 306
 307   memcpy(kb, &blowfish__init, sizeof(blowfish__init));
 308
 309   j = 0;
 310   for (i = 0; i < 18; i++) {
 311     a = 0;
 312     for (l = 0; l < 4; l++) {
 313       a = (a << 8) | p[j];
 314       j++;
 315       if (j >= sz)
 316         j = 0;
 317     }
 318     kb->p[i] ^= a;
 319   }
 320
 321   blowfish__buildKey(kb);
 322 }
 323
 324 /*----- Test rig ----------------------------------------------------------*/
 325
 326 #ifdef TEST_RIG
 327
 328 int main(void)
 329 {
 330   /* --- Stage one: ECB tests --- */
 331
 332   {
 333     static struct {
 334       uint_32 k[2];
 335       uint_32 p[2];
 336       uint_32 c[2];
 337     } table[] = {
 338       { { 0x00000000u, 0x00000000u },
 339         { 0x00000000u, 0x00000000u },
 340         { 0x4EF99745u, 0x6198DD78u } },
 341
 342       { { 0xFFFFFFFFu, 0xFFFFFFFFu },
 343         { 0xFFFFFFFFu, 0xFFFFFFFFu },
 344         { 0x51866FD5u, 0xB85ECB8Au } },
 345
 346       { { 0x30000000u, 0x00000000u },
 347         { 0x10000000u, 0x00000001u },
 348         { 0x7D856F9Au, 0x613063F2u } },
 349
 350       { { 0x11111111u, 0x11111111u },
 351         { 0x11111111u, 0x11111111u },
 352         { 0x2466DD87u, 0x8B963C9Du } },
 353
 354       { { 0x01234567u, 0x89ABCDEFu },
 355         { 0x11111111u, 0x11111111u },
 356         { 0x61F9C380u, 0x2281B096u } },
 357
 358       { { 0x11111111u, 0x11111111u },
 359         { 0x01234567u, 0x89ABCDEFu },
 360         { 0x7D0CC630u, 0xAFDA1EC7u } },
 361
 362       { { 0x00000000u, 0x00000000u },
 363         { 0x00000000u, 0x00000000u },
 364         { 0x4EF99745u, 0x6198DD78u } },
 365
 366       { { 0xFEDCBA98u, 0x76543210u },
 367         { 0x01234567u, 0x89ABCDEFu },
 368         { 0x0ACEAB0Fu, 0xC6A0A28Du } },
 369
 370       { { 0x7CA11045u, 0x4A1A6E57u },
 371         { 0x01A1D6D0u, 0x39776742u },
 372         { 0x59C68245u, 0xEB05282Bu } },
 373
 374       { { 0x0131D961u, 0x9DC1376Eu },
 375         { 0x5CD54CA8u, 0x3DEF57DAu },
 376         { 0xB1B8CC0Bu, 0x250F09A0u } },
 377
 378       { { 0x07A1133Eu, 0x4A0B2686u },
 379         { 0x0248D438u, 0x06F67172u },
 380         { 0x1730E577u, 0x8BEA1DA4u } },
 381
 382       { { 0x3849674Cu, 0x2602319Eu },
 383         { 0x51454B58u, 0x2DDF440Au },
 384         { 0xA25E7856u, 0xCF2651EBu } },
 385
 386       { { 0x04B915BAu, 0x43FEB5B6u },
 387         { 0x42FD4430u, 0x59577FA2u },
 388         { 0x353882B1u, 0x09CE8F1Au } },
 389
 390       { { 0x0113B970u, 0xFD34F2CEu },
 391         { 0x059B5E08u, 0x51CF143Au },
 392         { 0x48F4D088u, 0x4C379918u } },
 393
 394       { { 0x0170F175u, 0x468FB5E6u },
 395         { 0x0756D8E0u, 0x774761D2u },
 396         { 0x432193B7u, 0x8951FC98u } },
 397
 398       { { 0x43297FADu, 0x38E373FEu },
 399         { 0x762514B8u, 0x29BF486Au },
 400         { 0x13F04154u, 0xD69D1AE5u } },
 401
 402       { { 0x07A71370u, 0x45DA2A16u },
 403         { 0x3BDD1190u, 0x49372802u },
 404         { 0x2EEDDA93u, 0xFFD39C79u } },
 405
 406       { { 0x04689104u, 0xC2FD3B2Fu },
 407         { 0x26955F68u, 0x35AF609Au },
 408         { 0xD887E039u, 0x3C2DA6E3u } },
 409
 410       { { 0x37D06BB5u, 0x16CB7546u },
 411         { 0x164D5E40u, 0x4F275232u },
 412         { 0x5F99D04Fu, 0x5B163969u } },
 413
 414       { { 0x1F08260Du, 0x1AC2465Eu },
 415         { 0x6B056E18u, 0x759F5CCAu },
 416         { 0x4A057A3Bu, 0x24D3977Bu } },
 417
 418       { { 0x58402364u, 0x1ABA6176u },
 419         { 0x004BD6EFu, 0x09176062u },
 420         { 0x452031C1u, 0xE4FADA8Eu } },
 421
 422       { { 0x02581616u, 0x4629B007u },
 423         { 0x480D3900u, 0x6EE762F2u },
 424         { 0x7555AE39u, 0xF59B87BDu } },
 425
 426       { { 0x49793EBCu, 0x79B3258Fu },
 427         { 0x437540C8u, 0x698F3CFAu },
 428         { 0x53C55F9Cu, 0xB49FC019u } },
 429
 430       { { 0x4FB05E15u, 0x15AB73A7u },
 431         { 0x072D43A0u, 0x77075292u },
 432         { 0x7A8E7BFAu, 0x937E89A3u } },
 433
 434       { { 0x49E95D6Du, 0x4CA229BFu },
 435         { 0x02FE5577u, 0x8117F12Au },
 436         { 0xCF9C5D7Au, 0x4986ADB5u } },
 437
 438       { { 0x018310DCu, 0x409B26D6u },
 439         { 0x1D9D5C50u, 0x18F728C2u },
 440         { 0xD1ABB290u, 0x658BC778u } },
 441
 442       { { 0x1C587F1Cu, 0x13924FEFu },
 443         { 0x30553228u, 0x6D6F295Au },
 444         { 0x55CB3774u, 0xD13EF201u } },
 445
 446       { { 0x01010101u, 0x01010101u },
 447         { 0x01234567u, 0x89ABCDEFu },
 448         { 0xFA34EC48u, 0x47B268B2u } },
 449
 450       { { 0x1F1F1F1Fu, 0x0E0E0E0Eu },
 451         { 0x01234567u, 0x89ABCDEFu },
 452         { 0xA7907951u, 0x08EA3CAEu } },
 453
 454       { { 0xE0FEE0FEu, 0xF1FEF1FEu },
 455         { 0x01234567u, 0x89ABCDEFu },
 456         { 0xC39E072Du, 0x9FAC631Du } },
 457
 458       { { 0x00000000u, 0x00000000u },
 459         { 0xFFFFFFFFu, 0xFFFFFFFFu },
 460         { 0x014933E0u, 0xCDAFF6E4u } },
 461
 462       { { 0xFFFFFFFFu, 0xFFFFFFFFu },
 463         { 0x00000000u, 0x00000000u },
 464         { 0xF21E9A77u, 0xB71C49BCu } },
 465
 466       { { 0x01234567u, 0x89ABCDEFu },
 467         { 0x00000000u, 0x00000000u },
 468         { 0x24594688u, 0x5754369Au } },
 469
 470       { { 0xFEDCBA98u, 0x76543210u },
 471         { 0xFFFFFFFFu, 0xFFFFFFFFu },
 472         { 0x6B5C5A9Cu, 0x5D9E0A5Au } }
 473     };
 474
 475     int f = 1;
 476     int i;
 477
 478     printf("*** stage one: ");
 479     fflush(stdout);
 480
 481     for (i = 0; i < sizeof(table) / sizeof(table[0]); i++) {
 482       char kb[8], p[8], c[8];
 483       blowfish_key k;
 484
 485       store32(kb + 0, table[i].k[0]);
 486       store32(kb + 4, table[i].k[1]);
 487       blowfish_setKey(&k, kb, 8);
 488
 489       store32(p + 0, table[i].p[0]);
 490       store32(p + 4, table[i].p[1]);
 491       blowfish_encrypt(&k, p, c);
 492
 493       if (load32(c + 0) != table[i].c[0] ||
 494           load32(c + 4) != table[i].c[1]) {
 495         printf("\n"
 496                "!!! bad encryption\n"
 497                "                    key = %08lx-%08lx\n"
 498                "              plaintext = %08lx-%08lx\n"
 499                "    expected ciphertext = %08lx-%08lx\n"
 500                "  calculated ciphertext = %08lx-%08lx\n",
 501                (unsigned long)table[i].k[0],
 502                (unsigned long)table[i].k[1],
 503                (unsigned long)table[i].p[0],
 504                (unsigned long)table[i].p[1],
 505                (unsigned long)table[i].c[0],
 506                (unsigned long)table[i].c[1],
 507                (unsigned long)load32(c + 0),
 508                (unsigned long)load32(c + 4));
 509         f = 0;
 510       }
 511
 512       blowfish_decrypt(&k, c, p);
 513       if (load32(p + 0) != table[i].p[0] ||
 514           load32(p + 4) != table[i].p[1]) {
 515         printf("\n"
 516                "!!! bad decryption\n"
 517                "                    key = %08lx-%08lx\n"
 518                "             ciphertext = %08lx-%08lx\n"
 519                "     expected plaintext = %08lx-%08lx\n"
 520                "   calculated plaintext = %08lx-%08lx\n",
 521                (unsigned long)table[i].k[0],
 522                (unsigned long)table[i].k[1],
 523                (unsigned long)table[i].c[0],
 524                (unsigned long)table[i].c[1],
 525                (unsigned long)table[i].p[0],
 526                (unsigned long)table[i].p[1],
 527                (unsigned long)load32(p + 0),
 528                (unsigned long)load32(p + 4));
 529         f = 0;
 530       }
 531
 532       putchar('.');
 533       fflush(stdout);
 534     }
 535     putchar('\n');
 536     if (f)
 537       printf("*** stage one ok\n");
 538   }
 539
 540   /* --- Stage 2: key scheduling --- */
 541
 542   {
 543     static struct {
 544       uint_32 c[2];
 545     } table[] = {
 546       {{ 0xF9AD597Cu, 0x49DB005Eu }},
 547       {{ 0xE91D21C1u, 0xD961A6D6u }},
 548       {{ 0xE9C2B70Au, 0x1BC65CF3u }},
 549       {{ 0xBE1E6394u, 0x08640F05u }},
 550       {{ 0xB39E4448u, 0x1BDB1E6Eu }},
 551       {{ 0x9457AA83u, 0xB1928C0Du }},
 552       {{ 0x8BB77032u, 0xF960629Du }},
 553       {{ 0xE87A244Eu, 0x2CC85E82u }},
 554       {{ 0x15750E7Au, 0x4F4EC577u }},
 555       {{ 0x122BA70Bu, 0x3AB64AE0u }},
 556       {{ 0x3A833C9Au, 0xFFC537F6u }},
 557       {{ 0x9409DA87u, 0xA90F6BF2u }},
 558       {{ 0x884F8062u, 0x5060B8B4u }},
 559       {{ 0x1F85031Cu, 0x19E11968u }},
 560       {{ 0x79D9373Au, 0x714CA34Fu }},
 561       {{ 0x93142887u, 0xEE3BE15Cu }},
 562       {{ 0x03429E83u, 0x8CE2D14Bu }},
 563       {{ 0xA4299E27u, 0x469FF67Bu }},
 564       {{ 0xAFD5AED1u, 0xC1BC96A8u }},
 565       {{ 0x10851C0Eu, 0x3858DA9Fu }},
 566       {{ 0xE6F51ED7u, 0x9B9DB21Fu }},
 567       {{ 0x64A6E14Au, 0xFD36B46Fu }},
 568       {{ 0x80C7D7D4u, 0x5A5479ADu }},
 569       {{ 0x05044B62u, 0xFA52D080u }},
 570     };
 571
 572     unsigned char kk[] = {
 573       0xF0, 0xE1, 0xD2, 0xC3, 0xB4, 0xA5, 0x96, 0x87,
 574       0x78, 0x69, 0x5A, 0x4B, 0x3C, 0x2D, 0x1E, 0x0F,
 575       0x00, 0x11, 0x22, 0x33, 0x44, 0x55, 0x66, 0x77
 576     };
 577
 578     int i;
 579     int f = 1;
 580
 581     printf("*** stage two: ");
 582     fflush(stdout);
 583
 584     for (i = 0; i < sizeof(kk); i++) {
 585       blowfish_key k;
 586       unsigned char p[8] = { 0xFE, 0xDC, 0xBA, 0x98,
 587                              0x76, 0x54, 0x32, 0x10 };
 588
 589       blowfish_setKey(&k, kk, i + 1);
 590       blowfish_encrypt(&k, p, p);
 591
 592       if (load32(p + 0) != table[i].c[0] ||
 593           load32(p + 4) != table[i].c[1]) {
 594         printf("!!! bad encryption\n"
 595                "  key length = %i\n"
 596                "    expected = %08lx-%08lx\n"
 597                "  calculated = %08lx-%08lx\n",
 598                i + 1,
 599                (unsigned long)table[i].c[0],
 600                (unsigned long)table[i].c[1],
 601                (unsigned long)load32(p + 0),
 602                (unsigned long)load32(p + 4));
 603         f = 0;
 604       }
 605
 606       putchar('.');
 607       fflush(stdout);
 608     }
 609
 610     putchar('\n');
 611
 612     if (f)
 613       printf("*** stage two ok\n");
 614   }
 615
 616   return (0);
 617
 618 }
 619
 620 #endif
 621
 622 /*----- That's all, folks -------------------------------------------------*/