a couple of changes; but some parts are now broken
[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 void
142 rmd160_init( RMD160_CONTEXT *hd )
143 {
144     hd->h0 = 0x67452301;
145     hd->h1 = 0xEFCDAB89;
146     hd->h2 = 0x98BADCFE;
147     hd->h3 = 0x10325476;
148     hd->h4 = 0xC3D2E1F0;
149     hd->nblocks = 0;
150     hd->count = 0;
151 }
152
153
154 #if defined(__GNUC__) && defined(__i386__)
155 static inline u32
156 rol(int n, u32 x)
157 {
158         __asm__("roll %%cl,%0"
159                 :"=r" (x)
160                 :"0" (x),"c" (n));
161         return x;
162 }
163 #else
164   #define rol(n,x) ( ((x) << (n)) | ((x) >> (32-(n))) )
165 #endif
166
167
168 /****************
169  * Transform the message X which consists of 16 32-bit-words
170  */
171 static void
172 transform( RMD160_CONTEXT *hd, byte *data )
173 {
174     static int r[80] = {
175         0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15,
176         7, 4, 13, 1, 10, 6, 15, 3, 12, 0, 9, 5, 2, 14, 11, 8,
177         3, 10, 14, 4, 9, 15, 8, 1, 2, 7, 0, 6, 13, 11, 5, 12,
178         1, 9, 11, 10, 0, 8, 12, 4, 13, 3, 7, 15, 14, 5, 6, 2,
179         4, 0, 5, 9, 7, 12, 2, 10, 14, 1, 3, 8, 11, 6, 15, 13 };
180     static int rr[80] = {
181         5, 14, 7, 0, 9, 2, 11, 4, 13, 6, 15, 8, 1, 10, 3, 12,
182         6, 11, 3, 7, 0, 13, 5, 10, 14, 15, 8, 12, 4, 9, 1, 2,
183         15, 5, 1, 3, 7, 14, 6, 9, 11, 8, 12, 2, 10, 0, 4, 13,
184         8, 6, 4, 1, 3, 11, 15, 0, 5, 12, 2, 13, 9, 7, 10, 14,
185         12, 15, 10, 4, 1, 5, 8, 7, 6, 2, 13, 14, 0, 3, 9, 11 };
186     static int s[80] = {
187         11, 14, 15, 12, 5, 8, 7, 9, 11, 13, 14, 15, 6, 7, 9, 8,
188         7, 6, 8, 13, 11, 9, 7, 15, 7, 12, 15, 9, 11, 7, 13, 12,
189         11, 13, 6, 7, 14, 9, 13, 15, 14, 8, 13, 6, 5, 12, 7, 5,
190         11, 12, 14, 15, 14, 15, 9, 8, 9, 14, 5, 6, 8, 6, 5, 12,
191         9, 15, 5, 11, 6, 8, 13, 12, 5, 12, 13, 14, 11, 8, 5, 6  };
192     static int ss[80] = {
193         8, 9, 9, 11, 13, 15, 15, 5, 7, 7, 8, 11, 14, 14, 12, 6,
194         9, 13, 15, 7, 12, 8, 9, 11, 7, 7, 12, 7, 6, 15, 13, 11,
195         9, 7, 15, 11, 8, 6, 6, 14, 12, 13, 5, 14, 13, 13, 7, 5,
196         15, 5, 8, 11, 14, 14, 6, 14, 6, 9, 12, 9, 12, 5, 15, 8,
197         8, 5, 12, 9, 12, 5, 14, 6, 8, 13, 6, 5, 15, 13, 11, 11  };
198     u32 a,b,c,d,e,aa,bb,cc,dd,ee,t;
199     int rbits, j;
200   #ifdef BIG_ENDIAN_HOST
201     u32 x[16];
202   #else
203     u32 *x;
204   #endif
205
206 #define K(a)   ( (a) < 16 ? 0x00000000 :              \
207                  (a) < 32 ? 0x5A827999 :              \
208                  (a) < 48 ? 0x6ED9EBA1 :              \
209                  (a) < 64 ? 0x8F1BBCDC : 0xA953FD4E )
210 #define KK(a)  ( (a) < 16 ? 0x50A28BE6 :              \
211                  (a) < 32 ? 0x5C4DD124 :              \
212                  (a) < 48 ? 0x6D703EF3 :              \
213                  (a) < 64 ? 0x7A6D76E9 : 0x00000000 )
214
215 #define F0(x,y,z)   ( (x) ^ (y) ^ (z) )
216 #define F1(x,y,z)   ( ((x) & (y)) | (~(x) & (z)) )
217 #define F2(x,y,z)   ( ((x) | ~(y)) ^ (z) )
218 #define F3(x,y,z)   ( ((x) & (z)) | ((y) & ~(z)) )
219 #define F4(x,y,z)   ( (x) ^ ((y) | ~(z)) )
220 #define F(a,x,y,z)  ( (a) < 16 ? F0((x),(y),(z)) : \
221                       (a) < 32 ? F1((x),(y),(z)) : \
222                       (a) < 48 ? F2((x),(y),(z)) : \
223                       (a) < 64 ? F3((x),(y),(z)) : \
224                                  F4((x),(y),(z)) )
225
226   #ifdef BIG_ENDIAN_HOST
227     { int i;
228       byte *p2, *p1;
229       for(i=0, p1=data, p2=(byte*)x; i < 16; i++, p2 += 4 ) {
230         p2[3] = *p1++;
231         p2[2] = *p1++;
232         p2[1] = *p1++;
233         p2[0] = *p1++;
234       }
235     }
236   #else
237     x = (u32*)data;
238   #endif
239
240     a = aa = hd->h0;
241     b = bb = hd->h1;
242     c = cc = hd->h2;
243     d = dd = hd->h3;
244     e = ee = hd->h4;
245
246     for(j=0; j < 80; j++ ) {
247         t = a + F( j, b, c, d ) + x[ r[j] ] + K(j);
248         rbits = s[j];
249         a = rol(rbits, t) + e;
250         c = rol(10,c);
251         t = a; a = e; e = d; d = c; c = b; b = t;
252
253         t = aa + F(79-j, bb, cc, dd ) + x[ rr[j] ] + KK(j);
254         rbits = ss[j];
255         aa = rol(rbits, t) + ee;
256         cc = rol(10,cc);
257         t = aa; aa = ee; ee = dd; dd = cc; cc = bb; bb = t;
258     }
259
260     t      = hd->h1 + c + dd;
261     hd->h1 = hd->h2 + d + ee;
262     hd->h2 = hd->h3 + e + aa;
263     hd->h3 = hd->h4 + a + bb;
264     hd->h4 = hd->h0 + b + cc;
265     hd->h0 = t;
266 }
267
268
269
270 /* Update the message digest with the contents
271  * of INBUF with length INLEN.
272  */
273 void
274 rmd160_write( RMD160_CONTEXT *hd, byte *inbuf, size_t inlen)
275 {
276     if( hd->count == 64 ) { /* flush the buffer */
277         transform( hd, hd->buf );
278         hd->count = 0;
279         hd->nblocks++;
280     }
281     if( !inbuf )
282         return;
283     if( hd->count ) {
284         for( ; inlen && hd->count < 64; inlen-- )
285             hd->buf[hd->count++] = *inbuf++;
286         rmd160_write( hd, NULL, 0 );
287         if( !inlen )
288             return;
289     }
290
291     while( inlen >= 64 ) {
292         transform( hd, inbuf );
293         hd->count = 0;
294         hd->nblocks++;
295         inlen -= 64;
296         inbuf += 64;
297     }
298     for( ; inlen && hd->count < 64; inlen-- )
299         hd->buf[hd->count++] = *inbuf++;
300 }
301
302
303 /* The routine terminates the computation
304  */
305
306 void
307 rmd160_final( RMD160_CONTEXT *hd )
308 {
309     u32 t, msb, lsb;
310     byte *p;
311
312     rmd160_write(hd, NULL, 0); /* flush */;
313
314     msb = 0;
315     t = hd->nblocks;
316     if( (lsb = t << 6) < t ) /* multiply by 64 to make a byte count */
317         msb++;
318     msb += t >> 26;
319     t = lsb;
320     if( (lsb = t + hd->count) < t ) /* add the count */
321         msb++;
322     t = lsb;
323     if( (lsb = t << 3) < t ) /* multiply by 8 to make a bit count */
324         msb++;
325     msb += t >> 29;
326
327     if( hd->count < 56 ) { /* enough room */
328         hd->buf[hd->count++] = 0x80; /* pad */
329         while( hd->count < 56 )
330             hd->buf[hd->count++] = 0;  /* pad */
331     }
332     else { /* need one extra block */
333         hd->buf[hd->count++] = 0x80; /* pad character */
334         while( hd->count < 64 )
335             hd->buf[hd->count++] = 0;
336         rmd160_write(hd, NULL, 0);  /* flush */;
337         memset(hd->buf, 0, 56 ); /* fill next block with zeroes */
338     }
339     /* append the 64 bit count */
340     hd->buf[56] = lsb      ;
341     hd->buf[57] = lsb >>  8;
342     hd->buf[58] = lsb >> 16;
343     hd->buf[59] = lsb >> 24;
344     hd->buf[60] = msb      ;
345     hd->buf[61] = msb >>  8;
346     hd->buf[62] = msb >> 16;
347     hd->buf[63] = msb >> 24;
348     transform( hd, hd->buf );
349
350     p = hd->buf;
351   #ifdef BIG_ENDIAN_HOST
352     #define X(a) do { *p++ = hd->h##a      ; *p++ = hd->h##a >> 8;      \
353                       *p++ = hd->h##a >> 16; *p++ = hd->h##a >> 24; } while(0)
354   #else /* little endian */
355     #define X(a) do { *(u32*)p = hd->h##a ; p += 4; } while(0)
356   #endif
357     X(0);
358     X(1);
359     X(2);
360     X(3);
361     X(4);
362   #undef X
363 }
364
365