Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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?

share|improve this question
1  
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. $\;$ –  Ricky Demer Mar 31 at 13:57

1 Answer 1

up vote 3 down vote accepted

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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