md4.c (4769B)
1 /* vim:set ts=2 sw=2 et cindent: */ 2 /* This Source Code Form is subject to the terms of the Mozilla Public 3 * License, v. 2.0. If a copy of the MPL was not distributed with this 4 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */ 5 6 /* 7 * "clean room" MD4 implementation (see RFC 1320) 8 */ 9 10 #include <string.h> 11 #include "md4.h" 12 13 /* the "conditional" function */ 14 #define F(x, y, z) (((x) & (y)) | (~(x) & (z))) 15 16 /* the "majority" function */ 17 #define G(x, y, z) (((x) & (y)) | ((x) & (z)) | ((y) & (z))) 18 19 /* the "parity" function */ 20 #define H(x, y, z) ((x) ^ (y) ^ (z)) 21 22 /* rotate n-bits to the left */ 23 #define ROTL(x, n) (((x) << (n)) | ((x) >> (0x20 - n))) 24 25 /* round 1: [abcd k s]: a = (a + F(b,c,d) + X[k]) <<< s */ 26 #define RD1(a, b, c, d, k, s) \ 27 a += F(b, c, d) + X[k]; \ 28 a = ROTL(a, s) 29 30 /* round 2: [abcd k s]: a = (a + G(b,c,d) + X[k] + MAGIC) <<< s */ 31 #define RD2(a, b, c, d, k, s) \ 32 a += G(b, c, d) + X[k] + 0x5A827999; \ 33 a = ROTL(a, s) 34 35 /* round 3: [abcd k s]: a = (a + H(b,c,d) + X[k] + MAGIC) <<< s */ 36 #define RD3(a, b, c, d, k, s) \ 37 a += H(b, c, d) + X[k] + 0x6ED9EBA1; \ 38 a = ROTL(a, s) 39 40 /* converts from word array to byte array, len is number of bytes */ 41 static void w2b(uint8_t* out, const uint32_t* in, uint32_t len) { 42 uint8_t* bp; 43 const uint32_t *wp, *wpend; 44 45 bp = out; 46 wp = in; 47 wpend = wp + (len >> 2); 48 49 for (; wp != wpend; ++wp, bp += 4) { 50 bp[0] = (uint8_t)((*wp) & 0xFF); 51 bp[1] = (uint8_t)((*wp >> 8) & 0xFF); 52 bp[2] = (uint8_t)((*wp >> 16) & 0xFF); 53 bp[3] = (uint8_t)((*wp >> 24) & 0xFF); 54 } 55 } 56 57 /* converts from byte array to word array, len is number of bytes */ 58 static void b2w(uint32_t* out, const uint8_t* in, uint32_t len) { 59 uint32_t* wp; 60 const uint8_t *bp, *bpend; 61 62 wp = out; 63 bp = in; 64 bpend = in + len; 65 66 for (; bp != bpend; bp += 4, ++wp) { 67 *wp = (uint32_t)bp[0] | ((uint32_t)bp[1] << 8) | ((uint32_t)bp[2] << 16) | 68 ((uint32_t)bp[3] << 24); 69 } 70 } 71 72 /* update state: data is 64 bytes in length */ 73 static void md4step(uint32_t state[4], const uint8_t* data) { 74 uint32_t A, B, C, D, X[16]; 75 76 b2w(X, data, 64); 77 78 A = state[0]; 79 B = state[1]; 80 C = state[2]; 81 D = state[3]; 82 83 RD1(A, B, C, D, 0, 3); 84 RD1(D, A, B, C, 1, 7); 85 RD1(C, D, A, B, 2, 11); 86 RD1(B, C, D, A, 3, 19); 87 RD1(A, B, C, D, 4, 3); 88 RD1(D, A, B, C, 5, 7); 89 RD1(C, D, A, B, 6, 11); 90 RD1(B, C, D, A, 7, 19); 91 RD1(A, B, C, D, 8, 3); 92 RD1(D, A, B, C, 9, 7); 93 RD1(C, D, A, B, 10, 11); 94 RD1(B, C, D, A, 11, 19); 95 RD1(A, B, C, D, 12, 3); 96 RD1(D, A, B, C, 13, 7); 97 RD1(C, D, A, B, 14, 11); 98 RD1(B, C, D, A, 15, 19); 99 100 RD2(A, B, C, D, 0, 3); 101 RD2(D, A, B, C, 4, 5); 102 RD2(C, D, A, B, 8, 9); 103 RD2(B, C, D, A, 12, 13); 104 RD2(A, B, C, D, 1, 3); 105 RD2(D, A, B, C, 5, 5); 106 RD2(C, D, A, B, 9, 9); 107 RD2(B, C, D, A, 13, 13); 108 RD2(A, B, C, D, 2, 3); 109 RD2(D, A, B, C, 6, 5); 110 RD2(C, D, A, B, 10, 9); 111 RD2(B, C, D, A, 14, 13); 112 RD2(A, B, C, D, 3, 3); 113 RD2(D, A, B, C, 7, 5); 114 RD2(C, D, A, B, 11, 9); 115 RD2(B, C, D, A, 15, 13); 116 117 RD3(A, B, C, D, 0, 3); 118 RD3(D, A, B, C, 8, 9); 119 RD3(C, D, A, B, 4, 11); 120 RD3(B, C, D, A, 12, 15); 121 RD3(A, B, C, D, 2, 3); 122 RD3(D, A, B, C, 10, 9); 123 RD3(C, D, A, B, 6, 11); 124 RD3(B, C, D, A, 14, 15); 125 RD3(A, B, C, D, 1, 3); 126 RD3(D, A, B, C, 9, 9); 127 RD3(C, D, A, B, 5, 11); 128 RD3(B, C, D, A, 13, 15); 129 RD3(A, B, C, D, 3, 3); 130 RD3(D, A, B, C, 11, 9); 131 RD3(C, D, A, B, 7, 11); 132 RD3(B, C, D, A, 15, 15); 133 134 state[0] += A; 135 state[1] += B; 136 state[2] += C; 137 state[3] += D; 138 } 139 140 void md4sum(const uint8_t* input, uint32_t inputLen, uint8_t* result) { 141 uint8_t final[128]; 142 uint32_t i, n, m, state[4]; 143 uint64_t inputLenBits; 144 uint32_t inputLenBitsLow; 145 uint32_t inputLenBitsHigh; 146 147 /* magic initial states */ 148 state[0] = 0x67452301; 149 state[1] = 0xEFCDAB89; 150 state[2] = 0x98BADCFE; 151 state[3] = 0x10325476; 152 153 /* compute number of complete 64-byte segments contained in input */ 154 m = inputLen >> 6; 155 156 /* digest first m segments */ 157 for (i = 0; i < m; ++i) md4step(state, (input + (i << 6))); 158 159 /* build final buffer */ 160 n = inputLen % 64; 161 memcpy(final, input + (m << 6), n); 162 final[n] = 0x80; 163 memset(final + n + 1, 0, 120 - (n + 1)); 164 165 /* Append the original input length in bits as a 64-bit number. This is done 166 * in two 32-bit chunks, with the least-significant 32 bits first. 167 * w2b will handle endianness. */ 168 inputLenBits = inputLen << 3; 169 inputLenBitsLow = (uint32_t)(inputLenBits & 0xFFFFFFFF); 170 w2b(final + (n >= 56 ? 120 : 56), &inputLenBitsLow, 4); 171 inputLenBitsHigh = (uint32_t)((inputLenBits >> 32) & 0xFFFFFFFF); 172 w2b(final + (n >= 56 ? 124 : 60), &inputLenBitsHigh, 4); 173 174 md4step(state, final); 175 if (n >= 56) md4step(state, final + 64); 176 177 /* copy state to result */ 178 w2b(result, state, 16); 179 }