ripemd160.c

   1 /* ripemd160.c
   2
   3    RIPE-MD160
   4
   5    Copyright (C) 1998, 2001, 2002, 2003 Free Software Foundation, Inc.
   6    Copyright (C) 2011 Niels Möller
   7
   8    This file is part of GNU Nettle.
   9
  10    GNU Nettle is free software: you can redistribute it and/or
  11    modify it under the terms of either:
  12
  13      * the GNU Lesser General Public License as published by the Free
  14        Software Foundation; either version 3 of the License, or (at your
  15        option) any later version.
  16
  17    or
  18
  19      * the GNU General Public License as published by the Free
  20        Software Foundation; either version 2 of the License, or (at your
  21        option) any later version.
  22
  23    or both in parallel, as here.
  24
  25    GNU Nettle is distributed in the hope that it will be useful,
  26    but WITHOUT ANY WARRANTY; without even the implied warranty of
  27    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  28    General Public License for more details.
  29
  30    You should have received copies of the GNU General Public License and
  31    the GNU Lesser General Public License along with this program.  If
  32    not, see http://www.gnu.org/licenses/.
  33 */
  34
  35 #if HAVE_CONFIG_H
  36 # include "config.h"
  37 #endif
  38
  39 #include <string.h>
  40 #include <assert.h>
  41
  42 #include "ripemd160.h"
  43
  44 #include "macros.h"
  45 #include "nettle-write.h"
  46
  47 /*********************************
  48  * RIPEMD-160 is not patented, see (as of 2011-08-28)
  49  *   http://www.esat.kuleuven.ac.be/~bosselae/ripemd160.html
  50  * Note that the code uses Little Endian byteorder, which is good for
  51  * 386 etc, but we must add some conversion when used on a big endian box.
  52  *
  53  *
  54  * Pseudo-code for RIPEMD-160
  55  *
  56  * RIPEMD-160 is an iterative hash function that operates on 32-bit words.
  57  * The round function takes as input a 5-word chaining variable and a 16-word
  58  * message block and maps this to a new chaining variable. All operations are
  59  * defined on 32-bit words. Padding is identical to that of MD4.
  60  *
  61  *
  62  * RIPEMD-160: definitions
  63  *
  64  *
  65  *   nonlinear functions at bit level: exor, mux, -, mux, -
  66  *
  67  *   f(j, x, y, z) = x XOR y XOR z      (0 <= j <= 15)
  68  *   f(j, x, y, z) = (x AND y) OR (NOT(x) AND z)  (16 <= j <= 31)
  69  *   f(j, x, y, z) = (x OR NOT(y)) XOR z    (32 <= j <= 47)
  70  *   f(j, x, y, z) = (x AND z) OR (y AND NOT(z))  (48 <= j <= 63)
  71  *   f(j, x, y, z) = x XOR (y OR NOT(z))    (64 <= j <= 79)
  72  *
  73  *
  74  *   added constants (hexadecimal)
  75  *
  76  *   K(j) = 0x00000000      (0 <= j <= 15)
  77  *   K(j) = 0x5A827999     (16 <= j <= 31)  int(2**30 x sqrt(2))
  78  *   K(j) = 0x6ED9EBA1     (32 <= j <= 47)  int(2**30 x sqrt(3))
  79  *   K(j) = 0x8F1BBCDC     (48 <= j <= 63)  int(2**30 x sqrt(5))
  80  *   K(j) = 0xA953FD4E     (64 <= j <= 79)  int(2**30 x sqrt(7))
  81  *   K'(j) = 0x50A28BE6     (0 <= j <= 15)      int(2**30 x cbrt(2))
  82  *   K'(j) = 0x5C4DD124    (16 <= j <= 31)      int(2**30 x cbrt(3))
  83  *   K'(j) = 0x6D703EF3    (32 <= j <= 47)      int(2**30 x cbrt(5))
  84  *   K'(j) = 0x7A6D76E9    (48 <= j <= 63)      int(2**30 x cbrt(7))
  85  *   K'(j) = 0x00000000    (64 <= j <= 79)
  86  *
  87  *
  88  *   selection of message word
  89  *
  90  *   r(j)      = j          (0 <= j <= 15)
  91  *   r(16..31) = 7, 4, 13, 1, 10, 6, 15, 3, 12, 0, 9, 5, 2, 14, 11, 8
  92  *   r(32..47) = 3, 10, 14, 4, 9, 15, 8, 1, 2, 7, 0, 6, 13, 11, 5, 12
  93  *   r(48..63) = 1, 9, 11, 10, 0, 8, 12, 4, 13, 3, 7, 15, 14, 5, 6, 2
  94  *   r(64..79) = 4, 0, 5, 9, 7, 12, 2, 10, 14, 1, 3, 8, 11, 6, 15, 13
  95  *   r0(0..15) = 5, 14, 7, 0, 9, 2, 11, 4, 13, 6, 15, 8, 1, 10, 3, 12
  96  *   r0(16..31)= 6, 11, 3, 7, 0, 13, 5, 10, 14, 15, 8, 12, 4, 9, 1, 2
  97  *   r0(32..47)= 15, 5, 1, 3, 7, 14, 6, 9, 11, 8, 12, 2, 10, 0, 4, 13
  98  *   r0(48..63)= 8, 6, 4, 1, 3, 11, 15, 0, 5, 12, 2, 13, 9, 7, 10, 14
  99  *   r0(64..79)= 12, 15, 10, 4, 1, 5, 8, 7, 6, 2, 13, 14, 0, 3, 9, 11
 100  *
 101  *
 102  *   amount for rotate left (rol)
 103  *
 104  *   s(0..15)  = 11, 14, 15, 12, 5, 8, 7, 9, 11, 13, 14, 15, 6, 7, 9, 8
 105  *   s(16..31) = 7, 6, 8, 13, 11, 9, 7, 15, 7, 12, 15, 9, 11, 7, 13, 12
 106  *   s(32..47) = 11, 13, 6, 7, 14, 9, 13, 15, 14, 8, 13, 6, 5, 12, 7, 5
 107  *   s(48..63) = 11, 12, 14, 15, 14, 15, 9, 8, 9, 14, 5, 6, 8, 6, 5, 12
 108  *   s(64..79) = 9, 15, 5, 11, 6, 8, 13, 12, 5, 12, 13, 14, 11, 8, 5, 6
 109  *   s'(0..15) = 8, 9, 9, 11, 13, 15, 15, 5, 7, 7, 8, 11, 14, 14, 12, 6
 110  *   s'(16..31)= 9, 13, 15, 7, 12, 8, 9, 11, 7, 7, 12, 7, 6, 15, 13, 11
 111  *   s'(32..47)= 9, 7, 15, 11, 8, 6, 6, 14, 12, 13, 5, 14, 13, 13, 7, 5
 112  *   s'(48..63)= 15, 5, 8, 11, 14, 14, 6, 14, 6, 9, 12, 9, 12, 5, 15, 8
 113  *   s'(64..79)= 8, 5, 12, 9, 12, 5, 14, 6, 8, 13, 6, 5, 15, 13, 11, 11
 114  *
 115  *
 116  *   initial value (hexadecimal)
 117  *
 118  *   h0 = 0x67452301; h1 = 0xEFCDAB89; h2 = 0x98BADCFE; h3 = 0x10325476;
 119  *              h4 = 0xC3D2E1F0;
 120  *
 121  *
 122  * RIPEMD-160: pseudo-code
 123  *
 124  *   It is assumed that the message after padding consists of t 16-word blocks
 125  *   that will be denoted with X[i][j], with 0 <= i <= t-1 and 0 <= j <= 15.
 126  *   The symbol [+] denotes addition modulo 2**32 and rol_s denotes cyclic left
 127  *   shift (rotate) over s positions.
 128  *
 129  *
 130  *   for i := 0 to t-1 {
 131  *   A := h0; B := h1; C := h2; D = h3; E = h4;
 132  *   A' := h0; B' := h1; C' := h2; D' = h3; E' = h4;
 133  *   for j := 0 to 79 {
 134  *       T := rol_s(j)(A [+] f(j, B, C, D) [+] X[i][r(j)] [+] K(j)) [+] E;
 135  *       A := E; E := D; D := rol_10(C); C := B; B := T;
 136  *       T := rol_s'(j)(A' [+] f(79-j, B', C', D') [+] X[i][r'(j)]
 137                    [+] K'(j)) [+] E';
 138  *       A' := E'; E' := D'; D' := rol_10(C'); C' := B'; B' := T;
 139  *   }
 140  *   T := h1 [+] C [+] D'; h1 := h2 [+] D [+] E'; h2 := h3 [+] E [+] A';
 141  *   h3 := h4 [+] A [+] B'; h4 := h0 [+] B [+] C'; h0 := T;
 142  *   }
 143  */
 144
 145 /* Some examples:
 146  * ""                    9c1185a5c5e9fc54612808977ee8f548b2258d31
 147  * "a"                   0bdc9d2d256b3ee9daae347be6f4dc835a467ffe
 148  * "abc"                 8eb208f7e05d987a9b044a8e98c6b087f15a0bfc
 149  * "message digest"      5d0689ef49d2fae572b881b123a85ffa21595f36
 150  * "a...z"               f71c27109c692c1b56bbdceb5b9d2865b3708dbc
 151  * "abcdbcde...nopq"     12a053384a9c0c88e405a06c27dcf49ada62eb2b
 152  * "A...Za...z0...9"     b0e20b6e3116640286ed3a87a5713079b21f5189
 153  * 8 times "1234567890"  9b752e45573d4b39f4dbd3323cab82bf63326bfb
 154  * 1 million times "a"   52783243c1697bdbe16d37f97f68f08325dc1528
 155  */
 156
 157 void
 158 ripemd160_init(struct ripemd160_ctx *ctx)
 159 {
 160   static const uint32_t iv[_RIPEMD160_DIGEST_LENGTH] =
 161     {
 162       0x67452301,
 163       0xEFCDAB89,
 164       0x98BADCFE,
 165       0x10325476,
 166       0xC3D2E1F0,
 167     };
 168   memcpy(ctx->state, iv, sizeof(ctx->state));
 169   ctx->count = 0;
 170   ctx->index = 0;
 171 }
 172
 173 #define COMPRESS(ctx, data) (_nettle_ripemd160_compress((ctx)->state, (data)))
 174
 175 /* Update the message digest with the contents
 176  * of DATA with length LENGTH.
 177  */
 178 void
 179 ripemd160_update(struct ripemd160_ctx *ctx, size_t length, const uint8_t *data)
 180 {
 181   MD_UPDATE(ctx, length, data, COMPRESS, ctx->count++);
 182 }
 183
 184 void
 185 ripemd160_digest(struct ripemd160_ctx *ctx, size_t length, uint8_t *digest)
 186 {
 187   uint64_t bit_count;
 188
 189   assert(length <= RIPEMD160_DIGEST_SIZE);
 190
 191   MD_PAD(ctx, 8, COMPRESS);
 192
 193   /* There are 2^9 bits in one block */
 194   bit_count = (ctx->count << 9) | (ctx->index << 3);
 195                                                                         \
 196   /* append the 64 bit count */
 197   LE_WRITE_UINT64(ctx->block + 56, bit_count);
 198   _nettle_ripemd160_compress(ctx->state, ctx->block);
 199
 200   _nettle_write_le32(length, digest, ctx->state);
 201   ripemd160_init(ctx);
 202 }