0
$\begingroup$

Assume $M_1$ is $\operatorname{OAEP}$ padded and encrypted and the ciphertext is 1024 bytes as an example. If an adversary somehow gets around the encryption and manages to get half of the bits of $\operatorname{OAEP}(M_1)$, and although infeasible, assume that it was somehow possible to loop through all combinations of the missing 512 bytes. At some point the $\operatorname{OAEP}$ decode will succeed and give $M_1$.

Will the decode operation succeed more than once to give other plaintexts, and if so, how many times?

$\endgroup$
0
$\begingroup$

Skipping over the OAEP details, considering only the probability that a random ciphertext will have a valid all-zero pad.

For a $t$ bit pad, the random probability is $1/2^t$. Brute forcing 512 bytes or $512\times8$ bits will result in on average $2^{512\times8}/2^t$ valid padding. Assuming a $128$-bit zero pad this is$\dots$

$$3.069183e1194$$

As you said this is impossible. Information theoretically we know the message is one of the $2^{512\times8}/2^t$. If you have any additional structure of the message, you may reduce the candidates further.

Another way to look at this is the birthday bound. Where it'll take on average $2^{t/2}$ random samples to find a valid padding.

$\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.