Subject: Re: Some comments on the use of DH in S/MIME

From: [email-masked] (Peter Gutmann)
Date: Fri, 1 Jan 1999 18:32:38 (NZDT)

>I believe you've misunderstood the attack. It is indeed a problem for CMS 
>(though likely not for S/MIME). Let's deal with the RSA case for a second: 
>The purpose of the attack is to recover the MEK given a wrapped MEK in a 
>known public key. The attack depends on the attacker being able to 
>differentiate a message which when decrypted yields an badly formatted (in 
>the PKCS-1) sense message from a message which is correctly formatted but 
>(presumably) yields a bad message encryption key.
 
It also depended on an implementation bug in which some SSL implementations 
wouldn't check the PKCS #1 padding properly, stopping at the '00 02' and 
returning an error specific to this case (these implementations were 
identified in the CERT advisory and have now been fixed).
 
There are two ways to determine just how serious this is as a problem.  The 
first one is to look at how it affects existing implementations: Currently 
every S/MIME implementation, PGP, and countless other vendor-specific 
protocols use PKCS #1 padding.  Somehow, the entire planet has managed to get 
by in the presence of the "weakness", which would indicate that it's not much 
of a practical threat.
 
The second approach is to see just what it would take to implement this attack 
on CMS (not S/MIME, but anything involving CMS).  For this analysis I'll make 
several assumptions:
 
1. The implementor has managed to design a protocol which will accept 
   arbitrary numbers of chosen-ciphertext messages and reply to each one with 
   an exact indication of how the decrypt failed, leaking information about
   the decrypted message to an attacker.  This is a fairly remarkable feat, 
   but let's say, just for arguments sake, that someone did do this.
2. The implementor and any third-party reviewers have somehow missed the CERT 
   advisory, RSA labs bulletin, publicity about the attack, and whatever else 
   is around there which tells people about the problem and (very simple) fix.
3. The PKCS #1 implementation being used is correct (that is, it doesn't have 
   the implementation bug which was found and fixed in the SSL implementations).
4. A typical query+response takes half a second (this means opening a 
   connecting, generating a chosen-ciphertext message, transmitting it, having 
   the victim decode and try to decrypt it, generating a response, wrapping up 
   an exact indication of the decryption error it encountered, and sending it 
   back to the attacker).
 
OK, so we have a server which does all of the above sitting there ready for 
attack.  With a correct PKCS #1 implementation (that is, it checks the padding 
as per the PKCS #1 spec), the complexity is approximately 1 million attempts 
(for the 00 02 padding) x 20 (for the second 00 before the MEK) x 2 (for the 
minimum of 8 nonzero bytes), or 40 million attempts (the 1 million attempts 
requires the presence of the SSL implementation bug mentioned above).
 
This requires just under 8 months of CPU time to perform, after which you've 
recovered a single MEK.
 
I would suggest that anyone who doesn't notice that their server is under 
continuous attack for 8 solid months has more than simple crypto problems to 
worry about.
 
>Note that the attack does NOT necessarily require return receipt or even 
>accurate error reporting if it's being used in an interactive protocol. If 
>the message is long, you may be able to differentiate these two error tpes 
>through timing analysis. 
 
This will slow things down even further, because you need to wait seconds 
(minutes?) for each response.  In this case you'd need to continously attack a 
server for years to recover a single MEK.
 
>>As a security threat, I'd say this rates somewhere down with "Router hit by
>>meteorite", "Computer trampled by stampeding water buffalo", "Hard drive
>>kidnapped by space aliens", and similar FUD.
>
>I believe this estimate is unjustifiably optimistic.
 
Given the above analysis I'll let list members decide how realistic this is or 
not.  However, I'm also prepared to put my money where my mouth is: If you 
like, I'll set up a process on a server which runs some protocol which is 
specificaly custom-designed to provide this "weakness" for you, and you can 
try and recover a MEK with it.  If you can recover a single MEK before 
whatever Y2K-induced armageddon is supposed to swallow us all occurs, I'll 
admit I was wrong, and that it is a practical weakness.
 
Peter.