1
$\begingroup$

We have Mersenne Twister pseudorandom number generator. It has several variants, CryptMT among them, that is of cryptographic grade.

There are alternatives to Mersenne Twister, like Xorshift or Xoroshiro.

Question: Do those algorithms have cryptographic variants, or are they secure per se, or are there other simple pseudorandom number generators that are good for cryptography?

I need a generator that has good random properties as it will be used to generate random matrices (not keys). At the same time it has to be unpredictable enough so the attacker has little control what matrices are generated when messing with the seed.

CLARIFICATION:

The setup is as follows: a random seed is chosen and used to generate pseudorandom square matrices over Boolean ring. Those matrices, when chosen randomly, have certain probability of being singular or not. The PRNG must generate such a sequence so the probability of a matrix being singular is the same as if they were chosen randomly.

The matrices are not secret, they are presented to the user and forward secrecy is not needed. Based on initial state the user might be able to predict all next matrices in a sequence, as long as they admit the right probability distribution.

ATTACK SCENARIO:

An attacker might be able to alter some bits of the random seed. Not all bits, as he might be restricted to altering only a subset of bits of the seed, or flipping several bits at once. Even when the attacked has such ability, the probability of a matrix being singular should be the same as if it was chosen randomly.

HARDER PROBLEM:

We want not only (non)singularity of a matrix to be close to random distribution, but also its rank.

$\endgroup$
  • $\begingroup$ if you are looking for good statistical properties MT is okay, but if you are looking for something somewhat related to security, therefore Marsenne Twister is definitely not your guy. $\endgroup$ – ddddavidee Jun 4 at 9:18
  • $\begingroup$ When you say “little control [over] what matrices are generated when messing with the seed”, what exactly do you need? Careful of making “desirable” results brute-forceable by someone who knows how you’re generating them, for example… $\endgroup$ – Ry- Jun 4 at 15:46
  • $\begingroup$ You didn't express concerns in terms of performances/area/code size. Then why don't you use a NIST approved DRBG ? $\endgroup$ – Ruggero Jun 5 at 10:36
3
$\begingroup$

XorShift and Xoroshiro are LFSRs. LFSRs are a component of some hardware-implementation-focused algorithms. LFSRs are not secure on their own. They are linear, so their state (and thus future output) can be predicted from a few known output bits. Additional operations have to be used in stream ciphers that utilize LFSRs.

Mersenne twister is based on a generalized feedback shift register, so it has similar properties. (Note that generalized does not mean better. Algorithms recommended by Sebastiano Vigna are faster, smaller, and have better quality ouput.)

The operations that CryptMT adds on top of Mersenne Twister will not necessarily (and probably won't) work well with different base RNGs. So Do Not attempt to make your own Frankenstein algorithm.

We shouldn't even be confident that CryptMT is secure. It hasn't received much scrutiny compared to other algorithms. Its design is unusual. (It looks ad hoc and brittle to me. Like RC4.)

The reason why it was rejected in favor of other ciphers is because "The security of the cipher, in particular the non-linear filter component, might not yet be as well-understood as some of the other finalists."

Most non-secure RNGs are quite different from secure ones. Non-secure RNGs, at best, perform just enough scrambling to make patterns in the sequence harder to notice. Secure RNGs must have no exploitable bias or patterns, cannot permit an attacker from using known output to predict past/present output bits they haven't already seen, and can't be vulnerable to key/seed recovery.

It's not easy to build a better secure RNG from an insecure one. Any method based solely on filtering is questionable. You could tweak the original RNG until it's secure, but that would be a totally different algorithm. Or you can pass output through a PRF as is done in CTR mode. But you can use any non-repeating sequence with the PRF, including cheaper ones like incrementing a counter.

Instead of CryptMT, I suggest using ChaCha. Most people, unless they have a good reason to use another specific algorithm, should choose ChaCha for the software they write. ChaCha is fast, secure, and makes efficient use of modern computer hardware.

(If you must use lightweight algorithms on an embedded system, then the answer depends on several factors.)

You wrote:

At the same time it has to be unpredictable enough so the attacker has little control what matrices are generated when messing with the seed.

That may rule out some algorithms. The security of cryptographic algorithms is usually predicated on the key being randomly chosen. (Related key attacks and weak key classes exist with some algorithms.) For RNGs specifically, it may be possible for an attacker to decide on a desirable RNG state and run the initialization procedure backwards to find a seed which leads to that state.

There isn't such a problem with ChaCha used as an RNG. If you don't need secrecy from the algorithm, you can freely choose the key, IV, and counter value. (Ideally, use a secret key and limit the variables the attacker controls to the IV.)

Because each output block from ChaCha is generated using a (really good) one way function, it isn't possible to search for desirable seeds with any method faster than brute force. Certain hash-based RNGs wouldn't have that problem either.

ChaCha adapted from a stream cipher to an RNG should be your First choice for secure deterministic RNGs. (But it Does Not provide backtracking resistance, so consider erasing or replacing the key after some time.)

Alternatively, Blake2X, Skein, and KMAC can be adapted for your Second choice. They all accept secret keys and are all extendable output functions, so it's possible to output as many pseudorandom bits as you want.

$\endgroup$
3
$\begingroup$

Forget the Mersenne Twister and xorshift; maybe CryptMT is secure but it has received very little scrutiny since it was rejected from the eSTREAM portfolio a decade ago. Cryptography is rife with good pseudorandom number generators, like ChaCha: if you pick the seed uniformly at random, the attacker has no hope of distinguishing the output from uniform random, and the world has high confidence in this state of affairs because it has been subjected to heavy scrutiny and there are trillions of euros of economic value protected by ChaCha in HTTPS around the world.

If you have measured performance, and you have profiled, and you have confirmed that a lot of time is spent in ChaCha, and you are confident that this will never be security-relevant—in particular, if you can quantify the statistical tests you need to defeat and argue that smarter statistical tests will never be relevant—then maybe you will have a reason to look elsewhere. But the first thing you can do with ChaCha is tune down the number of rounds from the default ChaCha20 to the cheaper ChaCha12 or even cheaper ChaCha8.


Update, for question's addendum:

If the adversary can control the seed, then even if you used a random oracle for the PRNG (which is the strongest possible model—not attained by ChaCha but a reasonable model for, say, SHAKE128), the adversary can spend an expected $t$ trials finding a seed with a property that occurs only $1/t$ of the time, like $t = 2^n$ trials to find a seed under which the first $n$ bits of output are all zero. No amount of cryptography can help you against this.

But if the adversary can't control the seed, the property you want—nonsingular matrices with high probability—is essentially guaranteed with any cryptographic PRNG. If it weren't, then the putative cryptographic PRNG would be astonishingly bad, because a very simple test—generate a matrix and test whether it's nonsingular—would serve as an attack against the PRNG that breaks it without even knowing how the PRNG is designed!

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.