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