File Coverage

chacha.c
Criterion Covered Total %
statement 142 147 96.6
branch 55 68 80.8
condition n/a
subroutine n/a
pod n/a
total 197 215 91.6


line stmt bran cond sub pod time code
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
24             #include
25             #include
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              
59 632           static void init_context(chacha_context_t *ctx, const unsigned char *seed, int init_buffer)
60             {
61 632           uint32_t *x = ctx->state;
62              
63 632           x[ 0] = 0x61707865;
64 632           x[ 1] = 0x3320646e;
65 632           x[ 2] = 0x79622d32;
66 632           x[ 3] = 0x6b206574;
67 632           x[ 4] = U8TO32_LE((seed + 0));
68 632           x[ 5] = U8TO32_LE((seed + 4));
69 632           x[ 6] = U8TO32_LE((seed + 8));
70 632           x[ 7] = U8TO32_LE((seed + 12));
71 632           x[ 8] = U8TO32_LE((seed + 16));
72 632           x[ 9] = U8TO32_LE((seed + 20));
73 632           x[10] = U8TO32_LE((seed + 24));
74 632           x[11] = U8TO32_LE((seed + 28));
75 632           x[12] = 0;
76 632           x[13] = 0;
77 632           x[14] = U8TO32_LE((seed + 32));
78 632           x[15] = U8TO32_LE((seed + 36));
79              
80 632 50         if (init_buffer) {
81 632           memset(ctx->buf, 0, BUFSZ);
82 632           ctx->have = 0;
83             }
84 632           }
85              
86 5392232           static INLINE uint32_t rotl32(uint32_t x, const unsigned int n) {
87 5392232           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 */
96 16849           static void chacha_core(unsigned char* buf, const chacha_context_t *ctx) {
97             uint32_t i, x[16];
98 16849           const uint32_t *s = ctx->state;
99              
100 16849           memcpy(x, s, 16*sizeof(uint32_t));
101              
102 185339 100         for (i = 0; i < CHACHA_ROUNDS; i += 2) {
103 168490           QUARTERROUND( x[ 0], x[ 4], x[ 8], x[12] );
104 168490           QUARTERROUND( x[ 1], x[ 5], x[ 9], x[13] );
105 168490           QUARTERROUND( x[ 2], x[ 6], x[10], x[14] );
106 168490           QUARTERROUND( x[ 3], x[ 7], x[11], x[15] );
107 168490           QUARTERROUND( x[ 0], x[ 5], x[10], x[15] );
108 168490           QUARTERROUND( x[ 1], x[ 6], x[11], x[12] );
109 168490           QUARTERROUND( x[ 2], x[ 7], x[ 8], x[13] );
110 168490           QUARTERROUND( x[ 3], x[ 4], x[ 9], x[14] );
111             }
112              
113 286433 100         for (i = 0; i < 16; i++)
114 269584           x[i] += s[i];
115              
116             #if __LITTLE_ENDIAN__ || (defined(BYTEORDER) && (BYTEORDER == 0x1234 || BYTEORDER == 0x12345678))
117 16849           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 16849           }
123              
124 16435           static INLINE void increment_chacha_counter(chacha_context_t *ctx) {
125             /* Arguably we should continue this into their nonce */
126 16435 50         if (++ctx->state[12] == 0)
127 0           ctx->state[13]++;
128 16435           }
129              
130 1135           static uint32_t chacha_keystream(unsigned char* buf, uint32_t n, chacha_context_t *ctx) {
131 1135           uint32_t r = n;
132 17501 100         while (r >= CORESZ) {
133 16366           chacha_core(buf, ctx);
134 16366           increment_chacha_counter(ctx);
135 16366           buf += CORESZ;
136 16366           r -= CORESZ;
137             }
138 1135 100         if (r > 0) {
139             unsigned char sbuf[CORESZ];
140 69           chacha_core(sbuf, ctx);
141 69           increment_chacha_counter(ctx);
142 69           memcpy(buf, sbuf, r);
143             }
144 1135           return n;
145             }
146              
147             /* The method for refilling our buffer.
148             * This includes reseeding policy.
149             */
150 997           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 997           ctx->have = chacha_keystream(ctx->buf, BUFSZ, ctx);
158             #endif
159 997           return ctx->have;
160             }
161              
162              
163             /*****************************************************************************/
164             /* Test vectors */
165             /*****************************************************************************/
166             #if RUN_INTERNAL_TESTS
167 69           static int _test_qr(void) {
168             uint32_t i;
169 69           uint32_t tv1i[4] = {0x11111111, 0x01020304, 0x9b8d6f43, 0x01234567};
170 69           uint32_t tv1o[4] = {0xea2a92f4, 0xcb1cf8ce, 0x4581472e, 0x5881c4bb};
171 69           uint32_t tv2i[4] = {0x516461b1, 0x2a5f714c, 0x53372767, 0x3d631689};
172 69           uint32_t tv2o[4] = {0xbdb886dc, 0xcfacafd2, 0xe46bea80, 0xccc07c79};
173             if (CHACHA_ROUNDS != 20) return 0;
174 69           QUARTERROUND(tv1i[0],tv1i[1],tv1i[2],tv1i[3]);
175 69           QUARTERROUND(tv2i[0],tv2i[1],tv2i[2],tv2i[3]);
176 345 100         for (i = 0; i < 4; i++) {
177 276 50         if (tv1i[i] != tv1o[i]) croak("QR test 2.1.1 fail %u\n",i);
178 276 50         if (tv2i[i] != tv2o[i]) croak("QR test 2.2.1 fail %u\n",i);
179             }
180 69           return 1;
181             }
182 69           static int _test_core(void) {
183             uint32_t test, i;
184 69           unsigned char keys[6][40] = { {0},{0},{0},{0},{0} };
185 69           char ebuf[6][129] = {
186             "76b8e0ada0f13d90405d6ae55386bd28bdd219b8a08ded1aa836efcc8b770dc7da41597c5157488d7724e03fb8d84a376a43b8f41518a11cc387b669b2ee6586",
187             "4540f05a9f1fb296d7736e7b208e3c96eb4fe1834688d2604f450952ed432d41bbe2a0b6ea7566d2a5d1e7e20d42af2c53d792b1c43fea817e9ad275ae546963",
188             "de9cba7bf3d69ef5e786dc63973f653a0b49e015adbff7134fcb7df137821031e85a050278a7084527214f73efc7fa5b5277062eb7a0433e445f41e31afab757",
189             "ef3fdfd6c61578fbf5cf35bd3dd33b8009631634d21e42ac33960bd138e50d32111e4caf237ee53ca8ad6426194a88545ddc497a0b466e7d6bbdb0041b2f586b",
190             "f798a189f195e66982105ffb640bb7757f579da31602fc93ec01ac56f85ac3c134a4547b733b46413042c9440049176905d3be59ea1c53f15916155c2be8241a",
191             "10f1e7e4d13b5915500fdd1fa32071c4c7d1f4c733c068030422aa9ac3d46c4ed2826446079faa0914c2d705d98b02a2b5129cd1de164eb9cbd083e8a2503c4e",
192             };
193 69           keys[1][31] = 1;
194 69           keys[2][39] = 1;
195 69           keys[3][32] = 1;
196 2277 100         for (i = 0; i < 32; i++) keys[4][ 0+i] = i;
197 621 100         for (i = 0; i < 8; i++) keys[4][32+i] = i;
198 2277 100         for (i = 0; i < 32; i++) keys[5][ 0+i] = i;
199 69           keys[5][35] = 0x4a;
200              
201             if (CHACHA_ROUNDS != 20) return 0;
202 483 100         for (test = 0; test < 6; test++) {
203 414           unsigned char* key = keys[test];
204 414           char* expout = ebuf[test];
205             char got[129];
206             chacha_context_t ctx;
207 414           init_context(&ctx, key, 1);
208 414 100         if (test == 5) { ctx.state[12]=1; ctx.state[13]=0x09000000; }
209 414           chacha_core(ctx.buf, &ctx);
210 414 100         if (test == 0) {
211 828 100         for (i = 5; i < 16; i++)
212 759 50         if (ctx.state[i] != 0)
213 0           croak("core modified state");
214             }
215 26910 100         for (i = 0; i < 64; i++)
216 26496           sprintf(got+2*i,"%02x", ctx.buf[i]);
217 414           got[128] = '\0';
218 414 50         if (memcmp(got, expout, 128))
219 0           croak("fail core test vector %u:\n exp %s\n got %s\n",test,expout,got);
220             }
221 69           return 1;
222             }
223 69           static int _test_keystream(void) {
224             uint32_t test, i;
225 69           unsigned char keys[2][40] = { {0},{0} };
226 69           char ebuf[2][1024+1] = {
227             "f798a189f195e66982105ffb640bb7757f579da31602fc93ec01ac56f85ac3c134a4547b733b46413042c9440049176905d3be59ea1c53f15916155c2be8241a38008b9a26bc35941e2444177c8ade6689de95264986d95889fb60e84629c9bd9a5acb1cc118be563eb9b3a4a472f82e09a7e778492b562ef7130e88dfe031c79db9d4f7c7a899151b9a475032b63fc385245fe054e3dd5a97a5f576fe064025d3ce042c566ab2c507b138db853e3d6959660996546cc9c4a6eafdc777c040d70eaf46f76dad3979e5c5360c3317166a1c894c94a371876a94df7628fe4eaaf2ccb27d5aaae0ad7ad0f9d4b6ad3b54098746d4524d38407a6deb3ab78fab78c9",
228             "af051e40bba0354981329a806a140eafd258a22a6dcb4bb9f6569cb3efe2deaf837bd87ca20b5ba12081a306af0eb35c41a239d20dfc74c81771560d9c9c1e4b224f51f3401bd9e12fde276fb8631ded8c131f823d2c06e27e4fcaec9ef3cf788a3b0aa372600a92b57974cded2b9334794cba40c63e34cdea212c4cf07d41b769a6749f3f630f4122cafe28ec4dc47e26d4346d70b98c73f3e9c53ac40c5945398b6eda1a832c89c167eacd901d7e2bf363",
229             };
230 2277 100         for (i = 0; i < 32; i++) keys[0][ 0+i] = i;
231 621 100         for (i = 0; i < 8; i++) keys[0][32+i] = i;
232 2277 100         for (i = 0; i < 32; i++) keys[1][ 0+i] = i;
233 69           keys[1][35] = 0x4a;
234              
235             if (CHACHA_ROUNDS != 20) return 0;
236              
237 207 100         for (test = 0; test < 2; test++) {
238 138           unsigned char* key = keys[test];
239 138           char* expout = ebuf[test];
240             unsigned char kbuf[512];
241             char got[1024+1];
242 138           uint32_t gen, len = strlen(expout) / 2;
243             chacha_context_t ctx;
244              
245 138 50         if (len > 512) croak("Test vector too large");
246 138           init_context(&ctx, key, 1);
247 138           gen = chacha_keystream(kbuf, len, &ctx);
248 138 50         if (gen < len) croak("short keystream");
249             /* Check state block counter */
250 30084 100         for (i = 0; i < len; i++)
251 29946           sprintf(got+2*i,"%02x", kbuf[i]);
252 138           got[2*len] = '\0';
253 138 50         if (memcmp(got, expout, 2*len))
254 0           croak("fail keystream test vector %u:\n exp %s\n got %s\n",test,expout,got);
255             }
256 69           return 1;
257             }
258              
259 69           int chacha_selftest(void) {
260 69 50         if (_test_qr() && _test_core() && _test_keystream())
    50          
    50          
261 69           return 1;
262 0           return 0;
263             }
264             #else
265             int chacha_selftest(void) { return 1; }
266             #endif
267              
268             /*****************************************************************************/
269             /* API */
270             /*****************************************************************************/
271              
272 80           void chacha_seed(chacha_context_t *cs, uint32_t bytes, const unsigned char* data, char good)
273             {
274 80 50         if (bytes < 40) croak("Not enough seed bytes given to ChaCha\n");
275 80           init_context(cs, data, 1);
276 80           cs->goodseed = good;
277 80           }
278 45           void chacha_rand_bytes(chacha_context_t *cs, uint32_t bytes, unsigned char* data)
279             {
280 91 100         while (bytes > 0) {
281             uint32_t copybytes;
282 46 100         if (cs->have == 0)
283 11           _refill_buffer(cs);
284 46           copybytes = (bytes > cs->have) ? cs->have : bytes;
285 46           memcpy(data, cs->buf + BUFSZ - cs->have, copybytes);
286 46           data += copybytes;
287 46           cs->have -= copybytes;
288 46           bytes -= copybytes;
289             }
290 45           }
291 251562           uint32_t chacha_irand32(chacha_context_t *cs)
292             {
293             uint32_t a;
294             unsigned char* ptr;
295 251562 100         if (cs->have < 4)
296 986           _refill_buffer(cs);
297 251562           ptr = cs->buf + BUFSZ - cs->have;
298 251562           cs->have -= 4;
299 251562           a = U8TO32_LE(ptr);
300 251562           return a;
301             }
302             #if BITS_PER_WORD == 64
303 8656           UV chacha_irand64(chacha_context_t *cs)
304             {
305 8656           uint32_t a = chacha_irand32(cs);
306 8656           uint32_t b = chacha_irand32(cs);
307 8656           return (((UV)a) << 32) | b;
308             }
309             #else
310             UV chacha_irand64(chacha_context_t *cs) { return chacha_irand32(cs); }
311             #endif