Created
August 7, 2024 23:38
-
-
Save bakkot/3f63616c7be2e93da4fd9da889519a2d to your computer and use it in GitHub Desktop.
ChaCha8Rand (Go's math/rand/v2 RNG) implemented in JS
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
'use strict'; | |
// see https://github.com/C2SP/C2SP/blob/94012bb895565ab4259263d241a9549c4174ccb0/chacha8rand/chacha8rand.go | |
// TODO compare against https://github.com/golang/go/blob/9177e12ccc2115e44de824ae7247ace88617c29a/src/internal/chacha8rand/chacha8_generic.go | |
// should be the same but it's a bit hard to compare | |
// this is not optimized | |
function uint32(n) { | |
return n >>> 0; | |
} | |
function add32(a, b) { | |
return uint32(uint32(a) + uint32(b)); | |
} | |
function xor32(a, b) { | |
return uint32(a ^ b); | |
} | |
function rotl32(a, b) { | |
return uint32((uint32(a) << b) | (uint32(a) >>> (32 - b))); | |
} | |
// ChaCha8 constants | |
const j0 = 0x61707865; // expa | |
const j1 = 0x3320646e; // nd 3 | |
const j2 = 0x79622d32; // 2-by | |
const j3 = 0x6b206574; // te k | |
function quarterRound(a, b, c, d) { | |
a = add32(a, b); | |
d = rotl32(xor32(d, a), 16); | |
c = add32(c, d); | |
b = rotl32(xor32(b, c), 12); | |
a = add32(a, b); | |
d = rotl32(xor32(d, a), 8); | |
c = add32(c, d); | |
b = rotl32(xor32(b, c), 7); | |
return [a, b, c, d]; | |
} | |
// returns { bytes, nextKey } | |
// bytes is a length-992 Uint8Array of random bytes | |
// nextKey is a length-32 Uint8Array suitable for passing into this function again | |
function gen(key) { | |
if (!(key instanceof Uint8Array) || key.length !== 32 || key.buffer.byteLength !== 32) { | |
throw new TypeError('key should be length-32 Uint8Array'); | |
} | |
// todo worry about endianness | |
key = new Uint32Array(key.buffer); | |
let stream = new Uint8Array(1024); | |
let c0 = j0, c1 = j1, c2 = j2, c3 = j3; | |
let c4 = key[0], c5 = key[1], c6 = key[2], c7 = key[3]; | |
let c8 = key[4], c9 = key[5], c10 = key[6], c11 = key[7]; | |
let c12 = 0, c13 = 0, c14 = 0, c15 = 0; | |
let [p1, p5, p9, p13] = quarterRound(c1, c5, c9, c13); | |
let [p2, p6, p10, p14] = quarterRound(c2, c6, c10, c14); | |
let [p3, p7, p11, p15] = quarterRound(c3, c7, c11, c15); | |
for (let offset = 0; offset < 1024; offset += 64) { | |
let [fcr0, fcr4, fcr8, fcr12] = quarterRound(c0, c4, c8, c12); | |
let [x0, x5, x10, x15] = quarterRound(fcr0, p5, p10, p15); | |
let [x1, x6, x11, x12] = quarterRound(p1, p6, p11, fcr12); | |
let [x2, x7, x8, x13] = quarterRound(p2, p7, fcr8, p13); | |
let [x3, x4, x9, x14] = quarterRound(p3, fcr4, p9, p14); | |
for (let i = 0; i < 3; i++) { | |
[x0, x4, x8, x12] = quarterRound(x0, x4, x8, x12); | |
[x1, x5, x9, x13] = quarterRound(x1, x5, x9, x13); | |
[x2, x6, x10, x14] = quarterRound(x2, x6, x10, x14); | |
[x3, x7, x11, x15] = quarterRound(x3, x7, x11, x15); | |
[x0, x5, x10, x15] = quarterRound(x0, x5, x10, x15); | |
[x1, x6, x11, x12] = quarterRound(x1, x6, x11, x12); | |
[x2, x7, x8, x13] = quarterRound(x2, x7, x8, x13); | |
[x3, x4, x9, x14] = quarterRound(x3, x4, x9, x14); | |
} | |
// implicitly subtract out the constants and counter here | |
// also, replace additions of constant 0 with just the value | |
let result = new Uint32Array([ | |
x0, x1, x2, x3, | |
add32(x4, c4), add32(x5, c5), add32(x6, c6), add32(x7, c7), | |
add32(x8, c8), add32(x9, c9), add32(x10, c10), add32(x11, c11), | |
x12, x13, x14, x15, | |
]); | |
stream.set(new Uint8Array(result.buffer), offset); | |
c12 = add32(c12, 1); | |
} | |
let output = new Uint8Array(1024); | |
// "for each sequence of four blocks, first we output the first four bytes of each block, then the next four bytes of each block, and so on" | |
// see | |
// https://github.com/C2SP/C2SP/blob/94012bb895565ab4259263d241a9549c4174ccb0/chacha8rand.md#design-rationale | |
// for rationale | |
let streamOffset = 0; | |
for (let b = 0; b < 16; b += 4) { | |
for (let i = 0; i < 64; i += 4) { | |
output.set(stream.subarray(streamOffset + 0 * 64 + i, streamOffset + 0 * 64 + i + 4), b * 64 + i * 4 + 0); | |
output.set(stream.subarray(streamOffset + 1 * 64 + i, streamOffset + 1 * 64 + i + 4), b * 64 + i * 4 + 4); | |
output.set(stream.subarray(streamOffset + 2 * 64 + i, streamOffset + 2 * 64 + i + 4), b * 64 + i * 4 + 8); | |
output.set(stream.subarray(streamOffset + 3 * 64 + i, streamOffset + 3 * 64 + i + 4), b * 64 + i * 4 + 12); | |
} | |
streamOffset += 256; | |
} | |
let nextKey = output.slice(1024 - 32); | |
let bytes = output.slice(0, 1024 - 32); | |
return { bytes, nextKey }; | |
} | |
// should match ouput from | |
// https://github.com/C2SP/C2SP/blob/94012bb895565ab4259263d241a9549c4174ccb0/chacha8rand.md#sample-output | |
{ | |
let { bytes, nextKey } = gen(new TextEncoder().encode('ABCDEFGHIJKLMNOPQRSTUVWXYZ123456')); | |
for (let i = 0; i < bytes.length; i += 32) { | |
console.log(bytes.subarray(i, i + 32).reduce((acc, val) => acc + val.toString(16).padStart(2, '0'), '')); | |
} | |
0, { bytes, nextKey } = gen(nextKey); | |
for (let i = 0; i < bytes.length; i += 32) { | |
console.log(bytes.subarray(i, i + 32).reduce((acc, val) => acc + val.toString(16).padStart(2, '0'), '')); | |
} | |
0, { bytes, nextKey } = gen(nextKey); | |
for (let i = 0; i < bytes.length; i += 32) { | |
console.log(bytes.subarray(i, i + 32).reduce((acc, val) => acc + val.toString(16).padStart(2, '0'), '')); | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment