Follow @Openwall on Twitter for new release announcements and other news
[<prev] [next>] [<thread-prev] [day] [month] [year] [list]
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.