doc/hashes.rst

   1 Hash functions
   2 ==============
   3 A hash function is an algorithm to map an arbitrary long message (in the form
   4 of a bit string) to a fixed length message digest or hash value.
   5 The hash function aims to be collision free, which means that it is not
   6 practicable to find two messages with the same hash value (although this
   7 collision must exist). Also it should not be practicable to construct a
   8 message which maps to a given hash value.
   9
  10 List of available hash functions
  11 --------------------------------
  12 The following hash functions are currently implemented:
  13
  14 * Blake
  15 * BlueMidnightWish
  16 * CubeHash
  17 * Echo
  18 * Grøstl
  19 * Keccak
  20 * MD5
  21 * SHA-256
  22 * SHA-1
  23 * Shabal
  24 * Skein
  25
  26 High frequent parameters
  27 ------------------------
  28 +-----------------+------------------------------------------------------------+
  29 | block size      | 512 bits                                                   |
  30 +-----------------+------------------------------------------------------------+
  31 | hash value size | 128 bits, 160 bits, 224 bits, 256 bits, 384 bits, 512 bits |
  32 +-----------------+------------------------------------------------------------+
  33
  34 Parts of a hash function
  35 ------------------------
  36 * initialization function
  37 * compression algorithm
  38 * finalization function
  39
  40 hash function API
  41 -----------------
  42 The API is not always consistent due to the fact that we tried to optimize the
  43 code for size (flash, heap and stack) and speed (runtime of the different
  44 components).
  45
  46 Generally the API of the implemented block ciphers consists of:
  47
  48 +--------------+--------------------------------------------------------------+
  49 | \*_init      | function, which implements the initialization of the context |
  50 +--------------+--------------------------------------------------------------+
  51 | \*_nextBlock | function, which implements the compression algorithm         |
  52 +--------------+--------------------------------------------------------------+
  53 | \*_lastBlock | function, which implements the padding algorithm             |
  54 +--------------+--------------------------------------------------------------+
  55 | \*_ctx2hash  | function, which turns a context into an actual hash value    |
  56 +--------------+--------------------------------------------------------------+
  57 | \*_ctx_t     | context type, which can contains the state of a hashing      |
  58 |              | process                                                      |
  59 +--------------+--------------------------------------------------------------+
  60
  61 ``*_init`` function
  62 ~~~~~~~~~~~~~~~~~~~
  63 The ``*_init`` function generally takes a pointer to the context as parameter.
  64 This function initializes the context with algorithm specific values.
  65
  66 ``*_nextBlock`` function
  67 ~~~~~~~~~~~~~~~~~~~~~~~~
  68 The ``*_nextBlock`` function is the core of each hash function. It updates the
  69 hash state with a given message block. So this function uses a context pointer
  70 and a message pointer as parameters. The size of a message block is fixed for
  71 each hash function (mostly 512 bit). For the last block of a messages which may
  72 be smaller than the blocksize you have to use the ``*_lastBlock`` function
  73 described below.
  74
  75 ``*_lastBlock`` function
  76 ~~~~~~~~~~~~~~~~~~~~~~~~
  77 The ``*_lastBlock`` function finalizes the context with the last bits of a
  78 message. Since the last block is not required to have the blocksize you have
  79 to specify the length of the last block (normally in bits). This function
  80 performs the padding and final processing.
  81
  82 ``*_ctx2hash`` function
  83 ~~~~~~~~~~~~~~~~~~~~~~~
  84 The ``*_ctx2hash`` function turns a given hash context into an actual hash
  85 value. If multiple sized hash value may be created from a context it is
  86 necessary to give the the size of the hash value as parameter.
  87
  88
  89 Hash function abstraction layer (HFAL)
  90 ======================================
  91 The HashFunctionAbstractionLayer (BCAL) is an abstraction layer which allows
  92 usage of all implemented hash functions in a simple way. It abstracts specific
  93 function details and is suitable for implementations which want to be flexible
  94 in the choosing of specific hash functions. Another important aspect is that
  95 this abstraction layer enables the implementation of hash function operating
  96 modes independently from concrete hash function. It is very simple to use and
  97 reassembles the API used to implement individual hash functions.
  98
  99 The main component is a hash function descriptor which contains the details of
 100 the individual hash functions.
 101
 102 Parts of HFAL
 103 -------------
 104 The HFAL is split up in different parts:
 105
 106 * HFAL declaration for HFAL descriptors
 107 * algorithm specific definitions of HFAL descriptors
 108 * HFAL basic context type
 109 * HFAL basic functions
 110
 111 HFAL declaration for HFAL descriptors
 112 -------------------------------------
 113 The HFAL descriptor is a structure which is usually placed in FLASH or ROM since
 114 modification is unnecessary. It contains all information required to use the
 115 according hash function.
 116
 117 ::
 118
 119    typedef struct {
 120         uint8_t  type; /* 2 == hashfunction */
 121         uint8_t  flags;
 122         PGM_P    name;
 123         uint16_t ctxsize_B;
 124         uint16_t blocksize_b;
 125         uint16_t hashsize_b;
 126         hf_init_fpt init;
 127         hf_nextBlock_fpt  nextBlock;
 128         hf_lastBlock_fpt  lastBlock;
 129         hf_ctx2hash_fpt   ctx2hash;
 130         hf_free_fpt free;
 131         hf_mem_fpt mem;
 132    } hfdesc_t; /* hashfunction descriptor type */
 133
 134 +-------------+----------------------------------------------------------------+
 135 | type        | should be set to ``2`` to indicate that this descriptor is for |
 136 |             | a hash function.                                               |
 137 +-------------+----------------------------------------------------------------+
 138 | flags       | currently unused, should be set to zero.                       |
 139 +-------------+----------------------------------------------------------------+
 140 | name        | is a pointer to a zero terminated ASCII string giving the name |
 141 |             | of the implemented primitive. On targets with                  |
 142 |             | Harvard-architecture the string resides in code memory         |
 143 |             | (FLASH, ROM, ...).                                             |
 144 +-------------+----------------------------------------------------------------+
 145 | ctxsize_B   | is the number of bytes which should be allocated for the       |
 146 |             | context variable.                                              |
 147 +-------------+----------------------------------------------------------------+
 148 | blocksize_b | is the number of bits on which are hashed by one iteration of  |
 149 |             | the nextBlock function.                                        |
 150 +-------------+----------------------------------------------------------------+
 151 | hashsize_b  | is the number of bits on which are output as final hash value. |
 152 +-------------+----------------------------------------------------------------+
 153 | init        | is a pointer to the init function.                             |
 154 +-------------+----------------------------------------------------------------+
 155 | nextBlock   | is a pointer to the algorithm specific nextBlock function.     |
 156 +-------------+----------------------------------------------------------------+
 157 | lastBlock   | is a pointer to the algorithm specific lastBlock function.     |
 158 +-------------+----------------------------------------------------------------+
 159 | ctx2hash    | is a pointer to the algorithm specific ctx2hash function.      |
 160 +-------------+----------------------------------------------------------------+
 161 | free        | is a pointer to the free function or NULL if there is no free  |
 162 |             | function.                                                      |
 163 +-------------+----------------------------------------------------------------+
 164 | mem         | is a pointer to the algorithm specific mem function. This      |
 165 |             | function hashes a complete message which has to reside         |
 166 |             | entirely in RAM. This value may be NULL if there is no such    |
 167 |             | function.                                                      |
 168 +-------------+----------------------------------------------------------------+
 169
 170 HFAL-Basic context
 171 ------------------
 172 Besides the context types for individual hash functions there is a generic context
 173 type for HFAL. This is the context to use when using HFAL based functions.
 174 The HFAL context has the following structure:
 175
 176 ::
 177
 178    typedef struct{
 179         hfdesc_t* desc_ptr;
 180         void*     ctx;
 181    } hfgen_ctx_t;
 182
 183 +----------+-----------------------------------------------+
 184 | desc_ptr | a pointer to the HFAL descriptor              |
 185 +----------+-----------------------------------------------+
 186 | ctx      | pointer to the hash function specific context |
 187 +----------+-----------------------------------------------+
 188
 189 HFAL-Basic
 190 ----------
 191 HFAL-Basic provides the basic features of an hash function on top of the
 192 HFAL. To use it you simply have to include the algorithms you want to use,
 193 the HFAL descriptor file and of course the HFAL-Basic implementation.
 194
 195 The following functions are provided:
 196
 197 ``hfal_hash_init``
 198 ~~~~~~~~~~~~~~~~~~
 199 ::
 200
 201    uint8_t hfal_hash_init(const hfdesc_t* hash_descriptor, hfgen_ctx_t* ctx)
 202
 203 this function initializes a HFAL context based on the given HFAL descriptor
 204 pointer (first parameter). The context to initialize is designated by the
 205 pointer passed as second parameter.
 206
 207 If everything works fine ``0`` is returned. In the case something fails the
 208 following codes are returned:
 209
 210 +---+-------------------------------------------------------------------+
 211 | 3 | It was not possible to allocate enough memory to hold the context |
 212 |   | variable for the selected hash function.                          |
 213 +---+-------------------------------------------------------------------+
 214
 215 ``hfal_hash_nextBlock``
 216 ~~~~~~~~~~~~~~~~~~~~~~~
 217 ::
 218
 219    void hfal_hash_nextBlock(hfgen_ctx_t* ctx, const void* block)
 220
 221 this function hashes a block of memory (of algorithm specific length) and
 222 updates the context accordingly.
 223
 224 ``hfal_hash_lastBlock``
 225 ~~~~~~~~~~~~~~~~~~~~~~~
 226 ::
 227
 228    void hfal_hash_lastBlock(hfgen_ctx_t* ctx, const void* block, uint16_t length_b)
 229
 230 this function is used to hash the last block of a message. Since messages are
 231 not required to consist of full blocks (or even full bytes) the length of the
 232 block must be given in bits. The context is updated accordingly. This function
 233 already performs padding and related stuff.
 234
 235 ``hfal_hash_ctx2hash``
 236 ~~~~~~~~~~~~~~~~~~~~~~
 237 ::
 238
 239    void hfal_hash_ctx2hash(void* dest, hfgen_ctx_t* ctx)
 240
 241 this function converts a context into an actual hash value which is stored in
 242 ``dest``. The application is responsible for allocating enough room.
 243
 244 ``hfal_hash_free``
 245 ~~~~~~~~~~~~~~~~~~
 246 ::
 247
 248    void hfal_hash_free(hfgen_ctx_t* ctx)
 249
 250 this function differs from the individual hash functions ``free`` function
 251 in that it is always provided and must be called to avoid memory holes.
 252 This function also automatically calls the implementation specific ``free``
 253 function if one is provided.
 254
 255 ``hfal_hash_mem``
 256 ~~~~~~~~~~~~~~~~~
 257 ::
 258
 259    void hfal_hash_mem(const hfdesc_t* hash_descriptor, void* dest, const void* msg, uint32_t length_b)
 260
 261 this function is always provided (even if the actual algorithm does not
 262 specify a ``mem`` function. It hashes an entire message which resides in
 263 RAM and stores the hash value in ``dest``. ``msg`` is the pointer to the
 264 message and ``length_b`` is the message length in bits.
 265
 266 ``hfal_hash_getBlocksize``
 267 ~~~~~~~~~~~~~~~~~~~~~~~~~~
 268 ::
 269
 270    uint16_t hfal_hash_getBlocksize(const hfdesc_t* hash_descriptor)
 271
 272 returns the blocksize of the described (``hash_descriptor``) hash function.
 273
 274 ``hfal_hash_getHashsize``
 275 ~~~~~~~~~~~~~~~~~~~~~~~~~
 276 ::
 277
 278    uint16_t hfal_hash_getHashsize(const hfdesc_t* hash_descriptor)
 279
 280 returns the hash value size of the described (``hash_descriptor``) hash
 281 function.
 282
 283 ``hfal_hash_getCtxsize``
 284 ~~~~~~~~~~~~~~~~~~~~~~~~
 285 ::
 286
 287    uint16_t hfal_hash_getCtxsize_B(const hfdesc_t* hash_descriptor)
 288
 289 returns the size of a context variable of the described (``hash_descriptor``)
 290 hash function.
 291
 292
 293