Subject: [ietf-tls] A design weakness of SSL/TLS

From: Hugo Krawczyk <[email-masked]>
Date: Wed, 6 Jun 2001 23:44:33 +0300 (IDT)

Here is the note I promised the other day regarding the new results that
were mentioned in this list:

In a paper to be presented in the upcoming CRYPTO'2001 conference (and 
available at http://eprint.iacr.org/2001/045/)  I show that 
the ORDER of encryption and authentication as applied to the transmitted 
data by SSL/TLS (i.e, first-mac-then-encrypt) provides a weaker security 
guarantee than expected.  Somewhat surprisingly, it turns out that 
there are very strong ciphers (e.g. providing Shannon's perfect secrecy) 
that in combination with any secure MAC (even one with unconditional 
security) make SSL/TLS vulnerable to attack.

Specifically, I present an example of a perfectly-secret encryption function 
(a seemingly harmless variant of one-time pad encryption) which 
combined with any secure MAC function under SSL/TLS results in a record-layer 
protocol where data secrecy can be totally broken by an active attacker 
(for example it is possible for the attacker to find passwords transmitted 
under the protection of the protocol, credit card numbers, etc.).

This contradicts an important design goal of a generic protocol such as 
TLS where different cryptographic algorithms may be used. In particular, 
this principle is reflected in the following statement  in RFC 2246: 
    "The TLS protocol is secure, in that any cipher suite offers its promised 
    level of security"
This seems to imply that if one chooses a secure encryption function and a 
secure MAC then the information protected by the protocol should be secured
against passive and active attacks.  The above result, however, shows that 
this is not guaranteed, in general, by SSL/TLS.  So the bad news are that 
SSL/TLS is NOT generically secure: plugging in *individually secure* 
encryption and MAC functions does not guarantee the security of the protocol.

Fortunately, there are good news too: in the same paper I prove that if the
encryption mode is either CBC encryption (using a secure block cipher) 
or a traditional stream cipher (which are the two common modes of encryption 
used in SSL/TLS) then its combination with a secure MAC algorithm under the
first-mac-then-encrypt method DOES provide security against passive and active 
attacks.  This means that currently implemented ciphersuites are secure.  
In other words, THE IDENTIFIED PROBLEM SHOWS A SUBSTANTIAL DESIGN WEAKNESS OF
THE PROTOCOL BUT NOT A PRACTICAL FLAW OF *CURRENT* IMPLEMENTATIONS. 

It is important to note that the above design weakness is not unavoidable: 
in another recent paper with Canetti (presented at Eurocrypt'2001) 
we show that using a different ordering of encryption and authentication, 
i.e. first encrypt the data then apply a MAC to the ciphertext, the 
obtained protocol IS generically secure, namely secure under the 
combination of ANY individually-secure encryption and MAC functions.  
This is the order used, for example, in the ESP protocol of IPSEC.
 
While I feel that these results should be taken into consideration when 
designing new protocols (for which one should adopt the first-encrypt-then-mac 
method), it is not clear what effect they should have for a widespread 
standarized protocol such as SSL/TLS. Specifically for the TLS WG 
I see several possibilities regarding these findings:

  (1) Ignore these results

  (2) Make a note in a future revised version of the RFC about the care needed
      in choosing ciphertexts or adopting new algorithms or modes
      even when these changes seem minor and "harmless".
      (Indeed, while the paper proves the security of current modes it also
       makes clear how fragile the security of these modes is: for example,
       encoding data before encryption, or encrypting the data and MAC 
       with separate IVs are enough to render the protocol insecure!) 

  (3) change the order of encryption and authentication in a future version of
      the protocol (a decision that certainly changes "the bits in the wire").

Doing (2) certainly seems easy.
As for (3), it would be very desirable to have a more robust and 
better-designed protocol but I am not in a position to judge the practical 
complexity of mandating such a change in widely-deployed standard as TLS.

Hugo

---
You are currently subscribed to ietf-tls as: [email-masked]
To unsubscribe send a blank email to [email-masked]

---

From: Bodo Moeller <[email-masked]>
Date: Thu, 14 Jun 2001 14:29:57 +0200 (CEST)

> security) make SSL/TLS vulnerable to attack.

Is this really that surprising?  Note that Mihir Bellare's and
Chanathip Namprempre's ASIACRYPT 2000 paper "Authenticated Encryption:
Relations among notions and analysis of the generic composition
paradigm" already shows that Encrypt-then-MAC is sound while
MAC-then-Encrypt and MAC-and-Encrypt have problems.

(The paper should be avaiable from <URL: http://www.cse.ucsd.edu/users/mihir/>.)

-- 
Bodo Möller <[email-masked]>
PGP http://www.informatik.tu-darmstadt.de/TI/Mitarbeiter/moeller/0x36d2c658.html
* TU Darmstadt, Theoretische Informatik, Alexanderstr. 10, D-64283 Darmstadt
* Tel. +49-6151-16-6628, Fax +49-6151-16-6036

---

---

From: James Morris <[email-masked]>
Date: Thu, 14 Jun 2001 23:08:29 +1000 (EST)

> MAC-then-Encrypt and MAC-and-Encrypt have problems.

It's interesting that Ferguson and Schneier's paper "A Cryptographic
Evaluation of IPSec" criticises IPsec's Encrypt-then-MAC for violating
the Horton Principle (authenticate what was meant, not what was said), and
refers to SSL's authentication of plaintext as the correct method.

- James
-- 
James Morris
<[email-masked]>

---

---

From: Hugo Krawczyk <[email-masked]>
Date: Thu, 14 Jun 2001 19:45:15 +0300 (IDT)

> (The paper should be avaiable from <URL: http://www.cse.ucsd.edu/users/mihir/>.)

Bodo, 

I think this question is more of academic interest than TLS interest
but since you ask I'll respond.

You'll find an answer to your question in my paper where I address this
issue explicitly.
Summary: Indeed [BN] prove that AtE is not necessarily CCA-secure.
However, as it turns out by the recent results, being CCA-secure is no
guarantee for security or insecurity for the purpose of building a "secure
channels"  protocol as TLS. To make the point even clearer, if you take
the specific example in [BN] with which they show the "insecurity" of AtE
composition and you plug that example as your data protection function in
TLS, the resultant protocol IS SECURE.

Is there a bug in [BN]? No. It is just that your conclusion that their
result invalidates AtE as the method for secure channels is
incorrect. (Or, in other words, CCA is not the validating notion when the
problem that you are trying to solve is secure communications)

Hugo

---

---

From: Hugo Krawczyk <[email-masked]>
Date: Fri, 15 Jun 2001 16:08:46 +0300 (IDT)

> refers to SSL's authentication of plaintext as the correct method.

The recent results show that Encrypt-then-MAC is a better and more robust
method for generic and (hopefully) long-lived protocols such as TLS and
IPsec. In my opinion, the above criticism against ipsec is not justified
in the case of ESP which combines encryption and authentication in the
right way. A valid criticism could have been applied to the early design
of ipsec where authentication and confidentiality were provided by two
different protocols, AH and ESP, and their intereaction and order of
composition was not uniquely specified. Fortunately, however, ESP was
eventually corrected to include authentication and we got a GOOD protocol.

There is howver one issue related to Encrypt-then-MAC and the "Horton
principle" that is relevat here and I discuss it in remark 4.1 of my
paper: 

  Note that the authentication of the ciphertext provides plaintext
  integrity as long as the encryption and decryption keys used at the
  sender and receiver, respectively, are the same. While this key
  synchrony is implicit in our analytical models \cite{ck}, a key mismatch
  can happen in practice. A system concerned with detecting such cases can
  check the plaintext for redundancy information (such redundancy exists
  in most applications: e.g., message formats, non-cryptographic checksums,
  etc.).  If the redundancy entropy is significant then a key mismatch
  will corrupt this redundancy with high probability.

In TLS where the encryption and MAC key are derived together from the same
key this situation is quite improbable. Yet, if one was to design TLS
under the EtA method this issue had to be addressed.

Hugo

---

---

From: Hugo Krawczyk <[email-masked]>
Date: Fri, 15 Jun 2001 16:18:53 +0300 (IDT)

Niels,

If I understand your comments below, what you are saying is something like:

"The negative results in Hugo's paper have no practical signifcance since
they assume the encryption function to be IND-CPA, and such a security
notion is obviously too weak to provide a secure MAC/encryption
composition"

(Note for those that did not read the paper: IND-CPA is just a scary
acronym used in the crypto literature to mean resistance of an encryption
function to chosen-plaintext attacks)

Well, Niels, this is plain wrong. So either I misunderstood you (please
correct me) or you misunderstood the paper.

If what you said was true then we had no hope to create a secure protocol
out of the common modes of encryption in use, including CBC encryption and
stream ciphers. Indeed all these modes are just IND-CPA (i.e., resistnat
to chosen plaintext attacks but not to chosen-ciphertext attacks, which is
what you refer to when talking about decryption oracles). 
In particular, this would have left us with no hope for the security of
TLS which uses these modes of encryption.

What really gives PRACTICAL significance to the recent results is that 
they do NOT assume any fancy features of encryption not present in the 
EXISTING (and easier to design) encryption modes, but only assume 
resistance to chosen plaintext attacks (IND-CPA) which is what these 
modes really are.

"As an engineer" you should ask yourself what is the right way to use the
existing (and future) PRACTICAL cryptographic schemes, rather than to 
build on strong notions of security not achieved by the existing 
encryption functions.

Hugo

> 
> I scanned through Hugo Krawczyk's paper (http://eprint.iacr.org/2001/045/)
> to look at the (claimed) problem with authenticate-then-encrypt. The
> encryption scheme that leads to a weakness in authenticate-then-encrypt
> satisfies the IND-CPA property. In the definition of the IND-CPA property
> the attacker is limited using an encryption oracle, but has no access to a
> decryption oracle. As an engineer I find the IND-CPA definition useless
> because it has no relation to the real world. In real life there is almost
> always a party that performs the decryption, and we must assume that the
> attacker has access to a decryption oracle of some form. (In many systems
> the recipient will respond with a recognisable error code when the
> decrypted message makes no sense. The attacker can use this to gather
> information: send a bogus ciphertext to the receiver and check for the
> error code.)
> 
> The 'attack' on authenticate-then-encrypt uses an encryption scheme that is
> not secure when the attacker has a decryption oracle of the type mentioned
> above. The paper explicitly mentions that even without any authentication,
> the encryption scheme is not secure when used to encrypt messages. The
> authenticate-then-encrypt scheme proposed is insecure because the
> encryption scheme is insecure. This has _nothing_ to do with the
> authenticate-then-encrypt construction. The encryption scheme is weak. The
> fact that the encryption scheme is IND-CPA is a criticism of the IND-CPA
> definition, not an indication of a problem with the
> authenticate-then-encrypt construction.
> 
> If we want to we can also define an authentication scheme and an encryption
> scheme under which authenticate-then-encrypt is secure but
> encrypt-then-authenticate is weak. I don't think this tells us anything
> about the relative merit of authenticate-then-encrypt and
> encrypt-then-authenticate.
> 
> Cheers!
> 
> Niels
> 
> 
> ==============================================================
> Niels Ferguson, [email-masked], phone: +31 20 463 0977
> PGP: 3EC2 3304 9B6E 27D9  72E7 E545 C1E0 5D7E
> 

---

---

From: Bodo Moeller <[email-masked]>
Date: Fri, 15 Jun 2001 19:12:32 +0200 (CEST)

>>> In a paper to be presented in the upcoming CRYPTO'2001 conference
>>> (and available at http://eprint.iacr.org/2001/045/) I show that
>>> the ORDER of encryption and authentication as applied to the
>>> transmitted data by SSL/TLS (i.e, first-mac-then-encrypt) provides
>>> a weaker security guarantee than expected.  Somewhat surprisingly,
>>> it turns out that there are very strong ciphers (e.g. providing
>>> Shannon's perfect secrecy) that in combination with any secure MAC
>>> (even one with unconditional security) make SSL/TLS vulnerable to
>>> attack.

> problem that you are trying to solve is secure communications)

I did not claim that your results were not new or not interesting.
It just so happens that I was not surprised (quit possibly I should
have been?).

In your paper, you write that "These results [of Bellare and
Namprempre] are insufficient in general for claiming the security, or
demonstrating the insecurity, of channels that use these methods for
protecting data".  The example that you mention above shows that they
are indeed insufficient for demonstrating the insecurity, but is it
true that they are insufficient for demonstrating the security?  For
the encrypt-then-MAC construction with a strongly unforgeable MAC (as
opposed to a weakly unforgeable MAC where the attacker may be able to
come up with new MAC tags for messages for which a MAC tag is already
known), Bellare and Namprempre show not only IND-CPA, but also IND-CCA
and NM-CPA security and INT-PTEXT and INT-CTEXT integrity.
If this does not suffice for building secure channels, then I'd
really be surprised.

Anyway, your paper shows that the security of the MAC-then-encrypt
construction as used by TLS relies on various unspoken assumptions;
thanks to a proper combination of intuition and luck, these
assumptions are satisfied by TLS.  I'd assume that there are more
possibilites to make MAC-then-encrypt secure than considered in the
paper: For example, the claim that separate message and MAC encryption
is insecure (remark 5.4) does not appear to be true if stateful
encryption is used (so that the attacker cannot directly influence
IVs).  (Additional requirements for the encryption operations are
necessary, ENC* obviously must still be excluded; standard modes
of operation or XOR-stream ciphers should be OK.)

---