[Crypto] Public signature of challenges as authentication
Solution 1:
What issues is there with this approach?
There are both theoretical and practical concerns with this kind of solution.
First, it is generally not seen as a good idea these days to just sign whatever the somebody else handed you, especially if you also use the signing key in other contexts. This is to prevent an attacker from sending you a "challenge" like "you, lurscher, authorize a wire transfer to me, SEJPM, with a value of 10k USD" and then me presenting this to your bank. There are ways to fix this problem though.
The more practical concerns though are usually more important in this context. Namely: Most servers simply don't have have a public key they are sure is associated with a given user. And if they do, how long do you think it will take until users start complaining or loosing their private keys? Using good old static authenticators (like passwords) is simpler. Additionally, from a server's perspective there is typically very little extra security gained from such an involved authentication strategy. You already assuming a secure channel after all and I can't think of a scenario right now where standard password transmission over HTTPS with server-side (basic) hashing would be significantly more secure than a public-key based solution (in a web context).
Outside of web contexts, yes, authenticating both parties with a public key is a viable strategy which is why TLS has built-in support to do so.
Solution 2:
a simple authentication protocol would be to send a long random string challenge, and get the client to sign it
Well, yes. This is the most common way to do authentication challenges. However, the protocol you describe has a major flaw: all it guarantees is that the client has seen and accepted the random challenge. This guarantees that the client was alive and responding at some point after the challenge was emitted: using a random challenge practically guarantees that the challenge is unique, and therefore the protocol is not vulnerable to a replay attack. But it doesn't guarantee that the challenger is actually talking to the client. A man-in-the-middle could have relayed the challenge and its response.
If you rely on HTTPS to send the challenge, most MitM attack surface is removed, am I correct?
Maybe. If the challenged party is already authenticated, then yes. But then, if the challenged party is already authenticated, why would you want to authenticate it again? There is a scenario where this makes sense, which is if you want the challenged party to prove that it has a second identity. For example, you've made a connection to a machine and authenticated it, and now you want to authenticate a specific user of that machine. But other than that, it's redundant.
Now suppose you have a TLS connection where only the server is authenticated, and the server sends a random nonce, and the client signs it. This only validates that the legitimate client was willing to sign the nonce. It might have been willing to sign the same nonce when talking to another server, too. So you can't in general rely on this to authenticate the client. This only works if you're sure that the client will only ever use its key to authenticate with one specific server.
there must be some weaknesses in the above protocol that I am ignoring.
As I explained above, the weakness is that signing a random challenge only verifies that the challenger was willing to sign this string, which is not very useful. Generally speaking, if you want assurance about some property, the signature has to encompass all the information you want assurance about (except for the identity of the signing party, which is implicitly embedded in the signature). A random challenge is necessary to avoid replay attacks, but it is not sufficient. If you rely on the signature to establish a secure channel, for example, all the parameters that went into the channel setup must be encoded in the message that is signed: configuration parameters, random nonces, ephemeral keys, etc. This is said to bind the signature to those parameters. In particular, if the channel setup uses some form of key exchange (typically Diffie-Hellman) to set up a session key, the public keys are included in the message to be signed. This guarantees that the signature was made specifically for this session, and is not being replayed by a man-in-the-middle (which would have a signature made for the legitimate client's public key and the MitM's public key, instead of the legitimate client's public key and the legitimate server's public key).
When setting up a secure channel, the authentication signatures are typically done over a transcript, i.e. an unambiguous encoding of all the messages sent so far. In TLS, the signature is sent in CertificateVerify messages (TLS 1.2, TLS 1.3).
Since most of authentication still relies on more sophisticated protocols like sending some form of secret over the tubes and verifying it in the server,
No, that's not how “most” of authentication works. Server and client authentication in TLS don't work like that. User authentication with protocols such as OAuth doesn't work like that. Classic password authentication authentication works like that, but PAKE (password-authenticated key exchange) protocols don't work like that (the two sides negotiate shared secret that is only shared if the client used the correct password, without having the client reveal the password to the server). HTTP cookie-based authentication can work like that.