Evidence for SHA-1 being a real problem in SSH?

[mgkuhn]

This document has encouraged one of our system administrators to disable any use of SHA-1 in a major SSH server at our site. This has caused compatibility problems, in particular for users of various mobile phone and tablet SSH clients that do not yet support SHA-2.

It would be nice if you could add two things:

a) List which widely used SSH clients are or are not yet compatible with your configuration, to better inform the paranoia-versus-usability trade-off involved.

b) A more detailed discussion of what practical security is actually gained (or not) by disabling SHA-1.

For a) I can note the following:

The Android SSH client ConnectBot version 1.7.1 (the latest version released on Google Play at the time of writing this) only supports the following algorithms:

• src/com/trilead/ssh2/crypto/digest/MAC.java:
  • "hmac-sha1-96", "hmac-sha1", "hmac-md5-96", "hmac-md5"
• src/com/trilead/ssh2/transport/KexManager.java:
• "diffie-hellman-group-exchange-sha1", "diffie-hellman-group14-sha1", "diffie-hellman-group1-sha1"
• src/com/trilead/ssh2/crypto/cipher/BlockCipherFactory.java:
  • "aes256-ctr", "aes192-ctr", "aes128-ctr", "blowfish-ctr", "aes256-cbc", "aes192-cbc", "aes128-cbc", "blowfish-cbc", "3des-ctr", "3des-cbc"

Therefore, any SHA-2-only configuration will not work with it yet.

Likewise, the iOS ssh client "iSSH - SSH / VNC Console, v5.3.2" by Zinger-Soft appears not compatible.

For b), it would be useful to note the following, to put worries about SHA-1 security into perspective:

The property of SHA-1 that is most suspected is its collision resistance, that is the cost for an adversary to find a pair of messages X != Y such that H(X) = H(Y). Collision resistance is of crucial importance in certificate applications, because lack of collision resistance allows an adversary to present one object X to a certification authority and another object Y to the verifier of the resulting certificate or signature. The lack of collision resistance in MD5 was reportedly abused to sign components of the Flame malware. While similar chosen-prefix collisions have not yet been demonstrated for SHA-1, this is one of several events that has caused a drive to phase out the use of SHA-1 in certificates.

However, if you do not use SSH with certificates, then what risks are there from the ~2^60 collision attacks that have been proposed for SHA-1? Where SHA-1 is used inside the HMAC construction, none of the proposed attacks are applicable, because the attacker knows nothing about the internal state or the output of the inner SHA-1 invocation in HMAC. The HMAC construct provides powerful safeguards around the hash function, by putting it into an unknown state and finally passing its output through a pseudo-random function. Another application of SHA-1 in SSH is as part of the digital signatures that authenticate the exchanged Diffie-Hellman parameters. Again, collision-resistance is not essential here, because a collision can only be abused in applications where a digital signature is verified by at least two different parties (which could be shown different X and Y). Without certificates, the digital signatures generated in the SSH protocol are only ever verified once, by the recipient, and therefore there is nothing useful an adversary could do with a collision they have found. A lack of second-preimage resistance would obviously be of much more concern, but the only proposed attack that I am aware of is the one by Kelsey and Scheier, which still costs 2^106 steps, and which can therefore hardly be described as practical.

No doubt, it is very nice to have SHA-2 (and SHA-3!) widely implemented as fall-back options. But I can not yet see anything in the current research literature that would justify breaking compatibility with widely used SSH clients by disabling SHA-1 today, considering that (without certificates) SSH does not rely on the collision resistance of this secure hash function.

Remember that if you disable a security mechanism, some of your users might chose to circumvent this measure by falling back to some even less secure techniques. In particular, HMAC-SHA-1 is very likely to be far more secure than not using SSH at all, if that is the alternative.

Perhaps the document could be structured such that disabling SHA-1 is left as a step for the future, once it has been more widely implemented on mobile OS SSH clients? After all, hmac-sha2-256 was only defined in July 2012 and has a ridiculously-long digest length of 32 bytes.

[stribika-rdonly]

You are correct, SHA-1 collisions are not sufficient to break HMAC-SHA-1. I have no new attacks. Even HMAC-MD5 is safe. I did consider attacks on the hash function used as a KDF after the key exchange and in RSA signatures as well. To attack "SHA-1 as KDF" you need a preimage attack that works even if you only control part of the input. You can't really attack "SHA-1 in RSA" because of how the protocol works, you have to attack the entire construct: rsa_sign(sk, sha1(data_from_authenticated_server || sha2(shared_secret || attacker_controlled_data))).

However, I know it is somehow possible to break SSH so I recommend against using any algorithm that shows the slightest sign of weakness. They may not be a attacking the primitives but implementation flaws. So I recommend disabling stuff that's hard to implement. They may be exploiting weak RNGs, etc.

I chose paranoia over compatibility at every opportunity when I wrote this. The compatibility problems are listed here and I will add this information regarding ConnectBot and mention mobile clients in general on the main page when I get home. By the way, they are working on it.

I don't think these compatibility problems as serious as with TLS for example. SSH has important advantages in this area.

• No fallback to plaintext. Servers are not running telnet anymore and even if they were the fallback is not automatic.
• If you are a company, you typically control both ends of the connection. If you are using it at home, you also control both ends. There are of course exceptions, such as services offered publicly, like github.
• Users are skilled enough to upgrade or reconfigure their clients. They are expected to manage a server after all. This is not necessarily true for tunneling.

Large scale server upgrades and even config changes are painful though. If you have tens of thousands of servers, you have to make the change process very resilient to low memory, low diskspace, out of PIDs, power loss, race conditions, etc.

