]> git.cryptolib.org Git - avr-crypto-lib.git/blob - doc/hashes.rst
new hashes documentation in reStructuredText-format
[avr-crypto-lib.git] / 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