Crypto++  8.5
Free C++ class library of cryptographic schemes
poly1305.cpp
1 // poly1305.cpp - written and placed in the public domain by Jeffrey Walton and Jean-Pierre Munch
2 // Based on Andy Polyakov's Base-2^26 scalar multiplication implementation.
3 // For more information, see https://www.openssl.org/~appro/cryptogams/.
4 
5 // Copyright (c) 2006-2017, CRYPTOGAMS by <appro@openssl.org>
6 // All rights reserved.
7 //
8 // Redistribution and use in source and binary forms, with or without
9 // modification, are permitted provided that the following conditions
10 // are met:
11 //
12 // * Redistributions of source code must retain copyright notices,
13 // this list of conditions and the following disclaimer.
14 // * Redistributions in binary form must reproduce the above
15 // copyright notice, this list of conditions and the following
16 // disclaimer in the documentation and/or other materials
17 // provided with the distribution.
18 // * Neither the name of the CRYPTOGAMS nor the names of its copyright
19 // holder and contributors may be used to endorse or promote products
20 // derived from this software without specific prior written permission.
21 
22 #include "pch.h"
23 #include "cryptlib.h"
24 #include "poly1305.h"
25 #include "aes.h"
26 #include "cpu.h"
27 
28 ////////////////////////////// Common Poly1305 //////////////////////////////
29 
30 ANONYMOUS_NAMESPACE_BEGIN
31 
32 using namespace CryptoPP;
33 
34 inline word32 CONSTANT_TIME_CARRY(word32 a, word32 b)
35 {
36  return ((a ^ ((a ^ b) | ((a - b) ^ b))) >> (sizeof(a) * 8 - 1));
37 }
38 
39 void Poly1305_HashBlocks(word32 h[5], word32 r[4], const byte *input, size_t length, word32 padbit)
40 {
41  word32 r0, r1, r2, r3;
42  word32 s1, s2, s3;
43  word32 h0, h1, h2, h3, h4, c;
44  word64 d0, d1, d2, d3;
45 
46  r0 = r[0]; r1 = r[1];
47  r2 = r[2]; r3 = r[3];
48 
49  s1 = r1 + (r1 >> 2);
50  s2 = r2 + (r2 >> 2);
51  s3 = r3 + (r3 >> 2);
52 
53  h0 = h[0]; h1 = h[1]; h2 = h[2];
54  h3 = h[3]; h4 = h[4];
55 
56  while (length >= 16)
57  {
58  // h += m[i]
59  h0 = (word32)(d0 = (word64)h0 + GetWord<word32>(false, LITTLE_ENDIAN_ORDER, input + 0));
60  h1 = (word32)(d1 = (word64)h1 + (d0 >> 32) + GetWord<word32>(false, LITTLE_ENDIAN_ORDER, input + 4));
61  h2 = (word32)(d2 = (word64)h2 + (d1 >> 32) + GetWord<word32>(false, LITTLE_ENDIAN_ORDER, input + 8));
62  h3 = (word32)(d3 = (word64)h3 + (d2 >> 32) + GetWord<word32>(false, LITTLE_ENDIAN_ORDER, input + 12));
63  h4 += (word32)(d3 >> 32) + padbit;
64 
65  // h *= r "%" p
66  d0 = ((word64)h0 * r0) +
67  ((word64)h1 * s3) +
68  ((word64)h2 * s2) +
69  ((word64)h3 * s1);
70  d1 = ((word64)h0 * r1) +
71  ((word64)h1 * r0) +
72  ((word64)h2 * s3) +
73  ((word64)h3 * s2) +
74  (h4 * s1);
75  d2 = ((word64)h0 * r2) +
76  ((word64)h1 * r1) +
77  ((word64)h2 * r0) +
78  ((word64)h3 * s3) +
79  (h4 * s2);
80  d3 = ((word64)h0 * r3) +
81  ((word64)h1 * r2) +
82  ((word64)h2 * r1) +
83  ((word64)h3 * r0) +
84  (h4 * s3);
85  h4 = (h4 * r0);
86 
87  // a) h4:h0 = h4<<128 + d3<<96 + d2<<64 + d1<<32 + d0
88  h0 = (word32)d0;
89  h1 = (word32)(d1 += d0 >> 32);
90  h2 = (word32)(d2 += d1 >> 32);
91  h3 = (word32)(d3 += d2 >> 32);
92  h4 += (word32)(d3 >> 32);
93 
94  // b) (h4:h0 += (h4:h0>>130) * 5) %= 2^130
95  c = (h4 >> 2) + (h4 & ~3U);
96  h4 &= 3;
97  h0 += c;
98  h1 += (c = CONSTANT_TIME_CARRY(h0,c));
99  h2 += (c = CONSTANT_TIME_CARRY(h1,c));
100  h3 += (c = CONSTANT_TIME_CARRY(h2,c));
101  h4 += CONSTANT_TIME_CARRY(h3,c);
102 
103  input += 16;
104  length -= 16;
105  }
106 
107  h[0] = h0; h[1] = h1; h[2] = h2;
108  h[3] = h3; h[4] = h4;
109 }
110 
111 void Poly1305_HashFinal(word32 h[5], word32 n[4], byte *mac, size_t size)
112 {
113  word32 h0, h1, h2, h3, h4;
114  word32 g0, g1, g2, g3, g4;
115  word32 mask;
116  word64 t;
117 
118  h0 = h[0];
119  h1 = h[1];
120  h2 = h[2];
121  h3 = h[3];
122  h4 = h[4];
123 
124  // compare to modulus by computing h + -p
125  g0 = (word32)(t = (word64)h0 + 5);
126  g1 = (word32)(t = (word64)h1 + (t >> 32));
127  g2 = (word32)(t = (word64)h2 + (t >> 32));
128  g3 = (word32)(t = (word64)h3 + (t >> 32));
129  g4 = h4 + (word32)(t >> 32);
130 
131  // if there was carry into 131st bit, h3:h0 = g3:g0
132  mask = 0 - (g4 >> 2);
133  g0 &= mask; g1 &= mask;
134  g2 &= mask; g3 &= mask;
135  mask = ~mask;
136  h0 = (h0 & mask) | g0; h1 = (h1 & mask) | g1;
137  h2 = (h2 & mask) | g2; h3 = (h3 & mask) | g3;
138 
139  // mac = (h + nonce) % (2^128)
140  h0 = (word32)(t = (word64)h0 + n[0]);
141  h1 = (word32)(t = (word64)h1 + (t >> 32) + n[1]);
142  h2 = (word32)(t = (word64)h2 + (t >> 32) + n[2]);
143  h3 = (word32)(t = (word64)h3 + (t >> 32) + n[3]);
144 
145  if (size >= 16)
146  {
147  PutWord<word32>(false, LITTLE_ENDIAN_ORDER, mac + 0, h0);
148  PutWord<word32>(false, LITTLE_ENDIAN_ORDER, mac + 4, h1);
149  PutWord<word32>(false, LITTLE_ENDIAN_ORDER, mac + 8, h2);
150  PutWord<word32>(false, LITTLE_ENDIAN_ORDER, mac + 12, h3);
151  }
152  else
153  {
155  PutWord<word32>(false, LITTLE_ENDIAN_ORDER, m + 0, h0);
156  PutWord<word32>(false, LITTLE_ENDIAN_ORDER, m + 4, h1);
157  PutWord<word32>(false, LITTLE_ENDIAN_ORDER, m + 8, h2);
158  PutWord<word32>(false, LITTLE_ENDIAN_ORDER, m + 12, h3);
159  std::memcpy(mac, m, size);
160  }
161 }
162 
163 ANONYMOUS_NAMESPACE_END
164 
165 NAMESPACE_BEGIN(CryptoPP)
166 
167 ////////////////////////////// Bernstein Poly1305 //////////////////////////////
168 
169 // TODO: No longer needed. Remove at next major version bump
170 template <class T>
171 void Poly1305_Base<T>::HashBlocks(const byte *input, size_t length, word32 padbit) {
172  CRYPTOPP_UNUSED(input); CRYPTOPP_UNUSED(length); CRYPTOPP_UNUSED(padbit);
173  CRYPTOPP_ASSERT(0);
174 }
175 
176 // TODO: No longer needed. Remove at next major version bump
177 template <class T>
178 void Poly1305_Base<T>::HashFinal(byte *mac, size_t length) {
179  CRYPTOPP_UNUSED(mac); CRYPTOPP_UNUSED(length);
180  CRYPTOPP_ASSERT(0);
181 }
182 
183 template <class T>
185 {
186  return m_cipher.AlgorithmProvider();
187 }
188 
189 template <class T>
190 void Poly1305_Base<T>::UncheckedSetKey(const byte *key, unsigned int length, const NameValuePairs &params)
191 {
192  CRYPTOPP_ASSERT(key && length >= 32);
193 
194  // key is {k,r} pair. k is AES key, r is the additional key that gets clamped
195  length = SaturatingSubtract(length, (unsigned)BLOCKSIZE);
196  m_cipher.SetKey(key, length);
197  key += length;
198 
199  // Rbar is clamped and little endian
200  m_r[0] = GetWord<word32>(false, LITTLE_ENDIAN_ORDER, key + 0) & 0x0fffffff;
201  m_r[1] = GetWord<word32>(false, LITTLE_ENDIAN_ORDER, key + 4) & 0x0ffffffc;
202  m_r[2] = GetWord<word32>(false, LITTLE_ENDIAN_ORDER, key + 8) & 0x0ffffffc;
203  m_r[3] = GetWord<word32>(false, LITTLE_ENDIAN_ORDER, key + 12) & 0x0ffffffc;
204 
205  // Mark the nonce as dirty, meaning we need a new one
206  m_used = true;
207 
209  if (params.GetValue(Name::IV(), t) && t.begin() && t.size())
210  {
211  CRYPTOPP_ASSERT(t.size() == m_nk.size());
212  Resynchronize(t.begin(), (int)t.size());
213  }
214 
215  Restart();
216 }
217 
218 template <class T>
219 void Poly1305_Base<T>::Update(const byte *input, size_t length)
220 {
221  CRYPTOPP_ASSERT((input && length) || !length);
222  if (!length) return;
223 
224  size_t rem, num = m_idx;
225  if (num)
226  {
227  rem = BLOCKSIZE - num;
228  if (length >= rem)
229  {
230  // Process
231  memcpy_s(m_acc + num, BLOCKSIZE - num, input, rem);
232  Poly1305_HashBlocks(m_h, m_r, m_acc, BLOCKSIZE, 1);
233  input += rem; length -= rem;
234  }
235  else
236  {
237  // Accumulate
238  memcpy_s(m_acc + num, BLOCKSIZE - num, input, length);
239  m_idx = num + length;
240  return;
241  }
242  }
243 
244  rem = length % BLOCKSIZE;
245  length -= rem;
246 
247  if (length >= BLOCKSIZE) {
248  Poly1305_HashBlocks(m_h, m_r, input, length, 1);
249  input += length;
250  }
251 
252  if (rem)
253  memcpy(m_acc, input, rem);
254 
255  m_idx = rem;
256 }
257 
258 template <class T>
259 void Poly1305_Base<T>::TruncatedFinal(byte *mac, size_t size)
260 {
261  CRYPTOPP_ASSERT(mac); // Pointer is valid
262  CRYPTOPP_ASSERT(!m_used); // Nonce is fresh
263 
264  ThrowIfInvalidTruncatedSize(size);
265 
266  size_t num = m_idx;
267  if (num)
268  {
269  m_acc[num++] = 1; /* pad bit */
270  while (num < BLOCKSIZE)
271  m_acc[num++] = 0;
272  Poly1305_HashBlocks(m_h, m_r, m_acc, BLOCKSIZE, 0);
273  }
274 
275  Poly1305_HashFinal(m_h, m_n, mac, size);
276 
277  // Restart
278  m_used = true;
279  Restart();
280 }
281 
282 template <class T>
283 void Poly1305_Base<T>::Resynchronize(const byte *nonce, int nonceLength)
284 {
285  CRYPTOPP_ASSERT(nonceLength == -1 || nonceLength == (int)BLOCKSIZE);
286  if (nonceLength == -1) { nonceLength = BLOCKSIZE; }
287 
288  // Encrypt the nonce, stash in m_nk
289  m_cipher.ProcessBlock(nonce, m_nk.begin());
290 
291  m_n[0] = GetWord<word32>(false, LITTLE_ENDIAN_ORDER, m_nk + 0);
292  m_n[1] = GetWord<word32>(false, LITTLE_ENDIAN_ORDER, m_nk + 4);
293  m_n[2] = GetWord<word32>(false, LITTLE_ENDIAN_ORDER, m_nk + 8);
294  m_n[3] = GetWord<word32>(false, LITTLE_ENDIAN_ORDER, m_nk + 12);
295 
296  // Mark nonce as unused, meaning it is fresh
297  m_used = false;
298 }
299 
300 template <class T>
302 {
303  rng.GenerateBlock(iv, BLOCKSIZE);
304 }
305 
306 template <class T>
308 {
309  m_h[0] = m_h[1] = m_h[2] = m_h[3] = m_h[4] = 0;
310  m_idx = 0;
311 }
312 
313 ////////////////////////////// IETF Poly1305 //////////////////////////////
314 
315 void Poly1305TLS_Base::UncheckedSetKey(const byte *key, unsigned int length, const NameValuePairs &params)
316 {
317  CRYPTOPP_UNUSED(params); CRYPTOPP_UNUSED(length);
318  CRYPTOPP_ASSERT(key && length >= 32);
319 
320  // key is {r,s} pair. r is the additional key that gets clamped, s is the nonce.
321  m_r[0] = GetWord<word32>(false, LITTLE_ENDIAN_ORDER, key + 0) & 0x0fffffff;
322  m_r[1] = GetWord<word32>(false, LITTLE_ENDIAN_ORDER, key + 4) & 0x0ffffffc;
323  m_r[2] = GetWord<word32>(false, LITTLE_ENDIAN_ORDER, key + 8) & 0x0ffffffc;
324  m_r[3] = GetWord<word32>(false, LITTLE_ENDIAN_ORDER, key + 12) & 0x0ffffffc;
325 
326  key += 16;
327  m_n[0] = GetWord<word32>(false, LITTLE_ENDIAN_ORDER, key + 0);
328  m_n[1] = GetWord<word32>(false, LITTLE_ENDIAN_ORDER, key + 4);
329  m_n[2] = GetWord<word32>(false, LITTLE_ENDIAN_ORDER, key + 8);
330  m_n[3] = GetWord<word32>(false, LITTLE_ENDIAN_ORDER, key + 12);
331 
332  Restart();
333 }
334 
335 void Poly1305TLS_Base::Update(const byte *input, size_t length)
336 {
337  CRYPTOPP_ASSERT((input && length) || !length);
338  if (!length) return;
339 
340  size_t rem, num = m_idx;
341  if (num)
342  {
343  rem = BLOCKSIZE - num;
344  if (length >= rem)
345  {
346  // Process
347  memcpy_s(m_acc + num, BLOCKSIZE - num, input, rem);
348  Poly1305_HashBlocks(m_h, m_r, m_acc, BLOCKSIZE, 1);
349  input += rem; length -= rem;
350  }
351  else
352  {
353  // Accumulate
354  memcpy_s(m_acc + num, BLOCKSIZE - num, input, length);
355  m_idx = num + length;
356  return;
357  }
358  }
359 
360  rem = length % BLOCKSIZE;
361  length -= rem;
362 
363  if (length >= BLOCKSIZE) {
364  Poly1305_HashBlocks(m_h, m_r, input, length, 1);
365  input += length;
366  }
367 
368  if (rem)
369  memcpy(m_acc, input, rem);
370 
371  m_idx = rem;
372 }
373 
374 void Poly1305TLS_Base::TruncatedFinal(byte *mac, size_t size)
375 {
376  CRYPTOPP_ASSERT(mac); // Pointer is valid
377 
378  ThrowIfInvalidTruncatedSize(size);
379 
380  size_t num = m_idx;
381  if (num)
382  {
383  m_acc[num++] = 1; /* pad bit */
384  while (num < BLOCKSIZE)
385  m_acc[num++] = 0;
386  Poly1305_HashBlocks(m_h, m_r, m_acc, BLOCKSIZE, 0);
387  }
388 
389  Poly1305_HashFinal(m_h, m_n, mac, size);
390 
391  Restart();
392 }
393 
395 {
396  m_h[0] = m_h[1] = m_h[2] = m_h[3] = m_h[4] = 0;
397  m_idx = 0;
398 }
399 
400 template class Poly1305_Base<AES>;
401 template class Poly1305<AES>;
402 
403 NAMESPACE_END
FixedSizeAlignedSecBlock
Fixed size stack-based SecBlock with 16-byte alignment.
Definition: secblock.h:1258
ConstByteArrayParameter::size
size_t size() const
Length of the memory block.
Definition: algparam.h:88
Poly1305TLS_Base::UncheckedSetKey
void UncheckedSetKey(const byte *key, unsigned int length, const NameValuePairs &params)
Sets the key for this object without performing parameter validation.
Definition: poly1305.cpp:315
Poly1305_Base::GetNextIV
void GetNextIV(RandomNumberGenerator &rng, byte *iv)
Retrieves a secure IV for the next message.
Definition: poly1305.cpp:301
Poly1305_Base::Resynchronize
void Resynchronize(const byte *iv, int ivLength=-1)
Resynchronize with an IV.
Definition: poly1305.cpp:283
CRYPTOPP_ASSERT
#define CRYPTOPP_ASSERT(exp)
Debugging and diagnostic assertion.
Definition: trap.h:68
LITTLE_ENDIAN_ORDER
@ LITTLE_ENDIAN_ORDER
byte order is little-endian
Definition: cryptlib.h:145
word64
unsigned long long word64
64-bit unsigned datatype
Definition: config_int.h:91
Poly1305_Base::Restart
void Restart()
Restart the hash.
Definition: poly1305.cpp:307
pch.h
Precompiled header file.
word32
unsigned int word32
32-bit unsigned datatype
Definition: config_int.h:62
RandomNumberGenerator
Interface for random number generators.
Definition: cryptlib.h:1434
poly1305.h
Classes for Poly1305 message authentication code.
aes.h
Class file for the AES cipher (Rijndael)
Poly1305
Poly1305 message authentication code.
Definition: poly1305.h:136
Poly1305TLS_Base::Restart
void Restart()
Restart the hash.
Definition: poly1305.cpp:394
cpu.h
Functions for CPU features and intrinsics.
Poly1305_Base::Update
void Update(const byte *input, size_t length)
Updates a hash with additional input.
Definition: poly1305.cpp:219
Poly1305_Base
Poly1305 message authentication code base class.
Definition: poly1305.h:43
Poly1305_Base::AlgorithmProvider
std::string AlgorithmProvider() const
Retrieve the provider of this algorithm.
Definition: poly1305.cpp:184
RandomNumberGenerator::GenerateBlock
virtual void GenerateBlock(byte *output, size_t size)
Generate random array of bytes.
Poly1305TLS_Base::TruncatedFinal
void TruncatedFinal(byte *mac, size_t size)
Computes the hash of the current message.
Definition: poly1305.cpp:374
Poly1305_Base::UncheckedSetKey
void UncheckedSetKey(const byte *key, unsigned int length, const NameValuePairs &params)
Sets the key for this object without performing parameter validation.
Definition: poly1305.cpp:190
ConstByteArrayParameter::begin
const byte * begin() const
Pointer to the first byte in the memory block.
Definition: algparam.h:84
CryptoPP
Crypto++ library namespace.
NameValuePairs::GetValue
bool GetValue(const char *name, T &value) const
Get a named value.
Definition: cryptlib.h:379
Poly1305_Base::TruncatedFinal
void TruncatedFinal(byte *mac, size_t size)
Computes the hash of the current message.
Definition: poly1305.cpp:259
Poly1305TLS_Base::Update
void Update(const byte *input, size_t length)
Updates a hash with additional input.
Definition: poly1305.cpp:335
SaturatingSubtract
T1 SaturatingSubtract(const T1 &a, const T2 &b)
Performs a saturating subtract clamped at 0.
Definition: misc.h:1093
memcpy_s
void memcpy_s(void *dest, size_t sizeInBytes, const void *src, size_t count)
Bounds checking replacement for memcpy()
Definition: misc.h:525
NameValuePairs
Interface for retrieving values given their names.
Definition: cryptlib.h:321
cryptlib.h
Abstract base classes that provide a uniform interface to this library.
ConstByteArrayParameter
Used to pass byte array input as part of a NameValuePairs object.
Definition: algparam.h:24