Follow @Openwall on Twitter for new release announcements and other news
[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Message-ID: <alpine.LRH.2.02.1511161028120.8405@argo.troja.mff.cuni.cz>
Date: Tue, 17 Nov 2015 23:42:14 +0100 (CET)
From: Pavel Kankovsky <peak@...o.troja.mff.cuni.cz>
To: owl-dev@...ts.openwall.com
Subject: Re: OpenSSH

On Mon, 16 Nov 2015, gremlin@...mlin.ru wrote:

> On 2015-11-14 15:25:43 +0100, Pavel Kankovsky wrote:
>
> > What about KexAlgorithms? And DH groups?
>
> For now, it has diffie-hellman-group-exchange-sha256 and
> curve25519-sha256@...ssh.org for server and, additionally,
> diffie-hellman-group-exchange-sha1 and diffie-hellman-group14-sha1
> for client.

Have you modified /etc/ssh/moduli (the list of groups for 
diffie-hellman-group-exchange-*)? The developers seem to have already 
eliminated all DH groups with a modulus shorter than 2048 bits but a 
higher lower limit might be needed to prevent the key exchange from being 
the weakest link.

> >> 4. ECDSA support is fully disabled by CFLAGS="-UOPENSSL_HAS_ECC".
> > Is this intentional?
>
> Yes: ECDH and ECDSA based on NIST curves must not be trusted at all.

If NIST curves have been somehow manipulated then at least one of 
the two following conditions would have to be true:

   1. There is a feasible preimage attack against SHA-1 that makes it
   possible to turn "cooked" parameters back into an X9.62 seed. (Note we
   are talking about preimages rather than collisions here!)

   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.

Moreover, the vulnerabilities must have already been feasible to exploit
in 1990's when the curves were standardized and they must have avoided 
independent discovery for almost 20 years. Possible? Yes. Likely? Umm...
I do not think so. YMMV.

That said, SSH should probably support more curves, perhaps even curves 
with arbitrary parameters (like TLS; see RFC 4492).

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...

> >> 5. RSA keys have minimal size of 4096 bits and default size
> >> of 8192.
> > It it notoriously difficult to compare the relative strength of
> > symmetric and asymmetric crypto.
>
> 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. (In fact, the cost of legitimate RSA operations 
already grows asymptotically faster than the length of keys.)

> That means the cryptoprocessors already used for brute-force attacks 
> would be much more power-consuming, [...]

The difficulty lies in the existence of attacks that are substantially 
more efficient than brute force. For instance, you do not need to resort 
to brute force in order to crack a public RSA keys because you can always 
use GNFS to factorize its modulus N and its expected computational 
complexity is (give or take some constants):

   L = exp[(64/9 ln(N))^(1/3) * (ln(ln(N)))^(2/3)]

You can replace ln(N) with n ln(2) where n is the number of bits of N 
(e.g. log_2(N)). Let me show some results:

n      log_2(L)  log_10(L)
  512       63.9       19.2
1024       86.8       26.1
2048      116.9       35.2
3072      138.7       41.8
4096      156.5       47.1
8196      208.5       62.8

It is obvious the complexity of such attack grows much slower than 2^n 
expected for brute force yet at the same time much faster than the number 
of memory cells (n) needed to handle the values.

BTW: See Kleinjung et al. <https://www.cs.bris.ac.uk/~nigel/cloud-keys/> 
if you would like to convert the abovementioned values to dollars. Their 
2012 estimate of the cost of factorization of 1024 and 2048-bit moduli is 
something in the order of $10^8 and $10^17, respectively. Also, Heninger 
demonstrated the ability to crack a 512-bit modulus for less than $100.

> >> I think of disabling ED25519 [... as it ...] looks intentionally
> >> weakened by reducing the key size beyond good sence,
> > As far as I know Ed25519 is able to provide approximately 128
> > BoS. [...]
> 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.

First, let me note there are two size parameters in DSA because DSA 
operates in a subgroup of a much larger multiplicative group of F_p. Let n 
denote log_2 of the order of the subgroup and l denote log_2 p. The size 
of private keys (as well as the size of message digests to be signed) is n 
while the size of public keys is l. When you say "1024-bit keys" you 
probably talk about the value of l.

The complexity of some attacks depends on n (approx. 2^(n/2)) while the 
complexity of other attacks depends on l (GNFS is the most efficient known 
attack of this kind, therefore the same convoluted formula for its 
complexity applies to both DSA and RSA--see above). Attacks of the first 
kind are more efficient in some cases, attacks of the second kind in other 
cases and there are also balanced cases where neither kind gets much 
advantage--traditional DSA with n = 160 and l = 1024 is an example of such 
balanced design providing cca 80 "bits of security".

On the other hand, there is only one kind of (publicly) known attacks 
against arbitrary elliptic curves and it corresponds to the first kind 
described by the previous paragraph--their complexity depends on the 
square root of the order of the subgroup. (There are some more efficient 
attacks against special and presumably rare weak curves. 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.)

The order of Ed25519 is cca 2^252 and this corresponds to 126 "bits of 
security" (until a major breakthrough makes attacks against ECC more 
efficient).

To sum it up: Ed25519 is likely to be much stronger than traditional DSA 
despite having much shorter public keys. (OTOH, its private keys are 
longer: it's 160 bits for DSA and 256 bits for Ed25519.)

-- 
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.