Let's say I need to verify a digital signature and the public key is stored in untrusted storage which I need to fetch before I verify the digital signature. However, I can store the cryptographic hash of the public key in trusted storage and I decide to use the hash to verify the integrity of the public key. Now say I am using RSA PKCS #1 1.5 signature scheme, the public key contains (n, e), i.e., modulus and public exponent.

Here is the questions: Can I compute the only hash of the modulus for integrity? Do I get any security advantage if I compute the hash of the modulus concatenate with the public exponent? Specifically, I wonder what could go wrong if the attacker can change the my public exponent? (Assume the signature is created with public exponent 65537)


Can I compute the only hash of the modulus for integrity?

Well, if we allow the attacker to modify the value of $e$ you use (because it's in untrusted storage and you don't verify it), how can he exploit that? Well, the most obvious approach for him would be to modify $e$ to be the value 1; that would make generating forgeries really quite simple.

Now, if your signature verification software prohibits $e=1$ (and doesn't parse $e=-1$; likely it doesn't); well, it might be safe, as generating alternative values for $e$ where the attacker does know the $d$ value is equivalent to factoring, and there is no other known way to take $e$-th roots that's not equivalent to factoring. This is, of course, assuming that your PKCS #1 1.5 signature verification code does all the checks; if not, then (depending on which checks are skipped) it's known to be possible to generate a forgery that passes the partial checks with $e=3$.

On the other hand, why take the risk? It's easy enough to include $e$ in the hash, and that avoids the question entirely. Alternatively, you can just bolt in $e=65537$ in your verification code; in that case, the attacker can't change it.

  • $\begingroup$ An excellent practical answer. $\endgroup$
    – TonyK
    Dec 1 '15 at 21:05
  • $\begingroup$ How about the attacker sending chosen ciphertexts or plaintexts with varying values of $e$ (assuming a scenario where the attacker can force the cryptographic module to reload $e$ from the breached storage at will)? Could that reveal information that fixed-$e$ attacks wouldn't? $\endgroup$ Dec 1 '15 at 21:35
  • $\begingroup$ @poncho, could you elaborate on the exploitation by changing e to 1-that? It does not seem downright obvious to me. $\endgroup$
    – drdot
    Dec 1 '15 at 21:38
  • $\begingroup$ @dannycrane: RSA signature verification of $S$ works by computing $V=S^e \bmod N$, and then running some checks on the resulting value $V$. The attacker knows what $V$ needs to look like for the signature to pass; if $e=1$, then he can just generate a signature $S$ that is precisely that $V$. $\endgroup$
    – poncho
    Dec 1 '15 at 21:52
  • $\begingroup$ ok. You mean e = 1. I get it :) $\endgroup$
    – drdot
    Dec 1 '15 at 22:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.