Textbook-RSA meet-in-the-middle attack against other RSA based schemes?

Question

A “meet-in-the-middle” (not “man-in-the-middle”!) attack on textbook-RSA was presented to me. The only requirements for it was that the attacker gets the output of RSA and the public key, and that the message be the product of 2 numbers of the same magnitude, which apparently happens with 20% probability. (ie: only eavesdropping).

This attack can reduce the attack of a 64-bit message to O(2^34) instead of O(2^64) for exhaustive search. (ie: almost square root of attack time)

The ISO public key encryption scheme has RSA(pk,x) sent "in the clear" as header. So it seems to me that textbook-RSA can be used to recover x, from which Hash(x) gives the symmetric key…

What am I missing here? Could someone clarify please?

Or maybe I do understand correctly, but that meet-in-the-middle attack on textbook-RSA is not that significant (20% chance of achieving sqrt the time of exhaustive search).

edit: Sorry, I made a mistake: the attack can reduce a O(2^64) exhaustive search into O(2^34) attack which is not almost half the time, but almost square root of the exhaustive search time.

meta: I would like to accept answer but I cannot, neither can I add comments

Answer 1

I suspect that the meet-in-the-middle attack you have in mind is what is presented in this answer (or something similar).

If so, then it's not actually correct to say "the only requirement is that the message be a product of 2 numbers of the same magnitude"; the message needs to be a product of two numbers of the same small magnitude.

For example, the attack can work if the message were a product of two 64 bit numbers; however this would imply that the message itself was no longer than 128 bits.

This is a credible attack against textbook RSA used to pass 128 bit messages; however any sane public key encryption method (such as ISO 18033-2) would include padding to make the message presented to the RSA primitive much larger; this completely invalidates this attack.