Skip to content

Instantly share code, notes, and snippets.

@bakkot
Created August 7, 2024 23:38
Show Gist options
  • Save bakkot/3f63616c7be2e93da4fd9da889519a2d to your computer and use it in GitHub Desktop.
Save bakkot/3f63616c7be2e93da4fd9da889519a2d to your computer and use it in GitHub Desktop.
ChaCha8Rand (Go's math/rand/v2 RNG) implemented in JS
'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