Slashdot Mirror
Discrete Logarithm Problem Partly Solved -- Time To Drop Some Crypto Methods?
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."
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
However, someone intercepted the message, cracked slashdot's https rsa key, modified this message, then submitted it on my behalf.
All your Logs are belong to us.
If this is just being publicly announced now, it was probably known to NSA, the GRU, and the MSS years ago. The superpower security agencies put substantial resources into cryptanalytic number theory.
Early public key cryptosystems used the knapsack problem. That turned out to have reasonably easy solutions. Factoring products of two big primes may be all we have left. That's believed to be hard, but there's no proof of a lower bound on it.
TFA links to the published version on SpringerLink, which is paywalled. A free preprint is available on the arXiv.
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.
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'
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.
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.
Yes, these elliptic curves address defined over a finite field, but there's no known connection between the discrete log problem for the field and for the elliptic curve.
Even though I didn't really understood the math, two important points stick out from their description:
As far as I understood they empirically showed their approach to work on one example. A study showing the general feasibility of the heuristics would be more convincing (yeah, that's the engineer speaking not the mathematician).
It should also be noted that the authors themselves write in their conclusion:
"Compared to existing approaches, and in particular to the line of recent works [15,10], the practical relevance of our algorithm is not clear, and will be explored by further work."
So, before running to conclusions maybe we should wait for the "further work".
Until you try to impliment them on hardware that can exist in the real world.
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).
Unless you're talking about the Dual EC DRBG.
Prime fields are safer, but they are inconvenient. Elements in a GF(2**n) field map nicely to n bits.
I should use this sig to advertise my book ISBN-13 : 978-1501515132.