Re: [viff-devel] VIFF and random numbers

2010-07-13 Thread Mikkel Krøigård
Of course it is also worth mentioning that this is a very quick and  
dirty implementation of BBS. I am sure you can save a lot of time by  
implementing this in a clever way.


No tricks were used except for gmpy.

Citat af Mikkel Krøigård :

By the way, I just implemented the Blum Blum Shub generator in  
Python just to see how fast it would be compared to urandom. Note  
here that urandom is significantly slower than the default Python  
PRNG, but we can't use the normal one anyway.


The BBS generator must square modulo n (product of two Blum primes)  
and then extract log log n lower-order bits from that. I picked a  
2048 bit n and extracted 10 bits per squaring.


I then generated 10 random bits a million times using urandom and BBS:

urandom: 30 seconds
BBS: 80 seconds

Not THAT bad really. This is the ideal situation for BBS though.

However, if you use for example random() instead (random float in  
[0;1) ), then you must either pool bits (which takes time) or throw  
away bits per call, because you need about 53 bits per number (I'm  
assuming they ARE double-precision, not a Python geek :) ). There I  
got:


urandom: 29 seconds
BBS: 435 seconds (not surprising, since 80*6 = 420)

This is of course horrible.

PS: There are probably better crypto-secure PRNGS out there, I just  
picked BBS because I know that one quite well.


Also, the CryptGenRandom generator in Windows is claimed to have  
been patched and fixed for Windows XP and Vista (presumably Windows  
7 too). However, it's probably not good practice to take their word  
for it :)


Citat af Thomas P Jakobsen :


I agree that tests should be reproducible. But it is also very
important to use a cryptographically secure PRNG.

I don't know whether these two requirements can be satisfied by the
same number generator. If not, the best solution is to have two
"modes" of operation:

- A test mode where the execution can be reproduced and
- a secure mode using a cryptographically secure PRNG

Regards,
Thomas




___
viff-devel mailing list (http://viff.dk/)
viff-devel@viff.dk
http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk



___
viff-devel mailing list (http://viff.dk/)
viff-devel@viff.dk
http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk


Re: [viff-devel] VIFF and random numbers

2010-07-13 Thread Mikkel Krøigård
By the way, I just implemented the Blum Blum Shub generator in Python  
just to see how fast it would be compared to urandom. Note here that  
urandom is significantly slower than the default Python PRNG, but we  
can't use the normal one anyway.


The BBS generator must square modulo n (product of two Blum primes)  
and then extract log log n lower-order bits from that. I picked a 2048  
bit n and extracted 10 bits per squaring.


I then generated 10 random bits a million times using urandom and BBS:

urandom: 30 seconds
BBS: 80 seconds

Not THAT bad really. This is the ideal situation for BBS though.

However, if you use for example random() instead (random float in  
[0;1) ), then you must either pool bits (which takes time) or throw  
away bits per call, because you need about 53 bits per number (I'm  
assuming they ARE double-precision, not a Python geek :) ). There I got:


urandom: 29 seconds
BBS: 435 seconds (not surprising, since 80*6 = 420)

This is of course horrible.

PS: There are probably better crypto-secure PRNGS out there, I just  
picked BBS because I know that one quite well.


Also, the CryptGenRandom generator in Windows is claimed to have been  
patched and fixed for Windows XP and Vista (presumably Windows 7 too).  
However, it's probably not good practice to take their word for it :)


Citat af Thomas P Jakobsen :


I agree that tests should be reproducible. But it is also very
important to use a cryptographically secure PRNG.

I don't know whether these two requirements can be satisfied by the
same number generator. If not, the best solution is to have two
"modes" of operation:

- A test mode where the execution can be reproduced and
- a secure mode using a cryptographically secure PRNG

Regards,
Thomas




___
viff-devel mailing list (http://viff.dk/)
viff-devel@viff.dk
http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk


Re: [viff-devel] VIFF and random numbers

2010-07-06 Thread Thomas P Jakobsen
I agree that tests should be reproducible. But it is also very
important to use a cryptographically secure PRNG.

I don't know whether these two requirements can be satisfied by the
same number generator. If not, the best solution is to have two
"modes" of operation:

- A test mode where the execution can be reproduced and
- a secure mode using a cryptographically secure PRNG

Regards,
Thomas
___
viff-devel mailing list (http://viff.dk/)
viff-devel@viff.dk
http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk


Re: [viff-devel] VIFF and random numbers

2010-07-06 Thread Martin Geisler
Mikkel Krøigård  writes:

Hi everybody

> Indeed it should satisfy those properties. Say if you Shamir share
> something, the adversary might get t shares in order. If it can guess
> the next bit with non-negligible advantage, this will completely break
> our claim that the adversary has no information on the secret.
>
> Luckily it should not be hard to replace. I think we knew about this
> earlier but just forgot, actually.

No, we did not forget it -- it was designed from the start with an aim
towards making tests reproducible. This is why VIFF announces the random
seed when it starts and why the seed is chosen as a small integer.

-- 
Martin Geisler

Mercurial links: http://mercurial.ch/


pgpBdiC07ULeT.pgp
Description: PGP signature
___
viff-devel mailing list (http://viff.dk/)
viff-devel@viff.dk
http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk


Re: [viff-devel] VIFF and random numbers

2010-07-06 Thread Martin Geisler
Marcel Keller  writes:

> Thomas P Jakobsen wrote:
>
>> If not, I guess we'll have to use some external package (openssl?) or
>> implement our own algorithm.
>
> viff.util.rand is used to make all randomness replayable, which
> already helped me to find bugs triggered by certain randomness. I
> would like to have this feature also in the future, therefore I would
> vote against a random number generator using noise not only to
> generate a seed.

Right, but note that the seed is not enough to ensure deterministic
output because of jitter in the network.

> If the environment variable VIFF_SEED is set to the empty string, VIFF
> already uses /dev/urandom by using random.SystemRandom for random
> number generation. This possibility is not documented however.

It's documented in the final paragraph here:

  http://viff.dk/doc/util.html#viff.util.rand

I will of course agree that it could be made more explicit :-)

-- 
Martin Geisler

Mercurial links: http://mercurial.ch/


pgpEQ0pxZDe3R.pgp
Description: PGP signature
___
viff-devel mailing list (http://viff.dk/)
viff-devel@viff.dk
http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk


Re: [viff-devel] VIFF and random numbers

2010-07-06 Thread Marcel Keller

Thomas P Jakobsen wrote:

The urandom is os-specific:

"This function returns random bytes from an OS-specific randomness
source. The returned data should be unpredictable enough for
cryptographic applications, though its exact quality depends on the OS
implementation. On a UNIX-like system this will query /dev/urandom,
and on Windows it will use CryptGenRandom."

I don't know whether this will be good enough.


There is a paper describing various flaws:
http://www.pinkas.net/PAPERS/gpr06.pdf


If not, I guess we'll
have to use some external package (openssl?)  or implement our own
algorithm.


viff.util.rand is used to make all randomness replayable, which already
helped me to find bugs triggered by certain randomness. I would like to
have this feature also in the future, therefore I would vote against a
random number generator using noise not only to generate a seed.

If the environment variable VIFF_SEED is set to the empty string, VIFF
already uses /dev/urandom by using random.SystemRandom for random number
generation. This possibility is not documented however.

Best regards,
Marcel



On Tue, Jul 6, 2010 at 15:40, Ivan Bjerre Damgård  wrote:

It is not good to use the wrong kind of PRG, it should
be fixed as soon as possible. But do we know that
os.urandom will be OK on any platform, or is this
OS -dependent at the end of the day?

- Ivan

On 06/07/2010, at 15.22, Thomas P Jakobsen wrote:


VIFF itself as well as most protocols implemented in VIFF uses the
viff.util package for random number generation. This package in turn
uses the random package in the Python standard library. This means
that random numbers are generated using a Mersenne twister.

As far as I can see, this is a problem, since Mersenne twister PRNGs
are generally not suited for cryptographic usage. E.g. it is not known
to pass the "next-bit test" and withstand the "state compromise
extensions", see
http://en.wikipedia.org/wiki/Cryptographically_secure_pseudorandom_number_generator.

One solution would be to use the os.urandom() function instead. This
has specifically been designed to produce cryptographically secure
random numbers.

(We should probably keep the old random generator, too. It is probably
faster and not all random numbers used in VIFF and VIFF programs need
to be cryptographically secure.)


Let me know what you think about this.

Kind regards,
Thomas
___
viff-devel mailing list (http://viff.dk/)
viff-devel@viff.dk
http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk



___
viff-devel mailing list (http://viff.dk/)
viff-devel@viff.dk
http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk



___
viff-devel mailing list (http://viff.dk/)
viff-devel@viff.dk
http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk


Re: [viff-devel] VIFF and random numbers

2010-07-06 Thread Mikkel Krøigård

I had not seen the later replies before answering. My apologies.

The way I've always understood urandom is exactly that. It's  
"probably" unpredictable but there's no actual proof of this, like  
there would be if you used for example Blum Blum Shub.


I'm sure there are multiple implementations of cryptographically  
secure PRNGs floating around. I think I even have one in Java. I  
suspect they are much slower than urandom though.


Citat af Thomas P Jakobsen :


The urandom is os-specific:

"This function returns random bytes from an OS-specific randomness
source. The returned data should be unpredictable enough for
cryptographic applications, though its exact quality depends on the OS
implementation. On a UNIX-like system this will query /dev/urandom,
and on Windows it will use CryptGenRandom."

I don't know whether this will be good enough. If not, I guess we'll
have to use some external package (openssl?)  or implement our own
algorithm.

Regards,
Thomas



On Tue, Jul 6, 2010 at 15:40, Ivan Bjerre Damgård  wrote:

It is not good to use the wrong kind of PRG, it should
be fixed as soon as possible. But do we know that
os.urandom will be OK on any platform, or is this
OS -dependent at the end of the day?

- Ivan

On 06/07/2010, at 15.22, Thomas P Jakobsen wrote:


VIFF itself as well as most protocols implemented in VIFF uses the
viff.util package for random number generation. This package in turn
uses the random package in the Python standard library. This means
that random numbers are generated using a Mersenne twister.

As far as I can see, this is a problem, since Mersenne twister PRNGs
are generally not suited for cryptographic usage. E.g. it is not known
to pass the "next-bit test" and withstand the "state compromise
extensions", see
http://en.wikipedia.org/wiki/Cryptographically_secure_pseudorandom_number_generator.

One solution would be to use the os.urandom() function instead. This
has specifically been designed to produce cryptographically secure
random numbers.

(We should probably keep the old random generator, too. It is probably
faster and not all random numbers used in VIFF and VIFF programs need
to be cryptographically secure.)


Let me know what you think about this.

Kind regards,
Thomas
___
viff-devel mailing list (http://viff.dk/)
viff-devel@viff.dk
http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk




___
viff-devel mailing list (http://viff.dk/)
viff-devel@viff.dk
http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk



___
viff-devel mailing list (http://viff.dk/)
viff-devel@viff.dk
http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk


Re: [viff-devel] VIFF and random numbers

2010-07-06 Thread Mikkel Krøigård
Indeed it should satisfy those properties. Say if you Shamir share  
something, the adversary might get t shares in order. If it can guess  
the next bit with non-negligible advantage, this will completely break  
our claim that the adversary has no information on the secret.


Luckily it should not be hard to replace. I think we knew about this  
earlier but just forgot, actually.


By the way, I am not sure we use any random numbers that should NOT  
secure in this way.


Citat af Thomas P Jakobsen :


VIFF itself as well as most protocols implemented in VIFF uses the
viff.util package for random number generation. This package in turn
uses the random package in the Python standard library. This means
that random numbers are generated using a Mersenne twister.

As far as I can see, this is a problem, since Mersenne twister PRNGs
are generally not suited for cryptographic usage. E.g. it is not known
to pass the "next-bit test" and withstand the "state compromise
extensions", see
http://en.wikipedia.org/wiki/Cryptographically_secure_pseudorandom_number_generator.

One solution would be to use the os.urandom() function instead. This
has specifically been designed to produce cryptographically secure
random numbers.

(We should probably keep the old random generator, too. It is probably
faster and not all random numbers used in VIFF and VIFF programs need
to be cryptographically secure.)


Let me know what you think about this.

Kind regards,
Thomas
___
viff-devel mailing list (http://viff.dk/)
viff-devel@viff.dk
http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk




___
viff-devel mailing list (http://viff.dk/)
viff-devel@viff.dk
http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk


Re: [viff-devel] VIFF and random numbers

2010-07-06 Thread Thomas P Jakobsen
The urandom is os-specific:

"This function returns random bytes from an OS-specific randomness
source. The returned data should be unpredictable enough for
cryptographic applications, though its exact quality depends on the OS
implementation. On a UNIX-like system this will query /dev/urandom,
and on Windows it will use CryptGenRandom."

I don't know whether this will be good enough. If not, I guess we'll
have to use some external package (openssl?)  or implement our own
algorithm.

Regards,
Thomas



On Tue, Jul 6, 2010 at 15:40, Ivan Bjerre Damgård  wrote:
> It is not good to use the wrong kind of PRG, it should
> be fixed as soon as possible. But do we know that
> os.urandom will be OK on any platform, or is this
> OS -dependent at the end of the day?
>
> - Ivan
>
> On 06/07/2010, at 15.22, Thomas P Jakobsen wrote:
>
>> VIFF itself as well as most protocols implemented in VIFF uses the
>> viff.util package for random number generation. This package in turn
>> uses the random package in the Python standard library. This means
>> that random numbers are generated using a Mersenne twister.
>>
>> As far as I can see, this is a problem, since Mersenne twister PRNGs
>> are generally not suited for cryptographic usage. E.g. it is not known
>> to pass the "next-bit test" and withstand the "state compromise
>> extensions", see
>> http://en.wikipedia.org/wiki/Cryptographically_secure_pseudorandom_number_generator.
>>
>> One solution would be to use the os.urandom() function instead. This
>> has specifically been designed to produce cryptographically secure
>> random numbers.
>>
>> (We should probably keep the old random generator, too. It is probably
>> faster and not all random numbers used in VIFF and VIFF programs need
>> to be cryptographically secure.)
>>
>>
>> Let me know what you think about this.
>>
>> Kind regards,
>> Thomas
>> ___
>> viff-devel mailing list (http://viff.dk/)
>> viff-devel@viff.dk
>> http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk
>
>
___
viff-devel mailing list (http://viff.dk/)
viff-devel@viff.dk
http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk


Re: [viff-devel] VIFF and random numbers

2010-07-06 Thread Ivan Bjerre Damgård
It is not good to use the wrong kind of PRG, it should
be fixed as soon as possible. But do we know that 
os.urandom will be OK on any platform, or is this
OS -dependent at the end of the day?

- Ivan

On 06/07/2010, at 15.22, Thomas P Jakobsen wrote:

> VIFF itself as well as most protocols implemented in VIFF uses the
> viff.util package for random number generation. This package in turn
> uses the random package in the Python standard library. This means
> that random numbers are generated using a Mersenne twister.
> 
> As far as I can see, this is a problem, since Mersenne twister PRNGs
> are generally not suited for cryptographic usage. E.g. it is not known
> to pass the "next-bit test" and withstand the "state compromise
> extensions", see
> http://en.wikipedia.org/wiki/Cryptographically_secure_pseudorandom_number_generator.
> 
> One solution would be to use the os.urandom() function instead. This
> has specifically been designed to produce cryptographically secure
> random numbers.
> 
> (We should probably keep the old random generator, too. It is probably
> faster and not all random numbers used in VIFF and VIFF programs need
> to be cryptographically secure.)
> 
> 
> Let me know what you think about this.
> 
> Kind regards,
> Thomas
> ___
> viff-devel mailing list (http://viff.dk/)
> viff-devel@viff.dk
> http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk

___
viff-devel mailing list (http://viff.dk/)
viff-devel@viff.dk
http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk