5
$\begingroup$

My best interpretation of this question is that Java's crypto API has been subverted to perform RSA signature using PKCS#1 v1.5 encryption padding.

Assume the signature $S$ of a message $M$ is obtained by:

  • hashing $M$ using SHA-1, yielding the 20-byte $H$;
  • generating a 105-byte uniformly (true) random $R$;
  • forming the 128-byte $P=\text{0x00}||\text{0x02}||R||\text{0x00}||H$;
  • forming the 128-byte $S=P^d\bmod N$ where $(N,d)$ is a 1024-bit RSA private key.

I assume that verification of an alleged signature $S$ of alleged message $M$ is as follows:

  • rejecting the signature unless $S$ is 128-byte with $S<N$;
  • forming the 128-byte $P=S^e\bmod N$ where $(N,e)$ is the 1024-bit RSA publickey;
  • hashing $M$ using SHA-1, yielding the 20-byte $H$;
  • accepting the signature when the left 2 bytes of $P$ are $\text{0x00}||\text{0x02}$, and the 21th byte from the right of $P$ is $\text{0x00}$, and the right 20 bytes of $P$ are $H$.

Note: conversion from bytestring to number, and vice-versa, is per the big-endian convention.

What attacks are there on this scheme, easier than factoring the public modulus?

$\endgroup$
1
  • 2
    $\begingroup$ I think it would be more interesting to ask about attacks that are easier than factoring the modulus, $\hspace{.4 in}$ even if they are harder than factoring the private key. $\;$ $\endgroup$
    – user991
    Mar 31, 2014 at 13:57

1 Answer 1

4
$\begingroup$

There's an easy attack against public keys with $e=3$.

Here's how it works; the attacker selects an arbitrary message $M$ that hashes to an odd value $H$ (or, more generally, a $H$ of the form $k8^n$ for odd $k$). Since half of the potential messages hash this way, this is not a severe limitation to the attacker.

Then, the attacker looks for a perfect cube between $2\times2^{1008}$ and $3\times 2^{1008}$ and whose lower 136 bits are $0x00 || H$, that is, a cube $C$ between $2\cdot 2^{1008}$ and $3\cdot 2^{1008}$ and for which $C \equiv H\ (\bmod\ 2^{168})$. Such a cube is easy to find, just compute $x = \sqrt[3]{H} (\bmod \ 2^{168})$ (with the $H$ of the form we selected, such a value always exists), and then select a value $X$ in the range $\sqrt[3]{2\cdot 2^{1008}}$ to $\sqrt[3]{3\cdot 2^{1008}}$ with $X \equiv x\ (\bmod\ 2^{168})$; $C = X^3$ is such a cube.

The value $X$ is be a valid signature for the message that hashes to $H$; the verifier will compute $X^3 \bmod N$ (which will be precisely $X^3$, and then verify that the first two bytes are $0x00$ $0x02$, and that the right hand bytes are $0x00$ $H$.

This attack can be generalized (for this key size) to $e=5$, and can be extended to handle the case where the verifier also checks to see if there are any zero pads in the random pad.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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