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

#### Soulskill posted about 7 months ago | from the now-let's-be-paranoid-that-the-NSA-solved-it-years-ago dept.

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? (5, Interesting)

## Sun (104778) | about 7 months ago | (#47023343)

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:Is Diffie Hellman at risk? (5, Insightful)

## LordLimecat (1103839) | about 7 months ago | (#47023413)

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.

## Re:Is Diffie Hellman at risk? (5, Informative)

## Sun (104778) | about 7 months ago | (#47023455)

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 compromisedWhich 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

## Re:Is Diffie Hellman at risk? (1)

## storkus (179708) | about 7 months ago | (#47023661)

I'm guessing Schneier et al won't have a chance to analyze and reply until next week, but this is so important, who knows?

It also occurred to me that, since the mess with the NSA broke out, I have not seen anything about Suite B being modified--everything in there is still officially supported for "State Secrets". I keep wondering if we're missing something there...

## Re:Is Diffie Hellman at risk? (0)

## Anonymous Coward | about 7 months ago | (#47024059)

Adversaries are encrypted now? Man, what will they think of next?

## Re:Is Diffie Hellman at risk? (2)

## Kjella (173770) | about 7 months ago | (#47024547)

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

Actually there is no need for DH, you can create a new throwaway RSA private/public key pair on both sides, sign it with your main key, use the throwaway keys to transfer the session key then wipe the throwaway keys. The problem with this approach is that generating a new RSA key pair for every session + transferring new key + extra round trips is a really slow process compared to DH.

## Re:Is Diffie Hellman at risk? (0)

## Anonymous Coward | about 7 months ago | (#47024825)

So in other words: There actually is a real need for this...

As the alternatives are cumbersome and require more resources.

## Re:Is Diffie Hellman at risk? (1)

## houstonbofh (602064) | about 7 months ago | (#47025167)

So in other words: There actually is a real need for this... As the alternatives are cumbersome and require more resources.

Too bad computers are out of resources, and no more seem to be coming.

I think generating a key pair is less load than modern window managers.

## Re:Is Diffie Hellman at risk? (2)

## lister king of smeg (2481612) | about 7 months ago | (#47025949)

A better way to handle this would probably be to have the client generate the session key and encrypt it with the servers public key, this would distribute the load for generating keys away form the server so they would not be as easily DOS'ed.

## Re:Is Diffie Hellman at risk? (1)

## Fnord666 (889225) | about 7 months ago | (#47025557)

Actually there is no need for DH, you can create a new throwaway RSA private/public key pair on both sides, sign it with your main key, use the throwaway keys to transfer the session key then wipe the throwaway keys. The problem with this approach is that generating a new RSA key pair for every session + transferring new key + extra round trips is a really slow process compared to DH.

So how do you go about securely communicating one part of the throwaway keys to the other side so that the session key can be transferred?

## Re:Is Diffie Hellman at risk? (1)

## Kjella (173770) | about 7 months ago | (#47026943)

So how do you go about securely communicating one part of the throwaway keys to the other side so that the session key can be transferred?

Static RSA using the main keys. It won't have PFS, but it will only contain the public keys of the throwaway pair so recovering it later won't do you any good.

As a step process:

1. Static RSA with main keys, swap public throwaway keys.

2. Static RSA with throwaway keys

3. Negotiate session key

4. Throw away private key used in 2. immediately

5. Server is compromised, main key stolen

6. Traffic in 1. is decrypted, public keys found

7. Private keys for 2. is gone, session key can't be decrypted = perfect forward security

## Re:Is Diffie Hellman at risk? (1)

## CrimsonAvenger (580665) | about 7 months ago | (#47024963)

So, why exactly would we want to decrypt the adversary that captured some encrypted communications?

## Re:Is Diffie Hellman at risk? (4, Interesting)

## houstonbofh (602064) | about 7 months ago | (#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.

## Re:Is Diffie Hellman at risk? (1)

## Anonymous Coward | about 7 months ago | (#47024765)

It's like religion. It's not the theory, it's the implementation that's flawed.

## Re:Is Diffie Hellman at risk? (1)

## houstonbofh (602064) | about 7 months ago | (#47025159)

It's like religion. It's not the theory, it's the implementation that's flawed.

I like that a lot.

## Re:Is Diffie Hellman at risk? (-1)

## Anonymous Coward | about 7 months ago | (#47025239)

huh? isn't the theory of religion that ignorance/faith is virtuous?

## Re:Is Diffie Hellman at risk? (1)

## Bill, Shooter of Bul (629286) | about 7 months ago | (#47026179)

No, this paper is explicitly stating that the theory is flawed. If this attack is expanded, SSL traffic will essentially be as secure as rot13. That's very different and much worse than heartbleed or any key generation issue. My applications were not affected by either of those coding mistakes, but they and everything else using the same algorithm would be by a break in DH.

## Re:Is Diffie Hellman at risk? (0)

## Anonymous Coward | about 7 months ago | (#47026289)

that's ridiculous. it's free software. you could have disabled the heartbleed extension 4 years ago like fortress IT security [twitter.com] did.

## Somewhat (5, Interesting)

## l2718 (514756) | about 7 months ago | (#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.

## Re:Somewhat (1)

## Fnord666 (889225) | about 7 months ago | (#47025823)

This is not at all relevant to most implementations of DH, which use prime fields of large characteristic.

Exactly. Probably more interesting is that their solution is applicable to a wider range of finite fields than recent improvements.

From the paper:

Although we insist on the case of finite fields of small characteristic, where quasi-polynomial complexity is obtained, our new algorithm improves the com- plexity of discrete logarithm computations in a much larger range of finite fields.

I see no good basis for the ScienceDaily author's leap from the paper's results to his conclusion that

Since solving this variant of the discrete logarithm is now within the capacity of current computers, relying on its difficulty for cryptographic applications is therefore no longer an option.This work is still at a theoretical stage and the algorithm still needs to be refined before it is possible to provide a practical demonstration of the weakness of this variant of the discrete logarithm. Nonetheless, these results reveal a flaw in cryptographic security and open the way to additional research. For instance, the algorithm could be adapted in order to test the robustness of other cryptographic applications.## Re:Is Diffie Hellman at risk? (1)

## Anonymous Coward | about 7 months ago | (#47023687)

What?

I was told by a scientist friend 14 years ago that diffie hellman was a sort of knapsack problem - and thus solvable in polynomial time - and that it was therefore inherently weaker than RSA. :/ could it be that this has been known for decades but not widely spread?

When I look the knapsack problem up wikipedia says it's NP hard but that many cases, including random cases are solvable in polynomial time, even though not all can.

You know, that's how decision problems for circuit verification are. While, in theory problems with as many variables as they have shouldn't be solvable - actual circuits always seem to fall to pruning algorithms that are totally safe. So practical problems are solvable, and they don't know why.

## Re:Is Diffie Hellman at risk? (0)

## Anonymous Coward | about 7 months ago | (#47023715)

I'm thinking he was confused with Merkle–Hellman

## Re: Is Diffie Hellman at risk? (1)

## loufoque (1400831) | about 7 months ago | (#47024245)

Knapsack is NP-complete.

## Re:Is Diffie Hellman at risk? (1)

## mellon (7048) | about 7 months ago | (#47024841)

What this is is another argument for using long keys. The improvement doesn't appear to be sufficient to render Diffie-Hellman unusable.

## Re:Is Diffie Hellman at risk? (1)

## mellon (7048) | about 7 months ago | (#47024849)

Er, actually the above is half an answer, and turns out to be wrong in its explanation, although not in its conclusion. Math is hard.

## Re:Is Diffie Hellman at risk? (2)

## russotto (537200) | about 7 months ago | (#47025721)

Breaking the discrete logarithm problem breaks both DH and RSA; obtaining the private exponent from the RSA public key can be done by solving the discrete logarithm problem. However, this algorithm solves the discrete logarithm problem only for certain fields (Galois fields of small characteristic), and I don't believe those are the ones interesting for RSA or DH. (RSA uses a composite group; DH uses a prime field of large characteristic)

## Almost first post! (2)

## Anonymous Coward | about 7 months ago | (#47023349)

However, someone intercepted the message, cracked slashdot's https rsa key, modified this message, then submitted it on my behalf.

## Re:Almost first post! (5, Interesting)

## Sun (104778) | about 7 months ago | (#47023387)

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:Almost first post! (0)

## Anonymous Coward | about 7 months ago | (#47023521)

Many number theorists believe the problem of discrete logarithms and factoring are somehow linked, and historically advance in one has led to advance in other [wordpress.com] . However, this particular breakhrough [arxiv.org] was first published nearly a year ago, and also currently only relevant for small to medium prime fields...

