SSH: reusing public keys and known-man-in-the-middle

Usually, people recommend to use a single private-public key pair everywhere (if we're not talking about a possibility of compromising the private key)

Note that there are two key pairs involved in an SSH connection:

• one to identify the server host (the server has the private key);
• one to identify the user (the client has the private key), if using public key authentication.

The recommendations you cite are about user keys. Having a single private key per user is a viable model, though I don't particularly recommend it (the cost of having separate key pairs per host or site isn't that high). Server keys, on the other hand, are never duplicated. They are generated afresh when the SSH server is installed.

On this topic, beyond the posts you've cited in your question, see also What is the difference between authorized_keys and known_hosts file for SSH?

In the attack you describe, you've mixed up the roles of the keys. These are the host keys, ssh_host_rsa, and not user keys. This isn't directly relevant in how the attack you describe works, but may be part of your confusion.

The sticky point is at step 3.3:

PC1 accepts S1_id_rsa.pub's fingerprint (as it's known)

There are two cases.

• If PC1 has connected to S2 before, then PC1 (or more precisely the account of the user on PC1) has memorized S2's host public key in its known_hosts file. So if S1 sends S2's host key, the SSH client on PC1 will detect that the purported host key does not match the recorded host key and abort the connection with a scary message:

  @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
  @    WARNING: REMOTE HOST IDENTIFICATION HAS CHANGED!     @
  @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
  IT IS POSSIBLE THAT SOMEONE IS DOING SOMETHING NASTY!
  Someone could be eavesdropping on you right now (man-in-the-middle attack)!
  It is also possible that the RSA host key has just been changed.
  

  The attack is thus impossible in this scenario (unless the user goes out of his way to bypass the check — OpenSSH purposefully makes this difficult).

• If PC1 has never connected to S2, then PC1 will happily accept whatever S1 is now telling it is S2's key. Since PC1 has no prior knowledge of any association between the name S2 and a cryptographic identity, nor any way to contact a trusted third party who knows such an association (i.e. a public-key infrastructure), there is no way to prevent this man-in-the-middle attack.

Finally, I think I got it.

First of all - I've mixed up ssh v1 and ssh v2 protocols in my description. The challenge-response authorization is from ssh v1.

In ssh v2 client simply signs a specific package with his private key and server checks it using stored public key. This package is described in rfc, here:

To perform actual authentication, the client MAY then send a
signature generated using the private key.  The client MAY send the
signature directly without first verifying whether the key is
acceptable.  The signature is sent using the following packet:

  byte      SSH_MSG_USERAUTH_REQUEST
  string    user name
  string    service name
  string    "publickey"
  boolean   TRUE
  string    public key algorithm name
  string    public key to be used for authentication
  string    signature

The value of 'signature' is a signature by the corresponding private
key over the following data, in the following order:

  string    session identifier
  byte      SSH_MSG_USERAUTH_REQUEST
  string    user name
  string    service name
  string    "publickey"
  boolean   TRUE
  string    public key algorithm name
  string    public key to be used for authentication

So, the signed package contains "session identifier" which is calculated as follows:

  H = hash(V_C || V_S || I_C || I_S || K_S || e || f || K)
  <…..>
  mpint     K, the shared secret  

That is, signature does depend on shared secret, and shared secrets are different for P1<->S1 and S1<->S2 tunnels.