Why does SSH authentication protocol choose to have the server with the public key send a challenge message encrypted with this public key of the client instead of having the client send a message signed with it's private key along with client ID and have the server verify the signature?
Wouldn't verifying the signature be enough proof that the client really does possess the private key and hence is authenticated?
The server sending an encrypted challenge has a few advantages over the signature-based method you described:
If the server doesn't recognize the client's public key, there's no reason to have the client waste time and energy generating a signature.
The server is not just trying to verify that the person who signed the message has the private key but that the client it is connected to is the one who signed the message. So a signature would need to be of data that could not have been stolen from a separate communication (either with this server or another one).
As described in section 3.4.2.2 of the O'Reilly book on SSH:
The client receives the challenge and decrypts it with the corresponding private key. It then combines the challenge with the session identifier, hashes the result with MD5, and returns the hash value to the server as its response to the challenge. The session identifier is mixed in to bind the authenticator to the current session, protecting against replay attacks taking advantage of weak or compromised random-number generation in creating the challenge.
The hashing operation is there to prevent misuse of the client's private key via the protocol, including a chosen-plaintext attack. If the client simply returns the decrypted challenge instead, a corrupt server can present any data encrypted with the client's public key, and the unsuspecting client dutifully decrypts and returns it. It might be the data-encryption key for an enciphered email message the attacker intercepted. Also, remember that with RSA, "decrypting" some data with the private key is actually the same operation as "signing" it. So the server can supply chosen, unencrypted data to the client as a "challenge," to be signed with the client's private key -- perhaps a document saying, "OWAH TAGU SIAM" or something even more nefarious.
That is, because the server wants to be sure that it the client has the private key, even in a signature based method it would be best for the server to send a random challenge and have that signed, making the process look very similar but without the benefits described above.
I am interpreting your question two ways: (1) "Why doesn't the client generate their own signed message to send to the server?" and (2) "Why doesn't the server send an unencrypted nonce for the client to then sign and send back?"
To answer (1), such a scheme would be susceptible to replay attacks. An adversary need only collect one of these signed messages and would be able to authenticate with the server indefinitely. You may be able to imagine a scheme where the server would keep track of previous authentications and will make sure that future ones are unique, but such a scheme would require much more overhead on the server's side and would still be susceptible to replay if the adversary intercepts one of these signed messages in an instance where it doesn't reach the server.
(2) is more nuanced and maybe someone else will be able to weigh in on it better than I can, but it seems to me that either design might be considered acceptable from a security standpoint.
