Discrete Logarithm Problem Partly Solved -- Time To Drop Some Crypto Methods? 114
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."
Is Diffie Hellman at risk? (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
Re:Almost first post! (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
Re:Is Diffie Hellman at risk? (Score:5, 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.
Somewhat (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.
Re:Probably known already (Score:2, Interesting)
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.
Repercussion on SmartCards? (Score:4, Interesting)
Hype (Score:2, Interesting)
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).