cbcmodem.nc

传感器网络中的嵌入式操作系统源代码

// $Id: CBCModeM.nc,v 1.1.2.4 2003/08/26 09:08:14 cssharp Exp $

/*									tab:4
 * "Copyright (c) 2000-2003 The Regents of the University  of California.  
 * All rights reserved.
 *
 * Permission to use, copy, modify, and distribute this software and its
 * documentation for any purpose, without fee, and without written agreement is
 * hereby granted, provided that the above copyright notice, the following
 * two paragraphs and the author appear in all copies of this software.
 * 
 * IN NO EVENT SHALL THE UNIVERSITY OF CALIFORNIA BE LIABLE TO ANY PARTY FOR
 * DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES ARISING OUT
 * OF THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN IF THE UNIVERSITY OF
 * CALIFORNIA HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 * 
 * THE UNIVERSITY OF CALIFORNIA SPECIFICALLY DISCLAIMS ANY WARRANTIES,
 * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY
 * AND FITNESS FOR A PARTICULAR PURPOSE.  THE SOFTWARE PROVIDED HEREUNDER IS
 * ON AN "AS IS" BASIS, AND THE UNIVERSITY OF CALIFORNIA HAS NO OBLIGATION TO
 * PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS."
 *
 * Copyright (c) 2002-2003 Intel Corporation
 * All rights reserved.
 *
 * This file is distributed under the terms in the attached INTEL-LICENSE     
 * file. If you do not find these files, copies can be found by writing to
 * Intel Research Berkeley, 2150 Shattuck Avenue, Suite 1300, Berkeley, CA, 
 * 94704.  Attention:  Intel License Inquiry.
 */

/* Authors: Naveen Sastry
 * Date:    9/26/02
 */

/**
 * Implements CBC Mode using Cipher Text Stealing (CBC-CTS) as described in
 * Schneir's Applied Cryptography (195-6) and RFC-2040.
 * <br>
 * Plain CBC mode is pretty simple; using CTS complicates things. CTS allows
 * the ciphertext to be the same size as the plaintext, even for plaintexts
 * which aren't a multiple of the block size.
 *
 *        C_0     == E[IV]
 *        C_i     == E[ C_{i-1} ^ P_i ]                   0 < i < n-2
 *        C_{n-1} == E[ C_{n-2} ^ P_{n-1} ]
 *                == E[ C_{n-2} ^ (P_{n-1} || 0/-L) ]
 *                == C_{n-1}/+L || C_{n-1}/-L    (naming of ciphertext block
 *                                                into left and right pieces)
 *        C_n     == E[ C_{n-1}/+L ^ P_n || C_{n-1}/-L ]
 *
 *  Where 0 = the zero block
 *        n = number of blocks. the last block may be length 1..blockSize bytes
 *        L = |P_n|, the length of the last block and
 *        /+L refers to the first L bytes of a block and
 *        /-L refers to the last (blockSize - L) bytes of a block
 *
 * We then output C_0 || ... || C_{n-2} || C_n || C_{n-1}/+L so that the
 * ciphertext is the same size as the input.
 * @author Naveen Sastry
 */
module CBCModeM {
  provides {
    interface BlockCipherMode;
  }
  uses {
    interface BlockCipher;
    interface BlockCipherInfo;
  }
} 

