home *** CD-ROM | disk | FTP | other *** search
/ Unix System Administration Handbook 1997 October / usah_oct97.iso / rfc / 2000s / rfc2040.txt < prev    next >
Text File  |  1996-10-27  |  55KB  |  1,628 lines
  1.  
  2.  
  3.  
  4.  
  5.  
  6.  
  7. Network Working Group                                         R. Baldwin
  8. Request for Comments: 2040                       RSA Data Security, Inc.
  9. Category: Informational                                        R. Rivest
  10.                                      MIT Laboratory for Computer Science
  11.                                              and RSA Data Security, Inc.
  12.                                                             October 1996
  13.  
  14.  
  15.          The RC5, RC5-CBC, RC5-CBC-Pad, and RC5-CTS Algorithms
  16.  
  17. Status of this Memo
  18.  
  19.    This memo provides information for the Internet community.  This memo
  20.    does not specify an Internet standard of any kind.  Distribution of
  21.    this memo is unlimited.
  22.  
  23. Acknowledgments
  24.  
  25.    We would like to thank Steve Dusse, Victor Chang, Tim Mathews, Brett
  26.    Howard, and Burt Kaliski for helpful suggestions.
  27.  
  28. Table of Contents
  29.  
  30.      1.        Executive Summary .......................  1
  31.      2.        Overview ................................  2
  32.      3.        Terminology and Notation ................  3
  33.      4.        Description of RC5 Keys .................  4
  34.      5.        Description of RC5 Key Expansion ........  6
  35.      6.        Description of RC5 Block Cipher ......... 10
  36.      7.        Description of RC5-CBC and RC5-CBC-Pad .. 12
  37.      8.        Description of RC5-CTS .................. 18
  38.      9.        Test Program and Vectors ................ 19
  39.      10.       Security Considerations ................. 26
  40.      11.       ASN.1 Identifiers ....................... 28
  41.      References ........................................ 28
  42.      Authors' Addresses ................................ 29
  43.  
  44. 1.  Executive Summary
  45.  
  46.    This document defines four ciphers with enough detail to ensure
  47.    interoperability between different implementations.  The first cipher
  48.    is the raw RC5 block cipher.  The RC5 cipher takes a fixed size input
  49.    block and produces a fixed sized output block using a transformation
  50.    that depends on a key.  The second cipher, RC5-CBC, is the Cipher
  51.    Block Chaining (CBC) mode for RC5.  It can process messages whose
  52.    length is a multiple of the RC5 block size.  The third cipher, RC5-
  53.    CBC-Pad, handles plaintext of any length, though the ciphertext will
  54.    be longer than the plaintext by at most the size of a single RC5
  55.  
  56.  
  57.  
  58. Baldwin & Rivest             Informational                      [Page 1]
  59.  
  60. RFC 2040         RC5, RC5-CBC, RC5-CBC-Pad, and RC5-CTS     October 1996
  61.  
  62.  
  63.    block.  The RC5-CTS cipher is the Cipher Text Stealing mode of RC5,
  64.    which handles plaintext of any length and the ciphertext length
  65.    matches the plaintext length.
  66.  
  67.    The RC5 cipher was invented by Professor Ronald L. Rivest of the
  68.    Massachusetts Institute of Technology in 1994.  It is a very fast and
  69.    simple algorithm that is parameterized by the block size, the number
  70.    of rounds, and key length.  These parameters can be adjusted to meet
  71.    different goals for security, performance, and exportability.
  72.  
  73.    RSA Data Security Incorporated has filed a patent application on the
  74.    RC5 cipher and for trademark protection for RC5, RC5-CBC, RC5-CBC-
  75.    Pad, RC5-CTS and assorted variations.
  76.  
  77. 2.  Overview
  78.  
  79.    This memo is a restatement of existing published material.  The
  80.    description of RC5 follows the notation and order of explanation
  81.    found in the original RC5 paper by Professor Rivest [2].  The CBC
  82.    mode appears in reference works such as the one by Bruce Schneier
  83.    [6].  The CBC-Pad mode is the same as in the Public Key Cryptography
  84.    Standard (PKCS) number five [5].  Sample C code [8] is included for
  85.    clarity only and is equivalent to the English language descriptions.
  86.  
  87.    The ciphers will be explained in a bottom up object-oriented fashion.
  88.    First, RC5 keys will be presented along with the key expansion
  89.    algorithm.  Second, the RC5 block cipher is explained, and finally,
  90.    the RC5-CBC and RC5-CBC-Pad ciphers are specified.  For brevity, only
  91.    the encryption process is described.  Decryption is achieved by
  92.    inverting the steps of encryption.
  93.  
  94.    The object-oriented description found here should make it easier to
  95.    implement interoperable systems, though it is not as terse as the
  96.    functional descriptions found in the references.  There are two
  97.    classes of objects, keys and cipher algorithms.  Both classes share
  98.    operations that create and destroy these objects in a manner that
  99.    ensures that secret information is not returned to the memory
  100.    manager.
  101.  
  102.    Keys also have a "set" operation that copies a secret key into the
  103.    object.  The "set" operation for the cipher objects defines the
  104.    number of rounds, and the initialization vector.
  105.  
  106.    There are four operations for the cipher objects described in this
  107.    memo.  There is binding a key to a cipher object, setting a new
  108.    initialization vector for a cipher object without changing the key,
  109.    encrypting part of a message (this would be performed multiple times
  110.    for long messages), and processing the last part of a message which
  111.  
  112.  
  113.  
  114. Baldwin & Rivest             Informational                      [Page 2]
  115.  
  116. RFC 2040         RC5, RC5-CBC, RC5-CBC-Pad, and RC5-CTS     October 1996
  117.  
  118.  
  119.    may add padding or check the length of the message.
  120.  
  121.    In summary, the cipher will be explained in terms of these
  122.    operations:
  123.  
  124.    RC5_Key_Create           - Create a key object.
  125.  
  126.    RC5_Key_Destroy          - Destroy a key object.
  127.  
  128.    RC5_Key_Set              - Bind a user key to a key object.
  129.  
  130.    RC5_CBC_Create           - Create a cipher object.
  131.  
  132.    RC5_CBC_Destroy          - Destroy a cipher object.
  133.  
  134.    RC5_CBC_Encrypt_Init     - Bind a key object to a cipher object.
  135.  
  136.    RC5_CBC_SetIV            - Set a new IV without changing the key.
  137.  
  138.    RC5_CBC_Encrypt_Update   - Process part of a message.
  139.  
  140.    RC5_CBC_Encrypt_Final    - Process the end of a message.
  141.  
  142. 3.  Terminology and Notation
  143.  
  144.    The term "word" refers to a string of bits of a particular length
  145.    that can be operated on as either an unsigned integer or as a bit
  146.    vector.  For example a "word" might be 32 or 64 bits long depending
  147.    on the desired block size for the RC5 cipher.  A 32 bit word will
  148.    produce a 64 bit block size.  For best performance the RC5 word size
  149.    should match the register size of the CPU.  The term "byte" refers to
  150.    eight bits.
  151.  
  152.    The following variables will be used throughout this memo with these
  153.    meanings:
  154.  
  155.   W  This is the word size for RC5 measured in bits.  It is half the
  156.       block size.  The word sizes covered by this memo are 32 and 64.
  157.  
  158.   WW This is the word size for RC5 measured in bytes.
  159.  
  160.   B  This is the block size for RC5 measured in bits.  It is twice
  161.       the word size.  When RC5 is used as a 64 bit block cipher, B is
  162.       64 and W is 32. 0 < B < 257.  In the sample code, B, is used as
  163.       a variable instead of a cipher system parameter, but this usage
  164.       should be obvious from context.
  165.  
  166.   BB This is the block size for RC5 measured in bytes.  BB = B / 8.
  167.  
  168.  
  169.  
  170. Baldwin & Rivest             Informational                      [Page 3]
  171.  
  172. RFC 2040         RC5, RC5-CBC, RC5-CBC-Pad, and RC5-CTS     October 1996
  173.  
  174.  
  175.   b  This is the byte length of the secret key.  0 <= b < 256.
  176.  
  177.   K  This is the secret key which is treated as a sequence of b
  178.       bytes indexed by: K[0], ..., K[b-1].
  179.  
  180.   R  This is the number of rounds of the inner RC5 transform.
  181.       0 <= R < 256.
  182.  
  183.   T  This is the number of words in the expanded key table.  It is
  184.       always 2*(R + 1).  1 < T < 513.
  185.  
  186.   S  This is the expanded key table which is treated as a sequence
  187.       of words indexed by: S[0], ..., S[T-1].
  188.  
  189.   N  This is the byte length of the plaintext message.
  190.  
  191.   P  This is the plaintext message which is treated as a sequence of
  192.       N bytes indexed by: P[0], ..., P[N-1].
  193.  
  194.   C  This is the ciphertext output which is treated as a sequence of
  195.       bytes indexed by: C[0], C[1], ...
  196.  
  197.   I  This is the initialization vector for the CBC mode which is
  198.       treated as a sequence of bytes indexed by: I[0], ..., I[BB-1].
  199.  
  200. 4.  Description of RC5 Keys
  201.  
  202.    Like most block ciphers, RC5 expands a small user key into a table of
  203.    internal keys.  The byte length of the user key is one of the
  204.    parameters of the cipher, so the RC5 user key object must be able to
  205.    hold variable length keys.  A possible structure for this in C is:
  206.  
  207.   /* Definition of RC5 user key object. */
  208.   typedef struct rc5UserKey
  209.   {
  210.     int          keyLength; /* In Bytes. */
  211.     unsigned char   *keyBytes;
  212.   } rc5UserKey;
  213.  
  214.    The basic operations on a key are to create, destroy and set.  To
  215.    avoid exposing key material to other parts of an application, the
  216.    destroy operation zeros the memory allocated for the key before
  217.    releasing it to the memory manager.  A general key object may support
  218.    other operations such as generating a new random key and deriving a
  219.    key from key-agreement information.
  220.  
  221.  
  222.  
  223.  
  224.  
  225.  
  226. Baldwin & Rivest             Informational                      [Page 4]
  227.  
  228. RFC 2040         RC5, RC5-CBC, RC5-CBC-Pad, and RC5-CTS     October 1996
  229.  
  230.  
  231. 4.1 Creating an RC5 Key
  232.  
  233.    To create a key, the memory for the key object must be allocated and
  234.    initialized.  The C code below assumes that a function called
  235.    "malloc" will return a block of uninitialized memory from the heap,
  236.    or zero indicating an error.
  237.  
  238.   /* Allocate and initialize an RC5 user key.
  239.    * Return 0 if problems.
  240.    */
  241.   rc5UserKey *RC5_Key_Create ()
  242.   {
  243.     rc5UserKey *pKey;
  244.  
  245.     pKey = (rc5UserKey *) malloc (sizeof(*pKey));
  246.     if (pKey != ((rc5UserKey *) 0))
  247.     {
  248.         pKey->keyLength = 0;
  249.         pKey->keyBytes = (unsigned char *) 0;
  250.     }
  251.     return (pKey);
  252.   }
  253.  
  254. 4.2 Destroying an RC5 Key
  255.  
  256.    To destroy a key, the memory must be zeroed and released to the
  257.    memory manager.  The C code below assumes that a function called
  258.    "free" will return a block of memory to the heap.
  259.  
  260.   /* Zero and free an RC5 user key.
  261.    */
  262.   void RC5_Key_Destroy (pKey)
  263.     rc5UserKey      *pKey;
  264.   {
  265.     unsigned char   *to;
  266.     int          count;
  267.  
  268.     if (pKey == ((rc5UserKey *) 0))
  269.         return;
  270.     if (pKey->keyBytes == ((unsigned char *) 0))
  271.         return;
  272.     to = pKey->keyBytes;
  273.     for (count = 0 ; count < pKey->keyLength ; count++)
  274.         *to++ = (unsigned char) 0;
  275.     free (pKey->keyBytes);
  276.     pKey->keyBytes = (unsigned char *) 0;
  277.     pKey->keyLength = 0;
  278.     free (pKey);
  279.  
  280.  
  281.  
  282. Baldwin & Rivest             Informational                      [Page 5]
  283.  
  284. RFC 2040         RC5, RC5-CBC, RC5-CBC-Pad, and RC5-CTS     October 1996
  285.  
  286.  
  287.   }
  288.  
  289. 4.3 Setting an RC5 Key
  290.  
  291.    Setting the key object makes a copy of the secret key into a block of
  292.    memory allocated from the heap.
  293.  
  294.   /* Set the value of an RC5 user key.
  295.    * Copy the key bytes so the caller can zero and
  296.    * free the original.
  297.    * Return zero if problems
  298.    */
  299.   int RC5_Key_Set (pKey, keyLength, keyBytes)
  300.     rc5UserKey  *pKey;
  301.     int          keyLength;
  302.     unsigned char   *keyBytes;
  303.   {
  304.     unsigned char   *keyBytesCopy;
  305.     unsigned char   *from, *to;
  306.     int          count;
  307.  
  308.     keyBytesCopy = (unsigned char *) malloc (keyLength);
  309.     if (keyBytesCopy == ((unsigned char *) 0))
  310.         return (0);
  311.     from = keyBytes;
  312.     to = keyBytesCopy;
  313.     for (count = 0 ; count < keyLength ; count++)
  314.         *to++ = *from++;
  315.     pKey->keyLength = count;
  316.     pKey->keyBytes = keyBytesCopy;
  317.     return (1);
  318.   }
  319.  
  320. 5.  Description of RC5 Key Expansion
  321.  
  322.    This section describes the key expansion algorithm.  To be specific,
  323.    the sample code assumes that the block size is 64 bits.  Several
  324.    programming parameters depend on the block size.
  325.  
  326.   /* Definitions for RC5 as a 64 bit block cipher. */
  327.   /* The "unsigned int" will be 32 bits on all but */
  328.   /* the oldest compilers, which will make it 16 bits. */
  329.   /* On a DEC Alpha "unsigned long" is 64 bits, not 32. */
  330.   #define RC5_WORD     unsigned int
  331.   #define W            (32)
  332.   #define WW           (W / 8)
  333.   #define ROT_MASK     (W - 1)
  334.   #define BB           ((2 * W) / 8) /* Bytes per block */
  335.  
  336.  
  337.  
  338. Baldwin & Rivest             Informational                      [Page 6]
  339.  
  340. RFC 2040         RC5, RC5-CBC, RC5-CBC-Pad, and RC5-CTS     October 1996
  341.  
  342.  
  343.   /* Define macros used in multiple procedures. */
  344.   /* These macros assumes ">>" is an unsigned operation, */
  345.   /* and that x and s are of type RC5_WORD. */
  346.   #define SHL(x,s)    ((RC5_WORD)((x)<<((s)&ROT_MASK)))
  347.   #define SHR(x,s,w)  ((RC5_WORD)((x)>>((w)-((s)&ROT_MASK))))
  348.   #define ROTL(x,s,w) ((RC5_WORD)(SHL((x),(s))|SHR((x),(s),(w))))
  349.  
  350. 5.1 Definition of initialization constants
  351.  
  352.    Two constants, Pw and Qw, are defined for any word size W by the
  353.    expressions:
  354.  
  355.         Pw = Odd((e-2)*2**W)
  356.  
  357.         Qw = Odd((phi-1)*2**W)
  358.  
  359.    where e is the base of the natural logarithm (2.71828 ...), and phi
  360.    is the golden ratio (1.61803 ...), and 2**W is 2 raised to the power
  361.    of W, and Odd(x) is equal to x if x is odd, or equal to x plus one if
  362.    x is even.  For W equal to 16, 32, and 64, the Pw and Qw constants
  363.    are the following hexadecimal values:
  364.  
  365.   #define P16  0xb7e1
  366.   #define Q16  0x9e37
  367.   #define P32  0xb7e15163
  368.   #define Q32  0x9e3779b9
  369.   #define P64  0xb7e151628aed2a6b
  370.   #define Q64  0x9e3779b97f4a7c15
  371.   #if W == 16
  372.   #define Pw   P16 /* Select 16 bit word size */
  373.   #define Qw   Q16
  374.   #endif
  375.   #if W == 32
  376.   #define Pw   P32 /* Select 32 bit word size */
  377.   #define Qw   Q32
  378.   #endif
  379.   #if W == 64
  380.   #define Pw   P64 /* Select 64 bit word size */
  381.   #define Qw   Q64
  382.   #endif
  383.  
  384.  
  385.  
  386.  
  387.  
  388.  
  389.  
  390.  
  391.  
  392.  
  393.  
  394. Baldwin & Rivest             Informational                      [Page 7]
  395.  
  396. RFC 2040         RC5, RC5-CBC, RC5-CBC-Pad, and RC5-CTS     October 1996
  397.  
  398.  
  399. 5.2 Interface definition
  400.  
  401.    The key expansion routine converts the b-byte secret key, K, into an
  402.    expanded key, S, which is a sequence of T = 2*(R+1) words.  The
  403.    expansion algorithm uses two constants that are derived from the
  404.    constants, e, and phi.  These are used to initialize S, which is then
  405.    modified using K.  A C code procedure header for this routine could
  406.    be:
  407.  
  408.   /* Expand an RC5 user key.
  409.    */
  410.   void RC5_Key_Expand (b, K, R, S)
  411.     int      b; /* Byte length of secret key */
  412.     char        *K; /* Secret key */
  413.     int      R; /* Number of rounds */
  414.     RC5_WORD *S;    /* Expanded key buffer, 2*(R+1) words */
  415.   {
  416.  
  417. 5.3 Convert secret key from bytes to words
  418.  
  419.    This step converts the b-byte key into a sequence of words stored in
  420.    the array L.  On a little-endian processor this is accomplished by
  421.    zeroing the L array and copying in the b bytes of K.  The following C
  422.    code will achieve this effect on all processors:
  423.  
  424.     int i, j, k, LL, t, T;
  425.     RC5_WORD    L[256/WW];  /* Based on max key size */
  426.     RC5_WORD    A, B;
  427.  
  428.     /* LL is number of elements used in L. */
  429.     LL = (b + WW - 1) / WW;
  430.     for (i = 0 ; i < LL ; i++)  {
  431.         L[i] = 0;
  432.     }
  433.     for (i = 0 ; i < b ; i++)  {
  434.         t = (K[i] & 0xFF) << (8*(i%4)); /* 0, 8, 16, 24*/
  435.         L[i/WW] = L[i/WW] + t;
  436.     }
  437.  
  438. 5.4 Initialize the expanded key table
  439.  
  440.    This step fills in the S table with a fixed (key independent)
  441.    pseudo-random pattern using an arithmetic progression based on Pw and
  442.    Qw modulo 2**W.  The element S[i] equals i*Qw + Pw modulo 2**W.  This
  443.    table could be precomputed and copied as needed or computed on the
  444.    fly.  In C code it can be computed by:
  445.  
  446.  
  447.  
  448.  
  449.  
  450. Baldwin & Rivest             Informational                      [Page 8]
  451.  
  452. RFC 2040         RC5, RC5-CBC, RC5-CBC-Pad, and RC5-CTS     October 1996
  453.  
  454.  
  455.     T = 2*(R+1);
  456.     S[0] = Pw;
  457.     for (i = 1 ; i < T ; i++)  {
  458.         S[i] = S[i-1] + Qw;
  459.     }
  460.  
  461. 5.5 Mix in the secret key
  462.  
  463.    This step mixes the secret key, K, into the expanded key, S.  First
  464.    the number of iterations of the mixing function, k, is set to three
  465.    times the maximum of the number of initialized elements of L, called
  466.    LL, and the number of elements in S, called T.  Each iteration is
  467.    similar to an interation of the encryption inner loop in that two
  468.    variables A and B are updated by the first and second halves of the
  469.    iteration.
  470.  
  471.    Initially A and B are zero as are the indexes into the S array, i,
  472.    and the L array, j.  In the first half of the iteration, a partial
  473.    result is computed by summing S[i], A and B.  The new value for A is
  474.    this partial result rotated left three bits.  The A value is then
  475.    placed into S[i].  The second half of the iteration computes a second
  476.    partial result that is the sum of L[j], A and B.  The second partial
  477.    result is then rotated left by A+B bit positions and set to be the
  478.    new value for B.  The new B value is then placed into L[j].  At the
  479.    end of the iteration, i and j are incremented modulo the size of
  480.    their respective arrays.  In C code:
  481.  
  482.     i = j = 0;
  483.     A = B = 0;
  484.     if (LL > T)
  485.         k = 3 * LL; /* Secret key len > expanded key. */
  486.     else
  487.         k = 3 * T;  /* Secret key len < expanded key. */
  488.     for ( ; k > 0 ; k--)  {
  489.         A = ROTL(S[i] + A + B, 3, W);
  490.         S[i] = A;
  491.         B = ROTL(L[j] + A + B, A + B, W);
  492.         L[j] = B;
  493.         i = (i + 1) % T;
  494.         j = (j + 1) % LL;
  495.     }
  496.     return;
  497.   } /* End of RC5_Key_Expand */
  498.  
  499.  
  500.  
  501.  
  502.  
  503.  
  504.  
  505.  
  506. Baldwin & Rivest             Informational                      [Page 9]
  507.  
  508. RFC 2040         RC5, RC5-CBC, RC5-CBC-Pad, and RC5-CTS     October 1996
  509.  
  510.  
  511. 6.  Description of RC5 Block Cipher
  512.  
  513.    This section describes the RC5 block cipher by explaining the steps
  514.    required to perform an encryption of a single input block.  The
  515.    decryption process is the reverse of these steps so it will not be
  516.    explained.  The RC5 cipher is parameterized by a version number, V, a
  517.    round count, R, and a word size in bits, W.  This description
  518.    corresponds to original version of RC5 (V = 16 decimal) and covers
  519.    any positive value for R and the values 16, 32, and 64 for W.
  520.  
  521.    The inputs to this process are the expanded key table, S, the number
  522.    of rounds, R, the input buffer pointer, in, and the output buffer
  523.    pointer, out.  A possible C code procedure header for this would be:
  524.  
  525.   void RC5_Block_Encrypt (S, R, in, out)
  526.     RC5_WORD    *S;
  527.     int  R;
  528.     char    *in;
  529.     char    *out;
  530.   {
  531.  
  532. 6.1 Loading A and B values
  533.  
  534.    This step converts input bytes into two unsigned integers called A
  535.    and B.  When RC5 is used as a 64 bit block cipher A and B are 32 bit
  536.    values.  The first input byte becomes the least significant byte of
  537.    A, the fourth input byte becomes the most significant byte of A, the
  538.    fifth input byte becomes the least significant byte of B and the last
  539.    input byte becomes the most significant byte of B.  This conversion
  540.    can be very efficient for little-endian processors such as the Intel
  541.    family.  In C code this could be expressed as:
  542.  
  543.     int  i;
  544.     RC5_WORD    A, B;
  545.  
  546.     A  =  in[0] & 0xFF;
  547.     A += (in[1] & 0xFF) << 8;
  548.     A += (in[2] & 0xFF) << 16;
  549.     A += (in[3] & 0xFF) << 24;
  550.     B  =  in[4] & 0xFF;
  551.     B += (in[5] & 0xFF) << 8;
  552.     B += (in[6] & 0xFF) << 16;
  553.     B += (in[7] & 0xFF) << 24;
  554.  
  555.  
  556.  
  557.  
  558.  
  559.  
  560.  
  561.  
  562. Baldwin & Rivest             Informational                     [Page 10]
  563.  
  564. RFC 2040         RC5, RC5-CBC, RC5-CBC-Pad, and RC5-CTS     October 1996
  565.  
  566.  
  567. 6.2 Iterating the round function
  568.  
  569.    This step mixes the expanded key with the input to perform the
  570.    fundamental encryption operation.  The first two words of the
  571.    expanded key are added to A and B respectively, and then the round
  572.    function is repeated R times.
  573.  
  574.    The first half of the round function computes a new value for A based
  575.    on the values of A, B, and the next unused word in the expanded key
  576.    table.  Specifically, A is XOR'ed with B and then this first partial
  577.    result is rotated to the left by an amount specified by B to form the
  578.    second partial result.  The rotation is performed on a W bit boundary
  579.    (i.e., 32 bit rotation for the version of RC5 that has a 64 bit block
  580.    size).  The actual rotation amount only depends on the least
  581.    significant log base-2 of W bits of B.  The next unused word of the
  582.    expanded key table is then added to the second partial result and
  583.    this becomes the new value for A.
  584.  
  585.    The second half of the round function is identical except the roles
  586.    of A and B are switched. Specifically, B is exclusive or'ed with A
  587.    and then this first partial result is rotated to the left by an
  588.    amount specified by A to form the second partial result.  The next
  589.    unused word of the expanded key table is then added to the second
  590.    partial result and this becomes the new value for B.
  591.  
  592.    One way to express this in C code is:
  593.  
  594.     A = A + S[0];
  595.     B = B + S[1];
  596.     for (i = 1 ; i <= R ; i++) {
  597.         A = A ^ B;
  598.         A = ROTL(A, B, W) + S[2*i];
  599.         B = B ^ A;
  600.         B = ROTL(B, A, W) + S[(2*i)+1];
  601.     }
  602.  
  603. 6.3 Storing the A and B values
  604.  
  605.    The final step is to convert A and B back into a sequence of bytes.
  606.    This is the inverse of the load operation.  An expression of this in
  607.    C code could be:
  608.  
  609.     out[0] = (A >>  0) & 0xFF;
  610.     out[1] = (A >>  8) & 0xFF;
  611.     out[2] = (A >> 16) & 0xFF;
  612.     out[3] = (A >> 24) & 0xFF;
  613.     out[4] = (B >>  0) & 0xFF;
  614.     out[5] = (B >>  8) & 0xFF;
  615.  
  616.  
  617.  
  618. Baldwin & Rivest             Informational                     [Page 11]
  619.  
  620. RFC 2040         RC5, RC5-CBC, RC5-CBC-Pad, and RC5-CTS     October 1996
  621.  
  622.  
  623.     out[6] = (B >> 16) & 0xFF;
  624.     out[7] = (B >> 24) & 0xFF;
  625.     return;
  626.   } /* End of RC5_Block_Encrypt */
  627.  
  628. 7.  Description of RC5-CBC and RC5-CBC-Pad
  629.  
  630.    This section describes the CBC and CBC-Pad modes of the RC5 cipher.
  631.    This description is based on the RC5 key objects and RC5 block cipher
  632.    described earlier.
  633.  
  634. 7.1 Creating cipher objects
  635.  
  636.    The cipher object needs to keep track of the padding mode, the number
  637.    of rounds, the expanded key, the initialization vector, the CBC
  638.    chaining block, and an input buffer.  A possible structure definition
  639.    for this in C code would be:
  640.  
  641.   /* Definition of the RC5 CBC algorithm object.
  642.    */
  643.   typedef struct rc5CBCAlg
  644.   {
  645.     int          Pad;   /* 1 = RC5-CBC-Pad, 0 = RC5-CBC. */
  646.     int          R;     /* Number of rounds. */
  647.     RC5_WORD        *S;     /* Expanded key. */
  648.     unsigned char    I[BB]; /* Initialization vector. */
  649.     unsigned char    chainBlock[BB];
  650.     unsigned char    inputBlock[BB];
  651.     int          inputBlockIndex; /* Next inputBlock byte. */
  652.   } rc5CBCAlg;
  653.  
  654.    To create a cipher algorithm object, the parameters must be checked
  655.    and then space allocated for the expanded key table.  The expanded
  656.    key is initialized using the method described earlier.  Finally, the
  657.    state variables (padding mode, number of rounds, and the input
  658.    buffer) are set to their initial values.  In C this could be
  659.    accomplished by:
  660.  
  661.   /* Allocate and initialize the RC5 CBC algorithm object.
  662.    * Return 0 if problems.
  663.    */
  664.   rc5CBCAlg *RC5_CBC_Create (Pad, R, Version, bb, I)
  665.     int      Pad;       /* 1 = RC5-CBC-Pad, 0 = RC5-CBC. */
  666.     int      R;         /* Number of rounds. */
  667.     int      Version;   /* RC5 version number. */
  668.     int      bb;        /* Bytes per RC5 block == IV len. */
  669.     char     *I;        /* CBC IV, bb bytes long. */
  670.   {
  671.  
  672.  
  673.  
  674. Baldwin & Rivest             Informational                     [Page 12]
  675.  
  676. RFC 2040         RC5, RC5-CBC, RC5-CBC-Pad, and RC5-CTS     October 1996
  677.  
  678.  
  679.     rc5CBCAlg    *pAlg;
  680.     int           index;
  681.  
  682.     if ((Version != RC5_FIRST_VERSION) ||
  683.         (bb != BB) ||   (R < 0) || (255 < R))
  684.         return ((rc5CBCAlg *) 0);
  685.     pAlg = (rc5CBCAlg *) malloc (sizeof(*pAlg));
  686.     if (pAlg == ((rc5CBCAlg *) 0))
  687.         return ((rc5CBCAlg *) 0);
  688.     pAlg->S = (RC5_WORD *) malloc (BB * (R + 1));
  689.     if (pAlg->S == ((RC5_WORD *) 0))    {
  690.         free (pAlg);
  691.         return ((rc5CBCAlg *) 0);
  692.     }
  693.     pAlg->Pad = Pad;
  694.     pAlg->R = R;
  695.     pAlg->inputBlockIndex = 0;
  696.     for (index = 0 ; index < BB ; index++)
  697.         pAlg->I[index] = I[index];
  698.     return (pAlg);
  699.   }
  700.  
  701. 7.2 Destroying cipher objects
  702.  
  703.    Destroying the cipher object is the inverse of creating it with care
  704.    being take to zero memory before returning it to the memory manager.
  705.    In C this could be accomplished by:
  706.  
  707.   /* Zero and free an RC5 algorithm object.
  708.    */
  709.   void RC5_CBC_Destroy (pAlg)
  710.     rc5CBCAlg   *pAlg;
  711.   {
  712.     RC5_WORD    *to;
  713.     int      count;
  714.  
  715.     if (pAlg == ((rc5CBCAlg *) 0))
  716.         return;
  717.     if (pAlg->S == ((RC5_WORD *) 0))
  718.         return;
  719.     to = pAlg->S;
  720.     for (count = 0 ; count < (1 + pAlg->R) ; count++)
  721.     {
  722.         *to++ = 0;  /* Two expanded key words per round. */
  723.         *to++ = 0;
  724.     }
  725.    free (pAlg->S);
  726.     for (count = 0 ; count < BB ; count++)
  727.  
  728.  
  729.  
  730. Baldwin & Rivest             Informational                     [Page 13]
  731.  
  732. RFC 2040         RC5, RC5-CBC, RC5-CBC-Pad, and RC5-CTS     October 1996
  733.  
  734.  
  735.     {
  736.         pAlg->I[count] = (unsigned char) 0;
  737.         pAlg->inputBlock[count] = (unsigned char) 0;
  738.         pAlg->chainBlock[count] = (unsigned char) 0;
  739.     }
  740.     pAlg->Pad = 0;
  741.     pAlg->R = 0;
  742.     pAlg->inputBlockIndex = 0;
  743.     free (pAlg);
  744.   }
  745.  
  746. 7.3 Setting the IV for cipher objects
  747.  
  748.    For CBC cipher objects, the state of the algorithm depends on the
  749.    expanded key, the CBC chain block, and any internally buffered input.
  750.    Often the same key is used with many messages that each have a unique
  751.    initialization vector.  To avoid the overhead of creating a new
  752.    cipher object, it makes more sense to provide an operation that
  753.    allows the caller to change the initialization vector for an existing
  754.    cipher object.  In C this could be accomplished by the following
  755.    code:
  756.  
  757.   /* Setup a new initialization vector for a CBC operation
  758.    * and reset the CBC object.
  759.    * This can be called after Final without needing to
  760.    * call Init or Create again.
  761.    * Return zero if problems.
  762.    */
  763.   int RC5_CBC_SetIV (pAlg, I)
  764.     rc5CBCAlg   *pAlg;
  765.     char        *I;     /* CBC Initialization vector, BB bytes. */
  766.   {
  767.     int     index;
  768.  
  769.     pAlg->inputBlockIndex = 0;
  770.     for (index = 0 ; index < BB ; index++)
  771.     {
  772.         pAlg->I[index] = pAlg->chainBlock[index] = I[index];
  773.         pAlg->inputBlock[index] = (unsigned char) 0;
  774.     }
  775.     return (1);
  776.   }
  777.  
  778. 7.4 Binding a key to a cipher object
  779.  
  780.    The operation that binds a key to a cipher object performs the key
  781.    expansion.  Key expansion could be an operation on keys, but that
  782.    would not work correctly for ciphers that modify the expanded key as
  783.  
  784.  
  785.  
  786. Baldwin & Rivest             Informational                     [Page 14]
  787.  
  788. RFC 2040         RC5, RC5-CBC, RC5-CBC-Pad, and RC5-CTS     October 1996
  789.  
  790.  
  791.    they operate.  After expanding the key, this operation must
  792.    initialize the CBC chain block from the initialization vector and
  793.    prepare the input buffer to receive the first character.  In C this
  794.    could be done by:
  795.  
  796.   /* Initialize the encryption object with the given key.
  797.    * After this routine, the caller frees the key object.
  798.    * The IV for this CBC object can be changed by calling
  799.    * the SetIV routine.  The only way to change the key is
  800.    * to destroy the CBC object and create a new one.
  801.    * Return zero if problems.
  802.    */
  803.   int RC5_CBC_Encrypt_Init (pAlg, pKey)
  804.     rc5CBCAlg       *pAlg;
  805.     rc5UserKey  *pKey;
  806.   {
  807.     if ((pAlg == ((rc5CBCAlg *) 0)) ||
  808.         (pKey == ((rc5UserKey *) 0)))
  809.         return (0);
  810.     RC5_Key_Expand (Key->keyLength, pKey->keyBytes,
  811.                     pAlg->R, pAlg->S);
  812.     return (RC5_CBC_SetIV(pAlg, pAlg->I));
  813.   }
  814.  
  815. 7.5 Processing part of a message
  816.  
  817.    The encryption process described here uses the Init-Update-Final
  818.    paradigm.  The update operation can be performed on a sequence of
  819.    message parts in order to incrementally produce the ciphertext.
  820.    After the last part is processed, the Final operation is called to
  821.    pick up any plaintext bytes or padding that are buffered inside the
  822.    cipher object.  An appropriate procedure header for this operation
  823.    would be:
  824.  
  825.   /* Encrypt a buffer of plaintext.
  826.    * The plaintext and ciphertext buffers can be the same.
  827.    * The byte len of the ciphertext is put in *pCipherLen.
  828.    * Call this multiple times passing successive
  829.    * parts of a large message.
  830.    * After the last part has been passed to Update,
  831.    * call Final.
  832.    * Return zero if problems like output buffer too small.
  833.    */
  834.   int RC5_CBC_Encrypt_Update (pAlg, N, P,
  835.                               pCipherLen, maxCipherLen, C)
  836.     rc5CBCAlg   *pAlg;      /* Cipher algorithm object. */
  837.     int          N;         /* Byte length of P. */
  838.     char        *P;         /* Plaintext buffer. */
  839.  
  840.  
  841.  
  842. Baldwin & Rivest             Informational                     [Page 15]
  843.  
  844. RFC 2040         RC5, RC5-CBC, RC5-CBC-Pad, and RC5-CTS     October 1996
  845.  
  846.  
  847.     int         *pCipherLen;/* Gets byte len of C. */
  848.     int          maxCipherLen;  /* Size of C. */
  849.     char        *C;         /* Ciphertext buffer. */
  850.   {
  851.  
  852. 7.5.1   Output buffer size check.
  853.  
  854.    The first step of plaintext processing is to make sure that the
  855.    output buffer is big enough hold the ciphertext.  The ciphertext will
  856.    be produced in multiples of the block size and depends on the number
  857.    of plaintext characters passed to this operation plus any characters
  858.    that are in the cipher object's internal buffer.  In C code this
  859.    would be:
  860.  
  861.     int      plainIndex, cipherIndex, j;
  862.  
  863.     /* Check size of the output buffer. */
  864.     if (maxCipherLen < (((pAlg->inputBlockIndex+N)/BB)*BB))
  865.     {
  866.         *pCipherLen = 0;
  867.         return (0);
  868.     }
  869.  
  870. 7.5.2   Divide plaintext into blocks
  871.  
  872.    The next step is to add characters to the internal buffer until a
  873.    full block has been constructed.  When that happens, the buffer
  874.    pointers are reset and the input buffer is exclusive-or'ed (XORed)
  875.    with the CBC chaining block.  The byte order of the chaining block is
  876.    the same as the input block.  For example, the ninth input byte is
  877.    XOR'ed with the first ciphertext byte.  The result is then passed to
  878.    the RC5 block cipher which was described earlier.  To reduce data
  879.    movement and byte alignment problems, the output of RC5 can be
  880.    directly written into the CBC chaining block.  Finally, this output
  881.    is copied to the ciphertext buffer provided by the user.  Before
  882.    returning, the actual size of the ciphertext is passed back to the
  883.    caller.  In C, this step can be performed by:
  884.  
  885.     plainIndex = cipherIndex = 0;
  886.     while (plainIndex < N)
  887.     {
  888.         if (pAlg->inputBlockIndex < BB)
  889.         {
  890.             pAlg->inputBlock[pAlg->inputBlockIndex]
  891.                     = P[plainIndex];
  892.             pAlg->inputBlockIndex++;
  893.             plainIndex++;
  894.         }
  895.  
  896.  
  897.  
  898. Baldwin & Rivest             Informational                     [Page 16]
  899.  
  900. RFC 2040         RC5, RC5-CBC, RC5-CBC-Pad, and RC5-CTS     October 1996
  901.  
  902.  
  903.         if (pAlg->inputBlockIndex == BB)
  904.         {   /* Have a complete input block, process it. */
  905.             pAlg->inputBlockIndex = 0;
  906.             for (j = 0 ; j < BB ; j++)
  907.             {   /* XOR in the chain block. */
  908.                 pAlg->inputBlock[j] = pAlg->inputBlock[j]
  909.                                  ^ pAlg->chainBlock[j];
  910.             }
  911.             RC5_Block_Encrypt(pAlg->S, pAlg->R
  912.                              pAlg->inputBlock,
  913.                              pAlg->chainBlock);
  914.             for (j = 0 ; j < BB ; j++)
  915.             {   /* Output the ciphertext. */
  916.                 C[cipherIndex] = pAlg->chainBlock[j];
  917.                 cipherIndex++;
  918.             }
  919.         }
  920.     }
  921.     *pCipherLen = cipherIndex;
  922.     return (1);
  923.   } /* End of RC5_CBC_Encrypt_Update */
  924.  
  925. 7.6 Final block processing
  926.  
  927.    This step handles the last block of plaintext.  For RC5-CBC, this
  928.    step just performs error checking to ensure that the plaintext length
  929.    was indeed a multiple of the block length.  For RC5-CBC-Pad, padding
  930.    bytes are added to the plaintext.  The pad bytes are all the same and
  931.    are set to a byte that represents the number of bytes of padding.
  932.    For example if there are eight bytes of padding, the bytes will all
  933.    have the hexadecimal value 0x08.  There will be between one and BB
  934.    padding bytes, inclusive.  In C code this would be:
  935.  
  936.   /* Produce the final block of ciphertext including any
  937.    * padding, and then reset the algorithm object.
  938.    * Return zero if problems.
  939.    */
  940.   int RC5_CBC_Encrypt_Final (pAlg, pCipherLen, maxCipherLen, C)
  941.     rc5CBCAlg   *pAlg;
  942.     int         *pCipherLen;    /* Gets byte len of C. */
  943.     int          maxCipherLen;  /* Len of C buffer. */
  944.     char        *C;             /* Ciphertext buffer. */
  945.   {
  946.     int     cipherIndex, j;
  947.     int     padLength;
  948.  
  949.     /* For non-pad mode error if input bytes buffered. */
  950.     *pCipherLen = 0;
  951.  
  952.  
  953.  
  954. Baldwin & Rivest             Informational                     [Page 17]
  955.  
  956. RFC 2040         RC5, RC5-CBC, RC5-CBC-Pad, and RC5-CTS     October 1996
  957.  
  958.  
  959.     if ((pAlg->Pad == 0) && (pAlg->inputBlockIndex != 0))
  960.         return (0);
  961.  
  962.     if (pAlg->Pad == 0)
  963.         return (1);
  964.     if (maxCipherLen < BB)
  965.         return (0);
  966.  
  967.     padLength = BB - pAlg->inputBlockIndex;
  968.     for (j = 0 ; j < padLength ; j++)
  969.     {
  970.         pAlg->inputBlock[pAlg->inputBlockIndex]
  971.                = (unsigned char) padLength;
  972.         pAlg->inputBlockIndex++;
  973.     }
  974.     for (j = 0 ; j < BB ; j++)
  975.     {   /* XOR the chain block into the plaintext block. */
  976.         pAlg->inputBlock[j] = pAlg->inputBlock[j]
  977.                              ^ pAlg->chainBlock[j];
  978.     }
  979.     RC5_Block_Encrypt(pAlg->S, pAlg->R,
  980.                       pAlg->inputBlock, pAlg->chainBlock);
  981.     cipherIndex = 0;
  982.     for (j = 0 ; j < BB ; j++)
  983.     {   /* Output the ciphertext. */
  984.         C[cipherIndex] = pAlg->chainBlock[j];
  985.         cipherIndex++;
  986.     }
  987.     *pCipherLen = cipherIndex;
  988.  
  989.     /* Reset the CBC algorithm object. */
  990.     return (RC5_CBC_SetIV(pAlg, pAlg->I));
  991.   } /* End of RC5_CBC_Encrypt_Final */
  992.  
  993. 8.  Description of RC5-CTS
  994.  
  995.    The Cipher Text Stealing (CTS) mode for block ciphers is described by
  996.    Schneier on pages 195 and 196 of [6].  This mode handles any length
  997.    of plaintext and produces ciphertext whose length matches the
  998.    plaintext length.  The CTS mode behaves like the CBC mode for all but
  999.    the last two blocks of the plaintext.  The following steps describe
  1000.    how to handle the last two portions of the plaintext, called Pn-1 and
  1001.    Pn, where the length of Pn-1 equals the block size, BB, and the
  1002.    length of the last block, Pn, is Ln bytes.  Notice that Ln ranges
  1003.    from 1 to BB, inclusive, so Pn could in fact be a complete block.
  1004.  
  1005.  
  1006.  
  1007.  
  1008.  
  1009.  
  1010. Baldwin & Rivest             Informational                     [Page 18]
  1011.  
  1012. RFC 2040         RC5, RC5-CBC, RC5-CBC-Pad, and RC5-CTS     October 1996
  1013.  
  1014.  
  1015.    1. Exclusive-or Pn-1 with the previous ciphertext
  1016.       block, Cn-2, to create Xn-1.
  1017.  
  1018.    2. Encrypt Xn-1 to create En-1.
  1019.  
  1020.    3. Select the first Ln bytes of En-1 to create Cn.
  1021.  
  1022.    4. Pad Pn with zeros at the end to create P of length BB.
  1023.  
  1024.    5. Exclusive-or En-1 with P to create to create Dn.
  1025.  
  1026.    6. Encrypt Dn to create Cn-1
  1027.  
  1028.    7. The last two parts of the ciphertext are Cn-1 and
  1029.       Cn respectively.
  1030.  
  1031.    To implement CTS encryption, the RC5-CTS object must hold on to
  1032.    (buffer) at most 2*BB bytes of plaintext and process them specially
  1033.    when the RC5_CTS_Encrypt_Final routine is called.
  1034.  
  1035.    The following steps describe how to decrypt Cn-1 and Cn.
  1036.  
  1037.    1. Decrypt Cn-1 to create Dn.
  1038.  
  1039.    2. Pad Cn with zeros at the end to create C of length BB.
  1040.  
  1041.    3. Exclusive-or Dn with C to create Xn.
  1042.  
  1043.    4. Select the first Ln bytes of Xn to create Pn.
  1044.  
  1045.    5. Append the tail (BB minus Ln) bytes of Xn to Cn
  1046.       to create En.
  1047.  
  1048.    6. Decrypt En to create Pn-1.
  1049.  
  1050.    7. The last two parts of the plaintext are Pn-1 and
  1051.       Pn respectively.
  1052.  
  1053. 9.  Test Program and Vectors
  1054.  
  1055.    To help confirm the correctness of an implementation, this section
  1056.    gives a test program and results from a set of test vectors.
  1057.  
  1058. 9.1 Test Program
  1059.  
  1060.    The following test program written in C reads test vectors from its
  1061.    input stream and writes results on its output stream.  The following
  1062.    subsections give a set of test vectors for inputs and the resulting
  1063.  
  1064.  
  1065.  
  1066. Baldwin & Rivest             Informational                     [Page 19]
  1067.  
  1068. RFC 2040         RC5, RC5-CBC, RC5-CBC-Pad, and RC5-CTS     October 1996
  1069.  
  1070.  
  1071.    outputs.
  1072.  
  1073.   #include <stdio.h>
  1074.  
  1075.   #define BLOCK_LENGTH     (8 /* bytes */)
  1076.   #define MAX_KEY_LENGTH   (64 /* bytes */)
  1077.   #define MAX_PLAIN_LENGTH (128 /* bytes */)
  1078.   #define MAX_CIPHER_LENGTH(MAX_PLAIN_LENGTH + BLOCK_LENGTH)
  1079.   #define MAX_ROUNDS       (20)
  1080.   #define MAX_S_LENGTH     (2 * (MAX_ROUNDS + 1))
  1081.  
  1082.   typedef struct test_vector
  1083.   {
  1084.     int padding_mode;
  1085.     int rounds;
  1086.     char    keytext[2*MAX_KEY_LENGTH+1];
  1087.     int key_length;
  1088.     char    key[MAX_KEY_LENGTH];
  1089.     char    ivtext[2*BLOCK_LENGTH+1];
  1090.     int iv_length;
  1091.     char    iv[BLOCK_LENGTH];
  1092.     char    plaintext[2*MAX_PLAIN_LENGTH+1];
  1093.     int plain_length;
  1094.     char    plain[MAX_PLAIN_LENGTH];
  1095.     char    ciphertext[2*MAX_CIPHER_LENGTH+1];
  1096.     int cipher_length;
  1097.     char    cipher[MAX_CIPHER_LENGTH];
  1098.     RC5_WORD    S[MAX_S_LENGTH];
  1099.   } test_vector;
  1100.  
  1101.   void show_banner()
  1102.   {
  1103.     (void) printf("RC5 CBC Tester.\n");
  1104.     (void) printf("Each input line should contain the following\n");
  1105.     (void) printf("test parameters separated by a single space:\n");
  1106.     (void) printf("- Padding mode flag.  Use 1 for RC5_CBC_Pad, else
  1107.   0.\n");
  1108.     (void) printf("- Number of rounds for RC5.\n");
  1109.     (void) printf("- Key bytes in hexadecimal.  Two characters per
  1110.   byte like '01'.\n");
  1111.     (void) printf("- IV bytes in hexadecimal.  Must be 16 hex
  1112.   characters.\n");
  1113.     (void) printf("- Plaintext bytes in hexadecimal.\n");
  1114.     (void) printf("An end of file or format error terminates the
  1115.   tester.\n");
  1116.     (void) printf("\n");
  1117.   }
  1118.  
  1119.  
  1120.  
  1121.  
  1122. Baldwin & Rivest             Informational                     [Page 20]
  1123.  
  1124. RFC 2040         RC5, RC5-CBC, RC5-CBC-Pad, and RC5-CTS     October 1996
  1125.  
  1126.  
  1127.   /* Convert a buffer from ascii hex to bytes.
  1128.    * Set pTo_length to the byte length of the result.
  1129.    * Return 1 if everything went OK.
  1130.    */
  1131.   int hex_to_bytes (from, to, pTo_length)
  1132.     char    *from, *to;
  1133.     int     *pTo_length;
  1134.   {
  1135.     char    *pHex;  /* Ptr to next hex character. */
  1136.     char    *pByte;     /* Ptr to next resulting byte. */
  1137.     int  byte_length = 0;
  1138.     int  value;
  1139.  
  1140.     pByte = to;
  1141.     for (pHex = from ; *pHex != 0 ; pHex += 2)  {
  1142.         if (1 != sscanf(pHex, "%02x", &value))
  1143.             return (0);
  1144.         *pByte++ = ((char)(value & 0xFF));
  1145.         byte_length++;
  1146.     }
  1147.     *pTo_length = byte_length;
  1148.     return (1);
  1149.   }
  1150.  
  1151.   /* Convert a buffer from bytes to ascii hex.
  1152.    * Return 1 if everything went OK.
  1153.    */
  1154.   int bytes_to_hex (from, from_length, to)
  1155.     char    *from, *to;
  1156.     int from_length;
  1157.   {
  1158.     char    *pHex;  /* Ptr to next hex character. */
  1159.     char    *pByte;     /* Ptr to next resulting byte. */
  1160.     int  value;
  1161.  
  1162.     pHex = to;
  1163.     for (pByte = from ; from_length > 0 ; from_length--)  {
  1164.         value = *pByte++ & 0xFF;
  1165.         (void) sprintf(pHex, "%02x", value);
  1166.         pHex += 2;
  1167.     }
  1168.     return (1);
  1169.   }
  1170.  
  1171.   /* Return 1 if get a valid test vector. */
  1172.   int get_test_vector(ptv)
  1173.     test_vector *ptv;
  1174.   {
  1175.  
  1176.  
  1177.  
  1178. Baldwin & Rivest             Informational                     [Page 21]
  1179.  
  1180. RFC 2040         RC5, RC5-CBC, RC5-CBC-Pad, and RC5-CTS     October 1996
  1181.  
  1182.  
  1183.     if (1 != scanf("%d", &ptv->padding_mode))
  1184.         return (0);
  1185.     if (1 != scanf("%d", &ptv->rounds))
  1186.         return (0);
  1187.     if ((ptv->rounds < 0) || (MAX_ROUNDS < ptv->rounds))
  1188.         return (0);
  1189.     if (1 != scanf("%s", &ptv->keytext))
  1190.         return (0);
  1191.     if (1 != hex_to_bytes(ptv->keytext, ptv->key,
  1192.                          &ptv->key_length))
  1193.         return (0);
  1194.     if (1 != scanf("%s", &ptv->ivtext))
  1195.         return (0);
  1196.     if (1 != hex_to_bytes(ptv->ivtext, ptv->iv,
  1197.                          &ptv->iv_length))
  1198.         return (0);
  1199.     if (BLOCK_LENGTH != ptv->iv_length)
  1200.         return (0);
  1201.     if (1 != scanf("%s", &ptv->plaintext))
  1202.         return (0);
  1203.     if (1 != hex_to_bytes(ptv->plaintext, ptv->plain,
  1204.                          &ptv->plain_length))
  1205.         return (0);
  1206.     return (1);
  1207.   }
  1208.  
  1209.   void run_test (ptv)
  1210.     test_vector *ptv;
  1211.   {
  1212.     rc5UserKey  *pKey;
  1213.     rc5CBCAlg       *pAlg;
  1214.     int          numBytesOut;
  1215.  
  1216.     pKey = RC5_Key_Create ();
  1217.     RC5_Key_Set (pKey, ptv->key_length, ptv->key);
  1218.  
  1219.     pAlg = RC5_CBC_Create (ptv->padding_mode,
  1220.                     ptv->rounds,
  1221.                     RC5_FIRST_VERSION,
  1222.                     BB,
  1223.                     ptv->iv);
  1224.     (void) RC5_CBC_Encrypt_Init (pAlg, pKey);
  1225.     ptv->cipher_length = 0;
  1226.     (void) RC5_CBC_Encrypt_Update (pAlg,
  1227.                     ptv->plain_length, ptv->plain,
  1228.                     &(numBytesOut),
  1229.                     MAX_CIPHER_LENGTH - ptv->cipher_length,
  1230.                     &(ptv->cipher[ptv->cipher_length]));
  1231.  
  1232.  
  1233.  
  1234. Baldwin & Rivest             Informational                     [Page 22]
  1235.  
  1236. RFC 2040         RC5, RC5-CBC, RC5-CBC-Pad, and RC5-CTS     October 1996
  1237.  
  1238.  
  1239.     ptv->cipher_length += numBytesOut;
  1240.     (void) RC5_CBC_Encrypt_Final (pAlg,
  1241.                     &(numBytesOut),
  1242.                     MAX_CIPHER_LENGTH - ptv->cipher_length,
  1243.                     &(ptv->cipher[ptv->cipher_length]));
  1244.     ptv->cipher_length += numBytesOut;
  1245.     bytes_to_hex (ptv->cipher, ptv->cipher_length,
  1246.                  ptv->ciphertext);
  1247.     RC5_Key_Destroy (pKey);
  1248.     RC5_CBC_Destroy (pAlg);
  1249.   }
  1250.  
  1251.   void show_results (ptv)
  1252.     test_vector *ptv;
  1253.   {
  1254.     if (ptv->padding_mode)
  1255.         printf ("RC5_CBC_Pad ");
  1256.     else
  1257.         printf ("RC5_CBC     ");
  1258.     printf ("R = %2d ", ptv->rounds);
  1259.     printf ("Key = %s ", ptv->keytext);
  1260.     printf ("IV = %s ", ptv->ivtext);
  1261.     printf ("P = %s ", ptv->plaintext);
  1262.     printf ("C = %s", ptv->ciphertext);
  1263.     printf ("\n");
  1264.   }
  1265.  
  1266.   int main(argc, argv)
  1267.     int argc;
  1268.     char *argv[];
  1269.   {
  1270.     test_vector tv;
  1271.     test_vector *ptv = &tv;
  1272.  
  1273.     show_banner();
  1274.     while (get_test_vector(ptv))  {
  1275.         run_test(ptv);
  1276.         show_results(ptv);
  1277.     }
  1278.     return (0);
  1279.   }
  1280.  
  1281.  
  1282.  
  1283.  
  1284.  
  1285.  
  1286.  
  1287.  
  1288.  
  1289.  
  1290. Baldwin & Rivest             Informational                     [Page 23]
  1291.  
  1292. RFC 2040         RC5, RC5-CBC, RC5-CBC-Pad, and RC5-CTS     October 1996
  1293.  
  1294.  
  1295. 9.2 Test vectors
  1296.  
  1297.    The following text is an input file to the test program presented in
  1298.    the previous subsection.  The output is given in the next subsection.
  1299.  
  1300.   0 00 00                 0000000000000000 0000000000000000
  1301.   0 00 00                 0000000000000000 ffffffffffffffff
  1302.   0 00 00                 0000000000000001 0000000000000000
  1303.   0 00 00                 0000000000000000 0000000000000001
  1304.   0 00 00                 0102030405060708 1020304050607080
  1305.   0 01 11                 0000000000000000 0000000000000000
  1306.   0 02 00                 0000000000000000 0000000000000000
  1307.   0 02 00000000           0000000000000000 0000000000000000
  1308.   0 08 00                 0000000000000000 0000000000000000
  1309.   0 08 00                 0102030405060708 1020304050607080
  1310.   0 12 00                 0102030405060708 1020304050607080
  1311.   0 16 00                 0102030405060708 1020304050607080
  1312.   0 08 01020304           0000000000000000 ffffffffffffffff
  1313.   0 12 01020304           0000000000000000 ffffffffffffffff
  1314.   0 16 01020304           0000000000000000 ffffffffffffffff
  1315.   0 12 0102030405060708   0000000000000000 ffffffffffffffff
  1316.   0 08 0102030405060708   0102030405060708 1020304050607080
  1317.   0 12 0102030405060708   0102030405060708 1020304050607080
  1318.   0 16 0102030405060708   0102030405060708 1020304050607080
  1319.   0 08 01020304050607081020304050607080
  1320.                           0102030405060708 1020304050607080
  1321.   0 12 01020304050607081020304050607080
  1322.                           0102030405060708 1020304050607080
  1323.   0 16 01020304050607081020304050607080
  1324.                           0102030405060708 1020304050607080
  1325.  
  1326.   0 12 0102030405         0000000000000000 ffffffffffffffff
  1327.   0 08 0102030405         0000000000000000 ffffffffffffffff
  1328.   0 08 0102030405         7875dbf6738c6478 0808080808080808
  1329.   1 08 0102030405         0000000000000000 ffffffffffffffff
  1330.  
  1331.   0 08 0102030405         0000000000000000 0000000000000000
  1332.   0 08 0102030405         7cb3f1df34f94811 1122334455667701
  1333.  
  1334.   1 08 0102030405         0000000000000000
  1335.   ffffffffffffffff7875dbf6738c647811223344556677
  1336.  
  1337.  
  1338.  
  1339.  
  1340.  
  1341.  
  1342.  
  1343.  
  1344.  
  1345.  
  1346. Baldwin & Rivest             Informational                     [Page 24]
  1347.  
  1348. RFC 2040         RC5, RC5-CBC, RC5-CBC-Pad, and RC5-CTS     October 1996
  1349.  
  1350.  
  1351. 9.3 Test results
  1352.  
  1353.    The following text is the output produced by the test program run on
  1354.    the inputs given in the previous subsection.
  1355.  
  1356.   RC5 CBC Tester.
  1357.   Each input line should contain the following
  1358.   test parameters separated by a single space:
  1359.   - Padding mode flag.  Use 1 for RC5_CBC_Pad, else 0.
  1360.   - Number of rounds for RC5.
  1361.   - Key bytes in hexadecimal.  Two characters per byte
  1362.     like '01'.
  1363.   - IV bytes in hexadecimal.  Must be 16 hex characters.
  1364.   - Plaintext bytes in hexadecimal.
  1365.   An end of file or format error terminates the tester.
  1366.  
  1367.   RC5_CBC     R =  0 Key = 00 IV = 0000000000000000
  1368.    P = 0000000000000000 C = 7a7bba4d79111d1e
  1369.   RC5_CBC     R =  0 Key = 00 IV = 0000000000000000
  1370.    P = ffffffffffffffff C = 797bba4d78111d1e
  1371.   RC5_CBC     R =  0 Key = 00 IV = 0000000000000001
  1372.    P = 0000000000000000 C = 7a7bba4d79111d1f
  1373.   RC5_CBC     R =  0 Key = 00 IV = 0000000000000000
  1374.    P = 0000000000000001 C = 7a7bba4d79111d1f
  1375.   RC5_CBC     R =  0 Key = 00 IV = 0102030405060708
  1376.    P = 1020304050607080 C = 8b9ded91ce7794a6
  1377.   RC5_CBC     R =  1 Key = 11 IV = 0000000000000000
  1378.    P = 0000000000000000 C = 2f759fe7ad86a378
  1379.   RC5_CBC     R =  2 Key = 00 IV = 0000000000000000
  1380.    P = 0000000000000000 C = dca2694bf40e0788
  1381.   RC5_CBC     R =  2 Key = 00000000 IV = 0000000000000000
  1382.    P = 0000000000000000 C = dca2694bf40e0788
  1383.   RC5_CBC     R =  8 Key = 00 IV = 0000000000000000
  1384.    P = 0000000000000000 C = dcfe098577eca5ff
  1385.   RC5_CBC     R =  8 Key = 00 IV = 0102030405060708
  1386.    P = 1020304050607080 C = 9646fb77638f9ca8
  1387.   RC5_CBC     R = 12 Key = 00 IV = 0102030405060708
  1388.    P = 1020304050607080 C = b2b3209db6594da4
  1389.   RC5_CBC     R = 16 Key = 00 IV = 0102030405060708
  1390.    P = 1020304050607080 C = 545f7f32a5fc3836
  1391.   RC5_CBC     R =  8 Key = 01020304 IV = 0000000000000000
  1392.    P = ffffffffffffffff C = 8285e7c1b5bc7402
  1393.   RC5_CBC     R = 12 Key = 01020304 IV = 0000000000000000
  1394.    P = ffffffffffffffff C = fc586f92f7080934
  1395.   RC5_CBC     R = 16 Key = 01020304 IV = 0000000000000000
  1396.    P = ffffffffffffffff C = cf270ef9717ff7c4
  1397.   RC5_CBC     R = 12 Key = 0102030405060708 IV = 0000000000000000
  1398.    P = ffffffffffffffff C = e493f1c1bb4d6e8c
  1399.  
  1400.  
  1401.  
  1402. Baldwin & Rivest             Informational                     [Page 25]
  1403.  
  1404. RFC 2040         RC5, RC5-CBC, RC5-CBC-Pad, and RC5-CTS     October 1996
  1405.  
  1406.  
  1407.   RC5_CBC     R =  8 Key = 0102030405060708 IV = 0102030405060708
  1408.    P = 1020304050607080 C = 5c4c041e0f217ac3
  1409.   RC5_CBC     R = 12 Key = 0102030405060708 IV = 0102030405060708
  1410.    P = 1020304050607080 C = 921f12485373b4f7
  1411.   RC5_CBC     R = 16 Key = 0102030405060708 IV = 0102030405060708
  1412.    P = 1020304050607080 C = 5ba0ca6bbe7f5fad
  1413.   RC5_CBC     R =  8 Key = 01020304050607081020304050607080
  1414.    IV = 0102030405060708
  1415.    P = 1020304050607080 C = c533771cd0110e63
  1416.   RC5_CBC     R = 12 Key = 01020304050607081020304050607080
  1417.    IV = 0102030405060708
  1418.    P = 1020304050607080 C = 294ddb46b3278d60
  1419.   RC5_CBC     R = 16 Key = 01020304050607081020304050607080
  1420.    IV = 0102030405060708
  1421.    P = 1020304050607080 C = dad6bda9dfe8f7e8
  1422.   RC5_CBC     R = 12 Key = 0102030405 IV = 0000000000000000
  1423.    P = ffffffffffffffff C = 97e0787837ed317f
  1424.   RC5_CBC     R =  8 Key = 0102030405 IV = 0000000000000000
  1425.    P = ffffffffffffffff C = 7875dbf6738c6478
  1426.   RC5_CBC     R =  8 Key = 0102030405 IV = 7875dbf6738c6478
  1427.    P = 0808080808080808 C = 8f34c3c681c99695
  1428.   RC5_CBC_Pad R =  8 Key = 0102030405 IV = 0000000000000000
  1429.    P = ffffffffffffffff C = 7875dbf6738c64788f34c3c681c99695
  1430.   RC5_CBC     R =  8 Key = 0102030405 IV = 0000000000000000
  1431.    P = 0000000000000000 C = 7cb3f1df34f94811
  1432.   RC5_CBC     R =  8 Key = 0102030405 IV = 7cb3f1df34f94811
  1433.    P = 1122334455667701 C = 7fd1a023a5bba217
  1434.   RC5_CBC_Pad R =  8 Key = 0102030405 IV = 0000000000000000
  1435.    P = ffffffffffffffff7875dbf6738c647811223344556677
  1436.    C = 7875dbf6738c64787cb3f1df34f948117fd1a023a5bba217
  1437.  
  1438. 10. Security Considerations
  1439.  
  1440.    The RC5 cipher is relatively new so critical reviews are still being
  1441.    performed.  However, the cipher's simple structure makes it easy to
  1442.    analyze and hopefully easier to assess its strength.  Reviews so far
  1443.    are very promising.
  1444.  
  1445.    Early results [1] suggest that for RC5 with a 64 bit block size (32
  1446.    bit word size), 12 rounds will suffice to resist linear and
  1447.    differential cyptanalysis.  The 128 bit block version has not been
  1448.    studied as much as the 64 bit version, but it appears that 16 rounds
  1449.    would be an appropriate minimum.  Block sizes less than 64 bits are
  1450.    academically interesting but should not be used for cryptographic
  1451.    security.  Greater security can be achieved by increasing the number
  1452.    of rounds at the cost of decreasing the throughput of the cipher.
  1453.  
  1454.  
  1455.  
  1456.  
  1457.  
  1458. Baldwin & Rivest             Informational                     [Page 26]
  1459.  
  1460. RFC 2040         RC5, RC5-CBC, RC5-CBC-Pad, and RC5-CTS     October 1996
  1461.  
  1462.  
  1463.    The length of the secret key helps determine the cipher's resistance
  1464.    to brute force key searching attacks.  A key length of 128 bits
  1465.    should give adequate protection against brute force key searching by
  1466.    a well funded opponent for a couple decades [7].  For RC5 with 12
  1467.    rounds, the key setup time and data encryption time are the same for
  1468.    all key lengths less than 832 bits, so there is no performance reason
  1469.    for choosing short keys.  For larger keys, the key expansion step
  1470.    will run slower because the user key table, L, will be longer than
  1471.    the expanded key table, S.  However, the encryption time will be
  1472.    unchanged since it is only a function of the number of rounds.
  1473.  
  1474.    To comply with export regulations it may be necessary to choose keys
  1475.    that only have 40 unknown bits.  A poor way to do this would be to
  1476.    choose a simple 5 byte key.  This should be avoided because it would
  1477.    be easy for an opponent to pre-compute key searching information.
  1478.    Another common mechanism is to pick a 128 bit key and publish the
  1479.    first 88 bits.  This method reveals a large number of the entries in
  1480.    the user key table, L, and the question of whether RC5 key expansion
  1481.    provides adequate security in this situation has not been studied,
  1482.    though it may be fine.  A conservative way to conform to a 40 bit
  1483.    limitation is to pick a seed value of 128 bits, publish 88 bits of
  1484.    this seed, run the entire seed through a hash function like MD5 [4],
  1485.    and use the 128 bit output of the hash function as the RC5 key.
  1486.  
  1487.    In the case of 40 unknown key bits with 88 known key bits (i.e., 88
  1488.    salt bits) there should still be 12 or more rounds for the 64 bit
  1489.    block version of RC5, otherwise the value of adding salt bits to the
  1490.    key is likely to be lost.
  1491.  
  1492.    The lifetime of the key also influences security.  For high security
  1493.    applications, the key to any 64 bit block cipher should be changed
  1494.    after encrypting 2**32 blocks (2**64 blocks for a 128 bit block
  1495.    cipher).  This helps to guard against linear and differential
  1496.    cryptanalysis.  For the case of 64 bit blocks, this rule would
  1497.    recommend changing the key after 2**40 (i.e. 10**12) bytes are
  1498.    encrypted.  See Schneier [6] page 183 for further discussion.
  1499.  
  1500.  
  1501.  
  1502.  
  1503.  
  1504.  
  1505.  
  1506.  
  1507.  
  1508.  
  1509.  
  1510.  
  1511.  
  1512.  
  1513.  
  1514. Baldwin & Rivest             Informational                     [Page 27]
  1515.  
  1516. RFC 2040         RC5, RC5-CBC, RC5-CBC-Pad, and RC5-CTS     October 1996
  1517.  
  1518.  
  1519. 11. ASN.1 Identifiers
  1520.  
  1521.    For applications that use ASN.1 descriptions, it is necessary to
  1522.    define the algorithm identifier for these ciphers along with their
  1523.    parameter block formats.  The ASN.1 definition of an algorithm
  1524.    identifier already exists and is listed below for reference.
  1525.  
  1526.   AlgorithmIdentifier ::= SEQUENCE {
  1527.     algorithm    OBJECT IDENTIFIER,
  1528.     parameters   ANY DEFINED BY algorithm OPTIONAL
  1529.   }
  1530.  
  1531.   The values for the algorithm field are:
  1532.  
  1533.   RC5_CBC  OBJECT IDENTIFIER ::=
  1534.     { iso (1) member-body (2) US (840) rsadsi (113549)
  1535.       encryptionAlgorithm (3) RC5CBC (8) }
  1536.  
  1537.   RC5_CBC_Pad OBJECT IDENTIFIER ::=
  1538.   { iso (1) member-body (2) US (840) rsadsi (113549)
  1539.     encryptionAlgorithm (3) RC5CBCPAD (9) }
  1540.  
  1541.    The structure of the parameters field for these algorithms is given
  1542.    below.  NOTE: if the iv field is not included, then the
  1543.    initialization vector defaults to a block of zeros whose size depends
  1544.    on the blockSizeInBits field.
  1545.  
  1546.   RC5_CBC_Parameters ::= SEQUENCE {
  1547.     version           INTEGER (v1_0(16)),
  1548.     rounds            INTEGER (8..127),
  1549.     blockSizeInBits   INTEGER (64, 128),
  1550.     iv                OCTET STRING OPTIONAL
  1551.   }
  1552.  
  1553. References
  1554.  
  1555.    [1] Kaliski, Burton S., and Yinqun Lisa Yin, "On Differential and
  1556.    Linear Cryptanalysis of the RC5 Encryption Algorithm", In Advances
  1557.    in Cryptology - Crypto '95, pages 171-184, Springer-Verlag, New
  1558.    York, 1995.
  1559.  
  1560.    [2] Rivest, Ronald L., "The RC5 Encryption Algorithm", In
  1561.    Proceedings of the Second International Workshop on Fast Software
  1562.    Encryption, pages 86-96, Leuven Belgium, December 1994.
  1563.  
  1564.    [3] Rivest, Ronald L., "RC5 Encryption Algorithm", In Dr. Dobbs
  1565.    Journal, number 226, pages 146-148, January 1995.
  1566.  
  1567.  
  1568.  
  1569.  
  1570. Baldwin & Rivest             Informational                     [Page 28]
  1571.  
  1572. RFC 2040         RC5, RC5-CBC, RC5-CBC-Pad, and RC5-CTS     October 1996
  1573.  
  1574.  
  1575.    [4] Rivest, Ronald L., "The MD5 Message-Digest Algorithm", RFC
  1576.    1321.
  1577.  
  1578.    [5] RSA Laboratories, "Public Key Cryptography Standards (PKCS)",
  1579.    RSA Data Security Inc.  See ftp.rsa.com.
  1580.  
  1581.    [6] Schneier, Bruce, "Applied Cryptography", Second Edition, John
  1582.    Wiley and Sons, New York, 1996.  Errata: on page 195, line 13, the
  1583.    reference number should be [402].
  1584.  
  1585.    [7] Business Software Alliance, Matt Blaze et al., "Minimum Key
  1586.    Length for Symmetric Ciphers to Provide Adequate Commercial
  1587.    Security", http://www.bsa.org/bsa/cryptologists.html.
  1588.  
  1589.    [8] RSA Data Security Inc., "RC5 Reference Code in C", See the web
  1590.    site: www.rsa.com, for availability.  Not available with the first
  1591.    draft of this document.
  1592.  
  1593. Authors' Addresses
  1594.  
  1595.    Robert W. Baldwin
  1596.    RSA Data Security, Inc.
  1597.    100 Marine Parkway
  1598.    Redwood City, CA 94065
  1599.  
  1600.    Phone: (415) 595-8782
  1601.    Fax:   (415) 595-1873
  1602.    EMail: baldwin@rsa.com, or baldwin@lcs.mit.edu
  1603.  
  1604.  
  1605.    Ronald L. Rivest
  1606.    Massachusetts Institute of Technology
  1607.    Laboratory for Computer Science
  1608.    NE43-324
  1609.    545 Technology Square
  1610.    Cambridge, MA 02139-1986
  1611.  
  1612.    Phone: (617) 253-5880
  1613.    EMail: rivest@theory.lcs.mit.edu
  1614.  
  1615.  
  1616.  
  1617.  
  1618.  
  1619.  
  1620.  
  1621.  
  1622.  
  1623.  
  1624.  
  1625.  
  1626. Baldwin & Rivest             Informational                     [Page 29]
  1627.  
  1628.