Subject: [ietf-smtp] When using TLS, would randomizing the order of the EHLO response be helpful?

From: "Carl S. Gutekunst" <[email-masked]>
Date: Thu, 21 Mar 2013 00:47:00 -0700

This is a question for folks that actually know crypto, and also know SMTP.

A common theme of many of the recent statistical attacks on TLS (BEAST, 
Lucky 13, the ABPPS RC4 attack) has been knowing that some early part of 
the plaintext was constant. Knowing that some of the early bytes are 
limited to a range, or even fully known, was even more helpful.

On every SMTP server in the world, the first 100 to 250 bytes send by 
the server after TLS negotiation completes are both constant and known: 
they're the EHLO response. So that got me wondering if randomizing the 
EHLO response could be helpful in mitigating statistical attacks. 
Obviously the degree of "randomizing" is limited; RFC 5321 requires the 
first line to be the FQDN of the receiver, and every line will contain 
"\r\n\220-". The most I can do is randomize whole lines. But I don't 
have an intuitive feel for what might be effective in disrupting these 
statistical code-breaking techniques; hence the question.

I fully understand that fixing the vulnerabilities is much more 
important, but with RC4 in particular I'm wondering about hacks that 
might keep it a little more secure, a little bit longer.

<csg>

---

From: Paul Smith <[email-masked]>
Date: Thu, 21 Mar 2013 09:00:19 +0000

On 21/03/2013 07:47, Carl S. Gutekunst wrote:
> the server after TLS negotiation completes are both constant and 
> known: they're the EHLO response. So that got me wondering if 
> randomizing the EHLO response could be helpful in mitigating 
> statistical attacks. Obviously the degree of "randomizing" is limited; 
> RFC 5321 requires the first line to be the FQDN of the receiver, and 
> every line will contain "\r\n\220-". The most I can do is randomize 
> whole lines. But I don't have an intuitive feel for what might be 
> effective in disrupting these statistical code-breaking techniques; 
> hence the question.
Isn't it '250-'?

Anyway, I'm not a cryptographer either, but my limited understanding 
suggests that things like TLS work on a 'block' of data at once, not 
byte-by-byte. So, if this is deemed a risk or potential risk, it would 
make sense to make the first 'block' as random as possible. AIUI TLS 
uses the previous block as part if the encryption for the next block, so 
if they can't tell what the first block contains, they can't do the rest 
of the stream either.

So, randomising line order, possibly adding 'x-messwithhackers: <random 
string>' pseudo-capabilities, adding random text after the FQDN of the 
receiver on the first line of the EHLO response, etc, would all stand a 
fair chance of making it harder to hack.

But, I'm not a cryptographer, so I may be talking total garbage :-)

-

Paul Smith Computer Services
Tel: 01484 855800
Vat No: GB 685 6987 53

---

From: John C Klensin <[email-masked]>
Date: Thu, 21 Mar 2013 09:45:19 -0400

--On Thursday, March 21, 2013 00:47 -0700 "Carl S. Gutekunst"
<[email-masked]> wrote:

> A common theme of many of the recent statistical attacks on
> TLS (BEAST, Lucky 13, the ABPPS RC4 attack) has been knowing
> that some early part of the plaintext was constant. Knowing
> that some of the early bytes are limited to a range, or even
> fully known, was even more helpful.
> 
> On every SMTP server in the world, the first 100 to 250 bytes
> send by the server after TLS negotiation completes are both
> constant and known: they're the EHLO response. So that got me
> wondering if randomizing the EHLO response could be helpful in
> mitigating statistical attacks.
>...

Rather than trying to guess, I asked an expert who, in my
experience, always takes a "whole system" view of this sort of
issue.   His response is forwarded with permission.

    john

--On Thursday, March 21, 2013 09:26 -0400 Steven Bellovin
<[email-masked]> wrote:

