Subject: draft-miller-secsh-umac-00.txt

From: Damien Miller <[email-masked]>
Date: Wed, 13 Jun 2007 07:23:23 +1000 (EST)

Hi,

Attached is a draft for the use of Ted Krovetz' UMAC (RFC4418) as
a SSH MAC. OpenSSH -current implements the umac-64 method described
in the draft under the name "[email-masked]".

We'd be interested in hearing from anyone else who wants to implement it.

-d

---

From: Ben Harris <[email-masked]>
Date: Wed, 13 Jun 2007 13:32:49 +0100

>We'd be interested in hearing from anyone else who wants to implement it.

I haven't tried implementing this yet, but I notice one thing that could
be simplified.  The sequence number in SSH MACs is usually represented
as a uint32, and UMAC only requires that the nonce be a string of length
1 to BLOCKLEN bytes, so it seems a little strange to insist on padding
the sequence number to 8 bytes.  Why not just pass the 4-byte version of
the sequence number as the nonce?

On a more mundane note, you've forgotten your IANA Considerations.

-- 
Ben Harris

---

From: Simon Tatham <[email-masked]>
Date: Wed, 13 Jun 2007 14:55:14 +0100

> in the draft under the name "[email-masked]".

Since you don't specify what block cipher is used by your UMAC
methods, I presume it's AES-128, since RFC4418 says that's the
default if not otherwise explicitly stated.

So an obvious question is: is it sensible to mandate a fixed block
cipher, when UMAC helpfully provides flexibility in this area? Is
that flexibility not potentially an advantage? Have you considered
alternative options such as

 (a) calling it umac-64-aes128 and thereby leaving open an obvious
     avenue to introduce UMAC over other ciphers if necessary?

 (b) defining UMAC to use whatever block cipher is chosen by the
     normal key exchange process? (Though I suppose you'd at the
     very least have to introduce a special case to preserve MAC
     functionality when the kex process settles on the `none'
     cipher.)

I think that at the very least I'd be marginally more comfortable if
this draft specifically stated that the default AES-128 was in use.

I note in passing that UMAC might be less useful than HMAC in
crypto-hostile jurisdictions, since you can't implement it without
first implementing a block cipher and so literal-minded crypto laws
which forbid code which implements a block cipher might also forbid
UMAC while being not too unhappy with MDx- or SHA-based HMAC which
are only (in practice) used for integrity protection. Not that that
should be an argument against its _optional_ adoption, of course.
-- 
Simon Tatham         "You may call that a cheap shot.
<[email-masked]>    I prefer to think of it as good value."

---

From: "Wei Dai" <[email-masked]>
Date: Wed, 13 Jun 2007 10:41:30 -0700

> in the draft under the name "[email-masked]".

Have you also looked at Ted's new VMAC algorithm? It's still in Internet 
Draft stage, but it's simpler than UMAC and is also significantly faster on 
many platforms, especially 64-bit platforms. Public domain implementations 
are available from http://www.fastcrypto.org/vmac/ and 
http://www.cryptopp.com. (Disclosure: I contributed several ideas to the 
current VMAC design and am a co-author of the VMAC draft.)

Both UMAC and VMAC require unique nonces. Using the sequence number as the 
nonce as in your draft may cause nonces to be reused if someone takes a 
snapshot of an active SSH connection running an a virtual machine, and when 
that snapshot is restored, the SSH program sends out new packets before 
realizing that the connection is no longer valid.

Unless there is a good reason to believe this can't occur, it would be safer 
to use random nonces instead.

---

From: Ben Harris <[email-masked]>
Date: Wed, 13 Jun 2007 22:13:48 +0100

[This time _with_ the mailing list]

>     functionality when the kex process settles on the `none'

Please, no!  I suppose there might be some small gain from this, but 
nothing like enough to outweigh the horribleness of the idea.

>this draft specifically stated that the default AES-128 was in use.

That might be nice, but I think RFC 4418 is clear enough that AES-128 is 
implied.

-- 
Ben Harris

---

From: Ben Harris <[email-masked]>
Date: Wed, 13 Jun 2007 22:30:21 +0100

[Today is a bad day for forgetting to Cc the list.]

>realizing that the connection is no longer valid.

Many of the SSH algorithms break in those circumstances.  For instance, 
any stream cipher (including block ciphers in SDCTR mode) will leak 
hugely if the keystream gets reused.

>to use random nonces instead.

Would that help?  I'd expect the restored PRNG to at least start in sync 
with its former self.

In general, I think SSH assumes that time is linear, and isn't designed 
to work in the presence of forking time-streams.  This should probably 
have been mentioned in its Security Considerations.

-- 
Ben Harris

---

From: der Mouse <[email-masked]>
Date: Wed, 13 Jun 2007 17:47:20 -0400 (EDT)

>> [...save and restore virtual machine state...]
> Many of the SSH algorithms break in those circumstances.  For
> instance, any stream cipher (including block ciphers in SDCTR mode)
> will leak hugely if the keystream gets reused.

Only if the datastream isn't.  (Perhaps fortunately, the data stream is
likely to be identical to the original in such a case...at least long
enough for the connection to be torn down.)

> In general, I think SSH assumes that time is linear, and isn't
> designed to work in the presence of forking time-streams.  This
> should probably have been mentioned in its Security Considerations.

"Security considerations: this program assumes it is operating in a
space-time continuum with only one time dimension." :-)

/~\ The ASCII				der Mouse
\ / Ribbon Campaign
 X  Against HTML	       [email-masked]
