OLD | NEW |
1 // Copyright (c) 2012 The Chromium Authors. All rights reserved. | 1 // Copyright (c) 2012 The Chromium Authors. All rights reserved. |
2 // Use of this source code is governed by a BSD-style license that can be | 2 // Use of this source code is governed by a BSD-style license that can be |
3 // found in the LICENSE file. | 3 // found in the LICENSE file. |
4 | 4 |
5 #include "crypto/ghash.h" | 5 #include "crypto/ghash.h" |
6 | 6 |
| 7 #include <stddef.h> |
| 8 #include <stdint.h> |
| 9 |
7 #include <algorithm> | 10 #include <algorithm> |
8 | 11 |
9 #include "base/logging.h" | 12 #include "base/logging.h" |
10 #include "base/sys_byteorder.h" | 13 #include "base/sys_byteorder.h" |
11 | 14 |
12 namespace crypto { | 15 namespace crypto { |
13 | 16 |
14 // GaloisHash is a polynomial authenticator that works in GF(2^128). | 17 // GaloisHash is a polynomial authenticator that works in GF(2^128). |
15 // | 18 // |
16 // Elements of the field are represented in `little-endian' order (which | 19 // Elements of the field are represented in `little-endian' order (which |
17 // matches the description in the paper[1]), thus the most significant bit is | 20 // matches the description in the paper[1]), thus the most significant bit is |
18 // the right-most bit. (This is backwards from the way that everybody else does | 21 // the right-most bit. (This is backwards from the way that everybody else does |
19 // it.) | 22 // it.) |
20 // | 23 // |
21 // We store field elements in a pair of such `little-endian' uint64s. So the | 24 // We store field elements in a pair of such `little-endian' uint64s. So the |
22 // value one is represented by {low = 2**63, high = 0} and doubling a value | 25 // value one is represented by {low = 2**63, high = 0} and doubling a value |
23 // involves a *right* shift. | 26 // involves a *right* shift. |
24 // | 27 // |
25 // [1] http://csrc.nist.gov/groups/ST/toolkit/BCM/documents/proposedmodes/gcm/gc
m-revised-spec.pdf | 28 // [1] http://csrc.nist.gov/groups/ST/toolkit/BCM/documents/proposedmodes/gcm/gc
m-revised-spec.pdf |
26 | 29 |
27 namespace { | 30 namespace { |
28 | 31 |
29 // Get64 reads a 64-bit, big-endian number from |bytes|. | 32 // Get64 reads a 64-bit, big-endian number from |bytes|. |
30 uint64 Get64(const uint8 bytes[8]) { | 33 uint64_t Get64(const uint8_t bytes[8]) { |
31 uint64 t; | 34 uint64_t t; |
32 memcpy(&t, bytes, sizeof(t)); | 35 memcpy(&t, bytes, sizeof(t)); |
33 return base::NetToHost64(t); | 36 return base::NetToHost64(t); |
34 } | 37 } |
35 | 38 |
36 // Put64 writes |x| to |bytes| as a 64-bit, big-endian number. | 39 // Put64 writes |x| to |bytes| as a 64-bit, big-endian number. |
37 void Put64(uint8 bytes[8], uint64 x) { | 40 void Put64(uint8_t bytes[8], uint64_t x) { |
38 x = base::HostToNet64(x); | 41 x = base::HostToNet64(x); |
39 memcpy(bytes, &x, sizeof(x)); | 42 memcpy(bytes, &x, sizeof(x)); |
40 } | 43 } |
41 | 44 |
42 // Reverse reverses the order of the bits of 4-bit number in |i|. | 45 // Reverse reverses the order of the bits of 4-bit number in |i|. |
43 int Reverse(int i) { | 46 int Reverse(int i) { |
44 i = ((i << 2) & 0xc) | ((i >> 2) & 0x3); | 47 i = ((i << 2) & 0xc) | ((i >> 2) & 0x3); |
45 i = ((i << 1) & 0xa) | ((i >> 1) & 0x5); | 48 i = ((i << 1) & 0xa) | ((i >> 1) & 0x5); |
46 return i; | 49 return i; |
47 } | 50 } |
48 | 51 |
49 } // namespace | 52 } // namespace |
50 | 53 |
51 GaloisHash::GaloisHash(const uint8 key[16]) { | 54 GaloisHash::GaloisHash(const uint8_t key[16]) { |
52 Reset(); | 55 Reset(); |
53 | 56 |
54 // We precompute 16 multiples of |key|. However, when we do lookups into this | 57 // We precompute 16 multiples of |key|. However, when we do lookups into this |
55 // table we'll be using bits from a field element and therefore the bits will | 58 // table we'll be using bits from a field element and therefore the bits will |
56 // be in the reverse order. So normally one would expect, say, 4*key to be in | 59 // be in the reverse order. So normally one would expect, say, 4*key to be in |
57 // index 4 of the table but due to this bit ordering it will actually be in | 60 // index 4 of the table but due to this bit ordering it will actually be in |
58 // index 0010 (base 2) = 2. | 61 // index 0010 (base 2) = 2. |
59 FieldElement x = {Get64(key), Get64(key+8)}; | 62 FieldElement x = {Get64(key), Get64(key+8)}; |
60 product_table_[0].low = 0; | 63 product_table_[0].low = 0; |
61 product_table_[0].hi = 0; | 64 product_table_[0].hi = 0; |
62 product_table_[Reverse(1)] = x; | 65 product_table_[Reverse(1)] = x; |
63 | 66 |
64 for (int i = 0; i < 16; i += 2) { | 67 for (int i = 0; i < 16; i += 2) { |
65 product_table_[Reverse(i)] = Double(product_table_[Reverse(i/2)]); | 68 product_table_[Reverse(i)] = Double(product_table_[Reverse(i/2)]); |
66 product_table_[Reverse(i+1)] = Add(product_table_[Reverse(i)], x); | 69 product_table_[Reverse(i+1)] = Add(product_table_[Reverse(i)], x); |
67 } | 70 } |
68 } | 71 } |
69 | 72 |
70 void GaloisHash::Reset() { | 73 void GaloisHash::Reset() { |
71 state_ = kHashingAdditionalData; | 74 state_ = kHashingAdditionalData; |
72 additional_bytes_ = 0; | 75 additional_bytes_ = 0; |
73 ciphertext_bytes_ = 0; | 76 ciphertext_bytes_ = 0; |
74 buf_used_ = 0; | 77 buf_used_ = 0; |
75 y_.low = 0; | 78 y_.low = 0; |
76 y_.hi = 0; | 79 y_.hi = 0; |
77 } | 80 } |
78 | 81 |
79 void GaloisHash::UpdateAdditional(const uint8* data, size_t length) { | 82 void GaloisHash::UpdateAdditional(const uint8_t* data, size_t length) { |
80 DCHECK_EQ(state_, kHashingAdditionalData); | 83 DCHECK_EQ(state_, kHashingAdditionalData); |
81 additional_bytes_ += length; | 84 additional_bytes_ += length; |
82 Update(data, length); | 85 Update(data, length); |
83 } | 86 } |
84 | 87 |
85 void GaloisHash::UpdateCiphertext(const uint8* data, size_t length) { | 88 void GaloisHash::UpdateCiphertext(const uint8_t* data, size_t length) { |
86 if (state_ == kHashingAdditionalData) { | 89 if (state_ == kHashingAdditionalData) { |
87 // If there's any remaining additional data it's zero padded to the next | 90 // If there's any remaining additional data it's zero padded to the next |
88 // full block. | 91 // full block. |
89 if (buf_used_ > 0) { | 92 if (buf_used_ > 0) { |
90 memset(&buf_[buf_used_], 0, sizeof(buf_)-buf_used_); | 93 memset(&buf_[buf_used_], 0, sizeof(buf_)-buf_used_); |
91 UpdateBlocks(buf_, 1); | 94 UpdateBlocks(buf_, 1); |
92 buf_used_ = 0; | 95 buf_used_ = 0; |
93 } | 96 } |
94 state_ = kHashingCiphertext; | 97 state_ = kHashingCiphertext; |
95 } | 98 } |
(...skipping 15 matching lines...) Expand all Loading... |
111 } | 114 } |
112 | 115 |
113 state_ = kComplete; | 116 state_ = kComplete; |
114 | 117 |
115 // The lengths of the additional data and ciphertext are included as the last | 118 // The lengths of the additional data and ciphertext are included as the last |
116 // block. The lengths are the number of bits. | 119 // block. The lengths are the number of bits. |
117 y_.low ^= additional_bytes_*8; | 120 y_.low ^= additional_bytes_*8; |
118 y_.hi ^= ciphertext_bytes_*8; | 121 y_.hi ^= ciphertext_bytes_*8; |
119 MulAfterPrecomputation(product_table_, &y_); | 122 MulAfterPrecomputation(product_table_, &y_); |
120 | 123 |
121 uint8 *result, result_tmp[16]; | 124 uint8_t *result, result_tmp[16]; |
122 if (len >= 16) { | 125 if (len >= 16) { |
123 result = reinterpret_cast<uint8*>(output); | 126 result = reinterpret_cast<uint8_t*>(output); |
124 } else { | 127 } else { |
125 result = result_tmp; | 128 result = result_tmp; |
126 } | 129 } |
127 | 130 |
128 Put64(result, y_.low); | 131 Put64(result, y_.low); |
129 Put64(result + 8, y_.hi); | 132 Put64(result + 8, y_.hi); |
130 | 133 |
131 if (len < 16) | 134 if (len < 16) |
132 memcpy(output, result_tmp, len); | 135 memcpy(output, result_tmp, len); |
133 } | 136 } |
(...skipping 36 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
170 // In order to efficiently multiply, we use the precomputed table of i*key, | 173 // In order to efficiently multiply, we use the precomputed table of i*key, |
171 // for i in 0..15, to handle four bits at a time. We could obviously use | 174 // for i in 0..15, to handle four bits at a time. We could obviously use |
172 // larger tables for greater speedups but the next convenient table size is | 175 // larger tables for greater speedups but the next convenient table size is |
173 // 4K, which is a little large. | 176 // 4K, which is a little large. |
174 // | 177 // |
175 // In other fields one would use bit positions spread out across the field in | 178 // In other fields one would use bit positions spread out across the field in |
176 // order to reduce the number of doublings required. However, in | 179 // order to reduce the number of doublings required. However, in |
177 // characteristic 2 fields, repeated doublings are exceptionally cheap and | 180 // characteristic 2 fields, repeated doublings are exceptionally cheap and |
178 // it's not worth spending more precomputation time to eliminate them. | 181 // it's not worth spending more precomputation time to eliminate them. |
179 for (unsigned i = 0; i < 2; i++) { | 182 for (unsigned i = 0; i < 2; i++) { |
180 uint64 word; | 183 uint64_t word; |
181 if (i == 0) { | 184 if (i == 0) { |
182 word = x->hi; | 185 word = x->hi; |
183 } else { | 186 } else { |
184 word = x->low; | 187 word = x->low; |
185 } | 188 } |
186 | 189 |
187 for (unsigned j = 0; j < 64; j += 4) { | 190 for (unsigned j = 0; j < 64; j += 4) { |
188 Mul16(&z); | 191 Mul16(&z); |
189 // the values in |table| are ordered for little-endian bit positions. See | 192 // the values in |table| are ordered for little-endian bit positions. See |
190 // the comment in the constructor. | 193 // the comment in the constructor. |
191 const FieldElement& t = table[word & 0xf]; | 194 const FieldElement& t = table[word & 0xf]; |
192 z.low ^= t.low; | 195 z.low ^= t.low; |
193 z.hi ^= t.hi; | 196 z.hi ^= t.hi; |
194 word >>= 4; | 197 word >>= 4; |
195 } | 198 } |
196 } | 199 } |
197 | 200 |
198 *x = z; | 201 *x = z; |
199 } | 202 } |
200 | 203 |
201 // kReductionTable allows for rapid multiplications by 16. A multiplication by | 204 // kReductionTable allows for rapid multiplications by 16. A multiplication by |
202 // 16 is a right shift by four bits, which results in four bits at 2**128. | 205 // 16 is a right shift by four bits, which results in four bits at 2**128. |
203 // These terms have to be eliminated by dividing by the irreducible polynomial. | 206 // These terms have to be eliminated by dividing by the irreducible polynomial. |
204 // In GHASH, the polynomial is such that all the terms occur in the | 207 // In GHASH, the polynomial is such that all the terms occur in the |
205 // least-significant 8 bits, save for the term at x^128. Therefore we can | 208 // least-significant 8 bits, save for the term at x^128. Therefore we can |
206 // precompute the value to be added to the field element for each of the 16 bit | 209 // precompute the value to be added to the field element for each of the 16 bit |
207 // patterns at 2**128 and the values fit within 12 bits. | 210 // patterns at 2**128 and the values fit within 12 bits. |
208 static const uint16 kReductionTable[16] = { | 211 static const uint16_t kReductionTable[16] = { |
209 0x0000, 0x1c20, 0x3840, 0x2460, 0x7080, 0x6ca0, 0x48c0, 0x54e0, | 212 0x0000, 0x1c20, 0x3840, 0x2460, 0x7080, 0x6ca0, 0x48c0, 0x54e0, |
210 0xe100, 0xfd20, 0xd940, 0xc560, 0x9180, 0x8da0, 0xa9c0, 0xb5e0, | 213 0xe100, 0xfd20, 0xd940, 0xc560, 0x9180, 0x8da0, 0xa9c0, 0xb5e0, |
211 }; | 214 }; |
212 | 215 |
213 // static | 216 // static |
214 void GaloisHash::Mul16(FieldElement* x) { | 217 void GaloisHash::Mul16(FieldElement* x) { |
215 const unsigned msw = x->hi & 0xf; | 218 const unsigned msw = x->hi & 0xf; |
216 x->hi >>= 4; | 219 x->hi >>= 4; |
217 x->hi |= x->low << 60; | 220 x->hi |= x->low << 60; |
218 x->low >>= 4; | 221 x->low >>= 4; |
219 x->low ^= static_cast<uint64>(kReductionTable[msw]) << 48; | 222 x->low ^= static_cast<uint64_t>(kReductionTable[msw]) << 48; |
220 } | 223 } |
221 | 224 |
222 void GaloisHash::UpdateBlocks(const uint8* bytes, size_t num_blocks) { | 225 void GaloisHash::UpdateBlocks(const uint8_t* bytes, size_t num_blocks) { |
223 for (size_t i = 0; i < num_blocks; i++) { | 226 for (size_t i = 0; i < num_blocks; i++) { |
224 y_.low ^= Get64(bytes); | 227 y_.low ^= Get64(bytes); |
225 bytes += 8; | 228 bytes += 8; |
226 y_.hi ^= Get64(bytes); | 229 y_.hi ^= Get64(bytes); |
227 bytes += 8; | 230 bytes += 8; |
228 MulAfterPrecomputation(product_table_, &y_); | 231 MulAfterPrecomputation(product_table_, &y_); |
229 } | 232 } |
230 } | 233 } |
231 | 234 |
232 void GaloisHash::Update(const uint8* data, size_t length) { | 235 void GaloisHash::Update(const uint8_t* data, size_t length) { |
233 if (buf_used_ > 0) { | 236 if (buf_used_ > 0) { |
234 const size_t n = std::min(length, sizeof(buf_) - buf_used_); | 237 const size_t n = std::min(length, sizeof(buf_) - buf_used_); |
235 memcpy(&buf_[buf_used_], data, n); | 238 memcpy(&buf_[buf_used_], data, n); |
236 buf_used_ += n; | 239 buf_used_ += n; |
237 length -= n; | 240 length -= n; |
238 data += n; | 241 data += n; |
239 | 242 |
240 if (buf_used_ == sizeof(buf_)) { | 243 if (buf_used_ == sizeof(buf_)) { |
241 UpdateBlocks(buf_, 1); | 244 UpdateBlocks(buf_, 1); |
242 buf_used_ = 0; | 245 buf_used_ = 0; |
243 } | 246 } |
244 } | 247 } |
245 | 248 |
246 if (length >= 16) { | 249 if (length >= 16) { |
247 const size_t n = length / 16; | 250 const size_t n = length / 16; |
248 UpdateBlocks(data, n); | 251 UpdateBlocks(data, n); |
249 length -= n*16; | 252 length -= n*16; |
250 data += n*16; | 253 data += n*16; |
251 } | 254 } |
252 | 255 |
253 if (length > 0) { | 256 if (length > 0) { |
254 memcpy(buf_, data, length); | 257 memcpy(buf_, data, length); |
255 buf_used_ = length; | 258 buf_used_ = length; |
256 } | 259 } |
257 } | 260 } |
258 | 261 |
259 } // namespace crypto | 262 } // namespace crypto |
OLD | NEW |