At a certain point, a decrypting SSH proxy was implemented (70100 I believe?). It appears that the error message above is related to the firewall presenting it's key to the remote device, when the remote device is expecting the client's key. I ran into this with another customer.
Few things to try:
1) If you don't need the decrypting SSH proxy, use a generic proxy instead.
2) Clear the client key from the server, so that it can learn the firewall's key.
Let me know if this makes sense or if you have questions.
As it happens, Matt, we appear to have fixed the problem without implementing either of the changes you suggested.
This Firewall's Application Defense group is "connection settings" (something we have discovered with v8, as all of it's predecessors was more proxy based and would only use the packet filter equivalent of "connection settings" if specifically defined) and so we've changed the App Defense group on this rule to "minimal proxy" and everything has sprung into life.
That is good. Sorry, for some reason I had it in my head that you were at version 7, which is why I suggested the generic proxy.
I am interested though, after changing to the minimal proxy group, does the audit state that you are still using the ssh proxy?
What is interesting is that having just read Sam Leidl's blog about version 8 rules, the fact that we were using the SSH service in these rules should have meant that it was acting as a proxy anyway.
We can only say, based on this experience, that it clearly wasn't - otherwise, why did the change from "connection settings" to "minimal proxy" make it work?
When you use the built-in SSH application you are always using the SSH smart-proxy, as evidenced by the audit message you pasted. You had 'Connection Settings' set as the app. defense and this does not have the 'Use TCP proxy' box checked, but in the audit you are hitting the SSH proxy (cmd: 'sshp').
This probably has to do with the SSH Proxy application defense (the 'connection settings' app. def. group has <None> for SSH and the 'minimal proxy' group has <minimal proxy> selected SSH).
What do these commands give you back?:
$> cf appfilter q profile=ssh service=client_encryption
$> cf appfilter q profile=ssh service=server_encryption
This looks to be a problem in the way the proxy is handling negotiation of the algorithms that will be used to secure the connection. It's like the proxy has no settings configured in the SSH app. defense, or very strict settings (although if you configured strict settings I would have expected a better message, like 'Proxy configured for DSA keys, client sent RSA keys').
I've been trying to reproduce it but I cannot. Would you like to collect data for us in a working then non-working configuration? I would like you to if you can. You can PM me your Grant number and I'll open a ticket and email you directions on what I'd like you to collect. It'd be a simple setup, tcpdumps and audit with 'connection settings' as the App. Def. Group and then the same with 'minimal proxy' as the app. def. group.