> The right answer is to move away from RC4.  A crypto algorithm
> that is vulnerable in a situation like that is unacceptably
> weak.  RC4 was important 15 years ago, when computers were
> slower and the only real alternative was DES, which -- apart
> from its weaknesses -- was very slow in software.  Today, we
> have fast computers and AES.  (There's also a new stream
> cipher being discussed in the CFRG, but it's too soon to adopt
> it.)  I suspect that virtually every TLS implementation in the
> wild today supports AES; it's just a configuration change.
> (Btw -- unless your enemy is the NSA or its non-US equivalents,
> cryptanalysis is the least of your worries.  Hacking in is so
> much easier.)
> 
> 3 days ago, David McGrew -- co-chair of CFRG -- agreed that
> RC4 should be deprecated:
> https://www.ietf.org/mail-archive/web/cfrg/current/msg03342.ht
> ml This new result is not a surprise to anyone in the field;
> it's been known to be dubious for a fair number of years.
> Here's what I wrote last summer (or earlier) in the crypto
> chapter of a book I'm writing:
> 
> 	Stream ciphers are harder to employ properly than are block
> ciphers,  	but they do have their uses.  RC45 is by far the
> most popular choice,  	and it is extremely fast; that said, it
> appears to have a number  	of cryptanalytic weaknesses [Golic,
> 1997; Knudsen et al., 1998.  It's  	probably best to avoid new
> uses unless you really need its blinding  	speed; instead, use
> AES in counter mode.
> 
> Obviously, I need to strengthen that.  Btw, note the dates on
> the citations.
> 
> RC4 has enjoyed something of a comeback because of CBC-related
> weaknesses in TLS.  Again, the right choice is to fix TLS.
> 
> You may be interested in a 1997 paper of mine; it's also based
> on known or guessable plaintext:
> https://www.cs.columbia.edu/~smb/papers/probtxt.pdf .  Note
> the strongest recommendation: "The simplest defense, of
> course, is to avoid use of weak ciphers.  There is little
> doubt that DES is inadequate against a serious opponent.  That
> security systems based on it should be vulnerable is not
> surprising; what we have simply analyzed exactly how to attack
> one instantiation."
> 
> Feel free to send this to the list, with my name on it.  I
> doubt you'd get different advice from anyone else in the
> security area, with the possible exception of whether or not
> that new stream cipher (Salsa20) is ready for prime time.

---

From: "Carl S. Gutekunst" <[email-masked]>
Date: Thu, 21 Mar 2013 08:24:55 -0700

>> cryptanalysis is the least of your worries.  Hacking in is so

http://xkcd.com/538/

:-)

The references were exceptionally useful, thank you. I wasn't aware of 
the earlier RC4 work in Japan.

Deprecating RC4 was already part of the plan, although the 
interoperability issues in the SMTP space are quite different from the 
browser space: there are still millions of Exchange Servers out there 
whose only viable ciphers are RC4 and 3DES. And despite all the advances 
in CPU power over the years, 3DES is still expensive.

The idea of reordering the EHLO response was always a kludge, but I was 
still curious if it was a statistically interesting kludge.

<csg>

---

From: Ned Freed <[email-masked]>
Date: Thu, 21 Mar 2013 07:54:40 -0700 (PDT)

> might keep it a little more secure, a little bit longer.

An even simpler thing to do, and which introduces far more variability to the
initial server response than reording is to return something like this:

C: EHLO 1.com
S: 250-2.com
S: 250-XRAND p9g8u340prt8u390pr83uyfo983yro937yr9o37yr397h
S: ...

Randomizing what the client initially sends is also pretty easy:

C: NOOP rp08tu098309r8u309r8uy390r8u309r8u39r8u3
S: ...
C: EHLO ...