## Re: Almost first post! (0)

## Anonymous Coward | about 7 months ago | (#47023595)

Finding a RSA private key exponent is a discrete logarithm problem. Moreover, there is a polynomial time algorithm for factoring the modulus given a public/private key pair.

## Re:Almost first post! (0)

## Anonymous Coward | about 7 months ago | (#47023993)

Preliminaries from Alfred Menezes:

"Menezes says his analysis also shows the algorithm only becomes effective as the parameters of a cryptosystem, essentially the key size, grow asymptotically large. It may not be efficient; in fact, it may be slower than other algorithms against systems of small key size. Also, it is not effective against RSA and other non-pairing-based systems."

## Re:Almost first post! (2)

## TeknoHog (164938) | about 7 months ago | (#47024649)

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.

Discrete log is certainly being used with elliptic curves. EC isn't really an algorithm, but an alternative "number system" that is well suited for crypto (the common alternative is finite/Galois fields).

## Re:Almost first post! (1)

## russotto (537200) | about 7 months ago | (#47025825)

RSA private key is p,q,d where p and q are large primes and d is the private exponent.

RSA public key is n, e where n = pq and e is the public exponent. The private exponent d was chosen such that (m^e)^d (mod n) = m for any m (message) 0 m n.

RSA encryption is c = m^e (mod n)

RSA decryption is m = c^d (mod n)

Suppose I have an RSA public key n, e. I pick an arbitrary m and calculate

c = m ^ e (mod n)

Now I need to find d such that

m = c ^ d (mod n)

This is the discrete logarithm problem.

Being able to solve discrete root would ALSO break RSA; if you could figure out the eth root of c (mod n), you could get the message without having the private key.

And for completeness, solving integer factorization breaks RSA because with p and q you can calculate d.

Elliptic curve encryption also relies on a discrete logarithm problem being hard, but it's a discrete logarithm over an elliptic curve, which is believed to be harder.

## Re:Almost first post! (1)

## swillden (191260) | about 7 months ago | (#47028325)

Dlog is the base, however, to almost any other public key algorithm out there which isn't elliptic curve.

EC algorithms (ECDH, ECDSA, ECIES) are also based ultimately on the discrete log problem. So, this news is a potential threat to essentially all of the major asymmetric crypto algorithms, excepting only RSA.

## Re:Almost first post! (1)

## Anonymous Coward | about 7 months ago | (#47023797)

However, someone intercepted the message, cracked slashdot's https rsa key, modified this message, then submitted it on my behalf.

You are aware Slashdot has an in-house analytics database that can easily correlate any AC to IP addresses, corresponding MAC addresses, logins (if any) and locations. If push comes to shove, the police can be given your ID, most likely without the need for a warrant. Just a lowly peon that never registered; not a problem, if your comments are serious enough for the labor.

## Re:Almost first post! (0)

## Anonymous Coward | about 7 months ago | (#47024207)

The ids stored by slash along the posts are just the md5sum of the ip as can be seen in it's soruce code.

If you have a ipv4 it's trivial to reverse, ipv6 not so much. Of course still there are access logs and NSA sniffers all over the pipes.

## Re:Almost first post! (1)

## caluml (551744) | about 7 months ago | (#47024445)

Your MAC address isn't visible outside your local subnet. Slashdot has no way of knowing your MAC address. (Unless perhaps you're using IPv6 without privacy extensions enabled, but I'm guessing Slashdot is years away from IPv6.)

## Re:Almost first post! (1)

## DarwinSurvivor (1752106) | about 7 months ago | (#47024695)

## Re: Almost first post! (0)

## Anonymous Coward | about 7 months ago | (#47024883)

Or you allow JavaScript from dice(y) to run on your machine. Duh.

## Re: Almost first post! (1)

## caluml (551744) | about 7 months ago | (#47025335)

var locator = new ActiveXObject("WbemScripting.SWbemLocator");

// Get the info

var service = locator.ConnectServer(".");

var properties = service.ExecQuery("SELECT * FROM Win32_NetworkAdapterConfiguration");

var e = new Enumerator (properties);

Jesus, that looks horrible. I would hope that you have to add sites to your Local Intranet zone or whatever it's called these days before it'll work.

## Re:Almost first post! (0)

