des.c

The C++ code for data encryption system of NIST.

   *
   *        - No checks are done to ensure that there is enough room
   *          in <dst>, or that the bit numbers in <map> do not exceed
   *          the bits available in <src>.  A good reason to make this
   *          function static (private).
   *
   *        - The <mapsize> value is in bytes.  All permutations in DES
   *          use tables that are a multiple of 8 bits, so there is no
   *          need to handle partial bytes.  (Yes, I know that there
   *          are some machines out there that still use bytes of a size
   *          other than 8 bits.  For our purposes we'll stick with 8-bit
   *          bytes.)
   *
   * ------------------------------------------------------------------------ **
   */
  {
  int bitcount;
  int i;

  /* Clear all bits in the destination.
   */
  for( i = 0; i < mapsize; i++ )
    dst[i] = 0;

  /* Set destination bit if the mapped source bit it set. */
  bitcount = mapsize * 8;
  for( i = 0; i < bitcount; i++ )
    {
    if( GETBIT( src, map[i] ) )
      SETBIT( dst, i );
    }
  } /* Permute */


static void KeyShift( uchar *key, const int numbits )
  /* ------------------------------------------------------------------------ **
   * Split the 56-bit key in half & left rotate each half by <numbits> bits.
   *
   *  Input:  key     - The 56-bit key to be split-rotated.
   *          numbits - The number of bits by which to rotate the key.
   *
   *  Output: none.
   *
   *  Notes:  There are probably several better ways to implement this.
   *
   * ------------------------------------------------------------------------ **
   */
  {
  int   i;
  uchar keep = key[0];  /* Copy the highest order bits of the key. */

  /* Repeat the shift process <numbits> times.
   */
  for( i = 0; i < numbits; i++ )
    {
    int j;

    /* Shift the entire thing, byte by byte.
     */
    for( j = 0; j < 7; j++ )
      {
      if( j && (key[j] & 0x80) )  /* If the top bit of this byte is set. */
        key[j-1] |=  0x01;        /* ...shift it to last byte's low bit. */
      key[j] <<= 1;               /* Then left-shift the whole byte.     */
      }

    /* Now move the high-order bits of each 28-bit half-key to their
     * correct locations.
     * Bit 27 is the lowest order bit of the first half-key.
     * Before the shift, it was the highest order bit of the 2nd half-key.
     */
    if( GETBIT( key, 27 ) )     /* If bit 27 is set... */
      {
      CLRBIT( key, 27 );        /* ...clear bit 27. */
      SETBIT( key, 55 );        /* ...set lowest order bit of 2nd half-key. */
      }

    /* We kept the highest order bit of the first half-key in <keep>.
     * If it's set, copy it to bit 27.
     */
    if( keep & 0x80 )
      SETBIT( key, 27 );

    /* Rotate the <keep> byte too, in case <numbits> is 2 and there's
     * a second round coming.
     */
    keep <<= 1;
    }
  } /* KeyShift */


static void sbox( uchar *dst, const uchar *src )
  /* ------------------------------------------------------------------------ **
   * Perform S-Box substitutions.
   *
   *  Input:  dst - Destination byte array into which the S-Box substituted
   *                bitmap will be written.
   *          src - Source byte array.
   *
   *  Output: none.
   *
   *  Notes:  It's really not possible (for me, anyway) to understand how
   *          this works without reading one or more detailed explanations.
   *          Quick overview, though:
   *
   *          After the DataExpansion step (in which a 32-bit bit array is
   *          expanded to a 48-bit bit array) the expanded data block is
   *          XOR'd with 48-bits worth of key.  That 48 bits then needs to
   *          be condensed back into 32 bits.
   *
   *          The S-Box substitution handles the data reduction by breaking
   *          the 48-bit value into eight 6-bit values.  For each of these
   *          6-bit values there is a table (an S-Box table).  The table
   *          contains 64 possible values.  Conveniently, a 6-bit integer
   *          can represent a value between 0 and 63.
   *
   *          So, if you think of the 48-bit bit array as an array of 6-bit
   *          integers, you use S-Box table 0 with the 0th 6-bit value.
   *          Table 1 is used with the 6-bit value #1, and so on until #7.
   *          Within each table, the correct substitution is found based
   *          simply on the value of the 6-bit integer.
   *
   *          Well, the original algorithm (and most documentation) don't
   *          make it so simple.  There's a complex formula for mapping
   *          the 6-bit values to the correct substitution.  Fortunately,
   *          those lookups can be precomputed (and have been for this
   *          implementation).  See pp 274-274 in Schneier.
   *
   *          Oh, and the substitute values are all 4-bit values, so each
   *          6-bits gets reduced to 4-bits resulting in a 32-bit bit array.
   *
   * ------------------------------------------------------------------------ **
   */
  {
  int i;

  /* Clear the destination array.
   */
  for( i = 0; i < 4; i++ )
    dst[i] = 0;

  /* For each set of six input bits...
   */
  for( i = 0; i < 8; i++ )
    {
    int j;
    int Snum;
    int bitnum;

    /* Extract the 6-bit integer from the source.
     * This will be the lookup key within the SBox[i] array.
     */
    for( Snum = j = 0, bitnum = (i * 6); j < 6; j++, bitnum++ )
      {
      Snum <<= 1;
      Snum  |= GETBIT( src, bitnum );
      }

    /* Find the correct value in the correct SBox[]
     * and copy it into the destination.
     * Left shift the nibble four bytes for even values of <i>.
     */
    if( 0 == (i%2) )
      dst[i/2] |= ((SBox[i][Snum]) << 4);
    else
      dst[i/2] |= SBox[i][Snum];
    }
  } /* sbox */


