File: chacha.c

package info (click to toggle)
libmath-prime-util-perl 0.73-1
  • links: PTS, VCS
  • area: main
  • in suites: bullseye, buster, sid
  • size: 2,800 kB
  • sloc: perl: 24,676; ansic: 11,471; python: 24; makefile: 18
file content (311 lines) | stat: -rw-r--r-- 10,509 bytes parent folder | download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
/*
 * The ChaCha(20) CSPRNG interface.
 * New simple core, 10 Apr 2017, Dana Jacobsen
 */

/* Some benchmarks, repeatedly calling random_bytes(32768).  Time is
 * shown as nanoseconds per 32-bit word.
 *
 * 3700    ns/word  ChaCha20 in Perl
 *  760    ns/word  ISAAC in Perl
 *
 *   16.89 ns/word  ChaCha20 (simple from insane coding)
 *   11.20 ns/word  ChaCha20 (openbsd)
 *   10.31 ns/word  ChaCha20 (dj)
 *    3.26 ns/word  ISAAC
 *    2.23 ns/word  ChaCha20 (AVX2 Neves)
 *    1.95 ns/word  PCG64
 *    1.84 ns/word  ChaCha20 (AVX2 chacha-opt)
 *    1.48 ns/word  Xoroshiro128+
 *    1.16 ns/word  SplitMix64
 */

#include <stdio.h>
#include <stddef.h>
#include <string.h>
#include "ptypes.h"
#include "chacha.h"

#define CHACHA_ROUNDS 20
#define RUN_INTERNAL_TESTS 1
#define RESEED_ON_REFILL 0

/*****************************************************************************/
/* Chacha routines: init, quarter round, core, keystream                     */
/*****************************************************************************/

/* On UltraSparc, Perl's versions of these macros will crash. */
#if !defined(__x86_64__)
#undef U8TO32_LE
#undef U32TO8_LE
#endif

#ifndef U8TO32_LE
#define U8TO32_LE(p) \
  (((uint32_t)((p)[0])      ) | \
   ((uint32_t)((p)[1]) <<  8) | \
   ((uint32_t)((p)[2]) << 16) | \
   ((uint32_t)((p)[3]) << 24))
#endif
#ifndef U32TO8_LE
#define U32TO8_LE(p, v) \
  do { uint32_t _v = v; \
       (p)[0] = (((_v)      ) & 0xFFU); \
       (p)[1] = (((_v) >>  8) & 0xFFU); \
       (p)[2] = (((_v) >> 16) & 0xFFU); \
       (p)[3] = (((_v) >> 24) & 0xFFU); } while (0)
#endif

static void init_context(chacha_context_t *ctx, const unsigned char *seed, int init_buffer)
{
  uint32_t *x = ctx->state;

  x[ 0] = 0x61707865;
  x[ 1] = 0x3320646e;
  x[ 2] = 0x79622d32;
  x[ 3] = 0x6b206574;
  x[ 4] = U8TO32_LE((seed +  0));
  x[ 5] = U8TO32_LE((seed +  4));
  x[ 6] = U8TO32_LE((seed +  8));
  x[ 7] = U8TO32_LE((seed + 12));
  x[ 8] = U8TO32_LE((seed + 16));
  x[ 9] = U8TO32_LE((seed + 20));
  x[10] = U8TO32_LE((seed + 24));
  x[11] = U8TO32_LE((seed + 28));
  x[12] = 0;
  x[13] = 0;
  x[14] = U8TO32_LE((seed + 32));
  x[15] = U8TO32_LE((seed + 36));

  if (init_buffer) {
    memset(ctx->buf, 0, BUFSZ);
    ctx->have = 0;
  }
}

static INLINE uint32_t rotl32(uint32_t x, const unsigned int n) {
  return (x << n) | (x >> (-n & 31));
}
#define QUARTERROUND(a,b,c,d) \
  a += b;  d = rotl32(d ^ a, 16); \
  c += d;  b = rotl32(b ^ c, 12); \
  a += b;  d = rotl32(d ^ a,  8); \
  c += d;  b = rotl32(b ^ c,  7); \

/* Produces buffer from state, does not change state */
static void chacha_core(unsigned char* buf, const chacha_context_t *ctx) {
  uint32_t i, x[16];
  const uint32_t *s = ctx->state;

  memcpy(x, s, 16*sizeof(uint32_t));

  for (i = 0; i < CHACHA_ROUNDS; i += 2) {
    QUARTERROUND( x[ 0], x[ 4], x[ 8], x[12] );
    QUARTERROUND( x[ 1], x[ 5], x[ 9], x[13] );
    QUARTERROUND( x[ 2], x[ 6], x[10], x[14] );
    QUARTERROUND( x[ 3], x[ 7], x[11], x[15] );
    QUARTERROUND( x[ 0], x[ 5], x[10], x[15] );
    QUARTERROUND( x[ 1], x[ 6], x[11], x[12] );
    QUARTERROUND( x[ 2], x[ 7], x[ 8], x[13] );
    QUARTERROUND( x[ 3], x[ 4], x[ 9], x[14] );
  }

  for (i = 0; i < 16; i++)
    x[i] += s[i];

#if __LITTLE_ENDIAN__ || (defined(BYTEORDER) && (BYTEORDER == 0x1234 || BYTEORDER == 0x12345678))
  memcpy(buf, x, 16*sizeof(uint32_t));
#else
  for (i = 0; i < 16; i++)
    U32TO8_LE( buf+4*i, x[i] );
#endif
}

