Slashdot stories can be listened to in audio form via an RSS feed, as read by our own robotic overlord.

 



Forgot your password?
typodupeerror
Math Encryption

Discrete Logarithm Problem Partly Solved -- Time To Drop Some Crypto Methods? 114

Posted by Soulskill
from the now-let's-be-paranoid-that-the-NSA-solved-it-years-ago dept.
An anonymous reader points out this Science Daily report: "Researchers ... have solved one aspect of the discrete logarithm problem. This is considered to be one of the 'holy grails' of algorithmic number theory, on which the security of many cryptographic systems used today is based. They have devised a new algorithm that calls into question the security of one variant of this problem, which has been closely studied since 1976. The result ... discredits several cryptographic systems that until now were assumed to provide sufficient security safeguards. Although this work is still theoretical, it is likely to have repercussions especially on the cryptographic applications of smart cards, RFID chips , etc."
This discussion has been archived. No new comments can be posted.

Discrete Logarithm Problem Partly Solved -- Time To Drop Some Crypto Methods?

Comments Filter:
  • by Sun (104778) <shachar@shemesh.biz> on Friday May 16, 2014 @11:20PM (#47023343) Homepage

    I really really skimmed the article, but I think it all boils to this one algorithm. If Diffie Hellman is at risk, then all of our "perfect forward security" reliance of SSL is gone.

    Shachar

  • by Sun (104778) <shachar@shemesh.biz> on Friday May 16, 2014 @11:31PM (#47023387) Homepage

    RSA does not rely on discrete log. It rather relies on discrete root.

    Dlog is the base, however, to almost any other public key algorithm out there which isn't elliptic curve. This includes Diffie Hellman, El-Gamal, DSA, Schnor and I'm sure others as well.

    My reading of the article is that those are not yet borken, per se (spelling mistake left in intentionally). Since Diffie Hellman is primarily used for forward reference security, however (i.e. - figuring out a session key that will not be compromised even if the private key later is), the question is not whether it is safe today. The question is whether it will remain safe for the foreseeable future.

    If attacks on dlog are beginning to become practical, the answer is "less and less".

    Shachar

  • by houstonbofh (602064) on Friday May 16, 2014 @11:57PM (#47023451)

    If Diffie Hellman is at risk, then all of our "perfect forward security" reliance of SSL is gone.

    Shachar

    Really, it was gone already, many times. The key generation bug, the heartbleed bug... Even if it works, it is still probably easier to exploit coding mistakes, and we seem to have enough of them.

  • Somewhat (Score:5, Interesting)

    by l2718 (514756) on Saturday May 17, 2014 @12:01AM (#47023475)

    Reading the paper, the most notable feature is that their algorithm is efficiency for constant characteristic, including the common case of fields of characteristic 2. It's also okay for the characteristic to grow somewhat with the size of the field, but not very fast.

    This is not at all relevant to most implementations of DH, which use prime fields of large characteristic. For example, DSA depends on discrete log modulu a large prime p. In particular, I wouldn't worry about forward secrecy of current internet traffic.

  • by Anonymous Coward on Saturday May 17, 2014 @12:27AM (#47023563)

    Unless they are keeping keys to the algorithm that no one else has, and which cannot be determined after the fact. This is essentially the issue that they were accused of in regards to the elliptic curve random number generator they had put forward as a standard.

  • by brainnolo (688900) on Saturday May 17, 2014 @01:47AM (#47023791) Homepage
    SmartCards actually mostly rely on symmetric algorithms for most applications. The only commonly used public key algorithm is RSA, which is not based on discrete logarithm. This leaves DSA, among the relatively common algorithms, but that is rarely used on SmartCards. What would be interesting to know, is how EC-DSA is affected, since it is slowly replacing RSA because of the reduced key size.
  • Hype (Score:2, Interesting)

    by Anonymous Coward on Saturday May 17, 2014 @11:18AM (#47025867)

    I'm a cryptographer and the paper didn't even catch my eye when I was glancing this year's Eurocrypt papers. I also haven't heard anyone talk about it at work and this is despite all my coworkers working on crypto which would break if someone came up with a fast dlog algorithm in groups used in practice. The algorithm is purely for fields of small characteristic, which means that it's totally irrelevant for most practical applications, since typically one will work over subgroup of invertible elements for the finite field F_p, where the characteristic p is of the order of the security parameter (meaning it's huge).

    To me this looks like hype stemming from a popularizing science paper misunderstanding something (or misunderstanding it on purpose).

Loose bits sink chips.

Working...