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
Re: [viff-devel] Value overflow in Toft07
Dear Lars, thanks for pointing it out. It is now fixed in the official repository. Best regards, Marcel Lars Krapf wrote: Hello VIFF-team I would like to suggest the following patch to viff/comparison.py: 159c159 < l = int(self.options.security_parameter + math.log(dst_field.modulus, 2)) --- > l = self.options.security_parameter + math.log(dst_field.modulus, 2) otherwise the l in the next line: this_mask = rand.randint(0, (2**l) -1) is a float, and we get "34, Value out of Range" exceptions for big l. Best greetings Lars Krapf ___ 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] VIFF and random numbers
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] Value overflow in Toft07
Hello VIFF-team I would like to suggest the following patch to viff/comparison.py: 159c159 < l = int(self.options.security_parameter + math.log(dst_field.modulus, 2)) --- > l = self.options.security_parameter + math.log(dst_field.modulus, 2) otherwise the l in the next line: this_mask = rand.randint(0, (2**l) -1) is a float, and we get "34, Value out of Range" exceptions for big l. Best greetings Lars Krapf ___ viff-devel mailing list (http://viff.dk/) viff-devel@viff.dk http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk
[viff-devel] Fairplay --> VIFF compiler
Hi all, In the CACE project (http://www.cace-project.eu) we've just created a compiler that can translate MPC programs written for FairplayMP to VIFF programs. VIFF and Fairplay each have their benefits. If you write your MPC program in the Fairplay language, you can now freely decide which MPC engine you want to use to execute the program. Note that the compiler is not complete yet. There are still some performance issues and parts of the Fairplay language, SFDL, is not yet supported. The project is open source and you can find it at http://bitbucket.org/aicis/fairplay2viff Also, you can try out the compiler at http://smpc09.cs.au.dk:9091 For details on FairplayMP, see http://www.cs.huji.ac.il/project/Fairplay/fairplayMP.html Have a nice summer! Best regards, Thomas ___ viff-devel mailing list (http://viff.dk/) viff-devel@viff.dk http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk
