]>
Commit | Line | Data |
---|---|---|
1a4d82fc JJ |
1 | // Copyright 2014 The Rust Project Developers. See the COPYRIGHT |
2 | // file at the top-level directory of this distribution and at | |
3 | // http://rust-lang.org/COPYRIGHT. | |
4 | // | |
5 | // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or | |
6 | // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license | |
7 | // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your | |
8 | // option. This file may not be copied, modified, or distributed | |
9 | // except according to those terms. | |
10 | ||
11 | //! The ChaCha random number generator. | |
12 | ||
1a4d82fc JJ |
13 | use {Rng, SeedableRng, Rand}; |
14 | ||
92a42be0 SL |
15 | const KEY_WORDS: usize = 8; // 8 words for the 256-bit key |
16 | const STATE_WORDS: usize = 16; | |
c34b1796 | 17 | const CHACHA_ROUNDS: usize = 20; // Cryptographically secure from 8 upwards as of this writing |
1a4d82fc JJ |
18 | |
19 | /// A random number generator that uses the ChaCha20 algorithm [1]. | |
20 | /// | |
21 | /// The ChaCha algorithm is widely accepted as suitable for | |
22 | /// cryptographic purposes, but this implementation has not been | |
23 | /// verified as such. Prefer a generator like `OsRng` that defers to | |
24 | /// the operating system for cases that need high security. | |
25 | /// | |
26 | /// [1]: D. J. Bernstein, [*ChaCha, a variant of | |
27 | /// Salsa20*](http://cr.yp.to/chacha.html) | |
28 | #[derive(Copy, Clone)] | |
29 | pub struct ChaChaRng { | |
b039eaaf SL |
30 | buffer: [u32; STATE_WORDS], // Internal buffer of output |
31 | state: [u32; STATE_WORDS], // Initial state | |
32 | index: usize, // Index into state | |
1a4d82fc JJ |
33 | } |
34 | ||
35 | static EMPTY: ChaChaRng = ChaChaRng { | |
b039eaaf SL |
36 | buffer: [0; STATE_WORDS], |
37 | state: [0; STATE_WORDS], | |
38 | index: STATE_WORDS, | |
1a4d82fc JJ |
39 | }; |
40 | ||
41 | ||
42 | macro_rules! quarter_round{ | |
43 | ($a: expr, $b: expr, $c: expr, $d: expr) => {{ | |
c34b1796 AL |
44 | $a = $a.wrapping_add($b); $d = $d ^ $a; $d = $d.rotate_left(16); |
45 | $c = $c.wrapping_add($d); $b = $b ^ $c; $b = $b.rotate_left(12); | |
46 | $a = $a.wrapping_add($b); $d = $d ^ $a; $d = $d.rotate_left( 8); | |
47 | $c = $c.wrapping_add($d); $b = $b ^ $c; $b = $b.rotate_left( 7); | |
1a4d82fc JJ |
48 | }} |
49 | } | |
50 | ||
51 | macro_rules! double_round{ | |
52 | ($x: expr) => {{ | |
53 | // Column round | |
54 | quarter_round!($x[ 0], $x[ 4], $x[ 8], $x[12]); | |
55 | quarter_round!($x[ 1], $x[ 5], $x[ 9], $x[13]); | |
56 | quarter_round!($x[ 2], $x[ 6], $x[10], $x[14]); | |
57 | quarter_round!($x[ 3], $x[ 7], $x[11], $x[15]); | |
58 | // Diagonal round | |
59 | quarter_round!($x[ 0], $x[ 5], $x[10], $x[15]); | |
60 | quarter_round!($x[ 1], $x[ 6], $x[11], $x[12]); | |
61 | quarter_round!($x[ 2], $x[ 7], $x[ 8], $x[13]); | |
62 | quarter_round!($x[ 3], $x[ 4], $x[ 9], $x[14]); | |
63 | }} | |
64 | } | |
65 | ||
66 | #[inline] | |
67 | fn core(output: &mut [u32; STATE_WORDS], input: &[u32; STATE_WORDS]) { | |
68 | *output = *input; | |
69 | ||
85aaf69f | 70 | for _ in 0..CHACHA_ROUNDS / 2 { |
1a4d82fc JJ |
71 | double_round!(output); |
72 | } | |
73 | ||
85aaf69f | 74 | for i in 0..STATE_WORDS { |
c34b1796 | 75 | output[i] = output[i].wrapping_add(input[i]); |
1a4d82fc JJ |
76 | } |
77 | } | |
78 | ||
79 | impl ChaChaRng { | |
1a4d82fc JJ |
80 | /// Create an ChaCha random number generator using the default |
81 | /// fixed key of 8 zero words. | |
82 | pub fn new_unseeded() -> ChaChaRng { | |
83 | let mut rng = EMPTY; | |
84 | rng.init(&[0; KEY_WORDS]); | |
85 | rng | |
86 | } | |
87 | ||
88 | /// Sets the internal 128-bit ChaCha counter to | |
89 | /// a user-provided value. This permits jumping | |
90 | /// arbitrarily ahead (or backwards) in the pseudorandom stream. | |
91 | /// | |
92 | /// Since the nonce words are used to extend the counter to 128 bits, | |
93 | /// users wishing to obtain the conventional ChaCha pseudorandom stream | |
94 | /// associated with a particular nonce can call this function with | |
95 | /// arguments `0, desired_nonce`. | |
96 | pub fn set_counter(&mut self, counter_low: u64, counter_high: u64) { | |
b039eaaf | 97 | self.state[12] = (counter_low >> 0) as u32; |
1a4d82fc | 98 | self.state[13] = (counter_low >> 32) as u32; |
b039eaaf | 99 | self.state[14] = (counter_high >> 0) as u32; |
1a4d82fc JJ |
100 | self.state[15] = (counter_high >> 32) as u32; |
101 | self.index = STATE_WORDS; // force recomputation | |
102 | } | |
103 | ||
104 | /// Initializes `self.state` with the appropriate key and constants | |
105 | /// | |
106 | /// We deviate slightly from the ChaCha specification regarding | |
107 | /// the nonce, which is used to extend the counter to 128 bits. | |
108 | /// This is provably as strong as the original cipher, though, | |
109 | /// since any distinguishing attack on our variant also works | |
110 | /// against ChaCha with a chosen-nonce. See the XSalsa20 [1] | |
111 | /// security proof for a more involved example of this. | |
112 | /// | |
113 | /// The modified word layout is: | |
114 | /// ```text | |
115 | /// constant constant constant constant | |
116 | /// key key key key | |
117 | /// key key key key | |
118 | /// counter counter counter counter | |
119 | /// ``` | |
120 | /// [1]: Daniel J. Bernstein. [*Extending the Salsa20 | |
121 | /// nonce.*](http://cr.yp.to/papers.html#xsalsa) | |
122 | fn init(&mut self, key: &[u32; KEY_WORDS]) { | |
123 | self.state[0] = 0x61707865; | |
124 | self.state[1] = 0x3320646E; | |
125 | self.state[2] = 0x79622D32; | |
126 | self.state[3] = 0x6B206574; | |
127 | ||
85aaf69f | 128 | for i in 0..KEY_WORDS { |
b039eaaf | 129 | self.state[4 + i] = key[i]; |
1a4d82fc JJ |
130 | } |
131 | ||
132 | self.state[12] = 0; | |
133 | self.state[13] = 0; | |
134 | self.state[14] = 0; | |
135 | self.state[15] = 0; | |
136 | ||
137 | self.index = STATE_WORDS; | |
138 | } | |
139 | ||
140 | /// Refill the internal output buffer (`self.buffer`) | |
141 | fn update(&mut self) { | |
142 | core(&mut self.buffer, &self.state); | |
143 | self.index = 0; | |
144 | // update 128-bit counter | |
145 | self.state[12] += 1; | |
b039eaaf SL |
146 | if self.state[12] != 0 { |
147 | return; | |
148 | } | |
1a4d82fc | 149 | self.state[13] += 1; |
b039eaaf SL |
150 | if self.state[13] != 0 { |
151 | return; | |
152 | } | |
1a4d82fc | 153 | self.state[14] += 1; |
b039eaaf SL |
154 | if self.state[14] != 0 { |
155 | return; | |
156 | } | |
1a4d82fc JJ |
157 | self.state[15] += 1; |
158 | } | |
159 | } | |
160 | ||
161 | impl Rng for ChaChaRng { | |
162 | #[inline] | |
163 | fn next_u32(&mut self) -> u32 { | |
164 | if self.index == STATE_WORDS { | |
165 | self.update(); | |
166 | } | |
167 | ||
168 | let value = self.buffer[self.index % STATE_WORDS]; | |
169 | self.index += 1; | |
170 | value | |
171 | } | |
172 | } | |
173 | ||
174 | impl<'a> SeedableRng<&'a [u32]> for ChaChaRng { | |
1a4d82fc JJ |
175 | fn reseed(&mut self, seed: &'a [u32]) { |
176 | // reset state | |
c34b1796 | 177 | self.init(&[0; KEY_WORDS]); |
1a4d82fc | 178 | // set key in place |
b039eaaf | 179 | let key = &mut self.state[4..4 + KEY_WORDS]; |
62682a34 | 180 | for (k, s) in key.iter_mut().zip(seed) { |
1a4d82fc JJ |
181 | *k = *s; |
182 | } | |
183 | } | |
184 | ||
185 | /// Create a ChaCha generator from a seed, | |
186 | /// obtained from a variable-length u32 array. | |
187 | /// Only up to 8 words are used; if less than 8 | |
188 | /// words are used, the remaining are set to zero. | |
189 | fn from_seed(seed: &'a [u32]) -> ChaChaRng { | |
190 | let mut rng = EMPTY; | |
191 | rng.reseed(seed); | |
192 | rng | |
193 | } | |
194 | } | |
195 | ||
196 | impl Rand for ChaChaRng { | |
197 | fn rand<R: Rng>(other: &mut R) -> ChaChaRng { | |
b039eaaf | 198 | let mut key: [u32; KEY_WORDS] = [0; KEY_WORDS]; |
85aaf69f | 199 | for word in &mut key { |
1a4d82fc JJ |
200 | *word = other.gen(); |
201 | } | |
c34b1796 | 202 | SeedableRng::from_seed(&key[..]) |
1a4d82fc JJ |
203 | } |
204 | } | |
205 | ||
206 | ||
207 | #[cfg(test)] | |
d9579d0f | 208 | mod tests { |
1a4d82fc JJ |
209 | use std::prelude::v1::*; |
210 | ||
211 | use core::iter::order; | |
212 | use {Rng, SeedableRng}; | |
213 | use super::ChaChaRng; | |
214 | ||
215 | #[test] | |
216 | fn test_rng_rand_seeded() { | |
217 | let s = ::test::rng().gen_iter::<u32>().take(8).collect::<Vec<u32>>(); | |
85aaf69f SL |
218 | let mut ra: ChaChaRng = SeedableRng::from_seed(&*s); |
219 | let mut rb: ChaChaRng = SeedableRng::from_seed(&*s); | |
1a4d82fc JJ |
220 | assert!(order::equals(ra.gen_ascii_chars().take(100), |
221 | rb.gen_ascii_chars().take(100))); | |
222 | } | |
223 | ||
224 | #[test] | |
225 | fn test_rng_seeded() { | |
b039eaaf | 226 | let seed: &[_] = &[0, 1, 2, 3, 4, 5, 6, 7]; |
1a4d82fc JJ |
227 | let mut ra: ChaChaRng = SeedableRng::from_seed(seed); |
228 | let mut rb: ChaChaRng = SeedableRng::from_seed(seed); | |
229 | assert!(order::equals(ra.gen_ascii_chars().take(100), | |
230 | rb.gen_ascii_chars().take(100))); | |
231 | } | |
232 | ||
233 | #[test] | |
234 | fn test_rng_reseed() { | |
235 | let s = ::test::rng().gen_iter::<u32>().take(8).collect::<Vec<u32>>(); | |
85aaf69f | 236 | let mut r: ChaChaRng = SeedableRng::from_seed(&*s); |
1a4d82fc JJ |
237 | let string1: String = r.gen_ascii_chars().take(100).collect(); |
238 | ||
85aaf69f | 239 | r.reseed(&s); |
1a4d82fc JJ |
240 | |
241 | let string2: String = r.gen_ascii_chars().take(100).collect(); | |
242 | assert_eq!(string1, string2); | |
243 | } | |
244 | ||
245 | #[test] | |
b039eaaf | 246 | #[rustfmt_skip] |
1a4d82fc JJ |
247 | fn test_rng_true_values() { |
248 | // Test vectors 1 and 2 from | |
249 | // http://tools.ietf.org/html/draft-nir-cfrg-chacha20-poly1305-04 | |
b039eaaf | 250 | let seed: &[_] = &[0; 8]; |
1a4d82fc JJ |
251 | let mut ra: ChaChaRng = SeedableRng::from_seed(seed); |
252 | ||
85aaf69f | 253 | let v = (0..16).map(|_| ra.next_u32()).collect::<Vec<_>>(); |
1a4d82fc JJ |
254 | assert_eq!(v, |
255 | vec!(0xade0b876, 0x903df1a0, 0xe56a5d40, 0x28bd8653, | |
256 | 0xb819d2bd, 0x1aed8da0, 0xccef36a8, 0xc70d778b, | |
257 | 0x7c5941da, 0x8d485751, 0x3fe02477, 0x374ad8b8, | |
258 | 0xf4b8436a, 0x1ca11815, 0x69b687c3, 0x8665eeb2)); | |
259 | ||
85aaf69f | 260 | let v = (0..16).map(|_| ra.next_u32()).collect::<Vec<_>>(); |
1a4d82fc JJ |
261 | assert_eq!(v, |
262 | vec!(0xbee7079f, 0x7a385155, 0x7c97ba98, 0x0d082d73, | |
263 | 0xa0290fcb, 0x6965e348, 0x3e53c612, 0xed7aee32, | |
264 | 0x7621b729, 0x434ee69c, 0xb03371d5, 0xd539d874, | |
265 | 0x281fed31, 0x45fb0a51, 0x1f0ae1ac, 0x6f4d794b)); | |
266 | ||
267 | ||
b039eaaf | 268 | let seed: &[_] = &[0, 1, 2, 3, 4, 5, 6, 7]; |
1a4d82fc JJ |
269 | let mut ra: ChaChaRng = SeedableRng::from_seed(seed); |
270 | ||
271 | // Store the 17*i-th 32-bit word, | |
272 | // i.e., the i-th word of the i-th 16-word block | |
b039eaaf | 273 | let mut v: Vec<u32> = Vec::new(); |
85aaf69f | 274 | for _ in 0..16 { |
1a4d82fc | 275 | v.push(ra.next_u32()); |
85aaf69f | 276 | for _ in 0..16 { |
1a4d82fc JJ |
277 | ra.next_u32(); |
278 | } | |
279 | } | |
280 | ||
281 | assert_eq!(v, | |
282 | vec!(0xf225c81a, 0x6ab1be57, 0x04d42951, 0x70858036, | |
283 | 0x49884684, 0x64efec72, 0x4be2d186, 0x3615b384, | |
284 | 0x11cfa18e, 0xd3c50049, 0x75c775f6, 0x434c6530, | |
285 | 0x2c5bad8f, 0x898881dc, 0x5f1c86d9, 0xc1f8e7f4)); | |
286 | } | |
287 | ||
288 | #[test] | |
289 | fn test_rng_clone() { | |
b039eaaf | 290 | let seed: &[_] = &[0; 8]; |
1a4d82fc JJ |
291 | let mut rng: ChaChaRng = SeedableRng::from_seed(seed); |
292 | let mut clone = rng.clone(); | |
85aaf69f | 293 | for _ in 0..16 { |
1a4d82fc JJ |
294 | assert_eq!(rng.next_u64(), clone.next_u64()); |
295 | } | |
296 | } | |
297 | } |