Problem with gmp_randinit_set

[Pedro Gimeno]

Torbjörn Granlund wrote, On 2017-02-16 23:19:
> Pedro Gimeno <gmpdiscuss at formauri.es> writes:
> I haven't read you xxtea patch yet, but let's first see that we agree on
> the theory!
> 
> I believe the named modes ECB, CTR, ICM, whatnot don't necessarily apply
> to PRNG use as we have no plaintext.

That is not how the patch is implemented. The key and IV are constants, and the plaintext is the seed. The purpose of the crypto function is only to initialize the buffer for a given seed, so that the PRNG can take over from there. In the case of Mersenne Twister, the buffer is 624 32-bit words, of which only 1 bit is used from one of them on initialization. That bit is set to 1 in the patch, to ensure that the MT requisite of not all bits being zero is satisfied, and the remaining 623 words are filled with the encrypted version of the seed.

So, the crypto function (xxtea in the patch) takes a 19936-bit seed and converts it into a randomized buffer. The requisite that every seed should generate a different random sequence, makes this transformation need to be a bijection.

The requisite that as many seeds as possible generated different sequences, was stated by Kevin Ryde, so I stuck to it. I agreed it was a desirable property, given that GMP is in a unique position to provide that feature.

I kept this in mind all the time when I analysed the suitability of the different operation modes. CTR and OFB modes are just an XOR with a fixed sequence, therefore for the first 2^32 seeds, the low bits would be the only ones to change. ECB is even worse, as all words beyond the lowest would be equal. CFB could almost work, but the first word would always be just a constant XORed with the seed, which is why I discarded it. CBC and PCBC seemed like the only suitable alternatives, but I see potential issues even with them (if the first block-length lower bits are equal, the first output block is the same).

Of course, the seed could be a shorter integer, say up to 32 bits or up to the key length of the crypto function, in which case much of this discussion would be unnecessary. 32 bits is, in my experience, an extremely short seed space, too easy to exhaust and too prone to birthday collisions when the seeds are random.

> How should the seed look like?  One could put it both in counter and in
> the encryption function's key.  Or both.

This, of course, would drastically reduce the seed space. I'll leave up to you the decision of whether that's desirable or not.

> The state of the generator will be key, counter value, and for
> efficiency partial random_bits.  E.g., if the user asks for 32 bits of
> randomness and we have AES128 as the encrypt function, only one in four
> user calls will cause any encrypt operation.
> 
> Does this make sense to you?

It seems to me that you're discussing a different PRNG, not Mersenne Twister but "AES Twister" :)

That method can't be used for Mersenne Twister. The state of the generator is the 624-word buffer and the current pointers.

>   As a temporary fix, it would also work if minigmp's modular
>   exponentiation could be used, to make the output compatible.
>   
> I don't follow what you're trying to say there, I'm afraid.

The current seeding function takes the seed and calculates a modular exponentiation in order to generate a randomized buffer. That's what is causing the seeding function to need the mpz layer. If the output is to be made compatible, without using mpz, maybe minigmp can be used to provide the modular exponentiation.