## Anonymous Coward | about 7 months ago | (#47024757)

So THAT is why my posts are always ignored! Guess I offended /. a long time ago ...

## Springer Verlag says (2)

## Mister Liberty (769145) | about 7 months ago | (#47023379)

## Probably known already (2)

## Animats (122034) | about 7 months ago | (#47023415)

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.

## Re:Probably known already (1)

## Strider- (39683) | about 7 months ago | (#47023469)

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.

I think that many people forget the NSA's other mission: securing US Government communications. The easiest way to figure out how secure an algorithm is, is to take a look at what level of information it's authorized for. Despite everything that all the folks here say, the NSA and other agencies aren't stupid. They know full well that if they can break the algorithm, somebody else can as well.

## Re:Probably known already (2, Interesting)

## Anonymous Coward | about 7 months ago | (#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.

## Re:Probably known already (0)

## x0ra (1249540) | about 7 months ago | (#47023869)

## Re:Probably known already (4, Insightful)

## vadim_t (324782) | about 7 months ago | (#47024063)

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.

## Re:Probably known already (1)

## Electricity Likes Me (1098643) | about 7 months ago | (#47025965)

Yes except no one's been able to show that they actually do have the keys, or even a smoking gun of "this algorithm is always active".

What they are doing is the same wailing and knashing of teeth that happened 40 years ago.

Meanwhile it seems far more obvious that the NSA instead just relies on the CIAs direct intercept and tampering with targeted bits of hardware, rather then depending on people using a specific algorithm, with a specific set of constants, somewhere that's interesting to them and not one where the documentation for its specifications

explains exactly how to generate new constants which would eliminate any baked in security hole.## Re:Probably known already (0)

## Anonymous Coward | about 7 months ago | (#47026499)

Yes except no one's been able to show that they actually do have the keys, or even a smoking gun of "this algorithm is always active".

