[2883] in cryptography@c2.net mail archive
PKCS#1 Attack Summary
daemon@ATHENA.MIT.EDU (Bill Stewart)
Sat Jun 27 00:11:26 1998
Date: Fri, 26 Jun 1998 20:26:49 -0700
To: cypherpunks@cyberpass.net, cryptography@c2.net
From: Bill Stewart <bill.stewart@pobox.com>
Here's my first-readthrough description of the attack:
PKCS#1 is a standard for padding a plaintext for encrypting with RSA.
The format of the padded text is
EB == 00 || BlockType || PadString || 00 || Data
where BlockType is 02 for this application, PadString is enough octets of
non-zero pseudorandomness to pad the string to k bytes long,
and Data is typically a session key.
Vulnerable applications, including SSL, RSA-encrypt the EB,
c = (EB)**e mod n
and send it from a sender to a recipient, which replies with
an indication of whether the received value was good or bad,
with a passive eavesdropper watching the transaction.
The eavesdropper then takes the observed cyphertext, and
makes many attempts to send the recipient connections using
c' = c*r**e mod n
and notes which ones respond that the message is invalid.
About 1 time in 2**16, the c' will decrypt to a message of the form
00 02 stuff
where "stuff" will generally be invalid, but does leak some information
about the original message EB which can be used efficiently to
hunt for it, typically taking about 2**20 tries with a 1024-bit key.
(Discussion of how to do this was in a referenced article...)
The basic countermeasures are to reduce the probability that
"stuff" will be good enough for the recipient to continue
processing it (e.g. use the RSA-decrypted session key
to try to decrypt the credit-card number or other message)
to make the error messages less informative to the sender,
and to refuse to process huge numbers of bad attempts
from a given sender. (Email, for instance, isn't very vulnerable,
since you typically don't send back error messages saying the
mail didn't decrypt, and most mail clients are used by humans,
who will generally get some clue that there's a problem
if they receive millions of bad messages, even if their
mail servers or mail clients don't crash first.)
The cheap test is to check how long the decrypted PadString and
Data fields are, by looking for the first 00 byte -
usually the Data field is some known length, like 128 bits,
so if the 00 shows up sooner, or later, or not at all,
then the recipient should reject the packet as bad,
just as it would for a decrypted packet not starting with 00 02.
This is claimed to increase the number of tries to about 20 million,
which is some help.
A fancier version of the test is to include a checksum in the Data.
For typical applications, the Data is a session key, used to decrypt
an attached message, and the decrypted attached message often
contains some syntax that can be validated and used to reject bad keys.
This can substantially reduce the probability that a message is "good",
and therefore reduce the information given to the attacker.
However, I smell a timing attack here - if server performance is
consistent enough to detect the difference between a message that
fails to decrypt to 00 02 stuff and a message that does have that form
and then uses some time to decrypt the attached emssage with the session key,
you could get less reliable but still useful feedback.
Thanks!
Bill
Bill Stewart, bill.stewart@pobox.com
PGP Fingerprint D454 E202 CBC8 40BF 3C85 B884 0ABE 4639
