Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(294)

Side by Side Diff: crypto/ghash.cc

Issue 1539353003: Switch to standard integer types in crypto/. (Closed) Base URL: https://chromium.googlesource.com/chromium/src.git@master
Patch Set: fix Created 4 years, 12 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View unified diff | Download patch
« no previous file with comments | « crypto/ghash.h ('k') | crypto/ghash_unittest.cc » ('j') | no next file with comments »
Toggle Intra-line Diffs ('i') | Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
OLDNEW
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
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
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
OLDNEW
« no previous file with comments | « crypto/ghash.h ('k') | crypto/ghash_unittest.cc » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698