Re: Diffie-Hellman 128 bit
At 13/03/03 23:48, you wrote: I am looking at attacks on Diffie-Hellman. The protocol implementation I'm looking at designed their diffie-hellman using 128 bit primes (generated each time, yet P-1/2 will be a prime, so no go on pohlig-hellman attack), so what attacks are there that I can look at to come up with either the logarithm x from (a=g^x mod p) or the session key that is calculated. A brute force wouldn't work, unless I know the starting range. Are there any realistic attacks on DH parameters of this size, or is theoretically based on financial computation attacks? You can find good explanation for the rationale behind Diffie-Hellman parameters as well as general precautions for implementation in a good paper called "Security Issues in the Diffie-Hellman Key Agreement Protocol" You can find it in: http://citeseer.nj.nec.com/483430.html Regards, Hagai. Hagai Bar-El - Information Security Analyst Tel.: 972-8-9354152 Fax.: 972-8-9354152 E-mail: [EMAIL PROTECTED] Web: www.hbarel.com - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: Diffie-Hellman 128 bit
- Original Message - From: "NOP" <[EMAIL PROTECTED]> To: "Derek Atkins" <[EMAIL PROTECTED]> Cc: <[EMAIL PROTECTED]> Sent: Friday, March 14, 2003 9:32 PM Subject: Re: Diffie-Hellman 128 bit > Well, I'm attacking a protocol, I know the rules of DH parameters, and the > issue here is I'm trying to solve x, brute forcing that in the 128 bit range > can be difficult, and x doesn't have to be a prime. (a = g^x mod P). Their > primes are 128 bit primes, as well as their pubkeys, I've done some tests on > their prime, and all perform under this method of (p-1)/2 = prime. This > eliminates the pohlig-hellman discrete logarithm attack, but I'm trying to > learn the Gaussian integer method. Sorry, I mentioned using NFS in my previous reply, which is probably not the way you want to go about this (since it's not as efficient for small values and more complicated to code). Index-Calculus with Gaussian integers is indeed a good way. You can look at the paper from LaMacchia and Odlyzko http://citeseer.nj.nec.com/lamacchia91computation.html which Derek and maybe someone else pointed out.. They easily calculated discret logs modulo a 192-bit integer. --Anton - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: Diffie-Hellman 128 bit
> Well, I'm attacking a protocol, I know the rules of DH parameters, and the > issue here is I'm trying to solve x, brute forcing that in the 128 bit range > can be difficult, and x doesn't have to be a prime. (a = g^x mod P). Their > primes are 128 bit primes, as well as their pubkeys, I've done some tests on > their prime, and all perform under this method of (p-1)/2 = prime. This > eliminates the pohlig-hellman discrete logarithm attack, but I'm trying to > learn the Gaussian integer method. No, just use the Number Field Sieve algorithm (this is mentioned in section 3.5 of the manuscript I gave you the link to). You could read section 3.6 of the Handbook of Applied Cryptography for a basic introduction to the problem of discrete logarithm. --Anton - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: Diffie-Hellman 128 bit
On Fri, 14 Mar 2003, NOP wrote: >Nope, it uses 128 bit primes. I'm trying to compute the discrete logarithm >and they are staying within a 128 bit GF(p) field. Sickening. > >Thnx. > >Lance If they're using 128-bit primes, you don't really need to look for breaks - just throw a cpu at it and you're done. Bear - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: Diffie-Hellman 128 bit
Well, I'm attacking a protocol, I know the rules of DH parameters, and the issue here is I'm trying to solve x, brute forcing that in the 128 bit range can be difficult, and x doesn't have to be a prime. (a = g^x mod P). Their primes are 128 bit primes, as well as their pubkeys, I've done some tests on their prime, and all perform under this method of (p-1)/2 = prime. This eliminates the pohlig-hellman discrete logarithm attack, but I'm trying to learn the Gaussian integer method. Lance James - Original Message - From: "Derek Atkins" <[EMAIL PROTECTED]> To: "NOP" <[EMAIL PROTECTED]> Cc: <[EMAIL PROTECTED]> Sent: Friday, March 14, 2003 10:53 AM Subject: Re: Diffie-Hellman 128 bit > Hi, > > I'm sorry to inform you, but a brute-force attack on a 128-bit prime > is simple to mount. I don't think I can estimate the length of time > to attack a prime of this length, but it wouldn't be very long. > Consider that 425 bits is only about 4KMY (Kilo-MIP-Years) -- with > todays 2KM+ processors you're probably talking about a week or less to > crack it. Also, there aren't THAT many "strong" 128-bit primes. > > If you're using these numbers for real data (even if ephemeral), I > would suggest using at least 512-bit ephemeral DH Primes.. But then > you need some way to securely AGREE upon the ephemeral prime. > > How do you intend to prevent an attacker from forcing you to agree to > a prime that it's already solved? > > -derek > > NOP <[EMAIL PROTECTED]> writes: > > > I am looking at attacks on Diffie-Hellman. > > > > The protocol implementation I'm looking at designed their diffie-hellman > > using 128 bit primes (generated each time, yet P-1/2 will be a prime, so no > > go on pohlig-hellman attack), so what attacks are there that I can look at > > to come up with either the logarithm x from (a=g^x mod p) or the session key > > that is > > calculated. A brute force wouldn't work, unless I know the starting range. > > Are there any realistic > > attacks on DH parameters of this size, or is theoretically based on > > financial computation attacks? > > > > > > Thanks for your time. > > > > Lance James > > > > > > - > > The Cryptography Mailing List > > Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED] > > -- >Derek Atkins >Computer and Internet Security Consultant >[EMAIL PROTECTED] www.ihtfp.com > > - > The Cryptography Mailing List > Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED] > - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: Diffie-Hellman 128 bit
Hi, I'm sorry to inform you, but a brute-force attack on a 128-bit prime is simple to mount. I don't think I can estimate the length of time to attack a prime of this length, but it wouldn't be very long. Consider that 425 bits is only about 4KMY (Kilo-MIP-Years) -- with todays 2KM+ processors you're probably talking about a week or less to crack it. Also, there aren't THAT many "strong" 128-bit primes. If you're using these numbers for real data (even if ephemeral), I would suggest using at least 512-bit ephemeral DH Primes.. But then you need some way to securely AGREE upon the ephemeral prime. How do you intend to prevent an attacker from forcing you to agree to a prime that it's already solved? -derek NOP <[EMAIL PROTECTED]> writes: > I am looking at attacks on Diffie-Hellman. > > The protocol implementation I'm looking at designed their diffie-hellman > using 128 bit primes (generated each time, yet P-1/2 will be a prime, so no > go on pohlig-hellman attack), so what attacks are there that I can look at > to come up with either the logarithm x from (a=g^x mod p) or the session key > that is > calculated. A brute force wouldn't work, unless I know the starting range. > Are there any realistic > attacks on DH parameters of this size, or is theoretically based on > financial computation attacks? > > > Thanks for your time. > > Lance James > > > - > The Cryptography Mailing List > Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED] -- Derek Atkins Computer and Internet Security Consultant [EMAIL PROTECTED] www.ihtfp.com - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: Diffie-Hellman 128 bit
Nope, it uses 128 bit primes. I'm trying to compute the discrete logarithm and they are staying within a 128 bit GF(p) field. Sickening. Thnx. Lance - Original Message - From: "Anton Stiglic" <[EMAIL PROTECTED]> To: "NOP" <[EMAIL PROTECTED]>; <[EMAIL PROTECTED]> Sent: Friday, March 14, 2003 8:10 AM Subject: Re: Diffie-Hellman 128 bit > > - Original Message - > From: "NOP" <[EMAIL PROTECTED]> > To: <[EMAIL PROTECTED]> > Sent: Thursday, March 13, 2003 4:48 PM > Subject: Diffie-Hellman 128 bit > > > > I am looking at attacks on Diffie-Hellman. > > > > The protocol implementation I'm looking at designed their diffie-hellman > > using 128 bit primes (generated each time, yet P-1/2 will be a prime, so > no > > go on pohlig-hellman attack), > > 128-bit prime DH would be trivially breakable, maybe you mean that > it uses128-bit secret keys (and a larger prime, such as 512-bit prime at > least)? > > In any case, you can probably get all the information you are looking > for in this manuscript: > http://crypto.cs.mcgill.ca/~stiglic/Papers/dhfull.pdf > > Cheers! > > --Anton > > - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: Diffie-Hellman 128 bit
- Original Message - From: "NOP" <[EMAIL PROTECTED]> To: <[EMAIL PROTECTED]> Sent: Thursday, March 13, 2003 4:48 PM Subject: Diffie-Hellman 128 bit > I am looking at attacks on Diffie-Hellman. > > The protocol implementation I'm looking at designed their diffie-hellman > using 128 bit primes (generated each time, yet P-1/2 will be a prime, so no > go on pohlig-hellman attack), 128-bit prime DH would be trivially breakable, maybe you mean that it uses128-bit secret keys (and a larger prime, such as 512-bit prime at least)? In any case, you can probably get all the information you are looking for in this manuscript: http://crypto.cs.mcgill.ca/~stiglic/Papers/dhfull.pdf Cheers! --Anton - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: Diffie-Hellman 128 bit
At 01:48 PM 03/13/2003 -0800, NOP wrote: I am looking at attacks on Diffie-Hellman. The protocol implementation I'm looking at designed their diffie-hellman using 128 bit primes (generated each time, yet P-1/2 will be a prime, so no go on pohlig-hellman attack), so what attacks are there that I can look at to come up with either the logarithm x from (a=g^x mod p) or the session key that is calculated. A brute force wouldn't work, unless I know the starting range. Are there any realistic attacks on DH parameters of this size, or is theoretically based on financial computation attacks? Google for "Odlyzko Diffie Hellman" and look at the various papers. Unless you're talking about elliptic curve versions of Diffie Hellman (and even then 128 bits probably isn't enough), 128 is way too weak. DH is similar in strength to RSA, so don't think about using less than 1024, and realistically go for 2048 or more. - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Diffie-Hellman 128 bit
I am looking at attacks on Diffie-Hellman. The protocol implementation I'm looking at designed their diffie-hellman using 128 bit primes (generated each time, yet P-1/2 will be a prime, so no go on pohlig-hellman attack), so what attacks are there that I can look at to come up with either the logarithm x from (a=g^x mod p) or the session key that is calculated. A brute force wouldn't work, unless I know the starting range. Are there any realistic attacks on DH parameters of this size, or is theoretically based on financial computation attacks? Thanks for your time. Lance James - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