Showing the NSA actually has the keys would require one to either infiltrate the NSA (kind of hard) or have top secret clearance (in which case you wouldn't be allowed to release the information).

Someoneat the NSA has the numbers (whether or not the organization as a whole does) fo break Dual EC DRBG, which means it is broken period.As to the grandparent, the NSA improving DES's S-boxes wasn't even a nice thing by the NSA. If you've read up on the history of DES, the NSA improved the S-boxes with the understanding NIST

would notmake the algorithm public! They never intended for any of it to become public knowledge.## Re:Probably known already (1)

## evilviper (135110) | about 7 months ago | (#47026695)

It's not relevant for judging the character of the NSA, of course, but it's HIGHLY relevant as a bit of context, when people are acting paranoid, and throwing around accusations with no evidence.

## Re:Probably known already (1, Insightful)

## marcello_dl (667940) | about 7 months ago | (#47023725)

There are many other methods to send info, one time pads (number stations), steganography (lots of side channels for noise to be tampered with), couriers, stuff...

And BTW you still have to prove that NSA and all the other agencies are working for their own nation against the other nations. It may hold true at lower levels, but they don't answer to anyone by design, and it's apparent that we live in a global system where politics are a diversion.

## Re:Probably known already (1)

## Kjella (173770) | about 7 months ago | (#47024227)

There are many other methods to send info, one time pads (number stations), steganography (lots of side channels for noise to be tampered with), couriers, stuff...

OTP needs a secure side channel the same size as the data meaning you can't just call/text/mail someone and verify a fingerprint, which makes it extremely impractical, steganography with no or weak encryption is just security by obscurity, couriers depend on the security of the courier which is just like trusting the Internet - it too is a third party courier. Without regular PKI it wouldn't be practically feasible, fortunately the basic building blocks like RSA for signing/verifying in certificates and PGP messages, Diffie-Hellman for ephemeral keys and any symmetric cipher like AES for bulk transport still seem pretty unthreatened. The problem is the implementation, which is far from trivial to do right.

## Re:Probably known already (1)

## marcello_dl (667940) | about 7 months ago | (#47028077)

OTP needs a secure side channel the same size as the data meaning you can't just call/text/mail someone and verify a fingerprint, which makes it extremely impractical

Well that's a problem if your are already under the radar but otherwise? What if you just apply a salted hash to blocks of innocent files that you share with your pal and use them as the OTP? We all already share innocent files provably identical, the updates. Linux users routinely download compressed and signed packages those mega if not gigabytes can stay on the HD for the life of the PC. Windows updates are probably the same, thanks god I dunno and don't care. All I need to use OTP with a pal is the salt, and the hash function, and an optional way to say I "have been compromised". A rookie programmer can whip up the encoding and decoding function script without even saving it on the hd.

Steganography, what about patching an online game client? It appears I am gaming while I am trasmitting and raise no suspicion. I mean all network hardware sold could already have the capability to encode data masked as jitter, for what we know.

And these are the first things off my mind, what about people who do this for a living?

## Re:Probably known already (1)

## Anonymous Coward | about 7 months ago | (#47024599)

Key distribution for one time pads is a nightmare. It's possible for a giovernment to send tapes of one time pads through diplomatic baggage to their embassies in advance. But it's completely useless for anyone else.

## Re:Probably known already (1)

## houstonbofh (602064) | about 7 months ago | (#47025203)

Key distribution for one time pads is a nightmare. It's possible for a government to send tapes of one time pads through diplomatic baggage to their embassies in advance. But it's completely useless for anyone else.

Yeah... Mailing a flash drive is beyond the abilities of most people.

## Re:Probably known already (0)

## Anonymous Coward | about 7 months ago | (#47028149)

No, but mailing hundreds of them and keeping track of all of them and which should be renewed is. Besides, mail can be intercepted without your knowledge.

## Re:Probably known already (1)

## evilviper (135110) | about 7 months ago | (#47024057)

Factoring primes is popular, but not at all the ONLY method:

https://en.wikipedia.org/wiki/... [wikipedia.org]

## Re:Probably known already (1)

## Anonymous Coward | about 7 months ago | (#47024947)

> If this is just being publicly announced now, it was probably known to NSA, the GRU, and the MSS years ago.

I don't know about that. One thing that has become clear after Snowden's revelations is that the NSA has troubles with properly implemented cryptography. Whereas they no doubt have one or two tricks up their sleeve, they don't seem to be in possession of any revolutionary mathematical knowledge. They used to be years ahead of academia in cryptography, when academia was barely looking into it. That ended about 40 years ago.

## What the hell? (0)

## Anonymous Coward | about 7 months ago | (#47023423)

This is slashdot. We get cut and paste third rate analysis in the summary? No description of which cryptographic systems?

## Re: What the hell? (0)

## Anonymous Coward | about 7 months ago | (#47027021)

Analysis shows that not even the people involved in this "disclosure" are certain about in what regard their contribution really contributed to solving this problem!

Oh and "discretion" is adviced, but imho this is just another stupid attempt by the newops of this site to get som additional revenue from ad sales.

Google this. EVERYTHING links back here.

I guess the point is invalid, which must mean my hair is a bird! .. SlashRot did it again

## arXiv link (to the technical paper) (5, Informative)

## l2718 (514756) | about 7 months ago | (#47023429)

## Re:arXiv link (to the technical paper) (0)

## Anonymous Coward | about 7 months ago | (#47023447)

## Re:arXiv link (to the technical paper) (2)

## l2718 (514756) | about 7 months ago | (#47023485)

## Re:arXiv link (to the technical paper) (0)

## Anonymous Coward | about 7 months ago | (#47026307)

plus, how would it get it's kickbacks from douchebag.com

## Not much to see here. (1)

## Anonymous Coward | about 7 months ago | (#47023519)

The new algorithm is for small characteristics. Small characteristics have been suspect for some time and are no longer used. In fact: cryptographers are moving away from finite fields altogether in favor of elliptic curves, now that most of the relevant patents in that subject have either expired or been rendered toothlesss. No subexponential algorithm is known for the Discrete Logarithm Problem over elliptic curves.

## Re:Not much to see here. (1)

## TechyImmigrant (175943) | about 7 months ago | (#47023633)

>are moving away from finite fields altogether in favor of elliptic curves

Umm, what about all the elliptic curves in finite fields?

## Re:Not much to see here. (1)

## jopsen (885607) | about 7 months ago | (#47023775)

>are moving away from finite fields altogether in favor of elliptic curves Umm, what about all the elliptic curves in finite fields?

It may have been 6 years since I played with the discrete logarithm problem over elliptic curves, but aren't all the fields finite?

## Re:Not much to see here. (1)

## l2718 (514756) | about 7 months ago | (#47023957)

## Re:Not much to see here. (2)

## SuricouRaven (1897204) | about 7 months ago | (#47024159)

Until you try to impliment them on hardware that can exist in the real world.

## Re:Not much to see here. (2)

## l2718 (514756) | about 7 months ago | (#47023969)

definedover a finite field, but there's no known connection between the discrete log problem for the field and for the elliptic curve.## Re:Not much to see here. (2)

## TechyImmigrant (175943) | about 7 months ago | (#47027875)

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.

## It's still NP. (4, Informative)

## mark-t (151149) | about 7 months ago | (#47023565)

## Re:It's still NP. (0)

## Anonymous Coward | about 7 months ago | (#47023737)

NP doesn't stand for non-polynomial and indeed everything in P is also in NP. NP stands for non-deterministically polynomial.

## Re:It's still NP. (0)

## Anonymous Coward | about 7 months ago | (#47023917)

## Re:It's still NP. (1)

## Anubis IV (1279820) | about 7 months ago | (#47026103)

He never even mentioned NP!

Au contraire, he started with it in his title for the comment: "It's still NP."## Re:It's still NP. (1, Informative)

## WoOS (28173) | about 7 months ago | (#47023915)

Please note that the algortihm is

notO(n^log(n)) but n^O(log(n)). This puts the constant factor in the exponent which is a bit worse.## Re:It's still NP. (2, Insightful)

## ShadowRangerRIT (1301549) | about 7 months ago | (#47025905)

## Re:It's still NP. (1)

## fph il quozientatore (971015) | about 7 months ago | (#47026155)

## Re:It's still NP. (0)

## Anonymous Coward | about 7 months ago | (#47026205)

By n^O(log(n)) one means that it is bounded by something of the form n^(f(x)) where f(x) is in O(log(n)), which is different from saying O(n^(log(n))) which would imply that we are bounded by a multiple of n^(log(n)). See the multiple usages part of the article you linked for a similar example with O(1). And the point of the GP's post is that you can't rearrange the terms. The paper states n^(O(log(n))), also see the following https://en.wikipedia.org/wiki/Quasi-polynomial_time#Quasi-polynomial_time. Also by constant factor one means that the O(f(x)) notation means we are bounded by a multiple (constant factor) of f(x).

## Re:It's still NP. (1)

## Carewolf (581105) | about 7 months ago | (#47027885)

Yes, that is how I read it too. (posting to undo accidental wrong mod)

## Re:It's still NP. (3, Informative)

## l2718 (514756) | about 7 months ago | (#47023953)

## Re:It's still NP. (1)

## Twinbee (767046) | about 7 months ago | (#47025351)

## Re:It's still NP. (1)

## ShadowRangerRIT (1301549) | about 7 months ago | (#47025947)

A short key right now is 512 bits (0.5 KB). A longish key right now is 4096 bits (4 KB); many sites use shorter keys because high traffic sites can't afford the bandwidth and CPU required to transmit and process even a 4096 bit key for thousands of connections per second. Squaring even the short end of that range would produce a 262144 bit key (256KB). That's a ridiculous amount of data overhead just to initiate a connection, and performing math in a space that large would tax the CPU of individual computers; if a web server is performing that much math for every connection, you'd dramatically increase the overhead to serve web pages.

TL;DR: Squaring key length make math hard, hurt computer.

## Re:It's still NP. (1)

## Anonymous Coward | about 7 months ago | (#47024419)

n^log(n):

F(2^2) = 2^4 = you can probably solve it with pen and paper

F(2^3) = 2^9 = you could probably still solve it by hand if your life depended on it.

F(2^4) = 2^16 = too hard to solve by hand, but a PC could do it in less than a microsecond.

F(2^5) = 2^25 = solved in millisecond or so on a PC

F(2^6) = 2^36 = solved in a few minutes on a PC

F(2^7) = 2^49 = a little difficult to brute force, but still easily solved in half a day on a GPU.

F(2^8) = 2^64 = a server farm can solve this in a day.

F(2^9) = 2^81 = the top supercomputer in the world would take decades to solve this.

F(2^10) = 2^100 = our solar system won't exist long enough for you to get the answer.

...

F(2^16) = 2^256 = nothing in the known universe will ever solve this before the big fizzle.

From the above, you can see that squaring the key size isn't necessary unless the problem is already trivial to solve.

## Looks like this is specific to finite fields (0)

## Anonymous Coward | about 7 months ago | (#47023599)

I've basically only read the abstract and first section of the actual paper, but it looks like this is only demonstrating a weakness in the discrete log problem on finite fields. Specificaly fields of small characteristic. If you were using a large prime field, I suspect this isn't much of an issue. I'm also guessing this doesn't affect general elliptic curves. I'll be scared if they find a powerful algorithm to attack the general discrete log problem for groups.

I'm also wondering if this result will lead to a more efficient algorithm for factoring large integers. It has been my understanding these problems are related, unless it's more like discrete log on prime fields is related to integer factorization. But again, I haven't read the entire paper yet.

## Don't put Dlog to sleep so soon (5, Insightful)

## iceco2 (703132) | about 7 months ago | (#47023603)

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.

## Re:Don't put Dlog to sleep so soon (1)

## Anonymous Coward | about 7 months ago | (#47023705)

Fields with small characteristic have been known weaker for eons— (including by the author of this paper's prior work). In general, its well know that prime fields have the best security story.

## Re:Don't put Dlog to sleep so soon (1)

## garryknight (1190179) | about 7 months ago | (#47024391)

I am not tossing out all my crypto suit yet.You might want to hold onto it. While not as cool as a cloak of invisibility, a crypto suit is still a pretty good disguise...

## Repercussion on SmartCards? (3, Interesting)

## brainnolo (688900) | about 7 months ago | (#47023791)

## Re:Repercussion on SmartCards? (-1)

## Anonymous Coward | about 7 months ago | (#47023883)

## Re:Repercussion on SmartCards? (1)

## L-One-L-One (173461) | about 7 months ago | (#47023941)

Do you know what PFS is or how it works? Clearly the answer is "NO" but you should educate yourself.

The OP is right: smartcards mostly rely on symmetric algorithms. In fact the OP never said anything about PFS, and bank cards for example, which use RSA, do not implement PFS, because it is not needed in that context.

Do you know what a smart card is and how it works? Clearly the answer is "NO" but you should educate yourself ;-)

## Hold the horses (2)

## WoOS (28173) | about 7 months ago | (#47023991)

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".

## better late than never? (0)

## Anonymous Coward | about 7 months ago | (#47024111)

Apparently, these findings were already being discussed [untruth.org] in UCI Cryptography Seminars back in spring 2013.

## Solved in Sneakers, 1992 (1)

## breadlord (827860) | about 7 months ago | (#47024333)

## Re:Solved in Sneakers, 1992 (0)

## Anonymous Coward | about 7 months ago | (#47028137)

While the number-field sieve is the best method currently known...

If the first number starting each row in Pascal's triangle is used as an exponent of 2 and all of the other numbers in that row divide it without giving a remainder (modulo 0) then the exponent is prime. A modulo 1 or greater indicates the exponent is composite. Granted, it gets immediately large almost from the start, but an alternative solution to the Eratosthenes Sieve does exist.

## Which crypto methods are at risk? (1)

## daniel.benoy (1810984) | about 7 months ago | (#47024563)

Which crypto methods are at risk?

## multiple encryptions (0)

## Anonymous Coward | about 7 months ago | (#47025163)

It occurs to me that all the discussions seem to assume that something is encrypted only once. What happens if you take your document and encrypt it multiple times, using multiple techniques. Only the recipient knows the sequence and how many times each is run. I would think this would make it nigh onto impossible to decrypt. What am I missing?

## Re:multiple encryptions (1)

## mark-t (151149) | about 7 months ago | (#47025549)

## Hype (2, Interesting)

## Anonymous Coward | about 7 months ago | (#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).

## No threat to DH, RSA, DSA; also repost. (0)

## Anonymous Coward | about 7 months ago | (#47026425)

I can't read the article behind Springer's paywall past the first couple of pages, but it appears to be the published version of this 2013 preprint [arxiv.org] which, if I'm not mistaken, was already slashdotted last year.

There would seem to be basically no chance of making this strategy work over the finite field with p elements, which is what it would take to break Diffie-Hellman and DSA as currently implemented; such fields are never going to have sparse medium subfield representations beause they don't have, you know, any subfields.

It's true that similar sieving strategies often apply to factoring as to the DLP - but again, the analogy is to prime field DLPs, so there' s no way that this is going to help break RSA directly. so I don't see any reason for the FUD. We're still a couple of major research ideas away from that.