bungeman@google.com | cfcb1be | 2013-01-31 19:47:48 +0000 | [diff] [blame] | 1 | /* |
| 2 | * Copyright 2013 Google Inc. |
| 3 | * |
| 4 | * Use of this source code is governed by a BSD-style license that can be |
| 5 | * found in the LICENSE file. |
| 6 | * |
| 7 | * The following code is based on the description in RFC 3174. |
| 8 | * http://www.ietf.org/rfc/rfc3174.txt |
| 9 | */ |
| 10 | |
| 11 | #include "SkTypes.h" |
| 12 | #include "SkSHA1.h" |
| 13 | #include <string.h> |
| 14 | |
| 15 | /** SHA1 basic transformation. Transforms state based on block. */ |
| 16 | static void transform(uint32_t state[5], const uint8_t block[64]); |
| 17 | |
| 18 | /** Encodes input into output (5 big endian 32 bit values). */ |
| 19 | static void encode(uint8_t output[20], const uint32_t input[5]); |
| 20 | |
| 21 | /** Encodes input into output (big endian 64 bit value). */ |
| 22 | static void encode(uint8_t output[8], const uint64_t input); |
| 23 | |
| 24 | SkSHA1::SkSHA1() : byteCount(0) { |
| 25 | // These are magic numbers from the specification. The first four are the same as MD5. |
| 26 | this->state[0] = 0x67452301; |
| 27 | this->state[1] = 0xefcdab89; |
| 28 | this->state[2] = 0x98badcfe; |
| 29 | this->state[3] = 0x10325476; |
| 30 | this->state[4] = 0xc3d2e1f0; |
| 31 | } |
| 32 | |
| 33 | void SkSHA1::update(const uint8_t* input, size_t inputLength) { |
| 34 | unsigned int bufferIndex = (unsigned int)(this->byteCount & 0x3F); |
| 35 | unsigned int bufferAvailable = 64 - bufferIndex; |
| 36 | |
| 37 | unsigned int inputIndex; |
| 38 | if (inputLength >= bufferAvailable) { |
| 39 | if (bufferIndex) { |
| 40 | memcpy(&this->buffer[bufferIndex], input, bufferAvailable); |
| 41 | transform(this->state, this->buffer); |
| 42 | inputIndex = bufferAvailable; |
| 43 | } else { |
| 44 | inputIndex = 0; |
| 45 | } |
| 46 | |
| 47 | for (; inputIndex + 63 < inputLength; inputIndex += 64) { |
| 48 | transform(this->state, &input[inputIndex]); |
| 49 | } |
| 50 | |
| 51 | bufferIndex = 0; |
| 52 | } else { |
| 53 | inputIndex = 0; |
| 54 | } |
| 55 | |
| 56 | memcpy(&this->buffer[bufferIndex], &input[inputIndex], inputLength - inputIndex); |
| 57 | |
| 58 | this->byteCount += inputLength; |
| 59 | } |
| 60 | |
| 61 | void SkSHA1::finish(Digest& digest) { |
| 62 | // Get the number of bits before padding. |
| 63 | uint8_t bits[8]; |
| 64 | encode(bits, this->byteCount << 3); |
| 65 | |
| 66 | // Pad out to 56 mod 64. |
| 67 | unsigned int bufferIndex = (unsigned int)(this->byteCount & 0x3F); |
| 68 | unsigned int paddingLength = (bufferIndex < 56) ? (56 - bufferIndex) : (120 - bufferIndex); |
| 69 | static uint8_t PADDING[64] = { |
| 70 | 0x80, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, |
| 71 | 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, |
| 72 | 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, |
| 73 | 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, |
| 74 | }; |
| 75 | this->update(PADDING, paddingLength); |
| 76 | |
| 77 | // Append length (length before padding, will cause final update). |
| 78 | this->update(bits, 8); |
| 79 | |
| 80 | // Write out digest. |
| 81 | encode(digest.data, this->state); |
| 82 | |
| 83 | #if defined(SK_SHA1_CLEAR_DATA) |
| 84 | // Clear state. |
| 85 | memset(this, 0, sizeof(*this)); |
| 86 | #endif |
| 87 | } |
| 88 | |
| 89 | struct F1 { uint32_t operator()(uint32_t B, uint32_t C, uint32_t D) { |
| 90 | return (B & C) | ((~B) & D); |
| 91 | //return D ^ (B & (C ^ D)); |
| 92 | //return (B & C) ^ ((~B) & D); |
| 93 | //return (B & C) + ((~B) & D); |
| 94 | //return _mm_or_ps(_mm_andnot_ps(B, D), _mm_and_ps(B, C)); //SSE2 |
| 95 | //return vec_sel(D, C, B); //PPC |
| 96 | }}; |
| 97 | |
| 98 | struct F2 { uint32_t operator()(uint32_t B, uint32_t C, uint32_t D) { |
| 99 | return B ^ C ^ D; |
| 100 | }}; |
| 101 | |
| 102 | struct F3 { uint32_t operator()(uint32_t B, uint32_t C, uint32_t D) { |
| 103 | return (B & C) | (B & D) | (C & D); |
| 104 | //return (B & C) | (D & (B | C)); |
| 105 | //return (B & C) | (D & (B ^ C)); |
| 106 | //return (B & C) + (D & (B ^ C)); |
| 107 | //return (B & C) ^ (B & D) ^ (C & D); |
| 108 | }}; |
| 109 | |
| 110 | /** Rotates x left n bits. */ |
| 111 | static inline uint32_t rotate_left(uint32_t x, uint8_t n) { |
| 112 | return (x << n) | (x >> (32 - n)); |
| 113 | } |
| 114 | |
| 115 | template <typename T> |
| 116 | static inline void operation(T operation, |
| 117 | uint32_t A, uint32_t& B, uint32_t C, uint32_t D, uint32_t& E, |
| 118 | uint32_t w, uint32_t k) { |
| 119 | E += rotate_left(A, 5) + operation(B, C, D) + w + k; |
| 120 | B = rotate_left(B, 30); |
| 121 | } |
| 122 | |
| 123 | static void transform(uint32_t state[5], const uint8_t block[64]) { |
| 124 | uint32_t A = state[0], B = state[1], C = state[2], D = state[3], E = state[4]; |
| 125 | |
| 126 | // Round constants defined in SHA-1. |
| 127 | static const uint32_t K[] = { |
| 128 | 0x5A827999, //sqrt(2) * 2^30 |
| 129 | 0x6ED9EBA1, //sqrt(3) * 2^30 |
| 130 | 0x8F1BBCDC, //sqrt(5) * 2^30 |
| 131 | 0xCA62C1D6, //sqrt(10) * 2^30 |
| 132 | }; |
| 133 | |
| 134 | uint32_t W[80]; |
| 135 | |
| 136 | // Initialize the array W. |
| 137 | size_t i = 0; |
| 138 | for (size_t j = 0; i < 16; ++i, j += 4) { |
| 139 | W[i] = (((uint32_t)block[j ]) << 24) | |
| 140 | (((uint32_t)block[j+1]) << 16) | |
| 141 | (((uint32_t)block[j+2]) << 8) | |
| 142 | (((uint32_t)block[j+3]) ); |
| 143 | } |
| 144 | for (; i < 80; ++i) { |
| 145 | W[i] = rotate_left(W[i-3] ^ W[i-8] ^ W[i-14] ^ W[i-16], 1); |
| 146 | //The following is equivelent and speeds up SSE implementations, but slows non-SSE. |
| 147 | //W[i] = rotate_left(W[i-6] ^ W[i-16] ^ W[i-28] ^ W[i-32], 2); |
| 148 | } |
| 149 | |
| 150 | // Round 1 |
| 151 | operation(F1(), A, B, C, D, E, W[ 0], K[0]); |
| 152 | operation(F1(), E, A, B, C, D, W[ 1], K[0]); |
| 153 | operation(F1(), D, E, A, B, C, W[ 2], K[0]); |
| 154 | operation(F1(), C, D, E, A, B, W[ 3], K[0]); |
| 155 | operation(F1(), B, C, D, E, A, W[ 4], K[0]); |
| 156 | operation(F1(), A, B, C, D, E, W[ 5], K[0]); |
| 157 | operation(F1(), E, A, B, C, D, W[ 6], K[0]); |
| 158 | operation(F1(), D, E, A, B, C, W[ 7], K[0]); |
| 159 | operation(F1(), C, D, E, A, B, W[ 8], K[0]); |
| 160 | operation(F1(), B, C, D, E, A, W[ 9], K[0]); |
| 161 | operation(F1(), A, B, C, D, E, W[10], K[0]); |
| 162 | operation(F1(), E, A, B, C, D, W[11], K[0]); |
| 163 | operation(F1(), D, E, A, B, C, W[12], K[0]); |
| 164 | operation(F1(), C, D, E, A, B, W[13], K[0]); |
| 165 | operation(F1(), B, C, D, E, A, W[14], K[0]); |
| 166 | operation(F1(), A, B, C, D, E, W[15], K[0]); |
| 167 | operation(F1(), E, A, B, C, D, W[16], K[0]); |
| 168 | operation(F1(), D, E, A, B, C, W[17], K[0]); |
| 169 | operation(F1(), C, D, E, A, B, W[18], K[0]); |
| 170 | operation(F1(), B, C, D, E, A, W[19], K[0]); |
| 171 | |
| 172 | // Round 2 |
| 173 | operation(F2(), A, B, C, D, E, W[20], K[1]); |
| 174 | operation(F2(), E, A, B, C, D, W[21], K[1]); |
| 175 | operation(F2(), D, E, A, B, C, W[22], K[1]); |
| 176 | operation(F2(), C, D, E, A, B, W[23], K[1]); |
| 177 | operation(F2(), B, C, D, E, A, W[24], K[1]); |
| 178 | operation(F2(), A, B, C, D, E, W[25], K[1]); |
| 179 | operation(F2(), E, A, B, C, D, W[26], K[1]); |
| 180 | operation(F2(), D, E, A, B, C, W[27], K[1]); |
| 181 | operation(F2(), C, D, E, A, B, W[28], K[1]); |
| 182 | operation(F2(), B, C, D, E, A, W[29], K[1]); |
| 183 | operation(F2(), A, B, C, D, E, W[30], K[1]); |
| 184 | operation(F2(), E, A, B, C, D, W[31], K[1]); |
| 185 | operation(F2(), D, E, A, B, C, W[32], K[1]); |
| 186 | operation(F2(), C, D, E, A, B, W[33], K[1]); |
| 187 | operation(F2(), B, C, D, E, A, W[34], K[1]); |
| 188 | operation(F2(), A, B, C, D, E, W[35], K[1]); |
| 189 | operation(F2(), E, A, B, C, D, W[36], K[1]); |
| 190 | operation(F2(), D, E, A, B, C, W[37], K[1]); |
| 191 | operation(F2(), C, D, E, A, B, W[38], K[1]); |
| 192 | operation(F2(), B, C, D, E, A, W[39], K[1]); |
| 193 | |
| 194 | // Round 3 |
| 195 | operation(F3(), A, B, C, D, E, W[40], K[2]); |
| 196 | operation(F3(), E, A, B, C, D, W[41], K[2]); |
| 197 | operation(F3(), D, E, A, B, C, W[42], K[2]); |
| 198 | operation(F3(), C, D, E, A, B, W[43], K[2]); |
| 199 | operation(F3(), B, C, D, E, A, W[44], K[2]); |
| 200 | operation(F3(), A, B, C, D, E, W[45], K[2]); |
| 201 | operation(F3(), E, A, B, C, D, W[46], K[2]); |
| 202 | operation(F3(), D, E, A, B, C, W[47], K[2]); |
| 203 | operation(F3(), C, D, E, A, B, W[48], K[2]); |
| 204 | operation(F3(), B, C, D, E, A, W[49], K[2]); |
| 205 | operation(F3(), A, B, C, D, E, W[50], K[2]); |
| 206 | operation(F3(), E, A, B, C, D, W[51], K[2]); |
| 207 | operation(F3(), D, E, A, B, C, W[52], K[2]); |
| 208 | operation(F3(), C, D, E, A, B, W[53], K[2]); |
| 209 | operation(F3(), B, C, D, E, A, W[54], K[2]); |
| 210 | operation(F3(), A, B, C, D, E, W[55], K[2]); |
| 211 | operation(F3(), E, A, B, C, D, W[56], K[2]); |
| 212 | operation(F3(), D, E, A, B, C, W[57], K[2]); |
| 213 | operation(F3(), C, D, E, A, B, W[58], K[2]); |
| 214 | operation(F3(), B, C, D, E, A, W[59], K[2]); |
| 215 | |
| 216 | // Round 4 |
| 217 | operation(F2(), A, B, C, D, E, W[60], K[3]); |
| 218 | operation(F2(), E, A, B, C, D, W[61], K[3]); |
| 219 | operation(F2(), D, E, A, B, C, W[62], K[3]); |
| 220 | operation(F2(), C, D, E, A, B, W[63], K[3]); |
| 221 | operation(F2(), B, C, D, E, A, W[64], K[3]); |
| 222 | operation(F2(), A, B, C, D, E, W[65], K[3]); |
| 223 | operation(F2(), E, A, B, C, D, W[66], K[3]); |
| 224 | operation(F2(), D, E, A, B, C, W[67], K[3]); |
| 225 | operation(F2(), C, D, E, A, B, W[68], K[3]); |
| 226 | operation(F2(), B, C, D, E, A, W[69], K[3]); |
| 227 | operation(F2(), A, B, C, D, E, W[70], K[3]); |
| 228 | operation(F2(), E, A, B, C, D, W[71], K[3]); |
| 229 | operation(F2(), D, E, A, B, C, W[72], K[3]); |
| 230 | operation(F2(), C, D, E, A, B, W[73], K[3]); |
| 231 | operation(F2(), B, C, D, E, A, W[74], K[3]); |
| 232 | operation(F2(), A, B, C, D, E, W[75], K[3]); |
| 233 | operation(F2(), E, A, B, C, D, W[76], K[3]); |
| 234 | operation(F2(), D, E, A, B, C, W[77], K[3]); |
| 235 | operation(F2(), C, D, E, A, B, W[78], K[3]); |
| 236 | operation(F2(), B, C, D, E, A, W[79], K[3]); |
| 237 | |
| 238 | state[0] += A; |
| 239 | state[1] += B; |
| 240 | state[2] += C; |
| 241 | state[3] += D; |
| 242 | state[4] += E; |
| 243 | |
| 244 | #if defined(SK_SHA1_CLEAR_DATA) |
| 245 | // Clear sensitive information. |
| 246 | memset(W, 0, sizeof(W)); |
| 247 | #endif |
| 248 | } |
| 249 | |
| 250 | static void encode(uint8_t output[20], const uint32_t input[5]) { |
| 251 | for (size_t i = 0, j = 0; i < 5; i++, j += 4) { |
| 252 | output[j ] = (uint8_t)((input[i] >> 24) & 0xff); |
| 253 | output[j+1] = (uint8_t)((input[i] >> 16) & 0xff); |
| 254 | output[j+2] = (uint8_t)((input[i] >> 8) & 0xff); |
| 255 | output[j+3] = (uint8_t)((input[i] ) & 0xff); |
| 256 | } |
| 257 | } |
| 258 | |
| 259 | static void encode(uint8_t output[8], const uint64_t input) { |
| 260 | output[0] = (uint8_t)((input >> 56) & 0xff); |
| 261 | output[1] = (uint8_t)((input >> 48) & 0xff); |
| 262 | output[2] = (uint8_t)((input >> 40) & 0xff); |
| 263 | output[3] = (uint8_t)((input >> 32) & 0xff); |
| 264 | output[4] = (uint8_t)((input >> 24) & 0xff); |
| 265 | output[5] = (uint8_t)((input >> 16) & 0xff); |
| 266 | output[6] = (uint8_t)((input >> 8) & 0xff); |
| 267 | output[7] = (uint8_t)((input ) & 0xff); |
| 268 | } |