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