
Date: Mon, 21 Dec 2015 21:46:57 +0100 (CET) From: Pavel Kankovsky <peak@...o.troja.mff.cuni.cz> To: owldev@...ts.openwall.com Subject: Re: OpenSSH On Fri, 20 Nov 2015, gremlin@...mlin.ru wrote: > > 2. The hypothetical "spectral weakness" is real, there exists > > a sufficiently large subset of weak elliptical curves, and it > > is feasible to find a weak curve by trial and error. > > Very likely and, theoretically, possible. > However I can't neither prove nor refute that. I do not think it is likely anyone would find a proof that no such subset exists. (After all, we still have no solid proof that factorization and discrete logarithm are hard problems.) On the other hand, were the subset in question to exist, it is quite likely thatsooner or latersomeone would find discover and demonstrate at least a few weak "random" curves. But such discovery has not happened so far. Various weak curves have been found but all of them seem to be confined to welldefined regions. > > But then again, there is also the recent Pythian announcement > > by NSA that we need to get ready for the coming of quantum > > computers and the resulting cryptoapocalypse... > > We? Or our grandsons? We and right now. <http://arstechnica.com/security/2015/08/nsaprepsquantumresistantalgorithmstoheadoffcryptoapocolypse/> One notable detail is the disappearance of 256bit ECC from Suite B. They require at least 384bit ECC now but they still allow 3072bit RSA. This might suggest some adjustment of cryptographical strength is imminent. (Or it might be FUD intented to confuse potential adversaries. Who knows?) > >> It it notoriously difficult to compare the relative strength > >> of symmetric and asymmetric crypto. > > They don't need to be compared, as they serve for different purposes. They might serve different purposes but those particular purposes are often mere parts of one comprensive general purposesuch as to keep your SSH connections secureand it would be quite unfortunate if any part were considerably weaker than other parts. > >> However, it's relatively simple to notice that every additional > >> bit in a key would require at least two transistors (physical > >> areas on the chip) just to store it and much more to process. > > This is a correct observation... but also completely pointless > > because the same thing holds for both an attacker and a legitimate > > user and the whole point of cryptography is to make attacks much > > more expensive than legitimate operations. > > Where legitimate user performs computations once in a single thread, > attacker has to perform them many times in parallel. It is the need to perform them many times that deters attacks. The ability to perform them in parallel is advantageous to the attacker because it allows to use more computing power to save time. Consider an attack against RSA and let us suppose you have replaced, say, your 1024bit keys with new keys that are 2048 bit long. Recall the two relevant rows of the table I sent a while ago: n log_2(L) log_10(L) 1024 86.8 26.1 2048 116.9 35.2 An attack against longer keys is expected to be approximately 2^30 or 10^9 times more expensive than the attack against shorter keys. Any potential factor of two corresponding to the need to store and handle value that are twice as large, is a minor annoyance in this context. > >> IIRC, the DSA used 1024bit keys. Switching to the use of elliptic > >> curves could be a good reason to keep the key size the same, but > >> not to reduce it. > > I am afraid you compare apples to oranges. > > That's normal if you are interested in carbohydrates, vitamins etc. Let me carry that metaphor further and say that is it fallacious to assert that two apples provide more nutritients than one orange because two fruits are more fruits than one fruit. > > traditional DSA with n = 160 and l = 1024 is an example > > of such balanced design providing cca 80 "bits of security". > > s/is/was/ > > Now it's considered weak and even is disabled in SSH by default. It's weak now but it is no less balanced that it was in the past because it has been made weak and obsolete by the increase of available computing power that affected both kinds of attacks equally rather than by a breakthrough that would have made one kind of attack much more efficient that the other. > > There are some more efficient attacks against special and > > presumably rare weak curves. > > I doubt they are rare... most likely, only a small subset of all > curves is really strong. See above. I admit there is some concern about isogenies (an isogeny is a homomorphism with certain special properties). Some isogenies allow computationally tractable reduction of the discrete logarithm problem on one curve to the dlog problem on another curve and any hypothetical weakness of one curve would affect a potentially large set of other isogenous curves. On the other hand, any major breakthrough in the cryptanalysis of elliptic curves would probably provide new means to attack factorization and integer discrete logarithm (viz. the case of Silverman's xedni calculus). > > Also, there is a recent attack by Bernstein & Lange that might > > offer better *amortized* complexity but it does not seem to be > > useful in any practical situation. > > Yet... I have had a closer look at that thing... The attack in question allows you to decrease the cost of one discrete logarithm to 2^(n/3) but you must have already spent 2^(2n/3) to precompute a huge database of partial results. There is absolutely no way this approach would pay off unless you need to compute at least 2^(n/6) dlogs (= insanely many dlogs) in the same group simultaneously. (In fact, the authors themselves do not present the attack as a real threat. Their point is to show how existing measures of complexity fail to take precomputation into account. Read their paper, titled "Nonuniform Cracks in the Concrete: The Power of Free Precomputation", for details. BTW: The paper includes an interesting and perhaps somewhat disturbing result regarding symmetric ciphers.) > But the question was whether to enable ED25519 for server or to keep it > only in client, leaving server RSAonly. Personally, I would keep it on both sides for the time being. It is always possible to disable it in sshd_config, isn't it?  Pavel Kankovsky aka Peak "Que saisje?"
Powered by blists  more mailing lists