static INLINE void increment_chacha_counter(chacha_context_t *ctx) {
  /* Arguably we should continue this into their nonce */
  if (++ctx->state[12] == 0)
    ctx->state[13]++;
}

static uint32_t chacha_keystream(unsigned char* buf, uint32_t n, chacha_context_t *ctx) {
  uint32_t r = n;
  while (r >= CORESZ) {
    chacha_core(buf, ctx);
    increment_chacha_counter(ctx);
    buf += CORESZ;
    r -= CORESZ;
  }
  if (r > 0) {
    unsigned char sbuf[CORESZ];
    chacha_core(sbuf, ctx);
    increment_chacha_counter(ctx);
    memcpy(buf, sbuf, r);
  }
  return n;
}

/* The method for refilling our buffer.
 * This includes reseeding policy.
 */
static uint32_t  _refill_buffer(chacha_context_t *ctx) {
#if RESEED_ON_REFILL
  ctx->have = chacha_keystream(ctx->buf, BUFSZ, ctx);
  init_context(ctx, ctx->buf, 0);
  memset(ctx->buf, 0, KEYSZ);
  ctx->have = BUFSZ - KEYSZ;
#else
  ctx->have = chacha_keystream(ctx->buf, BUFSZ, ctx);
#endif
  return ctx->have;
}


