Re: safety of Pohlig-Hellman with a common modulus?
David Wagner wrote: > Peter Fairbrother wrote: >> Not usually. In general index calculus attacks don't work on P-H, [...] > > Sure they do. If I have a known plaintext pair (M,C), where > C = M^k (mod p), then with two discrete log computations I can > compute k, since k = dlog_g(C)/dlog_g(M) (mod p-1). This works for > any generator g, so I can do the precomputation for any g I like. Duuuh. I _knew_ that. I've even proposed changing p from time to time to limit the take from an IC attack. Dumb of me. Too much beer, no coffee, got a brainstorm and couldn't see the wood for the trees... Sorry. -- Peter Fairbrother - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: safety of Pohlig-Hellman with a common modulus?
- Original Message - From: "Peter Fairbrother" <[EMAIL PROTECTED]> To: "David Wagner" <[EMAIL PROTECTED]>; <[EMAIL PROTECTED]> Sent: Saturday, December 06, 2003 7:58 PM Subject: Re: safety of Pohlig-Hellman with a common modulus? > David Wagner wrote: > > > Steve Bellovin wrote: > >> Is it safe to use Pohlig-Hellman encryption with a common modulus? > >> That is, I want various parties to have their own exponents, but share > >> the same prime modulus. In my application, a chosen plaintext attack > >> will be possible. (I know that RSA with common modulus is not safe.) > > > > Yes, I believe so. The security of Pohlig-Hellman rests on the difficulty > > of the discrete log problem. > > Nope. In P-H there is no g. A ciphertext is M^k mod p. An attacker won't > know k, and usually won't know M, but see below. I don't know what the > problem is called, but it isn't DLP. Anyone? If you don`t know M and k, there are several values M', k' such that M'^k' mod p == M^k mod p. For example, if M is a generator of the group mod p, than all other generators M' will have a corresponding k' that will give you this value. Think about known plaintext attack or chosen plaintext attack. A symmetric cipher should be secure against these attacks and much more... In these attacks you know the bases of several values... --Anton - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: safety of Pohlig-Hellman with a common modulus?
Peter Fairbrother wrote: >Nope. In P-H there is no g. A ciphertext is M^k mod p. An attacker won't >know k, and usually won't know M, but see below. I don't know what the >problem is called, but it isn't DLP. Anyone? Ok, I was being slightly loose. To be more precise, the security of Pohlig-Hellman is based on the Decision Diffie-Hellman (DDH) problem, I believe. But the best known attack on DDH (when you're working in a prime-order subgroup) is to compute discrete logs. >Not usually. In general index calculus attacks don't work on P-H, [...] Sure they do. If I have a known plaintext pair (M,C), where C = M^k (mod p), then with two discrete log computations I can compute k, since k = dlog_g(C)/dlog_g(M) (mod p-1). This works for any generator g, so I can do the precomputation for any g I like. >When using P-H I usually pre-encrypt data in any old symmetric cipher with a >random IV and any old key, to avoid known plaintext attacks. Ok, that sounds like it should work. To break the composed scheme, one would need to break both P-H and the other symmetric cipher. - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: safety of Pohlig-Hellman with a common modulus?
David Wagner wrote: > Steve Bellovin wrote: >> Is it safe to use Pohlig-Hellman encryption with a common modulus? >> That is, I want various parties to have their own exponents, but share >> the same prime modulus. In my application, a chosen plaintext attack >> will be possible. (I know that RSA with common modulus is not safe.) > > Yes, I believe so. The security of Pohlig-Hellman rests on the difficulty > of the discrete log problem. Nope. In P-H there is no g. A ciphertext is M^k mod p. An attacker won't know k, and usually won't know M, but see below. I don't know what the problem is called, but it isn't DLP. Anyone? > Knowing the discrete log of g^y doesn't help > me learn the discrete log of g^x (assuming x,y are picked independently). > This is not like RSA, where using a common modulus allows devastating > attacks. > > There is a small caveat, but it is pretty minor. There are some > precomputation attacks one can do which depend only on the prime p; after > a long precomputation, one can compute discrete logs mod p fairly quickly. > The more people who use the same modulus, the more attractive such a > precomputation effort will be. So the only reason (that I know of) > for using different modulii with Pohlig-Hellman is to avoid putting all > your eggs in one basket. Not usually. In general index calculus attacks don't work on P-H, except in chosen plaintext attacks (where the chosen plaintext sort-of substitutes for g). When using P-H I usually pre-encrypt data in any old symmetric cipher with a random IV and any old key, to avoid known plaintext attacks. There are several other attacks to be aware of, including some nasty adaptive-chosen-plaintext and chosen-ciphertext attacks. -- Peter Fairbrother - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: safety of Pohlig-Hellman with a common modulus?
| Is it safe to use Pohlig-Hellman encryption with a common modulus? | That is, I want various parties to have their own exponents, but share | the same prime modulus. In my application, a chosen plaintext attack | will be possible. (I know that RSA with common modulus is not safe.) The question seems equivalent to: Is P-H with a *known* modulus safe? The only difference, from the point of view of an attacker, is that with a shared modulus, he gets to see a whole bunch of values X^e_i mod P, including (if he is a member of the system) some where he knows X and e. But with a known modulus, he can easily generate as many of these as he likes. The safety of P-H had better depend on the difficulty of solving the discrete log problem mod P, not on keeping P secret. (Keeping P secret would require great care in the protocol, in particular in how you respond to messages that are greater than P. Otherwise, an attacker can guess the rough size of P - based on the maximum sizes of messages he observes - and then try to do a binary division by sending messages of differing sizes.) The situation is different in RSA since there are *two* secrets: The factorization of N, and the correspondence between public and private keys. These secrets are so closely related that revealing one reveals the other as well. We usually only consider the implication "factoring N lets you get the private key from the public", but the other one is present as well. Giving someone a public/private key pair for a given N is *not* zero knowledge! -- Jerry - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: safety of Pohlig-Hellman with a common modulus?
Steve Bellovin wrote: >Is it safe to use Pohlig-Hellman encryption with a common modulus? >That is, I want various parties to have their own exponents, but share >the same prime modulus. In my application, a chosen plaintext attack >will be possible. (I know that RSA with common modulus is not safe.) Yes, I believe so. The security of Pohlig-Hellman rests on the difficulty of the discrete log problem. Knowing the discrete log of g^y doesn't help me learn the discrete log of g^x (assuming x,y are picked independently). This is not like RSA, where using a common modulus allows devastating attacks. There is a small caveat, but it is pretty minor. There are some precomputation attacks one can do which depend only on the prime p; after a long precomputation, one can compute discrete logs mod p fairly quickly. The more people who use the same modulus, the more attractive such a precomputation effort will be. So the only reason (that I know of) for using different modulii with Pohlig-Hellman is to avoid putting all your eggs in one basket. - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: safety of Pohlig-Hellman with a common modulus?
I wrote: Steve Bellovin wrote: > Is it safe to use Pohlig-Hellman encryption with a common modulus? > That is, I want various parties to have their own exponents, but share > the same prime modulus. In my application, a chosen plaintext attack > will be possible. (I know that RSA with common modulus is not safe.) > > --Steve Bellovin, http://www.research.att.com/~smb As far as I can tell it's safe - the main danger is that it that if an attacker does the work to calculate the factor base for an index calculus attack, the factor base is useful for attacking all ciphertext which uses the modulus. It's fairly easy to find an individual discreet log with a factor base, so such an attacker would get a bigger return on investment. Sorry, the above is complete nonsense, and only applies in a few situations. There are some chosen plaintext attacks, and especially adaptive chosen plaintext attacks, but they apply whether or not the modulus is shared. But P-H with a shared modulus is pretty much as safe as with different moduli, afaict. - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: safety of Pohlig-Hellman with a common modulus?
Steve Bellovin wrote: > Is it safe to use Pohlig-Hellman encryption with a common modulus? > That is, I want various parties to have their own exponents, but share > the same prime modulus. In my application, a chosen plaintext attack > will be possible. (I know that RSA with common modulus is not safe.) > > --Steve Bellovin, http://www.research.att.com/~smb As far as I can tell it's safe - the main danger is that it that if an attacker does the work to calculate the factor base for an index calculus attack, the factor base is useful for attacking all ciphertext which uses the modulus. It's fairly easy to find an individual discreet log with a factor base, so such an attacker would get a bigger return on investment. Two simple ways around that - use longer prime moduli, or change the modulus from time to time. The attack on RSA has no equivalent here. That attack involves using a key pair to find phi(n) or a divisor of it, but in Pohlig-Hellman the value of phi(p) is not secret (= p-1). I am presently using Pohlig-Hellman in a construction for universal re-encryption, taking advantage of it's key-multiplicative property. See http://www.zenadsl6186.zen.co.uk/ICURpaper3.pdf or http://www.zenadsl6186.zen.co.uk/ICURpaper3.ps for the messy math details, my application is in the online observable SFS for m-o-o-t. Pohlig-Hellman is still however very slow compared to modern symmetric ciphers, and in most cases where P-H is used a group cipher with the required key properties would be more efficient. No such cipher exists, but I am thinking of building one. I have already got a few indications of interest, if anyone else wants to contribute please let me know. I'm not committed to doing it, but if enough people want it.. - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
safety of Pohlig-Hellman with a common modulus?
Is it safe to use Pohlig-Hellman encryption with a common modulus? That is, I want various parties to have their own exponents, but share the same prime modulus. In my application, a chosen plaintext attack will be possible. (I know that RSA with common modulus is not safe.) --Steve Bellovin, http://www.research.att.com/~smb - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
