对OAEP的野蛮攻击

Question

例如，假设$M_1$是$\operatorname{OAEP}$填充和加密，并且密文为1024字节。如果对手不知何故绕过了加密，并设法获得了$\operatorname{OAEP}(M_1)$的一半位，尽管不可行，但假设在某种程度上可以遍历丢失的512个字节的所有组合。在某个时候，$\operatorname{OAEP}$ decode将成功并给出$M_1$。

解码操作会不止一次成功地给出其他明文，如果是，会成功多少次？

Answer 1

跳过OAEP的细节，只考虑随机密文将有一个有效的全零垫的概率。

对于一个$t$位垫，随机概率是$1/2^t$。强制执行512字节或$512\times8 8$位将导致平均$2^{512\times8}/2^t$有效填充。假设$128$-位零垫，这是$\dots$

$$3.069183e1194$$

就像你说的这是不可能的。理论上，我们知道消息是$2^{512\times8}/2^t$之一。如果您有任何附加的邮件结构，您可能会进一步减少候选人。

另一种看待这个问题的方法是生日装订。其中，它将平均花费$2^{t/2}$随机样本来查找有效的填充。