/*****************************************************************************/
/*   Test vectors                                                            */
/*****************************************************************************/
#if RUN_INTERNAL_TESTS
static int _test_qr(void) {
  uint32_t i;
  uint32_t tv1i[4] = {0x11111111, 0x01020304, 0x9b8d6f43, 0x01234567};
  uint32_t tv1o[4] = {0xea2a92f4, 0xcb1cf8ce, 0x4581472e, 0x5881c4bb};
  uint32_t tv2i[4] = {0x516461b1, 0x2a5f714c, 0x53372767, 0x3d631689};
  uint32_t tv2o[4] = {0xbdb886dc, 0xcfacafd2, 0xe46bea80, 0xccc07c79};
  if (CHACHA_ROUNDS != 20) return 0;
  QUARTERROUND(tv1i[0],tv1i[1],tv1i[2],tv1i[3]);
  QUARTERROUND(tv2i[0],tv2i[1],tv2i[2],tv2i[3]);
  for (i = 0; i < 4; i++) {
    if (tv1i[i] != tv1o[i]) croak("QR test 2.1.1 fail %u\n",i);
    if (tv2i[i] != tv2o[i]) croak("QR test 2.2.1 fail %u\n",i);
  }
  return 1;
}
static int _test_core(void) {
  uint32_t test, i;
  unsigned char keys[6][40] = { {0},{0},{0},{0},{0} };
  char ebuf[6][129] = {
   "76b8e0ada0f13d90405d6ae55386bd28bdd219b8a08ded1aa836efcc8b770dc7da41597c5157488d7724e03fb8d84a376a43b8f41518a11cc387b669b2ee6586",
   "4540f05a9f1fb296d7736e7b208e3c96eb4fe1834688d2604f450952ed432d41bbe2a0b6ea7566d2a5d1e7e20d42af2c53d792b1c43fea817e9ad275ae546963",
   "de9cba7bf3d69ef5e786dc63973f653a0b49e015adbff7134fcb7df137821031e85a050278a7084527214f73efc7fa5b5277062eb7a0433e445f41e31afab757",
   "ef3fdfd6c61578fbf5cf35bd3dd33b8009631634d21e42ac33960bd138e50d32111e4caf237ee53ca8ad6426194a88545ddc497a0b466e7d6bbdb0041b2f586b",
   "f798a189f195e66982105ffb640bb7757f579da31602fc93ec01ac56f85ac3c134a4547b733b46413042c9440049176905d3be59ea1c53f15916155c2be8241a",
   "10f1e7e4d13b5915500fdd1fa32071c4c7d1f4c733c068030422aa9ac3d46c4ed2826446079faa0914c2d705d98b02a2b5129cd1de164eb9cbd083e8a2503c4e",
  };
  keys[1][31] = 1;
  keys[2][39] = 1;
  keys[3][32] = 1;
  for (i = 0; i < 32; i++) keys[4][ 0+i] = i;
  for (i = 0; i <  8; i++) keys[4][32+i] = i;
  for (i = 0; i < 32; i++) keys[5][ 0+i] = i;
  keys[5][35] = 0x4a;

  if (CHACHA_ROUNDS != 20) return 0;
  for (test = 0; test < 6; test++) {
    unsigned char* key = keys[test];
    char* expout = ebuf[test];
    char got[129];
    chacha_context_t ctx;
    init_context(&ctx, key, 1);
    if (test == 5) { ctx.state[12]=1; ctx.state[13]=0x09000000; }
    chacha_core(ctx.buf, &ctx);
    if (test == 0) {
      for (i = 5; i < 16; i++)
        if (ctx.state[i] != 0)
          croak("core modified state");
    }
    for (i = 0; i < 64; i++)
      sprintf(got+2*i,"%02x", ctx.buf[i]);
    got[128] = '\0';
    if (memcmp(got, expout, 128))
      croak("fail core test vector %u:\n  exp %s\n  got %s\n",test,expout,got);
  }
  return 1;
}
static int _test_keystream(void) {
  uint32_t test, i;
  unsigned char keys[2][40] = { {0},{0} };
  char ebuf[2][1024+1] = {
   "f798a189f195e66982105ffb640bb7757f579da31602fc93ec01ac56f85ac3c134a4547b733b46413042c9440049176905d3be59ea1c53f15916155c2be8241a38008b9a26bc35941e2444177c8ade6689de95264986d95889fb60e84629c9bd9a5acb1cc118be563eb9b3a4a472f82e09a7e778492b562ef7130e88dfe031c79db9d4f7c7a899151b9a475032b63fc385245fe054e3dd5a97a5f576fe064025d3ce042c566ab2c507b138db853e3d6959660996546cc9c4a6eafdc777c040d70eaf46f76dad3979e5c5360c3317166a1c894c94a371876a94df7628fe4eaaf2ccb27d5aaae0ad7ad0f9d4b6ad3b54098746d4524d38407a6deb3ab78fab78c9",
   "af051e40bba0354981329a806a140eafd258a22a6dcb4bb9f6569cb3efe2deaf837bd87ca20b5ba12081a306af0eb35c41a239d20dfc74c81771560d9c9c1e4b224f51f3401bd9e12fde276fb8631ded8c131f823d2c06e27e4fcaec9ef3cf788a3b0aa372600a92b57974cded2b9334794cba40c63e34cdea212c4cf07d41b769a6749f3f630f4122cafe28ec4dc47e26d4346d70b98c73f3e9c53ac40c5945398b6eda1a832c89c167eacd901d7e2bf363",
  };
  for (i = 0; i < 32; i++) keys[0][ 0+i] = i;
  for (i = 0; i <  8; i++) keys[0][32+i] = i;
  for (i = 0; i < 32; i++) keys[1][ 0+i] = i;
  keys[1][35] = 0x4a;

  if (CHACHA_ROUNDS != 20) return 0;

  for (test = 0; test < 2; test++) {
    unsigned char* key = keys[test];
    char* expout = ebuf[test];
    unsigned char kbuf[512];
    char got[1024+1];
    uint32_t gen, len = strlen(expout) / 2;
    chacha_context_t ctx;

    if (len > 512) croak("Test vector too large");
    init_context(&ctx, key, 1);
    gen = chacha_keystream(kbuf, len, &ctx);
    if (gen < len) croak("short keystream");
    /* Check state block counter */
    for (i = 0; i < len; i++)
      sprintf(got+2*i,"%02x", kbuf[i]);
    got[2*len] = '\0';
    if (memcmp(got, expout, 2*len))
      croak("fail keystream test vector %u:\n  exp %s\n  got %s\n",test,expout,got);
  }
  return 1;
}

int chacha_selftest(void) {
  if (_test_qr() && _test_core() && _test_keystream())
    return 1;
  return 0;
}
#else
int chacha_selftest(void) { return 1; }
#endif

/*****************************************************************************/
/*   API                                                                     */
/*****************************************************************************/

void chacha_seed(chacha_context_t *cs, uint32_t bytes, const unsigned char* data, char good)
{
  if (bytes < 40) croak("Not enough seed bytes given to ChaCha\n");
  init_context(cs, data, 1);
  cs->goodseed = good;
}
void chacha_rand_bytes(chacha_context_t *cs, uint32_t bytes, unsigned char* data)
{
  while (bytes > 0) {
    uint32_t copybytes;
    if (cs->have == 0)
      _refill_buffer(cs);
    copybytes = (bytes > cs->have)  ?  cs->have  :  bytes;
    memcpy(data, cs->buf + BUFSZ - cs->have, copybytes);
    data += copybytes;
    cs->have -= copybytes;
    bytes -= copybytes;
  }
}
uint32_t chacha_irand32(chacha_context_t *cs)
{
  uint32_t a;
  unsigned char* ptr;
  if (cs->have < 4)
    _refill_buffer(cs);
  ptr = cs->buf + BUFSZ - cs->have;
  cs->have -= 4;
  a = U8TO32_LE(ptr);
  return a;
}
#if BITS_PER_WORD == 64
UV chacha_irand64(chacha_context_t *cs)
{
  uint32_t a = chacha_irand32(cs);
  uint32_t b = chacha_irand32(cs);
  return (((UV)a) << 32) | b;
}
#else
UV chacha_irand64(chacha_context_t *cs) { return chacha_irand32(cs); }
#endif