Subject: Authenticated cipher modes

From: Henrick Hellström <[email-masked]>
Date: Mon, 18 Apr 2005 10:48:21 +0200

While trying to figure out how to support CCM, EAX and OCB cipher modes 
or the Helix cipher (http://www.schneier.com/paper-helix.pdf), I spotted 
an issue with SSH-TRANS. These cipher modes have built in data 
integrity, but the SSH-TRANS algorithm negotiation mechanism clearly 
isn't designed to handle such encryption.

There are three reasons such encryption algorithms should be supported:
1. Performance. They are twice as fast since the encryption mode 
provides data integrity by itself.
2. Resources. Helix in particular consumes very little resources. There 
are no memory consuming s-boxes and the algorithm might be implemented 
to hold the entire state in CPU registers (at least on CPUs such as 
AMD64/EM64T and M680x0 that have a relatively high number of general 
purpose registers).
3. Security. According to http://cr.yp.to/papers.html#cachetiming, 
encryption algorithms that use sboxes are vulnerable to timing attacks, 
and fixed time algorithms such as Helix should be used for online 
transport encryption.

Here is the problem:

Suppose I define an encryption I name "[email-masked]". I would 
then want the following:

1. If the server and the client negotiate this encryption, they MUST 
also negotiate a designated data integrity name, which is specified to 
be coupled with the encryption in question. There is no point in adding 
a second layer of data integrity to e.g. Helix encryption. This is 
unfortunately not consistent with the algorithm selection mechanism 
specified in section 7.1 of SSH-TRANS. If the standard algorithm 
selection mechanism is followed, the client and the server might end up 
with e.g. [email-masked] for encryption and an unrelated data 
integrity algorithm. For example, this would happen if the client is 
sending "[email-masked],[email-masked],3des-cbc" for 
encryption and "hmac-sha1,[email-masked]" for data integrity, and 
the server is sending 
"[email-masked],[email-masked],3des-cbc" for 
encryption and "hmac-sha1,[email-masked]" for data integrity.

2. The processing rules of section 6.4 "Data integrity" of SSH-TRANS 
MUST be integrated into the encryption processing, if e.g. Helix 
encryption is selected. That is, the message counter should be processed 
by the encryption as unencrypted header data, in accordance with the 
Helix specification. (One should note that CCM mode is less of an issue 
in this respect, since an implicit message counter is part of the mode 
itself. Selecting CCM mode and the "none" data integrity algorithm would 
result in the desired state.)

-- 
Henrick Hellström
www.streamsec.com

---

From: Derek Fawcus <[email-masked]>
Date: Mon, 18 Apr 2005 10:34:00 +0100

> Selecting CCM mode and the "none" data integrity algorithm would 

I've not read Helix.  However in general I'd assumed that use of a encryption
including integrity algorithm could always simply be used with SSH by choosing
a SSH MAC of "none".  Certainly that's what I thought when I was considering
hacking in use of OCB.

DF

---

From: Damien Miller <[email-masked]>
Date: Mon, 18 Apr 2005 19:39:01 +1000

> result in the desired state.)

The problem with this arrangement is preventing the null MAC from being
inadvertantly selected with cipher modes that don't provide integrity.

Perhaps these modes need a modified key-exchange to negotiate them?

-d

---

From: Henrick Hellström <[email-masked]>
Date: Mon, 18 Apr 2005 12:09:57 +0200

> a SSH MAC of "none".  Certainly that's what I thought when I was considering

I see two problems with that.

Firstly, what happens if the client lists both an OCB mode encryption
algorithm and the "none" data integrity algorithm on top, and the server
turns out not to support the OCB mode encryption algorithm? It seems the
outcome of the algorithm negotiation would be an encryption algorithm
that doesn't support data integrity, coupled with the "none" data
integrity algorithm. Should the client simply disconnect if this
happens, or what? It seems to me that would only result in unnecessary
round-trips.

Secondly, using the "none" data integrity algorithm implies that the
implicit message counter is simply unprocessed (since this is what the
"none" data integrity algorithm does with the message counter), which
would open up for replay attacks.

-- 
Henrick Hellström
www.streamsec.com

---

From: [email-masked] (Peter Gutmann)
Date: Mon, 18 Apr 2005 22:41:41 +1200

Derek Fawcus <[email-masked]> writes:

>including integrity algorithm could always simply be used with SSH by
>choosing a SSH MAC of "none".  Certainly that's what I thought when I was
>considering hacking in use of OCB.

That doesn't seem right, it implies there's no MAC at all, and could lead to
problems with e.g. an encryption algorithm of 3DES and a MAC of none.  I think
it'd be more intuitive (and safer) to require that both the crypto and MAC
algorithm to have the same value, since crypto = MAC and MAC = crypto.

Peter.

---

From: Bill Sommerfeld <[email-masked]>
Date: Mon, 18 Apr 2005 10:00:48 -0400

> a SSH MAC of "none".  Certainly that's what I thought when I was considering

[wg chair hat off; just a suggestion]

how about listing the combined mode cipher in both the "cipher" and the
"mac" lists?  that avoids the unambiguity problem -- if you know what it
is, you'll know to accept it on an all-or-none basis; if you don't know
what it is, you'll reject both instances of it.

						- Bill

---

From: Jon Bright <[email-masked]>
Date: Mon, 18 Apr 2005 16:16:50 +0200

> what it is, you'll reject both instances of it.

I was going to suggest the same thing.  And if someone worked up a draft 
for the cipher, the draft could say if the MAC "blahblah" is chosen, the 
cipher "blahblah" MUST be chosen.  If the cipher "blahblah" is chosen, 
the MAC "blahblah" SHOULD be chosen.

-- 
Jon Bright
Silicon Circus Ltd.
http://www.siliconcircus.com

---

From: Simon Tatham <[email-masked]>
Date: Mon, 18 Apr 2005 15:27:33 +0100

> what it is, you'll reject both instances of it.

I think the problem is that this is inconsistent with the algorithm
mandated by the transport protocol for choosing ciphers and MACs:
the chosen cipher must be the first one on the client's list which
is also in the server's list, and likewise with MACs. Suppose, for
example, that a client's cipher list has (say) AES followed by
Helix, but its MAC list has Helix followed by (say) HMAC-SHA-1, and
suppose the server supports all of these things. The transport
protocol then _requires_ that both sides agree to use AES as cipher
and Helix as MAC, which makes no sense.

