Re: [viff-devel] VIFF and random numbers
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
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
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
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
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
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
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
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
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
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