BeRTOS
ripemd.c
Go to the documentation of this file.
00001 
00037 /*
00038  *
00039  *  RIPEMD160.c : RIPEMD-160 implementation
00040  *
00041  * Written in 2008 by Dwayne C. Litzenberger <dlitz@dlitz.net>
00042  *
00043  * ===================================================================
00044  * The contents of this file are dedicated to the public domain.  To
00045  * the extent that dedication to the public domain is not available,
00046  * everyone is granted a worldwide, perpetual, royalty-free,
00047  * non-exclusive license to exercise all rights associated with the
00048  * contents of this file for any purpose whatsoever.
00049  * No rights are reserved.
00050  * ===================================================================
00051  */
00052 
00053 #include "ripemd.h"
00054 #include <cfg/debug.h>
00055 #include <cfg/compiler.h>
00056 #include <cpu/byteorder.h>
00057 #include <string.h>
00058 
00059 #define RIPEMD160_DIGEST_SIZE   20
00060 
00061 
00062 /* cyclic left-shift the 32-bit word n left by s bits */
00063 #define ROL(s, n)  ROTL(n, s)
00064 
00065 /* Initial values for the chaining variables.
00066  * This is just 0123456789ABCDEFFEDCBA9876543210F0E1D2C3 in little-endian. */
00067 static const uint32_t initial_h[5] = { 0x67452301u, 0xEFCDAB89u, 0x98BADCFEu, 0x10325476u, 0xC3D2E1F0u };
00068 
00069 /* Ordering of message words.  Based on the permutations rho(i) and pi(i), defined as follows:
00070  *
00071  *  rho(i) := { 7, 4, 13, 1, 10, 6, 15, 3, 12, 0, 9, 5, 2, 14, 11, 8 }[i]  0 <= i <= 15
00072  *
00073  *  pi(i) := 9*i + 5 (mod 16)
00074  *
00075  *  Line  |  Round 1  |  Round 2  |  Round 3  |  Round 4  |  Round 5
00076  * -------+-----------+-----------+-----------+-----------+-----------
00077  *  left  |    id     |    rho    |   rho^2   |   rho^3   |   rho^4
00078  *  right |    pi     |   rho pi  |  rho^2 pi |  rho^3 pi |  rho^4 pi
00079  */
00080 
00081 /* Left line */
00082 static const uint8_t RL[5][16] = {
00083     { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 },   /* Round 1: id */
00084     { 7, 4, 13, 1, 10, 6, 15, 3, 12, 0, 9, 5, 2, 14, 11, 8 },   /* Round 2: rho */
00085     { 3, 10, 14, 4, 9, 15, 8, 1, 2, 7, 0, 6, 13, 11, 5, 12 },   /* Round 3: rho^2 */
00086     { 1, 9, 11, 10, 0, 8, 12, 4, 13, 3, 7, 15, 14, 5, 6, 2 },   /* Round 4: rho^3 */
00087     { 4, 0, 5, 9, 7, 12, 2, 10, 14, 1, 3, 8, 11, 6, 15, 13 }    /* Round 5: rho^4 */
00088 };
00089 
00090 /* Right line */
00091 static const uint8_t RR[5][16] = {
00092     { 5, 14, 7, 0, 9, 2, 11, 4, 13, 6, 15, 8, 1, 10, 3, 12 },   /* Round 1: pi */
00093     { 6, 11, 3, 7, 0, 13, 5, 10, 14, 15, 8, 12, 4, 9, 1, 2 },   /* Round 2: rho pi */
00094     { 15, 5, 1, 3, 7, 14, 6, 9, 11, 8, 12, 2, 10, 0, 4, 13 },   /* Round 3: rho^2 pi */
00095     { 8, 6, 4, 1, 3, 11, 15, 0, 5, 12, 2, 13, 9, 7, 10, 14 },   /* Round 4: rho^3 pi */
00096     { 12, 15, 10, 4, 1, 5, 8, 7, 6, 2, 13, 14, 0, 3, 9, 11 }    /* Round 5: rho^4 pi */
00097 };
00098 
00099 /*
00100  * Shifts - Since we don't actually re-order the message words according to
00101  * the permutations above (we could, but it would be slower), these tables
00102  * come with the permutations pre-applied.
00103  */
00104 
00105 /* Shifts, left line */
00106 static const uint8_t SL[5][16] = {
00107     { 11, 14, 15, 12, 5, 8, 7, 9, 11, 13, 14, 15, 6, 7, 9, 8 }, /* Round 1 */
00108     { 7, 6, 8, 13, 11, 9, 7, 15, 7, 12, 15, 9, 11, 7, 13, 12 }, /* Round 2 */
00109     { 11, 13, 6, 7, 14, 9, 13, 15, 14, 8, 13, 6, 5, 12, 7, 5 }, /* Round 3 */
00110     { 11, 12, 14, 15, 14, 15, 9, 8, 9, 14, 5, 6, 8, 6, 5, 12 }, /* Round 4 */
00111     { 9, 15, 5, 11, 6, 8, 13, 12, 5, 12, 13, 14, 11, 8, 5, 6 }  /* Round 5 */
00112 };
00113 
00114 /* Shifts, right line */
00115 static const uint8_t SR[5][16] = {
00116     { 8, 9, 9, 11, 13, 15, 15, 5, 7, 7, 8, 11, 14, 14, 12, 6 }, /* Round 1 */
00117     { 9, 13, 15, 7, 12, 8, 9, 11, 7, 7, 12, 7, 6, 15, 13, 11 }, /* Round 2 */
00118     { 9, 7, 15, 11, 8, 6, 6, 14, 12, 13, 5, 14, 13, 13, 7, 5 }, /* Round 3 */
00119     { 15, 5, 8, 11, 14, 14, 6, 14, 6, 9, 12, 9, 12, 5, 15, 8 }, /* Round 4 */
00120     { 8, 5, 12, 9, 12, 5, 14, 6, 8, 13, 6, 5, 15, 13, 11, 11 }  /* Round 5 */
00121 };
00122 
00123 /* Boolean functions */
00124 
00125 #define F1(x, y, z) ((x) ^ (y) ^ (z))
00126 #define F2(x, y, z) (((x) & (y)) | (~(x) & (z)))
00127 #define F3(x, y, z) (((x) | ~(y)) ^ (z))
00128 #define F4(x, y, z) (((x) & (z)) | ((y) & ~(z)))
00129 #define F5(x, y, z) ((x) ^ ((y) | ~(z)))
00130 
00131 /* Round constants, left line */
00132 static const uint32_t KL[5] = {
00133     0x00000000u,    /* Round 1: 0 */
00134     0x5A827999u,    /* Round 2: floor(2**30 * sqrt(2)) */
00135     0x6ED9EBA1u,    /* Round 3: floor(2**30 * sqrt(3)) */
00136     0x8F1BBCDCu,    /* Round 4: floor(2**30 * sqrt(5)) */
00137     0xA953FD4Eu     /* Round 5: floor(2**30 * sqrt(7)) */
00138 };
00139 
00140 /* Round constants, right line */
00141 static const uint32_t KR[5] = {
00142     0x50A28BE6u,    /* Round 1: floor(2**30 * cubert(2)) */
00143     0x5C4DD124u,    /* Round 2: floor(2**30 * cubert(3)) */
00144     0x6D703EF3u,    /* Round 3: floor(2**30 * cubert(5)) */
00145     0x7A6D76E9u,    /* Round 4: floor(2**30 * cubert(7)) */
00146     0x00000000u     /* Round 5: 0 */
00147 };
00148 
00149 static void ripemd160_init(Hash *h)
00150 {
00151     RIPEMD_Context *self = (RIPEMD_Context *)h;
00152     
00153     memcpy(self->h, initial_h, RIPEMD160_DIGEST_SIZE);
00154     memset(&self->buf, 0, sizeof(self->buf));
00155     self->length = 0;
00156     self->bufpos = 0;
00157 }
00158 
00159 static inline void byteswap_digest(uint32_t *p)
00160 {
00161     unsigned int i;
00162 
00163     for (i = 0; i < 4; i++) {
00164         p[0] = SWAB32(p[0]);
00165         p[1] = SWAB32(p[1]);
00166         p[2] = SWAB32(p[2]);
00167         p[3] = SWAB32(p[3]);
00168         p += 4;
00169     }
00170 }
00171 
00172 /* The RIPEMD160 compression function.  Operates on self->buf */
00173 static void ripemd160_compress(RIPEMD_Context *self)
00174 {
00175     uint8_t w, round;
00176     uint32_t T;
00177     uint32_t AL, BL, CL, DL, EL;    /* left line */
00178     uint32_t AR, BR, CR, DR, ER;    /* right line */
00179 
00180     /* Sanity check */
00181     ASSERT(self->bufpos == 64);
00182 
00183     /* Byte-swap the buffer if we're on a big-endian machine */
00184 #if CPU_BYTE_ORDER == CPU_BIG_ENDIAN
00185     byteswap_digest(self->buf.w);
00186 #endif
00187 
00188     /* Load the left and right lines with the initial state */
00189     AL = AR = self->h[0];
00190     BL = BR = self->h[1];
00191     CL = CR = self->h[2];
00192     DL = DR = self->h[3];
00193     EL = ER = self->h[4];
00194 
00195     /* Round 1 */
00196     round = 0;
00197     for (w = 0; w < 16; w++) { /* left line */
00198         T = ROL(SL[round][w], AL + F1(BL, CL, DL) + self->buf.w[RL[round][w]] + KL[round]) + EL;
00199         AL = EL; EL = DL; DL = ROL(10, CL); CL = BL; BL = T;
00200     }
00201     for (w = 0; w < 16; w++) { /* right line */
00202         T = ROL(SR[round][w], AR + F5(BR, CR, DR) + self->buf.w[RR[round][w]] + KR[round]) + ER;
00203         AR = ER; ER = DR; DR = ROL(10, CR); CR = BR; BR = T;
00204     }
00205 
00206     /* Round 2 */
00207     round++;
00208     for (w = 0; w < 16; w++) { /* left line */
00209         T = ROL(SL[round][w], AL + F2(BL, CL, DL) + self->buf.w[RL[round][w]] + KL[round]) + EL;
00210         AL = EL; EL = DL; DL = ROL(10, CL); CL = BL; BL = T;
00211     }
00212     for (w = 0; w < 16; w++) { /* right line */
00213         T = ROL(SR[round][w], AR + F4(BR, CR, DR) + self->buf.w[RR[round][w]] + KR[round]) + ER;
00214         AR = ER; ER = DR; DR = ROL(10, CR); CR = BR; BR = T;
00215     }
00216 
00217     /* Round 3 */
00218     round++;
00219     for (w = 0; w < 16; w++) { /* left line */
00220         T = ROL(SL[round][w], AL + F3(BL, CL, DL) + self->buf.w[RL[round][w]] + KL[round]) + EL;
00221         AL = EL; EL = DL; DL = ROL(10, CL); CL = BL; BL = T;
00222     }
00223     for (w = 0; w < 16; w++) { /* right line */
00224         T = ROL(SR[round][w], AR + F3(BR, CR, DR) + self->buf.w[RR[round][w]] + KR[round]) + ER;
00225         AR = ER; ER = DR; DR = ROL(10, CR); CR = BR; BR = T;
00226     }
00227 
00228     /* Round 4 */
00229     round++;
00230     for (w = 0; w < 16; w++) { /* left line */
00231         T = ROL(SL[round][w], AL + F4(BL, CL, DL) + self->buf.w[RL[round][w]] + KL[round]) + EL;
00232         AL = EL; EL = DL; DL = ROL(10, CL); CL = BL; BL = T;
00233     }
00234     for (w = 0; w < 16; w++) { /* right line */
00235         T = ROL(SR[round][w], AR + F2(BR, CR, DR) + self->buf.w[RR[round][w]] + KR[round]) + ER;
00236         AR = ER; ER = DR; DR = ROL(10, CR); CR = BR; BR = T;
00237     }
00238 
00239     /* Round 5 */
00240     round++;
00241     for (w = 0; w < 16; w++) { /* left line */
00242         T = ROL(SL[round][w], AL + F5(BL, CL, DL) + self->buf.w[RL[round][w]] + KL[round]) + EL;
00243         AL = EL; EL = DL; DL = ROL(10, CL); CL = BL; BL = T;
00244     }
00245     for (w = 0; w < 16; w++) { /* right line */
00246         T = ROL(SR[round][w], AR + F1(BR, CR, DR) + self->buf.w[RR[round][w]] + KR[round]) + ER;
00247         AR = ER; ER = DR; DR = ROL(10, CR); CR = BR; BR = T;
00248     }
00249 
00250     /* Final mixing stage */
00251     T = self->h[1] + CL + DR;
00252     self->h[1] = self->h[2] + DL + ER;
00253     self->h[2] = self->h[3] + EL + AR;
00254     self->h[3] = self->h[4] + AL + BR;
00255     self->h[4] = self->h[0] + BL + CR;
00256     self->h[0] = T;
00257 
00258     /* Clear the buffer and wipe the temporary variables */
00259     T = AL = BL = CL = DL = EL = AR = BR = CR = DR = ER = 0;
00260     memset(&self->buf, 0, sizeof(self->buf));
00261     self->bufpos = 0;
00262 }
00263 
00264 static void ripemd160_update(Hash *h, const void *data, size_t length)
00265 {
00266     RIPEMD_Context *self = (RIPEMD_Context *)h;
00267     const uint8_t *p = (const uint8_t *)data;
00268     unsigned int bytes_needed;
00269 
00270     /* Some assertions */
00271     ASSERT(p != NULL);
00272 
00273     /* We never leave a full buffer */
00274     ASSERT(self->bufpos < 64);
00275 
00276     while (length > 0) {
00277         /* Figure out how many bytes we need to fill the internal buffer. */
00278         bytes_needed = 64 - self->bufpos;
00279 
00280         if (length >= bytes_needed) {
00281             /* We have enough bytes, so copy them into the internal buffer and run
00282              * the compression function. */
00283             memcpy(&self->buf.b[self->bufpos], p, bytes_needed);
00284             self->bufpos += bytes_needed;
00285             self->length += bytes_needed << 3;    /* length is in bits */
00286             p += bytes_needed;
00287             ripemd160_compress(self);
00288             length -= bytes_needed;
00289             continue;
00290         }
00291 
00292         /* We do not have enough bytes to fill the internal buffer.
00293          * Copy what's there and return. */
00294         memcpy(&self->buf.b[self->bufpos], p, length);
00295         self->bufpos += length;
00296         self->length += length << 3;    /* length is in bits */
00297         return;
00298     }
00299 }
00300 
00301 static uint8_t* ripemd160_digest(Hash *h)
00302 {
00303     RIPEMD_Context *self = (RIPEMD_Context *)h;
00304     
00305     /* Append the padding */
00306     self->buf.b[self->bufpos++] = 0x80;
00307 
00308     if (self->bufpos > 56) {
00309         self->bufpos = 64;
00310         ripemd160_compress(self);
00311     }
00312 
00313     /* Append the length */
00314     self->buf.w[14] = cpu_to_le32((uint32_t)(self->length & 0xFFFFffffu));
00315     self->buf.w[15] = cpu_to_le32((uint32_t)((self->length >> 32) & 0xFFFFffffu));
00316 
00317     self->bufpos = 64;
00318     ripemd160_compress(self);
00319 
00320     /* Copy the final state into the output buffer */
00321 #if CPU_BYTE_ORDER == CPU_BIG_ENDIAN
00322     byteswap_digest(self->h);
00323 #endif
00324 
00325     return (uint8_t*)&self->h;
00326 }
00327 
00328 /**************************************************************************************/
00329 
00330 
00331 void RIPEMD_init(RIPEMD_Context *ctx)
00332 {
00333     ctx->hash.begin = ripemd160_init;
00334     ctx->hash.update = ripemd160_update;
00335     ctx->hash.final = ripemd160_digest;
00336     ctx->hash.digest_len = RIPEMD160_DIGEST_SIZE;
00337     ctx->hash.block_len = 64;
00338 }