You could solve this by having the (hypothetical?) Helix-for-SSH
draft specify an override to the normal cipher/MAC selection
process: `if the normal cipher and MAC selection selects Helix as
only one of or MAC for a particular direction, then Helix must be
used as both cipher and MAC for that direction, superseding whatever
the normal selection algorithm chose for the other slot'. It isn't
100% clear that this gives you the right priorities, but it would at
least be unambiguous.
-- 
Simon Tatham         "_shin_, n. An ingenious device for
<[email-masked]>    finding tables and chairs in the dark."

---

From: Derek Fawcus <[email-masked]>
Date: Mon, 18 Apr 2005 15:37:08 +0100

> algorithm to have the same value, since crypto = MAC and MAC = crypto.

Well it depends upon what one is trying to convey.  Strictly there is no outer
SSH MAC in this case,  so I'd argue that "none" is correct.

Unfortunatly as has been pointed out the the selection rules rather mess things
up here wrt to the effect on other cypher+MAC combinations if a combined algorithm
ends up not being selected.

I guess the simplest approach is to say that if a combined algorithm is chosen,
then the MAC offered is simply ignored,  and the protocol then proceeds as if
both ends had offered "none" as their preferred MAC.

DF

---

From: Ben Harris <[email-masked]>
Date: Mon, 18 Apr 2005 16:06:59 +0100

>isn't designed to handle such encryption.

I'd noticed this too, and was planning to address it once I'd got my current
SSH projects out of the way.  I'm glad to see that someone else is working
on it.

>specified in section 7.1 of SSH-TRANS.

My feeling about this is that the simplest way is to have the definition of
[email-masked] and friends include a rule like this:

  If the negotiated cipher algorithm for a direction is [email-masked],
  the negotiated MAC algorithm for that direction shall be ignored and the
  integrity protection provided by Helix be used instead.

Note that this _isn't_ the same as just using Helix for the MAC, since the
MAC and encryption keys in SSH are usually different.

>result in the desired state.)

My understanding was that the nonce in Helix and OCB had the same purpose as
the sequence number in the usual SSH MAC, so as to make the latter
technically unnecessary if using those modes.  It doesn't really matter, of
course, since feeding an extra four bytes into the MAC is hardly going to
kill performance.

-- 
Ben Harris

---

From: "denis bider" <[email-masked]>
Date: Mon, 18 Apr 2005 19:24:52 +0200

[Ben Harris]

> My understanding was that the nonce in Helix and OCB had the 
> same purpose as the sequence number in the usual SSH MAC, so 
> as to make the latter technically unnecessary if using those 
> modes.  It doesn't really matter, of course, since feeding an 
> extra four bytes into the MAC is hardly going to kill performance.

The problem is that a higher-level layer can rely on the SSH sequence number
- for example, it is used in SSH_MSG_UNIMPLEMENTED, so it must be there and
must be authenticated, or replaced by something 100% equivalent. Therefore
any Helix-in-SSH draft needs to spell out what happens to the SSH sequence
number:

- whether it is replaced entirely by some other field, in which case the SSH
sequence number is discarded and that other field needs to have the same
form and characteristics as the SSH sequence number (word32, incremented by
one, etc);

- or whether the SSH sequence number stays there but is also appended or
prepended to the plaintext before encryption, thereby authenticating it;

- or something else that works.

denis

---

From: "Sara Golemon" <[email-masked]>
Date: Mon, 18 Apr 2005 10:28:08 -0700

As a more general solution to this problem, how about an ability to
renegotiate methods?  If the client notices that there's a common cipher
available that allows for data integrity, it can send a new KEXINIT
requesting just that cipher and a mac of 'none'.  The server could then
respond with it's own KEXINIT which agrees with that request, or perhaps
another response rejecting the renegotiation (a KEXINIT with empty methods
would probably suffice for an explicit rejection).  If the server never
sends a KEXINIT in response then it can just be assumed by the client that
renegotiation is not supported.

This way, not only is the specific case being discussed covered, but so are
other edge cases (perhaps a session wants compression off initially--for an
interactive terminal-- Then on later for a large file transfer).

As to implementation specifics, I'd see a key exchange following the
KEXreINIT being reasonable, but the session_id should remain the same (as
with other key re-exchanges).  If that's just too wasteful, maybe one of the
reserved bits in the KEXINIT packet can be used to suppress key re-exchange.

-Sara

---

From: [email-masked] (Markus Gyger)
Date: Mon, 18 Apr 2005 20:42:16 +0200 (CEST)

Sara Golemon writes:
[re 2nd KEXINIT]
> interactive terminal-- Then on later for a large file transfer).

FYI, there is an OpenSSH patch that turns off encryption this way after
authentication is done: http://www.psc.edu/networking/projects/hpn-ssh/

Markus

---

From: Ben Harris <[email-masked]>
Date: Mon, 18 Apr 2005 19:43:41 +0100

>any Helix-in-SSH draft needs to spell out what happens to the SSH sequence

The obvious approach is that it effectively becomes part of the nonce.  To
avoid too much wheel-reinvention, I'd make the nonce the same as the counter
used by newmodes, so you could extract the sequence number by:

seq(pkt) = nonce(pkt) - nonce(NEWKEYS) + seq(NEWKEYS)

(where seq(x) is the sequence number of packet x, nonce(x) is the nonce of
packet x (as an integer), and NEWKEYS is the SSH_MSG_NEWKEYS packet that
started the use of this key.  nonce(NEWKEYS) is the IV generated by the KEX
algorithm.)

Of course, you wouldn't actually do that -- you'd just keep a counter the
same way you do now and increment it when you received a packet MAC'ed with
the next nonce in sequence.

I'm still not entirely sure that this is safe, or that all
authenticated-encryption modes have this kind of nonce, but then I'm also
not sure they all have the facility to MAC data without also encrypting them.

-- 
Ben Harris

---

From: Ben Harris <[email-masked]>
Date: Mon, 18 Apr 2005 20:09:47 +0100

In article <[email-masked]> you write:
>renegotiate methods?

We already have that to a large extent.  Either end can send a KEXINIT at
any time apart from during key exchange, and negotiate a different set of
settings from last time, and this could actually be used to accomplish what
you want:

client enc: [email-masked],3des-cbc
       mac: hmac-sha1
server enc: [email-masked],3des-cbc
       mac: hmac-sha1
< both notice that this is silly >
client enc: [email-masked],3des-cbc
       mac: none,hmac-sha1
server enc: [email-masked],3des-cbc
       mac: none,hmac-sha1

My worry here is that this kind of renogotiation opens up the possibility of
the two ends getting into a loop, with one end thinking it can do better
after each negotiation.

>If the client notices that there's a common cipher
>would probably suffice for an explicit rejection).

Is this actually necessary?  In the example above, the server could reject
the overture by just sending the same KEXINIT it sent the first time.

>If the server never

All servers are already required to support it.

>interactive terminal-- Then on later for a large file transfer).

2005-04-18 20:05:55	Server version: SSH-1.99-OpenSSH_3.8.1p1 Debian-8.sarge.4
2005-04-18 20:05:55	We claim version: SSH-2.0-PuTTY_Local:_Apr_18_2005_20:04:17
...
2005-04-18 20:06:13	Initiating key re-exchange (compression setting changed)
2005-04-18 20:06:13	Doing Diffie-Hellman group exchange
2005-04-18 20:06:13	Doing Diffie-Hellman key exchange
2005-04-18 20:06:14	Initialised AES-256 SDCTR client->server encryption
2005-04-18 20:06:14	Initialised HMAC-SHA1 client->server MAC algorithm
2005-04-18 20:06:14	Initialised zlib (RFC1950) compression
2005-04-18 20:06:14	Initialised AES-256 SDCTR server->client encryption
2005-04-18 20:06:14	Initialised HMAC-SHA1 server->client MAC algorithm
2005-04-18 20:06:14	Initialised zlib (RFC1950) decompression

-- 
Ben Harris

---

From: "Sara Golemon" <[email-masked]>
Date: Mon, 18 Apr 2005 12:44:55 -0700

> the overture by just sending the same KEXINIT it sent the first time.
Sending the same methods may (and most likely would) yield an agreeable set
of methods and allow the renegotiation to take place.  My intent with
sending blank methods is to allow the endpoint to say, "No, I don't support
renegotiation at all, even if it makes sense to do so."

> All servers are already required to support it.
I'm sorry, where in the draft does it say that?  It mentions KEY re-exchange
(and recommends it be done regularly), but not methods.  Of course, method
renegotiation isn't explicitly prohibited either...

Given that method renegotiation is appearantly part of the spec, I'd be
inclined to ask: "So why not use it for this ciphers containing data
integrity issue?"  It seems like a much more straightforward approach than
adding per-cipher specific logic to the method selection criteria.

> the two ends getting into a loop, with one end thinking it can do better
Excellent point.  Given that method renegotiation is already allowed, what
is the accepted policy for dealing with such a situation?  Left to
individual vendor implementation to 'be the bigger stack' and give up
eventually?

Taking another tack, how about a psuedo-mac?  e.g. none-ocb  Which is "none
MAC available only when coupled with an ocb cipher".  This could be placed
at the front of the methods list (avoiding any major changes to the
selection criteria), but its use would be dependant on the selected cipher.
This is similar to the coupling between kex method and hostkey method (If
kex requires an encryption capable hostkey method, then signing only methods
are ignored).

-Sara

-Sara

---

From: Ben Harris <[email-masked]>
Date: Mon, 18 Apr 2005 21:02:52 +0100

>renegotiation isn't explicitly prohibited either...

transport-24, section 9, second paragraph, fourth sentence:

                                                   It is permissible to
   change some or all of the algorithms during the re-exchange.

>adding per-cipher specific logic to the method selection criteria.

1: I'm scared of infinite loops.
2: It's expensive.  Diffie-Hellman takes quite a lot of CPU, and doing it
   several times is going to make session set-up quite a lot slower.

>is the accepted policy for dealing with such a situation?

I think the accepted policy is not to trigger a re-key based on the results
of a previous key-exchange.  That way, you can never end up in a loop.

>kex requires an encryption capable hostkey method, then signing only methods

I don't think there's anything intrinsically wrong with that idea, but I
don't see that it has any advantage over having OCB just override the
selected MAC (which is equivalent to always having "none-ocb" at the start
of the MAC list).  Are there circumstances where one might want to use OCB
(or similar) with an external MAC?

-- 
Ben Harris

---

From: "Sara Golemon" <[email-masked]>
Date: Mon, 18 Apr 2005 14:26:29 -0700

>    change some or all of the algorithms during the re-exchange.
Thanks!

> (or similar) with an external MAC?
I can't honestly imagine any.  Both methods rely on understanding of one
assumption or another.   The only real difference is that one is implicit,
the other is explicit.  I'm just offering my thoughts to the discussion for
whatever they're worth.

-Sara

---

From: [email-masked] (Niels Möller)
Date: 19 Apr 2005 08:33:55 +0200

> `if the normal cipher and MAC selection selects Helix as only one of
> or MAC for a particular direction, then Helix must be used as both
> cipher and MAC for that direction, superseding whatever the normal
> selection algorithm chose for the other slot'

I think one could define the procedure as follows:

  If helix is selected as the cipher to use by the ordinary selection
  mechanism, *and helix is present* on both parties' lists of
  authentication methods, then helix must be used for authentication,
  bypassing the usual selection rules for the authentication method.

In effect, it says that implementations supporting helix should do the
cipher selection before the authentication selection.

This doesn't conflict too badly with current procedures. However, it
still shouldn't be done lightly, because it *will* conflict when
somebody proposes the analogous change with a reverse dependency

  If foo is selected as the authentication method, and foo is present
  on the cipher list of both parties, then foo must be used also for
  encryption.

An alternative of a slightly different flavour, but which still
introduces a dependency between cipher selection and authentication
selection, is the following rule:

  If all occurances of helix on the authentication lists must be
  ignored unless helix is also used for the cipher for the
  corresponding data stream.

Both these alternatives make it possible to use helix + a different
mac.

Regards,
/Niels

---

From: "denis bider" <[email-masked]>
Date: Tue, 19 Apr 2005 10:20:17 +0200

[Sara Golemon]
> Given that method renegotiation is appearantly part of the 
> spec, I'd be inclined to ask: "So why not use it for this 
> ciphers containing data integrity issue?"  It seems like a 
> much more straightforward approach than adding per-cipher 
> specific logic to the method selection criteria.

The per-cipher specific logic in this case would be very simple (requiring
only very local code change), efficient in terms of additional roundtrips
(none required), and compatible with the installed base (special rules for
helix are orthogonal to rules currently in use), whereas the proposal to use
renegotiation for this purpose is complex (key re-exchange is like turning a
bus on a highway), inefficient (requires many additional roundtrips for
something that could be done without any), and not necessarily compatible
with the installed base (though key re-exchange is required, not all
implementations support it).

I therefore think that harnessing key re-exchange for this purpose would be
a very bad decision.

---

From: Henrick Hellström <[email-masked]>
Date: Thu, 21 Apr 2005 09:14:13 +0200

> not sure they all have the facility to MAC data without also encrypting them.

I'd say that is not a good idea. The best way is to use random per 
packet nonces sent explicitly by the sender, and process the sequence 
number as implicit unencrypted header data. This operation is supported 
by Helix, CCM and EAX. (OCB doesn't support processing of unencrypted 
header data, but is designed for nonces that are sequence numbers).

I am not sure exactly how you would implement your solution, but there 
are two things to keep in mind:

* There are differential attacks against Helix that exploit repeated 
nonces. Given the nature of differential attacks and how the nonce is 
processed by Helix, I guess the only safe way to prevent them would be 
to use independently random nonces. Simply incrementing the nonce by one 
for each packet would result in nonces with a pair-wise low hamming 
difference. That gives me chills rather than a warm fuzzy feeling.

