Establish Trust By Signing Random Seed

Question

I'm trying to get my server to establish trust with a client. Neither is on the Internet, so there are no certificate authorities. The typical way to establish trust in my domain is for a client to "request a seed", the server provides a seed, and the client "provides a key", and the server "verifies the key". (In case you are curious: ISO 14229-1, Unified Diagnostic Services) There is no required way to generate either the seed or the key, or to verify it.

Assuming I can properly generate an RSA asymmetric key pair and distribute it, the server holds the public key (n, e) and the client holds the private key K. Assume good cryptographic hashes, strong random number generators, appropriate retry timeouts to prevent replay attacks, etc.

Is the private key vulnerable in the following scheme?

1. Server provides the seed: A random number M.
2. Client signs said seed (S = RSASSA-PKCS1-V1_5-SIGN(K,M)) and sends the signature to the server.
3. The server verifies that signature (RSASSA-PKCS1-V1_5-VERIFY ((n, e), M, S)).
4. If the signature could be verified with the public key, then the client can be trusted.

I'm worried about a known-plaintext attack: I see the private key getting mixed into the signature, unlike with encryption where only the public key is mixed into the output.

Answer 1

If you can recover the private key from a message and a signature (and the public key), then that signature method is broken, and broken quite bad.

We believe that RSA, with a decent signature padding method, is secure, and hence the specific failure mode you mentioned cannot happen.

There are two obvious ways to try to recover the private key for RSA; we believe that both are infeasible.

In the first one, we have the padded value of M (note: RSASSA-PKCS1_V1_5 has deterministic padding, so we always know that Pad(M) looks like, and we have the signature S; we could try to find the value $d$ where $Pad(M)^d = S \pmod{N}$, d would be the private key. However, this is a discrete log problem; we believe that is difficult

In the second one, we could try to factor the public modulus $N$; if we could, then we could compute $d = e^{-1} \pmod{lcm(p-1,q-1)}$, and that would be the private key. However, we believe that factoring a number the size of N is difficult.

One thing that might be an issue is a man-in-the-middle; if there is something between the client and the server; the server sends M to the man-in-the-middle, who forwards it to the client; the client returns the signature to the man-in-the-middle, who forwards it to the server. The server thinks it has authenticated the client, but if the man-in-the-middle can then send its own requests to server, it hasn't really.

It might be that the larger protocol has protections against this sort of thing; however that's what I would be worried about.