Slashdot Mirror

← Back to Stories (view on slashdot.org)

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

Posted by Soulskill on 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."

10 of 114 comments (clear)

  1. Is Diffie Hellman at risk? by Sun · · Score: 5, Interesting

    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

    1. Re:Is Diffie Hellman at risk? by LordLimecat · · Score: 5, Insightful

      Seeing it on slashdot means nothing. Wait till a reputable source that DOESNT have a habit of blowing everything up into a crisis reports on this-- schneier's blog would be a good place to start.

    2. Re:Is Diffie Hellman at risk? by houstonbofh · · Score: 4, Interesting

      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.

    3. Re:Is Diffie Hellman at risk? by Sun · · Score: 5, Informative

      Posted it as a question there already.

      Here's the thing, however. From reading the article, it seems that DH was not, itself, broken. Here's the problem, however: DH is used for forward reference security. It is used to ensure that an adversary that captured the encrypted communication cannot be decrypted later, even if the RSA key is later compromised

      Which means that whether DH has already been broken is a moot question. The real question is whether it is likely to be broken in the near future (where what "near" means depends on what you're actually encrypting).

      Here is what Schneier usually has to say about that: Attacks always get better over time.

      Of course, the main problem with replacing DH is that we don't really have anything better on hand.

      Shachar

  2. Re:Almost first post! by Sun · · Score: 5, Interesting

    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

  3. arXiv link (to the technical paper) by l2718 · · Score: 5, Informative

    TFA links to the published version on SpringerLink, which is paywalled. A free preprint is available on the arXiv.

  4. Somewhat by l2718 · · Score: 5, Interesting

    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.

  5. It's still NP. by mark-t · · Score: 4, Informative

    As I understand it, they've simplified the problem to a compiexity of O(n^log(n))... this is still non-polynomial time... but the rate of complexity growth is effectively polynomial. If I understand correctly, that means that the additional security that was formerly thought to be obtained by merely doubling cryptographic key length must now be obtained by squaring it.

    --
    File under 'M' for 'Manic ranting'
  6. Don't put Dlog to sleep so soon by iceco2 · · Score: 5, Insightful

    The result is on for fields with small characteristic, but the most commonly used finite fields in this context are the Zp for some prime p which have characteristic p.
    So though this is a very interesting result, I am not tossing out all my crypto suit yet.
    we should be cautiously seeking better alternatives, but the worst thing we can do is to panic and ditch well studied algorithms and implementations every time some progress is made on their cryptanalysis.

  7. Re:Probably known already by vadim_t · · Score: 4, Insightful

    No, like the [Dual EC DRBG](http://en.wikipedia.org/wiki/Dual_EC_DRBG) controversy.

    I love it how people (shills?) keep bringing up DES S-boxes, as if they had anything to do with anything. The thing with DES was in 1975. Almost 40 years ago. Since then the NSA went through 10 directors, and the US through 8 presidents. And most of the staff in high positions died or retired.

    It's ridiculous to try to pretend that something nice a completely different NSA did 40 years ago has the slightest relevance to today's completely different environment and politics.