Add the ability to create rand_xoshiro directly from the state

[Shatur]

We're currently passing verification from a lab for our secure PQC solution where we use xoshiro. During the code review they revealed that we shouldn't use bytes for randomization because they're vulnerable to template attacks. Each byte have only 255 variants and they can be distinguished between each other when measuring power consumption.

To avoid this, we need to construct xoshiro directly from the state (using u32). Would you be open to adding additional (non-trait) constructor that creates xoshiro from a state without constructing it byte by byte?

[dhardy]

What?

Firstly, xoshiro generators are not cryptographically secure. Their output is predictable from a few output samples, so secure seeding is irrelevant.

Secondly, from_seed does not work on a per-byte basis; it takes a byte-slice and casts that to a sequence of either u32 or u64 words. Edit: this is wrong; see the next comment. It's not always clear what the optimiser does but I don't think any per-byte logic is happening. You can also generate a byte-slice without per-byte logic; Rng::fill_bytes is designed to work this way.

[Shatur]

Firstly, xoshiro generators are not cryptographically secure.

Yes. We're using it to generate random for some other algorithms to create randomization against side channel attacks. So it doesn't need to be cryptographically secure.

But If the seed written in memory byte by byte, a template attack can recover the seed. And If the seed becomes known, all randomization becomes useless.

Secondly, from_seed does not work on a per-byte basis; it takes a byte-slice and casts that

It doesn't cast it. The alignment for any array of u8 is 1, while the alignment of any array of u32 is 4. So it's impossible to just cast it, it requires copying:

https://docs.rs/rand_core/latest/src/rand_core/utils.rs.html#141-151

And while the code iterates over chunks, for platforms that cannot do unaligned reads it copies bytes because &[u8; 4] is guaranteed to be only byte aligned.

I know that our use case is a bit weird, but having a constructor from the state directly (i.e. from [u32; 4]) without any copying would make sense?

[dhardy]

I can only assume you've done the necessary crypto-analysis for this case, but it still seems odd to me that you have selected an inherently predictable PRNG instead of something like SipHash. But clearly you have very tight memory requirements.

I'm also surprised by your determination not to vendor the Xoshiro PRNG. In this case it may be the best option; at least I don't see much reason to consider rand_xoshiro a special case that should carry methods like from_state(u32, u32).

@tarcieri do you have further thoughts on this? I hadn't considered the implication of from_seed potentially leaking seeds through template attacks on platforms without unaligned reads. Of note is that the only per-byte operation in from_seed should be a copy, which may be less easy to read through side-channel attacks than some other algorithms (speculative), e.g. Rc4 uses an array-lookup based on byte values.

[Shatur]

I'm just a regular programmer, all the analysis was done by our mathematicians 🙂
Yeah, the requirements are quite tight.

We're fine with vendoring, but if the necessary methods are available, we would use a version from crates.io. I think having a constructor from the state directly without spending cycles on copying could be useful for small RNGs. But feel free to close the issue if you disagree.

We also learned about it only recently. My team was skeptical about it at first, but they received some convincing articles from the lab that did the analysis. If you're interested, I can ask what articles the lab provided.

[dhardy]

I'm interested to know whether this is a wider issue. Specifically, whether it does affect from_seed and what architectures might be affected. If it is, please report as a security issue (probably against the rand_core repo), not here.

I think having a constructor from the state directly without spending cycles on copying could be useful for small RNGs.

I believe the optimiser can often solves this (at least to word copies), just apparently not everywhere. It's a long time since we restricted SeedableRng::Seed to byte-slice-types, but in retrospect perhaps it would have been better to use u32-slice-types. Now, we could introduce inherent constructors to get around this, but I'm still not convinced it would be useful enough to warrant the number of API additions.

[dhardy]

And while the code iterates over chunks, for platforms that cannot do unaligned reads it copies bytes because &[u8; 4] is guaranteed to be only byte aligned.

read_words is #[inline(always)] so LLVM should be able to infer alignment and avoid per-byte copy.

[Shatur]

The inline doesn't matter. If the pointer is not aligned in memory, it's byte by byte copy. The compiler may generate the runtime check for alignment and if the location in memory happens to be aligned - do it more efficiently. But if the pointer is not aligned, there is nothing it can do, other than copy byte by byte.

[dhardy]

Two levels of inlining are required (SeedableRng::from_seed and read_words), but it definitely should matter:

let seed: [u8; 32] = todo!(); // has known alignment
let rng = Xoshiro256StarStar::from_seed(seed);

[Shatur]

Ah, you think that the compiler will align seed by 4? This could happen, but last time I inspected assembly for something very similar, it didn't happen...