summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--ChangeLog5
-rw-r--r--openbsd-compat/arc4random.c261
-rw-r--r--openbsd-compat/chacha_private.h222
3 files changed, 488 insertions, 0 deletions
diff --git a/ChangeLog b/ChangeLog
index 0d8152f00..34b6d17f9 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,8 @@
120131009
2 - (djm) [openbsd-compat/arc4random.c openbsd-compat/chacha_private.h] Pull
3 in OpenBSD implementation of arc4random, shortly to replace the existing
4 bsd-arc4random.c
5
120130922 620130922
2 - (dtucker) [platform.c platform.h sshd.c] bz#2156: restore Linux oom_adj 7 - (dtucker) [platform.c platform.h sshd.c] bz#2156: restore Linux oom_adj
3 setting when handling SIGHUP to maintain behaviour over retart. Patch 8 setting when handling SIGHUP to maintain behaviour over retart. Patch
diff --git a/openbsd-compat/arc4random.c b/openbsd-compat/arc4random.c
new file mode 100644
index 000000000..356e23181
--- /dev/null
+++ b/openbsd-compat/arc4random.c
@@ -0,0 +1,261 @@
1/* $OpenBSD: arc4random.c,v 1.25 2013/10/01 18:34:57 markus Exp $ */
2
3/*
4 * Copyright (c) 1996, David Mazieres <dm@uun.org>
5 * Copyright (c) 2008, Damien Miller <djm@openbsd.org>
6 * Copyright (c) 2013, Markus Friedl <markus@openbsd.org>
7 *
8 * Permission to use, copy, modify, and distribute this software for any
9 * purpose with or without fee is hereby granted, provided that the above
10 * copyright notice and this permission notice appear in all copies.
11 *
12 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
13 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
14 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
15 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
16 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
17 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
18 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
19 */
20
21/*
22 * ChaCha based random number generator for OpenBSD.
23 */
24
25#include <fcntl.h>
26#include <limits.h>
27#include <stdlib.h>
28#include <string.h>
29#include <unistd.h>
30#include <sys/types.h>
31#include <sys/param.h>
32#include <sys/time.h>
33#include <sys/sysctl.h>
34#include "thread_private.h"
35
36#define KEYSTREAM_ONLY
37#include "chacha_private.h"
38
39#ifdef __GNUC__
40#define inline __inline
41#else /* !__GNUC__ */
42#define inline
43#endif /* !__GNUC__ */
44
45#define KEYSZ 32
46#define IVSZ 8
47#define BLOCKSZ 64
48#define RSBUFSZ (16*BLOCKSZ)
49static int rs_initialized;
50static pid_t rs_stir_pid;
51static chacha_ctx rs; /* chacha context for random keystream */
52static u_char rs_buf[RSBUFSZ]; /* keystream blocks */
53static size_t rs_have; /* valid bytes at end of rs_buf */
54static size_t rs_count; /* bytes till reseed */
55
56static inline void _rs_rekey(u_char *dat, size_t datlen);
57
58static inline void
59_rs_init(u_char *buf, size_t n)
60{
61 if (n < KEYSZ + IVSZ)
62 return;
63 chacha_keysetup(&rs, buf, KEYSZ * 8, 0);
64 chacha_ivsetup(&rs, buf + KEYSZ);
65}
66
67static void
68_rs_stir(void)
69{
70 int mib[2];
71 size_t len;
72 u_char rnd[KEYSZ + IVSZ];
73
74 mib[0] = CTL_KERN;
75 mib[1] = KERN_ARND;
76
77 len = sizeof(rnd);
78 sysctl(mib, 2, rnd, &len, NULL, 0);
79
80 if (!rs_initialized) {
81 rs_initialized = 1;
82 _rs_init(rnd, sizeof(rnd));
83 } else
84 _rs_rekey(rnd, sizeof(rnd));
85 memset(rnd, 0, sizeof(rnd));
86
87 /* invalidate rs_buf */
88 rs_have = 0;
89 memset(rs_buf, 0, RSBUFSZ);
90
91 rs_count = 1600000;
92}
93
94static inline void
95_rs_stir_if_needed(size_t len)
96{
97 pid_t pid = getpid();
98
99 if (rs_count <= len || !rs_initialized || rs_stir_pid != pid) {
100 rs_stir_pid = pid;
101 _rs_stir();
102 } else
103 rs_count -= len;
104}
105
106static inline void
107_rs_rekey(u_char *dat, size_t datlen)
108{
109#ifndef KEYSTREAM_ONLY
110 memset(rs_buf, 0,RSBUFSZ);
111#endif
112 /* fill rs_buf with the keystream */
113 chacha_encrypt_bytes(&rs, rs_buf, rs_buf, RSBUFSZ);
114 /* mix in optional user provided data */
115 if (dat) {
116 size_t i, m;
117
118 m = MIN(datlen, KEYSZ + IVSZ);
119 for (i = 0; i < m; i++)
120 rs_buf[i] ^= dat[i];
121 }
122 /* immediately reinit for backtracking resistance */
123 _rs_init(rs_buf, KEYSZ + IVSZ);
124 memset(rs_buf, 0, KEYSZ + IVSZ);
125 rs_have = RSBUFSZ - KEYSZ - IVSZ;
126}
127
128static inline void
129_rs_random_buf(void *_buf, size_t n)
130{
131 u_char *buf = (u_char *)_buf;
132 size_t m;
133
134 _rs_stir_if_needed(n);
135 while (n > 0) {
136 if (rs_have > 0) {
137 m = MIN(n, rs_have);
138 memcpy(buf, rs_buf + RSBUFSZ - rs_have, m);
139 memset(rs_buf + RSBUFSZ - rs_have, 0, m);
140 buf += m;
141 n -= m;
142 rs_have -= m;
143 }
144 if (rs_have == 0)
145 _rs_rekey(NULL, 0);
146 }
147}
148
149static inline void
150_rs_random_u32(u_int32_t *val)
151{
152 _rs_stir_if_needed(sizeof(*val));
153 if (rs_have < sizeof(*val))
154 _rs_rekey(NULL, 0);
155 memcpy(val, rs_buf + RSBUFSZ - rs_have, sizeof(*val));
156 memset(rs_buf + RSBUFSZ - rs_have, 0, sizeof(*val));
157 rs_have -= sizeof(*val);
158 return;
159}
160
161void
162arc4random_stir(void)
163{
164 _ARC4_LOCK();
165 _rs_stir();
166 _ARC4_UNLOCK();
167}
168
169void
170arc4random_addrandom(u_char *dat, int datlen)
171{
172 int m;
173
174 _ARC4_LOCK();
175 if (!rs_initialized)
176 _rs_stir();
177 while (datlen > 0) {
178 m = MIN(datlen, KEYSZ + IVSZ);
179 _rs_rekey(dat, m);
180 dat += m;
181 datlen -= m;
182 }
183 _ARC4_UNLOCK();
184}
185
186u_int32_t
187arc4random(void)
188{
189 u_int32_t val;
190
191 _ARC4_LOCK();
192 _rs_random_u32(&val);
193 _ARC4_UNLOCK();
194 return val;
195}
196
197void
198arc4random_buf(void *buf, size_t n)
199{
200 _ARC4_LOCK();
201 _rs_random_buf(buf, n);
202 _ARC4_UNLOCK();
203}
204
205/*
206 * Calculate a uniformly distributed random number less than upper_bound
207 * avoiding "modulo bias".
208 *
209 * Uniformity is achieved by generating new random numbers until the one
210 * returned is outside the range [0, 2**32 % upper_bound). This
211 * guarantees the selected random number will be inside
212 * [2**32 % upper_bound, 2**32) which maps back to [0, upper_bound)
213 * after reduction modulo upper_bound.
214 */
215u_int32_t
216arc4random_uniform(u_int32_t upper_bound)
217{
218 u_int32_t r, min;
219
220 if (upper_bound < 2)
221 return 0;
222
223 /* 2**32 % x == (2**32 - x) % x */
224 min = -upper_bound % upper_bound;
225
226 /*
227 * This could theoretically loop forever but each retry has
228 * p > 0.5 (worst case, usually far better) of selecting a
229 * number inside the range we need, so it should rarely need
230 * to re-roll.
231 */
232 for (;;) {
233 r = arc4random();
234 if (r >= min)
235 break;
236 }
237
238 return r % upper_bound;
239}
240
241#if 0
242/*-------- Test code for i386 --------*/
243#include <stdio.h>
244#include <machine/pctr.h>
245int
246main(int argc, char **argv)
247{
248 const int iter = 1000000;
249 int i;
250 pctrval v;
251
252 v = rdtsc();
253 for (i = 0; i < iter; i++)
254 arc4random();
255 v = rdtsc() - v;
256 v /= iter;
257
258 printf("%qd cycles\n", v);
259 exit(0);
260}
261#endif
diff --git a/openbsd-compat/chacha_private.h b/openbsd-compat/chacha_private.h
new file mode 100644
index 000000000..7c3680fa6
--- /dev/null
+++ b/openbsd-compat/chacha_private.h
@@ -0,0 +1,222 @@
1/*
2chacha-merged.c version 20080118
3D. J. Bernstein
4Public domain.
5*/
6
7/* $OpenBSD: chacha_private.h,v 1.2 2013/10/04 07:02:27 djm Exp $ */
8
9typedef unsigned char u8;
10typedef unsigned int u32;
11
12typedef struct
13{
14 u32 input[16]; /* could be compressed */
15} chacha_ctx;
16
17#define U8C(v) (v##U)
18#define U32C(v) (v##U)
19
20#define U8V(v) ((u8)(v) & U8C(0xFF))
21#define U32V(v) ((u32)(v) & U32C(0xFFFFFFFF))
22
23#define ROTL32(v, n) \
24 (U32V((v) << (n)) | ((v) >> (32 - (n))))
25
26#define U8TO32_LITTLE(p) \
27 (((u32)((p)[0]) ) | \
28 ((u32)((p)[1]) << 8) | \
29 ((u32)((p)[2]) << 16) | \
30 ((u32)((p)[3]) << 24))
31
32#define U32TO8_LITTLE(p, v) \
33 do { \
34 (p)[0] = U8V((v) ); \
35 (p)[1] = U8V((v) >> 8); \
36 (p)[2] = U8V((v) >> 16); \
37 (p)[3] = U8V((v) >> 24); \
38 } while (0)
39
40#define ROTATE(v,c) (ROTL32(v,c))
41#define XOR(v,w) ((v) ^ (w))
42#define PLUS(v,w) (U32V((v) + (w)))
43#define PLUSONE(v) (PLUS((v),1))
44
45#define QUARTERROUND(a,b,c,d) \
46 a = PLUS(a,b); d = ROTATE(XOR(d,a),16); \
47 c = PLUS(c,d); b = ROTATE(XOR(b,c),12); \
48 a = PLUS(a,b); d = ROTATE(XOR(d,a), 8); \
49 c = PLUS(c,d); b = ROTATE(XOR(b,c), 7);
50
51static const char sigma[16] = "expand 32-byte k";
52static const char tau[16] = "expand 16-byte k";
53
54static void
55chacha_keysetup(chacha_ctx *x,const u8 *k,u32 kbits,u32 ivbits)
56{
57 const char *constants;
58
59 x->input[4] = U8TO32_LITTLE(k + 0);
60 x->input[5] = U8TO32_LITTLE(k + 4);
61 x->input[6] = U8TO32_LITTLE(k + 8);
62 x->input[7] = U8TO32_LITTLE(k + 12);
63 if (kbits == 256) { /* recommended */
64 k += 16;
65 constants = sigma;
66 } else { /* kbits == 128 */
67 constants = tau;
68 }
69 x->input[8] = U8TO32_LITTLE(k + 0);
70 x->input[9] = U8TO32_LITTLE(k + 4);
71 x->input[10] = U8TO32_LITTLE(k + 8);
72 x->input[11] = U8TO32_LITTLE(k + 12);
73 x->input[0] = U8TO32_LITTLE(constants + 0);
74 x->input[1] = U8TO32_LITTLE(constants + 4);
75 x->input[2] = U8TO32_LITTLE(constants + 8);
76 x->input[3] = U8TO32_LITTLE(constants + 12);
77}
78
79static void
80chacha_ivsetup(chacha_ctx *x,const u8 *iv)
81{
82 x->input[12] = 0;
83 x->input[13] = 0;
84 x->input[14] = U8TO32_LITTLE(iv + 0);
85 x->input[15] = U8TO32_LITTLE(iv + 4);
86}
87
88static void
89chacha_encrypt_bytes(chacha_ctx *x,const u8 *m,u8 *c,u32 bytes)
90{
91 u32 x0, x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14, x15;
92 u32 j0, j1, j2, j3, j4, j5, j6, j7, j8, j9, j10, j11, j12, j13, j14, j15;
93 u8 *ctarget = NULL;
94 u8 tmp[64];
95 u_int i;
96
97 if (!bytes) return;
98
99 j0 = x->input[0];
100 j1 = x->input[1];
101 j2 = x->input[2];
102 j3 = x->input[3];
103 j4 = x->input[4];
104 j5 = x->input[5];
105 j6 = x->input[6];
106 j7 = x->input[7];
107 j8 = x->input[8];
108 j9 = x->input[9];
109 j10 = x->input[10];
110 j11 = x->input[11];
111 j12 = x->input[12];
112 j13 = x->input[13];
113 j14 = x->input[14];
114 j15 = x->input[15];
115
116 for (;;) {
117 if (bytes < 64) {
118 for (i = 0;i < bytes;++i) tmp[i] = m[i];
119 m = tmp;
120 ctarget = c;
121 c = tmp;
122 }
123 x0 = j0;
124 x1 = j1;
125 x2 = j2;
126 x3 = j3;
127 x4 = j4;
128 x5 = j5;
129 x6 = j6;
130 x7 = j7;
131 x8 = j8;
132 x9 = j9;
133 x10 = j10;
134 x11 = j11;
135 x12 = j12;
136 x13 = j13;
137 x14 = j14;
138 x15 = j15;
139 for (i = 20;i > 0;i -= 2) {
140 QUARTERROUND( x0, x4, x8,x12)
141 QUARTERROUND( x1, x5, x9,x13)
142 QUARTERROUND( x2, x6,x10,x14)
143 QUARTERROUND( x3, x7,x11,x15)
144 QUARTERROUND( x0, x5,x10,x15)
145 QUARTERROUND( x1, x6,x11,x12)
146 QUARTERROUND( x2, x7, x8,x13)
147 QUARTERROUND( x3, x4, x9,x14)
148 }
149 x0 = PLUS(x0,j0);
150 x1 = PLUS(x1,j1);
151 x2 = PLUS(x2,j2);
152 x3 = PLUS(x3,j3);
153 x4 = PLUS(x4,j4);
154 x5 = PLUS(x5,j5);
155 x6 = PLUS(x6,j6);
156 x7 = PLUS(x7,j7);
157 x8 = PLUS(x8,j8);
158 x9 = PLUS(x9,j9);
159 x10 = PLUS(x10,j10);
160 x11 = PLUS(x11,j11);
161 x12 = PLUS(x12,j12);
162 x13 = PLUS(x13,j13);
163 x14 = PLUS(x14,j14);
164 x15 = PLUS(x15,j15);
165
166#ifndef KEYSTREAM_ONLY
167 x0 = XOR(x0,U8TO32_LITTLE(m + 0));
168 x1 = XOR(x1,U8TO32_LITTLE(m + 4));
169 x2 = XOR(x2,U8TO32_LITTLE(m + 8));
170 x3 = XOR(x3,U8TO32_LITTLE(m + 12));
171 x4 = XOR(x4,U8TO32_LITTLE(m + 16));
172 x5 = XOR(x5,U8TO32_LITTLE(m + 20));
173 x6 = XOR(x6,U8TO32_LITTLE(m + 24));
174 x7 = XOR(x7,U8TO32_LITTLE(m + 28));
175 x8 = XOR(x8,U8TO32_LITTLE(m + 32));
176 x9 = XOR(x9,U8TO32_LITTLE(m + 36));
177 x10 = XOR(x10,U8TO32_LITTLE(m + 40));
178 x11 = XOR(x11,U8TO32_LITTLE(m + 44));
179 x12 = XOR(x12,U8TO32_LITTLE(m + 48));
180 x13 = XOR(x13,U8TO32_LITTLE(m + 52));
181 x14 = XOR(x14,U8TO32_LITTLE(m + 56));
182 x15 = XOR(x15,U8TO32_LITTLE(m + 60));
183#endif
184
185 j12 = PLUSONE(j12);
186 if (!j12) {
187 j13 = PLUSONE(j13);
188 /* stopping at 2^70 bytes per nonce is user's responsibility */
189 }
190
191 U32TO8_LITTLE(c + 0,x0);
192 U32TO8_LITTLE(c + 4,x1);
193 U32TO8_LITTLE(c + 8,x2);
194 U32TO8_LITTLE(c + 12,x3);
195 U32TO8_LITTLE(c + 16,x4);
196 U32TO8_LITTLE(c + 20,x5);
197 U32TO8_LITTLE(c + 24,x6);
198 U32TO8_LITTLE(c + 28,x7);
199 U32TO8_LITTLE(c + 32,x8);
200 U32TO8_LITTLE(c + 36,x9);
201 U32TO8_LITTLE(c + 40,x10);
202 U32TO8_LITTLE(c + 44,x11);
203 U32TO8_LITTLE(c + 48,x12);
204 U32TO8_LITTLE(c + 52,x13);
205 U32TO8_LITTLE(c + 56,x14);
206 U32TO8_LITTLE(c + 60,x15);
207
208 if (bytes <= 64) {
209 if (bytes < 64) {
210 for (i = 0;i < bytes;++i) ctarget[i] = c[i];
211 }
212 x->input[12] = j12;
213 x->input[13] = j13;
214 return;
215 }
216 bytes -= 64;
217 c += 64;
218#ifndef KEYSTREAM_ONLY
219 m += 64;
220#endif
221 }
222}