Re: Problem with gmp_randinit_set

[Pedro Gimeno]

What I had in mind for the upper half, is something like this:

  gmp_uint_least32_t k[4];
  ...
  k[0] = high_bit ? 0x4BEDAF6D : 0x5443092C;
  k[1] = high_bit ? 0x674DD5FB : 0xA67C9FE2;
  k[2] = high_bit ? 0xB79D42BC : 0x31CC686A;
  k[3] = high_bit ? 0x94C371EA : 0xC41175D6;

Marco Bodrato wrote, On 2017-03-03 08:11:

> I vote for decryption in the main library, I like use of sum to detect the
> end of the loop :-)

Fine with me.
___
gmp-bugs mailing list
gmp-bugs@gmplib.org
https://gmplib.org/mailman/listinfo/gmp-bugs

Re: Problem with gmp_randinit_set

[Marco Bodrato]

Ciao,

Il Ven, 3 Marzo 2017 3:10 am, Pedro Gimeno ha scritto:
> Marco Bodrato wrote, On 2017-03-02 21:37:
> Just one comment. You're switching algorithms for the top half. Wouldn't
> it be easier to change the key (the k[] array) instead? That might also
> produce less correlation in the upper half, not sure. Obviously a

y = f(x), z = f^-1(x), implies y = f(f(z)). If f(x) is a "random"
permutation, f(f(x)) is less random; cycles with even order split in
shorter cycles. You are right.

I was lazy. But of course we do not need to use the same function for
randseed, and for the legacy_randseed, as I did in my code.
I vote for decryption in the main library, I like use of sum to detect the
end of the loop :-)

> Thanks for looking into this.

Best regards,
m

-- 
http://bodrato.it/papers/

___
gmp-bugs mailing list
gmp-bugs@gmplib.org
https://gmplib.org/mailman/listinfo/gmp-bugs

Re: Problem with gmp_randinit_set

[Pedro Gimeno]

Marco Bodrato wrote, On 2017-02-21 15:21:

> Problem: e is even!
> value and (2^n-k-value) will be mangled to the same seed...
> 

Well, these are more bugs then.

I've wanted to replace that seeding routine since it was written. I was never 
happy with it, but I didn't find a suitable replacement until 2006, and the 
idea of changing it was not very well received back then.

> Of course we can change the exponent, with a new one, co-prime with the
> Euler phi of 2^n-k... but this is an incompatible change.

As I said it's all or nothing. Either compatibility is kept, or the whole thing 
is changed to a better and faster seeding function. There's no point in trying 
to keep the spirit of the current algorithm, unless it can be shown to 
outperform the alternatives, which I seriously doubt.

>> Seeds bigger would generate different results, potentially breaking
>> compatibility if these are used, but I don't think there's a big chance of
>> that happening.
> 
> If we change the function, the sequences will be changed for any value,
> right? It's not only an issue affecting "bigger seeds"...

Right. I meant that for example, if someone used 2^19937-20026 as seed, the 
sequence obtained should be the same as using 1 as seed. But I doubt anyone is 
using seeds that large. I said it with respect to the idea of taking seed mod 
2^19936 instead of seed mod (2^19937 - 20027). The preceding sentence was:

>> I don't think it'd be a big deal to cut it out to 2^19936-1 now.

That would automatically break compatibility for seeds of 2^19936 and above. Is 
that important?

___
gmp-bugs mailing list
gmp-bugs@gmplib.org
https://gmplib.org/mailman/listinfo/gmp-bugs

Re: Problem with gmp_randinit_set

[Marco Bodrato]

Ciao,

Il Dom, 19 Febbraio 2017 9:21 am, Niels Möller ha scritto:
> But shifting, as you suggest, might be simpler, using
>
>   2 B^623 = 20023 (mod p)

A possible generalization follows:

#include 
#include 
#include 
#include 

#define GSIZE (19937 / GMP_NUMB_BITS)
#define GSHIFT (19937 % GMP_NUMB_BITS)
#define SIZE (GSIZE + 1)
#define K 20023
/* B^312 mod p */
#define B312MODP ((mp_limb_t) K << (GMP_NUMB_BITS-GSHIFT))
#define USE_NIELS_SHORTCUT (((mp_limb_t) K >> GSHIFT) == 0)

/* Reduces r modulo p in place, result is SIZE limbs (non-canonical
   representation). */
static void
reduce (mp_ptr rp, mp_size_t n)
{
  mp_limb_t cy, hi;
  assert (n > GSIZE);
  assert (GSHIFT != 0); /* 19937 is prime */

  if (USE_NIELS_SHORTCUT)
{
  if (n == SIZE)
return;

  while (n >= 2*SIZE)
{
  rp[n - SIZE] = mpn_addmul_1 (rp + n - 2*SIZE,
   rp + n - SIZE, SIZE, B312MODP);
  n -= GSIZE;
}

  cy = mpn_addmul_1 (rp, rp + SIZE, n - SIZE, B312MODP);
  if (n < 2*SIZE - 1)
cy = mpn_add_1 (rp + n - SIZE, rp + n - SIZE, 2*SIZE - n - 1, cy);
  hi = rp[GSIZE];
  rp[GSIZE] = cy + (hi & (((mp_limb_t)1 << GSHIFT) - 1))
+ mpn_add_1 (rp, rp, SIZE - 1, (hi >> GSHIFT) * K);
}
  else
{
  while (n >= 2 * GSIZE)
{
  hi = mpn_rshift (rp + n - GSIZE, rp + n - GSIZE, GSIZE, GSHIFT);
  cy = mpn_addmul_1 (rp + n - 2*GSIZE, rp + n - GSIZE, GSIZE, K);
  rp[n - GSIZE] = cy + (hi >> (GMP_NUMB_BITS - GSHIFT));
  n -= GSIZE - 1;
}

  hi = mpn_rshift (rp + GSIZE, rp + GSIZE, n - GSIZE, GSHIFT);
  cy = mpn_addmul_1 (rp, rp + GSIZE, n - GSIZE, K);
  cy = mpn_add_1 (rp + n - GSIZE, rp + n - GSIZE, 2*GSIZE - n, cy);
  rp[GSIZE] = cy + (hi >> (GMP_NUMB_BITS - GSHIFT));
}
}

int
main (int argc, char **argv)
{
  mpz_t p, x, r, ref;
  int i;
  gmp_randstate_t rands;

  mpz_inits (p, x, r, ref, NULL);
  gmp_randinit_default (rands);

  mpz_setbit (p, 19937);
  mpz_sub_ui (p, p, K);

  for (i = 0;  i < 64000; i++)
{
  mpz_urandomb (x, rands, 16);
  mpz_rrandomb (x, rands, mpz_get_ui (x) + 2);
  mpz_tdiv_r (ref, x, p);
  mpz_set (r, x);
  reduce (mpz_limbs_modify (r, mpz_size (r)), mpz_size(r));
  mpz_limbs_finish (r, SIZE);

  if (!mpz_congruent_p (r, ref, p))
{
  gmp_printf ("Failed (%i) for size %d: %Zx\n"
  " got: %Zx\n"
  " exp: %Zx\n",
  i, mpz_size (x), x, r, ref);
  exit (1);
}
}
  mpz_clears (p, x, r, ref, NULL);
  gmp_randclear(rands);
}

Best regards,
m

-- 
http://bodrato.it/

___
gmp-bugs mailing list
gmp-bugs@gmplib.org
https://gmplib.org/mailman/listinfo/gmp-bugs

Re: Problem with gmp_randinit_set

[Niels Möller]

ni...@lysator.liu.se (Niels Möller) writes:

> It shouldn't be too hard to rewrite randseed_mt to use mpn_powm, right?
> Which probably didn't exist when the original version was written. 

Or if we want to take advantage of the structure, we need an mpn
function to reduce numbers modulo 2^19937 - 20023. The input seed is of
arbitrary size, right?

How important is support for other limbsizes than 32 and 64 bits?
We'd need special code to support artificially small limbs, where 20023
doesn't fit in a limb. Perhaps it's good enough to have special code for
32 and 64 bits, and fall back to mpn_powm for other sizes. And then test
that all variants produce the same results.

Regards,
/Niels

-- 
Niels Möller. PGP-encrypted email is preferred. Keyid 368C6677.
Internet email is subject to wholesale government surveillance.
___
gmp-bugs mailing list
gmp-bugs@gmplib.org
https://gmplib.org/mailman/listinfo/gmp-bugs

Re: Problem with gmp_randinit_set

[Pedro Gimeno]

Torbjörn Granlund wrote, On 2017-02-16 23:19:
> Pedro Gimeno  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.

___
gmp-bugs mailing list
gmp-bugs@gmplib.org
https://gmplib.org/mailman/listinfo/gmp-bugs

Re: Problem with gmp_randinit_set

[Torbjörn Granlund]

Pedro Gimeno  writes:

  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.

That patch makes a lot of sense...  I'll apply it now.

Perhaps we should expand testing wrt this?

We should check that seeding is effective, that gmp_randinit_set(b, a)
make a and b behave the same including that the seed follows, and that
further seeding affects both identically.  More?


-- 
Torbjörn
Please encrypt, key id 0xC8601622
___
gmp-bugs mailing list
gmp-bugs@gmplib.org
https://gmplib.org/mailman/listinfo/gmp-bugs

Re: Problem with gmp_randinit_set

[Torbjörn Granlund]

Pedro Gimeno  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
___
gmp-bugs mailing list
gmp-bugs@gmplib.org
https://gmplib.org/mailman/listinfo/gmp-bugs

Re: Problem with gmp_randinit_set

[Pedro Gimeno]

Torbjörn Granlund wrote, On 2017-02-15 03:40:
> Pedro Gimeno  writes:
>   
>   One possible fix would be to resurrect my patch for a different
>   seeding routine, which was based on the xxtea encryption
>   [...]
>   
> I like the idea of applying a symmetric cipher for PRNG; I have in fact
> done some work towards using AES for that in GMP.  I don't know about
> xxtea or its pros and cons, and perhaps that is superior to AES.  On
> AES's plus side is that we can access hardware instructions in many
> cases, and that a C implementation is quite small.

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.

As a temporary fix, it would also work if minigmp's modular exponentiation 
could be used, to make the output compatible.

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



mt-copy-functions.diff
Description: plain/text
___
gmp-bugs mailing list
gmp-bugs@gmplib.org
https://gmplib.org/mailman/listinfo/gmp-bugs

Re: Problem with gmp_randinit_set

[Torbjörn Granlund]

Pedro Gimeno  writes:

  Ah, yes, that was a problem that needed to be avoided. Thanks for
  looking into this.
  
  One possible fix would be to resurrect my patch for a different
  seeding routine, which was based on the xxtea encryption
  algorithm. That one is faster and uses far less mpz code, and I think
  it wouldn't be difficult to get rid of mpz usage totally. It was
  written in or before 2006, I believe, and I rebased it in 2009, so
  merging it with current code might be troublesome. Fortunately, that
  part of the code doesn't seem to have changed a lot.
  
  The problem is that it wouldn't be a good idea to apply that patch to
  stable versions, because it causes the sequences to be different.
  
  I've attached the patch as it was in 2009 (against revision
  af3f365253c5).
  
I like the idea of applying a symmetric cipher for PRNG; I have in fact
done some work towards using AES for that in GMP.  I don't know about
xxtea or its pros and cons, and perhaps that is superior to AES.  On
AES's plus side is that we can access hardware instructions in many
cases, and that a C implementation is quite small.

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?

-- 
Torbjörn
Please encrypt, key id 0xC8601622
___
gmp-bugs mailing list
gmp-bugs@gmplib.org
https://gmplib.org/mailman/listinfo/gmp-bugs

Re: Problem with gmp_randinit_set

[Pedro Gimeno]

Torbjörn Granlund wrote, On 2017-02-15 00:45:
> Pedro Gimeno  writes:
> 
>   Torbjörn Granlund wrote, On 2017-02-14 01:41:
>   
>   > One can change Mersenne_Twister_Generator_Noseed to
>   > Mersenne_Twister_Generator to fix this (and move __gmp_randiset_mt to
>   > randmts.c as mandated by Mersenne_Twister_Generator's scope), and then
>   > your code supposedly runs without a crash.  But I don't see why one ever
>   > wants Mersenne_Twister_Generator_Noseed, which suggests my understanding
>   > of this code is very poor indeed.
>   
>   It's been about 15 years ago, but my recollection is that the rationale 
> behind the _Noseed version was to avoid a dependency on randmts.c, and it 
> seems I neglected to consider this use case.
>   
>   I agree with your fix.
>   
> I realised a serious flaw with that fix; it introduces a dependency from
> mpn_random* to mpz.  That's not OK, I'm afraid.

Ah, yes, that was a problem that needed to be avoided. Thanks for looking into 
this.

One possible fix would be to resurrect my patch for a different seeding 
routine, which was based on the xxtea encryption algorithm. That one is faster 
and uses far less mpz code, and I think it wouldn't be difficult to get rid of 
mpz usage totally. It was written in or before 2006, I believe, and I rebased 
it in 2009, so merging it with current code might be troublesome. Fortunately, 
that part of the code doesn't seem to have changed a lot.

The problem is that it wouldn't be a good idea to apply that patch to stable 
versions, because it causes the sequences to be different.

I've attached the patch as it was in 2009 (against revision af3f365253c5).


mt-xxtea-patch-against-13003.diff
Description: plain/text
___
gmp-bugs mailing list
gmp-bugs@gmplib.org
https://gmplib.org/mailman/listinfo/gmp-bugs

Re: Problem with gmp_randinit_set

[Torbjörn Granlund]

Pedro Gimeno  writes:

  Torbjörn Granlund wrote, On 2017-02-14 01:41:
  
  > One can change Mersenne_Twister_Generator_Noseed to
  > Mersenne_Twister_Generator to fix this (and move __gmp_randiset_mt to
  > randmts.c as mandated by Mersenne_Twister_Generator's scope), and then
  > your code supposedly runs without a crash.  But I don't see why one ever
  > wants Mersenne_Twister_Generator_Noseed, which suggests my understanding
  > of this code is very poor indeed.
  
  It's been about 15 years ago, but my recollection is that the rationale 
behind the _Noseed version was to avoid a dependency on randmts.c, and it seems 
I neglected to consider this use case.
  
  I agree with your fix.
  
I realised a serious flaw with that fix; it introduces a dependency from
mpn_random* to mpz.  That's not OK, I'm afraid.


-- 
Torbjörn
Please encrypt, key id 0xC8601622
___
gmp-bugs mailing list
gmp-bugs@gmplib.org
https://gmplib.org/mailman/listinfo/gmp-bugs

Re: Problem with gmp_randinit_set

[Pedro Gimeno]

Torbjörn Granlund wrote, On 2017-02-14 01:41:

> One can change Mersenne_Twister_Generator_Noseed to
> Mersenne_Twister_Generator to fix this (and move __gmp_randiset_mt to
> randmts.c as mandated by Mersenne_Twister_Generator's scope), and then
> your code supposedly runs without a crash.  But I don't see why one ever
> wants Mersenne_Twister_Generator_Noseed, which suggests my understanding
> of this code is very poor indeed.

It's been about 15 years ago, but my recollection is that the rationale behind 
the _Noseed version was to avoid a dependency on randmts.c, and it seems I 
neglected to consider this use case.

I agree with your fix.
___
gmp-bugs mailing list
gmp-bugs@gmplib.org
https://gmplib.org/mailman/listinfo/gmp-bugs

Re: Problem with gmp_randinit_set

[Torbjörn Granlund]

   gmp_randinit_set(b, a);
   gmp_randseed_ui(b, 123456); /* crashes */
  
  AFAICT this is a gmp bug, but I don't rule out the possibility that
  it's a user bug.
  
This looks like a GMP bug.

I never looked properly through the GMP PRNG code, and looking at it now
I don't immediately understand its structure.  (This code was written by
an external contributor.)

What happens with your code is that GMP tries to call a seed application
function through a pointer, but that pointer was explicitly zeroed by
gmp_randinit_set (or in __gmp_randiset_mt to be exact).

One can change Mersenne_Twister_Generator_Noseed to
Mersenne_Twister_Generator to fix this (and move __gmp_randiset_mt to
randmts.c as mandated by Mersenne_Twister_Generator's scope), and then
your code supposedly runs without a crash.  But I don't see why one ever
wants Mersenne_Twister_Generator_Noseed, which suggests my understanding
of this code is very poor indeed.

-- 
Torbjörn
Please encrypt, key id 0xC8601622
___
gmp-bugs mailing list
gmp-bugs@gmplib.org
https://gmplib.org/mailman/listinfo/gmp-bugs