As to whether or not this is actually useful, I'll try to have to say about
that in a bit. (I'm trying to come up speed on the RC4 attack; it's not easy
given the paper on it doesn't seem to be available yet. If someone know
otherwise I'd appreciate a pointer.)

				Ned

---

From: Ned Freed <[email-masked]>
Date: Thu, 21 Mar 2013 08:25:45 -0700 (PDT)

Oh, one more thing. If clients did start sending NOOP as the first command
after STARTTLS that would actually defeat the randomizing in EHLO. That can be
addressed by sending something random in the response to NOOP, or for that
matter just echoing what the client said.

				Ned

---

From: "Carl S. Gutekunst" <[email-masked]>
Date: Thu, 21 Mar 2013 08:44:46 -0700

> S: 250-XRAND p9g8u340prt8u390pr83uyfo983yro937yr9o37yr397h

Yep, that would be a lot more effective, with one addition: randomize 
the length of that string.

All pending any thoughts on whether this is statistically interesting or 
just moving the deck chairs. Even the latter might be useful for putting 
a shiny red sticker on the box that says "Now Resists the BEAST!"

(Curse djb for not coming up with a clever name for their attack....)

<csg>

---

From: John C Klensin <[email-masked]>
Date: Thu, 21 Mar 2013 12:07:51 -0400

> matter just echoing what the client said.

Yes.  Steve also suggested the liberal use of NOOP or spurious
extension announcements with random parameter strings in a
follow-up note.

But, especially given the relative importance of envelope
information relative to content and given that we know other
ways to really harden content that works end to end, I wonder
whether this is a discussion of the wrong problem.  Specifically
I wonder whether it is analogous to worrying how to get the
windows locked down and barred really securely while leaving the
virtual door wide open.  What is the threat model for which more
than nuisance-level encryption of the envelope is really
necessary and for which a marginal improvement in security with
a relatively weak algorithm is worth the trouble?

   john

---

From: Ned Freed <[email-masked]>
Date: Thu, 21 Mar 2013 23:17:56 -0700 (PDT)

> issue.   His response is forwarded with permission.

With all due respect to Steve, I don't think he's thought about this very hard
or considered the email situation specifically. For one thing, there are two
new attacks, not one.

Let's start by looking at the two new attacks. Lucky 13 is a repeated session
attack on CBC mode ciphers. A particular record in the data stream is modified
in different ways, causing the receiver to report an error, and how long it
takes to generate the report is measured. The number of sessions needed to
perform this attack is large (in expiriments it ranged from 2^15 to 2^22) and
LAN adjacency to the receiver was exploited. The number of sessions needed as
well as the amount of data that can be recovered vary enormously depending on
the TLS implementation and cipher suite used. But one of the ways to avoid
this attack is to use RC4, which because it doesn't require padding to a block
boundary is invulnerable to this type of attack. Note that any record in the
stream can be attacked; it doesn't have to be at the beginning.

The second (currently unnamed) attack is on RC4 specifically. This is a
repeated session eavesdropping attack and it only works on the first 256 bytes
of the stream. Some bytes can be deduced after 2^24 sessions and reliable
recovery is possible at around 2^30 session.

Given the overall characteristics of email sessions these are not remotely
feasible attacks. (There's some stuff in one of the papers about using malware
to cause lots of sessions to be generated; my position on that is given the
ability to infect the user's PC with malware there's so much more low-hanging
fruit I'm not worried about anyone using this attack on email.)

All that said, if you assume somone is going to attack email this way the thing
to go after rather obviously isn't message or envelope data - there's no
practical way to generate enough iterations of the same session/transaction for
that to work. User authentication credentials are another matter, however.
These occur consistently in the same place in email sessions.

The NOOP command/EHLO response business discussed could be used to improve
proection of these credentials in email sessions. But it's the length that
matters, not the content, because the goal is to make it impossible to
correlate the credentials found in multiple sessions.

However, there's a much simpler way to defeat these attacks: Use CRAM-MD5
or SCRAM-SHA1 under the SSL/TLS session instead of PLAIN. The changing
nonce will make it impossible to correlate credential information across
multiple sessions.

I will again repeat that these attacks are totally impractical in the email
space. But if you want to worry about them and for whatever reason you have to
fix things at the application layer, IMO the thing to do right now is to use an
RC4 cipher suite paired with CRAM-MD5 and/or SCRAM-SHA1 under your SSL/TLS
session for authentication.

And of course Steve is correct that a move away from RC4 is a good idea. (And
so is a move towards AES-GCM.) This has been true for a long time: It's
well known that there are structural weaknesses in RC4 (and CBC).

That said, I take issue with the apothegm that "attacks only get better, they
don't get worse". What seems to happen in practice is an attack is found, then
it is improved iteratively. Then after a while the improvements slow down and
finally stop. And then after a while a *new* attack, sometimes related,
sometimes not, is found and the process repeats. We've seen this pattern with
differential attacks, linear attacks, chosen prefix attacks, oracle padding
attacks, and so on.

What this says to me is that it doesn't make sense to expend a lot of effort on
defeating attacks that appear to be infeasible and which given due
consideration of the application space seem unlikely to become feasible.

				Ned