tag:blogger.com,1999:blog-3722233.post6037506695705789893..comments2021-05-16T09:01:42.816-05:00Comments on Computational Complexity: this paper from 2015 cracks Diffie-Hellman. What to tell the students?Lance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger7125tag:blogger.com,1999:blog-3722233.post-11714143468695484982019-09-18T17:04:02.628-05:002019-09-18T17:04:02.628-05:00You should have asked the resident cryptographer i...You should have asked the resident cryptographer in your department. =)<br /><br />I think the long answer is that this does not represent a significant practical vulnerability for a combination of many factors:<br />- Cryptographically speaking, many people have transitioned to 256-bit elliptic curves which offer stronger security both in terms of known algorithms as well as in terms of avoiding precomputation attacks.<br /><br />- I believe it would be quite difficult to apply the algorithm from the paper. In particular, I emailed them a few years ago to ask for their code and was told it is not available. The paper does not contain sufficient details on its own to re-implement the algorithms without significant additional work.<br /><br />- Exploiting other flaws is easier.<br />Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-30444788402635765742019-09-16T21:06:05.689-05:002019-09-16T21:06:05.689-05:00P.S. There is a Wikipedia page on the issue which...P.S. There is a Wikipedia page on the issue which indicates that some the default backing out to non-export security standards has been eliminated: https://en.wikipedia.org/wiki/Logjam_(computer_security)Paul Beamehttp://www.cs.washington.edu/people/faculty/beamenoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-7562658609040884202019-09-16T21:03:18.970-05:002019-09-16T21:03:18.970-05:00There has been some rebuttal about this, though I ...There has been some rebuttal about this, though I am not sure of the current status. Maybe the sky is not falling. One instance is the following:<br /><br />http://www.wisdom.weizmann.ac.il/~eyalro/RonenShamirDhReview.pdfPaul Beamehttp://www.cs.washington.edu/people/faculty/beamenoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-26724254731449120822019-09-16T14:40:55.876-05:002019-09-16T14:40:55.876-05:00That sounds like this is STILL a problem and switc...That sounds like this is STILL a problem and switching over to Ellipic Curve would not help much.<br /><br />Is all of that true?GASARCHhttps://www.blogger.com/profile/03615736448441925334noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-81468164890903662002019-09-16T14:40:15.503-05:002019-09-16T14:40:15.503-05:00So to the question of what to tell my students, le...So to the question of what to tell my students, let me<br />run these up the flagpole and see who salutes<br /><br />1) Only applied to groups presented in a certain way---<br />was it a common way people were using DH?<br /><br />2) People COULD switch to Elliptic curve groups--- have people done this?<br /><br />3) Are there a lot of DH protocols being used that should not be?<br /><br />GASARCHhttps://www.blogger.com/profile/03615736448441925334noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-15951034092072992792019-09-16T12:12:45.830-05:002019-09-16T12:12:45.830-05:00> These attacks [against Elliptic Curve DH] ar...> These attacks [against Elliptic Curve DH] are still subexponential, but are $\exp(\sqrt{\log n})$<br /><br />No, they are conjectured to be exponential ~p^.5, where p is the group's order. Otherwise, the recommended parameter size |p| ~ 256 bits would have been grossly inadequate.<br /><br />Regarding the prevalence of securely configured SSL servers out there, by some measure it is about 70%: https://www.ssllabs.com/ssl-pulse/.Anonymoushttps://www.blogger.com/profile/07754918192713194263noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-64500603750534179072019-09-16T11:06:03.777-05:002019-09-16T11:06:03.777-05:00There are two points to make:
1. Number-field sie...There are two points to make:<br /><br />1. Number-field sieve based attacks only work on DH instances over groups presented a particular way. A way to subvert them is to switch to Elliptic Curve DH, which the best known attacks are "generic" attacks (which can be proven to be optimal in the generic group model). These attacks are still subexponential, but are $\exp(\sqrt{\log n})$ instead of $\exp(\sqrt[3]{\log n})$ I believe (the second $\exp(\cdot)$ has some additional $\log\log n$ factors).<br /><br />2. Logjam constituted a precomputation attack on DH instances. Essentially, during the handshake of TLS 1.2 you could "force" a client to use a particular *static* DH group (which you have already done massive precomputation for) essentially because part of the server's initial message isn't signed (so you don't have to break the signature). Part of this is fixed by removing static DH over weak groups from the standard in TLS 1.3 (there used to be static DH over 512 bit group which was intentionally weak to comply with export controls in the early 2000's).<br /><br />Of course, Logjam noticed that even in "non-static" DH problems people tended to use the same groups (I believe for efficiency reasons), so they were "semi-static". This could be fixed by always generating new safe primes, but its much easier to employ the fix mentioned in point #1 and switch to elliptic curve groups (where precomputation is much less useful), which is precisely what TLS 1.3 does.Markhttps://www.blogger.com/profile/17563688458495404020noreply@blogger.com