initially checkin
[gnupg.git] / cipher / rmd160.c
1 /* rmd160.c  -  RIPE-MD160
2  *      Copyright (c) 1997 by Werner Koch (dd9jn)
3  *
4  * This file is part of G10.
5  *
6  * G10 is free software; you can redistribute it and/or modify
7  * it under the terms of the GNU General Public License as published by
8  * the Free Software Foundation; either version 2 of the License, or
9  * (at your option) any later version.
10  *
11  * G10 is distributed in the hope that it will be useful,
12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14  * GNU General Public License for more details.
15  *
16  * You should have received a copy of the GNU General Public License
17  * along with this program; if not, write to the Free Software
18  * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA
19  */
20
21 #include <config.h>
22 #include <stdio.h>
23 #include <stdlib.h>
24 #include <string.h>
25 #include <assert.h>
26 #include "util.h"
27 #include "memory.h"
28 #include "rmd.h"
29
30 /*********************************
31  * RIPEMD-160 is not patented, see (as of 25.10.97)
32  *   http://www.esat.kuleuven.ac.be/~bosselae/ripemd160.html
33  * Note that the code uses Little Endian byteorder, which is good for
34  * 386 etc, but we must add some conversion when used on a big endian box.
35  *
36  *
37  * Pseudo-code for RIPEMD-160
38  *
39  * RIPEMD-160 is an iterative hash function that operates on 32-bit words.
40  * The round function takes as input a 5-word chaining variable and a 16-word
41  * message block and maps this to a new chaining variable. All operations are
42  * defined on 32-bit words. Padding is identical to that of MD4.
43  *
44  *
45  * RIPEMD-160: definitions
46  *
47  *
48  *   nonlinear functions at bit level: exor, mux, -, mux, -
49  *
50  *   f(j, x, y, z) = x XOR y XOR z                (0 <= j <= 15)
51  *   f(j, x, y, z) = (x AND y) OR (NOT(x) AND z)  (16 <= j <= 31)
52  *   f(j, x, y, z) = (x OR NOT(y)) XOR z          (32 <= j <= 47)
53  *   f(j, x, y, z) = (x AND z) OR (y AND NOT(z))  (48 <= j <= 63)
54  *   f(j, x, y, z) = x XOR (y OR NOT(z))          (64 <= j <= 79)
55  *
56  *
57  *   added constants (hexadecimal)
58  *
59  *   K(j) = 0x00000000      (0 <= j <= 15)
60  *   K(j) = 0x5A827999     (16 <= j <= 31)      int(2**30 x sqrt(2))
61  *   K(j) = 0x6ED9EBA1     (32 <= j <= 47)      int(2**30 x sqrt(3))
62  *   K(j) = 0x8F1BBCDC     (48 <= j <= 63)      int(2**30 x sqrt(5))
63  *   K(j) = 0xA953FD4E     (64 <= j <= 79)      int(2**30 x sqrt(7))
64  *   K'(j) = 0x50A28BE6     (0 <= j <= 15)      int(2**30 x cbrt(2))
65  *   K'(j) = 0x5C4DD124    (16 <= j <= 31)      int(2**30 x cbrt(3))
66  *   K'(j) = 0x6D703EF3    (32 <= j <= 47)      int(2**30 x cbrt(5))
67  *   K'(j) = 0x7A6D76E9    (48 <= j <= 63)      int(2**30 x cbrt(7))
68  *   K'(j) = 0x00000000    (64 <= j <= 79)
69  *
70  *
71  *   selection of message word
72  *
73  *   r(j)      = j                    (0 <= j <= 15)
74  *   r(16..31) = 7, 4, 13, 1, 10, 6, 15, 3, 12, 0, 9, 5, 2, 14, 11, 8
75  *   r(32..47) = 3, 10, 14, 4, 9, 15, 8, 1, 2, 7, 0, 6, 13, 11, 5, 12
76  *   r(48..63) = 1, 9, 11, 10, 0, 8, 12, 4, 13, 3, 7, 15, 14, 5, 6, 2
77  *   r(64..79) = 4, 0, 5, 9, 7, 12, 2, 10, 14, 1, 3, 8, 11, 6, 15, 13
78  *   r0(0..15) = 5, 14, 7, 0, 9, 2, 11, 4, 13, 6, 15, 8, 1, 10, 3, 12
79  *   r0(16..31)= 6, 11, 3, 7, 0, 13, 5, 10, 14, 15, 8, 12, 4, 9, 1, 2
80  *   r0(32..47)= 15, 5, 1, 3, 7, 14, 6, 9, 11, 8, 12, 2, 10, 0, 4, 13
81  *   r0(48..63)= 8, 6, 4, 1, 3, 11, 15, 0, 5, 12, 2, 13, 9, 7, 10, 14
82  *   r0(64..79)= 12, 15, 10, 4, 1, 5, 8, 7, 6, 2, 13, 14, 0, 3, 9, 11
83  *
84  *
85  *   amount for rotate left (rol)
86  *
87  *   s(0..15)  = 11, 14, 15, 12, 5, 8, 7, 9, 11, 13, 14, 15, 6, 7, 9, 8
88  *   s(16..31) = 7, 6, 8, 13, 11, 9, 7, 15, 7, 12, 15, 9, 11, 7, 13, 12
89  *   s(32..47) = 11, 13, 6, 7, 14, 9, 13, 15, 14, 8, 13, 6, 5, 12, 7, 5
90  *   s(48..63) = 11, 12, 14, 15, 14, 15, 9, 8, 9, 14, 5, 6, 8, 6, 5, 12
91  *   s(64..79) = 9, 15, 5, 11, 6, 8, 13, 12, 5, 12, 13, 14, 11, 8, 5, 6
92  *   s'(0..15) = 8, 9, 9, 11, 13, 15, 15, 5, 7, 7, 8, 11, 14, 14, 12, 6
93  *   s'(16..31)= 9, 13, 15, 7, 12, 8, 9, 11, 7, 7, 12, 7, 6, 15, 13, 11
94  *   s'(32..47)= 9, 7, 15, 11, 8, 6, 6, 14, 12, 13, 5, 14, 13, 13, 7, 5
95  *   s'(48..63)= 15, 5, 8, 11, 14, 14, 6, 14, 6, 9, 12, 9, 12, 5, 15, 8
96  *   s'(64..79)= 8, 5, 12, 9, 12, 5, 14, 6, 8, 13, 6, 5, 15, 13, 11, 11
97  *
98  *
99  *   initial value (hexadecimal)
100  *
101  *   h0 = 0x67452301; h1 = 0xEFCDAB89; h2 = 0x98BADCFE; h3 = 0x10325476;
102  *                                                      h4 = 0xC3D2E1F0;
103  *
104  *
105  * RIPEMD-160: pseudo-code
106  *
107  *   It is assumed that the message after padding consists of t 16-word blocks
108  *   that will be denoted with X[i][j], with 0 <= i <= t-1 and 0 <= j <= 15.
109  *   The symbol [+] denotes addition modulo 2**32 and rol_s denotes cyclic left
110  *   shift (rotate) over s positions.
111  *
112  *
113  *   for i := 0 to t-1 {
114  *       A := h0; B := h1; C := h2; D = h3; E = h4;
115  *       A' := h0; B' := h1; C' := h2; D' = h3; E' = h4;
116  *       for j := 0 to 79 {
117  *           T := rol_s(j)(A [+] f(j, B, C, D) [+] X[i][r(j)] [+] K(j)) [+] E;
118  *           A := E; E := D; D := rol_10(C); C := B; B := T;
119  *           T := rol_s'(j)(A' [+] f(79-j, B', C', D') [+] X[i][r'(j)]
120                                                        [+] K'(j)) [+] E';
121  *           A' := E'; E' := D'; D' := rol_10(C'); C' := B'; B' := T;
122  *       }
123  *       T := h1 [+] C [+] D'; h1 := h2 [+] D [+] E'; h2 := h3 [+] E [+] A';
124  *       h3 := h4 [+] A [+] B'; h4 := h0 [+] B [+] C'; h0 := T;
125  *   }
126  */
127
128 /* Some examples:
129  * ""                    9c1185a5c5e9fc54612808977ee8f548b2258d31
130  * "a"                   0bdc9d2d256b3ee9daae347be6f4dc835a467ffe
131  * "abc"                 8eb208f7e05d987a9b044a8e98c6b087f15a0bfc
132  * "message digest"      5d0689ef49d2fae572b881b123a85ffa21595f36
133  * "a...z"               f71c27109c692c1b56bbdceb5b9d2865b3708dbc
134  * "abcdbcde...nopq"     12a053384a9c0c88e405a06c27dcf49ada62eb2b
135  * "A...Za...z0...9"     b0e20b6e3116640286ed3a87a5713079b21f5189
136  * 8 times "1234567890"  9b752e45573d4b39f4dbd3323cab82bf63326bfb
137  * 1 million times "a"   52783243c1697bdbe16d37f97f68f08325dc1528
138  */
139
140
141 static void
142 initialize( RMDHANDLE hd )
143 {
144     hd->h0 = 0x67452301;
145     hd->h1 = 0xEFCDAB89;
146     hd->h2 = 0x98BADCFE;
147     hd->h3 = 0x10325476;
148     hd->h4 = 0xC3D2E1F0;
149     hd->bufcount = 0;
150     hd->nblocks = 0;
151 }
152
153
154 /****************
155  * Transform the message X which consists of 16 32-bit-words
156  */
157 static void
158 transform( RMDHANDLE hd, u32 *x )
159 {
160     static int r[80] = {
161         0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15,
162         7, 4, 13, 1, 10, 6, 15, 3, 12, 0, 9, 5, 2, 14, 11, 8,
163         3, 10, 14, 4, 9, 15, 8, 1, 2, 7, 0, 6, 13, 11, 5, 12,
164         1, 9, 11, 10, 0, 8, 12, 4, 13, 3, 7, 15, 14, 5, 6, 2,
165         4, 0, 5, 9, 7, 12, 2, 10, 14, 1, 3, 8, 11, 6, 15, 13 };
166     static int rr[80] = {
167         5, 14, 7, 0, 9, 2, 11, 4, 13, 6, 15, 8, 1, 10, 3, 12,
168         6, 11, 3, 7, 0, 13, 5, 10, 14, 15, 8, 12, 4, 9, 1, 2,
169         15, 5, 1, 3, 7, 14, 6, 9, 11, 8, 12, 2, 10, 0, 4, 13,
170         8, 6, 4, 1, 3, 11, 15, 0, 5, 12, 2, 13, 9, 7, 10, 14,
171         12, 15, 10, 4, 1, 5, 8, 7, 6, 2, 13, 14, 0, 3, 9, 11 };
172     static int s[80] = {
173         11, 14, 15, 12, 5, 8, 7, 9, 11, 13, 14, 15, 6, 7, 9, 8,
174         7, 6, 8, 13, 11, 9, 7, 15, 7, 12, 15, 9, 11, 7, 13, 12,
175         11, 13, 6, 7, 14, 9, 13, 15, 14, 8, 13, 6, 5, 12, 7, 5,
176         11, 12, 14, 15, 14, 15, 9, 8, 9, 14, 5, 6, 8, 6, 5, 12,
177         9, 15, 5, 11, 6, 8, 13, 12, 5, 12, 13, 14, 11, 8, 5, 6  };
178     static int ss[80] = {
179         8, 9, 9, 11, 13, 15, 15, 5, 7, 7, 8, 11, 14, 14, 12, 6,
180         9, 13, 15, 7, 12, 8, 9, 11, 7, 7, 12, 7, 6, 15, 13, 11,
181         9, 7, 15, 11, 8, 6, 6, 14, 12, 13, 5, 14, 13, 13, 7, 5,
182         15, 5, 8, 11, 14, 14, 6, 14, 6, 9, 12, 9, 12, 5, 15, 8,
183         8, 5, 12, 9, 12, 5, 14, 6, 8, 13, 6, 5, 15, 13, 11, 11  };
184     u32 a,b,c,d,e,aa,bb,cc,dd,ee,t;
185     int rbits, j;
186
187 #define K(a)   ( (a) < 16 ? 0x00000000 :              \
188                  (a) < 32 ? 0x5A827999 :              \
189                  (a) < 48 ? 0x6ED9EBA1 :              \
190                  (a) < 64 ? 0x8F1BBCDC : 0xA953FD4E )
191 #define KK(a)  ( (a) < 16 ? 0x50A28BE6 :              \
192                  (a) < 32 ? 0x5C4DD124 :              \
193                  (a) < 48 ? 0x6D703EF3 :              \
194                  (a) < 64 ? 0x7A6D76E9 : 0x00000000 )
195
196 #define F0(x,y,z)   ( (x) ^ (y) ^ (z) )
197 #define F1(x,y,z)   ( ((x) & (y)) | (~(x) & (z)) )
198 #define F2(x,y,z)   ( ((x) | ~(y)) ^ (z) )
199 #define F3(x,y,z)   ( ((x) & (z)) | ((y) & ~(z)) )
200 #define F4(x,y,z)   ( (x) ^ ((y) | ~(z)) )
201 #define F(a,x,y,z)  ( (a) < 16 ? F0((x),(y),(z)) : \
202                       (a) < 32 ? F1((x),(y),(z)) : \
203                       (a) < 48 ? F2((x),(y),(z)) : \
204                       (a) < 64 ? F3((x),(y),(z)) : \
205                                  F4((x),(y),(z)) )
206
207 #define rol(n,x) ( ((x) << (n)) | ((x) >> (32-(n))) )
208
209     a = aa = hd->h0;
210     b = bb = hd->h1;
211     c = cc = hd->h2;
212     d = dd = hd->h3;
213     e = ee = hd->h4;
214
215     for(j=0; j < 80; j++ ) {
216         t = a + F( j, b, c, d ) + x[ r[j] ] + K(j);
217         rbits = s[j];
218         a = rol(rbits, t) + e;
219         c = rol(10,c);
220         t = a; a = e; e = d; d = c; c = b; b = t;
221
222         t = aa + F(79-j, bb, cc, dd ) + x[ rr[j] ] + KK(j);
223         rbits = ss[j];
224         aa = rol(rbits, t) + ee;
225         cc = rol(10,cc);
226         t = aa; aa = ee; ee = dd; dd = cc; cc = bb; bb = t;
227     }
228
229     t      = hd->h1 + c + dd;
230     hd->h1 = hd->h2 + d + ee;
231     hd->h2 = hd->h3 + e + aa;
232     hd->h3 = hd->h4 + a + bb;
233     hd->h4 = hd->h0 + b + cc;
234     hd->h0 = t;
235 }
236
237
238
239
240 RMDHANDLE
241 rmd160_open( int secure )
242 {
243     RMDHANDLE hd;
244
245     hd = secure? m_alloc_secure( sizeof *hd )
246                : m_alloc( sizeof *hd );
247     initialize(hd);
248     return hd;
249 }
250
251
252 RMDHANDLE
253 rmd160_copy( RMDHANDLE a )
254 {
255     RMDHANDLE b;
256
257     assert(a);
258     b = m_is_secure(a)? m_alloc_secure( sizeof *b )
259                       : m_alloc( sizeof *b );
260     memcpy( b, a, sizeof *a );
261     return b;
262 }
263
264 void
265 rmd160_close(RMDHANDLE hd)
266 {
267     if( hd )
268         m_free(hd);
269 }
270
271
272
273 /* Update the message digest with the contents
274  * of INBUF with length INLEN.
275  */
276 void
277 rmd160_write( RMDHANDLE hd, byte *inbuf, size_t inlen)
278 {
279     if( hd->bufcount == 64 ) { /* flush the buffer */
280         transform( hd, (u32*)hd->buffer );
281         hd->bufcount = 0;
282         hd->nblocks++;
283     }
284     if( !inbuf )
285         return;
286     if( hd->bufcount ) {
287         for( ; inlen && hd->bufcount < 64; inlen-- )
288             hd->buffer[hd->bufcount++] = *inbuf++;
289         rmd160_write( hd, NULL, 0 );
290         if( !inlen )
291             return;
292     }
293
294     while( inlen >= 64 ) {
295         transform( hd, (u32*)inbuf );
296         hd->bufcount = 0;
297         hd->nblocks++;
298         inlen -= 64;
299         inbuf += 64;
300     }
301     for( ; inlen && hd->bufcount < 64; inlen-- )
302         hd->buffer[hd->bufcount++] = *inbuf++;
303 }
304
305
306 /* The routine final terminates the computation and
307  * returns the digest.
308  * The handle is prepared for a new cycle, but adding bytes to the
309  * handle will the destroy the returned buffer.
310  * Returns: 20 bytes representing the digest.
311  */
312
313 byte *
314 rmd160_final(RMDHANDLE hd)
315 {
316     u32 t, msb, lsb;
317     byte *p;
318
319     rmd160_write(hd, NULL, 0); /* flush */;
320
321     msb = 0;
322     t = hd->nblocks;
323     if( (lsb = t << 6) < t ) /* multiply by 64 to make a byte count */
324         msb++;
325     msb += t >> 26;
326     t = lsb;
327     if( (lsb = t + hd->bufcount) < t ) /* add the bufcount */
328         msb++;
329     t = lsb;
330     if( (lsb = t << 3) < t ) /* multiply by 8 to make a bit count */
331         msb++;
332     msb += t >> 29;
333
334     if( hd->bufcount < 56 ) { /* enough room */
335         hd->buffer[hd->bufcount++] = 0x80; /* pad */
336         while( hd->bufcount < 56 )
337             hd->buffer[hd->bufcount++] = 0;  /* pad */
338     }
339     else { /* need one extra block */
340         hd->buffer[hd->bufcount++] = 0x80; /* pad character */
341         while( hd->bufcount < 64 )
342             hd->buffer[hd->bufcount++] = 0;
343         rmd160_write(hd, NULL, 0);  /* flush */;
344         memset(hd->buffer, 0, 56 ); /* fill next block with zeroes */
345     }
346     /* append the 64 bit count */
347     hd->buffer[56] = lsb      ;
348     hd->buffer[57] = lsb >>  8;
349     hd->buffer[58] = lsb >> 16;
350     hd->buffer[59] = lsb >> 24;
351     hd->buffer[60] = msb      ;
352     hd->buffer[61] = msb >>  8;
353     hd->buffer[62] = msb >> 16;
354     hd->buffer[63] = msb >> 24;
355     transform( hd, (u32*)hd->buffer );
356
357     p = hd->buffer;
358   #ifdef HAVE_BIG_ENDIAN
359     #define X(a) do { *p++ = hd->h##a >> 24; *p++ = hd->h##a >> 16;      \
360                         *p++ = hd->h##a >> 8; *p++ = hd->h##a; } while(0)
361   #else /* little endian */
362     #define X(a) do { *(u32*)p = hd->h##a ; p += 4; } while(0)
363   #endif
364     X(0);
365     X(1);
366     X(2);
367     X(3);
368     X(4);
369   #undef X
370
371     initialize( hd );   /* prepare for next cycle */
372     return hd->buffer; /* now contains the digest */
373 }
374
375