* One trivial method of making the nonces independent and still mix in 
the sequence number would unfortunately not provide protection against 
replay attacks. This would happen if you e.g. used the formula:

nonce(pkt) = nonce(NEWKEYS) + seq(pkt) - seq(NEWKEYS) + sentnonce(pkt)

(where nonce(pkt) is the effective nonce fed into the algorithm by the 
implementation, and sentnonce is a random value generated by the sender 
and prefixed to the packet that is sent to the other peer.) The problem 
with this is that an active attacker can resend packets simply by 
modifying sentnonce(X) in accordance with the formula to make the packet 
pass as having any other sequence number.

-- 
Henrick Hellström
www.streamsec.com

---

From: Ben Harris <[email-masked]>
Date: Thu, 21 Apr 2005 16:34:19 +0100 (BST)

On Thu, 21 Apr 2005, Henrick Hellström wrote:

[ Using counters as nonces in authenticated ciphers ]

> I'd say that is not a good idea. The best way is to use random per packet 
> nonces sent explicitly by the sender, and process the sequence number as 
> implicit unencrypted header data. This operation is supported by Helix, CCM 
> and EAX. (OCB doesn't support processing of unencrypted header data, but is 
> designed for nonces that are sequence numbers).

As far as I can see, CCM and EAX aren't interesting, since they're no 
cheaper than using a separate block cipher and MAC.  That suggests that we 
should be concentrating on OCB and Helix at present, which appear to have 
rather different requirements from one another.

> I am not sure exactly how you would implement your solution, but there are 
> two things to keep in mind:
>
> * There are differential attacks against Helix that exploit repeated nonces. 
> Given the nature of differential attacks and how the nonce is processed by 
> Helix, I guess the only safe way to prevent them would be to use 
> independently random nonces. Simply incrementing the nonce by one for each 
> packet would result in nonces with a pair-wise low hamming difference. That 
> gives me chills rather than a warm fuzzy feeling.

Having read Muller's FSE2004 paper, I agree -- feeding related nonces to 
Helix looks like being a bad idea, though this is obviously not a problem 
for OCB.

Thus, I think we have two situations:

For OCB, the nonce can be a counter (initialised by the IV from KEX), and 
the SSH sequence number need not be directly handled by OCB at all.

For Helix, the nonce needs to be effectively random.  I see two obvious 
ways of achieving this:

1: Generate a random nonce for each message and send it with the nonce.
    This adds extra data to each packet, but is probably relatively cheap.
    It requires that the SSH sequence number be processed as header data by
    Helix.

2: Feed a counter through a one-way function (either a block cipher or a
    hash) to generate the nonce.  This is more expensive (at least if you
    use a hash), but saves on network traffic and means that the sequence
    number is implicit in the nonce so that it need not be processed by
    Helix (though it may as well be, since doing so is cheap).

-- 
Ben Harris

---

From: Henrick Hellström <[email-masked]>
Date: Thu, 21 Apr 2005 17:53:12 +0200

>    Helix (though it may as well be, since doing so is cheap).

The obvious solution would be to use a separately keyed instance of 
Helix as a continuous PRNG. The PRNG seed (i.e. the second Helix key and 
nonce) could be the initial IV from the NEWKEYS.

-- 
Henrick Hellström
www.streamsec.com

---

From: Ben Harris <[email-masked]>
Date: Thu, 21 Apr 2005 17:35:59 +0100

>nonce) could be the initial IV from the NEWKEYS.

Ah yes, of course.  Why didn't I think of that?

-- 
Ben Harris