North American Network Operators Group

Date Prev | Date Next | Date Index | Thread Index | Author Index | Historical

Re: SSL crack in the news

  • From: Eric Rescorla
  • Date: Sat Feb 22 17:43:17 2003

"Mark Radabaugh" <[email protected]> writes:

> http://www.cnn.com/2003/TECH/internet/02/21/email.encryption.reut/index.html
> 
> Very little real information...
Here's the writeup I sent to the cryptography mailing list.

----------------------------------------------------------

Here's a fairly detailed description of how the attack works.

You can also find a writeup by the authors at:
http://lasecwww.epfl.ch/memo_ssl.shtml


EXECUTIVE SUMMARY
This is a potentially serious attack for automated systems that rely on
passwords. Effectively, it potentially allows the attacker to recover an
encrypted password. It doesn't appear to be serious for non-automated
situations.


OVERVIEW
Imagine you have some protocol that uses passwords and the password
always falls in the same place in the message stream.  (IMAP, for
instance). What happens is that the attacker observes a connection using
that password. He then deliberately introduces a bogus message into the
encrypted traffic and observes the server's behavior. This allows him to
determine whether a single byte of the plaintext is a certain (chosen)
value. By iterating over the various bytes in the plaintext he can then
determine the entire plaintext.


HOW THE ATTACK WORKS
Basically, the attack exploits CBC padding. Recall that the standard
CBC padding is to pad with the length of the pad.  So, if you have an
8 byte block cipher and the data is 5 bytes long you'd have XX XX XX
XX XX 03 03 03. This technique allows you to remove the pad by
examining the final byte and then removing that many bytes. [0]
Typically you also check that all the pad values are correct.

Say the attacker intercepts a pair of consecutive blocks A and B,
which are:
        A = AA AA AA AA AA AA AA a
        B = BB BB BB BB BB BB BB b

And the plaintext of B corresponds to
        P = PP PP PP PP PP PP PP p

The attacker wants to attack B and guesses that p == y. He transmits
a new message A' || B where
        A' = AA AA AA AA AA AA AA (a XOR y)

When the server decrypts B, the final byte will be (p xor y).
If the attacker has guessed correctly then there will appear
to be a zero length pad and MAC verification proceeds. Since
the packet has been damaged, the MAC check fails. If the
attacker has guessed wrong then the last byte will be nonzero
and the padding check will fail. 

Many TLS implementations generated different errors for these
two cases. This allows the attacker to discover which type
of error has occurred and thus verify his guess. Unfortunately,
since this generates an error, the attacker can only guess once.

The attack described above was discovered a year or two ago
and implementations were quickly modified to generate the same
error for both cases.

This attack introduces two new features:
(1) The authors observed that if you were moving passwords over
TLS then the password would generally appear in the same place
in each protocol exchange. This lets you iterate the attack 
over multiple character guesses and eventually over multiple
positions.

(2) Even if the same error message generated the MAC check takes
time. You can therefore use timing analysis to determine what
kind of error occurred. This has the downside that there's some
noise but if you take enough samples you can factor that out.


PRACTICALITY
Let's estimate how long this will take. Most passwords are 7-bit ASCII,
so naively we need to try all 128 values for each character. On average
we'll get a hit halfway through our search so we expect have to try
about 64 values for each character position. If we assume an 8 character
password this means we'll need about 8*64==512 trials. Now, you
could be smarter about what characters are probable and reduce these
numbers somewhat but this is the right order of magnitude.

Now, things are complicated a bit by the fact that each trial creates an
error on both client and server. This has two implications. First, it
creates a really obvious signature.  Second, it requires that the client
create a lot of SSL connections for the attacker to work with. This is
only likely if the client is automated.



REQUIRED CONDITIONS
So, under what conditions can this attack be successful?

(1) The protocol must have the same data appearing in a 
    predictable place in the protocol stream. In practice,
    this limits its usefulness to recovering passwords.
    However, this condition pretty common for things like
    HTTP, IMAP, POP, etc.

(2) The SSL implementations must negotiate a block cipher.  Many SSL
    implementations choose RC4 by default and RC4 is not vulnerable
    to this attack.

(3) The attacker needs to be able to hijack or intercept TCP
    connections. There are tools to do this that require varying
    degrees of sophistication and access to use.

(4) The client must be willing to initiate a lot of connections
    even if it's getting SSL errors. As a consequence it almost
    certainly needs to be an automated client.

(5) The attacker and the server must have a reasonably good network
    connection between them. The noisier the network, the more
    trials you need to distinguish the two outcomes.


OUTCOME OF A SUCCESSFUL ATTACK
A successful attacker will be able to recover the plaintext of
whatever connection he's attacking. In general, this will be most
useful when the data is a password. If he captures the password
the attacker will be able to pose as whatever user owns the
password. 

The demonstration described by the authors is against IMAP (Outlook as
the client).  In that case they recover the password after about an
hour of observation. Note that the authors had to turn off RC4 to get
an attackable connection.



NOT AFFECTED
This attack doesn't pose a threat for a number of important (and common)
cases:

(1) Manual remote login by users, like over SSLtelnet (because
    you won't get enough trials). Note, however, that if you
    use the same password for POP or IMAP and telnet then you
    could recover the password using IMAP and then use it to
    log in remotely.

(2) Credit card transactions from web browsers (not enough trials
    and because most Web SSL traffic uses RC4).

It's also important to recognize that just using OpenSSL doesn't
necessarily make you vulnerable. So, for instance, OpenSSH uses
OpenSSL for its crypto engine but this problem doesn't affect
OpenSSH at all. This is an SSL-specific issue. I would expect
other SSL implementations to be vulnerable to the same attack.


-Ekr


[0] TLS uses a variant of this scheme in which you have a pad length
byte and then pad with the value, so the above block would be
XX XX XX XX XX 02 02 02. But the principle is the same.