Bleichenbacher's CCA2 on RSA
A server is giving feedback it's not supposed to. Can you stage an online attack?
Hello There, Is there an optimal choice for the first s ? I have tried random values (but I am sure there is a better choice) for a few hours, with no luck. Any hint ? Thanks
I started with the value
s = ceiling(N / 3B) (
B being defined in the paper as
2^(8 * (k-2)) ). This is the same value as is recommended in Step 2.a of the paper.
I arrive at a valid solution but it is 14 hex characters, and a bunch of 0's padded on the right. They are not ASCII characters and this doesn't resemble a valid padded message. Any thoughts? I wouldn't think a valid solution would be found by accident.
That doesn't sound quite right, you can email us with the specifics if you like. Otherwise I'm not sure there's much I can recommend beside double checking you implemented the algorithm, as described in the paper, correctly
I rewrote basically the exact same algorithm on a python 2.7 machine and got the correct answer. The python 3 version seems to give an incorrect answer. In any case I got it, thanks.
It may have to do with the fact that python 2 will round down to the nearest integer when you divide two integers. Python 3 will actually give you back a float when you divide two integers (use // in 3 to get the behavior of / in 2). In any case, congrats on solving the problem!
Is it expected that the oracle returns 0 on the original ciphertext?
The oracle should be returning a 1 on the given ciphertext, since I've confirmed by factorizing the modulus it's PCKS15 padded. Seems like either the example code from this does not work in python3 or the problem is busted now.
For those who are trying to do this problem offline, I've written a function for Python3 that you can use instead. If the creators are bummed about me posting the private exponent, y'all can hmu and have me remove the post.
def is_padded(cnum): #first we decode it on our end d = 0x519ae77c3b9a12d4f94419fed92658e7ebb1bb6fe660ee234bb1d5e0d7f600441b69501ed308ef59c20fa55a4ef6613 N = 0x4c81390477e071a7a9afd85eeb93f3596cf69fb8e7fadf422f22c68891586611af5e74aa8b4df9a585486898f632ae63 pt = pow(cnum, d, N) #next, convert to bytes plaintext = pt.to_bytes(96//2, 'big') #finally, confirm it's PCKS formatted hasHeader = plaintext == 0 and plaintext == 2 hasDivider = 0 not in plaintext[2:10] and 0 in plaintext[10:] return hasHeader and hasDivider