1
$\begingroup$

I am trying to understand (in the frame of exponent 3) how to calculate a "forgery" in the case where the desired result is:

xxxxxxxxxxx[...]xxxxxxxxxxxxxxxxxxxxHHHHHHHHHHH[...]HHHHHHHH

where HH = a 160 bit hash which are the least significant bytes, and xx are the remaining (1024-160) bits where I could put "garbage".

From: Is this Bleichenbacher '06 style signature forgery possible? (Or more like, why isn't it?)

I understand that the hash must either have lsbit = 1 or the there must be multiples of 0 bits in 3's to assure a cube root is theoretically possible.

(I do not have "reputation" so I cannot comment in that thread)

That is trivial as I can simply re-request the challenge and test its hash to see if the value has those characteristics.

A traditional Bleichenbacher with the hash farther toward the msbit end with garbage space available to the less significant end is trivial.

Effectively trying to find x where: $$x^3\pmod{2^{128}} = h$$

Thoughts?

$\endgroup$
5
$\begingroup$

When $\gcd(e, \phi(n)) = 1$, integers modulo $n$ coprime to $n$ have a unique $e$th root modulo $n$. This is the basis of RSA. Unlike for an unfactored RSA modulus, $\phi(2^{160})$ is easy to compute: it's $2^{159}$.

You can calculate this cube root the same way that you do RSA, essentially. Treat $2^{160}$ as if it were an RSA modulus, with $e = 3$. Calculate $d = e^{-1} \pmod {2^{159}}$, which is the value:

$d = 243583606221817153033947472119380503275988757163$.

Now, for numbers $h$ coprime to $2^{160}$--that is, odd numbers--you can calculate the cube root as:

$x \equiv \sqrt[3]h \equiv h^d \pmod {2^{160}}$.

Because $x < 2^{160}$, $x^3$ cannot exceed $2^{480}$, so it will not wrap modulo a 1024-bit RSA modulus $n$. $x^3 \mod n$ as calculated by a signature verifier would retain the property that $x^3 \equiv h \pmod {2^{160}}$, and your forgery is complete.

Assuming that your hash's low bit is $1$, anyway.

$\endgroup$

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.