1 /*
2 * The ChaCha(20) CSPRNG interface.
3 * New simple core, 10 Apr 2017, Dana Jacobsen
4 */
5
6 /* Some benchmarks, repeatedly calling random_bytes(32768). Time is
7 * shown as nanoseconds per 32-bit word.
8 *
9 * 3700 ns/word ChaCha20 in Perl
10 * 760 ns/word ISAAC in Perl
11 *
12 * 16.89 ns/word ChaCha20 (simple from insane coding)
13 * 11.20 ns/word ChaCha20 (openbsd)
14 * 10.31 ns/word ChaCha20 (dj)
15 * 3.26 ns/word ISAAC
16 * 2.23 ns/word ChaCha20 (AVX2 Neves)
17 * 1.95 ns/word PCG64
18 * 1.84 ns/word ChaCha20 (AVX2 chacha-opt)
19 * 1.48 ns/word Xoroshiro128+
20 * 1.16 ns/word SplitMix64
21 */
22
23 #include <stdio.h>
24 #include <stddef.h>
25 #include <string.h>
26 #include "ptypes.h"
27 #include "chacha.h"
28
29 #define CHACHA_ROUNDS 20
30 #define RUN_INTERNAL_TESTS 1
31 #define RESEED_ON_REFILL 0
32
33 /*****************************************************************************/
34 /* Chacha routines: init, quarter round, core, keystream */
35 /*****************************************************************************/
36
37 /* On UltraSparc, Perl's versions of these macros will crash. */
38 #if !defined(__x86_64__)
39 #undef U8TO32_LE
40 #undef U32TO8_LE
41 #endif
42
43 #ifndef U8TO32_LE
44 #define U8TO32_LE(p) \
45 (((uint32_t)((p)[0]) ) | \
46 ((uint32_t)((p)[1]) << 8) | \
47 ((uint32_t)((p)[2]) << 16) | \
48 ((uint32_t)((p)[3]) << 24))
49 #endif
50 #ifndef U32TO8_LE
51 #define U32TO8_LE(p, v) \
52 do { uint32_t _v = v; \
53 (p)[0] = (((_v) ) & 0xFFU); \
54 (p)[1] = (((_v) >> 8) & 0xFFU); \
55 (p)[2] = (((_v) >> 16) & 0xFFU); \
56 (p)[3] = (((_v) >> 24) & 0xFFU); } while (0)
57 #endif
58
init_context(chacha_context_t * ctx,const unsigned char * seed,int init_buffer)59 static void init_context(chacha_context_t *ctx, const unsigned char *seed, int init_buffer)
60 {
61 uint32_t *x = ctx->state;
62
63 x[ 0] = 0x61707865;
64 x[ 1] = 0x3320646e;
65 x[ 2] = 0x79622d32;
66 x[ 3] = 0x6b206574;
67 x[ 4] = U8TO32_LE((seed + 0));
68 x[ 5] = U8TO32_LE((seed + 4));
69 x[ 6] = U8TO32_LE((seed + 8));
70 x[ 7] = U8TO32_LE((seed + 12));
71 x[ 8] = U8TO32_LE((seed + 16));
72 x[ 9] = U8TO32_LE((seed + 20));
73 x[10] = U8TO32_LE((seed + 24));
74 x[11] = U8TO32_LE((seed + 28));
75 x[12] = 0;
76 x[13] = 0;
77 x[14] = U8TO32_LE((seed + 32));
78 x[15] = U8TO32_LE((seed + 36));
79
80 if (init_buffer) {
81 memset(ctx->buf, 0, BUFSZ);
82 ctx->have = 0;
83 }
84 }
85
rotl32(uint32_t x,const unsigned int n)86 static INLINE uint32_t rotl32(uint32_t x, const unsigned int n) {
87 return (x << n) | (x >> (-n & 31));
88 }
89 #define QUARTERROUND(a,b,c,d) \
90 a += b; d = rotl32(d ^ a, 16); \
91 c += d; b = rotl32(b ^ c, 12); \
92 a += b; d = rotl32(d ^ a, 8); \
93 c += d; b = rotl32(b ^ c, 7); \
94
95 /* Produces buffer from state, does not change state */
chacha_core(unsigned char * buf,const chacha_context_t * ctx)96 static void chacha_core(unsigned char* buf, const chacha_context_t *ctx) {
97 uint32_t i, x[16];
98 const uint32_t *s = ctx->state;
99
100 memcpy(x, s, 16*sizeof(uint32_t));
101
102 for (i = 0; i < CHACHA_ROUNDS; i += 2) {
103 QUARTERROUND( x[ 0], x[ 4], x[ 8], x[12] );
104 QUARTERROUND( x[ 1], x[ 5], x[ 9], x[13] );
105 QUARTERROUND( x[ 2], x[ 6], x[10], x[14] );
106 QUARTERROUND( x[ 3], x[ 7], x[11], x[15] );
107 QUARTERROUND( x[ 0], x[ 5], x[10], x[15] );
108 QUARTERROUND( x[ 1], x[ 6], x[11], x[12] );
109 QUARTERROUND( x[ 2], x[ 7], x[ 8], x[13] );
110 QUARTERROUND( x[ 3], x[ 4], x[ 9], x[14] );
111 }
112
113 for (i = 0; i < 16; i++)
114 x[i] += s[i];
115
116 #if __LITTLE_ENDIAN__ || (defined(BYTEORDER) && (BYTEORDER == 0x1234 || BYTEORDER == 0x12345678))
117 memcpy(buf, x, 16*sizeof(uint32_t));
118 #else
119 for (i = 0; i < 16; i++)
120 U32TO8_LE( buf+4*i, x[i] );
121 #endif
122 }
123
increment_chacha_counter(chacha_context_t * ctx)124 static INLINE void increment_chacha_counter(chacha_context_t *ctx) {
125 /* Arguably we should continue this into their nonce */
126 if (++ctx->state[12] == 0)
127 ctx->state[13]++;
128 }
129
chacha_keystream(unsigned char * buf,uint32_t n,chacha_context_t * ctx)130 static uint32_t chacha_keystream(unsigned char* buf, uint32_t n, chacha_context_t *ctx) {
131 uint32_t r = n;
132 while (r >= CORESZ) {
133 chacha_core(buf, ctx);
134 increment_chacha_counter(ctx);
135 buf += CORESZ;
136 r -= CORESZ;
137 }
138 if (r > 0) {
139 unsigned char sbuf[CORESZ];
140 chacha_core(sbuf, ctx);
141 increment_chacha_counter(ctx);
142 memcpy(buf, sbuf, r);
143 }
144 return n;
145 }
146
147 /* The method for refilling our buffer.
148 * This includes reseeding policy.
149 */
_refill_buffer(chacha_context_t * ctx)150 static uint32_t _refill_buffer(chacha_context_t *ctx) {
151 #if RESEED_ON_REFILL
152 ctx->have = chacha_keystream(ctx->buf, BUFSZ, ctx);
153 init_context(ctx, ctx->buf, 0);
154 memset(ctx->buf, 0, KEYSZ);
155 ctx->have = BUFSZ - KEYSZ;
156 #else
157 ctx->have = chacha_keystream(ctx->buf, BUFSZ, ctx);
158 #endif
159 return ctx->have;
160 }
161
162
163 /*****************************************************************************/
164 /* Test vectors */
165 /*****************************************************************************/
166 #if RUN_INTERNAL_TESTS
_test_qr(void)167 static int _test_qr(void) {
168 uint32_t i;
169 uint32_t tv1i[4] = {0x11111111, 0x01020304, 0x9b8d6f43, 0x01234567};
170 uint32_t tv1o[4] = {0xea2a92f4, 0xcb1cf8ce, 0x4581472e, 0x5881c4bb};
171 uint32_t tv2i[4] = {0x516461b1, 0x2a5f714c, 0x53372767, 0x3d631689};
172 uint32_t tv2o[4] = {0xbdb886dc, 0xcfacafd2, 0xe46bea80, 0xccc07c79};
173 if (CHACHA_ROUNDS != 20) return 0;
174 QUARTERROUND(tv1i[0],tv1i[1],tv1i[2],tv1i[3]);
175 QUARTERROUND(tv2i[0],tv2i[1],tv2i[2],tv2i[3]);
176 for (i = 0; i < 4; i++) {
177 if (tv1i[i] != tv1o[i]) croak("QR test 2.1.1 fail %u\n",i);
178 if (tv2i[i] != tv2o[i]) croak("QR test 2.2.1 fail %u\n",i);
179 }
180 return 1;
181 }
_test_core(void)182 static int _test_core(void) {
183 uint32_t test, i;
184 unsigned char keys[6][40] = { {0},{0},{0},{0},{0} };
185 char ebuf[6][129] = {
186 "76b8e0ada0f13d90405d6ae55386bd28bdd219b8a08ded1aa836efcc8b770dc7da41597c5157488d7724e03fb8d84a376a43b8f41518a11cc387b669b2ee6586",
187 "4540f05a9f1fb296d7736e7b208e3c96eb4fe1834688d2604f450952ed432d41bbe2a0b6ea7566d2a5d1e7e20d42af2c53d792b1c43fea817e9ad275ae546963",
188 "de9cba7bf3d69ef5e786dc63973f653a0b49e015adbff7134fcb7df137821031e85a050278a7084527214f73efc7fa5b5277062eb7a0433e445f41e31afab757",
189 "ef3fdfd6c61578fbf5cf35bd3dd33b8009631634d21e42ac33960bd138e50d32111e4caf237ee53ca8ad6426194a88545ddc497a0b466e7d6bbdb0041b2f586b",
190 "f798a189f195e66982105ffb640bb7757f579da31602fc93ec01ac56f85ac3c134a4547b733b46413042c9440049176905d3be59ea1c53f15916155c2be8241a",
191 "10f1e7e4d13b5915500fdd1fa32071c4c7d1f4c733c068030422aa9ac3d46c4ed2826446079faa0914c2d705d98b02a2b5129cd1de164eb9cbd083e8a2503c4e",
192 };
193 keys[1][31] = 1;
194 keys[2][39] = 1;
195 keys[3][32] = 1;
196 for (i = 0; i < 32; i++) keys[4][ 0+i] = i;
197 for (i = 0; i < 8; i++) keys[4][32+i] = i;
198 for (i = 0; i < 32; i++) keys[5][ 0+i] = i;
199 keys[5][35] = 0x4a;
200
201 if (CHACHA_ROUNDS != 20) return 0;
202 for (test = 0; test < 6; test++) {
203 unsigned char* key = keys[test];
204 char* expout = ebuf[test];
205 char got[129];
206 chacha_context_t ctx;
207 init_context(&ctx, key, 1);
208 if (test == 5) { ctx.state[12]=1; ctx.state[13]=0x09000000; }
209 chacha_core(ctx.buf, &ctx);
210 if (test == 0) {
211 for (i = 5; i < 16; i++)
212 if (ctx.state[i] != 0)
213 croak("core modified state");
214 }
215 for (i = 0; i < 64; i++)
216 sprintf(got+2*i,"%02x", ctx.buf[i]);
217 got[128] = '\0';
218 if (memcmp(got, expout, 128))
219 croak("fail core test vector %u:\n exp %s\n got %s\n",test,expout,got);
220 }
221 return 1;
222 }
_test_keystream(void)223 static int _test_keystream(void) {
224 uint32_t test, i;
225 unsigned char keys[2][40] = { {0},{0} };
226 char ebuf[2][1024+1] = {
227 "f798a189f195e66982105ffb640bb7757f579da31602fc93ec01ac56f85ac3c134a4547b733b46413042c9440049176905d3be59ea1c53f15916155c2be8241a38008b9a26bc35941e2444177c8ade6689de95264986d95889fb60e84629c9bd9a5acb1cc118be563eb9b3a4a472f82e09a7e778492b562ef7130e88dfe031c79db9d4f7c7a899151b9a475032b63fc385245fe054e3dd5a97a5f576fe064025d3ce042c566ab2c507b138db853e3d6959660996546cc9c4a6eafdc777c040d70eaf46f76dad3979e5c5360c3317166a1c894c94a371876a94df7628fe4eaaf2ccb27d5aaae0ad7ad0f9d4b6ad3b54098746d4524d38407a6deb3ab78fab78c9",
228 "af051e40bba0354981329a806a140eafd258a22a6dcb4bb9f6569cb3efe2deaf837bd87ca20b5ba12081a306af0eb35c41a239d20dfc74c81771560d9c9c1e4b224f51f3401bd9e12fde276fb8631ded8c131f823d2c06e27e4fcaec9ef3cf788a3b0aa372600a92b57974cded2b9334794cba40c63e34cdea212c4cf07d41b769a6749f3f630f4122cafe28ec4dc47e26d4346d70b98c73f3e9c53ac40c5945398b6eda1a832c89c167eacd901d7e2bf363",
229 };
230 for (i = 0; i < 32; i++) keys[0][ 0+i] = i;
231 for (i = 0; i < 8; i++) keys[0][32+i] = i;
232 for (i = 0; i < 32; i++) keys[1][ 0+i] = i;
233 keys[1][35] = 0x4a;
234
235 if (CHACHA_ROUNDS != 20) return 0;
236
237 for (test = 0; test < 2; test++) {
238 unsigned char* key = keys[test];
239 char* expout = ebuf[test];
240 unsigned char kbuf[512];
241 char got[1024+1];
242 uint32_t gen, len = strlen(expout) / 2;
243 chacha_context_t ctx;
244
245 if (len > 512) croak("Test vector too large");
246 init_context(&ctx, key, 1);
247 gen = chacha_keystream(kbuf, len, &ctx);
248 if (gen < len) croak("short keystream");
249 /* Check state block counter */
250 for (i = 0; i < len; i++)
251 sprintf(got+2*i,"%02x", kbuf[i]);
252 got[2*len] = '\0';
253 if (memcmp(got, expout, 2*len))
254 croak("fail keystream test vector %u:\n exp %s\n got %s\n",test,expout,got);
255 }
256 return 1;
257 }
258
chacha_selftest(void)259 int chacha_selftest(void) {
260 if (_test_qr() && _test_core() && _test_keystream())
261 return 1;
262 return 0;
263 }
264 #else
chacha_selftest(void)265 int chacha_selftest(void) { return 1; }
266 #endif
267
268 /*****************************************************************************/
269 /* API */
270 /*****************************************************************************/
271
chacha_seed(chacha_context_t * cs,uint32_t bytes,const unsigned char * data,char good)272 void chacha_seed(chacha_context_t *cs, uint32_t bytes, const unsigned char* data, char good)
273 {
274 if (bytes < 40) croak("Not enough seed bytes given to ChaCha\n");
275 init_context(cs, data, 1);
276 cs->goodseed = good;
277 }
chacha_rand_bytes(chacha_context_t * cs,uint32_t bytes,unsigned char * data)278 void chacha_rand_bytes(chacha_context_t *cs, uint32_t bytes, unsigned char* data)
279 {
280 while (bytes > 0) {
281 uint32_t copybytes;
282 if (cs->have == 0)
283 _refill_buffer(cs);
284 copybytes = (bytes > cs->have) ? cs->have : bytes;
285 memcpy(data, cs->buf + BUFSZ - cs->have, copybytes);
286 data += copybytes;
287 cs->have -= copybytes;
288 bytes -= copybytes;
289 }
290 }
chacha_irand32(chacha_context_t * cs)291 uint32_t chacha_irand32(chacha_context_t *cs)
292 {
293 uint32_t a;
294 unsigned char* ptr;
295 if (cs->have < 4)
296 _refill_buffer(cs);
297 ptr = cs->buf + BUFSZ - cs->have;
298 cs->have -= 4;
299 a = U8TO32_LE(ptr);
300 return a;
301 }
302 #if BITS_PER_WORD == 64
chacha_irand64(chacha_context_t * cs)303 UV chacha_irand64(chacha_context_t *cs)
304 {
305 uint32_t a = chacha_irand32(cs);
306 uint32_t b = chacha_irand32(cs);
307 return (((UV)a) << 32) | b;
308 }
309 #else
chacha_irand64(chacha_context_t * cs)310 UV chacha_irand64(chacha_context_t *cs) { return chacha_irand32(cs); }
311 #endif
312