/ \ Email!	     7D C8 61 52 5D E7 2D 39  4E F1 31 3E E8 B3 27 4B

---

From: Nicolas Williams <[email-masked]>
Date: Wed, 13 Jun 2007 17:09:20 -0500

> space-time continuum with only one time dimension." :-)

And with time running only in one direction (hereinafter: "forward" ;)

I don't think there's a dependence on time being monotonic and
non-discrete at a quantum level, just that it not go backward.

:)

But note that even in a VM save/restore case time goes forward (well,
from our p.o.v. anyways.  So we may need a more precise description of
the problem.

I propose that we say that SSHv2 (and probably most cryptographic
protocols) is not continuation reentrance safe ('continuation
reentrance' meaning, here, calling a Scheme-like continuation function
of indefinite extent more than once).

Nico
--

---

From: Damien Miller <[email-masked]>
Date: Thu, 14 Jun 2007 11:15:34 +1000 (EST)

On Wed, 13 Jun 2007, Wei Dai wrote:

> Have you also looked at Ted's new VMAC algorithm? It's still
> in Internet Draft stage, but it's simpler than UMAC and is
> also significantly faster on many platforms, especially 64-bit
> platforms. Public domain implementations are available from
> http://www.fastcrypto.org/vmac/ and http://www.cryptopp.com.
> (Disclosure: I contributed several ideas to the current VMAC design
> and am a co-author of the VMAC draft.)

I had noticed it when we first started looking at UMAC, but it seems to
have progressed quite a bit since then - thanks for the pointer.

> Both UMAC and VMAC require unique nonces. Using the sequence number as
> the nonce as in your draft may cause nonces to be reused if someone
> takes a snapshot of an active SSH connection running an a virtual
> machine, and when that snapshot is restored, the SSH program sends out
> new packets before realizing that the connection is no longer valid.
>
> Unless there is a good reason to believe this can't occur, it would be
> safer to use random nonces instead.

I don't think that this is a very likely attack for the SSH protocol. The
attacker would need:

1. The ability to snapshot the SSH sender and resume it at will.
2. The ability to inject different data into the SSH sender once it has
   resumed, so that MAC nonces are reused with different data.
3. The ability to circumvent the symmetric crypto in SSH.

If all these came together, *and* the attacker was able to completely
break UMAC with the resulting data, then they could spoof the remote end
back to the local sender. The attacker would need to be able to do this
before the remote end gave up and, unless they are prepared to spoof TCP
at the sender, would get <= 1 TCP window of data from the SSH sender to
work with.

Such a scenario doesn't seem very likely: apart from needing to
cirvumvent the symmetric crypto in order to make the MAC match the
decrypted packet, the ability to snapshot and resume a VM is very likely
to imply access to the memory contents of the SSH sender, from which
they could read the MAC keys out directly.

If the attacker doesn't have any magic way around the symmetric crypto,
then they would have to guess, using their captive VM'd process as
an oracle. The smallest useful packet they could guess at would be a
SSH_MSG_CHANNEL_DATA packet:

  packet_len | padding_len | type | channel_id | data_len | data | padding
      u32          u8         u8       u32         u32

The smallest such packet would be for a single byte of channel data, so
the overall padded length would be 16 bytes, of which 1 byte would be
padding.

Even if we assume that the attacker's success criteria is injection
of *any* data into an open channel, then the only non-critical fields
in the packet are the data and the padding (2 bytes). If they got
packet_len, padding_len, type, or data_len wrong, then the packet
would not parse successfully. If they got channel_id wrong, then the
implementation would either disconnect or ignore the data, and most
sessions would have only a small number of channels open (OpenSSH's
default limit is 10). So there would be only around 2^16 correct guesses
in a space of 2^128.

On the other hand, using random nonces has two downsides: first, they
would either need to be added to the packet (overhead) or generated by
some agreed PRF (more protocol complexity). Secondly, UMAC performs best
when the nonces are monotonically increasing counters and so using a
per-packet random nonce would slow it down.

-d

---

From: Damien Miller <[email-masked]>
Date: Mon, 18 Jun 2007 09:50:09 +1000 (EST)

On Thu, 14 Jun 2007, Damien Miller wrote:

> > Both UMAC and VMAC require unique nonces. Using the sequence number
> > as the nonce as in your draft may cause nonces to be reused if
> > someone takes a snapshot of an active SSH connection running an a
> > virtual machine, and when that snapshot is restored, the SSH program
> > sends out new packets before realizing that the connection is no
> > longer valid.
> >
> > Unless there is a good reason to believe this can't occur, it would
> > be safer to use random nonces instead.

Markus Friedl suggested a good compromise: use the KEX PRF to extract
192 bits of MAC key, give the first 128 to UMAC and use the remaining 64
bits as a "nonce seed".

The nonce that is supplied to UMAC can be nonce_seed + sequence_number.
The seed would be private like the other keying material and, while the
nonces would still be reused under this attack, the actual nonce values
would be not be known to the attacker.

This tweak does not need any new PRF, and it preserves UMACs
optimisation when the nonce is a monotonic big endian counter.

Thoughts?

-d

---

From: Ben Harris <[email-masked]>
Date: Mon, 18 Jun 2007 14:23:02 +0100

>would be not be known to the attacker.

Does that help?  RFC 4418 certainly doesn't suggest that it does -- it 
says that repeated nonces break the security guarantee, with no 
suggestion that the secrecy or otherwise of the nonce makes a 
difference.

In any case, isn't 64 bits too short to be a useful secret?

-- 
Ben Harris