bertos/sec/hash/ripemd.c

   1 /**
   2  * \file
   3  * <!--
   4  * This file is part of BeRTOS.
   5  *
   6  * Bertos 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  * This program 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., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
  19  *
  20  * As a special exception, you may use this file as part of a free software
  21  * library without restriction.  Specifically, if other files instantiate
  22  * templates or use macros or inline functions from this file, or you compile
  23  * this file and link it with other files to produce an executable, this
  24  * file does not by itself cause the resulting executable to be covered by
  25  * the GNU General Public License.  This exception does not however
  26  * invalidate any other reasons why the executable file might be covered by
  27  * the GNU General Public License.
  28  *
  29  * Copyright 2010 Develer S.r.l. (http://www.develer.com/)
  30  *
  31  * -->
  32  *
  33  * \brief RIPEMD-160 Hashing algorithm.
  34  * \author Giovanni Bajo <rasky@develer.com>
  35  */
  36
  37 /*
  38  *
  39  *  RIPEMD160.c : RIPEMD-160 implementation
  40  *
  41  * Written in 2008 by Dwayne C. Litzenberger <dlitz@dlitz.net>
  42  *
  43  * ===================================================================
  44  * The contents of this file are dedicated to the public domain.  To
  45  * the extent that dedication to the public domain is not available,
  46  * everyone is granted a worldwide, perpetual, royalty-free,
  47  * non-exclusive license to exercise all rights associated with the
  48  * contents of this file for any purpose whatsoever.
  49  * No rights are reserved.
  50  * ===================================================================
  51  */
  52
  53 #include "ripemd.h"
  54 #include <cfg/debug.h>
  55 #include <cfg/compiler.h>
  56 #include <cpu/byteorder.h>
  57 #include <string.h>
  58
  59 #define RIPEMD160_DIGEST_SIZE   20
  60
  61
  62 /* cyclic left-shift the 32-bit word n left by s bits */
  63 #define ROL(s, n)  ROTL(n, s)
  64
  65 /* Initial values for the chaining variables.
  66  * This is just 0123456789ABCDEFFEDCBA9876543210F0E1D2C3 in little-endian. */
  67 static const uint32_t initial_h[5] = { 0x67452301u, 0xEFCDAB89u, 0x98BADCFEu, 0x10325476u, 0xC3D2E1F0u };
  68
  69 /* Ordering of message words.  Based on the permutations rho(i) and pi(i), defined as follows:
  70  *
  71  *  rho(i) := { 7, 4, 13, 1, 10, 6, 15, 3, 12, 0, 9, 5, 2, 14, 11, 8 }[i]  0 <= i <= 15
  72  *
  73  *  pi(i) := 9*i + 5 (mod 16)
  74  *
  75  *  Line  |  Round 1  |  Round 2  |  Round 3  |  Round 4  |  Round 5
  76  * -------+-----------+-----------+-----------+-----------+-----------
  77  *  left  |    id     |    rho    |   rho^2   |   rho^3   |   rho^4
  78  *  right |    pi     |   rho pi  |  rho^2 pi |  rho^3 pi |  rho^4 pi
  79  */
  80
  81 /* Left line */
  82 static const uint8_t RL[5][16] = {
  83     { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 },   /* Round 1: id */
  84     { 7, 4, 13, 1, 10, 6, 15, 3, 12, 0, 9, 5, 2, 14, 11, 8 },   /* Round 2: rho */
  85     { 3, 10, 14, 4, 9, 15, 8, 1, 2, 7, 0, 6, 13, 11, 5, 12 },   /* Round 3: rho^2 */
  86     { 1, 9, 11, 10, 0, 8, 12, 4, 13, 3, 7, 15, 14, 5, 6, 2 },   /* Round 4: rho^3 */
  87     { 4, 0, 5, 9, 7, 12, 2, 10, 14, 1, 3, 8, 11, 6, 15, 13 }    /* Round 5: rho^4 */
  88 };
  89
  90 /* Right line */
  91 static const uint8_t RR[5][16] = {
  92     { 5, 14, 7, 0, 9, 2, 11, 4, 13, 6, 15, 8, 1, 10, 3, 12 },   /* Round 1: pi */
  93     { 6, 11, 3, 7, 0, 13, 5, 10, 14, 15, 8, 12, 4, 9, 1, 2 },   /* Round 2: rho pi */
  94     { 15, 5, 1, 3, 7, 14, 6, 9, 11, 8, 12, 2, 10, 0, 4, 13 },   /* Round 3: rho^2 pi */
  95     { 8, 6, 4, 1, 3, 11, 15, 0, 5, 12, 2, 13, 9, 7, 10, 14 },   /* Round 4: rho^3 pi */
  96     { 12, 15, 10, 4, 1, 5, 8, 7, 6, 2, 13, 14, 0, 3, 9, 11 }    /* Round 5: rho^4 pi */
  97 };
  98
  99 /*
 100  * Shifts - Since we don't actually re-order the message words according to
 101  * the permutations above (we could, but it would be slower), these tables
 102  * come with the permutations pre-applied.
 103  */
 104
 105 /* Shifts, left line */
 106 static const uint8_t SL[5][16] = {
 107     { 11, 14, 15, 12, 5, 8, 7, 9, 11, 13, 14, 15, 6, 7, 9, 8 }, /* Round 1 */
 108     { 7, 6, 8, 13, 11, 9, 7, 15, 7, 12, 15, 9, 11, 7, 13, 12 }, /* Round 2 */
 109     { 11, 13, 6, 7, 14, 9, 13, 15, 14, 8, 13, 6, 5, 12, 7, 5 }, /* Round 3 */
 110     { 11, 12, 14, 15, 14, 15, 9, 8, 9, 14, 5, 6, 8, 6, 5, 12 }, /* Round 4 */
 111     { 9, 15, 5, 11, 6, 8, 13, 12, 5, 12, 13, 14, 11, 8, 5, 6 }  /* Round 5 */
 112 };
 113
 114 /* Shifts, right line */
 115 static const uint8_t SR[5][16] = {
 116     { 8, 9, 9, 11, 13, 15, 15, 5, 7, 7, 8, 11, 14, 14, 12, 6 }, /* Round 1 */
 117     { 9, 13, 15, 7, 12, 8, 9, 11, 7, 7, 12, 7, 6, 15, 13, 11 }, /* Round 2 */
 118     { 9, 7, 15, 11, 8, 6, 6, 14, 12, 13, 5, 14, 13, 13, 7, 5 }, /* Round 3 */
 119     { 15, 5, 8, 11, 14, 14, 6, 14, 6, 9, 12, 9, 12, 5, 15, 8 }, /* Round 4 */
 120     { 8, 5, 12, 9, 12, 5, 14, 6, 8, 13, 6, 5, 15, 13, 11, 11 }  /* Round 5 */
 121 };
 122
 123 /* Boolean functions */
 124
 125 #define F1(x, y, z) ((x) ^ (y) ^ (z))
 126 #define F2(x, y, z) (((x) & (y)) | (~(x) & (z)))
 127 #define F3(x, y, z) (((x) | ~(y)) ^ (z))
 128 #define F4(x, y, z) (((x) & (z)) | ((y) & ~(z)))
 129 #define F5(x, y, z) ((x) ^ ((y) | ~(z)))
 130
 131 /* Round constants, left line */
 132 static const uint32_t KL[5] = {
 133     0x00000000u,    /* Round 1: 0 */
 134     0x5A827999u,    /* Round 2: floor(2**30 * sqrt(2)) */
 135     0x6ED9EBA1u,    /* Round 3: floor(2**30 * sqrt(3)) */
 136     0x8F1BBCDCu,    /* Round 4: floor(2**30 * sqrt(5)) */
 137     0xA953FD4Eu     /* Round 5: floor(2**30 * sqrt(7)) */
 138 };
 139
 140 /* Round constants, right line */
 141 static const uint32_t KR[5] = {
 142     0x50A28BE6u,    /* Round 1: floor(2**30 * cubert(2)) */
 143     0x5C4DD124u,    /* Round 2: floor(2**30 * cubert(3)) */
 144     0x6D703EF3u,    /* Round 3: floor(2**30 * cubert(5)) */
 145     0x7A6D76E9u,    /* Round 4: floor(2**30 * cubert(7)) */
 146     0x00000000u     /* Round 5: 0 */
 147 };
 148
 149 static void ripemd160_init(Hash *h)
 150 {
 151         RIPEMD_Context *self = (RIPEMD_Context *)h;
 152
 153     memcpy(self->h, initial_h, RIPEMD160_DIGEST_SIZE);
 154     memset(&self->buf, 0, sizeof(self->buf));
 155     self->length = 0;
 156     self->bufpos = 0;
 157 }
 158
 159 static inline void byteswap_digest(uint32_t *p)
 160 {
 161     unsigned int i;
 162
 163     for (i = 0; i < 4; i++) {
 164         p[0] = SWAB32(p[0]);
 165         p[1] = SWAB32(p[1]);
 166         p[2] = SWAB32(p[2]);
 167         p[3] = SWAB32(p[3]);
 168                 p += 4;
 169     }
 170 }
 171
 172 /* The RIPEMD160 compression function.  Operates on self->buf */
 173 static void ripemd160_compress(RIPEMD_Context *self)
 174 {
 175     uint8_t w, round;
 176     uint32_t T;
 177     uint32_t AL, BL, CL, DL, EL;    /* left line */
 178     uint32_t AR, BR, CR, DR, ER;    /* right line */
 179
 180     /* Sanity check */
 181     ASSERT(self->bufpos == 64);
 182
 183     /* Byte-swap the buffer if we're on a big-endian machine */
 184 #if CPU_BYTE_ORDER == CPU_BIG_ENDIAN
 185     byteswap_digest(self->buf.w);
 186 #endif
 187
 188     /* Load the left and right lines with the initial state */
 189     AL = AR = self->h[0];
 190     BL = BR = self->h[1];
 191     CL = CR = self->h[2];
 192     DL = DR = self->h[3];
 193     EL = ER = self->h[4];
 194
 195     /* Round 1 */
 196     round = 0;
 197     for (w = 0; w < 16; w++) { /* left line */
 198         T = ROL(SL[round][w], AL + F1(BL, CL, DL) + self->buf.w[RL[round][w]] + KL[round]) + EL;
 199         AL = EL; EL = DL; DL = ROL(10, CL); CL = BL; BL = T;
 200     }
 201     for (w = 0; w < 16; w++) { /* right line */
 202         T = ROL(SR[round][w], AR + F5(BR, CR, DR) + self->buf.w[RR[round][w]] + KR[round]) + ER;
 203         AR = ER; ER = DR; DR = ROL(10, CR); CR = BR; BR = T;
 204     }
 205
 206     /* Round 2 */
 207     round++;
 208     for (w = 0; w < 16; w++) { /* left line */
 209         T = ROL(SL[round][w], AL + F2(BL, CL, DL) + self->buf.w[RL[round][w]] + KL[round]) + EL;
 210         AL = EL; EL = DL; DL = ROL(10, CL); CL = BL; BL = T;
 211     }
 212     for (w = 0; w < 16; w++) { /* right line */
 213         T = ROL(SR[round][w], AR + F4(BR, CR, DR) + self->buf.w[RR[round][w]] + KR[round]) + ER;
 214         AR = ER; ER = DR; DR = ROL(10, CR); CR = BR; BR = T;
 215     }
 216
 217     /* Round 3 */
 218     round++;
 219     for (w = 0; w < 16; w++) { /* left line */
 220         T = ROL(SL[round][w], AL + F3(BL, CL, DL) + self->buf.w[RL[round][w]] + KL[round]) + EL;
 221         AL = EL; EL = DL; DL = ROL(10, CL); CL = BL; BL = T;
 222     }
 223     for (w = 0; w < 16; w++) { /* right line */
 224         T = ROL(SR[round][w], AR + F3(BR, CR, DR) + self->buf.w[RR[round][w]] + KR[round]) + ER;
 225         AR = ER; ER = DR; DR = ROL(10, CR); CR = BR; BR = T;
 226     }
 227
 228     /* Round 4 */
 229     round++;
 230     for (w = 0; w < 16; w++) { /* left line */
 231         T = ROL(SL[round][w], AL + F4(BL, CL, DL) + self->buf.w[RL[round][w]] + KL[round]) + EL;
 232         AL = EL; EL = DL; DL = ROL(10, CL); CL = BL; BL = T;
 233     }
 234     for (w = 0; w < 16; w++) { /* right line */
 235         T = ROL(SR[round][w], AR + F2(BR, CR, DR) + self->buf.w[RR[round][w]] + KR[round]) + ER;
 236         AR = ER; ER = DR; DR = ROL(10, CR); CR = BR; BR = T;
 237     }
 238
 239     /* Round 5 */
 240     round++;
 241     for (w = 0; w < 16; w++) { /* left line */
 242         T = ROL(SL[round][w], AL + F5(BL, CL, DL) + self->buf.w[RL[round][w]] + KL[round]) + EL;
 243         AL = EL; EL = DL; DL = ROL(10, CL); CL = BL; BL = T;
 244     }
 245     for (w = 0; w < 16; w++) { /* right line */
 246         T = ROL(SR[round][w], AR + F1(BR, CR, DR) + self->buf.w[RR[round][w]] + KR[round]) + ER;
 247         AR = ER; ER = DR; DR = ROL(10, CR); CR = BR; BR = T;
 248     }
 249
 250     /* Final mixing stage */
 251     T = self->h[1] + CL + DR;
 252     self->h[1] = self->h[2] + DL + ER;
 253     self->h[2] = self->h[3] + EL + AR;
 254     self->h[3] = self->h[4] + AL + BR;
 255     self->h[4] = self->h[0] + BL + CR;
 256     self->h[0] = T;
 257
 258     /* Clear the buffer and wipe the temporary variables */
 259     T = AL = BL = CL = DL = EL = AR = BR = CR = DR = ER = 0;
 260     memset(&self->buf, 0, sizeof(self->buf));
 261     self->bufpos = 0;
 262 }
 263
 264 static void ripemd160_update(Hash *h, const void *data, size_t length)
 265 {
 266         RIPEMD_Context *self = (RIPEMD_Context *)h;
 267         const uint8_t *p = (const uint8_t *)data;
 268     unsigned int bytes_needed;
 269
 270     /* Some assertions */
 271     ASSERT(p != NULL);
 272
 273     /* We never leave a full buffer */
 274     ASSERT(self->bufpos < 64);
 275
 276     while (length > 0) {
 277         /* Figure out how many bytes we need to fill the internal buffer. */
 278         bytes_needed = 64 - self->bufpos;
 279
 280         if (length >= bytes_needed) {
 281             /* We have enough bytes, so copy them into the internal buffer and run
 282              * the compression function. */
 283             memcpy(&self->buf.b[self->bufpos], p, bytes_needed);
 284             self->bufpos += bytes_needed;
 285             self->length += bytes_needed << 3;    /* length is in bits */
 286             p += bytes_needed;
 287             ripemd160_compress(self);
 288             length -= bytes_needed;
 289             continue;
 290         }
 291
 292         /* We do not have enough bytes to fill the internal buffer.
 293          * Copy what's there and return. */
 294         memcpy(&self->buf.b[self->bufpos], p, length);
 295         self->bufpos += length;
 296         self->length += length << 3;    /* length is in bits */
 297         return;
 298     }
 299 }
 300
 301 static uint8_t* ripemd160_digest(Hash *h)
 302 {
 303         RIPEMD_Context *self = (RIPEMD_Context *)h;
 304
 305     /* Append the padding */
 306     self->buf.b[self->bufpos++] = 0x80;
 307
 308     if (self->bufpos > 56) {
 309         self->bufpos = 64;
 310         ripemd160_compress(self);
 311     }
 312
 313     /* Append the length */
 314     self->buf.w[14] = cpu_to_le32((uint32_t)(self->length & 0xFFFFffffu));
 315     self->buf.w[15] = cpu_to_le32((uint32_t)((self->length >> 32) & 0xFFFFffffu));
 316
 317         self->bufpos = 64;
 318     ripemd160_compress(self);
 319
 320     /* Copy the final state into the output buffer */
 321 #if CPU_BYTE_ORDER == CPU_BIG_ENDIAN
 322     byteswap_digest(self->h);
 323 #endif
 324
 325         return (uint8_t*)&self->h;
 326 }
 327
 328 /**************************************************************************************/
 329
 330
 331 void RIPEMD_init(RIPEMD_Context *ctx)
 332 {
 333         ctx->hash.begin = ripemd160_init;
 334         ctx->hash.update = ripemd160_update;
 335         ctx->hash.final = ripemd160_digest;
 336         ctx->hash.digest_len = RIPEMD160_DIGEST_SIZE;
 337         ctx->hash.block_len = 64;
 338 }