Support algorithm subtraction syntax from ssh_config

As per `man ssh_config` for KexAlgorithms, MACs, and similar options:

```
Multiple algorithms must be comma-separated. Alternately if the specified value begins with a '+' character, then the specified methods will be appended to the default set instead of replacing them.  If the specified value begins with a '-' character, then the specified methods (including wildcards) will be removed from the default set instead of replacing them.
```

Without this, having these subtraction options in your SSH config will replace the default algorithms and cause Net::SSH to raise with `Net::SSH::Exception` and "could not settle on host_key algorithm". i.e. it uses `-ssh-rsa` as the algorithm, rather than removing `ssh-rsa` from the algorithm preferences.

2 files changed, 55 insertions, 4 deletions

diff --git a/lib/net/ssh/transport/algorithms.rb b/lib/net/ssh/transport/algorithms.rb
index ed656ee..8126aa6 100644
--- a/lib/net/ssh/transport/algorithms.rb
+++ b/lib/net/ssh/transport/algorithms.rb
@@ -290,10 +290,24 @@ module Net
           list = []
           option = Array(option).compact.uniq
 
-          if option.first && option.first.start_with?('+')
+          if option.first && option.first.start_with?('+', '-')
             list = supported.dup
-            list << option.first[1..-1]
-            list.concat(option[1..-1])
+
+            appends = option.select { |opt| opt.start_with?('+') }.map { |opt| opt[1..-1] }
+            deletions = option.select { |opt| opt.start_with?('-') }.map { |opt| opt[1..-1] }
+
+            list.concat(appends)
+
+            deletions.each do |opt|
+              if opt.include?('*')
+                opt_escaped = Regexp.escape(opt)
+                algo_re = /\A#{opt_escaped.gsub('\*', '[A-Za-z\d\-@\.]*')}\z/
+                list.delete_if { |existing_opt| algo_re.match(existing_opt) }
+              else
+                list.delete(opt)
+              end
+            end
+
             list.uniq!
           else
             list = option
diff --git a/test/transport/test_algorithms.rb b/test/transport/test_algorithms.rb
index 54f5774..105f3af 100644
--- a/test/transport/test_algorithms.rb
+++ b/test/transport/test_algorithms.rb
@@ -99,6 +99,16 @@ module Transport
                    algorithms(kex: %w[bogus diffie-hellman-group1-sha1], append_all_supported_algorithms: true)[:kex]
     end
 
+    def test_constructor_with_preferred_kex_supports_additions
+      assert_equal x25519_kex + ec_kex + %w[diffie-hellman-group-exchange-sha256 diffie-hellman-group14-sha1 diffie-hellman-group-exchange-sha1 diffie-hellman-group1-sha1],
+                   algorithms(kex: %w[+diffie-hellman-group1-sha1])[:kex]
+    end
+
+    def test_constructor_with_preferred_kex_supports_removals_with_wildcard
+      assert_equal x25519_kex + ec_kex + %w[diffie-hellman-group-exchange-sha256],
+                   algorithms(kex: %w[-diffie-hellman-group*-sha1 -diffie-hellman-group-exchange-sha1])[:kex]
+    end
+
     def test_constructor_with_preferred_encryption_should_put_preferred_encryption_first
       assert_equal %w[aes256-cbc aes256-ctr aes192-ctr aes128-ctr aes192-cbc aes128-cbc rijndael-cbc@lysator.liu.se blowfish-ctr blowfish-cbc cast128-ctr cast128-cbc 3des-ctr 3des-cbc idea-cbc none], algorithms(encryption: "aes256-cbc", append_all_supported_algorithms: true)[:encryption]
     end
@@ -111,6 +121,19 @@ module Transport
       assert_equal %w[aes256-cbc aes256-ctr aes192-ctr aes128-ctr aes192-cbc aes128-cbc rijndael-cbc@lysator.liu.se blowfish-ctr blowfish-cbc cast128-ctr cast128-cbc 3des-ctr 3des-cbc idea-cbc none], algorithms(encryption: %w[bogus aes256-cbc], append_all_supported_algorithms: true)[:encryption]
     end
 
+    def test_constructor_with_preferred_encryption_supports_additions
+      # There's nothing we can really append to the set since the default algos
+      # are frozen so this is really just testing that it doesn't do anything
+      # unexpected.
+      assert_equal %w[aes256-ctr aes192-ctr aes128-ctr aes256-cbc aes192-cbc aes128-cbc rijndael-cbc@lysator.liu.se blowfish-ctr blowfish-cbc cast128-ctr cast128-cbc 3des-ctr 3des-cbc idea-cbc none],
+                   algorithms(encryption: %w[+3des-cbc])[:encryption]
+    end
+
+    def test_constructor_with_preferred_encryption_supports_removals_with_wildcard
+      assert_equal %w[aes256-ctr aes192-ctr aes128-ctr cast128-ctr],
+                   algorithms(encryption: %w[-rijndael-cbc@lysator.liu.se -blowfish-* -3des-* -*-cbc -none])[:encryption]
+    end
+
     def test_constructor_with_preferred_hmac_should_put_preferred_hmac_first
       assert_equal %w[hmac-md5-96 hmac-sha2-512-etm@openssh.com hmac-sha2-256-etm@openssh.com hmac-sha2-512 hmac-sha2-256 hmac-sha1 hmac-sha2-512-96 hmac-sha2-256-96 hmac-sha1-96 hmac-ripemd160 hmac-ripemd160@openssh.com hmac-md5 none], algorithms(hmac: "hmac-md5-96", append_all_supported_algorithms: true)[:hmac]
     end
@@ -124,6 +147,16 @@ module Transport
         algorithms(hmac: "unknown hmac-md5-96", append_all_supported_algorithms: true)[:hmac]
     end
 
+    def test_constructor_with_preferred_hmac_supports_additions
+      assert_equal %w[hmac-sha2-512-etm@openssh.com hmac-sha2-256-etm@openssh.com hmac-sha2-512 hmac-sha2-256 hmac-sha1 hmac-sha2-512-96 hmac-sha2-256-96 hmac-sha1-96 hmac-ripemd160 hmac-ripemd160@openssh.com hmac-md5 hmac-md5-96],
+                   algorithms(hmac: %w[+hmac-md5-96 -none])[:hmac]
+    end
+
+    def test_constructor_with_preferred_hmac_supports_removals_with_wildcard
+      assert_equal %w[hmac-sha2-512-etm@openssh.com hmac-sha2-256-etm@openssh.com hmac-sha2-512 hmac-sha2-256 hmac-sha2-512-96 hmac-sha2-256-96 hmac-ripemd160 hmac-ripemd160@openssh.com],
+                   algorithms(hmac: %w[-hmac-sha1* -hmac-md5* -none])[:hmac]
+    end
+
     def test_constructor_with_preferred_compression_should_put_preferred_compression_first
       assert_equal %w[zlib none zlib@openssh.com], algorithms(compression: "zlib", append_all_supported_algorithms: true)[:compression]
     end
@@ -143,11 +176,15 @@ module Transport
       assert_equal %w[none zlib zlib@openssh.com], algorithms(compression: %w[bogus none zlib], append_all_supported_algorithms: true)[:compression]
     end
 
-    def test_constructor_with_append_to_default
+    def test_constructor_with_host_key_append_to_default
       default_host_keys = Net::SSH::Transport::Algorithms::ALGORITHMS[:host_key]
       assert_equal default_host_keys, algorithms(host_key: '+ssh-dss')[:host_key]
     end
 
+    def test_constructor_with_host_key_removals_with_wildcard
+      assert_equal ed_host_keys + %w[ecdsa-sha2-nistp521-cert-v01@openssh.com ecdsa-sha2-nistp384-cert-v01@openssh.com ecdsa-sha2-nistp256-cert-v01@openssh.com ecdsa-sha2-nistp521 ecdsa-sha2-nistp384 ecdsa-sha2-nistp256], algorithms(host_key: %w[-ssh-rsa* -ssh-dss])[:host_key]
+    end
+
     def test_initial_state_should_be_neither_pending_nor_initialized
       assert !algorithms.pending?
       assert !algorithms.initialized?