Re: [cryptography] Homomorphic split-key encryption OR snake oil crypto
* Saqib Ali: Can somebody explain me how this so-called Homomorphic split-key encryption works? Isn't this just a protocal which performs a cryptographic primitive using split key material, without actually recombining the keys? (Traditional Shamir secret sharing needs a trust party for key recombination.) If yes, you might want to look for RSA Threshold Cryptography and similar work. ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] Homomorphic split-key encryption OR snake oil crypto
On Sun, Feb 19, 2012 at 10:08 AM, Florian Weimer f...@deneb.enyo.de wrote: * Saqib Ali: Can somebody explain me how this so-called Homomorphic split-key encryption works? Isn't this just a protocal which performs a cryptographic primitive using split key material, without actually recombining the keys? (Traditional Shamir secret sharing needs a trust party for key recombination.) The key part is the homomorphism. ISTR this from a few years ago, and I see wikipedia has an OK article on the subject: http://en.wikipedia.org/wiki/Homomorphic_encryption#Fully_homomorphic_encryption The idea is that you could even write an entire program this way, which allows you to run it on untrusted systems without leaking the program or data to those systems. It seems unlikely to get deployed anytime soon. Nico -- ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] Homomorphic split-key encryption OR snake oil crypto
I don't see why you'd want split keys when it's already homomorphic. What would be the additional gain of that? Unless they need half the key to do the homomorphic computations. Also, homomorphic encryption and computation is usually slow. VERY slow. On Sun, Feb 19, 2012 at 17:22, Nico Williams n...@cryptonector.com wrote: On Sun, Feb 19, 2012 at 10:08 AM, Florian Weimer f...@deneb.enyo.de wrote: * Saqib Ali: Can somebody explain me how this so-called Homomorphic split-key encryption works? Isn't this just a protocal which performs a cryptographic primitive using split key material, without actually recombining the keys? (Traditional Shamir secret sharing needs a trust party for key recombination.) The key part is the homomorphism. ISTR this from a few years ago, and I see wikipedia has an OK article on the subject: http://en.wikipedia.org/wiki/Homomorphic_encryption#Fully_homomorphic_encryption The idea is that you could even write an entire program this way, which allows you to run it on untrusted systems without leaking the program or data to those systems. It seems unlikely to get deployed anytime soon. Nico -- ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] Homomorphic split-key encryption OR snake oil crypto
On Sun, 19 Feb 2012 17:08:25 +0100 Florian Weimer f...@deneb.enyo.de wrote: * Saqib Ali: Can somebody explain me how this so-called Homomorphic split-key encryption works? Isn't this just a protocal which performs a cryptographic primitive using split key material, without actually recombining the keys? (Traditional Shamir secret sharing needs a trust party for key recombination.) If yes, you might want to look for RSA Threshold Cryptography and similar work. What is the point of introducing homomorphic encryption here? When last I checked, we were still pretty far from practical FHE systems, and we have not really determined the appropriate security parameters for the systems we are aware of now. It is telling that the company in the link provides few details about their system, except so say that homomorphic encryption is something they plan to deploy in the future. Maybe they are talking about oblivious AES from garbled circuits, although I am not really sure what the advantage of such a thing might be. -- Ben -- Benjamin R Kreuter UVA Computer Science brk...@virginia.edu KK4FJZ -- If large numbers of people are interested in freedom of speech, there will be freedom of speech, even if the law forbids it; if public opinion is sluggish, inconvenient minorities will be persecuted, even if laws exist to protect them. - George Orwell signature.asc Description: PGP signature ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] Homomorphic split-key encryption OR snake oil crypto
Hi Florian, If the system involves split key / shared secrets (m of n), then it wouldn't be a homomorphic system. Would it? Saqib On Sun, Feb 19, 2012 at 8:08 AM, Florian Weimer f...@deneb.enyo.de wrote: * Saqib Ali: Can somebody explain me how this so-called Homomorphic split-key encryption works? Isn't this just a protocal which performs a cryptographic primitive using split key material, without actually recombining the keys? (Traditional Shamir secret sharing needs a trust party for key recombination.) If yes, you might want to look for RSA Threshold Cryptography and similar work. ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] Duplicate primes in lots of RSA moduli
Ben Laurie wrote: On Fri, Feb 17, 2012 at 8:39 PM, Thierry Moreau thierry.mor...@connotech.com wrote: Ben Laurie wrote: On Fri, Feb 17, 2012 at 7:32 PM, Thierry Moreau thierry.mor...@connotech.com wrote: Isn't /dev/urandom BY DEFINITION of limited true entropy? $ ls -l /dev/urandom lrwxr-xr-x 1 root wheel 6 Nov 20 18:49 /dev/urandom - random The above is the specific instance on your environment. Mine is different: different kernel major/minor device numbers for /dev/urandom and /dev/random. So? Your claim was Isn't /dev/urandom BY DEFINITION of limited true entropy? My response is: no. I got the definition from man 4 random If your /dev/urandom never blocks the requesting task irrespective of the random bytes usage, then maybe your /dev/random is not as secure as it might be (unless you have an high speed entropy source, but what is high speed in this context?) Oh, please. Once you have 256 bits of good entropy, that's all you need. First, about the definition, from man 4 random: quote A read from the /dev/urandom device will not block waiting for more entropy. As a result, if there is not sufficient entropy in the entropy pool, the returned values are theoretically vulnerable to a cryptographic attack on the algorithms used by the driver. Knowledge of how to do this is not available in the current non-classified literature, but it is theoretically possible that such an attack may exist. If this is a concern in your application, use /dev/random instead. /quote If the RSA modulus GCD findings is not a cryptographic attack, I don't know what is. (OK, it's not published as an attack on the *algorithm*, but please note the fact that /dev/urandom cryptographic weakness may be at stake according to other comments in the current discussion.) Second, about sufficiency of 256 bits of good entropy, the problem lies with good entropy: it is not testable by software because entropy quality depends on the process by which truly random data is collected and the software can not assess its own environment (at least for the Linux kernel which is meant to be adapted/customized/built for highly diversified environment). Third, since good entropy turns out to become someone's confidence in the true random data collection process, you may well have your own confidence. In conclusion, I am personally concerned that some operational mishaps made some RSA keys generated with /dev/urandom in environments where I depend on RSA security. And yes, my concern is rooted in the /dev/urandom definition as quoted above. If I am wrong in this logical inference (i.e. the RSA modulus GCD findings could be traced to other root cause than limited entropy of /dev/urandom), then I admittedly have to revise my understanding. Regards, -- - Thierry Moreau CONNOTECH Experts-conseils inc. 9130 Place de Montgolfier Montreal, QC, Canada H2M 2A1 Tel. +1-514-385-5691 ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] Duplicate primes in lots of RSA moduli
On Sun, Feb 19, 2012 at 5:39 PM, Thierry Moreau thierry.mor...@connotech.com wrote: Ben Laurie wrote: On Fri, Feb 17, 2012 at 8:39 PM, Thierry Moreau thierry.mor...@connotech.com wrote: Ben Laurie wrote: On Fri, Feb 17, 2012 at 7:32 PM, Thierry Moreau thierry.mor...@connotech.com wrote: Isn't /dev/urandom BY DEFINITION of limited true entropy? $ ls -l /dev/urandom lrwxr-xr-x 1 root wheel 6 Nov 20 18:49 /dev/urandom - random The above is the specific instance on your environment. Mine is different: different kernel major/minor device numbers for /dev/urandom and /dev/random. So? Your claim was Isn't /dev/urandom BY DEFINITION of limited true entropy? My response is: no. I got the definition from man 4 random If your /dev/urandom never blocks the requesting task irrespective of the random bytes usage, then maybe your /dev/random is not as secure as it might be (unless you have an high speed entropy source, but what is high speed in this context?) Oh, please. Once you have 256 bits of good entropy, that's all you need. First, about the definition, from man 4 random: quote A read from the /dev/urandom device will not block waiting for more entropy. As a result, if there is not sufficient entropy in the entropy pool, the returned values are theoretically vulnerable to a cryptographic attack on the algorithms used by the driver. Knowledge of how to do this is not available in the current non-classified literature, but it is theoretically possible that such an attack may exist. If this is a concern in your application, use /dev/random instead. /quote That's what your man 4 random says, it's not what mine says. If the RSA modulus GCD findings is not a cryptographic attack, I don't know what is. (OK, it's not published as an attack on the *algorithm*, but please note the fact that /dev/urandom cryptographic weakness may be at stake according to other comments in the current discussion.) I am not suggesting that the problems found are not caused by some implementation of /dev/urandom. My point is simply that urandom is not _defined_ to be weak. Second, about sufficiency of 256 bits of good entropy, the problem lies with good entropy: it is not testable by software because entropy quality depends on the process by which truly random data is collected and the software can not assess its own environment (at least for the Linux kernel which is meant to be adapted/customized/built for highly diversified environment). Third, since good entropy turns out to become someone's confidence in the true random data collection process, you may well have your own confidence. In conclusion, I am personally concerned that some operational mishaps made some RSA keys generated with /dev/urandom in environments where I depend on RSA security. And yes, my concern is rooted in the /dev/urandom definition as quoted above. If I am wrong in this logical inference (i.e. the RSA modulus GCD findings could be traced to other root cause than limited entropy of /dev/urandom), then I admittedly have to revise my understanding. As I have pointed out, some systems choose to make urandom the same as random. Would they suffer from the same problem, given the same environment? I think it would be useful to know. In any case, I think the design of urandom in Linux is flawed and should be fixed. ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] Homomorphic split-key encryption OR snake oil crypto
* Saqib Ali: If the system involves split key / shared secrets (m of n), then it wouldn't be a homomorphic system. Would it? I think the homomorphic part alludes to the fact that full reconstruction of the entire key is not needed to perform the cryptographic operation. In essence, I suspect it's a misnomer. We'd need a protocol description, not an interview, to be sure. ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] Homomorphic split-key encryption OR snake oil crypto
Florian, That's what I suspected as well. Unfortunately, it appears that Porticor's homomorphic split-key system is a closed one, so we may never see the details. But I think they are using the word Homomorphic to mislead people. Saqib On Sun, Feb 19, 2012 at 9:58 AM, Florian Weimer f...@deneb.enyo.de wrote: * Saqib Ali: If the system involves split key / shared secrets (m of n), then it wouldn't be a homomorphic system. Would it? I think the homomorphic part alludes to the fact that full reconstruction of the entire key is not needed to perform the cryptographic operation. In essence, I suspect it's a misnomer. We'd need a protocol description, not an interview, to be sure. ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] Homomorphic split-key encryption OR snake oil crypto
On 2012-02-20 2:08 AM, Florian Weimer wrote: Can somebody explain me how this so-called Homomorphic split-key encryption works? Homomorphic means you combine the keys without finding out the key that you are combining - Everyone gives you an encrypted copy of their key fragment, and when you are done, you have an encrypted copy of the combined key. Isn't this just a protocal which performs a cryptographic primitive using split key material, without actually recombining the keys? (Traditional Shamir secret sharing needs a trust party for key recombination.) If yes, you might want to look for RSA Threshold Cryptography and similar work. My understanding is that RSA Threshold always requires a trusted party, which makes it useless. If you have a party that is actually trusted, just let him count the votes or whatever. The cryptography does not do you any good. The only protocol that I am aware of that performs cryptographic operations on a split key with needing a trusted party, uses Gap Diffie Hellman groups. All known Gap Diffie Hellman Groups consist of an elliptic curve which supports a bilinear pairing from the curve to integers modulo some large prime. ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] Homomorphic split-key encryption OR snake oil crypto
There are multiparty computation too, but that's a bit different since it's essentially an encrypted VM where everybody runs one part. It could do the same thing without a snigle trusted party, though. On Sun, Feb 19, 2012 at 22:34, James A. Donald jam...@echeque.com wrote: On 2012-02-20 2:08 AM, Florian Weimer wrote: Can somebody explain me how this so-called Homomorphic split-key encryption works? Homomorphic means you combine the keys without finding out the key that you are combining - Everyone gives you an encrypted copy of their key fragment, and when you are done, you have an encrypted copy of the combined key. Isn't this just a protocal which performs a cryptographic primitive using split key material, without actually recombining the keys? (Traditional Shamir secret sharing needs a trust party for key recombination.) If yes, you might want to look for RSA Threshold Cryptography and similar work. My understanding is that RSA Threshold always requires a trusted party, which makes it useless. If you have a party that is actually trusted, just let him count the votes or whatever. The cryptography does not do you any good. The only protocol that I am aware of that performs cryptographic operations on a split key with needing a trusted party, uses Gap Diffie Hellman groups. All known Gap Diffie Hellman Groups consist of an elliptic curve which supports a bilinear pairing from the curve to integers modulo some large prime. __**_ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/**mailman/listinfo/cryptographyhttp://lists.randombit.net/mailman/listinfo/cryptography ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] Homomorphic split-key encryption OR snake oil crypto
On 2012-02-20 7:55 AM, Ali, Saqib wrote: Hi James, I am still not sure why you need homomorphism in this case. What is the benefit of using homomorphism to porticor's customer, for example? With RSA split keys, you need a trusted party to combine them - but if the trusted party is untrustworthy, you are hosed. Presumably, with homomorphic encryption, the trusted party would perform the operations, but not have access to the combined key. But I don't think this helps. It is a way of getting around the trusted party problem, but I don't think it does get around the trusted party problem. ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] Homomorphic split-key encryption OR snake oil crypto
Hi James, Exactly. True Homomorphism (or a fully Homomorphic system) does not require the hosting party to have any knowledge of the key, but still facilitates computational functions on the data without the need for decrypting the data. Having homomorphism is a split key / shared secret (m of n principle) doesn't make any sense. Saqib On Sun, Feb 19, 2012 at 4:26 PM, James A. Donald jam...@echeque.com wrote: On 2012-02-20 7:55 AM, Ali, Saqib wrote: Hi James, I am still not sure why you need homomorphism in this case. What is the benefit of using homomorphism to porticor's customer, for example? With RSA split keys, you need a trusted party to combine them - but if the trusted party is untrustworthy, you are hosed. Presumably, with homomorphic encryption, the trusted party would perform the operations, but not have access to the combined key. But I don't think this helps. It is a way of getting around the trusted party problem, but I don't think it does get around the trusted party problem. ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] Homomorphic split-key encryption OR snake oil crypto
My guess is that since fully homomorphic systems will be very slow that one could use it to guard just a tiny secret. But what's the point? Who cares if you can protect the customer's keys, if you can't protect the customer's plaintext data? Nico -- ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
[cryptography] Combined cipher modes
Hi list, This should be a pretty simple question for this list, so please pardon my ignorance. But better to ask than to continue in ignorance. :-) NIST refers to combined cipher modes as those supporting *both* authenticity and confidentiality, such as GCM and CCM. So my first question: Are there ANY combined cipher modes for block ciphers that do not cause the ciphers to act as a key stream? (That seems to be cause most of the ones I found build the confidentiality piece around CTR mode.) If yes, please name a few (especially those with no patent restrictions). I know when you have a cipher that acts in a streaming mode, that you need to be careful to use a unique IV for every encryption performed with the same key. So my second question is, if all the combined cipher modes all cause a cipher to act as if it is in a streaming mode, is it okay to just choose a completely RANDOM IV for each encryption? Because it sure doesn't seem to be feasible to record all the IVs for a given key to make sure that an IV isn't reused. If that is not acceptable, then how does one ever address this? Thanks, -kevin -- Blog: http://off-the-wall-security.blogspot.com/ The most likely way for the world to be destroyed, most experts agree, is by accident. That's where we come in; we're computer professionals. We *cause* accidents. -- Nathaniel Borenstein ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] Combined cipher modes
[Kevin W. Wall kevin.w.w...@gmail.com (2012-02-20 07:11:52 UTC)] So my second question is, if all the combined cipher modes all cause a cipher to act as if it is in a streaming mode, is it okay to just choose a completely RANDOM IV for each encryption? I'll bite on this one, leaving the harder part of your question to the real experts. Yes, that should be okay, PROVIDED you have access to a good source of entropy (aka randomness). See the long, long thread on duplicate primes in RSA moduli to get a notion of how horribly wrong things can go if you don't. - Harald ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