static void xor( uchar *dst, const uchar *a, const uchar *b, const int count )
  /* ------------------------------------------------------------------------ **
   * Perform an XOR operation on two byte arrays.
   *
   *  Input:  dst   - Destination array to which the result will be written.
   *          a     - The first string of bytes.
   *          b     - The second string of bytes.
   *          count - Number of bytes to XOR against one another.
   *
   *  Output: none.
   *
   *  Notes:  This function operates on whole byte chunks.  There's no need
   *          to XOR partial bytes so no need to write code to handle it.
   *
   *        - This function essentially implements dst = a ^ b; for byte
   *          arrays.
   *
   *        - <dst> may safely point to the same location as <a> or <b>.
   *
   * ------------------------------------------------------------------------ **
   */
  {
  int i;

  for( i = 0; i < count; i++ )
    dst[i] = a[i] ^ b[i];
  } /* xor */


/* -------------------------------------------------------------------------- **
 * Functions:
 */

uchar *auth_DESkey8to7( uchar *dst, const uchar *key )
  /* ------------------------------------------------------------------------ **
   * Compress an 8-byte DES key to its 7-byte form.
   *
   *  Input:  dst - Pointer to a memory location (minimum 7 bytes) to accept
   *                the compressed key.
   *          key - Pointer to an 8-byte DES key.  See the notes below.
   *
   *  Output: A pointer to the compressed key (same as <dst>) or NULL if
   *          either <src> or <dst> were NULL.
   *
   *  Notes:  There are no checks done to ensure that <dst> and <key> point
   *          to sufficient space.  Please be carefull.
   *
   *          The two pointers, <dst> and <key> may point to the same
   *          memory location.  Internally, a temporary buffer is used and
   *          the results are copied back to <dst>.
   *
   *          The DES algorithm uses 8 byte keys by definition.  The first
   *          step in the algorithm, however, involves removing every eigth
   *          bit to produce a 56-bit key (seven bytes).  SMB authentication
   *          skips this step and uses 7-byte keys.  The <auth_DEShash()>
   *          algorithm in this module expects 7-byte keys.  This function
   *          is used to convert an 8-byte DES key into a 7-byte SMB DES key.
   *
   * ------------------------------------------------------------------------ **
   */
  {
  int                  i;
  uchar                tmp[7];
  static const uint8_t map8to7[56] =
    {
     0,  1,  2,  3,  4,  5,  6,
     8,  9, 10, 11, 12, 13, 14,
    16, 17, 18, 19, 20, 21, 22,
    24, 25, 26, 27, 28, 29, 30,
    32, 33, 34, 35, 36, 37, 38,
    40, 41, 42, 43, 44, 45, 46,
    48, 49, 50, 51, 52, 53, 54,
    56, 57, 58, 59, 60, 61, 62
    };

  if( (NULL == dst) || (NULL == key) )
    return( NULL );

  Permute( tmp, key, map8to7, 7 );
  for( i = 0; i < 7; i++ )
    dst[i] = tmp[i];

  return( dst );
  } /* auth_DESkey8to7 */


uchar *auth_DEShash( uchar *dst, const uchar *key, const uchar *src )
  /* ------------------------------------------------------------------------ **
   * DES encryption of the input data using the input key.
   *
   *  Input:  dst - Destination buffer.  It *must* be at least eight bytes
   *                in length, to receive the encrypted result.
   *          key - Encryption key.  Exactly seven bytes will be used.
   *                If your key is shorter, ensure that you pad it to seven
   *                bytes.
   *          src - Source data to be encrypted.  Exactly eight bytes will
   *                be used.  If your source data is shorter, ensure that
   *                you pad it to eight bytes.
   *
   *  Output: A pointer to the encrpyted data (same as <dst>).
   *
   *  Notes:  In SMB, the DES function is used as a hashing function rather
   *          than an encryption/decryption tool.  When used for generating
   *          the LM hash the <src> input is the known value "KGS!@#$%" and
   *          the key is derived from the password entered by the user.
   *          When used to generate the LM or NTLM response, the <key> is
   *          derived from the LM or NTLM hash, and the challenge is used
   *          as the <src> input.
   *          See: http://ubiqx.org/cifs/SMB.html#SMB.8.3
   *
   *        - This function is called "DEShash" rather than just "DES"
   *          because it is only used for creating LM hashes and the
   *          LM/NTLM responses.  For all practical purposes, however, it
   *          is a full DES encryption implementation.
   *
   *        - This DES implementation does not need to be fast, nor is a
   *          DES decryption function needed.  The goal is to keep the
   *          code small, simple, and well documented.
   *
   *        - The input values are copied and refiddled within the module
   *          and the result is not written to <dst> until the very last
   *          step, so it's okay if <dst> points to the same memory as
   *          <key> or <src>.
   *
   * ------------------------------------------------------------------------ **
   */
  {
  int   i;          /* Loop counter.                                */
  uchar K[7];       /* Holds the key, as we manipulate it.          */
  uchar D[8];       /* The data block, as we manipulate it.         */

  /* Create the permutations of the key and the source.
   */
  Permute( K, key, KeyPermuteMap, 7 );
  Permute( D, src, InitialPermuteMap, 8 );

  /* DES encryption proceeds in 16 rounds.
   * The stuff inside the loop is known in the literature as "function f".
   */
  for( i = 0; i < 16; i++ )
    {
    int    j;
    uchar *L = D;           /* The left 4 bytes (half) of the data block.   */
    uchar *R = &(D[4]);     /* The right half of the ciphertext block.      */
    uchar  Rexp[6];         /* Expanded right half.                         */
    uchar  Rn[4];           /* New value of R, as we manipulate it.         */
    uchar  SubK[6];         /* The 48-bit subkey.                           */

    /* Generate the subkey for this round.
     */
    KeyShift( K, KeyRotation[i] );
    Permute( SubK, K, KeyCompression, 6 );

    /* Expand the right half (R) of the data block to 48 bytes,
     * then XOR the result with the Subkey for this round.
     */
    Permute( Rexp, R, DataExpansion, 6 );
    xor( Rexp, Rexp, SubK, 6 );

    /* S-Box substitutions, P-Box permutation, and final XOR.
     * The S-Box substitutions return a 32-bit value, which is then
     * run through the 32-bit to 32-bit P-Box permutation.  The P-Box
     * result is then XOR'd with the left-hand half of the key.
     * (Rexp is used as a temporary variable between the P-Box & XOR).
     */
    sbox( Rn, Rexp );
    Permute( Rexp, Rn, PBox, 4 );
    xor( Rn, L, Rexp, 4 );

    /* The previous R becomes the new L,
     * and Rn is moved into R ready for the next round.
     */
    for( j = 0; j < 4; j++ )
      {
      L[j] = R[j];
      R[j] = Rn[j];
      }
    }

  /* The encryption is complete.
   * Now reverse-permute the ciphertext to produce the final result.
   * We actually combine two steps here.  The penultimate step is to
   * swap the positions of L and R in the result of the 16 rounds,
   * after which the reverse of the Initial Permutation is applied.
   * To save a step, the FinalPermuteMap applies both the L/R swap
   * and the inverse of the Initial Permutation.
   */
  Permute( dst, D, FinalPermuteMap, 8 );
  return( dst );
  } /* auth_DEShash */

/* ========================================================================== */