Botan  2.8.0
Crypto and TLS for C++11
poly1305.cpp
Go to the documentation of this file.
1 /*
2 * Derived from poly1305-donna-64.h by Andrew Moon <liquidsun@gmail.com>
3 * in https://github.com/floodyberry/poly1305-donna
4 *
5 * (C) 2014 Andrew Moon
6 * (C) 2014 Jack Lloyd
7 *
8 * Botan is released under the Simplified BSD License (see license.txt)
9 */
10 
11 #include <botan/poly1305.h>
12 #include <botan/loadstor.h>
13 #include <botan/mul128.h>
14 #include <botan/internal/donna128.h>
15 
16 namespace Botan {
17 
18 namespace {
19 
20 void poly1305_init(secure_vector<uint64_t>& X, const uint8_t key[32])
21  {
22  /* r &= 0xffffffc0ffffffc0ffffffc0fffffff */
23  const uint64_t t0 = load_le<uint64_t>(key, 0);
24  const uint64_t t1 = load_le<uint64_t>(key, 1);
25 
26  X[0] = ( t0 ) & 0xffc0fffffff;
27  X[1] = ((t0 >> 44) | (t1 << 20)) & 0xfffffc0ffff;
28  X[2] = ((t1 >> 24) ) & 0x00ffffffc0f;
29 
30  /* h = 0 */
31  X[3] = 0;
32  X[4] = 0;
33  X[5] = 0;
34 
35  /* save pad for later */
36  X[6] = load_le<uint64_t>(key, 2);
37  X[7] = load_le<uint64_t>(key, 3);
38  }
39 
40 void poly1305_blocks(secure_vector<uint64_t>& X, const uint8_t *m, size_t blocks, bool is_final = false)
41  {
42 #if !defined(BOTAN_TARGET_HAS_NATIVE_UINT128)
43  typedef donna128 uint128_t;
44 #endif
45 
46  const uint64_t hibit = is_final ? 0 : (static_cast<uint64_t>(1) << 40); /* 1 << 128 */
47 
48  const uint64_t r0 = X[0];
49  const uint64_t r1 = X[1];
50  const uint64_t r2 = X[2];
51 
52  const uint64_t M44 = 0xfffffffffff;
53  const uint64_t M42 = 0x3ffffffffff;
54 
55  uint64_t h0 = X[3+0];
56  uint64_t h1 = X[3+1];
57  uint64_t h2 = X[3+2];
58 
59  const uint64_t s1 = r1 * (5 << 2);
60  const uint64_t s2 = r2 * (5 << 2);
61 
62  for(size_t i = 0; i != blocks; ++i)
63  {
64  const uint64_t t0 = load_le<uint64_t>(m, 0);
65  const uint64_t t1 = load_le<uint64_t>(m, 1);
66 
67  h0 += (( t0 ) & M44);
68  h1 += (((t0 >> 44) | (t1 << 20)) & M44);
69  h2 += (((t1 >> 24) ) & M42) | hibit;
70 
71  const uint128_t d0 = uint128_t(h0) * r0 + uint128_t(h1) * s2 + uint128_t(h2) * s1;
72  const uint64_t c0 = carry_shift(d0, 44);
73 
74  const uint128_t d1 = uint128_t(h0) * r1 + uint128_t(h1) * r0 + uint128_t(h2) * s2 + c0;
75  const uint64_t c1 = carry_shift(d1, 44);
76 
77  const uint128_t d2 = uint128_t(h0) * r2 + uint128_t(h1) * r1 + uint128_t(h2) * r0 + c1;
78  const uint64_t c2 = carry_shift(d2, 42);
79 
80  h0 = d0 & M44;
81  h1 = d1 & M44;
82  h2 = d2 & M42;
83 
84  h0 += c2 * 5;
85  h1 += carry_shift(h0, 44);
86  h0 = h0 & M44;
87 
88  m += 16;
89  }
90 
91  X[3+0] = h0;
92  X[3+1] = h1;
93  X[3+2] = h2;
94  }
95 
96 void poly1305_finish(secure_vector<uint64_t>& X, uint8_t mac[16])
97  {
98  /* fully carry h */
99  uint64_t h0 = X[3+0];
100  uint64_t h1 = X[3+1];
101  uint64_t h2 = X[3+2];
102 
103  uint64_t c;
104  c = (h1 >> 44); h1 &= 0xfffffffffff;
105  h2 += c; c = (h2 >> 42); h2 &= 0x3ffffffffff;
106  h0 += c * 5; c = (h0 >> 44); h0 &= 0xfffffffffff;
107  h1 += c; c = (h1 >> 44); h1 &= 0xfffffffffff;
108  h2 += c; c = (h2 >> 42); h2 &= 0x3ffffffffff;
109  h0 += c * 5; c = (h0 >> 44); h0 &= 0xfffffffffff;
110  h1 += c;
111 
112  /* compute h + -p */
113  uint64_t g0 = h0 + 5; c = (g0 >> 44); g0 &= 0xfffffffffff;
114  uint64_t g1 = h1 + c; c = (g1 >> 44); g1 &= 0xfffffffffff;
115  uint64_t g2 = h2 + c - (static_cast<uint64_t>(1) << 42);
116 
117  /* select h if h < p, or h + -p if h >= p */
118  c = (g2 >> ((sizeof(uint64_t) * 8) - 1)) - 1;
119  g0 &= c;
120  g1 &= c;
121  g2 &= c;
122  c = ~c;
123  h0 = (h0 & c) | g0;
124  h1 = (h1 & c) | g1;
125  h2 = (h2 & c) | g2;
126 
127  /* h = (h + pad) */
128  const uint64_t t0 = X[6];
129  const uint64_t t1 = X[7];
130 
131  h0 += (( t0 ) & 0xfffffffffff) ; c = (h0 >> 44); h0 &= 0xfffffffffff;
132  h1 += (((t0 >> 44) | (t1 << 20)) & 0xfffffffffff) + c; c = (h1 >> 44); h1 &= 0xfffffffffff;
133  h2 += (((t1 >> 24) ) & 0x3ffffffffff) + c; h2 &= 0x3ffffffffff;
134 
135  /* mac = h % (2^128) */
136  h0 = ((h0 ) | (h1 << 44));
137  h1 = ((h1 >> 20) | (h2 << 24));
138 
139  store_le(mac, h0, h1);
140 
141  /* zero out the state */
142  clear_mem(X.data(), X.size());
143  }
144 
145 }
146 
148  {
149  zap(m_poly);
150  zap(m_buf);
151  m_buf_pos = 0;
152  }
153 
154 void Poly1305::key_schedule(const uint8_t key[], size_t)
155  {
156  m_buf_pos = 0;
157  m_buf.resize(16);
158  m_poly.resize(8);
159 
160  poly1305_init(m_poly, key);
161  }
162 
163 void Poly1305::add_data(const uint8_t input[], size_t length)
164  {
165  verify_key_set(m_poly.size() == 8);
166 
167  if(m_buf_pos)
168  {
169  buffer_insert(m_buf, m_buf_pos, input, length);
170 
171  if(m_buf_pos + length >= m_buf.size())
172  {
173  poly1305_blocks(m_poly, m_buf.data(), 1);
174  input += (m_buf.size() - m_buf_pos);
175  length -= (m_buf.size() - m_buf_pos);
176  m_buf_pos = 0;
177  }
178  }
179 
180  const size_t full_blocks = length / m_buf.size();
181  const size_t remaining = length % m_buf.size();
182 
183  if(full_blocks)
184  poly1305_blocks(m_poly, input, full_blocks);
185 
186  buffer_insert(m_buf, m_buf_pos, input + full_blocks * m_buf.size(), remaining);
187  m_buf_pos += remaining;
188  }
189 
190 void Poly1305::final_result(uint8_t out[])
191  {
192  verify_key_set(m_poly.size() == 8);
193 
194  if(m_buf_pos != 0)
195  {
196  m_buf[m_buf_pos] = 1;
197  const size_t len = m_buf.size() - m_buf_pos - 1;
198  if (len > 0)
199  {
200  clear_mem(&m_buf[m_buf_pos+1], len);
201  }
202  poly1305_blocks(m_poly, m_buf.data(), 1, true);
203  }
204 
205  poly1305_finish(m_poly, out);
206 
207  m_poly.clear();
208  m_buf_pos = 0;
209  }
210 
211 }
fe X
Definition: ge.cpp:27
void verify_key_set(bool cond) const
Definition: sym_algo.h:89
void zap(std::vector< T, Alloc > &vec)
Definition: secmem.h:193
void clear_mem(T *ptr, size_t n)
Definition: mem_ops.h:97
uint64_t carry_shift(const donna128 &a, size_t shift)
Definition: donna128.h:116
uint64_t load_le< uint64_t >(const uint8_t in[], size_t off)
Definition: loadstor.h:235
Definition: alg_id.cpp:13
void clear() override
Definition: poly1305.cpp:147
size_t buffer_insert(std::vector< T, Alloc > &buf, size_t buf_offset, const T input[], size_t input_length)
Definition: secmem.h:103
void store_le(uint16_t in, uint8_t out[2])
Definition: loadstor.h:450