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