Coverage Report

Created: 2020-02-14 15:38

/src/botan/src/lib/mac/poly1305/poly1305.cpp
Line
Count
Source (jump to first uncovered line)
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
#include <botan/internal/ct_utils.h>
16
17
namespace Botan {
18
19
namespace {
20
21
void poly1305_init(secure_vector<uint64_t>& X, const uint8_t key[32])
22
180
   {
23
180
   /* r &= 0xffffffc0ffffffc0ffffffc0fffffff */
24
180
   const uint64_t t0 = load_le<uint64_t>(key, 0);
25
180
   const uint64_t t1 = load_le<uint64_t>(key, 1);
26
180
27
180
   X[0] = ( t0                    ) & 0xffc0fffffff;
28
180
   X[1] = ((t0 >> 44) | (t1 << 20)) & 0xfffffc0ffff;
29
180
   X[2] = ((t1 >> 24)             ) & 0x00ffffffc0f;
30
180
31
180
   /* h = 0 */
32
180
   X[3] = 0;
33
180
   X[4] = 0;
34
180
   X[5] = 0;
35
180
36
180
   /* save pad for later */
37
180
   X[6] = load_le<uint64_t>(key, 2);
38
180
   X[7] = load_le<uint64_t>(key, 3);
39
180
   }
40
41
void poly1305_blocks(secure_vector<uint64_t>& X, const uint8_t *m, size_t blocks, bool is_final = false)
42
573
   {
43
#if !defined(BOTAN_TARGET_HAS_NATIVE_UINT128)
44
   typedef donna128 uint128_t;
45
#endif
46
47
573
   const uint64_t hibit = is_final ? 0 : (static_cast<uint64_t>(1) << 40); /* 1 << 128 */
48
573
49
573
   const uint64_t r0 = X[0];
50
573
   const uint64_t r1 = X[1];
51
573
   const uint64_t r2 = X[2];
52
573
53
573
   const uint64_t M44 = 0xFFFFFFFFFFF;
54
573
   const uint64_t M42 = 0x3FFFFFFFFFF;
55
573
56
573
   uint64_t h0 = X[3+0];
57
573
   uint64_t h1 = X[3+1];
58
573
   uint64_t h2 = X[3+2];
59
573
60
573
   const uint64_t s1 = r1 * 20;
61
573
   const uint64_t s2 = r2 * 20;
62
573
63
4.72k
   for(size_t i = 0; i != blocks; ++i)
64
4.15k
      {
65
4.15k
      const uint64_t t0 = load_le<uint64_t>(m, 0);
66
4.15k
      const uint64_t t1 = load_le<uint64_t>(m, 1);
67
4.15k
68
4.15k
      h0 += (( t0                    ) & M44);
69
4.15k
      h1 += (((t0 >> 44) | (t1 << 20)) & M44);
70
4.15k
      h2 += (((t1 >> 24)             ) & M42) | hibit;
71
4.15k
72
4.15k
      const uint128_t d0 = uint128_t(h0) * r0 + uint128_t(h1) * s2 + uint128_t(h2) * s1;
73
4.15k
      const uint64_t c0 = carry_shift(d0, 44);
74
4.15k
75
4.15k
      const uint128_t d1 = uint128_t(h0) * r1 + uint128_t(h1) * r0 + uint128_t(h2) * s2 + c0;
76
4.15k
      const uint64_t c1 = carry_shift(d1, 44);
77
4.15k
78
4.15k
      const uint128_t d2 = uint128_t(h0) * r2 + uint128_t(h1) * r1 + uint128_t(h2) * r0 + c1;
79
4.15k
      const uint64_t c2 = carry_shift(d2, 42);
80
4.15k
81
4.15k
      h0 = d0 & M44;
82
4.15k
      h1 = d1 & M44;
83
4.15k
      h2 = d2 & M42;
84
4.15k
85
4.15k
      h0 += c2 * 5;
86
4.15k
      h1 += carry_shift(h0, 44);
87
4.15k
      h0 = h0 & M44;
88
4.15k
89
4.15k
      m += 16;
90
4.15k
      }
91
573
92
573
   X[3+0] = h0;
93
573
   X[3+1] = h1;
94
573
   X[3+2] = h2;
95
573
   }
96
97
void poly1305_finish(secure_vector<uint64_t>& X, uint8_t mac[16])
98
180
   {
99
180
   const uint64_t M44 = 0xFFFFFFFFFFF;
100
180
   const uint64_t M42 = 0x3FFFFFFFFFF;
101
180
102
180
   /* fully carry h */
103
180
   uint64_t h0 = X[3+0];
104
180
   uint64_t h1 = X[3+1];
105
180
   uint64_t h2 = X[3+2];
106
180
107
180
   uint64_t c;
108
180
                c = (h1 >> 44); h1 &= M44;
109
180
   h2 += c;     c = (h2 >> 42); h2 &= M42;
110
180
   h0 += c * 5; c = (h0 >> 44); h0 &= M44;
111
180
   h1 += c;     c = (h1 >> 44); h1 &= M44;
112
180
   h2 += c;     c = (h2 >> 42); h2 &= M42;
113
180
   h0 += c * 5; c = (h0 >> 44); h0 &= M44;
114
180
   h1 += c;
115
180
116
180
   /* compute h + -p */
117
180
   uint64_t g0 = h0 + 5; c = (g0 >> 44); g0 &= M44;
118
180
   uint64_t g1 = h1 + c; c = (g1 >> 44); g1 &= M44;
119
180
   uint64_t g2 = h2 + c - (static_cast<uint64_t>(1) << 42);
120
180
121
180
   /* select h if h < p, or h + -p if h >= p */
122
180
   const auto c_mask = CT::Mask<uint64_t>::expand(c);
123
180
   h0 = c_mask.select(g0, h0);
124
180
   h1 = c_mask.select(g1, h1);
125
180
   h2 = c_mask.select(g2, h2);
126
180
127
180
   /* h = (h + pad) */
128
180
   const uint64_t t0 = X[6];
129
180
   const uint64_t t1 = X[7];
130
180
131
180
   h0 += (( t0                    ) & M44)    ; c = (h0 >> 44); h0 &= M44;
132
180
   h1 += (((t0 >> 44) | (t1 << 20)) & M44) + c; c = (h1 >> 44); h1 &= M44;
133
180
   h2 += (((t1 >> 24)             ) & M42) + c;                 h2 &= M42;
134
180
135
180
   /* mac = h % (2^128) */
136
180
   h0 = ((h0      ) | (h1 << 44));
137
180
   h1 = ((h1 >> 20) | (h2 << 24));
138
180
139
180
   store_le(mac, h0, h1);
140
180
141
180
   /* zero out the state */
142
180
   clear_mem(X.data(), X.size());
143
180
   }
144
145
}
146
147
void Poly1305::clear()
148
0
   {
149
0
   zap(m_poly);
150
0
   zap(m_buf);
151
0
   m_buf_pos = 0;
152
0
   }
153
154
void Poly1305::key_schedule(const uint8_t key[], size_t)
155
180
   {
156
180
   m_buf_pos = 0;
157
180
   m_buf.resize(16);
158
180
   m_poly.resize(8);
159
180
160
180
   poly1305_init(m_poly, key);
161
180
   }
162
163
void Poly1305::add_data(const uint8_t input[], size_t length)
164
997
   {
165
997
   verify_key_set(m_poly.size() == 8);
166
997
167
997
   if(m_buf_pos)
168
459
      {
169
459
      buffer_insert(m_buf, m_buf_pos, input, length);
170
459
171
459
      if(m_buf_pos + length >= m_buf.size())
172
459
         {
173
459
         poly1305_blocks(m_poly, m_buf.data(), 1);
174
459
         input += (m_buf.size() - m_buf_pos);
175
459
         length -= (m_buf.size() - m_buf_pos);
176
459
         m_buf_pos = 0;
177
459
         }
178
459
      }
179
997
180
997
   const size_t full_blocks = length / m_buf.size();
181
997
   const size_t remaining   = length % m_buf.size();
182
997
183
997
   if(full_blocks)
184
114
      poly1305_blocks(m_poly, input, full_blocks);
185
997
186
997
   buffer_insert(m_buf, m_buf_pos, input + full_blocks * m_buf.size(), remaining);
187
997
   m_buf_pos += remaining;
188
997
   }
189
190
void Poly1305::final_result(uint8_t out[])
191
180
   {
192
180
   verify_key_set(m_poly.size() == 8);
193
180
194
180
   if(m_buf_pos != 0)
195
0
      {
196
0
      m_buf[m_buf_pos] = 1;
197
0
      const size_t len = m_buf.size() - m_buf_pos - 1;
198
0
      if (len > 0)
199
0
         {
200
0
         clear_mem(&m_buf[m_buf_pos+1], len);
201
0
         }
202
0
      poly1305_blocks(m_poly, m_buf.data(), 1, true);
203
0
      }
204
180
205
180
   poly1305_finish(m_poly, out);
206
180
207
180
   m_poly.clear();
208
180
   m_buf_pos = 0;
209
180
   }
210
211
}