What’s So Special About PKCS#1 v1.5?And The Attack That Just Won’t Go Away!

What’s So Special About PKCS#1 v1.5? And The Attack That Just Won’t Go Away!

RSA has been with us for many decades, and it’s still going strong. But it has weaknesses. The first is where we have a short message and the second is where we have a small value of e. To recap, in traditional RSA, we take the message of m, and an encryption key value e, along with a modulus of N, to give a cipher message of:

c = m^e (mod N)

To decrypt we use a value of d, to recover the message:

m = c^d (mod N)

The value of N is the product to two large prime numbers (p and q).

Short messages

If I use a small value of m, and which is less than N, we will end up with a discrete log problem, and where:

m^e = c

log (m^e) = log(c)

e log (m) = log ( c)

log (m) = log (c ) /e

m = Inv Log (log ( c) /e)

Here is the demo of this cracking:

An outline of the code used is:

import math
import sys

p=14222331744261730109
q=6549179332223292769

message=5
e=7

N=p*q

Cipher=(message**e) % N
print 'Message=',message
print 'N=',N
print 'e=',e
print 'Cipher=',Cipher
print '=============='

Message = 10**(math.log10(Cipher)/e)
print 'Message is:',int(round(Message)), ' Calculated from log10(Cipher/e)'
if ((message**e) > N):
	print 'Method will not work as M^e is larger than N'

The following gives a sample run:

Message= 5
p= 14222331744261730109
q= 6549179332223292769
N= 93144601115542176265237708764769281821
e= 7
Cipher= 78125
==============
Message is: 5  Calculated from log10(Cipher/e)

We can also have a problem when we have a small value of e, such as e=3.

PKCS#1 v1.5

PKCS#1 v1.5 aims to address the issues of small messages in RSA. With this we pad the message with random string (r):

x = 0x00 || 0x02 || r || 0x00 || m

and then the cipher becomes:

c = x^e (mod N)

The length of random value (r) is k-Len-3 bytes, and where k is the number of bytes in modulus (N), and Len is the number of bytes in the message. In this way we pad short messages, in order for the value of x to be large enough to make sure it is not possible to easily reverse the cipher for short messages. The receiver then derives the value of x. It then detects the 0x0 and 0x2 at the start of the value,and then removes the padding.

If you are interested, PKCS-15 also solves the Coppersmith’s Short Pad Attack [here] and the Hastad broadcast attack (and where the same message received by e recipients, results in a decryption of the message).

Bleichenbacher’s attack

Unfortunately PKCS#1 v1.5 is sussible to Bleichenbacher’s attack [here] and has been the core of many attacks on SSL:

Let’s say that Eve is attacking the server. In the message she sends, there’s padding of the pre-shared key (as it is much smaller than the public modulus — n). I have created a demo here:

In PKCS#1 v1.5 padding we then have two bytes at the start:

0x00 0x02

Eve then captures the cipher in the handshake and which contains the SSL pre-shared key (M):

C=M^e (mod N)

She then plays it back to the server, but adds an ‘s’ value (where she multiplies the cipher ( c) by s to the power of e (mod N)):

C′=C×(se) (mod N)

where e and N are the known public key elements. The server decrypts and gets:

M′=(C(s^e))^ d (modN)=C^d×s^{ed} ( modN)=M×s (modN)

M=C′s

When the server reads this, the first two bytes are likely to be incorrect, so it responds to say “Bad Crypto!”. Eve then keeps trying with different s values, until the server gives her a positive response, and she’s then on her way to finding the key. As we have 16 bits at the start, it will take us between 30,000 (1 in 215 which is 1-in-32,728) and 130,000 attempts (1 in 217 which is 1-in-131,073) to get a successful access.

We use padding to make sure that M (the pre-shared key) is the same length as the modulus (n). As M is only 48 bytes, we need to pad to give a length equal to n (256 bytes for a 2048-bit key).

In the end we just need to divide the original cipher by the value we have found, and we get M.

In this case we capture the cipher with M (which starts with \x00\x02), and then play it back with the addition of s^e, and then detect when there is a success in the cipher code:

import sys

e=79
d=1019
N=3337

def int_to_bytes(val, num_bytes):
    return [(val & (0xff << pos*8)) >> pos*8 for pos in range(num_bytes)]

print '==Initial values ===='
print 'e=',e,'d=',d,'N=',N
print '\n============='
 
pad = '\x00\x02\x55\x55'

val = int(pad.encode('hex'), 16)
print 'Padding is:',pad,' Int:',val

cipher = val**e % N

print 'Cipher is: ',cipher

for s in range(0,255):
	cipher_dash = (cipher*(s**e)) % N
	decode = cipher_dash **d % N
	result = int_to_bytes(decode,2)
	print s,
	if (result[0]==0 and result[1]==2):
		print '\n\\x00\\x02 Found it at s=',s
		break

Let’s select:

P=47 Q=71

The calculation of n and PHI is:

n=P × Q = 13 × 11 = 3337
PHI = (p-1)(q-1) = 3220

We can select e as:

e = 79

Next we can calculate d from:

(79 × d) mod 3220 = 1 [Link]
d = 1019
Encryption key [3337,79]
Decryption key [3337,1019]

Then, with a message of 688, we get:

Cipher=(688)^79 (mod3337)=1570

Decoded=(1570)^1019 (mod3337) =688

Conclusion

So there you go, PKCS#1 v1.5 addresses several RSA issues, but beware of the Bleichenbacher attack as it just refuses to go away: