Subject: draft-harris-ssh-rsa-kex-02 and a possible future change

From: Ben Harris <[email-masked]>
Date: Thu, 7 Jul 2005 12:33:01 +0100 (BST)

I've uploaded a new version of my RSA KEX draft. 
<http://www.ietf.org/internet-drafts/draft-harris-ssh-rsa-kex-02.txt>

Notable changes are:

1: Using SHA-512 in place of SHA-256.  This is largely because I've got
    the impression that -dh-group-exchange is heading in the direction of
    using SHA-512, and it seems silly to require implementations to support
    both SHA-256 and SHA-512.  Plus of course it gives us headroom in case
    decent collision attacks are found against the higher SHAs.

2: Including the encrypted secret in the data hashed to generate the
    exchange hash.  This should make it much harder for a client to
    generate hash collisions, since they'd need to generate K such that K
    and its RSA encryption between them generate a collision.  I conjecture
    that for reasonable RSA key sizes this is infeasible.

I don't imagine that either of these will be controversial.

I'd like to make another change, to move the transmission of K_S, the 
server's host key, from SSH_MSG_KEXRSA_DONE to SSH_MSG_KEXRSA_PUBKEY.  The 
reason for this would be to ensure that even if the server can change its 
key (which I can imagine being possible for some kinds of certificate), it 
can't use this to mount a collision attack on the exchange hash because it 
doesn't know what secret the client is going to send.  While this is 
rather different from the way the current KEX methods work, I can't 
imagine it being any more difficult for server implementations.  Would any 
client imeplementors find it a problem?

-- 
Ben Harris

---

From: der Mouse <[email-masked]>
Date: Thu, 7 Jul 2005 10:45:45 -0400 (EDT)

> 1: Using SHA-512 in place of SHA-256.

I'm not sure I like this.  SHA-256 is reasonably good for 32-bit
machines; SHA-512 (and SHA-384) are basically 64-bit algorithms,
calling for eight 64-bit temporaries in their core loops.

I think this change will disproportionately hurt exactly those machines
where your kex is most beneficial - old, slow, half-lung machines,
which are usually 32-bit.

>    Plus of course it gives us headroom in case decent collision
>    attacks are found against the higher SHAs.

True, though I'd prefer to address this by defining variants using
block-cipher-based hash functions.

>    exchange hash.

My reaction here is basically "shrug".  I don't really see the hazard
in the client managing to generate two sessions with the same exchange
hash in the first place.

> server's host key, from SSH_MSG_KEXRSA_DONE to SSH_MSG_KEXRSA_PUBKEY.
> [...].  Would any client imeplementors find it a problem?

Tentatively, I wouldn't.  I'll have to look at my code, though, and
make sure I do indeed have (or can easily arrange to have) the host key
at hand at that point.

/~\ 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: Ben Harris <[email-masked]>
Date: Thu, 07 Jul 2005 19:34:32 +0100

>which are usually 32-bit.

You're right.  On a convenient slow machine (50MHzish ARM7500FE), a 2048-bit
RSA public operation takes about 1/3s and a 1024-byte SHA-512 takes about
1/2s.  I haven't got a convenient SHA-256 implementation, but looking at the
spec it's a lot friendlier to small systems.  I'll reverse that change.

>in the client managing to generate two sessions with the same exchange

I don't think there's a hazard there, but there is one if the client gets to
co-operate with (or be) a server using a KEX method that lets the server
choose the last input to the hash.  Such a KEX method would be approximately
as sane as rsa1024-sha1-draft-01, so I can't safely assume that no-one will
ever deploy one.  Indeed, I suspect that the currently-defined KEX methods
might qualify depending on the host key formats in use.

-- 
Ben Harris

---

From: [email-masked] (Peter Gutmann)
Date: Fri, 08 Jul 2005 13:32:11 +1200

>I don't imagine that either of these will be controversial.

They are :-).  An SHA-2 discussion has just finished on the S/MIME list, where
the choice was MUST SHA-256, MAY the others.  The reason for this is that
SHA-512, being targeted at register-rich 64-bit CPUs, is horrible to implement
on the majority of current CPUs, which are neither register-rich (x86), nor
64-bit (any low-power embedded system).  In fact the hardware with 95% or
whatever of the market share (AMD/Intel x86) fails to meet both of these
requirements.

The other point is that there's no strong argument for -512 instead of -256.
The only reason for having it at all is to match large ECC and DLP field sizes
for DSA/ECC signatures, which is hardly a consideration in this case.

Peter.

---

From: Ben Harris <[email-masked]>
Date: Fri, 08 Jul 2005 12:30:35 +0100

In article <[email-masked]> you write:
>They are :-).

So I see.  Expect -03 on Monday.

-- 
Ben Harris