3
$\begingroup$

Based on the above two questions, I have simply one additional question: how broken is a XOR of two 64-bit multiply with carry generators, with one generator's output rotated by 24-bits before the XOR, and independently generated seed states, with the first output discarded?

Furthermore, what is the fastest attack against this generator with only $2^{20}$ outputs?

$\endgroup$
1
+25
$\begingroup$

I see no reason to expect your construction to be cryptographically secure. A single MWC generator is not something that was ever designed to be cryptographically secure. A cryptographically-strong PRNG needs to be designed in a very different way from a non-crypto PRNG. In particular, it sounds like MWC was designed to have a long period. But having a long period does not guarantee that a PRNG will be crypto-strength; not anywhere near it. And xor-ing two non-crypto-strength PRNGs is not in general a good way to build a crypto-strength PRNG; there's no reason to expect that such a scheme will be secure.

Crypto-strength PRNGs have much stronger requirements, so there is no reason to expect that a statistical non-crypto PRNG will be cryptographically strong (it almost certainly won't be, if it wasn't designed to be). If you want a crypto-strength PRNG, you need to pick one that was designed to be that way from the start; you're not likely to fare well by picking a non-crypto PRNG and then trying to tweak it.

In any case, this approach seems misguided. We have crypto-strength PRNGs that are secure, fast, and well-vetted. I don't know why one would mess around with trying to design your own based upon a non-crypto PRNG; that way tends to lead to insecurity. If you think you can do better than the entire field at designing fast crypto-strength PRNGs... well, maybe you can, but I doubt the odds are on your side. Instead, I recommend you use a standard crypto-strength PRNG, if you need crypto-quality pseudorandom numbers.

I recommend take a look at What stops the Multiply-With-Carry RNG from being a Cryptographically Secure PRNG?, as well as by KISS: A Bit Too Simple (PDF). The first one handles the plain MWC construction by Marsaglia; the later analyzes the non-cryptographic scheme by Marsaglia named KISS (which combines the output from two MWC generators as well as a linear congruential generator and a binary linear generator). Both do not exactly represent the same construction, but the broad lessons probably apply here as well. I've paraphrased from my answer there and extended it to apply to this specific question as well.

$\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.