c48.py

from pals.RSA import RSA, pkcs_115_pad
from pals.utils import bytes_to_int, int_to_bytes
from c47 import RSA_padding_oracle, bleichenbacher

def main(): 
    #setup the environment
    pub, pri = RSA.generate_keys(768)
    o = RSA_padding_oracle(pri)
    m = pkcs_115_pad(b'kick it, CC', o.n, 2)
    c = RSA.encrypt(m, pub)
    #do the attack
    p = bleichenbacher(c, pub, o.oracle)
    #convert to bytes
    p = b'\x00' + int_to_bytes(p)
    #make sure it matches what we encrypted
    assert(p == m)
    #celebrate with that sweet, sweet line to stdout
    print('success')

if __name__ == '__main__':
    main()

'''
Bleichenbacher's PKCS 1.5 Padding Oracle (Complete Case)
Cryptanalytic MVP award
This is an extraordinarily useful attack. PKCS#1v15 padding, despite being totally 
insecure, is the default padding used by RSA implementations. The OAEP standard that 
replaces it is not widely implemented. This attack routinely breaks SSL/TLS.
This is a continuation of challenge #47; it implements the complete BB'98 attack.

Set yourself up the way you did in #47, but this time generate a 768 bit modulus.

To make the attack work with a realistic RSA keypair, you need to reproduce step 2b 
from the paper, and your implementation of Step 3 needs to handle multiple ranges.

The full Bleichenbacher attack works basically like this:

Starting from the smallest 's' that could possibly produce a plaintext bigger than 
2B, iteratively search for an 's' that produces a conformant plaintext.
For our known 's1' and 'n', solve m1=m0s1-rn (again: just a definition of modular 
multiplication) for 'r', the number of times we've wrapped the modulus.
'm0' and 'm1' are unknowns, but we know both are conformant PKCS#1v1.5 plaintexts, 
and so are between [2B,3B].
We substitute the known bounds for both, leaving only 'r' free, and solve for a 
range of possible 'r' values. This range should be small!
Solve m1=m0s1-rn again but this time for 'm0', plugging in each value of 'r' we 
generated in the last step. This gives us new intervals to work with. Rule out any 
interval that is outside 2B,3B.
Repeat the process for successively higher values of 's'. Eventually, this process 
will get us down to just one interval, whereupon we're back to exercise #47.
What happens when we get down to one interval is, we stop blindly incrementing 's'; 
instead, we start rapidly growing 'r' and backing it out to 's' values by solving 
m1=m0s1-rn for 's' instead of 'r' or 'm0'. So much algebra! Make your teenage son 
do it for you! *Note: does not work well in practice*
'''