rsa-sha2-256/512: handling of incorrect signature encoding

Hey everyone,

last month, we released versions 7.xx of Bitvise SSH Server and Client, 
which implement the new rsa-sha2-256 and rsa-sha2-512 signatures.

We thought we worked out any compatibility issues prior to release – the 
algorithms interoperate with the OpenSSH 7.2p2 versions we’ve tried.

However, we’ve now learned of a user who is connecting from Arch Linux using 
OpenSSH 7.2 (without p2), and it appears that this version encodes tha 
rsa-sha2-512 signature (and probably also -256) in a different way than our 
implementation expects.

The problem is related to the multiple instances of algorithm names encoded 
in a “publickey” authentication request. First, the algorithm is encoded in 
the immediate request itself:

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

In this case:

- "public key algorithm name" should be either "rsa-sha2-256" or 
"rsa-sha2-512"

- "public key to be used for authentication" should be an "ssh-rsa" public 
key, like this:

string    "ssh-rsa"
mpint     e
mpint     n

- "signature" should be an "rsa-sha2-256" or "rsa-sha2-512" signature, like 
this:

string    "rsa-sha2-256" / "rsa-sha2-512"
string    rsa_signature_blob

To summarize, there are three algorithm names being encoded, and they are in 
sequence:

(1) "rsa-sha2-256" or "-512" or "ssh-rsa"
(2) "ssh-rsa"
(3) "rsa-sha2-256" or "-512" or "ssh-rsa"

The invariants our implementation currently expects are:
- name 1, in the USERAUTH request, can be any of the RSA signature algorithm 
names
- name 2, in the public key blob, must be "ssh-rsa"
- name 3, in the signature blob, must match name 1

However, what actually happens in OpenSSH 7.2 (not p2) is that name 1 is 
"rsa-sha2-512", but name 3 is "ssh-rsa". This causes a mismatch and an 
authentication failure with our implementation, because name 1 does not 
match name 3.

My questions are:

(A) Should we add "ssh-rsa" - and "ssh-rsa" only, not any other name - as a 
possible alias in name 3, which should be interpreted as an acceptable 
alternative if "rsa-sha2-256" or "rsa-sha2-512" is sent in name 1? Is this 
harmless?

or

(B) Should we deny an attempt to authenticate using mismatched name 1 and 
name 3, and inform the user to look into upgrading their software? Note that 
software often cannot be easily upgraded, and the practical alternative will 
be to disable the new signature algorithms, and continue to use "ssh-rsa".

If we decide to do (A), should we allow "ssh-rsa" to be accepted in ALL 
situations where the verifier has out-of-band knowledge that the actual 
signature algorithm is "rsa-sha2-256" or "-512"?

For example, should a server be able to send an "ssh-rsa" signature that's 
actually "rsa-sha2-512" because the negotiated algorithm is "rsa-sha2-512"? 
Or should the accommodation be restricted to client authentication only?

Regardless of what we think is best - should we put a paragraph about this 
in the rsa-sha2 draft?

denis