# 1024 RSA Hash Signature attack. Forge a valid signature

I have an RSA signature of 1024 bit where i know the following:

1. Public modulus N
2. Public exponent (0x03)
3. Cypher message

## Summary:

An MD5 hash is calculated from a collection of byte and is used as message (M).

Having an hash that is a perfect cube forge a signature accepted as valid will be easy.

## Question:

Can someone give advice to find a pratical way to hashing messages changing ending until their hash will be a perfect cube?

• I don't get the question. MD5 is completely broken and we can easily forge signatures with MD5. Why do you limit yourself to breaking the signature in this way (of course it's easier because you can forge from a given signature, but you still can't use MD5). – Yehuda Lindell Sep 10 '15 at 14:53
• Sorry i don't get the point. MD5 is not completely broken, there are way to find collision but i need to create a Message, find the MD5 hash and see how much away from an int i am. Knowing that i need to edit the last part of the message in order to forge a message that generate an MD5 hash perfectly cube. – Seed3Key Sep 10 '15 at 15:02
• I see. You want to forge a signature without getting any help at all from the signer. But is this purely academic? I wouldn't use this in any case. – Yehuda Lindell Sep 10 '15 at 15:04
• Yes it is academic but I want to forge a valid signature from a choosen message. If you have a way or idea to solve it i will be glad to hear your idea. – Seed3Key Sep 10 '15 at 15:40

A random 128 bit value has a tiny ($2^{-85}$) probability of being a perfect cube, and so that doesn't look like a viable approach. And, you can't control the output of MD5, and so it'll give you effectively random values.
A better way may be to collect a large number of signatures (with their messages); that is, $S_i = M_i^3 \bmod N$ values (where $M_i$ is the MD5 hash of the $i$th message). Then, you would factor each $M_i$, and look for linear combinations of common factors. At the same time, you would hash a large number of messages, and look for a message with an MD5 hash $M$ that can be represented by a linear combination of signed messages $M = M_a^{i_a} M_b^{i_b} ... M_z^{i_z}$. When you find such a linear combintation, you then have the signature for that message $S = S_a^{i_a}S_b^{i_b} ... S_z^{i_z}$