How to solve this Baby Bleichenbacher Attack?

Lightening

11/10/23, 5:37 AM

I am trying to solve this problem from https://toc.cryptobook.us/book.pdf. I am having trouble with this question :

(Baby Bleichenbacher attack). Consider an RSA public key (n, e), where n is an RSA modulus, and e is an encryption exponent. For x ∈ Zn, consider the predicate Px : Zn → {0, 1} defined as:

Show that by querying the predicate Px at about log2 n points, it is possible to learn the value of x.

206

1 + 2

cryptanalysis

fgrieu

11/10/23, 6:32 AM

Hint: assume $x<n/2$. What do you learn when submitting $r=2$?

Lightening

11/10/23, 7:36 AM

@fgrieu Assuming x < n/2, if x \in [0, n/4] then P_x(r) will return 0, else it will return 1. I am getting that we are reducing range for possible values of x (we can use something like binary search), but how do we actually learn value of x?

Score:1

Crypto

Sergey Kaunov

11/18/23, 5:44 PM

By definition the starting knowledge is that x is in (0, n) interval. Then you test each power of 2 (incl. zero) as r. Each test tells you the new boundary for the interval to which x belong. If y eq. 1 -- we should drop lower half of the current interval, if it's eq. 0 then we drop upper bound. Let's imagine that for $2^0$ it returns 1, so we know that x is in ($n/2$, n). For the next step ($2^1$) if it returns 0, then x is in ($n/2$, $3n/4$). And so on.

As $P_x(0)$ tells us half of {Z_n} where x belongs, doubling of x let us iteratively calculate the interval (with length 1 in the end of the process) to which x will be wrapping around after each doubling.

PS Never heard term "Baby Bleichenbacher", but it doesn't differs in essence from "RSA parity oracle", which is easy to get a lot of examples, descriptions and discussions around.

+ 0

Elon Musk

I sit in a Tesla and translated this thread with Ai:

EN: How to solve this Baby Bleichenbacher Attack?

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.