1 | /**
|
2 | * A javascript implementation of a cryptographically-secure
|
3 | * Pseudo Random Number Generator (PRNG). The Fortuna algorithm is followed
|
4 | * here though the use of SHA-256 is not enforced; when generating an
|
5 | * a PRNG context, the hashing algorithm and block cipher used for
|
6 | * the generator are specified via a plugin.
|
7 | *
|
8 | * @author Dave Longley
|
9 | *
|
10 | * Copyright (c) 2010-2014 Digital Bazaar, Inc.
|
11 | */
|
12 | var forge = require('./forge');
|
13 | require('./util');
|
14 |
|
15 | var _crypto = null;
|
16 | if(forge.util.isNodejs && !forge.options.usePureJavaScript &&
|
17 | !process.versions['node-webkit']) {
|
18 | _crypto = require('crypto');
|
19 | }
|
20 |
|
21 | /* PRNG API */
|
22 | var prng = module.exports = forge.prng = forge.prng || {};
|
23 |
|
24 | /**
|
25 | * Creates a new PRNG context.
|
26 | *
|
27 | * A PRNG plugin must be passed in that will provide:
|
28 | *
|
29 | * 1. A function that initializes the key and seed of a PRNG context. It
|
30 | * will be given a 16 byte key and a 16 byte seed. Any key expansion
|
31 | * or transformation of the seed from a byte string into an array of
|
32 | * integers (or similar) should be performed.
|
33 | * 2. The cryptographic function used by the generator. It takes a key and
|
34 | * a seed.
|
35 | * 3. A seed increment function. It takes the seed and returns seed + 1.
|
36 | * 4. An api to create a message digest.
|
37 | *
|
38 | * For an example, see random.js.
|
39 | *
|
40 | * @param plugin the PRNG plugin to use.
|
41 | */
|
42 | prng.create = function(plugin) {
|
43 | var ctx = {
|
44 | plugin: plugin,
|
45 | key: null,
|
46 | seed: null,
|
47 | time: null,
|
48 | // number of reseeds so far
|
49 | reseeds: 0,
|
50 | // amount of data generated so far
|
51 | generated: 0,
|
52 | // no initial key bytes
|
53 | keyBytes: ''
|
54 | };
|
55 |
|
56 | // create 32 entropy pools (each is a message digest)
|
57 | var md = plugin.md;
|
58 | var pools = new Array(32);
|
59 | for(var i = 0; i < 32; ++i) {
|
60 | pools[i] = md.create();
|
61 | }
|
62 | ctx.pools = pools;
|
63 |
|
64 | // entropy pools are written to cyclically, starting at index 0
|
65 | ctx.pool = 0;
|
66 |
|
67 | /**
|
68 | * Generates random bytes. The bytes may be generated synchronously or
|
69 | * asynchronously. Web workers must use the asynchronous interface or
|
70 | * else the behavior is undefined.
|
71 | *
|
72 | * @param count the number of random bytes to generate.
|
73 | * @param [callback(err, bytes)] called once the operation completes.
|
74 | *
|
75 | * @return count random bytes as a string.
|
76 | */
|
77 | ctx.generate = function(count, callback) {
|
78 | // do synchronously
|
79 | if(!callback) {
|
80 | return ctx.generateSync(count);
|
81 | }
|
82 |
|
83 | // simple generator using counter-based CBC
|
84 | var cipher = ctx.plugin.cipher;
|
85 | var increment = ctx.plugin.increment;
|
86 | var formatKey = ctx.plugin.formatKey;
|
87 | var formatSeed = ctx.plugin.formatSeed;
|
88 | var b = forge.util.createBuffer();
|
89 |
|
90 | // paranoid deviation from Fortuna:
|
91 | // reset key for every request to protect previously
|
92 | // generated random bytes should the key be discovered;
|
93 | // there is no 100ms based reseeding because of this
|
94 | // forced reseed for every `generate` call
|
95 | ctx.key = null;
|
96 |
|
97 | generate();
|
98 |
|
99 | function generate(err) {
|
100 | if(err) {
|
101 | return callback(err);
|
102 | }
|
103 |
|
104 | // sufficient bytes generated
|
105 | if(b.length() >= count) {
|
106 | return callback(null, b.getBytes(count));
|
107 | }
|
108 |
|
109 | // if amount of data generated is greater than 1 MiB, trigger reseed
|
110 | if(ctx.generated > 0xfffff) {
|
111 | ctx.key = null;
|
112 | }
|
113 |
|
114 | if(ctx.key === null) {
|
115 | // prevent stack overflow
|
116 | return forge.util.nextTick(function() {
|
117 | _reseed(generate);
|
118 | });
|
119 | }
|
120 |
|
121 | // generate the random bytes
|
122 | var bytes = cipher(ctx.key, ctx.seed);
|
123 | ctx.generated += bytes.length;
|
124 | b.putBytes(bytes);
|
125 |
|
126 | // generate bytes for a new key and seed
|
127 | ctx.key = formatKey(cipher(ctx.key, increment(ctx.seed)));
|
128 | ctx.seed = formatSeed(cipher(ctx.key, ctx.seed));
|
129 |
|
130 | forge.util.setImmediate(generate);
|
131 | }
|
132 | };
|
133 |
|
134 | /**
|
135 | * Generates random bytes synchronously.
|
136 | *
|
137 | * @param count the number of random bytes to generate.
|
138 | *
|
139 | * @return count random bytes as a string.
|
140 | */
|
141 | ctx.generateSync = function(count) {
|
142 | // simple generator using counter-based CBC
|
143 | var cipher = ctx.plugin.cipher;
|
144 | var increment = ctx.plugin.increment;
|
145 | var formatKey = ctx.plugin.formatKey;
|
146 | var formatSeed = ctx.plugin.formatSeed;
|
147 |
|
148 | // paranoid deviation from Fortuna:
|
149 | // reset key for every request to protect previously
|
150 | // generated random bytes should the key be discovered;
|
151 | // there is no 100ms based reseeding because of this
|
152 | // forced reseed for every `generateSync` call
|
153 | ctx.key = null;
|
154 |
|
155 | var b = forge.util.createBuffer();
|
156 | while(b.length() < count) {
|
157 | // if amount of data generated is greater than 1 MiB, trigger reseed
|
158 | if(ctx.generated > 0xfffff) {
|
159 | ctx.key = null;
|
160 | }
|
161 |
|
162 | if(ctx.key === null) {
|
163 | _reseedSync();
|
164 | }
|
165 |
|
166 | // generate the random bytes
|
167 | var bytes = cipher(ctx.key, ctx.seed);
|
168 | ctx.generated += bytes.length;
|
169 | b.putBytes(bytes);
|
170 |
|
171 | // generate bytes for a new key and seed
|
172 | ctx.key = formatKey(cipher(ctx.key, increment(ctx.seed)));
|
173 | ctx.seed = formatSeed(cipher(ctx.key, ctx.seed));
|
174 | }
|
175 |
|
176 | return b.getBytes(count);
|
177 | };
|
178 |
|
179 | /**
|
180 | * Private function that asynchronously reseeds a generator.
|
181 | *
|
182 | * @param callback(err) called once the operation completes.
|
183 | */
|
184 | function _reseed(callback) {
|
185 | if(ctx.pools[0].messageLength >= 32) {
|
186 | _seed();
|
187 | return callback();
|
188 | }
|
189 | // not enough seed data...
|
190 | var needed = (32 - ctx.pools[0].messageLength) << 5;
|
191 | ctx.seedFile(needed, function(err, bytes) {
|
192 | if(err) {
|
193 | return callback(err);
|
194 | }
|
195 | ctx.collect(bytes);
|
196 | _seed();
|
197 | callback();
|
198 | });
|
199 | }
|
200 |
|
201 | /**
|
202 | * Private function that synchronously reseeds a generator.
|
203 | */
|
204 | function _reseedSync() {
|
205 | if(ctx.pools[0].messageLength >= 32) {
|
206 | return _seed();
|
207 | }
|
208 | // not enough seed data...
|
209 | var needed = (32 - ctx.pools[0].messageLength) << 5;
|
210 | ctx.collect(ctx.seedFileSync(needed));
|
211 | _seed();
|
212 | }
|
213 |
|
214 | /**
|
215 | * Private function that seeds a generator once enough bytes are available.
|
216 | */
|
217 | function _seed() {
|
218 | // update reseed count
|
219 | ctx.reseeds = (ctx.reseeds === 0xffffffff) ? 0 : ctx.reseeds + 1;
|
220 |
|
221 | // goal is to update `key` via:
|
222 | // key = hash(key + s)
|
223 | // where 's' is all collected entropy from selected pools, then...
|
224 |
|
225 | // create a plugin-based message digest
|
226 | var md = ctx.plugin.md.create();
|
227 |
|
228 | // consume current key bytes
|
229 | md.update(ctx.keyBytes);
|
230 |
|
231 | // digest the entropy of pools whose index k meet the
|
232 | // condition 'n mod 2^k == 0' where n is the number of reseeds
|
233 | var _2powK = 1;
|
234 | for(var k = 0; k < 32; ++k) {
|
235 | if(ctx.reseeds % _2powK === 0) {
|
236 | md.update(ctx.pools[k].digest().getBytes());
|
237 | ctx.pools[k].start();
|
238 | }
|
239 | _2powK = _2powK << 1;
|
240 | }
|
241 |
|
242 | // get digest for key bytes
|
243 | ctx.keyBytes = md.digest().getBytes();
|
244 |
|
245 | // paranoid deviation from Fortuna:
|
246 | // update `seed` via `seed = hash(key)`
|
247 | // instead of initializing to zero once and only
|
248 | // ever incrementing it
|
249 | md.start();
|
250 | md.update(ctx.keyBytes);
|
251 | var seedBytes = md.digest().getBytes();
|
252 |
|
253 | // update state
|
254 | ctx.key = ctx.plugin.formatKey(ctx.keyBytes);
|
255 | ctx.seed = ctx.plugin.formatSeed(seedBytes);
|
256 | ctx.generated = 0;
|
257 | }
|
258 |
|
259 | /**
|
260 | * The built-in default seedFile. This seedFile is used when entropy
|
261 | * is needed immediately.
|
262 | *
|
263 | * @param needed the number of bytes that are needed.
|
264 | *
|
265 | * @return the random bytes.
|
266 | */
|
267 | function defaultSeedFile(needed) {
|
268 | // use window.crypto.getRandomValues strong source of entropy if available
|
269 | var getRandomValues = null;
|
270 | var globalScope = forge.util.globalScope;
|
271 | var _crypto = globalScope.crypto || globalScope.msCrypto;
|
272 | if(_crypto && _crypto.getRandomValues) {
|
273 | getRandomValues = function(arr) {
|
274 | return _crypto.getRandomValues(arr);
|
275 | };
|
276 | }
|
277 |
|
278 | var b = forge.util.createBuffer();
|
279 | if(getRandomValues) {
|
280 | while(b.length() < needed) {
|
281 | // max byte length is 65536 before QuotaExceededError is thrown
|
282 | // http://www.w3.org/TR/WebCryptoAPI/#RandomSource-method-getRandomValues
|
283 | var count = Math.max(1, Math.min(needed - b.length(), 65536) / 4);
|
284 | var entropy = new Uint32Array(Math.floor(count));
|
285 | try {
|
286 | getRandomValues(entropy);
|
287 | for(var i = 0; i < entropy.length; ++i) {
|
288 | b.putInt32(entropy[i]);
|
289 | }
|
290 | } catch(e) {
|
291 | /* only ignore QuotaExceededError */
|
292 | if(!(typeof QuotaExceededError !== 'undefined' &&
|
293 | e instanceof QuotaExceededError)) {
|
294 | throw e;
|
295 | }
|
296 | }
|
297 | }
|
298 | }
|
299 |
|
300 | // be sad and add some weak random data
|
301 | if(b.length() < needed) {
|
302 | /* Draws from Park-Miller "minimal standard" 31 bit PRNG,
|
303 | implemented with David G. Carta's optimization: with 32 bit math
|
304 | and without division (Public Domain). */
|
305 | var hi, lo, next;
|
306 | var seed = Math.floor(Math.random() * 0x010000);
|
307 | while(b.length() < needed) {
|
308 | lo = 16807 * (seed & 0xFFFF);
|
309 | hi = 16807 * (seed >> 16);
|
310 | lo += (hi & 0x7FFF) << 16;
|
311 | lo += hi >> 15;
|
312 | lo = (lo & 0x7FFFFFFF) + (lo >> 31);
|
313 | seed = lo & 0xFFFFFFFF;
|
314 |
|
315 | // consume lower 3 bytes of seed
|
316 | for(var i = 0; i < 3; ++i) {
|
317 | // throw in more pseudo random
|
318 | next = seed >>> (i << 3);
|
319 | next ^= Math.floor(Math.random() * 0x0100);
|
320 | b.putByte(String.fromCharCode(next & 0xFF));
|
321 | }
|
322 | }
|
323 | }
|
324 |
|
325 | return b.getBytes(needed);
|
326 | }
|
327 | // initialize seed file APIs
|
328 | if(_crypto) {
|
329 | // use nodejs async API
|
330 | ctx.seedFile = function(needed, callback) {
|
331 | _crypto.randomBytes(needed, function(err, bytes) {
|
332 | if(err) {
|
333 | return callback(err);
|
334 | }
|
335 | callback(null, bytes.toString());
|
336 | });
|
337 | };
|
338 | // use nodejs sync API
|
339 | ctx.seedFileSync = function(needed) {
|
340 | return _crypto.randomBytes(needed).toString();
|
341 | };
|
342 | } else {
|
343 | ctx.seedFile = function(needed, callback) {
|
344 | try {
|
345 | callback(null, defaultSeedFile(needed));
|
346 | } catch(e) {
|
347 | callback(e);
|
348 | }
|
349 | };
|
350 | ctx.seedFileSync = defaultSeedFile;
|
351 | }
|
352 |
|
353 | /**
|
354 | * Adds entropy to a prng ctx's accumulator.
|
355 | *
|
356 | * @param bytes the bytes of entropy as a string.
|
357 | */
|
358 | ctx.collect = function(bytes) {
|
359 | // iterate over pools distributing entropy cyclically
|
360 | var count = bytes.length;
|
361 | for(var i = 0; i < count; ++i) {
|
362 | ctx.pools[ctx.pool].update(bytes.substr(i, 1));
|
363 | ctx.pool = (ctx.pool === 31) ? 0 : ctx.pool + 1;
|
364 | }
|
365 | };
|
366 |
|
367 | /**
|
368 | * Collects an integer of n bits.
|
369 | *
|
370 | * @param i the integer entropy.
|
371 | * @param n the number of bits in the integer.
|
372 | */
|
373 | ctx.collectInt = function(i, n) {
|
374 | var bytes = '';
|
375 | for(var x = 0; x < n; x += 8) {
|
376 | bytes += String.fromCharCode((i >> x) & 0xFF);
|
377 | }
|
378 | ctx.collect(bytes);
|
379 | };
|
380 |
|
381 | /**
|
382 | * Registers a Web Worker to receive immediate entropy from the main thread.
|
383 | * This method is required until Web Workers can access the native crypto
|
384 | * API. This method should be called twice for each created worker, once in
|
385 | * the main thread, and once in the worker itself.
|
386 | *
|
387 | * @param worker the worker to register.
|
388 | */
|
389 | ctx.registerWorker = function(worker) {
|
390 | // worker receives random bytes
|
391 | if(worker === self) {
|
392 | ctx.seedFile = function(needed, callback) {
|
393 | function listener(e) {
|
394 | var data = e.data;
|
395 | if(data.forge && data.forge.prng) {
|
396 | self.removeEventListener('message', listener);
|
397 | callback(data.forge.prng.err, data.forge.prng.bytes);
|
398 | }
|
399 | }
|
400 | self.addEventListener('message', listener);
|
401 | self.postMessage({forge: {prng: {needed: needed}}});
|
402 | };
|
403 | } else {
|
404 | // main thread sends random bytes upon request
|
405 | var listener = function(e) {
|
406 | var data = e.data;
|
407 | if(data.forge && data.forge.prng) {
|
408 | ctx.seedFile(data.forge.prng.needed, function(err, bytes) {
|
409 | worker.postMessage({forge: {prng: {err: err, bytes: bytes}}});
|
410 | });
|
411 | }
|
412 | };
|
413 | // TODO: do we need to remove the event listener when the worker dies?
|
414 | worker.addEventListener('message', listener);
|
415 | }
|
416 | };
|
417 |
|
418 | return ctx;
|
419 | };
|