Since I'm not a very good mathematician, I misunderstood Bleichenbacher's paper and implemented the second step simpler. It just narrows bounds recursively. This works. But I admit that this may be not as efficient as the original Bleichenbacher's idea.
import random, math, sys, os import functools HEADER_BITS=16 BITS=64 """ p=3900617629 q=2378309513 m=0x0002112233445566 """ e=17 n=9276876013626204677 good_c=7799333987906023269 def binlog(x): assert (x>0) return math.log(int(x), 2) B=2**(BITS-HEADER_BITS) _2B=2*B _3B_1=(3*B)-1 m_min=_2B m_max=_3B_1 s1_min=n//m_min s1_max=n//m_max calls_to_oracle=0 # Only header is checked @functools.cache def oracle(c): d=4911287298007382225 plaintext=pow(c, d, n) return (plaintext>>(BITS-HEADER_BITS))==2 def intervals_intersection(i1_s, i1_e, i2_s, i2_e): # https://scicomp.stackexchange.com/questions/26258/the-easiest-way-to-find-intersection-of-two-intervals # check for non-intersecting intervals: if (i2_s > i1_e) or (i1_s > i2_e): # non-intersects return None return max(i1_s, i2_s), min(i1_e, i2_e) def step_1(): t=[] print ("step_1() begin") global calls_to_oracle s=n // _3B_1 #s=2 while True: print("step_1. trying s", hex(s)," \r", end="") rt=oracle(good_c*pow(s, e, n) % n) calls_to_oracle=calls_to_oracle+1 if rt: print ("rt=True") print ("s", hex(s)) print ("overlaps in range (inclusive): ", s//s1_min, (s//s1_max)) for overlaps in range(s//s1_min, (s//s1_max)+1): lower=(_2B+n*overlaps)//s upper=(_3B_1+n*overlaps)//s if lower>=_2B and upper<=_3B_1: print ("m is between:", hex(lower), hex(upper)) print ("lower:", hex(lower)) print ("upper:", hex(lower)) print ("binlog(diff) %.1f" % binlog(upper-lower)) t.append((lower, upper, s)) return t s=s+1 if s-1 == n: assert False def step_2(a, b, s_start): print ("step_2") print ("a (lower)", hex(a)) print ("b (upper)", hex(b)) print ("s_start", hex(s_start)) global calls_to_oracle r_start=2*((b*s_start - _2B) // n) print ("r_start", hex(r_start)) for r in range(r_start, r_start+0x800): # tune this? print ("current r=", hex(r),"\r", end="") # pick s s_lower=(_2B + r*n)//b s_upper=(_3B_1 + r*n)//a for s in range(s_lower, s_upper+1): rt=oracle((good_c*pow(s, e, n)) % n) calls_to_oracle=calls_to_oracle+1 if rt: print ("Oracle called with s", hex(s)) print ("Valid padding.") # input interval - a,b # new interval: new_a=(_2B + r*n)//s # lower new_b=(_3B_1 + r*n)//s # upper tmp=intervals_intersection(a, b, new_a, new_b) if tmp==None: return None m_lower, m_upper=tmp print ("new m_lower/m_upper", hex(m_lower), hex(m_upper)) print ("m_lower:", hex(m_lower)) print ("m_upper:", hex(m_upper)) assert m_upper >= m_lower if m_lower==m_upper: # solution return s, m_lower, m_upper print ("diff", hex(m_upper-m_lower)) return s, m_lower, m_upper print ("Loop finished!") return None bounds=step_1() while True: new_bounds=[] for bound in bounds: lower, upper, s=bound tmp = step_2(lower, upper, s) if tmp!=None: s, lower, upper = tmp if upper-lower<=1: print ("Found! upper:", hex(upper)) print ("calls_to_oracle", calls_to_oracle) exit(0) new_bounds.append((lower, upper, s)) print ("calls_to_oracle", calls_to_oracle) print ("current len(bounds)", len(bounds)) bounds=new_bounds print ("Main loop finished without any result. Error.")
r variable used in all these expressions is like 'how many rounds we walked around n'.
TL;DR: we can decrypt any message using calls to 'oracle' equipped with the private RSA key, that can check padding.
Here we see how we can narrow bounds to the single solution:
... step_2 a (lower) 0x2112233445562 b (upper) 0x2112233445566 s_start 0x464c7467eadc r_start 0x241db6006 Oracle called with s 0x8c98e8d01400 Valid padding. new m_lower/m_upper 0x2112233445564 0x2112233445566 m_lower: 0x2112233445564 m_upper: 0x2112233445566 diff 0x2 calls_to_oracle 21007 current len(bounds) 1 step_2 a (lower) 0x2112233445564 b (upper) 0x2112233445566 s_start 0x8c98e8d01400 r_start 0x483b6c00e Oracle called with s 0x11931d1a06648 Valid padding. new m_lower/m_upper 0x2112233445565 0x2112233445566 m_lower: 0x2112233445565 m_upper: 0x2112233445566 diff 0x1 Found! upper: 0x2112233445566 calls_to_oracle 21011
Only ~21k calls to oracle for a ~48-bit (plaintext) message.
But my oracle is 'relaxed'. In fact, openssl does more. It checks also for the second zero byte after random padding. That zero byte must reside somewhere between random padding and the message. And the (random) padding string must be at least 8 bytes long.
Let's fix our toyish oracle:
# Header checked plus a zero byte required somewhere after >8 bytes of random padding @functools.cache def oracle_real(c): assert isinstance(c, gmpy2.mpz) plaintext=pow(c, d, n) plaintext_b=int(plaintext).to_bytes(length=BITS//8, byteorder="big", signed=False) header=plaintext_b[0:2] if header==b"\x00\x02": idx=search_first_zero_byte(plaintext_b[2:]) if idx>=8 and idx!=len(plaintext_b[2:])-1: # first zero byte is not the last byte return True else: return False else: return False
For full source code, click here. 256-bit RSA already.
Here I use GMP bignum library via Python's GMP bindings. Not that Python's original bignum support is bad. But it's too slow if compared to pure C GMP. And the most work happens here is bignum calculations.
Also, as a side effect, these 'gmpy2' prefixes you see in my source code is good for exploration -- you now clearly see the main data path. The data path where the most important happens.
Now it's all slower, because our 'oracle' is 'tougher' -- it requires more work so that the second zero byte must reside somewhere in the decrypted block.
... step_2 a (lower) 0x2123412345...ff0011222d log2=241.1 b (upper) 0x2123412345...ff00112233 log2=241.1 s_start 0x1a089fc6e1...ff9222ae58 log2=236.7 r_start 0x9d60b261b8...f641984834 log2=223.3 Oracle called with s 0x34113f8dc3...ff2448aba4 log2=237.7 Valid padding. new m_lower/m_upper 0x2123412345...ff00112232 log2=241.1 0x2123412345...ff00112233 log2=241.1 m_lower: 00000000: 00 02 12 34 12 34 56 78 AB CD FF FF 00 11 22 33 ...4.4Vx......"3 00000010: 00 02 12 34 12 34 56 78 AB CD FF FF 00 11 22 32 ...4.4Vx......"2 m_upper: 00000000: 00 02 12 34 12 34 56 78 AB CD FF FF 00 11 22 33 ...4.4Vx......"3 00000010: 00 02 12 34 12 34 56 78 AB CD FF FF 00 11 22 33 ...4.4Vx......"3 diff 1 Found! upper: 00000000: 00 02 12 34 12 34 56 78 AB CD FF FF 00 11 22 33 ...4.4Vx......"3 00000010: 00 02 12 34 12 34 56 78 AB CD FF FF 00 11 22 33 ...4.4Vx......"3 calls_to_oracle 1647198
~1.6 million calls to oracle, not that fast. But we got our 256-bit message decrypted.
Yes, I know about these lousy Disqus ads. Please use adblocker. I would consider to subscribe to 'pro' version of Disqus if the signal/noise ratio in comments would be good enough.