home *** CD-ROM | disk | FTP | other *** search
/ Black Box 4 / BlackBox.cdr / fileutil / pgp10src.arj / BASSLIB.C next >
Encoding:
C/C++ Source or Header  |  1991-05-22  |  34.5 KB  |  990 lines
  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.  
  990.