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