3
$\begingroup$

As Bleichenbacher states, a wrong implementation of the parsing function of the padding could lead to a signature forgery attack when using a low exponent.

In the provided example he assumes the attacker has the freedom to put chosen bytes in the "garbage" section at the end of the message, in order to create a perfect cube root.

00 01 FF FF ... FF 00  ASN.1  HASH  GARBAGE

I wonder if this attack, or any variants, could be generalized to the case where the GARBAGE (eg. the chosen bytes) is not at the end of the message. In general, let say we only have a few "free" bytes we can play with, in the middle of the message:

00 01 FF FF ... FF 00  ASN.1  HASH  FREE_1 00 00 ... 00 FREE_2 ... 00 ... FREE_N

Is it possible to efficiently (not by bruteforce) choose them in order to produce a fake signature? If yes, how many free bytes are needed to make it working and feasable?

[EDIT]

Example: Let say we have exactly 5 free bytes available, marked as XX. HH is a byte of some hash. All the others are fixed values (hex) we cannot change. Of course we can play a bit with the hash itself.

00 01 FF FF FF FF FF FF FF FF 00
HH HH HH HH HH HH HH HH HH HH HH HH HH HH HH HH HH HH HH HH
XX XX
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
XX XX
00 00
AA BB CC DD
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
XX
$\endgroup$
5
  • 1
    $\begingroup$ Note that the garbage at the end isn't supported by common errors in the verification library (where the hash would be expected to be at the end), nor was it necessary for the attack - an arbitrary hash value has a probability circa $4/7$ of making things the attacker needs a perfect cube, hence if the first message he tries to forge with doesn't work, he just tries a second one... $\endgroup$
    – poncho
    Dec 9, 2022 at 12:04
  • $\begingroup$ My reading of @poncho's comment is that the format enforced by the buggy code traditionally targeted is more on the tune of [00 [01 [FF…]]] GARBAGE [[00] ASN.1] HASH and then about $4/7$ (for $e=3$) of hashes enable an attack, for large enough public modulus. $\endgroup$
    – fgrieu
    Dec 9, 2022 at 17:26
  • $\begingroup$ @poncho Maybe I'm misunderstanding the point. How does this apply to the case in the question? In this generic case the hash is left justified and there are N single sparse (not contiguous) garbage bytes. I'm not asking about standard libraries. $\endgroup$
    – supergiox
    Dec 12, 2022 at 9:40
  • $\begingroup$ The answer will depend on parameters: location and size of the FREE_J, size of ASN.1 and HASH, minimum size of [FF FF … FF], size of the public modulus. Do you have a typical setup ? $\endgroup$
    – fgrieu
    Dec 12, 2022 at 14:01
  • 1
    $\begingroup$ @fgrieu I added a practical example in the question. $\endgroup$
    – supergiox
    Dec 12, 2022 at 14:28

1 Answer 1

1
+50
$\begingroup$

Bleichenbacher'06 attack can't be extended to the case at hand.

BB'06 attack with $e=3$ revolves on having the message representative $r$ (of format imposed by the 9 lines in the question's example) a cube of some integer $s$. Here the message representative $r$ is 128 bytes starting in 00 01 FF FF, with the $15$ leading bits at $0$ and several next ones at in, thus $r\lesssim2^{8\times128-15}=2^{1009}$, thus $s\lesssim2^{1009/3}$. More generally, for an $n$-bit RSA public modulus, the RSASSA-PKCS1-v1_5 message representative $r$ is $n'=8\,\lceil n/8\rceil-15$-bit, and just below $2^{n'}$, thus $s$ is just below $2^{n'/3}$. The BB'06 attacker's problem is finding a message and values XX such that $r=s^3$ for some $x$.

The derivative of $s^3$ w.r.t. $s$ is $3\,s^2$, therefore perfect cubes near $r$ are spaced about $3\,s^2=3\times2^{2\times1009/3}$. There are only $40$ bits in the free XX bytes that an adversary can choose, thus for a given hash only one chance in $2^{2\times1009/3-40}/3\approx2^{634.25}$ that suitable XX bytes exist if we don't use the fact there are many zeroes in the message representative.

That generalizes to: for an $n'$-bit message representative and arbitrary data imposed, we need at least in the order of $2\,n'/3$ free bits for the BB'06 attack to apply (and then their location can make the attack harder).

More rigorous argument: The last four lines in the example require that for some $x$ with $0\le x<2^8$ it holds $s^3\equiv\mathtt{0xAABBCCDD}\times2^{456}+x\pmod{2^{504}}$. If we exclude $x=0$, that leaves few values for $(x,s\bmod2^{504})$, that we can efficiently find and count: there are $224$, with haphazard values of $s\bmod2^{504}$, none of which less than $2^{1009/3}$ as required. Thus if there was a solution that's for $x=0$, thus the XX byte on the last line must be 00, and $s\equiv0\pmod2^{152}$. I'm quite confident that the last 32 free bits we have won't be enough to find a solution to the now haphazard-enough problem that we face (to be continued: I'm currently struggling at determining if there are solutions to $t^3\equiv\mathtt{0xAABBCCDD}\times2^{304}\pmod{2^{352}}$, where $s=t2^{152}\,$)


The question's example does not match the format described earlier in the question: there's no ASN.1 in the example, and (more importantly to the attempted rigorous argument) the example's AA BB CC DD is not in the format describedt.

$\endgroup$
2
  • $\begingroup$ The message representative is 128 bytes. Where does that 1009 exponent comes from? And why the density is $2^{2\times1009/3}$ ? Some resources would be appreciated. $\endgroup$
    – supergiox
    Dec 12, 2022 at 18:14
  • $\begingroup$ @supergiox: fixed yet more mistakes. Only the order of magnitude of $2^{2\times1009/3}$ was right. $\endgroup$
    – fgrieu
    Dec 13, 2022 at 6:15

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.