doc/acl_blockciphers.texi

   1 @c acl_blockcipher.texi
   2
   3 @section Block ciphers
   4 @subsection What a block cipher does
   5  A block cipher is a algorithm which turn an input of fixed length into an
   6  output of the same length (enciphering or encrypting). The transformation is
   7  specified by a key which has to be of a fixed length, or a length of a given
   8  set or range.
   9  Generally there is also an algorithm which turns the output back to the
  10  previous input (deciphering or decrypting) when supplied with the same key.
  11
  12 @subsection List of available block ciphers
  13 This is a list of the currently supported block ciphers:
  14 @itemize @bullet
  15   @item AES (Advanced Encryption Standard)
  16   @item Camellia
  17   @item CAST5
  18   @item CAST6
  19   @item CS-Cipher
  20   @item DES (Data Encryption Standard)
  21   @item Khazad
  22   @item Noekeon
  23   @item Present
  24   @item RC5
  25   @item RC6
  26   @item Seed
  27   @item Serpent (AES finalist)
  28   @item Shacal1
  29   @item Shacal2
  30   @item Skipjack
  31   @item TDES (Tripple DES)
  32   @item Threefish
  33   @item XTEA
  34 @end itemize
  35
  36 @subsection high frequent parameters:
  37 @table @asis
  38   @item block size
  39   64 bits, 128 bits
  40   @item key size
  41   64 bits, 80 bits, 128 bits, 192 bits, 256 bits
  42   (note that some block ciphers use different sizes)
  43 @end table
  44
  45 @subsection Parts of a block cipher
  46 @itemize @bullet
  47   @item encryption algorithm
  48   @item decryption algorithm
  49   @item mostly a set of subkeys
  50   @item mostly a keyschedule which generates the subkeys from the supplied key.
  51 @end itemize
  52  As we can see here a block cipher normally has an algorithm besides the
  53  encryption and decryption algorithm, which we call keyschedule.
  54  Mostly the encryption and decryption algorithm consist of multiple rounds,
  55  where each round (and sometimes between rounds) subkeys are needed to modify
  56  the data. This subkeys are generated by the keyschedule and stored in a state
  57  or context variable.
  58  Note that not all algorithms need a pregenerated context, sometimes it is easy
  59  to generate the subkeys "on the fly" so there is not always the need of a
  60  context variable. In this case instead of a context the actual key is passed
  61  to the encryption and decryption function.
  62
  63 @subsection API of block ciphers
  64  The API is not always consistent due to the fact that we tried to optimize the
  65  code for size (flash, heap and stack) and speed (runtime of the different
  66  components).
  67  Generally the API of the implemented block ciphers consists of:
  68 @table @code
  69  @item *_init
  70  function, which implements the keyschedule
  71  @item *_enc
  72  function, which implements the encryption algorithm
  73  @item *_dec
  74  function, which implements the decryption algorithm
  75  @item *_free
  76  function, which frees memory allocated for the keyschedule
  77  @item *_ctx_t
  78  context type, which can contain a keyschedule and other information
  79 @end table
  80 @subsubsection @code{*_init} function
  81  The @code{*_init} function generally takes a pointer to the key as first parameter.
  82  For ciphers where the keysize is not fixed the second parameter gives the
  83  keysize (in bits regularly) and the last parameter points to the context
  84  variable to fill.
  85  For some ciphers there are additional parameters like the number of rounds,
  86  these parameters generally occur before the context pointer.
  87
  88 @subsubsection @code{*_enc} and @code{*_dec} functions
  89  The encryption and decryption function of a specific algorithm normally do not
  90  differ in their parameters. Generally these functions take a pointer to the
  91  block to operate on. Some ciphers allow to specify two blocks, where the first
  92  one will be written to and the second will contain the source block. The two
  93  blocks may overlap or be the same. Most ciphers have only one block pointer.
  94  The block specified by the pointer is encrypted (if the @code{*_enc} function is
  95  called) or decrypted (if the @code{*_dec} function is called).
  96  The last parameter specifies either the key direct (with a pointer to it) or
  97  is a pointer to a context created with the @code{*_init} function.
  98  It is guaranteed that the context is in the same state as before the *_enc or
  99  @code{*_dec} function call. Most @code{*_enc} and @code{*_dec} functions do not modify the context
 100  at all, but some do for reducing dynamic memory requirements. So here are some
 101  limitations to the reentrant property.
 102
 103 @subsubsection @code{*_free} function
 104  A @code{*_free} function is only provided where needed (so most ciphers do not have
 105  it). It is used to free memory dynamically allocated by the @code{*_init} function.
 106
 107 @subsubsection *_ctx_t type
 108  A variable of the @code{*_ctx_t} type may hold information needed by the @code{*_enc} or
 109  @code{*_dec} function. It is initialized by the @code{*_init} function. If dynamic memory is
 110  allocated by the @code{*_init} function also a @code{*_free} function is provided which frees
 111  the allocated memory. An initialized @code{*_ctx_t} variable may not be copied as it
 112  may contains pointers to itself.
 113
 114 @section Block cipher abstraction layer (BCAL)
 115 The BlockCipeherAbstractionLayer (BCAL) is an abstraction layer which allows
 116 usage of all implemented block ciphers in a simple way. It abstracts specific
 117 function details and is suitable for implementations which want to be flexible
 118 in the choosing of specific block ciphers. Another important aspect is that this
 119 abstraction layer enables the implementation of block cipher operating modes
 120 independently from concrete ciphers. It is very simple to use and reassembles
 121 the API used to implement individual ciphers.
 122
 123 The main component is a block cipher descriptor which contains the details of
 124 the individual ciphers.
 125
 126 Care should be taken when choosing a specific keysize. It may be the case that
 127 the chosen keysize is not compatible with the chosen block cipher.
 128
 129
 130 @subsection Parts of BCAL
 131 The BCAL is split up in different parts:
 132 @itemize @bullet
 133   @item BCAL declaration for BCAL decriptors
 134   @item algorithm specific definitions of BCAL decriptors
 135   @item BCAL basic context type
 136   @item BCAL basic functions
 137 @end itemize
 138
 139 @subsubsection BCAL declaration for BCAL decriptors
 140 The BCAL descriptor is a structure which is usually placed in FLASH or ROM since
 141 modification is unnecessary. It contains all information required to use the
 142 according block cipher.
 143
 144 @verbatim
 145 typedef struct {
 146         uint8_t  type; /* 1==block cipher */
 147         uint8_t  flags;
 148         PGM_P    name;
 149         uint16_t ctxsize_B;
 150         uint16_t blocksize_b;
 151         bc_init_fpt init;
 152         bc_enc_fpt  enc;
 153         bc_dec_fpt  dec;
 154         bc_free_fpt free;
 155         PGM_VOID_P valid_keysize_desc;
 156 } bcdesc_t; /* block cipher descriptor type */
 157 @end verbatim
 158
 159 @table @var
 160   @item type
 161   should be set to @samp{1} to indicate that this descriptor is for a
 162   block cipher.
 163
 164  @item flags
 165  defines what kind of init function is provided and what kind of decrypt
 166  and encrypt functions are provided.
 167
 168  @table @asis
 169  @item bit 0
 170  if clear (@samp{0}) designates an init function with fixed key length, so
 171  the length parameter is omitted (@code{init(void* ctx, void* key)}).
 172
 173  if set (@samp{1}) designates an init function which requires an explicit
 174  keysize argument (@code{init(void*ctx, uint16_t length_b, void* key)}).
 175
 176  @item bit 1
 177  if clear (@samp{0}) designates that the encryption function transforms the
 178  plaintext block in place to the ciphertext (@code{enc(void* block, void* ctx)}).
 179
 180  if set (@samp{1}) designates that the encryption function offers a dedicated
 181  pointers for input and output. The two regions may be the same
 182  (@code{enc(void* out, void* in, void*ctx)}).
 183
 184  @item bit 2
 185  if clear (@samp{0}) designates that the decryption function transforms the
 186  ciphertext block in place to the plaintext (@code{dec(void* block, void* ctx)}).
 187
 188  if set (@samp{1}) designates that the decryption function offers a dedicated
 189  pointers for input and output. The two regions may be the same
 190  (@code{dec(void* out, void* in, void*ctx)}).
 191  @end table
 192
 193  @item name
 194  is a pointer to a zero terminated ASCII string giving the name of the
 195  implemented primitive. On targets with Harvard-architecture the string resides
 196  in code memory (FLASH, ROM, ...).
 197
 198  @item ctxsize_B
 199  is the number of bytes which should be allocated for the context variable.
 200
 201  @item blocksize_b
 202  is the number of bits on which the encrypt and decrypt function work on.
 203
 204  @item init
 205  is a pointer to the init function (see @samp{flags} how the init function
 206  should be called). If there is no init function this field is NULL.
 207
 208  @item enc
 209  is a pointer to the encryption function (see @samp{flags} how the encryption
 210  function should be called).
 211
 212  @item dec
 213  is a pointer to the decryption function (see @samp{flags} how the decryption
 214  function should be called).
 215
 216  @item free
 217  is a pointer to the free function or NULL if there is no free function.
 218
 219  @item valid_keysize_desc
 220  is a pointer to a keysize descriptor structure which is used to validate
 221  that the chosen keysize is valid
 222 @end table
 223
 224 @subsubsection BCAL-Basic context
 225 Besides the context types for individual ciphers there is a generic context
 226 type for BCAL. This is the context to use when using BCAL based functions.
 227 The BCAL context has the following structure:
 228 @verbatim
 229 typedef struct{
 230         bcdesc_t* desc_ptr;
 231         uint16_t  keysize;
 232         void*     ctx;
 233 } bcgen_ctx_t;
 234 @end verbatim
 235 @table @code
 236 @item desc_ptr
 237 a pointer to the BCAL descriptor
 238 @item keysize
 239 the chosen keysize
 240 @item ctx
 241 pointer to the cipher specific context
 242 @end table
 243
 244
 245
 246 @subsubsection BCAL-Basic
 247 BCAL-Basic provides the basic features of an block cipher on top of the
 248 BCAL. To use it you simply have to include the algorithms you want to use,
 249 the BCAL descriptor file and of course the BCAL-Basic implementation.
 250
 251 The following functions are provided:
 252 @table @code
 253 @item bcal_cipher_init
 254 @code{uint8_t bcal_cipher_init(const bcdesc_t* cipher_descriptor, const void* key, uint16_t keysize_b, bcgen_ctx_t* ctx)}
 255  this function initializes a BCAL context based on the given BCAL descriptor
 256  pointer (first parameter) with a given key (second parameter) of a given length
 257  (third parameter). The context to initialize is designated by the pointer
 258  passed as fourth parameter.
 259
 260  If everything works fine @samp{0} is returned. In the case something fails
 261  the following codes are returned:
 262 @table @samp
 263   @item 1
 264   The specified keysize is not available with this cipher
 265   @item 2
 266   It was not possible to allocate enough memory to hold the key.
 267   (This is returned when there is no actual init function and you ran out
 268   of memory)
 269   @item 3
 270   It was not possible to allocate enough memory to hold the context variable
 271   for the selected cipher.
 272 @end table
 273
 274 @item bcal_cipher_free
 275 @code{void bcal_cipher_free(bcgen_ctx_t* ctx)} this function frees the memory
 276 allocated by the init function and should be called whenever you are finished
 277 with BCAL context. It automatically also calls the @code{free} function if
 278 necessary.
 279
 280 @item bcal_cipher_enc
 281 @code{void bcal_cipher_enc(void* block, const bcgen_ctx_t* ctx)}
 282 this function encrypts a block in-place using a given BCAL contex.
 283
 284 @item bcal_cipher_dec
 285 @code{void bcal_cipher_dec(void* block, const bcgen_ctx_t* ctx)}
 286 this function decrypts a block in-place using a given BCAL contex.
 287
 288 @item bcal_cipher_getBlocksize_b
 289 @code{uint16_t bcal_cipher_getBlocksize_b(const bcdesc_t* desc)}
 290 this function returns the block size of a given cipher by using the BCAL
 291 descriptor (to which a pointer must be passed).
 292
 293 @item bcal_cipher_getKeysizeDesc
 294 @code{PGM_VOID_P bcal_cipher_getKeysizeDesc(const bcdesc_t* desc)}
 295 this function returns a pointer to the keysize descriptor of a given cipher by
 296 using the BCAL descriptor (to which a pointer must be passed).
 297
 298 @end table
 299
 300 @subsection Keysize descriptors
 301 There are a lot of different block ciphers or cryptographic algorithms in
 302 general which put several constrains to the number of bits which can be used
 303 as key.
 304
 305 Our approach is to find a simple and compact way do specify which lengths are
 306 valid and which are not. The system is quite simple, we use a list of patterns
 307 (with parameters) and if any matches the keysize is valid, if none matches the
 308 keysize is unsupported.
 309
 310 The patterns are:
 311 @itemize @bullet
 312 @item simple list of valid keysizes
 313 @item range of keysizes
 314 @item augmented range of keysizes
 315 @end itemize
 316
 317 @subsubsection simple list of valid keysizes
 318 The simple keysize list has the following structure:
 319 @verbatim
 320 typedef struct{ /* keysize is valid if listed in items */
 321         uint8_t  n_items;  /* number of items (value 0 is reserved) */
 322         uint16_t items[]; /* list of valid lengths */
 323 }keysize_desc_list_t;
 324 @end verbatim
 325 First we specify how many keysizes we want to declare valid (this is limited to
 326 255 keysizes but that should not impose any real world constrains). And follow
 327 it by the keysizes as 16bit unsigned values.
 328
 329 If you want to declare a lot of keys please check first the other methods since
 330 they may give a more compact definition.
 331
 332 @subsubsection range of keysizes
 333 This method specifies an entire range of keys a valid using the following
 334 structure:
 335 @verbatim
 336 typedef struct{ /* keysize is valid if min<=keysize<=max */
 337         uint16_t min;
 338         uint16_t max;
 339 }keysize_desc_range_t;
 340 @end verbatim
 341 So all keysizes between @code{min} and @code{max} (including @code{min} and
 342 @code{max}) are valid. Please note that in most cases also keysizes which
 343 are not a multiple of 8 (so are not full bytes) are also matched.
 344 If you want to avoid this see the augmented range of keysizes.
 345
 346 @subsubsection augmented range of keysizes
 347 The augmented range of keysizes uses the following structure:
 348 @verbatim
 349 typedef struct{ /* keysize is valid if min<=keysize<=max and if keysize mod distance == offset */
 350         uint16_t min;
 351         uint16_t max;
 352         uint16_t distance;
 353         uint16_t offset;
 354 }keysize_desc_arg_range_t;
 355 @end verbatim
 356 The restriction to a range is the same as with the simpler range of keysizes,
 357 but also another restriction is imposed. A valid keysize must have a reminder
 358 of @code{offset} when divided by @code{distance}. So you can limit a keysize
 359 to full bytes by simply setting @code{distance} to @samp{8} and @code{offset}
 360 to @samp{0}.
 361
 362 @subsubsection the actual descriptor
 363 The keysize descriptor is a list of the former patterns. Each pattern is
 364 preceded by byte designating the type of pattern and the list is terminated
 365 by a @code{NULL} byte.
 366
 367 The designator byte can have one of the following values:
 368 @table @samp
 369 @item 0x00
 370 Terminator byte, signals the end of the list
 371 @item 0x01
 372 simple list of keysizes
 373 @item 0x02
 374 simple range of keysizes
 375 @item 0x03
 376 augmented range of keysizes
 377 @end table
 378
 379