My Little Homegrown Simple Random Generator

That is a great blog post on PRNG and CSPRN. What I'd like to see is the graph of the results of that matrix problem when using chacha20 for completeness.

I just asked the AI at www.phind.com to translate the wikipedia C version of chacha20 to Rust. It looks good and seems to work. Looks to me that if one gives it all zeros as input it produces all zeros as output. Is that supposed to be so? Do you have any test vectors for chacha20?

I once wrote a version of some highly regarded PRNG (forget which now) in assembler for a tiny microcontroller. I'm guessing chacha20 would be much bigger code. We were pushed for every byte on that device. I was amazed my code ended up controlling "sparkly lights" on a costume, live on stage, at a Limp Bizkit concert.

There is a fascination with getting the most about of "randomness" out of the least memory as fast as possible. So I loved that argument between PGC and xoroshiro a while back.

Thanks. For a good PRNG the graph will be approximately flat at 29%.

Some weak PRNGs will also pass this test, it was just an example of something bad that can happen. I didn't put the graph for ChaCha because I didn't want to make the false impression that just this one test proves the generator is good.

No, it should never produce all zeros. The bits you shuffle never start out with all zeros because they contain the magic string "expand 32-byte k" in ASCII before the first iteration. Test vectors.

I'm lost. The C code example of chacha20 has arrays of sixteen uint32_t as input and output. Salsa20 - Wikipedia What do I do with those test test vectors that have 256 bit keys ( only 8 u32s) and 64 bit nonce (only 2 u32s)? And where does that "expand 32-byte k" go? Which is 16 bytes or 4 u32?

That wikipedia C code does indeed produce an array of zeros for an array of zero input.

The hind thing converted that C code to Rust with a couple of mistakes. It did not care about overflow on addition and some how it forgot about the ++2 in the for loop and did to many rounds. With that fixed I get the same results as the wikipedia C version:

macro_rules! ROTL {
    ($a:expr, $b:expr) => {
        (($a) << ($b)) | (($a) >> (32 - ($b)))
    };
}

macro_rules! QR {
    ($a:expr, $b:expr, $c:expr, $d:expr) => {
        $a = $a.wrapping_add($b);
        $d ^= $a;
        $d = ROTL!($d, 16);
        $c = $c.wrapping_add($d);
        $b ^= $c;
        $b = ROTL!($b, 12);
        $a = $a.wrapping_add($b);
        $d ^= $a;
        $d = ROTL!($d, 8);
        $c = $c.wrapping_add($d);
        $b ^= $c;
        $b = ROTL!($b, 7);
    };
}

const ROUNDS: usize = 20;

#[inline(never)]
pub fn chacha_block(output: &mut [u32], input: &[u32; 16]) {
    let mut x = *input; // Copy the input array to x

    // 10 loops × 2 rounds/loop = 20 rounds
    for _ in 0..ROUNDS / 2 {
        // Odd round
        QR!(x[0], x[4], x[8], x[12]); // column 0
        QR!(x[1], x[5], x[9], x[13]); // column 1
        QR!(x[2], x[6], x[10], x[14]); // column 2
        QR!(x[3], x[7], x[11], x[15]); // column 3
                                       // Even round
        QR!(x[0], x[5], x[10], x[15]); // diagonal 1 (main diagonal)
        QR!(x[1], x[6], x[11], x[12]); // diagonal 2
        QR!(x[2], x[7], x[8], x[13]); // diagonal 3
        QR!(x[3], x[4], x[9], x[14]); // diagonal 4
    }

    for i in 0..16 {
        output[i] = x[i].wrapping_add(input[i]);
    }
}

pub fn test() {
    let input = [0u32, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1];
    let mut output = [0u32; 16];
    chacha_block(&mut output[0..16], &input);
    println!("Result: {:x?}", output);
}

Search for "Initial state of ChaCha" in that Wikipedia article. Of the sixteen u32s: 4 are the magic string, 8 are the key, 2 are the nonce, and 2 are the counter that increments starting from 0.

Ha ha! Thanks.

1 Like

I just did install 'nightly' and the formatter finally works

1 Like

Unfortunately I can't find any combination of ways to put that initial state into the input to get the output shown in the Internet Draft.

One thing to pay attention to is that these test vectors are sequences of bytes, and ChaCha considers data to be little-endian.

Yeah, I thought about that. I was plugging that constant, b"expand 32-byte k", in every which way.

But ha! Silly me. I'm printing the output as u32s in hex and forgot that they might be appearing the wrong way around. I do actually have the right result!

Thanks.

1 Like