We have the (same) RSA key for verifying a website and for digital signature. A user would send a nonce encrypted using the public key, the websites returns the nonce by decrypting it using the private key. Now let's an attacker wants to have a hash to be encrypted with the website's private key. How could this work? I heard it is possible, but like technically how could this happen?
1 Answer
tl;dr: send to the server $enc(random) \times theHash$, and divide the value that you get back by $random$. That is your forged signature for $theHash$.
Your setup can be summarized as follows: with have a Server S with an RSA private key $(N; d)$, a Client C with the corresponding public key $(N;e)$. Furthermore the client as a value $h$ for which (s)he wishes to get a valid signature under the private key of the server, namely the client wants $h^d \mod N$. Finally the server authenticates itself by proving the knowledge of $d$(i.e computes $q^d \mod N$ where $q$ is possibly an encrypted nonce.
Observations: 1. We can assume that the server somehow checks that none of the queries is $h$, and refuses to decrypt any such query otherwise game over. 2. I wrote possibly because the client in fact doesn't need to send and encrypted query. He could send any value to the server as long as it's an element of $Z/Z_N$.
The attack: the client selects a random value $s$ such that $gcd(N, s) = 1$, and sends to the server the value $q = h\times s^e \mod N$. This is indeed a valid query. Next, the servers send back $\sigma = r^d \mod N = h^d \times s \mod N$. Finally the client computes the signature as $sig = \sigma \times s^{-1} \mod N = h^d \mod N$. So we have the signature that we wanted.
-
$\begingroup$ This is a great explaination, thank you! Now I got it $\endgroup$ Feb 9, 2019 at 14:45