Merge "translate: Skip matrix_rebuild during shutdown."
[asterisk/asterisk.git] / main / sha1.c
1 /*! \file
2  *
3  * \brief Based on the RFC 6234
4  *
5  * Copyright (c) 2011 IETF Trust and the persons identified as
6  * authors of the code.  All rights reserved.
7  *
8  * Redistribution and use in source and binary forms, with or
9  * without modification, are permitted provided that the following
10  * conditions are met:
11  *
12  * - Redistributions of source code must retain the above
13  *   copyright notice, this list of conditions and
14  *   the following disclaimer.
15  *
16  * - Redistributions in binary form must reproduce the above
17  *   copyright notice, this list of conditions and the following
18  *   disclaimer in the documentation and/or other materials provided
19  *   with the distribution.
20  *
21  * - Neither the name of Internet Society, IETF or IETF Trust, nor
22  *   the names of specific contributors, may be used to endorse or
23  *   promote products derived from this software without specific
24  *   prior written permission.
25  *
26  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND
27  * CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES,
28  * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
29  * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
30  * DISCLAIMED.  IN NO EVENT SHALL THE COPYRIGHT OWNER OR
31  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
32  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
33  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
34  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
35  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
36  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
37  * OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE,
38  * EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
39  *
40  *  Description:
41  *      This file implements the Secure Hash Algorithm SHA-1
42  *      as defined in the U.S. National Institute of Standards
43  *      and Technology Federal Information Processing Standards
44  *      Publication (FIPS PUB) 180-3 published in October 2008
45  *      and formerly defined in its predecessors, FIPS PUB 180-1
46  *      and FIP PUB 180-2.
47  *
48  *      A combined document showing all algorithms is available at
49  *              http://csrc.nist.gov/publications/fips/
50  *                     fips180-3/fips180-3_final.pdf
51  *
52  *      The SHA-1 algorithm produces a 160-bit message digest for a
53  *      given data stream that can serve as a means of providing a
54  *      "fingerprint" for a message.
55  *
56  *  Portability Issues:
57  *      SHA-1 is defined in terms of 32-bit "words".  This code
58  *      uses <stdint.h> (included via "sha.h") to define 32- and
59  *      8-bit unsigned integer types.  If your C compiler does
60  *      not support 32-bit unsigned integers, this code is not
61  *      appropriate.
62  *
63  *  Caveats:
64  *      SHA-1 is designed to work with messages less than 2^64 bits
65  *      long.  This implementation uses SHA1Input() to hash the bits
66  *      that are a multiple of the size of an 8-bit octet, and then
67  *      optionally uses SHA1FinalBits() to hash the final few bits of
68  *      the input.
69  */
70
71 #include <asterisk/sha1.h>
72
73 /*! Define the SHA1 circular left shift macro */
74 #define SHA1_ROTL(bits,word) \
75                 (((word) << (bits)) | ((word) >> (32-(bits))))
76
77 /*
78  * Add "length" to the length.
79  * Set Corrupted when overflow has occurred.
80  */
81 static uint32_t addTemp;
82 #define SHA1AddLength(context, length)                     \
83     (addTemp = (context)->Length_Low,                      \
84      (context)->Corrupted =                                \
85         (((context)->Length_Low += (length)) < addTemp) && \
86         (++(context)->Length_High == 0) ? shaInputTooLong  \
87                                         : (context)->Corrupted )
88
89 /* Local Function Prototypes */
90 static void SHA1ProcessMessageBlock(SHA1Context * context);
91 static void SHA1Finalize(SHA1Context * context, uint8_t Pad_Byte);
92 static void SHA1PadMessage(SHA1Context * context, uint8_t Pad_Byte);
93
94 /*!
95  * \brief SHA1Reset
96  * \param context the context to be reset.
97  * This function will initialize the SHA1Context in preparation
98  * for computing a new SHA1 message digest.
99  * \return sha Error Code.
100  */
101 int SHA1Reset(SHA1Context *context)
102 {
103         if (!context) {
104                 return shaNull;
105         }
106
107         context->Length_High = context->Length_Low = 0;
108         context->Message_Block_Index = 0;
109
110         /* Initial Hash Values: FIPS 180-3 section 5.3.1 */
111         context->Intermediate_Hash[0] = 0x67452301;
112         context->Intermediate_Hash[1] = 0xEFCDAB89;
113         context->Intermediate_Hash[2] = 0x98BADCFE;
114         context->Intermediate_Hash[3] = 0x10325476;
115         context->Intermediate_Hash[4] = 0xC3D2E1F0;
116
117         context->Computed = 0;
118         context->Corrupted = shaSuccess;
119
120         return shaSuccess;
121 }
122
123 /*!
124  *  \brief SHA1Input
125  * \param context [in/out] The SHA context to update
126  * \param message_array [in] An array of characters representing the next portion of
127  *                 the message.
128  * \param length [in] The length of the message in message_array.
129  *  This function accepts an array of octets as the next portion
130  *  of the message.
131  * \return sha Error Code.
132  */
133 int SHA1Input(SHA1Context *context,
134                           const uint8_t *message_array, unsigned length)
135 {
136         if (!context) {
137                 return shaNull;
138         }
139         if (!length) {
140                 return shaSuccess;
141         }
142         if (!message_array) {
143                 return shaNull;
144         }
145
146         if (context->Computed) {
147                 context->Corrupted = shaStateError;
148                 return shaStateError;
149         }
150
151         if (context->Corrupted) {
152                 return context->Corrupted;
153         }
154
155         while (length--) {
156                 context->Message_Block[context->Message_Block_Index++] =
157                         *message_array;
158
159                 if ((SHA1AddLength(context, 8) == shaSuccess) &&
160                         (context->Message_Block_Index == SHA1_Message_Block_Size))
161                         SHA1ProcessMessageBlock(context);
162
163                 message_array++;
164         }
165
166         return context->Corrupted;
167 }
168
169 /*!
170  * \brief SHA1FinalBits Add in any final bits of the message.
171  *
172  * \param context [in/out] The SHA context to update.
173  * \param message_bits [in] The final bits of the message, in the upper portion of the
174  *     byte.  (Use 0b###00000 instead of 0b00000### to input the
175  *     three bits ###.)
176  * \param length [in] *     The number of bits in message_bits, between 1 and 7.
177  * \returns sha Error Code.
178  */
179 int SHA1FinalBits(SHA1Context * context, uint8_t message_bits,
180                                   unsigned int length)
181 {
182         static uint8_t masks[8] = {
183                 /* 0 0b00000000 */ 0x00, /* 1 0b10000000 */ 0x80,
184                 /* 2 0b11000000 */ 0xC0, /* 3 0b11100000 */ 0xE0,
185                 /* 4 0b11110000 */ 0xF0, /* 5 0b11111000 */ 0xF8,
186                 /* 6 0b11111100 */ 0xFC, /* 7 0b11111110 */ 0xFE
187         };
188
189         static uint8_t markbit[8] = {
190                 /* 0 0b10000000 */ 0x80, /* 1 0b01000000 */ 0x40,
191                 /* 2 0b00100000 */ 0x20, /* 3 0b00010000 */ 0x10,
192                 /* 4 0b00001000 */ 0x08, /* 5 0b00000100 */ 0x04,
193                 /* 6 0b00000010 */ 0x02, /* 7 0b00000001 */ 0x01
194         };
195
196         if (!context)
197                 return shaNull;
198         if (!length)
199                 return shaSuccess;
200         if (context->Corrupted)
201                 return context->Corrupted;
202         if (context->Computed)
203                 return context->Corrupted = shaStateError;
204         if (length >= 8)
205                 return context->Corrupted = shaBadParam;
206
207         SHA1AddLength(context, length);
208         SHA1Finalize(context,
209                                  (uint8_t) ((message_bits & masks[length]) |
210                                                         markbit[length]));
211
212         return context->Corrupted;
213 }
214
215 /*
216  * \brief SHA1Result Returns the resulting 160-bit digest
217  * \param context [in/out] The SHA context to update.
218  * \param Message_Digest [out] Where the digest is returned.
219  *
220  *   This function will return the 160-bit message digest
221  *   into the Message_Digest array provided by the caller.
222  * \note The first octet of hash is stored in the element with index 0,
223  *       the last octet of hash in the element with index 19.
224  * \returns sha Error Code.
225  */
226 int SHA1Result(SHA1Context * context, uint8_t Message_Digest[SHA1HashSize])
227 {
228         int i;
229
230         if (!context) {
231                 return shaNull;
232         }
233         if (!Message_Digest) {
234                 return shaNull;
235         }
236         if (context->Corrupted) {
237                 return context->Corrupted;
238         }
239
240         if (!context->Computed) {
241                 SHA1Finalize(context, 0x80);
242         }
243
244         for (i = 0; i < SHA1HashSize; ++i) {
245                 Message_Digest[i] = (uint8_t) (context->Intermediate_Hash[i >> 2]
246                                 >> (8 * (3 - (i & 0x03))));
247         }
248
249         return shaSuccess;
250 }
251
252 /*!
253  * \brief Process the next 512 bits of the message stored in the Message_Block array.
254  * \param context [in/out] The SHA context to update
255  * \note  Many of the variable names in this code, especially the
256  *        single character names, were used because those were the
257  *        names used in the publication.
258  * \returns nothing.
259  */
260 static void SHA1ProcessMessageBlock(SHA1Context *context)
261 {
262         /* Constants defined in FIPS 180-3, section 4.2.1 */
263         const uint32_t K[4] = {
264                 0x5A827999, 0x6ED9EBA1, 0x8F1BBCDC, 0xCA62C1D6
265         };
266         int t;                                          /* Loop counter */
267         uint32_t temp;                          /* Temporary word value */
268         uint32_t W[80];                         /* Word sequence */
269         uint32_t A, B, C, D, E;         /* Word buffers */
270
271         /*
272          * Initialize the first 16 words in the array W
273          */
274         for (t = 0; t < 16; t++) {
275                 W[t] = ((uint32_t) context->Message_Block[t * 4]) << 24;
276                 W[t] |= ((uint32_t) context->Message_Block[t * 4 + 1]) << 16;
277                 W[t] |= ((uint32_t) context->Message_Block[t * 4 + 2]) << 8;
278                 W[t] |= ((uint32_t) context->Message_Block[t * 4 + 3]);
279         }
280
281         for (t = 16; t < 80; t++) {
282                 W[t] = SHA1_ROTL(1, W[t - 3] ^ W[t - 8] ^ W[t - 14] ^ W[t - 16]);
283         }
284
285         A = context->Intermediate_Hash[0];
286         B = context->Intermediate_Hash[1];
287         C = context->Intermediate_Hash[2];
288         D = context->Intermediate_Hash[3];
289         E = context->Intermediate_Hash[4];
290
291         for (t = 0; t < 20; t++) {
292                 temp = SHA1_ROTL(5, A) + SHA_Ch(B, C, D) + E + W[t] + K[0];
293                 E = D;
294                 D = C;
295                 C = SHA1_ROTL(30, B);
296                 B = A;
297                 A = temp;
298         }
299
300         for (t = 20; t < 40; t++) {
301                 temp = SHA1_ROTL(5, A) + SHA_Parity(B, C, D) + E + W[t] + K[1];
302                 E = D;
303                 D = C;
304                 C = SHA1_ROTL(30, B);
305                 B = A;
306                 A = temp;
307         }
308
309         for (t = 40; t < 60; t++) {
310                 temp = SHA1_ROTL(5, A) + SHA_Maj(B, C, D) + E + W[t] + K[2];
311                 E = D;
312                 D = C;
313                 C = SHA1_ROTL(30, B);
314                 B = A;
315                 A = temp;
316         }
317
318         for (t = 60; t < 80; t++) {
319                 temp = SHA1_ROTL(5, A) + SHA_Parity(B, C, D) + E + W[t] + K[3];
320                 E = D;
321                 D = C;
322                 C = SHA1_ROTL(30, B);
323                 B = A;
324                 A = temp;
325         }
326
327         context->Intermediate_Hash[0] += A;
328         context->Intermediate_Hash[1] += B;
329         context->Intermediate_Hash[2] += C;
330         context->Intermediate_Hash[3] += D;
331         context->Intermediate_Hash[4] += E;
332
333         context->Message_Block_Index = 0;
334 }
335
336 /*!
337  * \brief This helper function finishes off the digest calculations.
338  * \param context [in/out]  The context to pad.
339  * \param Pad_Byte [in]  The last byte to add to the message block
340  *     before the 0-padding and length.  This will contain the last
341  *     bits of the message followed by another single bit.  If the
342  *     message was an exact multiple of 8-bits long, Pad_Byte will
343  *     be 0x80.
344  * \returns sha Error Code.
345  */
346 static void SHA1Finalize(SHA1Context * context, uint8_t Pad_Byte)
347 {
348         int i;
349         SHA1PadMessage(context, Pad_Byte);
350         /* message may be sensitive, clear it out */
351         for (i = 0; i < SHA1_Message_Block_Size; ++i) {
352                 context->Message_Block[i] = 0;
353         }
354         context->Length_High = 0;       /* and clear length */
355         context->Length_Low = 0;
356         context->Computed = 1;
357 }
358
359 /*!
360  * \brief Pad message to be 512 bits.
361  * \param context [in/out]  The context to pad.
362  * \param Pad_Byte [in]  Last padding byte.
363  *
364  *  According to the standard, the message must be padded to the next
365  *  even multiple of 512 bits.  The first padding bit must be a '1'.
366  *  The last 64 bits represent the length of the original message.
367  *  All bits in between should be 0.  This helper function will pad
368  *  the message according to those rules by filling the Message_Block
369  *  array accordingly.  When it returns, it can be assumed that the
370  *  message digest has been computed.
371  *
372  * \returns nothing.
373  */
374 static void SHA1PadMessage(SHA1Context * context, uint8_t Pad_Byte)
375 {
376         /*
377          *  Check to see if the current message block is too small to hold
378          *  the initial padding bits and length.  If so, we will pad the
379          *  block, process it, and then continue padding into a second
380          *  block.
381          */
382         if (context->Message_Block_Index >= (SHA1_Message_Block_Size - 8)) {
383                 context->Message_Block[context->Message_Block_Index++] = Pad_Byte;
384                 while (context->Message_Block_Index < SHA1_Message_Block_Size) {
385                         context->Message_Block[context->Message_Block_Index++] = 0;
386                 }
387
388                 SHA1ProcessMessageBlock(context);
389         } else
390                 context->Message_Block[context->Message_Block_Index++] = Pad_Byte;
391
392         while (context->Message_Block_Index < (SHA1_Message_Block_Size - 8)) {
393                 context->Message_Block[context->Message_Block_Index++] = 0;
394         }
395
396         /*
397          *  Store the message length as the last 8 octets
398          */
399         context->Message_Block[56] = (uint8_t) (context->Length_High >> 24);
400         context->Message_Block[57] = (uint8_t) (context->Length_High >> 16);
401         context->Message_Block[58] = (uint8_t) (context->Length_High >> 8);
402         context->Message_Block[59] = (uint8_t) (context->Length_High);
403         context->Message_Block[60] = (uint8_t) (context->Length_Low >> 24);
404         context->Message_Block[61] = (uint8_t) (context->Length_Low >> 16);
405         context->Message_Block[62] = (uint8_t) (context->Length_Low >> 8);
406         context->Message_Block[63] = (uint8_t) (context->Length_Low);
407
408         SHA1ProcessMessageBlock(context);
409 }