| blob | 29dbe9afc6827c7860728dac94d1189274bbf44d |
1 .\" $NetBSD: arc4random.3,v 1.19 2014/11/17 18:41:29 riastradh Exp $
2 .\"
3 .\" Copyright (c) 2014 The NetBSD Foundation, Inc.
4 .\" All rights reserved.
5 .\"
6 .\" This code is derived from software contributed to The NetBSD Foundation
7 .\" by Taylor R. Campbell.
8 .\"
9 .\" Redistribution and use in source and binary forms, with or without
10 .\" modification, are permitted provided that the following conditions
11 .\" are met:
12 .\" 1. Redistributions of source code must retain the above copyright
13 .\" notice, this list of conditions and the following disclaimer.
14 .\" 2. Redistributions in binary form must reproduce the above copyright
15 .\" notice, this list of conditions and the following disclaimer in the
16 .\" documentation and/or other materials provided with the distribution.
17 .\"
18 .\" THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS
19 .\" ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
20 .\" TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
21 .\" PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS
22 .\" BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
23 .\" CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
24 .\" SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
25 .\" INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
26 .\" CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
27 .\" ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
28 .\" POSSIBILITY OF SUCH DAMAGE.
29 .\"
30 .Dd November 16, 2014
31 .Dt ARC4RANDOM 3
32 .Os
33 .Sh NAME
34 .Nm arc4random ,
35 .Nm arc4random_uniform ,
36 .Nm arc4random_buf ,
37 .Nm arc4random_stir ,
38 .Nm arc4random_addrandom
39 .Nd random number generator
40 .Sh LIBRARY
41 .Lb libc
42 .Sh SYNOPSIS
43 .In stdlib.h
44 .Ft uint32_t
45 .Fn arc4random "void"
46 .Ft uint32_t
47 .Fn arc4random_uniform "uint32_t bound"
48 .Ft void
49 .Fn arc4random_buf "void *buf" "size_t len"
50 .Ft void
51 .Fn arc4random_stir "void"
52 .Ft void
53 .Fn arc4random_addrandom "unsigned char *buf" "int len"
54 .Sh DESCRIPTION
55 The
56 .Nm
57 family of functions provides a cryptographic pseudorandom number
58 generator automatically seeded from the system entropy pool and safe to
59 use from multiple threads.
60 .Nm
61 is designed to prevent an adversary from guessing outputs,
62 unlike
63 .Xr rand 3
64 and
65 .Xr random 3 ,
66 and is faster and more convenient than reading from
67 .Pa /dev/urandom
68 directly.
69 .Pp
70 .Fn arc4random
71 returns an integer in [0, 2^32) chosen independently with uniform
72 distribution.
73 .Pp
74 .Fn arc4random_uniform
75 returns an integer in [0,
76 .Fa bound )
77 chosen independently with uniform distribution.
78 .Pp
79 .Fn arc4random_buf
80 stores
81 .Fa len
82 bytes into the memory pointed to by
83 .Fa buf ,
84 each byte chosen independently from [0, 256) with uniform
85 distribution.
86 .Pp
87 .Fn arc4random_stir
88 draws entropy from the operating system and incorporates it into the
89 library's PRNG state to influence future outputs.
90 .Pp
91 .Fn arc4random_addrandom
92 incorporates
93 .Fa len
94 bytes, which must be nonnegative, from the buffer
95 .Fa buf ,
96 into the library's PRNG state to influence future outputs.
97 .Pp
98 It is not necessary for an application to call
99 .Fn arc4random_stir
100 or
101 .Fn arc4random_addrandom
102 before calling other
103 .Nm
104 functions.
105 The first call to any
106 .Nm
107 function will initialize the PRNG state unpredictably from the system
108 entropy pool.
109 .Sh SECURITY MODEL
110 The
111 .Nm
112 functions provide the following security properties against three
113 different classes of attackers, assuming enough entropy is provided by
114 the operating system:
115 .Bl -bullet -offset abcd
116 .It
117 An attacker who has seen some outputs of any of the
118 .Nm
119 functions cannot predict past or future unseen outputs.
120 .It
121 An attacker who has seen the library's PRNG state in memory cannot
122 predict past outputs.
123 .It
124 An attacker who has seen one process's PRNG state cannot predict past
125 or future outputs in other processes, particularly its parent or
126 siblings.
127 .El
128 .Pp
129 One
130 .Sq output
131 means the result of any single request to an
132 .Nm
133 function, no matter how short it is.
134 .Sh IMPLEMENTATION NOTES
135 The
136 .Nm
137 functions are currently implemented using the ChaCha20 pseudorandom
138 function family.
139 For any 32-byte string
140 .Fa s ,
141 .Pf ChaCha20_ Fa s
142 is a function from 16-byte strings to 64-byte strings.
143 It is conjectured that if
144 .Fa s
145 is chosen with uniform distribution, then the distribution on
146 .Pf ChaCha20_ Fa s
147 is indistinguishable to a computationally bounded adversary from a
148 uniform distribution on all functions from 16-byte strings to 64-byte
149 strings.
150 .Pp
151 The PRNG state is a 32-byte ChaCha20 key
152 .Fa s .
153 Each request to
154 an
155 .Nm
156 function
157 .Bl -bullet -offset abcd -compact
158 .It
159 computes the 64-byte quantity
160 .Fa x
161 =
162 .Pf ChaCha20_ Fa s Ns (0),
163 .It
164 splits
165 .Fa x
166 into two 32-byte quantities
167 .Fa s'
168 and
169 .Fa k ,
170 .It
171 replaces
172 .Fa s
173 by
174 .Fa s' ,
175 and
176 .It
177 uses
178 .Fa k
179 as output.
180 .El
181 .Pp
182 .Fn arc4random
183 yields the first four bytes of
184 .Fa k
185 as output directly.
186 .Fn arc4random_buf
187 either yields up to 32 bytes of
188 .Fa k
189 as output directly, or, for longer
190 requests, uses
191 .Fa k
192 as a ChaCha20 key and yields the concatenation
193 .Pf ChaCha20_ Fa k Ns (0)
194 ||
195 .Pf ChaCha20_ Fa k Ns (1)
196 || ... as output.
197 .Fn arc4random_uniform
198 repeats
199 .Fn arc4random
200 until it obtains an integer in [2^32 %
201 .Fa bound ,
202 2^32), and reduces that modulo
203 .Fa bound .
204 .Pp
205 The PRNG state is per-thread, unless memory allocation fails inside the
206 library, in which case some threads may share global PRNG state with a
207 mutex.
208 The global PRNG state is zeroed on fork in the parent via
209 .Xr pthread_atfork 3 ,
210 and the per-thread PRNG state is zeroed on fork in the child via
211 .Xr minherit 2
212 with
213 .Dv MAP_INHERIT_ZERO ,
214 so that the child cannot reuse or see the parent's PRNG state.
215 The PRNG state is reseeded automatically from the system entropy pool
216 on the first use of an
217 .Nm
218 function after zeroing.
219 .Pp
220 The first use of an
221 .Nm
222 function may abort the process in the highly unlikely event that
223 library initialization necessary to implement the security model fails.
224 Additionally,
225 .Fn arc4random_stir
226 and
227 .Fn arc4random_addrandom
228 may abort the process in the highly unlikely event that the operating
229 system fails to provide entropy.
230 .Sh SEE ALSO
231 .Xr rand 3 ,
232 .Xr random 3 ,
233 .Xr rnd 4 ,
234 .Xr cprng 9
235 .Rs
236 .%A Daniel J. Bernstein
237 .%T ChaCha, a variant of Salsa20
238 .%D 2008-01-28
239 .%O Document ID: 4027b5256e17b9796842e6d0f68b0b5e
240 .%U http://cr.yp.to/papers.html#chacha
241 .Re
242 .Sh BUGS
243 There is no way to get deterministic, reproducible results out of
244 .Nm
245 for testing purposes.
246 .Pp
247 The name
248 .Sq arc4random
249 was chosen for hysterical raisins -- it was originally implemented
250 using the RC4 stream cipher, which has been known since shortly after
251 it was published in 1994 to have observable biases in the output, and
252 is now known to be broken badly enough to admit practical attacks in
253 the real world.
254 .\" Bob Jenkins, sci.crypt post dated 1994-09-16, message-id
255 .\" <359qjg$55v$1@mhadg.production.compuserve.com>,
256 .\" https://groups.google.com/d/msg/sci.crypt/JsO3xEATGFA/-wO4ttv7BCYJ
257 .\"
258 .\" Andrew Roos, `A Class of Weak Keys in the RC4 Stream Cipher',
259 .\" sci.crypt posts dated 1995-09-22, message-ids
260 .\" <43u1eh$1j3@hermes.is.co.za> and <44ebge$llf@hermes.is.co.za>.
261 .\"
262 .\" Paul Crowley, `Small bias in RC4 experimentally verified', March
263 .\" 1998, http://www.ciphergoth.org/crypto/rc4/
264 Unfortunately, the library found widespread adoption and the name stuck
265 before anyone recognized that it was silly.
266 .Pp
267 The signature of
268 .Fn arc4random_addrandom
269 is silly.
270 There is no reason to require casts or accept negative lengths:
271 it should take a
272 .Vt void *
273 buffer and a
274 .Vt size_t
275 length.
276 But it's too late to change that now.
277 .Pp
278 .Fn arc4random_uniform
279 does not help to choose integers in [0,
280 .Fa n )
281 uniformly at random when
282 .Fa n
283 > 2^32.
284 .Pp
285 The security model of
286 .Nm
287 is stronger than many applications need, and stronger than other
288 operating systems provide.
289 For example, applications encrypting messages with random, but not
290 secret, initialization vectors need only prevent an adversary from
291 guessing future outputs, since past outputs will have been published
292 already.
293 .Pp
294 On the one hand,
295 .Nm
296 could be marginally faster if it were not necessary to prevent an
297 adversary who sees the state from predicting past outputs.
298 On the other hand, there are applications in the wild that use
299 .Nm
300 to generate key material, such as OpenSSH, so for the sake of
301 .Nx
302 users it would be imprudent to weaken the security model.
303 On the third hand, relying on the security model of
304 .Nm
305 in
306 .Nx
307 may lead you to an unpleasant surprise on another operating system
308 whose implementation of
309 .Nm
310 has a weaker security model.
311 .Pp
312 One may be tempted to create new APIs to accommodate different
313 security models and performance constraints without unpleasant
314 surprises on different operating systems.
315 This should not be done lightly, though, because there are already too
316 many different choices, and too many opportunities for programmers to
317 reach for one and pick the wrong one.