[Bodo Moeller <bodo at openssl.org>] OpenSSL Security Advisory: Timing-based attacks on SSL/TLS with CBC encryption

[Zully Ramzan]

Eric, thanks for putting together such a great description -- it was
helpful to see the novel observations of this attack compared to
Vaudenay's original paper from Eurocrypt '02.  

For those who may not be aware, I wanted to point out that there is also
a very nice paper by John Black and Hector Urtubia that extends
Vaudenay's attack to other natural padding schemes and encryption modes.
The result appeared at USENIX Security '02.  

Careful error handling and timing for replies should mitigate the risk
of these attacks as well.    Nonetheless, it would certainly make sense
that attempts to repair existing implementations might want to take the
attacks in this paper into account as well.  

The paper can be found at:
http://www.cs.colorado.edu/~jrblack/papers.html 

"Side-Channel Attacks on Symmetric Encryption Schemes: The Case for
Authenticated Encryption [pdf] [ps.gz] [ps] [html] 
John Black and Hector Urtubia 
Following an idea of Vaudenay, we consider side-channel attacks based on
having an oracle which indicates whether the underlying padding is done
correctly or not. We examine several popular and natural padding schemes
and show that, under CBC mode encryption, they all succumb to an attack
which efficiently recovers the plaintext. We then extend our results to
other encryption modes and other side-channels culminating in a
recommendation for authenticated encryption as the "proper" notion for
symmetric encryption. 

Appeared at 11th USENIX Security Symposium -- USENIX Security '02, San
Francisco, USA, 2002"

Regards,
Zully 

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Zulfikar Ramzan
IP Dynamics, Inc.   http://www.ipdynamics.com
Unfettered, Simple VPNs
 
> -----Original Message-----
> From: Eric Rescorla [mailto:ekr at rtfm.com]
> Sent: Thursday, February 20, 2003 4:50 PM
> To: cryptography at wasabisystems.com
> Subject: Re: [Bodo Moeller <bodo at openssl.org>] OpenSSL Security
Advisory: Timing-
> based attacks on SSL/TLS with CBC encryption
> 
> 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.
> 
> 
> --
> [Eric Rescorla                                   ekr at rtfm.com]
>                 http://www.rtfm.com/
> 
> ---------------------------------------------------------------------
> The Cryptography Mailing List
> Unsubscribe by sending "unsubscribe cryptography" to
majordomo at wasabisystems.com

---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at wasabisystems.com