![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to basslib.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [PGP] / pgp / src|
Return to basslib.c CVS log | Up to [PGP] / pgp / src |
1.1 ! root 1: /* basslib.c -- BassOmatic encipherment functions in C. ! 2: Version 1.0 25 Jun 89 - Last revised 22 May 91 ! 3: ! 4: (c) Copyright 1988 by Philip Zimmermann. All rights reserved. ! 5: This software may not be copied without the written permission of ! 6: Philip Zimmermann. The author assumes no liability for damages ! 7: resulting from the use of this software, even if the damage results ! 8: from defects in this software. No warranty is expressed or implied. ! 9: ! 10: Boulder Software Engineering ! 11: 3021 Eleventh Street ! 12: Boulder, CO 80304 USA ! 13: Tel. (303) 444-4541 ! 14: FAX (303) 444-4541 ext. 10 ! 15: ! 16: BassOmatic is a conventional block cipher with a 256-byte ! 17: block size for the plaintext and the ciphertext. It also ! 18: uses a key size of up to 256 bytes. It runs fairly quickly ! 19: on a computer, faster than most simple DES implementations. ! 20: Like the DES, it can be used in cipher feedback and cipher block ! 21: chaining modes. It is based in part on Charles W. Merritt's ! 22: algorithms which have been used in secure military communications. ! 23: Merritt's original designs were refined by Zhahai Stewart and ! 24: Philip Zimmermann to improve security and to improve performance ! 25: in a portable C implementation. BassOmatic has not yet (in 1989) ! 26: been through a formal security review and has had only limited peer ! 27: review. The initial version was implemented in Microsoft C for the ! 28: IBM PC, and it has been ported to MPW C on the Apple Macintosh ! 29: and to Unix C without significant modification. ! 30: ! 31: BassOmatic gets its name from an old Dan Aykroyd Saturday Night Live ! 32: skit involving a blender and a whole fish. The BassOmatic algorithm ! 33: does to data what the original BassOmatic did to the fish. ! 34: */ ! 35: ! 36: /* Define STATIC as blank to assist execution performance profiling. */ ! 37: #define STATIC static /* define STATIC as static for normal use */ ! 38: ! 39: #include <stdio.h> /* for printf */ ! 40: ! 41: #include "memmgr.h" /* memory manager headers */ ! 42: #include "lfsr.h" /* Linear Feedback Shift Register headers */ ! 43: #include "basslib.h" /* BassOmatic headers */ ! 44: ! 45: /* on many CPUs, using 16 bits for bytecounter is actually faster: */ ! 46: #define bytecounter word16 /* byte, or word16 for speed */ ! 47: ! 48: #ifdef DEBUG ! 49: #define DEBUGprintf1(x) fprintf(stderr,x) ! 50: #define DEBUGprintf2(x,y) fprintf(stderr,x,y) ! 51: #else ! 52: #define DEBUGprintf1(x) /* null macro */ ! 53: #define DEBUGprintf2(x,y) /* null macro */ ! 54: #endif ! 55: ! 56: ! 57: #define NCONTEXTS 3 /* number of key contexts allowed at once */ ! 58: /* NUMBLOX is number of memory blocks in partition */ ! 59: #define NUMBLOX (NCONTEXTS*(NTABLES+3)+8) ! 60: /* declare memory partition buffer space */ ! 61: static byte part[partsize(256,NUMBLOX)]; /* memory partition */ ! 62: /* We could just call calloc() for this space, instead of declaring it here. */ ! 63: ! 64: /* The following variables comprise the keyed context information for the ! 65: ** BassOmatic machine. If the BassOmatic is rekeyed, these variables ! 66: ** will be affected. If more than one BassOmatic key context is needed ! 67: ** concurrently, these variables must be saved and restored for each ! 68: ** context change. ! 69: */ ! 70: ! 71: static boolean initialized = FALSE; /* determines whether key context is defined */ ! 72: static byteptr tlist[NTABLES] = {nil}; /* list of permutation table pointers */ ! 73: static byte bitmasks[NTABLES]; /* bitshredder bitmasks with 50% bits set */ ! 74: ! 75: static byteptr iv = nil; /* CFB Initialization Vector used by initcfb and basscfb */ ! 76: static boolean cfbuncryp = FALSE; /* TRUE means decrypting (in CFB mode) */ ! 77: static boolean uncryp = FALSE; /* TRUE means decrypting (in ECB mode) */ ! 78: /* The following parameters are computed from the key control byte...*/ ! 79: static char nrounds = 0; /* specifies number of rounds thru BassOmatic */ ! 80: static boolean hardrand = FALSE; /* means regenerate tables with BassOmatic */ ! 81: static boolean shred8ways = FALSE; /* means use 8-way bit shredding */ ! 82: static boolean rerand = FALSE; /* means replenish tables with every block */ ! 83: ! 84: static byteptr lfsr = nil; /* it would help to align LFSR on 256-byte boundary */ ! 85: /* rtail is an index into LFSR buffer */ ! 86: static byte rtail = 0; /* points to 256, which is same as 0 */ ! 87: ! 88: /* End of BassOmatic keyed context variables */ ! 89: ! 90: ! 91: ! 92: /* ! 93: ** fillbuf(dst,count,c) - fill byte buffer dst with byte c ! 94: ** dst is destination buffer pointer. ! 95: ** count is nonzero byte count. ! 96: ** c is fill byte. ! 97: */ ! 98: void fillbuf(register byteptr dst, register short count, register byte c) ! 99: { do *dst++ = c; while (--count); ! 100: } /* fillbuf */ ! 101: ! 102: ! 103: /* ! 104: ** CRC routines are purely for debugging purposes... ! 105: */ ! 106: #define CRCDEBUG /* enables CRC debugging code */ ! 107: #ifdef CRCDEBUG ! 108: /* ! 109: ** updcrc - updates CRC 16-bit accumulator with ch, ! 110: ** uses CCITT polynomial: X^16 + X^12 + X^5 + 1 ! 111: */ ! 112: static word16 updcrc(byte ch, word16 crcaccum) ! 113: { word16 shifter,flag,data; ! 114: data = ((word16) ch) & 0xff; ! 115: for (shifter = 0x80; shifter; shifter >>= 1) ! 116: { flag = (crcaccum & 0x8000); ! 117: crcaccum <<= 1; ! 118: crcaccum |= ((shifter & data) ? 1 : 0); ! 119: if (flag) crcaccum ^= 0x1021; ! 120: } ! 121: return (crcaccum & 0xffff); ! 122: } /* updcrc() */ ! 123: ! 124: ! 125: /* ! 126: ** crc() - compute crc of buffer ! 127: ** Used for diagnostic purposes. ! 128: */ ! 129: word16 crc(register byteptr buf, int count) ! 130: { word16 crcaccum; /* CRC accumulator */ ! 131: crcaccum = 0; /* clear crc accumulator */ ! 132: do crcaccum = updcrc(*buf++,crcaccum); ! 133: while (--count); /* loop 256 times */ ! 134: crcaccum = updcrc(0,crcaccum); /* finish up crc */ ! 135: crcaccum = updcrc(0,crcaccum); /* have to do it twice */ ! 136: return(crcaccum); /* return 16-bit CRC */ ! 137: } /* crc */ ! 138: ! 139: ! 140: #define dumpcrc(msg,buf) printf("%s CRC=%04x ",msg,crc(buf,256)) ! 141: ! 142: /* ! 143: ** dumpblock - dump 256-byte buffer in hex ! 144: */ ! 145: static void dumpblock(byteptr buf) ! 146: { bytecounter i; ! 147: i = 256; ! 148: printf(" Memory block at %04X: ",buf); ! 149: do ! 150: { if ((i & 15)==0) ! 151: putchar('\n'); ! 152: printf("%02X ",*buf++); ! 153: } while (--i); /* loop 256 times */ ! 154: dumpcrc("",buf-256); ! 155: putchar('\n'); ! 156: } /* dumpblock */ ! 157: ! 158: #endif /* end of CRC debugging routines */ ! 159: ! 160: ! 161: /* ! 162: ** randbuf and randbuf_counter are used by initbassrand, initbrand, ! 163: ** bassrand, and closebrand. They are not directly used by the BassOmatic ! 164: ** routines except by initkey(), and thus are not considered part of a ! 165: ** lasting key context. ! 166: */ ! 167: static byteptr randbuf = nil; /* buffer for BassOmatic random # generator */ ! 168: static byte randbuf_counter = 0; /* # of random bytes left in randbuf */ ! 169: ! 170: /* ! 171: ** initbrand - initialize bassrand, BassOmatic random number generator ! 172: ** For internal use by initkey() only. ! 173: ** seed is pointer to random number seed buffer. ! 174: ** seedlen is length of seed buffer, must be <= 256. ! 175: */ ! 176: static void initbrand(byteptr seed, short seedlen) ! 177: { short i; ! 178: if (randbuf==nil) ! 179: randbuf = (byteptr) gblock(part); /* allocate block */ ! 180: ! 181: if (seedlen > 256) seedlen=256; ! 182: for (i=0; i<seedlen; i++) /* copy original seed material to randbuf */ ! 183: randbuf[i] = seed[i]; ! 184: ! 185: /* fill rest of randbuf with randomly modified key material */ ! 186: for (; i<256; i++) /* pick up where we left off */ ! 187: randbuf[i] = getlfsr(lfsr,rtail); /* macro gets LFSR byte */ ! 188: ! 189: randbuf_counter = 0; /* # of random bytes left in randbuf */ ! 190: } /* initbrand */ ! 191: ! 192: ! 193: /* ! 194: ** initbassrand - initialize bassrand, BassOmatic random number generator ! 195: ** This can be used for generating cryptographically strong random ! 196: ** numbers by any external application code outside the BassOmatic. ! 197: ** key is pointer to BassOmatic key buffer. ! 198: ** keylen is length of key buffer, must be < 256. ! 199: ** seed is pointer to random number seed buffer. ! 200: ** seedlen is length of seed buffer, must be <= 256. ! 201: ** ! 202: ** NOTE: Because this routine calls initkey(), this generator ! 203: ** must be closed by calling closebass(), NOT closebrand(). ! 204: */ ! 205: void initbassrand(byteptr key, short keylen, byteptr seed, short seedlen) ! 206: { short i; ! 207: if (randbuf==nil) /* prevents multiple initialization */ ! 208: { initkey(key, keylen, FALSE); /* initialize BassOmatic */ ! 209: randbuf = (byteptr) gblock(part); /* allocate block */ ! 210: } ! 211: fillbuf(randbuf,256,0); /* get a clean start */ ! 212: if (seedlen > 256) seedlen=256; ! 213: for (i=0; i<seedlen; i++) /* copy original seed material to randbuf */ ! 214: randbuf[i] = seed[i]; ! 215: randbuf_counter = 0; /* # of random bytes left in randbuf */ ! 216: } /* initbassrand */ ! 217: ! 218: ! 219: /* ! 220: ** bassrand - BassOmatic pseudo-random number generator ! 221: ** This can be used for generating cryptographically strong random ! 222: ** numbers by any external application code outside the BassOmatic. ! 223: */ ! 224: byte bassrand(void) ! 225: { byteptr tmp; ! 226: if (randbuf_counter==0) /* if random buffer is spent...*/ ! 227: { tmp = (byteptr) gblock(part); /* allocate new block */ ! 228: bassomatic(randbuf,tmp); /* fill new block */ ! 229: rblock(part,randbuf); /* release old spent block */ ! 230: randbuf = tmp; /* start on new block */ ! 231: } ! 232: return(randbuf[--randbuf_counter]); /* take a byte from randbuf */ ! 233: } /* bassrand */ ! 234: ! 235: ! 236: /* ! 237: ** closebrand - deallocate storage used by bassrand ! 238: ** For internal use by initkey() only. ! 239: */ ! 240: static void closebrand(void) ! 241: { if (randbuf!=nil) ! 242: randbuf = rblock(part,randbuf); /* release block */ ! 243: } /* closebrand */ ! 244: ! 245: ! 246: /* ! 247: ** buildtbl - build a random byte permutation vector ! 248: ** ! 249: ** References context variables lfsr, rtail, and part. ! 250: ** ! 251: ** A permutation vector is a table of 256 bytes containing the ! 252: ** values 0-255 in random order. Each of the values 0-255 appears ! 253: ** exactly once in the table, with no duplicates and no omissions. ! 254: ** ! 255: ** The appropriate way to build such a table for cryptographic ! 256: ** applications is to do the following: ! 257: ** 1) Start with an empty table, meaning its length is zero. ! 258: ** 2) Use a pseudo-random number generator to generate random bytes ! 259: ** that are appended to the table if and only if they are not ! 260: ** already in the table. If the random byte is already in the ! 261: ** table, it is discarded and another one is generated from the ! 262: ** pseudo-random number generator. As the table gets nearly full, ! 263: ** more and more random bytes are discarded as duplicate entries. ! 264: ** This is continued until 256 bytes have been inserted in the table. ! 265: ** ! 266: ** While this approach seems computationally wasteful, it makes it harder ! 267: ** for a cryptanalyst to infer the properties of the pseudo-random number ! 268: ** generator, because so many of its output bytes are discarded. ! 269: ** ! 270: ** Permutation vectors such as these are useful for byte substitution ! 271: ** tables and byte transposition tables. These are also referred to ! 272: ** herein as key schedule tables. ! 273: */ ! 274: STATIC void buildtbl(register byteptr table, boolean rselect) ! 275: /* table is pointer to table to build. ! 276: rselect is to select which of 2 random number generators to use. ! 277: */ ! 278: { register byteptr notdup; /* scratchpad bitmap */ ! 279: register byte c; ! 280: register short tlen; /* current accumulated table length */ ! 281: register short randtics; /* counts LFSR tics */ ! 282: #define MAXTICS 16383 /* lose patience with LFSR after this long */ ! 283: notdup = (byteptr) gblock(part); /* we could use local stack array instead. */ ! 284: fillbuf(notdup,256,TRUE); /* initialize scratchpad bitmap */ ! 285: tlen = 0; /* start new table with length 0 */ ! 286: /* To fill one table, we can expect to have to tic the LFSR ! 287: typically about 1000-2500 times, on the average. */ ! 288: randtics = MAXTICS; /* countdown maximum LFSR tics */ ! 289: do ! 290: { /* get pseudo-random byte from either LFSR or BassOmatic... */ ! 291: c = rselect ? ! 292: bassrand() : /* get a hard random byte */ ! 293: getlfsr(lfsr,rtail); /* macro gets LFSR byte */ ! 294: if (notdup[c]) /* not in table already? */ ! 295: { table[tlen++] = c; /* append it */ ! 296: notdup[c] = FALSE; /* indicate it's now in table */ ! 297: } ! 298: if (--randtics == 0) /* detects bogus random generator */ ! 299: { /* Must be an LFSR problem, because the bassrand ! 300: generator will probably always run OK, so we ! 301: won't even check rselect. */ ! 302: DEBUGprintf1("\007Adjusting weak LFSR. "); ! 303: stomplfsr(lfsr); /* hit unruly LFSR upside the head */ ! 304: randtics=MAXTICS; /* reset countdown counter */ ! 305: } /* randtics alarm */ ! 306: } while (tlen<256); /* do until table is full */ ! 307: if (!rselect) ! 308: /* "discard" current contents of lfsr buffer. Causes ! 309: steplfsr256 to be called the next time getlfsr is called. */ ! 310: rtail=0; /* dump some LFSR output, confuse attacker */ ! 311: rblock(part,notdup); /* deallocate storage */ ! 312: } /* buildtbl */ ! 313: ! 314: ! 315: /* ! 316: ** Some notes-- ! 317: ** ! 318: ** With some sacrifice of performance due to bit packing and unpacking, ! 319: ** it would be possible to modify the whole BassOmatic algorithm to use ! 320: ** a smaller block size. This would require using smaller key schedule ! 321: ** tables with smaller entries. For example, you could use a table of ! 322: ** 16 4-bit entries instead of 256 8-bit entries. The number of bits in ! 323: ** each table entry exponentialy determines the number of entries in the ! 324: ** key schedule table, and those two dimensions together determine the ! 325: ** size of the plaintext or ciphertext block. The following chart ! 326: ** summarizes the relationship between table entry width and cipher ! 327: ** block size. ! 328: ** ! 329: ** ENTRY TABLE BLOCK ! 330: ** WIDTH LENGTH SIZE ! 331: ** ----- ------ ----- ! 332: ** 8 bits 256 entries 2048 bits, or 256 bytes ! 333: ** 7 bits 128 entries 896 bits, or 112 bytes ! 334: ** 6 bits 64 entries 384 bits, or 48 bytes ! 335: ** 5 bits 32 entries 160 bits, or 20 bytes ! 336: ** 4 bits 16 entries 64 bits, or 8 bytes ! 337: ** ! 338: ** ! 339: ** Other questions-- ! 340: ** How many of the key bits are actually effective in producing the ! 341: ** key schedule tables? Are any key bits wasted? ! 342: ** ! 343: ** There are 256! permutation tables possible. With 8 tables made ! 344: ** from a single key, there are (256!)**8 sets of tables possible. ! 345: ** If there are n bytes in a key (with n<=256), there are 256**n ! 346: ** keys possible. ! 347: ** ! 348: ** In theory, more than one of these keys can produce the same table ! 349: ** or set of tables, since a different selection of random output ! 350: ** bytes from the pseudorandom number generator may be discarded to ! 351: ** produce the same table. ! 352: */ ! 353: ! 354: ! 355: /* ! 356: ** invert - invert a random permutation table ! 357: ** Called from bldtbls. ! 358: */ ! 359: STATIC void invert(register byteptr intable, register byteptr outtable) ! 360: { register byte i; ! 361: i = 0; /* byte loop index i = 0,255,254,...2,1 */ ! 362: do outtable[intable[i]] = i; /* invert table */ ! 363: while (--i); /* loop 256 times */ ! 364: } /* invert */ ! 365: ! 366: ! 367: /* ! 368: ** transpose - transpose input via table to output ! 369: ** Called from bldtbls. ! 370: */ ! 371: STATIC void transpose(register byteptr in, register byteptr out, register byteptr table) ! 372: /* in and out are the input, output blocks, 256 bytes each. ! 373: table contains random permutation of 256 bytes. ! 374: */ ! 375: { register byte i; ! 376: i = 256; /* byte loop counter */ ! 377: do *out++ = in[*table++]; /* table transpose */ ! 378: while (--i); /* loop 256 times */ ! 379: } /* transpose */ ! 380: ! 381: ! 382: /* ! 383: ** halfmask(c) - returns TRUE iff 50% of the bits in c are set. ! 384: ** Called only from getmask. ! 385: */ ! 386: STATIC boolean halfmask(byte c) ! 387: { byte bitmask,nbits; ! 388: nbits=0; bitmask=0x80; ! 389: do ! 390: { if (c & bitmask) ! 391: nbits++; /* count the # of 1 bits */ ! 392: bitmask >>= 1; ! 393: } while (bitmask); ! 394: return(nbits==4); /* are 4 out of 8 bits set? */ ! 395: } /* halfmask */ ! 396: ! 397: ! 398: /* ! 399: ** getmask - search table for a suitable random mask byte. ! 400: ** Finds a random mask byte with 50% of its bits set. ! 401: ** Called from bldtbls. ! 402: */ ! 403: STATIC byte getmask(register byteptr table) ! 404: /* table contains random permutation of 256 bytes. */ ! 405: { byte i; ! 406: i = 0; /* byte loop index i = 0,255,254,...2,1 */ ! 407: do ! 408: { if (halfmask(table[i])) ! 409: return(table[i]); /* returns 1st 50% bitmask found */ ! 410: } while (--i); /* loop 256 times */ ! 411: return (0x0f); /* never gets here */ ! 412: } /* getmask */ ! 413: ! 414: ! 415: #define ptrswap(p1,p2) { register byteptr p3; p3=p1; p1=p2; p2=p3; } ! 416: ! 417: ! 418: /* ! 419: ** bldtbls - generate all the permutation tables for the BassOmatic ! 420: ** ! 421: ** References context variables tlist, shred8ways, bitmasks, and part. ! 422: */ ! 423: STATIC void bldtbls(boolean hardrand, boolean decryp) ! 424: /* hardrand specifies which random number generator to use. ! 425: decryp determines whether to invert the tables. ! 426: */ ! 427: { byteptr tmp; /* scratchpad table pointers */ ! 428: byteptr mixer; /* table transposer */ ! 429: byte i; ! 430: tmp = (byteptr) gblock(part); /* allocate new block */ ! 431: ! 432: mixer = (byteptr) gblock(part); /* allocate transposer table */ ! 433: buildtbl(mixer,hardrand); ! 434: ! 435: for (i=0; i<NTABLES; i++) /* for each key schedule table */ ! 436: { /* build a random byte permutation vector... */ ! 437: buildtbl(tmp,hardrand); ! 438: if (!shred8ways) /* need bitmasks for 2-way bitshredding */ ! 439: bitmasks[i] = getmask(tmp); ! 440: /* currently, tmp is the table we just built */ ! 441: transpose(tmp,tlist[i],mixer); /* mix up the table */ ! 442: /* now tlist[i] is the table we just built */ ! 443: } /* for each table */ ! 444: ! 445: rblock(part,mixer); /* deallocate transposer table */ ! 446: ! 447: /* For decryption, it's not safe to invert any tables until they've ! 448: all been built, in case hardrand is set. Use separate loop... */ ! 449: if (decryp) /* decryption uses inverted tables */ ! 450: for (i=0; i<NTABLES; i++) /* for each table */ ! 451: { invert(tlist[i],tmp); ! 452: ptrswap(tlist[i],tmp); /* swap/replace block ptrs */ ! 453: } /* for each table */ ! 454: rblock(part,tmp); /* deallocate block */ ! 455: DEBUGprintf1("*"); ! 456: } /* bldtbls */ ! 457: ! 458: ! 459: /* ! 460: ** bass_save - saves BassOmatic key context in context structure ! 461: */ ! 462: void bass_save(KEYCONTEXT *context) ! 463: { int i; ! 464: context->initialized = initialized; ! 465: for (i=0; i<NTABLES; i++) ! 466: context->tlist[i] = tlist[i]; ! 467: for (i=0; i<NTABLES; i++) ! 468: context->bitmasks[i] = bitmasks[i]; ! 469: context->iv = iv; /* note that iv was passed to initcfb by caller */ ! 470: context->cfbuncryp = cfbuncryp; ! 471: context->uncryp = uncryp; ! 472: context->nrounds = nrounds; ! 473: context->hardrand = hardrand; ! 474: context->shred8ways = shred8ways; ! 475: context->rerand = rerand; ! 476: context->lfsr = lfsr; ! 477: context->rtail = rtail; ! 478: } /* bass_save */ ! 479: ! 480: ! 481: /* ! 482: ** bass_restore - restore BassOmatic key context from context structure ! 483: */ ! 484: void bass_restore(KEYCONTEXT *context) ! 485: { int i; ! 486: initialized = context->initialized; ! 487: for (i=0; i<NTABLES; i++) ! 488: tlist[i] = context->tlist[i]; ! 489: for (i=0; i<NTABLES; i++) ! 490: bitmasks[i] = context->bitmasks[i]; ! 491: iv = context->iv; /* note that iv was passed to initcfb by caller */ ! 492: cfbuncryp = context->cfbuncryp; ! 493: uncryp = context->uncryp; ! 494: nrounds = context->nrounds; ! 495: hardrand = context->hardrand; ! 496: shred8ways = context->shred8ways; ! 497: rerand = context->rerand; ! 498: lfsr = context->lfsr; ! 499: rtail = context->rtail; ! 500: } /* bass_restore */ ! 501: ! 502: ! 503: /* ! 504: ** closebass - end the current BassOmatic key context, freeing its buffers ! 505: */ ! 506: void closebass(void) ! 507: { int i; ! 508: if (initialized) ! 509: { ! 510: /* Close BassOmatic random number generator, in case it's open: */ ! 511: closebrand(); ! 512: ! 513: for (i=0; i<NTABLES; i++) ! 514: if (tlist[i]!=nil) ! 515: tlist[i] = rblock(part,tlist[i]); ! 516: /* Note that iv is not allocated from memory manager, ! 517: and thus should not be deallocated */ ! 518: if (lfsr!=nil) ! 519: lfsr = rblock(part,lfsr); ! 520: initialized = FALSE; ! 521: } ! 522: } /* closebass */ ! 523: ! 524: ! 525: static char *copyright_notice(void) ! 526: /* force linker to include copyright notice in the executable object image. */ ! 527: { return ("(c)1988 Philip Zimmermann"); } /* copyright_notice */ ! 528: ! 529: ! 530: /* ! 531: ** initkey - Initializes the BassOmatic key schedule tables via key. ! 532: ** ! 533: ** References context variables from key context structure, all of them. ! 534: ** ! 535: ** Uses several bits from the first byte of the key to select ! 536: ** how exhaustivly to run the BassOmatic. The key control bits ! 537: ** specify what tradeoff to make between speed and security. ! 538: ** These bits in the first byte of the key have these meanings: ! 539: ** bits 0-2: Number of rounds thru BassOmatic (0-7 means 1-8 ! 540: ** times through). The greater the number, the slower ! 541: ** it runs. ! 542: ** bit 3: Set to 1 if we should use slower 8-way bit shredding, ! 543: ** Set to 0 if we should use faster 50% bitmask shredding. ! 544: ** bit 4: Set to 1 means use BassOmatic to build its own tables. ! 545: ** bit 5: Set to 1 iff we should rebuild tables with every block. ! 546: ** This implicitly disables bit 4, above. ! 547: ** bits 6-7: Reserved. ! 548: ** ! 549: ** Key control bit 4 enables a two-tiered key schedule table ! 550: ** generation. The first set of tables are generated in the usual ! 551: ** way with a linear feedback shift register (LFSR). Then, a new ! 552: ** set of tables is regenerated with a far better pseudo-random ! 553: ** number generator--namely, the BassOmatic running off the first ! 554: ** set of tables. The BassOmatic pseudo-random number generator ! 555: ** feeds its output back into itself to generate a stream of ! 556: ** random blocks. It is seeded with the same raw key that ! 557: ** seeded the LFSR. When the new set of tables are built, they ! 558: ** replace the first set as the working tables. ! 559: ** ! 560: ** Key control bit 5 keeps running the pseudorandom number generator ! 561: ** to continuously rebuild the key schedule tables for each block of text. ! 562: ** It automatically turns off key control bit 4. Continuously replenishing ! 563: ** the tables greatly slows down everything, but it improves security ! 564: ** significantly. This mode unfortunately also makes using the BassOmatic ! 565: ** in the DES-like cipher block chaining (CBC) and cipher feedback (CFB) ! 566: ** modes non-self-synchronizing. ! 567: */ ! 568: int initkey(byteptr key, short keylen, boolean decryp) ! 569: /* key is pointer to key buffer, up to 256 bytes long. ! 570: keylen is length of key buffer, including key control byte. ! 571: decryp is TRUE if decrypting, FALSE if encrypting. ! 572: */ ! 573: { byte i; ! 574: ! 575: /* initialize BassOmatic data structures */ ! 576: static boolean partition_initialized = FALSE; ! 577: if (!partition_initialized) ! 578: { /* if already initialized, skip these steps. */ ! 579: partition_initialized = TRUE; ! 580: pcreat2(part,256,NUMBLOX); /* initialize memory partition */ ! 581: #ifdef DEBUG2 ! 582: dumpfree(part); /* dump memory free list */ ! 583: #endif ! 584: } ! 585: ! 586: if (key == nil) /* initkey(nil,0,0) only initializes partition */ ! 587: return(0); ! 588: ! 589: if (keylen < 2) ! 590: { /* key must have control byte and nonzero body length */ ! 591: fprintf(stderr,"\nError: BassOmatic key too short.\n\007"); ! 592: return(-1); /* error return */ ! 593: } ! 594: ! 595: closebass(); /* deallocate any previously allocated buffers */ ! 596: ! 597: initialized = TRUE; /* set already initialized flag */ ! 598: for (i=0; i<NTABLES; i++) /* for each table */ ! 599: { /* get memory block from partition */ ! 600: tlist[i] = (byteptr) gblock(part); ! 601: } /* for each table */ ! 602: ! 603: nrounds = (*key & 0x07) + 1; /* specifies number of rounds */ ! 604: shred8ways = ((*key & 0x08) != 0); /* use 8-way bit shredding? */ ! 605: rerand = ((*key & 0x20) != 0); /* replenish tables with every block */ ! 606: /* hardrand means use BassOmatic table generator... */ ! 607: hardrand = ((*key & 0x10) != 0) && !rerand; ! 608: uncryp = FALSE; /* initially assume encrypt, in case of hardrand */ ! 609: ! 610: #ifdef DEBUG3 ! 611: if (decryp) /* use inverted tables for decryption */ ! 612: fprintf(stderr,"Decrypt, "); ! 613: else /* use non-inverted tables for encryption */ ! 614: fprintf(stderr,"Encrypt, "); ! 615: fprintf(stderr,"%x rounds, ",nrounds); ! 616: if (hardrand) /* BassOmatic random number generator */ ! 617: fprintf(stderr,"hard "); ! 618: else /* LFSR random number generator */ ! 619: fprintf(stderr,"LFSR "); ! 620: if (rerand) /* rebuild tables for every block */ ! 621: fprintf(stderr,"dynamic "); ! 622: else /* keep same tables throughout message */ ! 623: fprintf(stderr,"static "); ! 624: fprintf(stderr,"tables, "); ! 625: ! 626: if (shred8ways) ! 627: fprintf(stderr,"8-way bitshred.\n"); ! 628: else ! 629: fprintf(stderr,"2-way bitshred.\n"); ! 630: #endif /* DEBUG3 */ ! 631: ! 632: /* init LFSR random number generator with key seed */ ! 633: if (lfsr==nil) ! 634: lfsr = (byteptr) gblock(part); /* allocate LFSR buffer */ ! 635: if (keylen > 255) keylen=255; ! 636: /* Assume actual key starts after 1st byte, which is control byte */ ! 637: initlfsr(key+1,keylen-1,lfsr,&rtail); ! 638: /* dumpblock(lfsr); */ ! 639: ! 640: buildtbl(tlist[0],FALSE); /* build throwaway table to prime the LFSR */ ! 641: ! 642: /* generate all the permutation tables for the key schedule */ ! 643: if (!rerand) /* don't do it now if it's going to be redone anyway */ ! 644: bldtbls(FALSE,decryp && !hardrand); ! 645: ! 646: /* if hardrand, rebuild tables again, this time with BassOmatic */ ! 647: if (hardrand) /* rebuild tables with BassOmatic */ ! 648: { /* form progressivly better bassrand function. */ ! 649: /* init BassOmatic pseudo-random generator */ ! 650: initbrand(key+1,keylen-1); /* skip 1st key byte */ ! 651: bldtbls(hardrand,decryp);/* generate all the tables again */ ! 652: closebrand(); /* deallocate scratch buffers for bassrand */ ! 653: } /* if (hardrand) */ ! 654: uncryp = decryp; /* specifies BassOmatic decrypt or encrypt */ ! 655: ! 656: if (!rerand) /* if we don't need lfsr buffer anymore, then free it. */ ! 657: lfsr=rblock(part,lfsr); /* sure hope we don't use lfsr again */ ! 658: ! 659: /* Do an explicit reference to the copyright notice so that the linker ! 660: will be forced to include it in the executable object image... */ ! 661: copyright_notice(); /* has no real effect at run time */ ! 662: return(0); /* normal return */ ! 663: } /* initkey */ ! 664: ! 665: ! 666: /* Now for the primitives called directly from the BassOmatic algorithm...*/ ! 667: ! 668: ! 669: /* ! 670: ** shred1bit - 8-way random bit shred ! 671: ** ! 672: ** Tears each byte into 8 bits, and randomly distributes the bits. ! 673: ** Uses 8 different permutation vectors from tlist. ! 674: ** Unfortunately, it always uses the same 8 tables. ! 675: */ ! 676: STATIC void shred1bit(register byteptr in, register byteptr out) ! 677: /* in and out are input, output blocks, 256 bytes each. */ ! 678: { register byte bitmask; /* byte has 1 of its bits set */ ! 679: register bytecounter i; ! 680: register byteptr table; /* permutation vector */ ! 681: byteptr insave; /* for saving input buffer pointer */ ! 682: byte j; ! 683: bitmask = 0x80; /* initialize bitmask at highest bit */ ! 684: fillbuf(out,256,0); /* make sure output buffer is clean */ ! 685: /* We could run faster by skipping the fillbuf step, and ! 686: using "=" instead of "|=" the first time thru the j loop below. */ ! 687: ! 688: insave = in; /* save input buffer pointer */ ! 689: for (j=0; j<=7; j++) /* for each of 8 bits per byte */ ! 690: { i = 256; /* byte loop counter */ ! 691: table = tlist[j]; /* select a permutation vector */ ! 692: in = insave; /* recover input buffer pointer */ ! 693: do /* permute a single bit from each byte */ ! 694: out[*table++] |= (*in++ & bitmask); ! 695: while (--i); /* loop 256 times */ ! 696: bitmask >>= 1; /* select next bit for isolation */ ! 697: } ! 698: } /* shred1bit */ ! 699: ! 700: ! 701: /* ! 702: ** shred4bit - 2-way random bit shred ! 703: ** ! 704: ** Tears each byte in half, and randomly distributes the halves. ! 705: */ ! 706: STATIC void shred4bit(register byteptr in, register byteptr out, ! 707: register byteptr t1, register byteptr t2, register byte bitmask) ! 708: /* in and out are input, output blocks, 256 bytes each. ! 709: t1 and t2 each contain random permutation of 256 bytes. ! 710: bitmask is byte which has 50% of its bits set. ! 711: */ ! 712: { register bytecounter i; ! 713: byteptr insave; /* for saving input buffer pointer */ ! 714: insave = in; /* save input buffer pointer */ ! 715: i = 256; /* byte loop counter */ ! 716: do /* isolate half the bits */ ! 717: out[*t1++] = *in++ & bitmask; ! 718: while (--i); /* loop 256 times */ ! 719: in = insave; /* recover input buffer pointer */ ! 720: bitmask = ~bitmask; /* invert bitmask for other half */ ! 721: i = 256; /* byte loop counter */ ! 722: do /* isolate other half and combine the two halfs */ ! 723: out[*t2++] |= *in++ & bitmask; ! 724: while (--i); /* loop 256 times */ ! 725: } /* shred4bit */ ! 726: ! 727: ! 728: /* ! 729: ** multilookup - change input via multiple substitution tables ! 730: */ ! 731: STATIC void multilookup(register byteptr in, register byteptr out, byte ti) ! 732: /* in and out are input, output blocks, 256 bytes each. ! 733: ti contains index into starting point of tlist. ! 734: */ ! 735: { register byteptr table; ! 736: register byte i; ! 737: byte j; ! 738: j=8; ! 739: do ! 740: { table = tlist[ti++ & 7]; /* assumes 8 tables */ ! 741: i=32; ! 742: do *out++ = table[*in++]; /* multi-table substitute */ ! 743: while (--i); /* loop 32 times */ ! 744: } ! 745: while (--j); /* loop 8 times */ ! 746: } /* multilookup */ ! 747: ! 748: ! 749: /* ! 750: ** xortable - change block via xor with random table ! 751: ** ! 752: ** This function would serve as its own inverse, if the table is the ! 753: ** same each time. For use with an inverted table, call ixortable. ! 754: ** This function inverts 50% of the bits. ! 755: */ ! 756: STATIC void xortable(register byteptr block, register byteptr table) ! 757: /* block is a 256 byte block. ! 758: table contains random permutation of 256 bytes. ! 759: */ ! 760: { register bytecounter i; ! 761: i = 256; /* byte loop counter */ ! 762: do *block++ ^= *table++; /* table xor */ ! 763: while (--i); /* loop 256 times */ ! 764: } /* xortable */ ! 765: ! 766: ! 767: /* ! 768: ** ixortable - change block via xor with inverted random table ! 769: ** ! 770: ** This function inverts 50% of the bits. It is the inverse function ! 771: ** for xortable, if the table is inverted. Used for decryption. ! 772: */ ! 773: STATIC void ixortable(register byteptr block, register byteptr table) ! 774: /* block is a 256 byte block. ! 775: table contains random permutation of 256 bytes. ! 776: */ ! 777: { register byte i; ! 778: i = 0; /* byte loop index i = 0,255,254,...2,1 */ ! 779: do block[table[i]] ^= i; /* inverted table xor */ ! 780: while (--i); /* loop 256 times */ ! 781: } /* ixortable */ ! 782: ! 783: ! 784: /* ! 785: ** rake - rake forwards and backwards with xor and add ! 786: ** ! 787: ** This is not a keyed operation. It is only useful for increasing ! 788: ** the intersymbol dependencies between the plaintext and the ciphertext, ! 789: ** not the key and the ciphertext. Its inverse is function unrake. ! 790: */ ! 791: STATIC void rake(register byteptr block) ! 792: { register byte i; ! 793: register byteptr block1; ! 794: block1 = block++; ! 795: /* now block1 = 0, block = 1, relatively speaking */ ! 796: i = 255; /* loop 255 times */ ! 797: /* first do forward raking with cumulative xor */ ! 798: do /* from *1++ ^= *0++; thru *255++ ^= *254++; */ ! 799: *block++ ^= *block1++; ! 800: while (--i); ! 801: /* now block1 = 255, block = 256 */ ! 802: i = 255; /* loop 255 times */ ! 803: /* now do backward raking with cumulative add */ ! 804: do /* from *(--255) += *(--256); thru *(--1) += *(--2); */ ! 805: *(--block1) += *(--block); ! 806: while (--i); ! 807: /* now block1 = 0, block = 1 */ ! 808: } /* rake */ ! 809: ! 810: ! 811: /* ! 812: ** unrake - unrake forwards and backwards with subtract and xor ! 813: ** ! 814: ** This is the inverse function of rake. Used for decryption. ! 815: */ ! 816: STATIC void unrake(register byteptr block) ! 817: { register byte i; ! 818: register byteptr block1; ! 819: block1 = block++; ! 820: /* now block1 = 0, block = 1, relatively speaking */ ! 821: i = 255; /* loop 255 times */ ! 822: /* first do forward unraking with cumulative subtract */ ! 823: do /* from *0++ -= *1++; thru *254++ -= *255++; */ ! 824: *block1++ -= *block++; ! 825: while (--i); ! 826: /* now block1 = 255, block = 256 */ ! 827: i = 255; /* loop 255 times */ ! 828: /* now do backward unraking with cumulative xor */ ! 829: do /* from *(--256) ^= *(--255); thru *(--2) ^= *(--1); */ ! 830: *(--block) ^= *(--block1); ! 831: while (--i); ! 832: /* now block1 = 0, block = 1 */ ! 833: } /* unrake */ ! 834: ! 835: ! 836: /* ! 837: ** copy256(dst,src) - copy 256-byte buffer src to dst ! 838: */ ! 839: void copy256(register byteptr dst, register byteptr src) ! 840: { register bytecounter size; ! 841: size = 256; /* loop 256 times */ ! 842: do *dst++ = *src++; while (--size); ! 843: } /* copy256 */ ! 844: ! 845: ! 846: #define f(i,j) (((i)+(j)) & 7) /* used for circular addressing mod 8 */ ! 847: #define tl(i,j) tlist[f(i,j)] /* assumes 8 tables */ ! 848: ! 849: ! 850: /* ! 851: ** bassomatic - encipher 1 block with BassOmatic enciphering algorithm ! 852: ** ! 853: ** Assumes initkey has already been called. ! 854: ** References context variables tlist, nrounds, shred8ways, ! 855: ** bitmasks, uncryp, rerand, and part. ! 856: */ ! 857: void bassomatic(byteptr in, byteptr out) ! 858: /* in and out are input, output blocks, 256 bytes each. */ ! 859: { char i; /* signed char */ ! 860: byteptr tmp; ! 861: ! 862: if (rerand) /* dynamic replenishment of tables? */ ! 863: bldtbls(FALSE,uncryp); ! 864: ! 865: tmp = (byteptr) gblock(part); /* get memory block */ ! 866: copy256(out,in); /* copy in to out */ ! 867: ! 868: if (uncryp) ! 869: { /* do decryption */ ! 870: for (i=nrounds-1; i>=0; i--) /* repeat a few rounds */ ! 871: { multilookup(out,tmp,f(i,2)); ! 872: unrake(tmp); /* not effective if last step */ ! 873: if (shred8ways) /* use 8-way bit shredding */ ! 874: shred1bit(tmp,out); ! 875: else /* use faster 2-way bit shredding */ ! 876: shred4bit(tmp,out,tl(i,1),tl(i,5), ! 877: bitmasks[f(i,3)]); ! 878: ixortable(out,tl(i,0)); /* inverts 50% of bits */ ! 879: } /* for loop */ ! 880: } /* if decryption */ ! 881: else /* do encryption */ ! 882: { for (i=0; i<nrounds; i++) /* repeat a few rounds */ ! 883: { xortable(out,tl(i,0)); /* inverts 50% of bits */ ! 884: if (shred8ways) /* use 8-way bit shredding */ ! 885: shred1bit(out,tmp); ! 886: else /* use faster 2-way bit shredding */ ! 887: shred4bit(out,tmp,tl(i,1),tl(i,5), ! 888: bitmasks[f(i,3)]); ! 889: rake(tmp); /* not effective if last step */ ! 890: multilookup(tmp,out,f(i,2)); ! 891: } /* for loop */ ! 892: } /* else encryption */ ! 893: rblock(part,tmp); /* release block */ ! 894: } /* bassomatic */ ! 895: ! 896: ! 897: /* ! 898: ** xorbuf - change buffer via xor with random mask block ! 899: ** Used for Cipher Feedback (CFB) or Cipher Block Chaining ! 900: ** (CBC) modes of encryption. ! 901: ** Can be applied for any block encryption algorithm, ! 902: ** such as the DES or the BassOmatic. ! 903: */ ! 904: STATIC void xorbuf(register byteptr buf, register byteptr mask, register int count) ! 905: /* count must be > 0 */ ! 906: { do ! 907: *buf++ ^= *mask++; ! 908: while (--count); ! 909: } /* xorbuf */ ! 910: ! 911: ! 912: /* ! 913: ** cfbshift - shift bytes into IV for CFB input ! 914: ** Used only for Cipher Feedback (CFB) mode of encryption. ! 915: ** Can be applied for any block encryption algorithm, ! 916: ** such as the DES or the BassOmatic. ! 917: */ ! 918: STATIC void cfbshift(register byteptr iv, register byteptr buf, ! 919: register int count, int blocksize) ! 920: /* iv is the initialization vector. ! 921: buf is the buffer pointer. ! 922: count is the number of bytes to shift in...must be > 0. ! 923: blocksize is 8 for DES, 256 for BassOmatic. ! 924: */ ! 925: { int retained; ! 926: retained = blocksize-count; /* number bytes in iv to retain */ ! 927: /* left-shift retained bytes of IV over by count bytes to make room */ ! 928: while (retained--) ! 929: { *iv = *(iv+count); ! 930: iv++; ! 931: } ! 932: /* now copy count bytes from buf to shifted tail of IV */ ! 933: do *iv++ = *buf++; ! 934: while (--count); ! 935: } /* cfbshift */ ! 936: ! 937: ! 938: #define BLOCKSIZE 256 /* encryption block size for CFB mode. */ ! 939: ! 940: /* ! 941: ** initcfb - Initializes the BassOmatic key schedule tables via key, ! 942: ** and initializes the Cipher Feedback mode IV. ! 943: ** References context variables cfbuncryp and iv. ! 944: */ ! 945: int initcfb(byteptr iv0, byteptr key, short keylen, boolean decryp) ! 946: /* iv0 is copied to global iv, buffer will be destroyed by basscfb. ! 947: key is pointer to key buffer, up to 256 bytes long. ! 948: keylen is length of key buffer. ! 949: decryp is TRUE if decrypting, FALSE if encrypting. ! 950: */ ! 951: { iv = iv0; /* iv is not allocated from memory manager */ ! 952: cfbuncryp = decryp; ! 953: return (initkey(key,keylen,FALSE)); ! 954: } /* initcfb */ ! 955: ! 956: ! 957: /* ! 958: ** basscfb - encipher 1 block with BassOmatic enciphering algorithm, ! 959: ** using Cipher Feedback (CFB) mode. ! 960: ** ! 961: ** Assumes initcfb has already been called. ! 962: ** References context variables cfbuncryp and iv. ! 963: */ ! 964: void basscfb(byteptr buf, int count) ! 965: /* buf is input, output buffer, may be more than 1 block. ! 966: count is byte count of buffer. May be > BLOCKSIZE. ! 967: */ ! 968: { int chunksize; /* smaller of count, BLOCKSIZE */ ! 969: byte temp[BLOCKSIZE]; ! 970: ! 971: while ((chunksize = min(count,BLOCKSIZE)) > 0) ! 972: { bassomatic(iv,temp); /* encrypt iv. */ ! 973: ! 974: if (cfbuncryp) /* buf is ciphertext */ ! 975: /* shift in ciphertext to IV... */ ! 976: cfbshift(iv,buf,chunksize,BLOCKSIZE); ! 977: ! 978: /* convert buf via xor */ ! 979: xorbuf(buf,temp,chunksize); /* buf now has enciphered output */ ! 980: ! 981: if (!cfbuncryp) /* buf was plaintext, is now ciphertext */ ! 982: /* shift in ciphertext to IV... */ ! 983: cfbshift(iv,buf,chunksize,BLOCKSIZE); ! 984: ! 985: count -= chunksize; ! 986: buf += chunksize; ! 987: } ! 988: } /* basscfb */ ! 989:
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.