USAGE.blockciphers

   1 ===================================
   2 =      Usage of blockciphers      =
   3 ===================================
   4
   5 Author: Daniel Otte
   6 email:  bg@nerilex.org
   7
   8
   9 0. Foreword
  10  This file will describe how to use the blockcipher implementations provided by
  11  this library. It will not only show how to call the cryptographic functions
  12  but also discuss a little how to build security mechanisms from that.
  13  So you will also be introduced to the basic "modes of operation".
  14
  15 1. What a blockcipher does
  16  A blockcipher is a algorithm which turn an input of fixed length into an
  17  output of the same length (enciphering or encrypting). The transformation is
  18  specified by a key which has to be of a fixed length, or a length of a given
  19  set or range.
  20  Generally there is also an algorithm which turns the output back to the
  21  previous input (deciphering or decrypting) when supplied with te same key.
  22
  23 1.1. high frequent parameters:
  24   block size: 64 bits, 128 bits
  25   key size: 64 bits, 80 bits, 128 bits, 192 bits, 256 bits
  26   (note that some blockciphers use different sizes)
  27
  28 2. Parts of a blockcipher
  29   * encryption algorithm
  30   * decryption algorithm
  31   * mostly a set of subkeys
  32   * mostly a keyschedule which generates the subkeys from the supplied key.
  33  As we can see here a blockcipher normally has an algorithm besides the
  34  encryption and decryption algorithm, which we call keyschedule.
  35  Mostly the encryption and decryption algorithm consist of multiple rounds,
  36  where each round (and sometimes between rounds) subkeys are needed to modify
  37  the data. This subkeys are generated by the keyschedule and stored in a state
  38  or context variable.
  39  Note that not all algorithms need a pregenerated context, sometimes it is easy
  40  to generate the subkeys "on the fly" so there is not always the need of a
  41  context variable.
  42
  43 3. blockcipher API
  44  The API is not always consistent due to the fact that we tried to optimize the
  45  code for size (flash, heap and stack) and speed (runtime of the different
  46  components).
  47  Generally the API of the implemented blockciphers consists of:
  48
  49  *_init function, which implements the keyschedule
  50  *_enc  function, which implements the encryption algorithm
  51  *_dec  function, which implements the decryption algorithm
  52  *_free function, which frees memory allocated for the keyschedule
  53  *_ctx_t context type, which can contain a keyschedule and other information
  54
  55 3.1 look at the prototypes
  56  Generally the prototypes (defined in the *.h files) will tell you what
  57  parameter means what.
  58
  59 3.1.2 sizes in bits and bytes
  60  Working with cryptographical functions involves working with different
  61  lengths. Some times you want to know it in bits and sometimes in bytes. To
  62  reduce frustration and to avoid bugs we suffix a length parameter with either
  63  _b or _B depending on the meaning. _b means in bits and _B means in bytes
  64  (big b big word).
  65
  66 3.2. *_init function
  67  The *_init function generally takes a pointer to the key as first parameter.
  68  For ciphers where the keysize is not fixed the second parameter gives the
  69  keysize (in bits regularly) and the last parameter points to the context
  70  variable to fill.
  71  For some ciphers there are additional parameters like the number of rounds,
  72  these parameters generally occur before the context pointer.
  73
  74 3.3. *_enc and *_dec functions
  75  The encryption and decryption function of a specific algorithm normally do not
  76  differ in their parameters. Generally these functions take a pointer to the
  77  block to operate on. Some ciphers allow to specify two blocks, where the first
  78  one will be written to and the second will contain the source block. The two
  79  blocks may overlap or be the same. The last parameter specifies either the key
  80  direct (with a pointer to it) or is a pointer to a context created with the
  81  *_init function.
  82
  83 3.4. *_free function
  84  A *_free function is only provided where needed (so most ciphers do not have
  85  it). It is used to free memory dynamically allocated by the *_init function.
  86
  87 4. modes of operation
  88  The usage of cryptographic algorithms is usually motivated by the intend to
  89  fight potential threads. Blockciphers are generally good building blocks.
  90  There are different attacks to the cipher itself, but this is work to be done
  91  by cryptographers, but what stays up to you is using this building blocks in a
  92  secure manner.
  93  You may read http://en.wikipedia.org/wiki/Block_cipher_modes_of_operation to
  94  learn more.
  95
  96 4.1. ECB (electronic codebook mode)
  97  Electronic codebook mode is the simplest mode of operation and its usages is
  98  generally not suggested. In ECB-mode a message which is to encrypt is simply
  99  split up in blocks and each block gets independently encrypted. The problem
 100  with this mode is that, for example same data produces the same ciphertext,
 101  which may also allows an attack to inject selected data.
 102
 103     +----+   +----+   +----+           +----+   +----+   +----+
 104     | P1 |   | P2 |   | P3 |           | C1 |   | C2 |   | C3 |
 105     +----+   +----+   +----+           +----+   +----+   +----+
 106       |        |        |                |        |        |
 107       V        V        V                V        V        V
 108     o---o    o---o    o---o            o---o    o---o    o---o
 109     | E |    | E |    | E |            | D |    | D |    | D |
 110     o---o    o---o    o---o            o---o    o---o    o---o
 111       |        |        |                |        |        |
 112       V        V        V                V        V        V
 113     +----+   +----+   +----+           +----+   +----+   +----+
 114     | C1 |   | C2 |   | C3 |           | P1 |   | P2 |   | P3 |
 115     +----+   +----+   +----+           +----+   +----+   +----+
 116
 117 4.2. CBC (chipher-block-chaining mode)
 118  CBC-mode is a more advanced mode of operation. It solves most problems of
 119  ECB-mode. It again works by split ing up the message into blocks and
 120  introducing a initialization vector (IV) at the beginning. The IV should be
 121  randomly generated and is not required to be kept secret. The plaintext of
 122  each block is XORed with the ciphertext of the previous block (the first block
 123  is XORed with the IV) and then gets encrypted producing the ciphertext block.
 124  For decryption of a block simply decrypt the block an XOR it with the previous
 125  ciphertext block (or the IV in the case of the first block).
 126  CBC-mode has some properties which make it quite useless for some application.
 127  For example if you want to store a large amount of data, and you want to make
 128  a change in one block you would have to decrypt and re-encrypt all following
 129  blocks. If you have such a case read more about block cipher modes.
 130  The wikipedia article http://en.wikipedia.org/wiki/Block_cipher_modes_of_
 131  operation#Other_modes_and_other_cryptographic_primitives would make a good
 132  start.
 133
 134  +----+   +----+   +----+   +----+       +----+   +----+   +----+   +----+
 135  | IV |   | P1 |   | P2 |   | P3 |       | IV |   | C1 |   | C2 |   | C3 |
 136  +----+   +----+   +----+   +----+       +----+   +----+   +----+   +----+
 137    |        |        |        |            |        |        |        |
 138    +------> X   +--> X   +--> X            |        +---+    +---+    |
 139    |        |   |    |   |    |            |        |   |    |   |    |
 140    |        V   |    V   |    V            |        V   |    V   |    V
 141    |      o---o |  o---o |  o---o          |      o---o |  o---o |  o---o
 142    |      | E | |  | E | |  | E |          |      | D | |  | D | |  | D |
 143    |      o---o |  o---o |  o---o          |      o---o |  o---o |  o---o
 144    |        |   |    |   |    |            |        |   |    |   |    |
 145    |        +---+    +---+    +            +------> X   +--> X   +--> X
 146    |        |        |        |            |        |        |        |
 147    V        V        V        V            V        V        V        V
 148  +----+   +----+   +----+   +----+       +----+   +----+   +----+   +----+
 149  | IV |   | C1 |   | C2 |   | C3 |       | IV |   | P1 |   | P2 |   | P3 |
 150  +----+   +----+   +----+   +----+       +----+   +----+   +----+   +----+
 151
 152 4.3. stream cipher modes
 153  The following modes of operation turn the blockcipher in something better
 154  described as stream cipher. So you may consider reading USAGE.streamciphers
 155  or anything else about streamcipher if you wish to use this modes.
 156
 157 4.3.1. CTR (counter mode)
 158  This is quite simple. You use a counter which gets encrypted to produce a
 159  key stream. This key stream may be used to encrypt data by XOR-ing the
 160  plaintext with the key stream. Decrypting is exactly the same then encrypting
 161  BE WARNED, an attacker might flip a bit in the ciphertext and the
 162  corresponding bit in the plaintext gets flipped.
 163
 164  +---------+ o--o  +---------+ o--o  +---------+ o--o  +---------+
 165  | counter |-|+1|->| counter |-|+1|->| counter |-|+1|->| counter |
 166  +---------+ o--o  +---------+ o--o  +---------+ o--o  +---------+
 167       |                 |                 |                 |
 168       V                 V                 V                 V
 169     o---o             o---o             o---o             o---o
 170     | E |             | E |             | E |             | E |
 171     o---o             o---o             o---o             o---o
 172       |                 |                 |                 |
 173       V                 V                 V                 V
 174   +--------+        +--------+        +--------+        +--------+
 175   |  key   |        |  key   |        |  key   |        |  key   |
 176   | stream |        | stream |        | stream |        | stream |
 177   +--------+        +--------+        +--------+        +--------+
 178
 179 4.3.2 OFB (output-feedback mode)
 180  OFB-mode is much like CTR-mode. In fact the only difference is that you do not
 181  increment a counter, but use the output of the encryption operation before as
 182  input.
 183
 184  +-------+         +-------+         +-------+
 185  |   IV  |   +---->| input |   +---->| input |
 186  +-------+   |     +-------+   |     +-------+
 187      |       |         |       |         |
 188      V       |         V       |         V
 189    o---o     |       o---o     |       o---o
 190    | E |     |       | E |     |       | E |
 191    o---o     |       o---o     |       o---o
 192      |       |         |       |         |
 193      V       |         V       |         V
 194  +--------+  |     +--------+  |     +--------+
 195  | output |--+     | output |--+     | output |
 196  +--------+        +--------+        +--------+
 197      |                 |                 |
 198      V                 V                 V
 199  +--------+        +--------+        +--------+
 200  |  key   |        |  key   |        |  key   |
 201  | stream |        | stream |        | stream |
 202  +--------+        +--------+        +--------+
 203
 204 4.3.2 CFB (cipher-feedback mode)
 205  CFB-mode looks much like OFB-mode, but it has a lot of different properties.
 206  Instead of using the previous output block as input the resulting ciphertext
 207  is used as input. Due to the fact that not the entire output-block needs to be
 208  used, the ciphertext does not form the entire input block for the next
 209  operation but it is shifted in the input block.
 210  The resulting cipher is something known as self synchronizing stream cipher.
 211  This means that a manipulation of a single bit in the ciphertext will result
 212  in this bit flipped in the corresponding plaintext but the following blocks
 213  will be "destroyed" until the cipher "heald" itself, meaning the manipulated
 214  ciphertext block gets shift out of the input block.
 215
 216
 217       +-------+              +-------+              +-------+
 218       |   IV  |  +--------->>| input |  +--------->>| input |
 219       +-------+  |           +-------+  |           +-------+
 220           |      |               |      |               |
 221           V      |               V      |               V
 222         o---o    |             o---o    |             o---o
 223         | E |    |             | E |    |             | E |
 224         o---o    |             o---o    |             o---o
 225           |      |               |      |               |
 226           V      |               V      |               V
 227       +--------+ |           +--------+ |           +--------+
 228       | output | |           | output | |           | output |
 229       +--------+ |           +--------+ |           +--------+
 230           |      |               |      |               |
 231  +----+   V   +----+    +----+   V   +----+    +----+   V   +----+
 232  | P1 |-->X-->| C1 |    | P2 |-->X-->| C2 |    | P3 |-->X-->| C3 |
 233  +----+       +----+    +----+       +----+    +----+       +----+
 234
 235
 236    +-------------+         +-------------+
 237    |  +-------+  |         |  +-------+  |          +-------+
 238    |  |   IV  |  +---------|>>| input |  +-------->>| input |
 239    |  +-------+            |  +-------+             +-------+
 240    |      |                |      |                     |
 241    |      V                |      V                     V
 242    |    o---o              |    o---o                 o---o
 243    |    | E |              |    | E |                 | E |
 244    |    o---o              |    o---o                 o---o
 245    |      |                |      |                     |
 246    |      V                |      V                     V
 247    |  +--------+           |  +--------+            +--------+
 248    |  | output |           |  | output |            | output |
 249    |  +--------+           |  +--------+            +--------+
 250    |      |                |      |                      |
 251  +----+   V   +----+     +----+   V   +----+    +----+   V   +----+
 252  | C1 |-->X-->| P1 |     | C2 |-->X-->| P2 |    | C3 |-->X-->| P3 |
 253  +----+       +----+     +----+       +----+    +----+       +----+
 254