implementation
{
  enum {
    // we allocate some static buffeers on the stack; they have to be less
    // than this size
    CBCMODE_MAX_BLOCK_SIZE = 8
  };

  // We run a simple state machine in the incremental decrypt:
  //
  //    +--> ONE_BLOCK
  //    |
  // ---|
  //    |
  //    +--> GENERAL --+---> TWO_LEFT_A ----> TWO_LEFT_B
  //            ^      |
  //            |      |
  //            +------+
  enum {
    ONE_BLOCK,
    GENERAL,
    TWO_LEFT_A,
    TWO_LEFT_B
  };
  
  typedef struct CBCModeContext {
    uint8_t spill1 [CBCMODE_MAX_BLOCK_SIZE ];
    uint8_t spill2 [CBCMODE_MAX_BLOCK_SIZE ];
    uint8_t bsize;
    uint16_t remaining; // how many more bytes of ciphertext do we need to recv
    uint16_t completed; // how many bytes of plaintext we've deciphered.
    uint8_t accum;      // TRUE iff spill1 is the accumulator & spill2 holds
                        // prev cipher text. false o.w.
    uint8_t offset;     // into the accumulator
    uint8_t state;      // state enum
  } __attribute__ ((packed)) CBCModeContext;

#define MIN(a, b) ( ((a) < (b)) ? (a) : (b))
  
  /**
   * Initialize the Mode.  It uses the underlying BlockCipher's
   * preferred block cipher mode, and passes the key and keySize parameters
   * to the underlying BlockCipher.
   *
   * @param context structure to hold the opaque data from this initialization
   *        call. It should be passed to future invocations of this module
   *        which use this particular key. It also contains the opaque
   *        context for the underlying BlockCipher as well.
   * @param keySize key size in bytes
   * @param key pointer to the key
   * @return Whether initialization was successful. The command may be
   *         unsuccessful if the key size is not valid for the given cipher
   *         implementation. It can also fail if the preferred block size of
   *         the cipher does not agree with the preferred size of the mode.
   */
  command result_t BlockCipherMode.init(CipherModeContext * context,
                                        uint8_t keySize, uint8_t * key)
    {
      uint8_t blockSize = call BlockCipherInfo.getPreferredBlockSize();
      if (blockSize > CBCMODE_MAX_BLOCK_SIZE) {
        return FAIL;
      }

      ((CBCModeContext*)context->context)->bsize = blockSize;
      return call BlockCipher.init (&context->cc, blockSize, keySize, key);
    }

  void dumpBuffer (char * bufName, uint8_t * buf, uint8_t size)
    {
#ifdef O
      uint8_t i = 0;
      // fixme watch buffer overrun
      char tmp[256];
      for (; i < size; i++) {
        sprintf (tmp + i * 3, "%2x ", (char)buf[i] & 0xff);
      }
      dbg(DBG_CRYPTO, "%s: {%s}\n", bufName, tmp);
#endif
    }

  /**
   * Encrypts numBlocks of plaintext blocks (each of size blockSize) using the
   * key from the init phase. The IV is a pointer to the initialization vector
   * (of size equal to the blockSize) which is used to initialize the
   * encryption.
   *
   * In place encryption should work provided that the plain and and cipher
   * buffer are the same. (they may either be the same or
   * non-overlapping. partial overlaps are not supported).
   *
   * @param plainBlocks a plaintext block numBlocks, where each block is of
   *        blockSize bytes
   * @param cipherBlocks an array of numBlocks * blockSize bytes to hold
   *        the resulting cyphertext
   * @param numBlocks number of data blocks to encrypt
   * @param IV an array of the initialization vector. It should be of
   *        blockSize bytes
   * @return Whether the encryption was successful. Possible failure reasons
   *        include not calling init(). 
   */
  async command result_t BlockCipherMode.encrypt(CipherModeContext * context,
						 uint8_t * plainBlocks,
						 uint8_t * cipherBlocks,
						 uint16_t numBytes, uint8_t * IV)
    {
      uint8_t i,j, t, bsize, bsize2;
      uint16_t bc = 0;
      uint8_t spillblock[CBCMODE_MAX_BLOCK_SIZE];
      uint8_t eIV[CBCMODE_MAX_BLOCK_SIZE];

      bsize = ((CBCModeContext*) (context->context))->bsize;
      bsize2 = bsize + bsize;
      if (numBytes == 0) {
        return SUCCESS;
      }
      // we can only encrypt 256 blocks (since our block counter is a byte
      // [quicker to maintain an 8 bit counter than a 16 bit counter]_
      if ((numBytes / 256) > bsize) {
        return FAIL;
      }
      // we need at least 1 block size to work with.
      if (numBytes < bsize) {
        return FAIL;
      }
      dumpBuffer ("CBC.encrypt orig", plainBlocks, numBytes);

      if (call BlockCipher.encrypt (&(context->cc), IV, eIV) == FAIL) {
        return FAIL;
      }
      IV = eIV;
      
      // special case for the 1 byte encryption
      if (numBytes == bsize) {
        // FIXME UNROLL:
        // xor the iv and plaintext and encrypt
        for (j = 0; j < bsize; j++) {
          cipherBlocks[bc+ j] = plainBlocks[bc+j] ^ IV[j];
        }
        if (call BlockCipher.encrypt (&(context->cc), cipherBlocks + bc,
                                      cipherBlocks + bc) == FAIL) {
          return FAIL;
        }
        return SUCCESS;
      }

      // this loop deals with all but the last two blocks 
      // it xors the prev encr (stored in iv) and encrypts
      if (numBytes > bsize2) {       
        for (bc = 0; bc < numBytes - bsize2; bc += bsize) {
          // FIXME UNROLL:
          for (j = 0; j < bsize; j++) {
            cipherBlocks[bc+ j] = plainBlocks[bc+j] ^ IV[j];
          }
          if (call BlockCipher.encrypt (&context->cc, cipherBlocks + bc,
                                        cipherBlocks + bc) == FAIL) {
            return FAIL;
          }
          IV = cipherBlocks + bc;
        }
      }
      
      dbg (DBG_CRYPTO, "bc: %d\n", bc);
      // Now we deal with the last two blocks. The very last block may not be
      // full, so we use a technique called ciphertext stealing to deal with
      // it.
      //
      // We encrypt the second to last block as normal. Call the ciphertext
      // C_{n-1}. We do not output this ciphertext.  We then xor the last
      // partial block with C_{n-1} (of size m) and encrypt it to obtain
      // C_n. The ciphertext C_n is output in place of C_{n-1}. And we then
      // only need to output the first m bytes of C_{n-1}.
      //
      // How does this work? Well to decrypt, it is easy to obtain
      // C_{n-1} ^ p_n (the decryption of C_{n-1} yields this). xoring the
      // first m bytes of C_{n-1} yields p_n, and hence the complete C_{n-1}. 

      // start by generating C_{n-1} -- xor with the prev IV and encrypt.
      for (j = 0; j < bsize; j++) {
        spillblock[j] = plainBlocks[bc+ j] ^ IV[j];
      }
      if (call BlockCipher.encrypt(&context->cc, spillblock, spillblock) ==
          FAIL) {
          return FAIL;
      }
      dumpBuffer ("CBC.encrypt spill:", spillblock, bsize);
      
      j = numBytes - bc - bsize;
      dbg(DBG_CRYPTO, "CBC.encrypt j: %d; bc: %d\n", j, bc);

      // xor and output the first m bytes of C_{n-1}
      for (i = 0 ; i < j; i++) {
        // we do this in a convoluted manner to avoid alias problmes:
        //       if cipherBlock = plainblock
        t = plainBlocks[bc + bsize + i];
        cipherBlocks[bc + bsize +i] = spillblock[i];
        spillblock[i] ^= t;
      }
      // and encrypt -- note that the output of the encryption places the last
      // ciphertext in the correct position -- where the C_{n-1} would
      // ordinarily go. 
      if (call BlockCipher.encrypt(&context->cc, spillblock,
                                   cipherBlocks + bc) == FAIL) {
        return FAIL;
      }
      dumpBuffer( "CBC.encrypt cipher:", cipherBlocks, numBytes);
      return SUCCESS;
    }

  /**
   * Decrypts numBlocks of ciphertext blocks (each of size blockSize) using the
   * key from the init phase. The IV is a pointer to the initialization vector
   * (of size equal to the blockSize) which is used to initialize the
   * decryption.
   *
   * In place decryption should work provided that the plain and and cipher
   * buffer are the same. (they may either be the same or
   * non-overlapping. partial overlaps are not supported).
   *
   * @param cipherBlocks an array of numBlocks * blockSize bytes that holds
   *        the cipher text
   * @param plainBlocks an array of numBlocks * blockSize bytes to hold the
   *        resulting plaintext.
   * @param numBlocks number of data blocks to encrypt
   * @param IV an array of the initialization vector. It should be of
   *        blockSize bytes
   * @return Whether the decryption was successful. Possible failure reasons
   *        include not calling init(). 
   */
  async command result_t BlockCipherMode.decrypt(CipherModeContext * context,
						 uint8_t * cipherBlock,
						 uint8_t * plainBlock,
						 uint16_t numBytes, uint8_t * IV)
    {
      uint8_t i = 0, partialSize = 0,
        bsize = ((CBCModeContext*)context->context)->bsize;
      uint16_t bc = 0;
      uint8_t spillblock[CBCMODE_MAX_BLOCK_SIZE];
      uint8_t spillblock2[CBCMODE_MAX_BLOCK_SIZE];
      uint8_t eIV[CBCMODE_MAX_BLOCK_SIZE];
      
      if (numBytes == 0) {
        return SUCCESS;
      }
      // we need at least one block size to deal with.
      if (numBytes < bsize) {
        return FAIL;
      }

      if (call BlockCipher.encrypt (&context->cc, IV, eIV) != SUCCESS) {
        return FAIL;
      }
      IV = eIV;
      
      // deal with the single block case a bit specially: encrypt and xor it
      // and move on.
      if (numBytes == bsize) {
        if (call BlockCipher.decrypt (&context->cc,
                                      cipherBlock, plainBlock) != SUCCESS) {
          return FAIL;
        }
        for (i = 0; i < bsize; i++ ) {
          plainBlock[i] ^= IV[i];
        }