I am teaching cryptography this semester for the second time (I taught it in Fall 2019) and will soon tell the students about the paper from 2015:
Imperfect Forward Secrecy: How Diffie-Hellman Fails in Practice. There are 14 authors.
The upshot is that as Diffie-Hellman was implemented in 2015, many cases were crackable. In summary (and probably too simple):
DH in a 512-bit group can be cracked by the authors
DH in a 1024-bit group they speculate can be cracked with nation-state resources.
Is this a big deal? If YES then what is being done, and if NOT then why not?
I have come up with some statements that I DO NOT KNOW if they are true, but I am ASKING you, to shed some light on the BIG DEAL or NO BIG DEAL question. (Note- Idea for a game show: BIG DEAL or NO BIG DEAL where contestants are asked if a news story is a BIG DEAL or not.)
So, please comment on the following question:
1) Since 2015 the people who use DH have upped their game and are now using bigger parameters. (I doubt this is true)
2) DH is mostly not used on things that hackers are not interested in, so this is not a big deal.
3) The expertise required to crack DH via this paper is rather difficult, so hackers don't have the skills.
4) This paper is not a problem for a bad reason: Hackers don't need to use the number field sieve DL algorithm when all they need to do is (1) guess that the pin numer is 1234 or the year the user was born (or close to it), (2) put on a uniform from Geek-Squad or some such organization and claim they are here to help, (3) exploit a known security flaw that the company has not bothered fixing.
5) The 14 authors have mysteriously disappeared. (I doubt this is true.)
(Misc: My spell checker thinks that Diffie and crackable are not words, but Hellman is.)
There are two points to make:
ReplyDelete1. 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).
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).
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.
So to the question of what to tell my students, let me
Deleterun these up the flagpole and see who salutes
1) Only applied to groups presented in a certain way---
was it a common way people were using DH?
2) People COULD switch to Elliptic curve groups--- have people done this?
3) Are there a lot of DH protocols being used that should not be?
> These attacks [against Elliptic Curve DH] are still subexponential, but are $\exp(\sqrt{\log n})$
ReplyDeleteNo, 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.
Regarding the prevalence of securely configured SSL servers out there, by some measure it is about 70%: https://www.ssllabs.com/ssl-pulse/.
That sounds like this is STILL a problem and switching over to Ellipic Curve would not help much.
DeleteIs all of that true?
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:
ReplyDeletehttp://www.wisdom.weizmann.ac.il/~eyalro/RonenShamirDhReview.pdf
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)
ReplyDeleteYou should have asked the resident cryptographer in your department. =)
ReplyDeleteI think the long answer is that this does not represent a significant practical vulnerability for a combination of many factors:
- 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.
- 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.
- Exploiting other flaws is easier.