What's wrong with 32 byte digest length?

[rhyven]

It's worth mentioning that the JuiceSSH Android SSH client has some improvements over ConnectBot, and supports diffie-hellman-group-exchange-sha256 + aes256-ctr + hmac-sha2-256.

It was so good I paid for it with my own actual money.

[mgkuhn]

What's wrong with 32 byte digest length?

Assuming your adversary has a 10 Gbit/s line to your server and you use (instead of SSH) a hypothetical worst-case protocol that contains nothing but MACs, and the adversary can send you MACs at full line rate and they win this game as soon as they guess one single MAC right. Then they still need

  (2^64)*64/10e9/3600/24/365.25 = 3741 years

to try all 64-bit MACs. They need 24 trillion years to try all 96-bit MACs.

For SSH, the maximum attack rate is orders of magnitude slower than for the above hypothetical protocol, due to the TCP 3-way handshake and many many other obstacles (not least the CPU speed of the attacked server, the rest of the protocol, etc.).

I felt perfectly safe if my SSH data were protected by 64-bit (8-byte) MACs. I'm happy to tolerate the minor overhead of 96-bit (12-byte) MACs, to keep even the clinically paranoid truly at peace.

If you are worried about MAC collisions: these might happen with a 96-bit MAC if you have a single SSH session that transfers more than 2^48 = 281 trillion MACs under the same session key. Doesn't sound like a realistic application. It is not clear to me, where MAC collisions are a concern in SSH, i.e. where does SSH give an adversary oracle access to the MAC of my session key? But I am happy to be conservative, and the safety margin of a 96-bit MAC still looks very decent here.

People who standardize 256-bit (32-byte) and 512-bit (64-byte) MACs simply don't know what they are doing. Never use encryption schemes proposed by people who may not have understood the difference between offline and online attacks. I can't even see a post-quantum justification for why such long MACs might have any benefit. Neither were the authors of RFC 6668 able to give any.

Also, for some MAC schemes, it is safer to have the MAC much shorter than the internal state of the hash function used, such that an adversary with oracle access to the MAC is not able to recognize internal collisions of the hash function. (That's also one reason why sponge functions have become fashionable, such as SHA-3. If you really wanted a new, state of the art MAC, just try SHA-3, where all these things are automatically taken care of for you. Unlike Merkle–Damgård constructions such as SHA-1 and SHA-2, sponge functions like SHA-3 don't even require HMAC.)

[mgkuhn]

@rhyven Should worries about SHA-1 really outweigh worries about using a closed-source implementation?

[rhyven]

Ah yes, great point, and two separate issues:

• It is genuinely a fantastic client, far better than ConnectBot, even if you don't care about SHA1 & the rest of it. But it is closed source...
• You have a very good point about open vs closed source. It sounds like you see more danger in closed source than in weaker hashing functions, and you clearly have enough knowledge to be comfortable with SHA-1.

I don't have enough background in security to make that call, but your post has inspired me to do some reading. Thanks!

[rhyven]

A bit of reading brought me to this post by applied mathematician, Aaron Toponce:

https://pthree.org/2014/03/06/the-reality-of-sha1/

And this one by Eric Mill:
https://konklone.com/post/why-google-is-hurrying-the-web-to-kill-sha-1

Still reserving judgement re closed source vs sha1, but I think it's pretty clear that sha1 is on its' last legs. I do understand your comments about the MAC being perfectly safe, so perhaps it's not pressing enough to move from ConnectBot to JuiceSSH. Guess it's just an end-user decision re what they're least comfortable with.

[mgkuhn]

@stribika-rdonly: Of course it is possible to break SSH. All you need are users who accept host keys without verifying them independently, and then SSH is instantly very vulnerable to many forms of middle-person attacks. I would not be surprised if SSH is used that way by most users, because manually verifying host-key fingerprints is tedious and not essential to get connectivity. That's why probably only few people do it properly, and that's why determined attackers may often find it not that difficult to get around SSH in practice.

A much more useful contribution to hardening SSH would be to implement more widely convenient ways to validate SSH host-key fingerprints, e.g. via DNSSec/SSHFP (which again needs to be set up properly).

I really can't see how the NSA or anyone else might break SSH via SHA-1 being permitted in the server's configuration, or via the MAC being much less than 256 bits long ...

[mgkuhn]

Mihir Bellare, one of the inventors of HMAC, recently published in the Journal of Cryptology, October 2015, Volume 28, Issue 4, pp 844-878, a paper “New proofs for NMAC and HMAC: security without collision resistance” (DOI: 10.1007/s00145-014-9185-x) that contains an improved security proof for HMAC that no longer relies on the assumption that the iterated hash function used is weakly collision resistant. That means that collision attacks on MD5 and SHA-1 really do not affect the security of HMAC-SHA-1 or HMAC-MD5, which are therefore still considered good practical pseudo-random functions.

http://link.springer.com/article/10.1007/s00145-014-9185-x

[markhahn]

Old thread, but it's worth noting that not all SSH use is for system administration. Pretty much all academic computing (by profs, students, etc) takes place using SSH to remote clusters, and being high-handed in deprecating features does cause a lot of unnecessary disruption and support effort. Such user bases can easily be in the tens of thousands, and feature technical expertise (in this domain) no greater than random members of the public...

[jauderho]

As of OpenSSH 8.2, the team appears to moving towards deprecating ssh-rsa.

See https://www.openssh.com/releasenotes.html#8.2

It is now possible[1] to perform chosen-prefix attacks against the
SHA-1 hash algorithm for less than USD$50K. For this reason, we will
be disabling the "ssh-rsa" public key signature algorithm that depends
on SHA-1 by default in a near-future release.