跳到正文
研踪PaperTrail
← 研踪 PaperTrail

arXiv:2611.20277 · v1

A Bleichenbacher bit-by-bit oracle attack from partial message knowledge

首次提交 2026-11-16 06:15
版本更新 2026-11-16 06:15
雷达观测 2026-11-17 17:12
arXiv ↗PDF ↗

摘要

Oracle attacks show the importance of a correct implementation of cryptographic standards when translated into code. A notable example is the Bleichenbacher attack on RSA with PKCS#1 v1.5 padding and all the improvements that have been suggested over the decades. This paper shows how an attacker knowing a few least significant bytes of an RSA message can take advantage of a server with an oracle side-channel to decrypt the full message bit by bit. We will consider two oracles that can be tested with chosen ciphertexts: one revealing whether the decrypted message starts with the 00 02 bytes and a second one revealing if the decrypted message is fully PKCS compliant. For an attacker knowing the three least significant bytes of the message, the first oracle provides an attack where one oracle call gives the next least significant bit of the message and the second an attack which requires, with high probability, a small constant number of oracle calls to the oracle, with a constant which depends on the length of the message and the desired probability of success. The attack divides the message bits into two sections, one with the known part and one with the unknown part, and then chooses transformations that will keep the unknown part, except for the last unknown bit, orders of magnitude below the integer coming from the known part. The resulting string either gives a valid padding or not depending on the value of the unknown bit. The attacker can minimize the number of oracle calls at the cost of some local computation. Finally, the same method is adapted to show how it can also be used to extract the few least significant bytes of the message with an increased cost where the main complexity is finding a second valid message with a correct padding starting from the original captured ciphertext.

作者备注:Comments welcome

AI 论文解读

基于摘要 · 非全文审阅

此版本尚未生成 AI 解读。解读由后台任务生成并按论文版本保存,登录后共享已有结果。

版本差异

目前只收录了一个版本。收录下一版后,可以对照标题、作者、分类和摘要。

观测到的版本

相邻记录可能跳过中间版本;首次发现 v2 及以上也会标为版本更新。

v1 · 2026-11-16 06:15 · 最新观测版本

A Bleichenbacher bit-by-bit oracle attack from partial message knowledge

Oracle attacks show the importance of a correct implementation of cryptographic standards when translated into code. A notable example is the Bleichenbacher attack on RSA with PKCS#1 v1.5 padding and all the improvements that have been suggested over the decades. This paper shows how an attacker knowing a few least significant bytes of an RSA message can take advantage of a server with an oracle side-channel to decrypt the full message bit by bit. We will consider two oracles that can be tested with chosen ciphertexts: one revealing whether the decrypted message starts with the 00 02 bytes and a second one revealing if the decrypted message is fully PKCS compliant. For an attacker knowing the three least significant bytes of the message, the first oracle provides an attack where one oracle call gives the next least significant bit of the message and the second an attack which requires, with high probability, a small constant number of oracle calls to the oracle, with a constant which depends on the length of the message and the desired probability of success. The attack divides the message bits into two sections, one with the known part and one with the unknown part, and then chooses transformations that will keep the unknown part, except for the last unknown bit, orders of magnitude below the integer coming from the known part. The resulting string either gives a valid padding or not depending on the value of the unknown bit. The attacker can minimize the number of oracle calls at the cost of some local computation. Finally, the same method is adapted to show how it can also be used to extract the few least significant bytes of the message with an increased cost where the main complexity is finding a second valid message with a correct padding starting from the original captured ciphertext.

查看此版本解读 →查看此版本原文 ↗