Crypto++ 8.9
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 <[email protected]>
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
30ANONYMOUS_NAMESPACE_BEGIN
31
32using namespace CryptoPP;
33
34inline word32 CONSTANT_TIME_CARRY(word32 a, word32 b)
35{
36 return ((a ^ ((a ^ b) | ((a - b) ^ b))) >> (sizeof(a) * 8 - 1));
37}
38
39void 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
111void 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
163ANONYMOUS_NAMESPACE_END
164
165NAMESPACE_BEGIN(CryptoPP)
166
167////////////////////////////// Bernstein Poly1305 //////////////////////////////
168
169// TODO: No longer needed. Remove at next major version bump
170template <class T>
171void Poly1305_Base<T>::HashBlocks(const byte *input, size_t length, word32 padbit) {
172 CRYPTOPP_UNUSED(input); CRYPTOPP_UNUSED(length); CRYPTOPP_UNUSED(padbit);
174}
175
176// TODO: No longer needed. Remove at next major version bump
177template <class T>
178void Poly1305_Base<T>::HashFinal(byte *mac, size_t length) {
179 CRYPTOPP_UNUSED(mac); CRYPTOPP_UNUSED(length);
181}
182
183template <class T>
185{
186 return m_cipher.AlgorithmProvider();
187}
188
189template <class T>
190void 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
218template <class T>
219void 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 std::memcpy(m_acc, input, rem);
254
255 m_idx = rem;
256}
257
258template <class T>
259void 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
282template <class T>
283void 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
300template <class T>
302{
303 rng.GenerateBlock(iv, BLOCKSIZE);
304}
305
306template <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
315void 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
335void 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 std::memcpy(m_acc, input, rem);
370
371 m_idx = rem;
372}
373
374void 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
400template class Poly1305_Base<AES>;
401template class Poly1305<AES>;
402
403NAMESPACE_END
Class file for the AES cipher (Rijndael)
Used to pass byte array input as part of a NameValuePairs object.
Definition algparam.h:25
const byte * begin() const
Pointer to the first byte in the memory block.
Definition algparam.h:84
size_t size() const
Length of the memory block.
Definition algparam.h:88
Fixed size stack-based SecBlock with 16-byte alignment.
Definition secblock.h:1259
Interface for retrieving values given their names.
Definition cryptlib.h:327
bool GetValue(const char *name, T &value) const
Get a named value.
Definition cryptlib.h:384
Poly1305 message authentication code base class.
Definition poly1305.h:44
void Update(const byte *input, size_t length)
Updates a hash with additional input.
Definition poly1305.cpp:219
void TruncatedFinal(byte *mac, size_t size)
Computes the hash of the current message.
Definition poly1305.cpp:259
void GetNextIV(RandomNumberGenerator &rng, byte *iv)
Retrieves a secure IV for the next message.
Definition poly1305.cpp:301
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
void Restart()
Restart the hash.
Definition poly1305.cpp:307
void Resynchronize(const byte *iv, int ivLength=-1)
Resynchronize with an IV.
Definition poly1305.cpp:283
std::string AlgorithmProvider() const
Retrieve the provider of this algorithm.
Definition poly1305.cpp:184
Poly1305 message authentication code.
Definition poly1305.h:137
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
void TruncatedFinal(byte *mac, size_t size)
Computes the hash of the current message.
Definition poly1305.cpp:374
void Update(const byte *input, size_t length)
Updates a hash with additional input.
Definition poly1305.cpp:335
void Restart()
Restart the hash.
Definition poly1305.cpp:394
Interface for random number generators.
Definition cryptlib.h:1440
virtual void GenerateBlock(byte *output, size_t size)
Generate random array of bytes.
unsigned int word32
32-bit unsigned datatype
Definition config_int.h:72
unsigned long long word64
64-bit unsigned datatype
Definition config_int.h:101
Functions for CPU features and intrinsics.
Abstract base classes that provide a uniform interface to this library.
@ LITTLE_ENDIAN_ORDER
byte order is little-endian
Definition cryptlib.h:150
T1 SaturatingSubtract(const T1 &a, const T2 &b)
Performs a saturating subtract clamped at 0.
Definition misc.h:1302
void memcpy_s(void *dest, size_t sizeInBytes, const void *src, size_t count)
Bounds checking replacement for memcpy()
Definition misc.h:527
Crypto++ library namespace.
const char * IV()
ConstByteArrayParameter, also accepts const byte * for backwards compatibility.
Definition argnames.h:21
Precompiled header file.
Classes for Poly1305 message authentication code.
#define CRYPTOPP_ASSERT(exp)
Debugging and diagnostic assertion.
Definition trap.h:68