[Crypto][Python] D.Bleichenbacher attack on RSA PKCS#1, part III

Click for the previous part.

Raising the bar: using OpenSSL

Now I'm going to use the 'real' oracle -- OpenSSL. The code is mostly the same, but it calls openssl executable and also it can use RSA public key in PEM file format. See this and this.

Now tests on random RSA keys. 512 bits, 1024, 2048, 4096 -- all fast. Within one hour on AMD Ryzen 5 3600 6-Core.

512 bits:

...
Valid padding.
new m_lower/m_upper 0x20172f14a7...5461672109 log2=497.0 0x20172f14a7...546167210a log2=497.0
m_lower:
00000000: 00 02 01 72 F1 4A 75 D1  41 E6 0D ED 35 33 E7 3E  ...r.Ju.A...53.>
00000010: 68 14 B4 DB BE 64 07 6C  C5 00 48 65 6C 6C 6F 2C  h....d.l..Hello,
00000020: 20 77 6F 72 6C 64 21 20  48 6F 6C 61 2C 20 6D 75   world! Hola, mu
00000030: 6E 64 6F 21 20 47 75 74  65 6E 20 54 61 67 21 09  ndo! Guten Tag!.
m_upper:
00000000: 00 02 01 72 F1 4A 75 D1  41 E6 0D ED 35 33 E7 3E  ...r.Ju.A...53.>
00000010: 68 14 B4 DB BE 64 07 6C  C5 00 48 65 6C 6C 6F 2C  h....d.l..Hello,
00000020: 20 77 6F 72 6C 64 21 20  48 6F 6C 61 2C 20 6D 75   world! Hola, mu
00000030: 6E 64 6F 21 20 47 75 74  65 6E 20 54 61 67 21 0A  ndo! Guten Tag!.
diff 1
Found! upper:
00000000: 00 02 01 72 F1 4A 75 D1  41 E6 0D ED 35 33 E7 3E  ...r.Ju.A...53.>
00000010: 68 14 B4 DB BE 64 07 6C  C5 00 48 65 6C 6C 6F 2C  h....d.l..Hello,
00000020: 20 77 6F 72 6C 64 21 20  48 6F 6C 61 2C 20 6D 75   world! Hola, mu
00000030: 6E 64 6F 21 20 47 75 74  65 6E 20 54 61 67 21 0A  ndo! Guten Tag!.
With PKCS#1 1.5 padding removed:
00000000: 48 65 6C 6C 6F 2C 20 77  6F 72 6C 64 21 20 48 6F  Hello, world! Ho
00000010: 6C 61 2C 20 6D 75 6E 64  6F 21 20 47 75 74 65 6E  la, mundo! Guten
00000020: 20 54 61 67 21 0A                                  Tag!.
calls_to_oracle 18544

Only 18k calls to openssl!

RSA 1024 bits:

...
With PKCS#1 1.5 padding removed:
00000000: 4C 6F 72 65 6D 20 69 70  73 75 6D 20 64 6F 6C 6F  Lorem ipsum dolo
00000010: 72 20 73 69 74 20 61 6D  65 74 2C 20 63 6F 6E 73  r sit amet, cons
00000020: 65 63 74 65 74 75 72 20  61 64 69 70 69 73 63 69  ectetur adipisci
00000030: 6E 67 20 65 6C 69 74 2C  20 73 65 64 20 64 6F 20  ng elit, sed do
00000040: 65 69 75 73 6D 6F 64 20  74 65 6D 70 6F 72 20 69  eiusmod tempor i
00000050: 6E 63 69 64 69 64 75 6E  74 20 75 74 20 6C 61 62  ncididunt ut lab
00000060: 6F 72 65 2E 2E 2E 0A                              ore....
calls_to_oracle 140747

Only 140k calls to openssl.

2048 bits: 51k calls to openssl! 4096 bits: 66k calls!

But not 256-bits. My AMD spent ~5 hours on it. ~1.1 million calls. What's the problem? Why it's that slow? It's because the smaller the space, the lesser probability of zero byte residing somewhere. The larger the key, the larger the space, and that probability is much higher. The original Bleichenbacher's paper has all the info about probability calculations.

Now the video. Decrypting 2048-bit RSA message. I hope, this can be used in some 'c00l l33t hax0r' movie if fancier font is picked, maybe greenish:

You see, you can use my Python script to decrypt something real. As long as remote server would return the 'invalid padding' error. Despite the fact that all this you read was written by a non-professional crypto-noob like me.


Click for the next part.

(the post first published at 20230123.)


List of my other blog posts.

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.