draft-miller-secsh-umac-00.txt

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 "umac-64 <at> openssh.com".

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

-d

Network Working Group                                          D. Miller
Internet-Draft                                                P. Valchev
Intended status: Standards Track                                 OpenSSH
Expires: December 13, 2007                                 June 11, 2007


          The use of UMAC in the SSH Transport Layer Protocol
                     draft-miller-secsh-umac-00.txt

Status of this Memo

   By submitting this Internet-Draft, each author represents that any
   applicable patent or other IPR claims of which he or she is aware
   have been or will be disclosed, and any of which he or she becomes
   aware will be disclosed, in accordance with Section 6 of BCP 79.

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

In article <Pine.BSO.4.64.0706130715330.13880 <at> fuyu.mindrot.org> you write:
>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 "umac-64 <at> openssh.com".
>
>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

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

Damien Miller  <djm <at> mindrot.org> wrote:
> 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 "umac-64 <at> openssh.com".

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

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

> 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 "umac-64 <at> openssh.com".

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. 

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

[This time _with_ the mailing list]

In article <E1HyTJa-0007ON-00 <at> ixion.tartarus.org> you write:
> (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.)

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

>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.

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

--

-- 
Ben Harris

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

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

In article <01a601c7ade2$140a9340$0300a8c0 <at> weidai.com> you write:
>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.

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.

>Unless there is a good reason to believe this can't occur, it would be safer 
>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

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

>> [...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	       mouse <at> rodents.montreal.qc.ca
/ \ Email!	     7D C8 61 52 5D E7 2D 39  4E F1 31 3E E8 B3 27 4B

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

On Wed, Jun 13, 2007 at 05:47:20PM -0400, der Mouse wrote:
> >> [...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." 

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

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

On Wed, 13 Jun 2007, Wei Dai wrote:

> > 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 "umac-64 <at> openssh.com".
> 
> 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.

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

On Thu, 14 Jun 2007, Damien Miller wrote:

> On Wed, 13 Jun 2007, Wei Dai 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