[<prev] [next>] [<thread-prev] [day] [month] [year] [list]
Message-ID: <alpine.LRH.2.02.1511221045240.14147@argo.troja.mff.cuni.cz>
Date: Mon, 21 Dec 2015 21:46:57 +0100 (CET)
From: Pavel Kankovsky <peak@...o.troja.mff.cuni.cz>
To: owl-dev@...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 that--sooner or later--someone 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 well-defined 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 crypto-apocalypse...
>
> We? Or our grandsons?
We and right now.
<http://arstechnica.com/security/2015/08/nsa-preps-quantum-resistant-algorithms-to-head-off-crypto-apocolypse/>
One notable detail is the disappearance of 256-bit ECC from Suite B. They
require at least 384-bit ECC now but they still allow 3072-bit 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 purpose--such as to keep your
SSH connections secure--and 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 1024-bit 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 1024-bit 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
"Non-uniform 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 RSA-only.
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 sais-je?"
Powered by blists - more mailing lists
Confused about mailing lists and their use?
Read about mailing lists on Wikipedia
and check out these
guidelines on proper formatting of your messages.
