SSLeay and the PKCS#1 padding attack.

Correct PKCS#1 padding, for an rsa key n bytes long, containing an
m byte message
0x00 0x02 0x??{8,n-m-3} 0x00 0x??{m}

The core of the attack involves submitting doctored messages which
will occasionally pass the PKCS#1 padding check (a leading 0x00,0x02)
even though the message has decrypted incorrectly.
A server that reports a PKCS#1 padding check failure, either explicitly or
by difference in timing, is vunerable to this attack.

The best solution to this attack is to ignore the PKCS#1 decrypt failure.
If the decrypted bytes are invalid, the SSL/TLS handshake will fail later
with a MAC failure.  This error mode is currently what is used for the
Ephemeral DH ciphers.

For SSLeay 0.6.6, 0.8.1 and 0.9.0

1) These versions of SSLeay incorrectly check for the leading 0x00 0x02 bytes.
   The check for 0x00,0x02 will pass if the message decrypts to either
   0x00,0x02 or 0x02 or, for that matter, 0x00,0x00,0x02.  This means 
   that a greater number of bad decryptions will not be reported as a
   PKCS1 error.  This makes the attack much harder.  I have not fixed
   this bug in the released patches, but will for SSLeay 0.9.1.  I
   will not speculate on if this makes the attack infeasable, but I do
   feel it makes it much harder.  (A case of a bug
   making an attack harder :-).
2) SSLeay also checks for for the existance of the NULL seperator and verifies
   that it occurs at least 8 bytes from the 0x02.  This introduces extra
   failure cases so more probes would be required.  This would perhaps
   double the number of probes required.
3) SSLeay 0.9.0 does check the SSLv3/TLSv1 protocol number, but unforntunatly
   it did returns a different error message if they are wrong so in the case 
   of SSLeay 0.9.0, it would not have helped prevent this attack.

Make sure to upgrade to 0.6.6a, 0.8.1a or 0.9.0a.  I have made as few changes
as possible other than to fix serious errors.

Using the numbers provided in the RSA Laboratories Bulletin,
0.6.6, 0.8.1 and 0.9.0 all check for the length of the returned value,
making the number of probes required about 20 million.  SSLeay 0.9.0 does
do version number checking, for which the number of probes required is
estimated to be 2^40.  Considering the above mentioned error reporting
correct PKCS#1 decrypts, I would consider the trial rate even higher.

It should be noted that SSLv2 did not have a version number check, and since
most SSL servers support both SSLv3 and SSLv2, an attacker would attack
via SSLv2, for a cost of about 20 million probes, not via SSLv3, with 2^40.
eric 26-Jun-98

---8<---

More information on what vendors and the press are saying about this
issue can be found at:
	http://www.ssleay.org/announce/pkcs1.html