Problem with gmp_randinit_set

Torbjörn Granlund tg at gmplib.org
Thu Feb 16 22:19:48 UTC 2017


Pedro Gimeno <gmpdiscuss at formauri.es> writes:

  I chose xxtea for being simple and small (as can be seen in the patch)
  and for having variable block size, so I could encrypt just 1 block of
  19936 bits, eliminating the need to choose a suitable enciphering
  mode. For ciphers with smaller block size, ECB, OFB, CFB and CTR are
  definitely discarded; CBC and PCBC could perhaps work (I'm using names
  from https://en.wikipedia.org/wiki/Block_cipher_mode_of_operation ). I
  tested xxtea's randomness properties and I was very satisfied with the
  results.
  
If a crypto function's output of even a plain seed sequence 0, 1, 2,
3...  does not fulfill the strictest randomness tests, then there is a
serious flaw in the crypto function!

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.  I see no reason for anything much
beyond this algorithm:

  counter = 0
  while more bits needed
    random_bits = encrypt(counter)
    append_to_result(random_bits)
    counter = counter + 1

This is CRT (aka ICM) except that the result is not applied to anything.

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

I'd suggest to keep counter fixed in size.  I'd say to keep it to just
64 bits, or surely not more than 128 bits.  I.e., not a bignum.

Seeding should probably take put the low bits and use them for the
counter variable above, then of more bits are goves generate a
non-default key.  Why not the other way around?  Because accepting a new
key can require some time (and some people like reseeding), while
updating counter it very cheap.

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?

  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.

  > But I don't think we can leave MT broken or replace it (e.g.,
  > gmp_randinit_mt should use Mersenne Twister, period).  Shouldn't it be
  > possible to get both a and b (of the reporter's code) in the precis same
  > state after assigning one to the other, without significant dependency
  > changes in the MT code?
  
  With something like the attached? Perhaps. In fact I don't know why it
  isn't doing it now. Can that structure possibly come from disk or some
  other place that makes the pointers invalid? I guess not.
  
Thanks for this patch, I'll take a look now!

-- 
Torbjörn
Please encrypt, key id 0xC8601622


More information about the gmp-bugs mailing list