# Establish Trust By Signing Random Seed

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.

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.

• Hmm, I'll look at that padding scheme. I guess I should choose a size of M such that it will require padding. Jun 17 '15 at 22:50
• This vulnerability would appear to have always been in this seed-key trust scheme. All I'm doing is trying to establish a simple but secure way authenticate a client that doesn't involve a too-clever-by-half seed-scrambling to generate a key. Out of curiosity, how does one defeat a MITM attack without trusted third parties? It would seem that all the secrets have to be stored on either the client or the server, but since they're all in the same place using one trust anchor or a million doesn't make any difference if they can all be breached during the same event. Jun 17 '15 at 23:11
• If you use RSASSA-PKCS1_V1_5 signatures, you have to have padding; it's built into the protocol. As for how to protect against MITM, one obvious way would be to use the fact that the attacker cannot modify M; for example, do an (EC)DH exchange, and make M one of the public values; with that, the attacker can learn the value of M, but cannot learn the shared secret (and the key we use to encrypt/authenticate the rest of the exchange will be derived from the shared secret) Jun 17 '15 at 23:31
• @MutantPlatypus : $\;\;\;$ One typically sets things up so that the client can verify that the given public key really was what the server choose. $\:$ That applies even if there are no trusted third parties, although you would presumably want to switch "client" with "server" in my previous sentence. $\;\;\;\;$
– user991
Jun 17 '15 at 23:35