From owner-ietf-ssh@clinet.fi  Tue Jun  6 20:36:32 2000
Return-Path: <owner-ietf-ssh@clinet.fi>
Received: from faui45.informatik.uni-erlangen.de (root@faui45.informatik.uni-erlangen.de [131.188.34.45])
	by faui01.informatik.uni-erlangen.de (8.8.8/8.1.16-FAU) with ESMTP id UAA01850
	for <msfriedl@cip.informatik.uni-erlangen.de>; Tue, 6 Jun 2000 20:36:32 +0200 (MET DST)
Received: from mail.clinet.fi (mail.clinet.fi [194.100.0.7])
	by faui45.informatik.uni-erlangen.de (8.9.1/8.1.49-FAU) with ESMTP id UAA04271
	for <Markus.Friedl@informatik.uni-erlangen.de>; Tue, 6 Jun 2000 20:36:30 +0200 (MET DST)
Received: (from majordom@localhost)
	by mail.clinet.fi (8.9.3/8.9.3) id SAA11797
	for ietf-ssh-outgoing; Tue, 6 Jun 2000 18:39:17 +0300
Received: from citi.umich.edu (citi.umich.edu [141.211.92.141])
	by mail.clinet.fi (8.9.3/8.9.3) with ESMTP id SAA11783
	for <ietf-ssh@clinet.fi>; Tue, 6 Jun 2000 18:39:08 +0300
Received: from citi.umich.edu (india.citi.umich.edu [141.211.92.147])
	by citi.umich.edu (Postfix) with ESMTP id B75BC207C1
	for <ietf-ssh@clinet.fi>; Tue,  6 Jun 2000 11:38:55 -0400 (EDT)
From: Niels Provos <provos@citi.umich.edu>
Subject: Diffie-Hellman Group Exchange
To: ietf-ssh@clinet.fi
Date: Tue, 06 Jun 2000 11:38:55 -0400
Message-Id: <20000606153855.B75BC207C1@citi.umich.edu>
Sender: owner-ietf-ssh@clinet.fi
Precedence: bulk
Content-Length: 265
Lines: 15

Hi,

an internet-draft of the

 "Diffie-Hellman Group Exchange for the SSH Transport Layer Protocol"

is now available as

  draft-provos-secsh-dh-group-exchange-00.txt

Bodo and Markku could you please see if your concerns have been
addressed.

Greetings,
 Niels.
From owner-ietf-ssh@clinet.fi  Tue Jun  6 21:54:44 2000
Return-Path: <owner-ietf-ssh@clinet.fi>
Received: from faui45.informatik.uni-erlangen.de (root@faui45.informatik.uni-erlangen.de [131.188.34.45])
	by faui01.informatik.uni-erlangen.de (8.8.8/8.1.16-FAU) with ESMTP id VAA07901
	for <msfriedl@cip.informatik.uni-erlangen.de>; Tue, 6 Jun 2000 21:54:40 +0200 (MET DST)
Received: from mail.clinet.fi (mail.clinet.fi [194.100.0.7])
	by faui45.informatik.uni-erlangen.de (8.9.1/8.1.49-FAU) with ESMTP id VAA10327
	for <Markus.Friedl@informatik.uni-erlangen.de>; Tue, 6 Jun 2000 21:54:39 +0200 (MET DST)
Received: (from majordom@localhost)
	by mail.clinet.fi (8.9.3/8.9.3) id UAA23762
	for ietf-ssh-outgoing; Tue, 6 Jun 2000 20:28:04 +0300
Received: from ssh.com (fw.hel.fi.ssh.com [193.64.193.124])
	by mail.clinet.fi (8.9.3/8.9.3) with ESMTP id UAA23756
	for <ietf-ssh@clinet.fi>; Tue, 6 Jun 2000 20:28:03 +0300
Received: from torni.hel.fi.ssh.com (torni.hel.fi.ssh.com [10.1.0.43])
	by ssh.com (8.9.3/8.9.3/SSH-1.16) with ESMTP id UAA27256;
	Tue, 6 Jun 2000 20:28:03 +0300 (EEST)
Received: (from mkojo@localhost)
	by torni.hel.fi.ssh.com (8.9.3/8.9.3/SSH-1.17) id UAA00391;
	Tue, 6 Jun 2000 20:28:02 +0300 (EET DST)
Date: Tue, 6 Jun 2000 20:28:02 +0300 (EET DST)
Message-Id: <200006061728.UAA00391@torni.hel.fi.ssh.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
From: Mika Kojo <mkojo@ssh.com>
To: Niels Provos <provos@citi.umich.edu>
Cc: ietf-ssh@clinet.fi
Subject: Diffie-Hellman Group Exchange
In-Reply-To: <20000606153855.B75BC207C1@citi.umich.edu>
References: <20000606153855.B75BC207C1@citi.umich.edu>
X-Mailer: VM 6.34 under Emacs 19.34.2
Organization: SSH Communications Security, Finland
Sender: owner-ietf-ssh@clinet.fi
Precedence: bulk
Content-Length: 2670
Lines: 69


Hello all, 

I would like to point out one issue relating to the selection of the
Diffie-Hellman group. (My apologies if this has already been discussed
here, I joined to this list only very recently.)

Let F_q denote the usual finite field of q elements. Then we want to
apply Diffie-Hellman over its multiplicative group. If q = p, and g
\in F_p, we have g^ord(g) == 1 (in F_p^*), that is, ord(g) | p -
1. Yet the proposal requires that ord(g) = (p-1)/2, and ord(g) to be
prime.

In Diffie-Hellman, one is interested in computation of g^e (in F_p^*)
for e \in (1, c < ord(g)). In practice we usually select c << ord(g) =
(p-1)/2, for performance purposes. And indeed there seems to be no
known attack which can utilize this iff log c >= B (where B is a
security bound for square root attacks) and log p >= I (where I is a
security bound for Index calculus). We have B << I for all reasonable
selections of p.

However, it is clear that the problem of breaking Diffie-Hellman is no
longer (if c << ord(g)) the general subgroup discrete logarithm
problem. This gives rise to speculation that an attack might be
developed which in future requires modification to the bound B. (It
seems that e \in (1, (p-1)/2) is claimed in the draft, so my
discussion here is perhaps out of place. However, it is likely that
implementations wish to choose e \in (1, c << (p-1)/2) for
efficiency.)

My current opinion (until someone proves me wrong, or too paranoid) is
that there should be a possibility for negotiating also ord(g). This
would allow the participants to base the difficulty of breaking the
D-H on general subgroup discrete logarithm problem, without losing
efficiency. (Of course, it is still questionable whether D-H itself is
as difficult as general (subgroup) discrete log problem, but
questioning D-H difficulty might be too paranoid.)

This is perhaps marginal speculation, but I think reasonable when
considering e.g. recent problems with IPSec elliptic curves (and the
fact that those problems were conjectured years before hand).

Of course, if ord(g) << (p-1)/2 then parameter verification may end to
be more elaborate than when ord(g) = (p-1)/2.

Lastly I must acknowledge that this point is not mine but from a
recent sci.crypt discussion, where this was mentioned by Eric Verheul.

Best regards, 
Mika Kojo
SSH Communications Security Corp


Niels Provos writes:
> Hi,
> 
> an internet-draft of the
> 
>  "Diffie-Hellman Group Exchange for the SSH Transport Layer Protocol"
> 
> is now available as
> 
>   draft-provos-secsh-dh-group-exchange-00.txt
> 
> Bodo and Markku could you please see if your concerns have been
> addressed.
> 
> Greetings,
>  Niels.
From owner-ietf-ssh@clinet.fi  Wed Jun  7 01:15:58 2000
Return-Path: <owner-ietf-ssh@clinet.fi>
Received: from faui45.informatik.uni-erlangen.de (root@faui45.informatik.uni-erlangen.de [131.188.34.45])
	by faui01.informatik.uni-erlangen.de (8.8.8/8.1.16-FAU) with ESMTP id BAA17892
	for <msfriedl@cip.informatik.uni-erlangen.de>; Wed, 7 Jun 2000 01:15:57 +0200 (MET DST)
Received: from mail.clinet.fi (mail.clinet.fi [194.100.0.7])
	by faui45.informatik.uni-erlangen.de (8.9.1/8.1.49-FAU) with ESMTP id BAA23226
	for <Markus.Friedl@informatik.uni-erlangen.de>; Wed, 7 Jun 2000 01:15:55 +0200 (MET DST)
Received: (from majordom@localhost)
	by mail.clinet.fi (8.9.3/8.9.3) id XAA12021
	for ietf-ssh-outgoing; Tue, 6 Jun 2000 23:52:07 +0300
Received: from citi.umich.edu (citi.umich.edu [141.211.92.141])
	by mail.clinet.fi (8.9.3/8.9.3) with ESMTP id XAA12017
	for <ietf-ssh@clinet.fi>; Tue, 6 Jun 2000 23:52:05 +0300
Received: from citi.umich.edu (india.citi.umich.edu [141.211.92.147])
	by citi.umich.edu (Postfix) with ESMTP
	id 3E2CD207C1; Tue,  6 Jun 2000 16:52:04 -0400 (EDT)
Subject: Re: Diffie-Hellman Group Exchange 
From: Niels Provos <provos@citi.umich.edu>
In-Reply-To: Mika Kojo, Tue, 06 Jun 2000 20:28:02 +0300
To: Mika Kojo <mkojo@ssh.com>
Cc: ietf-ssh@clinet.fi
Date: Tue, 06 Jun 2000 16:52:04 -0400
Message-Id: <20000606205204.3E2CD207C1@citi.umich.edu>
Sender: owner-ietf-ssh@clinet.fi
Precedence: bulk
Content-Length: 1751
Lines: 34

In message <200006061728.UAA00391@torni.hel.fi.ssh.com>, Mika Kojo writes:
>Let F_q denote the usual finite field of q elements. Then we want to
>apply Diffie-Hellman over its multiplicative group. If q = p, and g
>\in F_p, we have g^ord(g) == 1 (in F_p^*), that is, ord(g) | p -
>1. Yet the proposal requires that ord(g) = (p-1)/2, and ord(g) to be
>prime.
The draft actually allows the server to use both type of generators.
It can either be for the whole multiplicative group GF(p) with
ord(g) = p-1, or for a subgroup of GF(p) with ord(g) = (p-1)/2 and
ord(g) prime.  This is because the draft only allows safe primes.

>In Diffie-Hellman, one is interested in computation of g^e (in F_p^*)
>for e \in (1, c < ord(g)). In practice we usually select c << ord(g) =
>(p-1)/2, for performance purposes. And indeed there seems to be no
>known attack which can utilize this iff log c >= B (where B is a
>security bound for square root attacks) and log p >= I (where I is a
>security bound for Index calculus). We have B << I for all reasonable
>selections of p.
The cited paper and the security considerations talk about short
exponents:

   [1] P. C. van Oorschot and M. J. Wiener, On Diffie-Hellman key agreement
       with short exponents, In Advances in Cryptology - EUROCRYPT'96,
       LNCS 1070, Springer-Verlag, 1996, pp.332-343.

>My current opinion (until someone proves me wrong, or too paranoid) is
>that there should be a possibility for negotiating also ord(g). This
This doesnt really make sense since there are only two possible orders,
either p-1 or (p-1)/2, which are about the size of p.  However, if
you have wording that explains this issue better, I'd be happy to
include it in a future version of the draft.
 
Greetings,
 Niels.
From owner-ietf-ssh@clinet.fi  Wed Jun  7 03:49:16 2000
Return-Path: <owner-ietf-ssh@clinet.fi>
Received: from faui45.informatik.uni-erlangen.de (root@faui45.informatik.uni-erlangen.de [131.188.34.45])
	by faui01.informatik.uni-erlangen.de (8.8.8/8.1.16-FAU) with ESMTP id DAA22431
	for <msfriedl@cip.informatik.uni-erlangen.de>; Wed, 7 Jun 2000 03:49:15 +0200 (MET DST)
Received: from mail.clinet.fi (mail.clinet.fi [194.100.0.7])
	by faui45.informatik.uni-erlangen.de (8.9.1/8.1.49-FAU) with ESMTP id DAA29057
	for <Markus.Friedl@informatik.uni-erlangen.de>; Wed, 7 Jun 2000 03:49:14 +0200 (MET DST)
Received: (from majordom@localhost)
	by mail.clinet.fi (8.9.3/8.9.3) id CAA24158
	for ietf-ssh-outgoing; Wed, 7 Jun 2000 02:07:44 +0300
Received: from ssh.com (fw.hel.fi.ssh.com [193.64.193.124])
	by mail.clinet.fi (8.9.3/8.9.3) with ESMTP id CAA24153
	for <ietf-ssh@clinet.fi>; Wed, 7 Jun 2000 02:07:43 +0300
Received: from torni.hel.fi.ssh.com (torni.hel.fi.ssh.com [10.1.0.43])
	by ssh.com (8.9.3/8.9.3/SSH-1.16) with ESMTP id CAA05846;
	Wed, 7 Jun 2000 02:07:43 +0300 (EEST)
Received: (from mkojo@localhost)
	by torni.hel.fi.ssh.com (8.9.3/8.9.3/SSH-1.17) id CAA21153;
	Wed, 7 Jun 2000 02:07:43 +0300 (EET DST)
Date: Wed, 7 Jun 2000 02:07:43 +0300 (EET DST)
Message-Id: <200006062307.CAA21153@torni.hel.fi.ssh.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
From: Mika Kojo <mkojo@ssh.com>
To: Niels Provos <provos@citi.umich.edu>
Cc: Mika Kojo <mkojo@ssh.com>, ietf-ssh@clinet.fi
Subject: Re: Diffie-Hellman Group Exchange 
In-Reply-To: <20000606205204.3E2CD207C1@citi.umich.edu>
References: <20000606205204.3E2CD207C1@citi.umich.edu>
X-Mailer: VM 6.34 under Emacs 19.34.2
Organization: SSH Communications Security, Finland
Sender: owner-ietf-ssh@clinet.fi
Precedence: bulk
Content-Length: 2637
Lines: 61


Niels, 

my apologies for not being explicit. My point in the previous message
was that in the draft the prime p was fixed to be a safe prime (or any
pair <p,g> such that ord(g) ~= p), and it might yield less security at
the same efficiency level as when using smaller subgroup (e.g.  
ord(g) << p).

The paper by van Oorschot and Wiener does not claim that the problem
with using exponents e << ord(g) to be as strong as e ~= ord(g), in
fact they seem to suggest otherwise.

However, as the draft indicates you suggest using exponent ~= p. Thus
you may lose in efficiency, but also this nullifies the point of my
previous message.

The practical benefits of fixing p to a safe prime might overweight
any (very) theoretical problems.


Best regards, 
Mika Kojo
SSH Communications Security Corp


Niels Provos writes:
> In message <200006061728.UAA00391@torni.hel.fi.ssh.com>, Mika Kojo writes:
> >Let F_q denote the usual finite field of q elements. Then we want to
> >apply Diffie-Hellman over its multiplicative group. If q = p, and g
> >\in F_p, we have g^ord(g) == 1 (in F_p^*), that is, ord(g) | p -
> >1. Yet the proposal requires that ord(g) = (p-1)/2, and ord(g) to be
> >prime.
> The draft actually allows the server to use both type of generators.
> It can either be for the whole multiplicative group GF(p) with
> ord(g) = p-1, or for a subgroup of GF(p) with ord(g) = (p-1)/2 and
> ord(g) prime.  This is because the draft only allows safe primes.
> 
> >In Diffie-Hellman, one is interested in computation of g^e (in F_p^*)
> >for e \in (1, c < ord(g)). In practice we usually select c << ord(g) =
> >(p-1)/2, for performance purposes. And indeed there seems to be no
> >known attack which can utilize this iff log c >= B (where B is a
> >security bound for square root attacks) and log p >= I (where I is a
> >security bound for Index calculus). We have B << I for all reasonable
> >selections of p.
> The cited paper and the security considerations talk about short
> exponents:
> 
>    [1] P. C. van Oorschot and M. J. Wiener, On Diffie-Hellman key agreement
>        with short exponents, In Advances in Cryptology - EUROCRYPT'96,
>        LNCS 1070, Springer-Verlag, 1996, pp.332-343.
> 
> >My current opinion (until someone proves me wrong, or too paranoid) is
> >that there should be a possibility for negotiating also ord(g). This
> This doesnt really make sense since there are only two possible orders,
> either p-1 or (p-1)/2, which are about the size of p.  However, if
> you have wording that explains this issue better, I'd be happy to
> include it in a future version of the draft.
>  
> Greetings,
>  Niels.
From owner-ietf-ssh@clinet.fi  Wed Jun  7 19:12:23 2000
Return-Path: <owner-ietf-ssh@clinet.fi>
Received: from faui45.informatik.uni-erlangen.de (root@faui45.informatik.uni-erlangen.de [131.188.34.45])
	by faui01.informatik.uni-erlangen.de (8.8.8/8.1.16-FAU) with ESMTP id TAA19094
	for <msfriedl@cip.informatik.uni-erlangen.de>; Wed, 7 Jun 2000 19:12:23 +0200 (MET DST)
Received: from mail.clinet.fi (mail.clinet.fi [194.100.0.7])
	by faui45.informatik.uni-erlangen.de (8.9.1/8.1.49-FAU) with ESMTP id TAA29260
	for <Markus.Friedl@informatik.uni-erlangen.de>; Wed, 7 Jun 2000 19:12:20 +0200 (MET DST)
Received: (from majordom@localhost)
	by mail.clinet.fi (8.9.3/8.9.3) id SAA19259
	for ietf-ssh-outgoing; Wed, 7 Jun 2000 18:08:02 +0300
Received: from cdc-info.cdc.informatik.tu-darmstadt.de (cdc-info.cdc.informatik.tu-darmstadt.de [130.83.23.100])
	by mail.clinet.fi (8.9.3/8.9.3) with ESMTP id SAA19255
	for <ietf-ssh@clinet.fi>; Wed, 7 Jun 2000 18:07:59 +0300
Received: from cdc1.cdc.informatik.tu-darmstadt.de (cdc1 [130.83.23.10])
	by cdc-info.cdc.informatik.tu-darmstadt.de (Postfix) with ESMTP
	id 6DE3E2C4C; Wed,  7 Jun 2000 17:07:49 +0200 (MET DST)
Received: by cdc1.cdc.informatik.tu-darmstadt.de (8.8.8+Sun/SMI-SVR4)
	id RAA00445; Wed, 7 Jun 2000 17:07:48 +0200 (MET DST)
Date: Wed, 7 Jun 2000 17:07:47 +0200
From: Bodo Moeller <moeller@cdc.informatik.tu-darmstadt.de>
To: Mika Kojo <mkojo@ssh.com>
Cc: Niels Provos <provos@citi.umich.edu>, ietf-ssh@clinet.fi
Subject: Re: Diffie-Hellman Group Exchange
Message-ID: <20000607170746.A431@cdc.informatik.tu-darmstadt.de>
References: <20000606205204.3E2CD207C1@citi.umich.edu> <200006062307.CAA21153@torni.hel.fi.ssh.com>
Mime-Version: 1.0
Content-Type: text/plain; charset=iso-8859-1
Content-Transfer-Encoding: 8bit
X-Mailer: Mutt 1.0i
In-Reply-To: <200006062307.CAA21153@torni.hel.fi.ssh.com>; from mkojo@ssh.com on Wed, Jun 07, 2000 at 02:07:43AM +0300
Sender: owner-ietf-ssh@clinet.fi
Precedence: bulk
Content-Length: 9581
Lines: 201

On Wed, Jun 07, 2000 at 02:07:43AM +0300, Mika Kojo wrote:

[...]
> However, as the draft indicates you suggest using exponent ~= p. Thus
> you may lose in efficiency, but also this nullifies the point of my
> previous message.
> 
> The practical benefits of fixing p to a safe prime might overweight
> any (very) theoretical problems.

Requiring safe primes also leads to practical problems; namely, generating
them is much slower than generating other usable primes.

> Niels Provos:

>> The cited paper and the security considerations talk about short
>> exponents:
>> 
>>    [1] P. C. van Oorschot and M. J. Wiener, On Diffie-Hellman key agreement
>>        with short exponents, In Advances in Cryptology - EUROCRYPT'96,
>>        LNCS 1070, Springer-Verlag, 1996, pp.332-343.

These security considerations apply when  g  generates the
multiplicative group; if it generates an appropriate sub-group, then
"non-safe" primes can be safe to use too.  Let me recycle an earlier
write-up on these issues.

>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
Date: Fri, 7 Apr 2000 11:28:24 +0200 (CEST)
From: bmoeller@hrzpub.tu-darmstadt.de (Bodo Moeller)
To: "IETF Transport Layer Security WG" <ietf-tls@lists.consensus.com>
Subject: Re: forward secrecy, RSA_EXPORT, D-H, etc.

[....]
> bmoeller@hrzpub.tu-darmstadt.de (Bodo Moeller):

>> Unfortunately, TLS ServerDHParams do not include a recommended
>> exponent length; and the client cannot be sure that  g  is a
>> generator of a prime-order subgroup.  Thus it is in general
>> not safe to assume that short exponents can be used.

[...]
> That said, I'm not enough of a DH weenie to know what the
> result of choosing ephemeral DH keys when g doesn't generate
> a prime order subgroup is. Does it just reveal the client 
> key (which isn't important since it's ephemeral anyway) or
> does it compromise the key exchange or the server key or what? 

If the client's ephemeral DH key is compromised, then obviously the
result of the key exchange is compromised too.  The server key is
ephemeral too, so there's nothing additional to attack there.

The relevant details about subgroup structure are as follows:
If  g  is any element of the cyclic group  (Z/pZ)*,
then it generates a subgroup of some order  q  where
q  can be any divisor of  p - 1.  (Note that I'm not requiring
that  q  be a prime.)  Important facts about  q  are:

  -  its largest prime factor  l  (more generally, because the complete
     factorization of  q  may not be known, its largest non-factorable
     factor.  But let's assume that we know the largest prime
     factor; often it is explicitly computed in one of the first
     steps of DH parameter generation.)

  -  the smooth part  s  of  q,  i.e. the largest factor that is the
     product of small primes, where "small" is defined with the
     Pohlig-Hellmann attack in mind.

Now let  Q  denote the bit length of  q,  let  L  denote the bit
length of the  l,  and let  S  denote  the bit length of  s.
(Note that  L + S <= Q.  When I speak of bit lengths, I actually
mean the base-2 log, but I'll pretend it's always an integer and
will ignore the rounding error.)

Then, when we're working in the order-q subgroup of  (Z/pZ)*
generated by  g,  exponents longer than  Q  bits obviously don't
make sense at all.  For attacks that make use the subgroup structure,
only exponents up to  L  bits in length have to be considered
(the attacker can use exponentiation by  q/l  to map any element into
the subgroup of  l  elements; basically, only  L  exponent bits
survive this exponentiation, and after the discrete logarithm
in this smaller subgroup has been found, the hardest sub-task
for finding the discrete log of the original element is done).
And as the smooth part of  q  makes Pohlig-Hellman attacks possible,
S  bits of the discrete logarithm cannot be considered
secret (these  S  bits are usually not actual bits in the binary
representation of the discrete log, but the knowledge is worth  S
bits).  So what remains to be attacked (this is, roughly, a result by
Wiener/van Oorschot, I think) are  L - S  bits if the exponent
has size at least  L;  if exponents are only  E  bits long  (E <= L),
only  E - S  bits must be attacked.

So the requirement to avoid this kind of attacks is  E - S >= 160
(or  122  as in your previous example, or whatever; I use  160
because that's what the DSS uses).  If you know  S  (or some upper
bound for  S), then you can determine how large  E  should be;
but a TLS client cannot do this.

Often DH parameters are created such as  S = 0  (i.e.,  q  is a prime).
Examples:

  -  p  is a strong prime, that is,  p = 2q + 1.  (For strong primes,
     one might also allow  S = 1,  i.e. use a quadratic non-residue
     as  g;  this one bit does not really matter.  In this case,
     when  q  is defined as above,  p = q + 1  where  q/2  is prime.)
     When strong primes are used,  g  can be chosen small to allow for
     efficient exponentation of  g.

  -  g  generates a large prime-order subgroup, where the order  q
     of this subgroup is somewhat smaller than  g;
     e.g. 1024-bit  g,  160-bit  q.  (Schnorr/DSA)
     Such parameters are much faster to create than strong primes;
     however, you cannot force  g  to be small.

But there are other possibilites than S = 0: PGP, for example, makes
sure that  p - 1  has a prime factor that is only a few bits smaller
than  p;  and it then uses a small  g  (for efficiency) without
insisting that  g  generate only the prime-order subgroup.
I.e., we have  S <= 10  or so, and the requirement  E - S >= 160
translates to  E >= 170.

Now assume you take this further and want to achieve two goals
when creating DH parameters for use in ephemeral DH:

  -   g  should be small to speed up exponentation.

  -   DH parameter generation should be fast so that you can use fresh
      parameters often (note that index-calculus attacks for discrete
      logs require a lot of pre-calculation that depends only on  p,
      and once this step has been finished, discrete logs mod  p  can
      be computed efficiently).

Let  P  be the length of the prime  p  that we want to find.
To achieve the above goals, one might use  L = 2/3 P  and  S <= 1/3 P.
That is, if you want  P = 1024,  first create a prime of around 683
bits, and then find a 1024-bit prime  p  that is congruent to 1 modulo
this 683-bit prime.  The requirement for the exponent length  E  is
E >= 160 + S,  i.e. (if we assume the maximum value for  S)
we need  E >= 160 + P/3 = 501.
Now if the client were to use only 160-bit exponents for
these parameters, then we could not rely on the key-exchange being
secure.


Bodo M"oller
<bmoeller@acm.org>
<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<


Thus my proposal is to allow "non-safe" primes and include a
"recommended minimum exponent length" field with the DH parameters.


Additional note: All of the above assumes that the server and the
client use new DH exponents for each exchange even if DH parameters
are reused.  Otherwise, in addition van Oorschot/Wiener attacks,
Lim/Lee attacks have to be taken into account if small subgroups
exists.

(In Lim/Lee attacks, an attacker ignores the generator -- usually a
generator of a prime-order subgroup -- and instead sends a "DH public
value" from a small subgroup.  If the other party continues as usual
using some DH exponent  x,  then effectively only  x mod order-of-subgroup
is actually used, and accordingly there are only few possiblities for
the apparent outcome of this "DH key exchange", and the attacker can
compute all of these.  Now if the attacked party uses the DH result
to, say, encrypt data, then the attacker can test all possible keys
and test-decrypt the encrypted data; as most decryptions will
lead to garbage, it's usually easy to tell which key was the correct
one, and hence what  x mod order-of-subgroup  is.  By doing
this for multiple small subgroups, the attacker can obtain
x mod gcd(order-of-subgroup_1, ..., order-of-subgroup_k),
and if  x  is a small exponent, this may suffice to determine  x.)

If client exponent reuse is desired, then an additional flag or value
could be used by the server to notify the client about the properties
of the DH parameters, but I don't think this optimization is worth
such extra effort -- usually it wouldn't even be used because it
requires a client-side cache and reduces forward secrecy.

If server exponent reuse is desired, which may make more sense because
the server is more likely to be a long-running process handling many
connections, then the server has to know whether its parameters are
safe against Lim/Lee attacks.  If a safe prime is used, for example,
then it's OK (except that it limits forward secrecry); similarly,
it's OK when a prime  p  is used such that  p-1  is the product of a
couple of large primes (this is recommended in the Lim/Lee paper).  In
general, it's not safe.

So my recommendation for this is to explicitly disallow exponent reuse
for clients, to recommend that servers not reuse exponents, and to
discuss some of the concerns when servers want to reuse exponents
anyway (i.e. that they no longer have full forward secrecy, and
that certain properties of the modulus can lead to problems).


-- 
Bodo Mller <moeller@cdc.informatik.tu-darmstadt.de>
PGP http://www.informatik.tu-darmstadt.de/TI/Mitarbeiter/moeller/0x36d2c658.html
* TU Darmstadt, Theoretische Informatik, Alexanderstr. 10, D-64283 Darmstadt
* Tel. +49-6151-16-6628, Fax +49-6151-16-6036
From owner-ietf-ssh@clinet.fi  Thu Jun  8 08:08:05 2000
Return-Path: <owner-ietf-ssh@clinet.fi>
Received: from faui45.informatik.uni-erlangen.de (root@faui45.informatik.uni-erlangen.de [131.188.34.45])
	by faui01.informatik.uni-erlangen.de (8.8.8/8.1.16-FAU) with ESMTP id IAA14482
	for <msfriedl@cip.informatik.uni-erlangen.de>; Thu, 8 Jun 2000 08:08:05 +0200 (MET DST)
Received: from mail.clinet.fi (mail.clinet.fi [194.100.0.7])
	by faui45.informatik.uni-erlangen.de (8.9.1/8.1.49-FAU) with ESMTP id IAA09637
	for <Markus.Friedl@informatik.uni-erlangen.de>; Thu, 8 Jun 2000 08:08:04 +0200 (MET DST)
Received: (from majordom@localhost)
	by mail.clinet.fi (8.9.3/8.9.3) id HAA29326
	for ietf-ssh-outgoing; Thu, 8 Jun 2000 07:11:15 +0300
Received: from ssh.com (fw.hel.fi.ssh.com [193.64.193.124])
	by mail.clinet.fi (8.9.3/8.9.3) with ESMTP id HAA29323
	for <ietf-ssh@clinet.fi>; Thu, 8 Jun 2000 07:11:14 +0300
Received: from torni.hel.fi.ssh.com (torni.hel.fi.ssh.com [10.1.0.43])
	by ssh.com (8.9.3/8.9.3/SSH-1.16) with ESMTP id HAA07626;
	Thu, 8 Jun 2000 07:11:14 +0300 (EEST)
Received: (from mkojo@localhost)
	by torni.hel.fi.ssh.com (8.9.3/8.9.3/SSH-1.17) id HAA17939;
	Thu, 8 Jun 2000 07:11:13 +0300 (EET DST)
Date: Thu, 8 Jun 2000 07:11:13 +0300 (EET DST)
Message-Id: <200006080411.HAA17939@torni.hel.fi.ssh.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
From: Mika Kojo <mkojo@ssh.com>
To: Bodo Moeller <moeller@cdc.informatik.tu-darmstadt.de>
Cc: Mika Kojo <mkojo@ssh.com>, ietf-ssh@clinet.fi
Subject: Re: Diffie-Hellman Group Exchange
In-Reply-To: <20000607170746.A431@cdc.informatik.tu-darmstadt.de>
References: <20000606205204.3E2CD207C1@citi.umich.edu>
	<200006062307.CAA21153@torni.hel.fi.ssh.com>
	<20000607170746.A431@cdc.informatik.tu-darmstadt.de>
X-Mailer: VM 6.34 under Emacs 19.34.2
Organization: SSH Communications Security, Finland
Sender: owner-ietf-ssh@clinet.fi
Precedence: bulk
Content-Length: 2443
Lines: 58


Bodo,

The analysis you present is interesting, and problems with reusing
exponents should certainly be taken into account. 

At this opportunity I wish to give few comments;

 * The folk knowledge that g = 2 is best is not always correct. Even 
   g being small does not usually speed up exponentiation (and very 
   possibly it doesn't speed Diffie-Hellman at all, given some 
   black-box exponentiation routine). 

   I back this claim by the well-known speed-ups: Montgomery
   representation, and fixed base (e.g. Lim-Lee comb) precomputation. 
   (In Montgomery with e.g. R = 2^n, s.t. p < R, we might benefit from
   using g = (c/R (mod p)), with c small. With Lim-Lee comb method,
   for example, you precompute g^(a_i) where almost all a_i are 
   very large. Thus it is difficult to see how g small helps.)
 
   Further in Diffie-Hellman it is difficult to avoid general base 
   in the second exponentiation.

   On the otherhand, if g = 2 I could see that on memory poor 
   devices, for example, some benefit could be obtained. Some of the 
   better exponentiation algorithms tend to spend quite a lot of 
   memory. However, SSH2 is not directed to memory poor devices 
   (but this is my opinion and understanding only!) and thus I do not
   see much interest in special concern for selecting small g. 
 
 * Using a subgroup of composite order may be beneficial for some 
   purposes, but in theory---as far as I know---it seems that prime
   order subgroups are better.

   As primes of form p = 2cq + 1, with c large and q prime, are quite
   easily generated I think that allowing composite order subgroups is 
   not particularly important.

   However, even when selecting "small" prime order subgroups one 
   must take into account few security criteria. So it is not 
   entirely clear which approach is the best.

 * Let lg p ~= 1024, and lg ord(g) ~= 600 as Bodo suggest with 
   exponent e, s.t. lg e <= 160, then the theoretical problem that I 
   mentioned before is present. The problem is that g^e would not be
   completely random in the group <g>. However, if lg ord(g) ~= 
   lg e ~= 160 then g^e would look like a general element in <g>.

   I am not suggesting that there exists an efficient attack which 
   utilizes this. My point is just to show that using prime order 
   subgroups that are significantly smaller than p have some benefits.


Best regards,
Mika Kojo
SSH Communications Security Corp


From owner-ietf-ssh@clinet.fi  Thu Jun  8 13:08:32 2000
Return-Path: <owner-ietf-ssh@clinet.fi>
Received: from faui45.informatik.uni-erlangen.de (root@faui45.informatik.uni-erlangen.de [131.188.34.45])
	by faui01.informatik.uni-erlangen.de (8.8.8/8.1.16-FAU) with ESMTP id NAA04255
	for <msfriedl@cip.informatik.uni-erlangen.de>; Thu, 8 Jun 2000 13:08:31 +0200 (MET DST)
Received: from mail.clinet.fi (mail.clinet.fi [194.100.0.7])
	by faui45.informatik.uni-erlangen.de (8.9.1/8.1.49-FAU) with ESMTP id NAA03271
	for <Markus.Friedl@informatik.uni-erlangen.de>; Thu, 8 Jun 2000 13:08:25 +0200 (MET DST)
Received: (from majordom@localhost)
	by mail.clinet.fi (8.9.3/8.9.3) id MAA19753
	for ietf-ssh-outgoing; Thu, 8 Jun 2000 12:03:07 +0300
Received: from cdc-info.cdc.informatik.tu-darmstadt.de (cdc-info.cdc.informatik.tu-darmstadt.de [130.83.23.100])
	by mail.clinet.fi (8.9.3/8.9.3) with ESMTP id MAA19526
	for <ietf-ssh@clinet.fi>; Thu, 8 Jun 2000 12:02:03 +0300
Received: from cdc1.cdc.informatik.tu-darmstadt.de (cdc1 [130.83.23.10])
	by cdc-info.cdc.informatik.tu-darmstadt.de (Postfix) with ESMTP
	id B41122C4C; Thu,  8 Jun 2000 11:02:00 +0200 (MET DST)
Received: by cdc1.cdc.informatik.tu-darmstadt.de (8.8.8+Sun/SMI-SVR4)
	id LAA00881; Thu, 8 Jun 2000 11:02:00 +0200 (MET DST)
Date: Thu, 8 Jun 2000 11:01:59 +0200
From: Bodo Moeller <moeller@cdc.informatik.tu-darmstadt.de>
To: Mika Kojo <mkojo@ssh.com>
Cc: ietf-ssh@clinet.fi
Subject: Re: Diffie-Hellman Group Exchange
Message-ID: <20000608110158.B861@cdc.informatik.tu-darmstadt.de>
References: <20000606205204.3E2CD207C1@citi.umich.edu> <200006062307.CAA21153@torni.hel.fi.ssh.com> <20000607170746.A431@cdc.informatik.tu-darmstadt.de> <200006080411.HAA17939@torni.hel.fi.ssh.com>
Mime-Version: 1.0
Content-Type: text/plain; charset=us-ascii
X-Mailer: Mutt 1.0i
In-Reply-To: <200006080411.HAA17939@torni.hel.fi.ssh.com>; from mkojo@ssh.com on Thu, Jun 08, 2000 at 07:11:13AM +0300
Sender: owner-ietf-ssh@clinet.fi
Precedence: bulk
Content-Length: 2440
Lines: 51

On Thu, Jun 08, 2000 at 07:11:13AM +0300, Mika Kojo wrote:

> At this opportunity I wish to give few comments;
> 
>  * The folk knowledge that g = 2 is best is not always correct. Even 
>    g being small does not usually speed up exponentiation (and very 
>    possibly it doesn't speed Diffie-Hellman at all, given some 
>    black-box exponentiation routine). 
> 
>    I back this claim by the well-known speed-ups: Montgomery
>    representation, and fixed base (e.g. Lim-Lee comb) precomputation. 
>    (In Montgomery with e.g. R = 2^n, s.t. p < R, we might benefit from
>    using g = (c/R (mod p)), with c small.

I claimed so myself recently, but now I have made experiments and
found out that small generators help even when using Montgomery
multiplication (using a modified mod_exp routine that uses standard
modular multiplication for multiplying with small factors, but
Montgomery multiplication for squaring the accumulator.)
Thus it seems that using a small  g  can help even for optimized
implementations.


>  * Using a subgroup of composite order may be beneficial for some 
>    purposes, but in theory---as far as I know---it seems that prime
>    order subgroups are better.
> 
>    As primes of form p = 2cq + 1, with c large and q prime, are quite
>    easily generated I think that allowing composite order subgroups is 
>    not particularly important.

Do you mean they should be ruled out in the specification?  In some
senses, it makes things easier to allow them -- for example because
it means that you can use generator 2 when using  p = 2cq + 1
where  q  is nearly as large as  p  (such primes are easier to find
than safe primes which is why PGP uses them for its ElGamal encryption
keys),  or when  p  is a Lim-Lee prime (i.e.  p-1  is the product of a
couple of primes all of which are large).  So I think that such
flexibility should be allowed.


>    [....]         My point is just to show that using prime order 
>    subgroups that are significantly smaller than p have some benefits.

Yes.  The only problem with them is that the client does not know
everything about how the DH parameters have been chosen, so it in
general it cannot know whether using small exponents is safe.  That's
why I proposed including a recommended exponent length with the
parameters -- the server should know according to which criteria
they have been selected, and thus can know how small exponents
can be safely made.
From owner-ietf-ssh@clinet.fi  Thu Jun  8 15:17:07 2000
Return-Path: <owner-ietf-ssh@clinet.fi>
Received: from faui45.informatik.uni-erlangen.de (root@faui45.informatik.uni-erlangen.de [131.188.34.45])
	by faui01.informatik.uni-erlangen.de (8.8.8/8.1.16-FAU) with ESMTP id PAA12308
	for <msfriedl@cip.informatik.uni-erlangen.de>; Thu, 8 Jun 2000 15:17:07 +0200 (MET DST)
Received: from mail.clinet.fi (mail.clinet.fi [194.100.0.7])
	by faui45.informatik.uni-erlangen.de (8.9.1/8.1.49-FAU) with ESMTP id PAA14630
	for <Markus.Friedl@informatik.uni-erlangen.de>; Thu, 8 Jun 2000 15:17:05 +0200 (MET DST)
Received: (from majordom@localhost)
	by mail.clinet.fi (8.9.3/8.9.3) id NAA11988
	for ietf-ssh-outgoing; Thu, 8 Jun 2000 13:54:56 +0300
Received: from tukki.cc.jyu.fi (mjos@tukki.cc.jyu.fi [130.234.1.1])
	by mail.clinet.fi (8.9.3/8.9.3) with ESMTP id NAA11971
	for <ietf-ssh@clinet.fi>; Thu, 8 Jun 2000 13:54:54 +0300
Received: from localhost (mjos@localhost)
	by tukki.cc.jyu.fi (8.9.3/8.9.3/antispam3) with ESMTP id NAA19440
	for <ietf-ssh@clinet.fi>; Thu, 8 Jun 2000 13:54:53 +0300 (EET DST)
Date: Thu, 8 Jun 2000 13:54:53 +0300 (EET DST)
From: Markku-Juhani Saarinen <mjos@cc.jyu.fi>
X-Sender: mjos@tukki
To: ietf-ssh@clinet.fi
Subject: RE: Diffie-Hellman Group Exchange
Message-ID: <Pine.GSO.4.10.10006081339050.17924-100000@tukki>
MIME-Version: 1.0
Content-Type: TEXT/PLAIN; charset=ISO-8859-1
Content-Transfer-Encoding: 8BIT
Sender: owner-ietf-ssh@clinet.fi
Precedence: bulk
Content-Length: 1314
Lines: 39




Niels Provos wrote:

> "Diffie-Hellman Group Exchange for the SSH Transport Layer Protocol"
>
>is now available as
>
>  draft-provos-secsh-dh-group-exchange-00.txt
>
>Bodo and Markku could you please see if your concerns have been
>addressed.

Niels,

  The group generator advice is still (IMHO) the wrong way around; secret
  key bits are leaked. One can counter this by using longer exponents but
  this will result in a small performance cost.

  One section reads: "[generator 2] is usable even when it is not a
  primitive root, as it still covers half of the space of possible 
  residues". From a mathematical point of view this doesn't make much
  sense: if you use a primitive root as g, an attacker can get one bit of
  the secret exponent by computing L(x) = x^((p-1)/2) and then put the
  secret into the subgroup of size (p-1)/2 by simply squaring it. 
  The problem is thus reduced to computing a DL in the smaller subgroup.

  Also you might consider mentioning that actually smaller exponents
  (e.g. 256 bits) can be used to boost up performance. This would set
  the security level around 2^128 (assuming that a subgroup of prime
  order is used) and quadruple the performance with a 1024-bit prime.

Cheers,
- mj

Markku-Juhani O. Saarinen <mjos@jyu.fi>  University of Jyvskyl, Finland 


From owner-ietf-ssh@clinet.fi  Thu Jun  8 15:10:24 2000
Return-Path: <owner-ietf-ssh@clinet.fi>
Received: from faui45.informatik.uni-erlangen.de (root@faui45.informatik.uni-erlangen.de [131.188.34.45])
	by faui01.informatik.uni-erlangen.de (8.8.8/8.1.16-FAU) with ESMTP id PAA11848
	for <msfriedl@cip.informatik.uni-erlangen.de>; Thu, 8 Jun 2000 15:10:24 +0200 (MET DST)
Received: from mail.clinet.fi (mail.clinet.fi [194.100.0.7])
	by faui45.informatik.uni-erlangen.de (8.9.1/8.1.49-FAU) with ESMTP id PAA13900
	for <Markus.Friedl@informatik.uni-erlangen.de>; Thu, 8 Jun 2000 15:10:23 +0200 (MET DST)
Received: (from majordom@localhost)
	by mail.clinet.fi (8.9.3/8.9.3) id OAA13353
	for ietf-ssh-outgoing; Thu, 8 Jun 2000 14:01:09 +0300
Received: from tukki.cc.jyu.fi (mjos@tukki.cc.jyu.fi [130.234.1.1])
	by mail.clinet.fi (8.9.3/8.9.3) with ESMTP id OAA13342
	for <ietf-ssh@clinet.fi>; Thu, 8 Jun 2000 14:01:06 +0300
Received: from localhost (mjos@localhost)
	by tukki.cc.jyu.fi (8.9.3/8.9.3/antispam3) with ESMTP id OAA20054
	for <ietf-ssh@clinet.fi>; Thu, 8 Jun 2000 14:01:04 +0300 (EET DST)
Date: Thu, 8 Jun 2000 14:01:04 +0300 (EET DST)
From: Markku-Juhani Saarinen <mjos@cc.jyu.fi>
X-Sender: mjos@tukki
To: ietf-ssh@clinet.fi
Subject: RE: Diffie-Hellman Group Exchange
In-Reply-To: <Pine.GSO.4.10.10006081339050.17924-100000@tukki>
Message-ID: <Pine.GSO.4.10.10006081356560.17924-100000@tukki>
MIME-Version: 1.0
Content-Type: TEXT/PLAIN; charset=ISO-8859-1
Content-Transfer-Encoding: 8BIT
Sender: owner-ietf-ssh@clinet.fi
Precedence: bulk
Content-Length: 627
Lines: 17


I just wrote:

>   Also you might consider mentioning that actually smaller exponents
>   (e.g. 256 bits) can be used to boost up performance. This would set
>   the security level around 2^128 (assuming that a subgroup of prime
>   order is used) and quadruple the performance with a 1024-bit prime.

Actually 2^128 would be the complexity of the Lambda DL method, but
the prime size of 1024 bits limits the security to around 2^70 anyway,
regardless of the exponent size. A 2^128 security level would require
prime p to be around 4100 bits.

- mj

Markku-Juhani O. Saarinen <mjos@jyu.fi>  University of Jyvskyl, Finland 

From owner-ietf-ssh@clinet.fi  Thu Jun  8 15:39:01 2000
Return-Path: <owner-ietf-ssh@clinet.fi>
Received: from faui45.informatik.uni-erlangen.de (root@faui45.informatik.uni-erlangen.de [131.188.34.45])
	by faui01.informatik.uni-erlangen.de (8.8.8/8.1.16-FAU) with ESMTP id PAA14400
	for <msfriedl@cip.informatik.uni-erlangen.de>; Thu, 8 Jun 2000 15:39:00 +0200 (MET DST)
Received: from mail.clinet.fi (mail.clinet.fi [194.100.0.7])
	by faui45.informatik.uni-erlangen.de (8.9.1/8.1.49-FAU) with ESMTP id PAA16688
	for <Markus.Friedl@informatik.uni-erlangen.de>; Thu, 8 Jun 2000 15:38:56 +0200 (MET DST)
Received: (from majordom@localhost)
	by mail.clinet.fi (8.9.3/8.9.3) id OAA13462
	for ietf-ssh-outgoing; Thu, 8 Jun 2000 14:01:53 +0300
Received: from ssh.com (fw.hel.fi.ssh.com [193.64.193.124])
	by mail.clinet.fi (8.9.3/8.9.3) with ESMTP id OAA13420
	for <ietf-ssh@clinet.fi>; Thu, 8 Jun 2000 14:01:41 +0300
Received: from torni.hel.fi.ssh.com (torni.hel.fi.ssh.com [10.1.0.43])
	by ssh.com (8.9.3/8.9.3/SSH-1.16) with ESMTP id OAA27060;
	Thu, 8 Jun 2000 14:01:41 +0300 (EEST)
Received: (from mkojo@localhost)
	by torni.hel.fi.ssh.com (8.9.3/8.9.3/SSH-1.17) id OAA15283;
	Thu, 8 Jun 2000 14:01:41 +0300 (EET DST)
Date: Thu, 8 Jun 2000 14:01:41 +0300 (EET DST)
Message-Id: <200006081101.OAA15283@torni.hel.fi.ssh.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
From: Mika Kojo <mkojo@ssh.com>
To: Bodo Moeller <moeller@cdc.informatik.tu-darmstadt.de>
Cc: Mika Kojo <mkojo@ssh.com>, ietf-ssh@clinet.fi
Subject: Re: Diffie-Hellman Group Exchange
In-Reply-To: <20000608110158.B861@cdc.informatik.tu-darmstadt.de>
References: <20000606205204.3E2CD207C1@citi.umich.edu>
	<200006062307.CAA21153@torni.hel.fi.ssh.com>
	<20000607170746.A431@cdc.informatik.tu-darmstadt.de>
	<200006080411.HAA17939@torni.hel.fi.ssh.com>
	<20000608110158.B861@cdc.informatik.tu-darmstadt.de>
X-Mailer: VM 6.34 under Emacs 19.34.2
Organization: SSH Communications Security, Finland
Sender: owner-ietf-ssh@clinet.fi
Precedence: bulk
Content-Length: 4214
Lines: 92


Bodo Moeller writes:
> On Thu, Jun 08, 2000 at 07:11:13AM +0300, Mika Kojo wrote:
> 
> > At this opportunity I wish to give few comments;
> > 
> >  * The folk knowledge that g = 2 is best is not always correct. Even 
> >    g being small does not usually speed up exponentiation (and very 
> >    possibly it doesn't speed Diffie-Hellman at all, given some 
> >    black-box exponentiation routine). 
> > 
> >    I back this claim by the well-known speed-ups: Montgomery
> >    representation, and fixed base (e.g. Lim-Lee comb) precomputation. 
> >    (In Montgomery with e.g. R = 2^n, s.t. p < R, we might benefit from
> >    using g = (c/R (mod p)), with c small.
> 
> I claimed so myself recently, but now I have made experiments and
> found out that small generators help even when using Montgomery
> multiplication (using a modified mod_exp routine that uses standard
> modular multiplication for multiplying with small factors, but
> Montgomery multiplication for squaring the accumulator.)
> Thus it seems that using a small  g  can help even for optimized
> implementations.

My apologies for repeating. And yes, benefits of g = 2 appear also in
Montgomery representation. However, they are not as great if you have
some binary window variant. There multiplying by 2^i, where i \n { 1,
3, ..., 2^k-1 }, can be efficient, but then you'll need also a
division routine. Though, I can see that this still could yield good
performance.

But as mentioned if we assume Montgomery exponentiation routine, then
setting g == 2/(2^n) (mod p), say, should give equal (or greater)
speed.

(Further speed up can be still obtained by suitable selection of the
prime number. For example, setting the highest bits to ones gives
faster division routine. Also using very low hamming weight primes may
give speed-ups, e.g. generalized Mersenne primes.)

In Diffie-Hellman it is very effective to use fixed base
precomputation ideas. Most of these require using exponents, in the
precomputation, larger than lg ord(g), so the structure of g is lost.


> >  * Using a subgroup of composite order may be beneficial for some 
> >    purposes, but in theory---as far as I know---it seems that prime
> >    order subgroups are better.
> > 
> >    As primes of form p = 2cq + 1, with c large and q prime, are quite
> >    easily generated I think that allowing composite order subgroups is 
> >    not particularly important.
> 
> Do you mean they should be ruled out in the specification?  In some
> senses, it makes things easier to allow them -- for example because
> it means that you can use generator 2 when using  p = 2cq + 1
> where  q  is nearly as large as  p  (such primes are easier to find
> than safe primes which is why PGP uses them for its ElGamal encryption
> keys),  or when  p  is a Lim-Lee prime (i.e.  p-1  is the product of a
> couple of primes all of which are large).  So I think that such
> flexibility should be allowed.

At the moment I do not see really good reasons why composite group
orders should be allowed. However, this is just that I have not yet
understood why g = 2 would make life so much easier---but perhaps I
will eventually.

Wouldn't Lim-Lee primes be almost impossible to verify by anyone? That
is, checking that g actually belongs to some large enough subgroup is
a bit difficult. (Of course, in the protocol suggested this might not
be of importance.)


> >    [....]         My point is just to show that using prime order 
> >    subgroups that are significantly smaller than p have some benefits.
> 
> Yes.  The only problem with them is that the client does not know
> everything about how the DH parameters have been chosen, so it in
> general it cannot know whether using small exponents is safe. That's
> why I proposed including a recommended exponent length with the
> parameters -- the server should know according to which criteria
> they have been selected, and thus can know how small exponents
> can be safely made.

Why cannot the client just compute the exponent length itself, it should
know p,g and ord(g)? A conservative choice is to select exponent size
to be approximately equal to the subgroup size. 


Best regards, 
Mika Kojo
SSH Communications Security Corp
From owner-ietf-ssh@clinet.fi  Thu Jun  8 15:58:10 2000
Return-Path: <owner-ietf-ssh@clinet.fi>
Received: from faui45.informatik.uni-erlangen.de (root@faui45.informatik.uni-erlangen.de [131.188.34.45])
	by faui01.informatik.uni-erlangen.de (8.8.8/8.1.16-FAU) with ESMTP id PAA15563
	for <msfriedl@cip.informatik.uni-erlangen.de>; Thu, 8 Jun 2000 15:58:09 +0200 (MET DST)
Received: from mail.clinet.fi (mail.clinet.fi [194.100.0.7])
	by faui45.informatik.uni-erlangen.de (8.9.1/8.1.49-FAU) with ESMTP id PAA18432
	for <Markus.Friedl@informatik.uni-erlangen.de>; Thu, 8 Jun 2000 15:58:05 +0200 (MET DST)
Received: (from majordom@localhost)
	by mail.clinet.fi (8.9.3/8.9.3) id OAA22039
	for ietf-ssh-outgoing; Thu, 8 Jun 2000 14:40:15 +0300
Received: from samantha.lysator.liu.se (root@samantha.lysator.liu.se [130.236.254.202])
	by mail.clinet.fi (8.9.3/8.9.3) with ESMTP id OAA18463;
	Thu, 8 Jun 2000 14:24:26 +0300
Received: from sture.lysator.liu.se (nisse@sture.lysator.liu.se [130.236.254.21])
	by samantha.lysator.liu.se (8.9.3/8.9.3) with ESMTP id NAA28524;
	Thu, 8 Jun 2000 13:23:37 +0200 (MET DST)
Received: (from nisse@localhost)
	by sture.lysator.liu.se (8.9.0/8.8.7) id NAA14333;
	Thu, 8 Jun 2000 13:23:32 +0200 (MET DST)
To: "Noel L Yap" <yap_noel@jpmorgan.com>
Cc: Ietf-Ssh@clinet.fi, Psst@Net.Lut.Ac.Uk, ssh@clinet.fi
Subject: Re: Using SRP as a key exchange metod in Secure Shell
References: <852568F7.0053F5EC.00@nyc-ntgw-n01.ny.jpmorgan.com>
From: nisse@lysator.liu.se (Niels Mller)
Date: 08 Jun 2000 13:23:32 +0200
In-Reply-To: "Noel L Yap"'s message of "Wed, 7 Jun 2000 11:17:02 -0400"
Message-ID: <nnwvk0xvpn.fsf@sture.lysator.liu.se>
X-Mailer: Gnus v5.7/Emacs 20.5
Sender: owner-ietf-ssh@clinet.fi
Precedence: bulk
Content-Length: 1165
Lines: 29

"Noel L Yap" <yap_noel@jpmorgan.com> writes:

> OK, I've read this, but since I'm a bit of a newbie, I have a couple of
> questions:
> 1. Can the SRP authentication be used to authenticate the client to the host
> without the use of assymetric keys?  I understand that this may not be as secure
> (since passwords generally have less entropy than keys), but in some situations,
> the convenience is worth the risk.

Yes.

One way to look at SRP is to view it like a assymetric system where
the user's private key is derived from a password. But the
host-authentication part of it really uses the verifier as a shared
(symmetric) secret.

> 2. What effects would such a change have on ssh-agent and ssh-add?

You would either have to type the SRP password each time, or tell the
agent about it. Or just get the hostkey and use the traditional host-
and userauthentication mechanisms in ssh.

Note that LSH doesn't (yet) have anything like ssh-agent or ssh-add.
I'm expecting the gateway feature (once that is implemented) to be
able to replace aah-agent in many cases. See
http://www.lysator.liu.se/~nisse/lsh/doc/gateway-mode.txt for some
ideas about that.

/Niels
From owner-ietf-ssh@clinet.fi  Mon Jun 12 19:43:42 2000
Return-Path: <owner-ietf-ssh@clinet.fi>
Received: from faui45.informatik.uni-erlangen.de (root@faui45.informatik.uni-erlangen.de [131.188.34.45])
	by faui01.informatik.uni-erlangen.de (8.8.8/8.1.16-FAU) with ESMTP id TAA03973
	for <msfriedl@cip.informatik.uni-erlangen.de>; Mon, 12 Jun 2000 19:43:42 +0200 (MET DST)
Received: from mail.clinet.fi (mail.clinet.fi [194.100.0.7])
	by faui45.informatik.uni-erlangen.de (8.9.1/8.1.49-FAU) with ESMTP id TAA20978
	for <Markus.Friedl@informatik.uni-erlangen.de>; Mon, 12 Jun 2000 19:43:41 +0200 (MET DST)
Received: (from majordom@localhost)
	by mail.clinet.fi (8.9.3/8.9.3) id SAA26087
	for ietf-ssh-outgoing; Mon, 12 Jun 2000 18:47:07 +0300
Received: from cdc-info.cdc.informatik.tu-darmstadt.de (cdc-info.cdc.informatik.tu-darmstadt.de [130.83.23.100])
	by mail.clinet.fi (8.9.3/8.9.3) with ESMTP id OAA22713
	for <ietf-ssh@clinet.fi>; Thu, 8 Jun 2000 14:43:51 +0300
Received: from cdc1.cdc.informatik.tu-darmstadt.de (cdc1 [130.83.23.10])
	by cdc-info.cdc.informatik.tu-darmstadt.de (Postfix) with ESMTP
	id 1D8882C4C; Thu,  8 Jun 2000 13:43:50 +0200 (MET DST)
Received: by cdc1.cdc.informatik.tu-darmstadt.de (8.8.8+Sun/SMI-SVR4)
	id NAA00559; Thu, 8 Jun 2000 13:43:49 +0200 (MET DST)
Date: Thu, 8 Jun 2000 13:43:48 +0200
From: Bodo Moeller <moeller@cdc.informatik.tu-darmstadt.de>
To: Mika Kojo <mkojo@ssh.com>
Cc: ietf-ssh@clinet.fi
Subject: Re: Diffie-Hellman Group Exchange
Message-ID: <20000608134347.A544@cdc.informatik.tu-darmstadt.de>
References: <20000606205204.3E2CD207C1@citi.umich.edu> <200006062307.CAA21153@torni.hel.fi.ssh.com> <20000607170746.A431@cdc.informatik.tu-darmstadt.de> <200006080411.HAA17939@torni.hel.fi.ssh.com> <20000608110158.B861@cdc.informatik.tu-darmstadt.de> <200006081101.OAA15283@torni.hel.fi.ssh.com>
Mime-Version: 1.0
Content-Type: text/plain; charset=iso-8859-1
Content-Transfer-Encoding: 8bit
X-Mailer: Mutt 1.0i
In-Reply-To: <200006081101.OAA15283@torni.hel.fi.ssh.com>; from mkojo@ssh.com on Thu, Jun 08, 2000 at 02:01:41PM +0300
Sender: owner-ietf-ssh@clinet.fi
Precedence: bulk
Content-Length: 3276
Lines: 72

On Thu, Jun 08, 2000 at 02:01:41PM +0300, Mika Kojo wrote:

>                             And yes, benefits of g = 2 appear also in
> Montgomery representation. However, they are not as great if you have
> some binary window variant. There multiplying by 2^i, where i \n { 1,
> 3, ..., 2^k-1 }, can be efficient, but then you'll need also a
> division routine. Though, I can see that this still could yield good
> performance.
>
> But as mentioned if we assume Montgomery exponentiation routine, then
> setting g == 2/(2^n) (mod p), say, should give equal (or greater)
> speed.

Maybe I just made a mistake when trying to determine the performance
when  g  is chosen such that it becomes  2  when converted to
Montgomery representation; speed gain was negligible.  With  g = 2
and a special Montgomery modexp variant for small bases (which
requires a division routine), I was able to obtain an about 20 %
speed-up.


> In Diffie-Hellman it is very effective to use fixed base
> precomputation ideas. Most of these require using exponents, in the
> precomputation, larger than lg ord(g), so the structure of g is lost.

Yes, but this can be used only when the same parameters are used
many times.  Servers can easily make use of it, but for SSH clients,
a small  g  can be more convenient.  (Also if the server wants to
optimize  g  for Montgomery, it cannot really know if the client
actually uses Montgomery multiplication, and in case it does, if it
uses the same variant of Montgomery multiplication.)


[...]
> Wouldn't Lim-Lee primes be almost impossible to verify by anyone? That
> is, checking that g actually belongs to some large enough subgroup is
> a bit difficult. (Of course, in the protocol suggested this might not
> be of importance.)

You can't verify them, but in this protocol verification is not
important.


>>>    [....]         My point is just to show that using prime order 
>>>    subgroups that are significantly smaller than p have some benefits.

>> Yes.  The only problem with them is that the client does not know
>> everything about how the DH parameters have been chosen, so it in
>> general it cannot know whether using small exponents is safe. That's
>> why I proposed including a recommended exponent length with the
>> parameters -- the server should know according to which criteria
>> they have been selected, and thus can know how small exponents
>> can be safely made.

> Why cannot the client just compute the exponent length itself, it should
> know p,g and ord(g)? A conservative choice is to select exponent size
> to be approximately equal to the subgroup size. 

If the protocol defines that only prime order subgroups may be used
(and if everone follows the specification), then there's no problem.
But if other subgroups are allowed, then problems can arise if the
client decides to optimize by choosing the exponent smaller than
ord(g).  If DH parameters include a (minimum) exponent length
in addition to or instead of  ord(g),  then such problems are avoided.


-- 
Bodo Mller <moeller@cdc.informatik.tu-darmstadt.de>
PGP http://www.informatik.tu-darmstadt.de/TI/Mitarbeiter/moeller/0x36d2c658.html
* TU Darmstadt, Theoretische Informatik, Alexanderstr. 10, D-64283 Darmstadt
* Tel. +49-6151-16-6628, Fax +49-6151-16-6036

From owner-ietf-ssh@clinet.fi  Thu Jun  8 17:14:52 2000
Return-Path: <owner-ietf-ssh@clinet.fi>
Received: from faui45.informatik.uni-erlangen.de (root@faui45.informatik.uni-erlangen.de [131.188.34.45])
	by faui01.informatik.uni-erlangen.de (8.8.8/8.1.16-FAU) with ESMTP id RAA21287
	for <msfriedl@cip.informatik.uni-erlangen.de>; Thu, 8 Jun 2000 17:14:51 +0200 (MET DST)
Received: from mail.clinet.fi (mail.clinet.fi [194.100.0.7])
	by faui45.informatik.uni-erlangen.de (8.9.1/8.1.49-FAU) with ESMTP id RAA26459
	for <Markus.Friedl@informatik.uni-erlangen.de>; Thu, 8 Jun 2000 17:14:49 +0200 (MET DST)
Received: (from majordom@localhost)
	by mail.clinet.fi (8.9.3/8.9.3) id PAA01743
	for ietf-ssh-outgoing; Thu, 8 Jun 2000 15:31:09 +0300
Received: from ssh.com (fw.hel.fi.ssh.com [193.64.193.124])
	by mail.clinet.fi (8.9.3/8.9.3) with ESMTP id PAA01691
	for <ietf-ssh@clinet.fi>; Thu, 8 Jun 2000 15:30:59 +0300
Received: from torni.hel.fi.ssh.com (torni.hel.fi.ssh.com [10.1.0.43])
	by ssh.com (8.9.3/8.9.3/SSH-1.16) with ESMTP id PAA04065;
	Thu, 8 Jun 2000 15:30:57 +0300 (EEST)
Received: (from mkojo@localhost)
	by torni.hel.fi.ssh.com (8.9.3/8.9.3/SSH-1.17) id PAA01781;
	Thu, 8 Jun 2000 15:30:56 +0300 (EET DST)
Date: Thu, 8 Jun 2000 15:30:56 +0300 (EET DST)
Message-Id: <200006081230.PAA01781@torni.hel.fi.ssh.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
From: Mika Kojo <mkojo@ssh.com>
To: Bodo Moeller <moeller@cdc.informatik.tu-darmstadt.de>
Cc: Mika Kojo <mkojo@ssh.com>, ietf-ssh@clinet.fi
Subject: Re: Diffie-Hellman Group Exchange
In-Reply-To: <20000608134347.A544@cdc.informatik.tu-darmstadt.de>
References: <20000606205204.3E2CD207C1@citi.umich.edu>
	<200006062307.CAA21153@torni.hel.fi.ssh.com>
	<20000607170746.A431@cdc.informatik.tu-darmstadt.de>
	<200006080411.HAA17939@torni.hel.fi.ssh.com>
	<20000608110158.B861@cdc.informatik.tu-darmstadt.de>
	<200006081101.OAA15283@torni.hel.fi.ssh.com>
	<20000608134347.A544@cdc.informatik.tu-darmstadt.de>
X-Mailer: VM 6.34 under Emacs 19.34.2
Organization: SSH Communications Security, Finland
Sender: owner-ietf-ssh@clinet.fi
Precedence: bulk
Content-Length: 1181
Lines: 30


Bodo Moeller writes:

[snip]
> Maybe I just made a mistake when trying to determine the performance
> when  g  is chosen such that it becomes  2  when converted to
> Montgomery representation; speed gain was negligible.  With  g = 2
> and a special Montgomery modexp variant for small bases (which
> requires a division routine), I was able to obtain an about 20 %
> speed-up.

Experiments speak for themselves, although being a bit surprising :)
It would be interesting for me to know more about your timings, but it
is probably not a topic for this list.

[snip]
> If the protocol defines that only prime order subgroups may be used
> (and if everone follows the specification), then there's no problem.
> But if other subgroups are allowed, then problems can arise if the
> client decides to optimize by choosing the exponent smaller than
> ord(g).  If DH parameters include a (minimum) exponent length
> in addition to or instead of  ord(g),  then such problems are avoided.

I see the problem. Yet I think it is one reason more for using prime
subgroups. Not that one length field would cause much concern, though.


Best regards, 
Mika Kojo
SSH Communications Security Corp
From owner-ietf-ssh@clinet.fi  Thu Jun  8 17:19:00 2000
Return-Path: <owner-ietf-ssh@clinet.fi>
Received: from faui45.informatik.uni-erlangen.de (root@faui45.informatik.uni-erlangen.de [131.188.34.45])
	by faui01.informatik.uni-erlangen.de (8.8.8/8.1.16-FAU) with ESMTP id RAA21415
	for <msfriedl@cip.informatik.uni-erlangen.de>; Thu, 8 Jun 2000 17:18:59 +0200 (MET DST)
Received: from mail.clinet.fi (mail.clinet.fi [194.100.0.7])
	by faui45.informatik.uni-erlangen.de (8.9.1/8.1.49-FAU) with ESMTP id RAA26836
	for <Markus.Friedl@informatik.uni-erlangen.de>; Thu, 8 Jun 2000 17:18:54 +0200 (MET DST)
Received: (from majordom@localhost)
	by mail.clinet.fi (8.9.3/8.9.3) id PAA05166
	for ietf-ssh-outgoing; Thu, 8 Jun 2000 15:45:56 +0300
Received: from cdc-info.cdc.informatik.tu-darmstadt.de (cdc-info.cdc.informatik.tu-darmstadt.de [130.83.23.100])
	by mail.clinet.fi (8.9.3/8.9.3) with ESMTP id PAA05050
	for <ietf-ssh@clinet.fi>; Thu, 8 Jun 2000 15:45:33 +0300
Received: from cdc1.cdc.informatik.tu-darmstadt.de (cdc1 [130.83.23.10])
	by cdc-info.cdc.informatik.tu-darmstadt.de (Postfix) with ESMTP
	id 4ABAF2C4C; Thu,  8 Jun 2000 14:45:26 +0200 (MET DST)
Received: by cdc1.cdc.informatik.tu-darmstadt.de (8.8.8+Sun/SMI-SVR4)
	id OAA00652; Thu, 8 Jun 2000 14:45:25 +0200 (MET DST)
Date: Thu, 8 Jun 2000 14:45:23 +0200
From: Bodo Moeller <moeller@cdc.informatik.tu-darmstadt.de>
To: Mika Kojo <mkojo@ssh.com>
Cc: ietf-ssh@clinet.fi
Subject: Re: Diffie-Hellman Group Exchange
Message-ID: <20000608144523.A642@cdc.informatik.tu-darmstadt.de>
References: <20000606205204.3E2CD207C1@citi.umich.edu> <200006062307.CAA21153@torni.hel.fi.ssh.com> <20000607170746.A431@cdc.informatik.tu-darmstadt.de> <200006080411.HAA17939@torni.hel.fi.ssh.com> <20000608110158.B861@cdc.informatik.tu-darmstadt.de> <200006081101.OAA15283@torni.hel.fi.ssh.com> <20000608134347.A544@cdc.informatik.tu-darmstadt.de> <200006081230.PAA01781@torni.hel.fi.ssh.com>
Mime-Version: 1.0
Content-Type: text/plain; charset=us-ascii
X-Mailer: Mutt 1.0i
In-Reply-To: <200006081230.PAA01781@torni.hel.fi.ssh.com>; from mkojo@ssh.com on Thu, Jun 08, 2000 at 03:30:56PM +0300
Sender: owner-ietf-ssh@clinet.fi
Precedence: bulk
Content-Length: 1229
Lines: 21

On Thu, Jun 08, 2000 at 03:30:56PM +0300, Mika Kojo wrote:

>> If the protocol defines that only prime order subgroups may be used
>> (and if everone follows the specification), then there's no problem.
>> But if other subgroups are allowed, then problems can arise if the
>> client decides to optimize by choosing the exponent smaller than
>> ord(g).  If DH parameters include a (minimum) exponent length
>> in addition to or instead of  ord(g),  then such problems are avoided.

> I see the problem. Yet I think it is one reason more for using prime
> subgroups. Not that one length field would cause much concern, though.

If the length field is not included, then it is a reason for using
prime order subgroups (and not only for using them in specific cases,
but for specifying that they *must* be used) -- however, such a
solution without length field would not be fool-proof: If someone for
efficiency reason violates the specification that the subgroup order
must be prime, then the assumption that exponents of a certain length
are safe may no longer be true.  Thus it's safer to include a recommended
exponent length, and if this is done, there's no longer a compelling
reason to always insist on prime-order subgroups.
From owner-ietf-ssh@clinet.fi  Thu Jun  8 17:43:08 2000
Return-Path: <owner-ietf-ssh@clinet.fi>
Received: from faui45.informatik.uni-erlangen.de (root@faui45.informatik.uni-erlangen.de [131.188.34.45])
	by faui01.informatik.uni-erlangen.de (8.8.8/8.1.16-FAU) with ESMTP id RAA22319
	for <msfriedl@cip.informatik.uni-erlangen.de>; Thu, 8 Jun 2000 17:43:07 +0200 (MET DST)
Received: from mail.clinet.fi (mail.clinet.fi [194.100.0.7])
	by faui45.informatik.uni-erlangen.de (8.9.1/8.1.49-FAU) with ESMTP id RAA29272
	for <Markus.Friedl@informatik.uni-erlangen.de>; Thu, 8 Jun 2000 17:43:03 +0200 (MET DST)
Received: (from majordom@localhost)
	by mail.clinet.fi (8.9.3/8.9.3) id PAA07537
	for ietf-ssh-outgoing; Thu, 8 Jun 2000 15:56:23 +0300
Received: from jpmorgan.com (threshold3.jpmorgan.com [169.71.1.12])
	by mail.clinet.fi (8.9.3/8.9.3) with ESMTP id PAA05352;
	Thu, 8 Jun 2000 15:46:49 +0300
Received: (from uucp@localhost)
	by jpmorgan.com (8.8.5/8.8.5) id IAA16397;
	Thu, 8 Jun 2000 08:46:39 -0400 (EDT)
Received: from jpmmailhost4.ny.jpmorgan.com(198.75.231.102) by threshold3.jpmorgan.com via smap (V4.2)
	id xma016287; Thu, 8 Jun 00 08:46:29 -0400
Received: from nyc-ntgw-n01.ny.jpmorgan.com (nyc_smtpmta_02.ny.jpmorgan.com [146.149.150.22])
	by jpmmailhost4.ny.jpmorgan.com (8.9.1a/8.9.1) with SMTP id IAA17174;
	Thu, 8 Jun 2000 08:46:26 -0400 (EDT)
Received: by nyc-ntgw-n01.ny.jpmorgan.com(Lotus SMTP MTA v4.6.4  (830.2 3-23-1999))  id 852568F8.00462A99 ; Thu, 8 Jun 2000 08:46:23 -0400
X-Lotus-FromDomain: JPMORGAN@SMTP
From: "Noel L Yap" <yap_noel@jpmorgan.com>
To: nisse@lysator.liu.se
cc: Ietf-Ssh@clinet.fi, Psst@Net.Lut.Ac.Uk, Ssh@clinet.fi
Message-ID: <852568F8.00462942.00@nyc-ntgw-n01.ny.jpmorgan.com>
Date: Thu, 8 Jun 2000 08:46:20 -0400
Subject: Re: Using SRP as a key exchange metod in Secure Shell
Mime-Version: 1.0
Content-type: text/plain; charset=us-ascii
Content-Disposition: inline
Sender: owner-ietf-ssh@clinet.fi
Precedence: bulk
Content-Length: 2118
Lines: 55





nisse@lysator.liu.se on 06/08/2000 07:23:32 AM
>"Noel L Yap" <yap_noel@jpmorgan.com> writes:
>
>> OK, I've read this, but since I'm a bit of a newbie, I have a couple of
>> questions:
>> 1. Can the SRP authentication be used to authenticate the client to the host
>> without the use of assymetric keys?  I understand that this may not be as
secure
>> (since passwords generally have less entropy than keys), but in some
situations,
>> the convenience is worth the risk.
>
>Yes.
>
>One way to look at SRP is to view it like a assymetric system where
>the user's private key is derived from a password. But the
>host-authentication part of it really uses the verifier as a shared
>(symmetric) secret.
>
>> 2. What effects would such a change have on ssh-agent and ssh-add?
>
>You would either have to type the SRP password each time, or tell the
>agent about it. Or just get the hostkey and use the traditional host-
>and userauthentication mechanisms in ssh.
>
>Note that LSH doesn't (yet) have anything like ssh-agent or ssh-add.
>I'm expecting the gateway feature (once that is implemented) to be
>able to replace aah-agent in many cases. See
>http://www.lysator.liu.se/~nisse/lsh/doc/gateway-mode.txt for some
>ideas about that.

This is great!  I prefer using SSH to secure CVS, but I don't really like the
key management issue (since I really have to trust the clients not to put the
keys in a safe place (and, sometimes, unsafe places aren't so obviously unsafe);
I would much rather trust them keeping their passphrases secret).

Now, what's the expected time frame or turn-around time for such a project?

Thanks,
Noel



This communication is for informational purposes only.  It is not intended as
an offer or solicitation for the purchase or sale of any financial instrument
or as an official confirmation of any transaction. All market prices, data
and other information are not warranted as to completeness or accuracy and
are subject to change without notice. Any comments or statements made herein
do not necessarily reflect those of J.P. Morgan & Co. Incorporated, its
subsidiaries and affiliates.

From owner-ietf-ssh@clinet.fi  Sat Jun 10 03:57:32 2000
Return-Path: <owner-ietf-ssh@clinet.fi>
Received: from faui45.informatik.uni-erlangen.de (root@faui45.informatik.uni-erlangen.de [131.188.34.45])
	by faui01.informatik.uni-erlangen.de (8.8.8/8.1.16-FAU) with ESMTP id DAA23821
	for <msfriedl@cip.informatik.uni-erlangen.de>; Sat, 10 Jun 2000 03:57:32 +0200 (MET DST)
Received: from mail.clinet.fi (mail.clinet.fi [194.100.0.7])
	by faui45.informatik.uni-erlangen.de (8.9.1/8.1.49-FAU) with ESMTP id DAA11962
	for <Markus.Friedl@informatik.uni-erlangen.de>; Sat, 10 Jun 2000 03:57:31 +0200 (MET DST)
Received: (from majordom@localhost)
	by mail.clinet.fi (8.9.3/8.9.3) id DAA27912
	for ietf-ssh-outgoing; Sat, 10 Jun 2000 03:04:05 +0300
Received: from syrinx.oankali.net (syrinx.oankali.net [206.243.169.50])
	by mail.clinet.fi (8.9.3/8.9.3) with ESMTP id DAA27909
	for <ietf-ssh@clinet.fi>; Sat, 10 Jun 2000 03:04:04 +0300
Received: (from res@localhost)
	by syrinx.oankali.net (8.9.3/8.9.3) id UAA09375;
	Fri, 9 Jun 2000 20:01:30 -0400
Date: Fri, 9 Jun 2000 20:01:30 -0400
Message-Id: <200006100001.UAA09375@syrinx.oankali.net>
From: "Richard E. Silverman" <slade@shore.net>
To: ietf-ssh@clinet.fi
Subject: KEXINIT "cookie" (SSH-TRANS)
Sender: owner-ietf-ssh@clinet.fi
Precedence: bulk
Content-Length: 651
Lines: 19


In the SSH-TRANS document, the format of a KEXINIT message includes a
16-byte random cookie, about which is said:

      The cookie MUST be a random value generated by the sender.  Its
      purpose is to make it impossible for either side to fully
      determine the keys and the session identifier.

After this, though, I can't find any mention of the cookie at all, so it
appears not to be used.  Can anyone comment on this?

Also, this is my first message on this list.  If there is a list archive
available, or a collection of protocol analyses and comments, I'd be
happy to be directed to them.

Thanks,

- Richard Silverman
  slade@shore.net
From owner-ietf-ssh@clinet.fi  Sat Jun 10 13:06:35 2000
Return-Path: <owner-ietf-ssh@clinet.fi>
Received: from faui45.informatik.uni-erlangen.de (root@faui45.informatik.uni-erlangen.de [131.188.34.45])
	by faui01.informatik.uni-erlangen.de (8.8.8/8.1.16-FAU) with ESMTP id NAA12161
	for <msfriedl@cip.informatik.uni-erlangen.de>; Sat, 10 Jun 2000 13:06:34 +0200 (MET DST)
Received: from mail.clinet.fi (mail.clinet.fi [194.100.0.7])
	by faui45.informatik.uni-erlangen.de (8.9.1/8.1.49-FAU) with ESMTP id NAA00316
	for <Markus.Friedl@informatik.uni-erlangen.de>; Sat, 10 Jun 2000 13:06:33 +0200 (MET DST)
Received: (from majordom@localhost)
	by mail.clinet.fi (8.9.3/8.9.3) id MAA30142
	for ietf-ssh-outgoing; Sat, 10 Jun 2000 12:14:10 +0300
Received: from samantha.lysator.liu.se (root@samantha.lysator.liu.se [130.236.254.202])
	by mail.clinet.fi (8.9.3/8.9.3) with ESMTP id MAA30139
	for <ietf-ssh@clinet.fi>; Sat, 10 Jun 2000 12:14:09 +0300
Received: from sture.lysator.liu.se (nisse@sture.lysator.liu.se [130.236.254.21])
	by samantha.lysator.liu.se (8.9.3/8.9.3) with ESMTP id LAA18307;
	Sat, 10 Jun 2000 11:13:31 +0200 (MET DST)
Received: (from nisse@localhost)
	by sture.lysator.liu.se (8.9.0/8.8.7) id LAA04569;
	Sat, 10 Jun 2000 11:13:27 +0200 (MET DST)
To: "Richard E. Silverman" <slade@shore.net>
Cc: ietf-ssh@clinet.fi
Subject: Re: KEXINIT "cookie" (SSH-TRANS)
References: <200006100001.UAA09375@syrinx.oankali.net>
From: nisse@lysator.liu.se (Niels Mller)
Date: 10 Jun 2000 11:13:27 +0200
In-Reply-To: "Richard E. Silverman"'s message of "Fri, 9 Jun 2000 20:01:30 -0400"
Message-ID: <nnya4dx5jc.fsf@sture.lysator.liu.se>
X-Mailer: Gnus v5.7/Emacs 20.5
Sender: owner-ietf-ssh@clinet.fi
Precedence: bulk
Content-Length: 1446
Lines: 35

"Richard E. Silverman" <slade@shore.net> writes:

> In the SSH-TRANS document, the format of a KEXINIT message includes a
> 16-byte random cookie, about which is said:
> 
>       The cookie MUST be a random value generated by the sender.  Its
>       purpose is to make it impossible for either side to fully
>       determine the keys and the session identifier.
> 
> After this, though, I can't find any mention of the cookie at all, so it
> appears not to be used.  Can anyone comment on this?

It's included in the exchange hash, as part of "I_C" and "I_S":

: The hash H is computed as the HASH hash of the concatenation of the
: following:
: 
:   string    V_C, the client's version string (CR and NL excluded)
:   string    V_S, the server's version string (CR and NL excluded)
:   string    I_C, the payload of the client's SSH_MSG_KEXINIT
:   string    I_S, the payload of the server's SSH_MSG_KEXINIT
:   string    K_S, the host key
:   mpint     e, exchange value sent by the client
:   mpint     f, exchange value sent by the server
:   mpint     K, the shared secret

So both host and user authentication depends on the random cookies.

Perhaps they are not terribly important for the dh-keyexchange method,
but for keyexchange methods where one of the parties doesn't
contribute any random values (like in the RSA-based methods used in
SSL and (I think) ssh-1), the cookies are needed to make replay
attacks more difficult.

/Niels
From owner-ietf-ssh@clinet.fi  Sat Jun 10 16:13:15 2000
Return-Path: <owner-ietf-ssh@clinet.fi>
Received: from faui45.informatik.uni-erlangen.de (root@faui45.informatik.uni-erlangen.de [131.188.34.45])
	by faui01.informatik.uni-erlangen.de (8.8.8/8.1.16-FAU) with ESMTP id QAA20254
	for <msfriedl@cip.informatik.uni-erlangen.de>; Sat, 10 Jun 2000 16:13:14 +0200 (MET DST)
Received: from mail.clinet.fi (mail.clinet.fi [194.100.0.7])
	by faui45.informatik.uni-erlangen.de (8.9.1/8.1.49-FAU) with ESMTP id QAA06531
	for <Markus.Friedl@informatik.uni-erlangen.de>; Sat, 10 Jun 2000 16:13:13 +0200 (MET DST)
Received: (from majordom@localhost)
	by mail.clinet.fi (8.9.3/8.9.3) id PAA10097
	for ietf-ssh-outgoing; Sat, 10 Jun 2000 15:30:49 +0300
Received: from folly.informatik.uni-erlangen.de (IDENT:postfix@nbgdi5-145-253-148-002.arcor-ip.net [145.253.148.2])
	by mail.clinet.fi (8.9.3/8.9.3) with ESMTP id PAA10094
	for <ietf-ssh@clinet.fi>; Sat, 10 Jun 2000 15:30:47 +0300
Received: by folly.informatik.uni-erlangen.de (Postfix, from userid 31451)
	id 3D117F9B; Sat, 10 Jun 2000 14:13:43 +0200 (CEST)
Date: Sat, 10 Jun 2000 14:13:42 +0200
From: Markus Friedl <markus.friedl@informatik.uni-erlangen.de>
To: "Richard E. Silverman" <slade@shore.net>
Cc: ietf-ssh@clinet.fi
Subject: Re: KEXINIT "cookie" (SSH-TRANS)
Message-ID: <20000610141342.A13373@folly.informatik.uni-erlangen.de>
References: <200006100001.UAA09375@syrinx.oankali.net>
Mime-Version: 1.0
Content-Type: text/plain; charset=us-ascii
X-Mailer: Mutt 1.0.1i
In-Reply-To: <200006100001.UAA09375@syrinx.oankali.net>; from slade@shore.net on Fri, Jun 09, 2000 at 08:01:30PM -0400
Sender: owner-ietf-ssh@clinet.fi
Precedence: bulk
Content-Length: 751
Lines: 19

On Fri, Jun 09, 2000 at 08:01:30PM -0400, Richard E. Silverman wrote:
> 
> In the SSH-TRANS document, the format of a KEXINIT message includes a
> 16-byte random cookie, about which is said:
> 
>       The cookie MUST be a random value generated by the sender.  Its
>       purpose is to make it impossible for either side to fully
>       determine the keys and the session identifier.
> 
> After this, though, I can't find any mention of the cookie at all, so it
> appears not to be used.  Can anyone comment on this?

the cookie is used when computing the 'hash H', since
the full payload of KEXINIT messages is used:

	string    I_C, the payload of the client's SSH_MSG_KEXINIT
	string    I_S, the payload of the server's SSH_MSG_KEXINIT

-markus
From owner-ietf-ssh@clinet.fi  Sun Jun 11 07:47:15 2000
Return-Path: <owner-ietf-ssh@clinet.fi>
Received: from faui45.informatik.uni-erlangen.de (root@faui45.informatik.uni-erlangen.de [131.188.34.45])
	by faui01.informatik.uni-erlangen.de (8.8.8/8.1.16-FAU) with ESMTP id HAA26233
	for <msfriedl@cip.informatik.uni-erlangen.de>; Sun, 11 Jun 2000 07:47:14 +0200 (MET DST)
Received: from mail.clinet.fi (mail.clinet.fi [194.100.0.7])
	by faui45.informatik.uni-erlangen.de (8.9.1/8.1.49-FAU) with ESMTP id HAA04960
	for <Markus.Friedl@informatik.uni-erlangen.de>; Sun, 11 Jun 2000 07:47:13 +0200 (MET DST)
Received: (from majordom@localhost)
	by mail.clinet.fi (8.9.3/8.9.3) id GAA01484
	for ietf-ssh-outgoing; Sun, 11 Jun 2000 06:34:31 +0300
Received: from syrinx.oankali.net (syrinx.oankali.net [206.243.169.50])
	by mail.clinet.fi (8.9.3/8.9.3) with ESMTP id GAA01478
	for <ietf-ssh@clinet.fi>; Sun, 11 Jun 2000 06:34:29 +0300
Received: (from res@localhost)
	by syrinx.oankali.net (8.9.3/8.9.3) id XAA10400;
	Sat, 10 Jun 2000 23:31:54 -0400
Date: Sat, 10 Jun 2000 23:31:53 -0400 (EDT)
From: "Richard E. Silverman" <res@shore.net>
X-Sender: res@syrinx.oankali.net
Reply-To: "Richard E. Silverman" <slade@shore.net>
To: ietf-ssh@clinet.fi
Subject: Re: KEXINIT "cookie" (SSH-TRANS)
In-Reply-To: <nnya4dx5jc.fsf@sture.lysator.liu.se>
Message-ID: <Pine.LNX.4.10.10006102319590.30746-100000@syrinx.oankali.net>
MIME-Version: 1.0
Content-Type: TEXT/PLAIN; charset=X-UNKNOWN
Content-Transfer-Encoding: 8bit
X-MIME-Autoconverted: from QUOTED-PRINTABLE to 8bit by mail.clinet.fi id GAA01481
Sender: owner-ietf-ssh@clinet.fi
Precedence: bulk
Content-Length: 955
Lines: 27


On 10 Jun 2000, Niels Mller wrote:

> It's included in the exchange hash, as part of "I_C" and "I_S":

Oops!  I missed that while looking for an explicit mention of the
"cookie."  Thanks!

> but for keyexchange methods where one of the parties doesn't
> contribute any random values (like in the RSA-based methods used in
> SSL and (I think) ssh-1), 

Yes, in SSH-1 the client generates the session key entirely on its own and
sends it to the server.

> the cookies are needed to make replay attacks more difficult.

It also prevents a trojaned client from picking gimmicked keys allowing
the attacker to guess them (e.g. pick from a reduced keyspace, or with a
special form, etc.).  A trojaned client is a disaster in any event, but
with SSH-2 it would have to find some way to signal the key to the
attacker, and that might be noticed.  In SSH-1, the trojaned client can
behave entirely normally and the compromise will never be noticed.

- Richard


From owner-ietf-ssh@clinet.fi  Mon Jun 12 20:47:36 2000
Return-Path: <owner-ietf-ssh@clinet.fi>
Received: from faui45.informatik.uni-erlangen.de (root@faui45.informatik.uni-erlangen.de [131.188.34.45])
	by faui01.informatik.uni-erlangen.de (8.8.8/8.1.16-FAU) with ESMTP id UAA06420
	for <msfriedl@cip.informatik.uni-erlangen.de>; Mon, 12 Jun 2000 20:47:36 +0200 (MET DST)
Received: from mail.clinet.fi (mail.clinet.fi [194.100.0.7])
	by faui45.informatik.uni-erlangen.de (8.9.1/8.1.49-FAU) with ESMTP id UAA24476
	for <Markus.Friedl@informatik.uni-erlangen.de>; Mon, 12 Jun 2000 20:47:35 +0200 (MET DST)
Received: (from majordom@localhost)
	by mail.clinet.fi (8.9.3/8.9.3) id TAA00328
	for ietf-ssh-outgoing; Mon, 12 Jun 2000 19:55:00 +0300
Received: from samantha.lysator.liu.se (root@samantha.lysator.liu.se [130.236.254.202])
	by mail.clinet.fi (8.9.3/8.9.3) with ESMTP id TAA00324
	for <ietf-ssh@clinet.fi>; Mon, 12 Jun 2000 19:54:59 +0300
Received: from sture.lysator.liu.se (nisse@sture.lysator.liu.se [130.236.254.21])
	by samantha.lysator.liu.se (8.9.3/8.9.3) with ESMTP id SAA00033;
	Mon, 12 Jun 2000 18:54:57 +0200 (MET DST)
Received: (from nisse@localhost)
	by sture.lysator.liu.se (8.9.0/8.8.7) id SAA29537;
	Mon, 12 Jun 2000 18:54:54 +0200 (MET DST)
To: "Richard E. Silverman" <slade@shore.net>
Cc: ietf-ssh@clinet.fi
Subject: Re: KEXINIT "cookie" (SSH-TRANS)
References: <Pine.LNX.4.10.10006102319590.30746-100000@syrinx.oankali.net>
From: nisse@lysator.liu.se (Niels Mller)
Date: 12 Jun 2000 18:54:53 +0200
In-Reply-To: "Richard E. Silverman"'s message of "Sat, 10 Jun 2000 23:31:53 -0400 (EDT)"
Message-ID: <nnem62x2jm.fsf@sture.lysator.liu.se>
X-Mailer: Gnus v5.7/Emacs 20.5
Sender: owner-ietf-ssh@clinet.fi
Precedence: bulk
Content-Length: 1338
Lines: 30

"Richard E. Silverman" <res@shore.net> writes:

> On 10 Jun 2000, Niels Mller wrote:
> 
> > the cookies are needed to make replay attacks more difficult.
> 
> It also prevents a trojaned client from picking gimmicked keys allowing
> the attacker to guess them (e.g. pick from a reduced keyspace, or with a
> special form, etc.).  A trojaned client is a disaster in any event, but
> with SSH-2 it would have to find some way to signal the key to the
> attacker, and that might be noticed.

I'm sure I can agree with that. A backdoored ssh2 client could just
choose its "secret" DH-exponent from a small space, known to the
attacker. If the attcker knows that the client chooses its exponent as
a random number between, say, 1000 and 5000, he can get the session
key by trying those few thousands of exponents exponents one by one.

Or am I missing something? As far as I can see, using a bad randomness
source (either by mistake, or by using a backdoored client), is as
disastrous to ssh2 security as it is with ssh1 or SSL.

There are also other ways information can be leaked. For instance, a
backdoored client might use a very good randomness source for creating
its cookie, and then choose a the secret exponent as HMAC(attacker's
secret key, cookie). I think that would be very hard to detect by just
observing the traffic.

/Niels

From owner-ietf-ssh@clinet.fi  Mon Jun 12 22:44:16 2000
Return-Path: <owner-ietf-ssh@clinet.fi>
Received: from faui45.informatik.uni-erlangen.de (root@faui45.informatik.uni-erlangen.de [131.188.34.45])
	by faui01.informatik.uni-erlangen.de (8.8.8/8.1.16-FAU) with ESMTP id WAA11260
	for <msfriedl@cip.informatik.uni-erlangen.de>; Mon, 12 Jun 2000 22:44:15 +0200 (MET DST)
Received: from mail.clinet.fi (mail.clinet.fi [194.100.0.7])
	by faui45.informatik.uni-erlangen.de (8.9.1/8.1.49-FAU) with ESMTP id WAA01319
	for <Markus.Friedl@informatik.uni-erlangen.de>; Mon, 12 Jun 2000 22:44:14 +0200 (MET DST)
Received: (from majordom@localhost)
	by mail.clinet.fi (8.9.3/8.9.3) id VAA10390
	for ietf-ssh-outgoing; Mon, 12 Jun 2000 21:42:40 +0300
Received: from mail.liu.se (wille.unit.liu.se [130.236.1.30])
	by mail.clinet.fi (8.9.3/8.9.3) with ESMTP id VAA10387
	for <ietf-ssh@clinet.fi>; Mon, 12 Jun 2000 21:42:39 +0300
Received: from sture.lysator.liu.se (sture.lysator.liu.se [130.236.254.21])
	by mail.liu.se (Postfix) with ESMTP
	id EB68B7B85; Mon, 12 Jun 2000 20:42:38 +0200 (MET DST)
Received: (from nisse@localhost)
	by sture.lysator.liu.se (8.9.0/8.8.7) id UAA03563;
	Mon, 12 Jun 2000 20:42:38 +0200 (MET DST)
To: "Richard E. Silverman" <slade@shore.net>
Cc: ietf-ssh@clinet.fi
Subject: Re: KEXINIT "cookie" (SSH-TRANS)
References: <Pine.LNX.4.10.10006102319590.30746-100000@syrinx.oankali.net> <nnem62x2jm.fsf@sture.lysator.liu.se>
From: nisse@lysator.liu.se (Niels Mller)
Date: 12 Jun 2000 20:42:38 +0200
In-Reply-To: nisse@lysator.liu.se's message of "12 Jun 2000 18:54:53 +0200"
Message-ID: <nn8zwawxk1.fsf@sture.lysator.liu.se>
X-Mailer: Gnus v5.7/Emacs 20.5
Sender: owner-ietf-ssh@clinet.fi
Precedence: bulk
Content-Length: 1466
Lines: 33

Ooops. I missed a negation here. Sorry for any confusion.

> "Richard E. Silverman" <res@shore.net> writes:
> 
> > On 10 Jun 2000, Niels Mller wrote:
> > 
> > > the cookies are needed to make replay attacks more difficult.
> > 
> > It also prevents a trojaned client from picking gimmicked keys allowing
> > the attacker to guess them (e.g. pick from a reduced keyspace, or with a
> > special form, etc.).  A trojaned client is a disaster in any event, but
> > with SSH-2 it would have to find some way to signal the key to the
> > attacker, and that might be noticed.
> 
> I'm sure I can agree with that. A backdoored ssh2 client could just
     ^ not

> choose its "secret" DH-exponent from a small space, known to the
> attacker. If the attcker knows that the client chooses its exponent as
> a random number between, say, 1000 and 5000, he can get the session
> key by trying those few thousands of exponents exponents one by one.
> 
> Or am I missing something? As far as I can see, using a bad randomness
> source (either by mistake, or by using a backdoored client), is as
> disastrous to ssh2 security as it is with ssh1 or SSL.
> 
> There are also other ways information can be leaked. For instance, a
> backdoored client might use a very good randomness source for creating
> its cookie, and then choose a the secret exponent as HMAC(attacker's
> secret key, cookie). I think that would be very hard to detect by just
> observing the traffic.
> 
> /Niels
From owner-ietf-ssh@clinet.fi  Wed Jun 14 12:15:59 2000
Return-Path: <owner-ietf-ssh@clinet.fi>
Received: from faui45.informatik.uni-erlangen.de (root@faui45.informatik.uni-erlangen.de [131.188.34.45])
	by faui01.informatik.uni-erlangen.de (8.8.8/8.1.16-FAU) with ESMTP id MAA02870
	for <msfriedl@cip.informatik.uni-erlangen.de>; Wed, 14 Jun 2000 12:15:59 +0200 (MET DST)
Received: from mail.clinet.fi (mail.clinet.fi [194.100.0.7])
	by faui45.informatik.uni-erlangen.de (8.9.1/8.1.49-FAU) with ESMTP id MAA15413
	for <Markus.Friedl@informatik.uni-erlangen.de>; Wed, 14 Jun 2000 12:15:57 +0200 (MET DST)
Received: (from majordom@localhost)
	by mail.clinet.fi (8.9.3/8.9.3) id JAA07623
	for ietf-ssh-outgoing; Wed, 14 Jun 2000 09:53:05 +0300
Received: from syrinx.oankali.net (syrinx.oankali.net [206.243.169.50])
	by mail.clinet.fi (8.9.3/8.9.3) with ESMTP id JAA07614
	for <ietf-ssh@clinet.fi>; Wed, 14 Jun 2000 09:53:03 +0300
Received: (from res@localhost)
	by syrinx.oankali.net (8.9.3/8.9.3) id CAA27510;
	Wed, 14 Jun 2000 02:50:16 -0400
Date: Wed, 14 Jun 2000 02:50:16 -0400 (EDT)
From: "Richard E. Silverman" <res@shore.net>
X-Sender: res@syrinx.oankali.net
Reply-To: "Richard E. Silverman" <slade@shore.net>
To: SECSH Discussion List <ietf-ssh@clinet.fi>
Subject: Re: KEXINIT "cookie" (SSH-TRANS)
In-Reply-To: <nnem62x2jm.fsf@sture.lysator.liu.se>
Message-ID: <Pine.LNX.4.10.10006140128180.10393-100000@syrinx.oankali.net>
MIME-Version: 1.0
Content-Type: TEXT/PLAIN; charset=US-ASCII
Sender: owner-ietf-ssh@clinet.fi
Precedence: bulk
Content-Length: 887
Lines: 23


Niels> Or am I missing something? ...

Not at all.  I had been thinking that the SSH-2 mechanism of generating
the session key from the shared secret, rather than using the secret
directly, would protect against this kind of attack, specifically when
using an SSH-1 style encrypted key exchange in which the session key is
chosen by the client.  But your comments have shown me that I wasn't
thinking clearly about it.  Following the example the of the SSH-2 DH
exchange, an SSH-1 style exchange in SSH-2 would probably have an exchange
hash computed over the client-chosen secret plus a bunch of externally
observable data.  The attacker has everything he needs to compute actual
session key from the compromised secret.  It does require more observation
and work than it would in SSH-1, but not enough to make any real
difference.

Thanks!

--
  Richard Silverman
  slade@shore.net


From owner-ietf-ssh@clinet.fi  Thu Jun 15 22:53:22 2000
Return-Path: <owner-ietf-ssh@clinet.fi>
Received: from faui45.informatik.uni-erlangen.de (root@faui45.informatik.uni-erlangen.de [131.188.34.45])
	by faui02.informatik.uni-erlangen.de (8.9.1/8.1.16-FAU) with ESMTP id WAA06545
	for <msfriedl@cip.informatik.uni-erlangen.de>; Thu, 15 Jun 2000 22:53:21 +0200 (MET DST)
Received: from mail.clinet.fi (mail.clinet.fi [194.100.0.7])
	by faui45.informatik.uni-erlangen.de (8.9.1/8.1.49-FAU) with ESMTP id WAA18793
	for <Markus.Friedl@informatik.uni-erlangen.de>; Thu, 15 Jun 2000 22:53:20 +0200 (MET DST)
Received: (from majordom@localhost)
	by mail.clinet.fi (8.9.3/8.9.3) id VAA12237
	for ietf-ssh-outgoing; Thu, 15 Jun 2000 21:50:35 +0300
Received: from syrinx.oankali.net (syrinx.oankali.net [206.243.169.50])
	by mail.clinet.fi (8.9.3/8.9.3) with ESMTP id VAA12234
	for <ietf-ssh@clinet.fi>; Thu, 15 Jun 2000 21:50:34 +0300
Received: (from res@localhost)
	by syrinx.oankali.net (8.9.3/8.9.3) id OAA04362;
	Thu, 15 Jun 2000 14:47:48 -0400
Date: Thu, 15 Jun 2000 14:47:48 -0400
Message-Id: <200006151847.OAA04362@syrinx.oankali.net>
From: "Richard E. Silverman" <slade@shore.net>
To: SECSH Discussion List <ietf-ssh@clinet.fi>
Subject: "ssh-rsa" public-key type
Sender: owner-ietf-ssh@clinet.fi
Precedence: bulk
Content-Length: 526
Lines: 15


The commercial version of SSH2 from ssh.com supports RSA as well as DSA keys
for publickey authentication.  The key format name it uses for this is
"ssh-rsa".  Unlike "ssh-dss", though, this is not defined in the current draft
standard.  So I'm curious why this type isn't "ssh-rsa@ssh.com" instead -- has
this global name been used in anticipation of its being added to the draft?

btw, is there an archive of this mailing list?  I went looking for one but
didn't find it.

Thanks,

--
  Richard Silverman
  slade@shore.net
From owner-ietf-ssh@clinet.fi  Sat Jun 17 03:44:56 2000
Return-Path: <owner-ietf-ssh@clinet.fi>
Received: from faui45.informatik.uni-erlangen.de (root@faui45.informatik.uni-erlangen.de [131.188.34.45])
	by faui02.informatik.uni-erlangen.de (8.9.1/8.1.16-FAU) with ESMTP id DAA16410
	for <msfriedl@cip.informatik.uni-erlangen.de>; Sat, 17 Jun 2000 03:44:56 +0200 (MET DST)
Received: from mail.clinet.fi (mail.clinet.fi [194.100.0.7])
	by faui45.informatik.uni-erlangen.de (8.9.1/8.1.49-FAU) with ESMTP id DAA00535
	for <Markus.Friedl@informatik.uni-erlangen.de>; Sat, 17 Jun 2000 03:44:55 +0200 (MET DST)
Received: (from majordom@localhost)
	by mail.clinet.fi (8.9.3/8.9.3) id CAA05926
	for ietf-ssh-outgoing; Sat, 17 Jun 2000 02:38:24 +0300
Received: from asgard.tky.hut.fi (asgard.tky.hut.fi [130.233.29.146])
	by mail.clinet.fi (8.9.3/8.9.3) with ESMTP id CAA05908
	for <ietf-ssh@clinet.fi>; Sat, 17 Jun 2000 02:38:22 +0300
Received: (from sjl@localhost)
	by asgard.tky.hut.fi (8.10.0/8.10.0) id e5GNaj132307;
	Sat, 17 Jun 2000 02:36:45 +0300
From: Sami Lehtinen <sjl@iki.fi>
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
Message-ID: <14666.47629.645249.255747@asgard.tky.hut.fi>
Date: Sat, 17 Jun 2000 02:36:45 +0300 (EEST)
To: "Richard E. Silverman" <slade@shore.net>
Cc: SECSH Discussion List <ietf-ssh@clinet.fi>
Subject: "ssh-rsa" public-key type
In-Reply-To: <200006151847.OAA04362@syrinx.oankali.net>
References: <200006151847.OAA04362@syrinx.oankali.net>
X-Mailer: VM 6.72 under 21.1 (patch 9) "Canyonlands" XEmacs Lucid
Sender: owner-ietf-ssh@clinet.fi
Precedence: bulk
Content-Length: 1077
Lines: 26

Richard E. Silverman writes:
  : 
  : The commercial version of SSH2 from ssh.com supports RSA as well as DSA keys
  : for publickey authentication.  The key format name it uses for this is
  : "ssh-rsa".  Unlike "ssh-dss", though, this is not defined in the current draft
  : standard.  So I'm curious why this type isn't "ssh-rsa@ssh.com" instead -- has
  : this global name been used in anticipation of its being added to the draft?

"ssh-rsa" is supposed to be added to the draft as soon as the patent
expires.

The only implementation (to my knowledge) that uses this is the one
that F-Secure distributes. Our (SSH Communications Security)
distribution shouldn't include that algorithm. If it does, it is a
serious bug :)

  : btw, is there an archive of this mailing list?  I went looking for one but
  : didn't find it.

Sorry, I don't know of any.

Regards,
-- 
[sjl@ssh.com          --  Sami J. Lehtinen  --           sjl@iki.fi]
[work:+358 9 85657425][gsm:+358 50 5170 258][http://www.iki.fi/~sjl]
[SSH Communications Security Corp               http://www.ssh.com/]
From owner-ietf-ssh@clinet.fi  Sat Jun 17 05:07:52 2000
Return-Path: <owner-ietf-ssh@clinet.fi>
Received: from faui45.informatik.uni-erlangen.de (root@faui45.informatik.uni-erlangen.de [131.188.34.45])
	by faui02.informatik.uni-erlangen.de (8.9.1/8.1.16-FAU) with ESMTP id FAA22395
	for <msfriedl@cip.informatik.uni-erlangen.de>; Sat, 17 Jun 2000 05:07:52 +0200 (MET DST)
Received: from mail.clinet.fi (mail.clinet.fi [194.100.0.7])
	by faui45.informatik.uni-erlangen.de (8.9.1/8.1.49-FAU) with ESMTP id FAA03440
	for <Markus.Friedl@informatik.uni-erlangen.de>; Sat, 17 Jun 2000 05:07:51 +0200 (MET DST)
Received: (from majordom@localhost)
	by mail.clinet.fi (8.9.3/8.9.3) id EAA12546
	for ietf-ssh-outgoing; Sat, 17 Jun 2000 04:07:37 +0300
Received: from syrinx.oankali.net (syrinx.oankali.net [206.243.169.50])
	by mail.clinet.fi (8.9.3/8.9.3) with ESMTP id EAA12543
	for <ietf-ssh@clinet.fi>; Sat, 17 Jun 2000 04:07:36 +0300
Received: (from res@localhost)
	by syrinx.oankali.net (8.9.3/8.9.3) id VAA05319;
	Fri, 16 Jun 2000 21:04:46 -0400
Date: Fri, 16 Jun 2000 21:04:46 -0400 (EDT)
From: "Richard E. Silverman" <res@shore.net>
X-Sender: res@syrinx.oankali.net
Reply-To: "Richard E. Silverman" <slade@shore.net>
To: SECSH Discussion List <ietf-ssh@clinet.fi>
Subject: Re: "ssh-rsa" public-key type
In-Reply-To: <14666.47629.645249.255747@asgard.tky.hut.fi>
Message-ID: <Pine.LNX.4.10.10006162103100.10393-100000@syrinx.oankali.net>
MIME-Version: 1.0
Content-Type: TEXT/PLAIN; charset=US-ASCII
Sender: owner-ietf-ssh@clinet.fi
Precedence: bulk
Content-Length: 499
Lines: 18


> "ssh-rsa" is supposed to be added to the draft as soon as the patent
> expires.

Ah, that makes sense.

> The only implementation (to my knowledge) that uses this is the one
> that F-Secure distributes. Our (SSH Communications Security)
> distribution shouldn't include that algorithm. If it does, it is a
> serious bug :)

Sorry, you're right; it is the F-Secure commercial product I was looking
at.  Too many SSH versions sitting on my machines.  :)

-- 
  Richard Silverman
  slade@shore.net

From owner-ietf-ssh@clinet.fi  Wed Jun 21 15:40:19 2000
Return-Path: <owner-ietf-ssh@clinet.fi>
Received: from faui45.informatik.uni-erlangen.de (root@faui45.informatik.uni-erlangen.de [131.188.34.45])
	by faui02.informatik.uni-erlangen.de (8.9.1/8.1.16-FAU) with ESMTP id PAA01472
	for <msfriedl@cip.informatik.uni-erlangen.de>; Wed, 21 Jun 2000 15:40:19 +0200 (MET DST)
Received: from mail.clinet.fi (mail.clinet.fi [194.100.0.7])
	by faui45.informatik.uni-erlangen.de (8.9.1/8.1.49-FAU) with ESMTP id PAA20084
	for <Markus.Friedl@informatik.uni-erlangen.de>; Wed, 21 Jun 2000 15:40:17 +0200 (MET DST)
Received: (from majordom@localhost)
	by mail.clinet.fi (8.9.3/8.9.3) id OAA04917
	for ietf-ssh-outgoing; Wed, 21 Jun 2000 14:24:15 +0300
Received: from cdc-info.cdc.informatik.tu-darmstadt.de (cdc-info.cdc.informatik.tu-darmstadt.de [130.83.23.100])
	by mail.clinet.fi (8.9.3/8.9.3) with ESMTP id OAA04911
	for <ietf-ssh@clinet.fi>; Wed, 21 Jun 2000 14:24:13 +0300
Received: from cdc1.cdc.informatik.tu-darmstadt.de (cdc1 [130.83.23.10])
	by cdc-info.cdc.informatik.tu-darmstadt.de (Postfix) with ESMTP
	id B3EAC2C4E; Wed, 21 Jun 2000 13:24:09 +0200 (MET DST)
Received: by cdc1.cdc.informatik.tu-darmstadt.de (8.8.8+Sun/SMI-SVR4)
	id NAA02033; Wed, 21 Jun 2000 13:24:08 +0200 (MET DST)
Date: Wed, 21 Jun 2000 13:24:08 +0200
From: Bodo Moeller <moeller@cdc.informatik.tu-darmstadt.de>
To: =?iso-8859-1?Q?Niels_M=F6ller?= <nisse@lysator.liu.se>
Cc: Ben Laurie <ben@algroup.co.uk>, Coderpunks <coderpunks@toad.com>,
        Cryptography <cryptography@c2.net>, ietf-ssh@clinet.fi
Subject: Re: Extracting Entropy?
Message-ID: <20000621132407.C1946@cdc.informatik.tu-darmstadt.de>
References: <394E92AA.B40A2274@algroup.co.uk> <nn66r4tf70.fsf@sture.lysator.liu.se> <20000621120841.A1798@cdc.informatik.tu-darmstadt.de> <nn3dm7tjy1.fsf@sture.lysator.liu.se>
Mime-Version: 1.0
Content-Type: text/plain; charset=iso-8859-1
Content-Transfer-Encoding: 8bit
X-Mailer: Mutt 1.0i
In-Reply-To: <nn3dm7tjy1.fsf@sture.lysator.liu.se>; from nisse@lysator.liu.se on Wed, Jun 21, 2000 at 12:19:50PM +0200
Sender: owner-ietf-ssh@clinet.fi
Precedence: bulk
Content-Length: 2317
Lines: 58

On Wed, Jun 21, 2000 at 12:19:50PM +0200, Niels Mller wrote:
> Bodo Moeller <moeller@cdc.informatik.tu-darmstadt.de> writes:
>> On Tue, Jun 20, 2000 at 07:50:11PM +0200, Niels Mller wrote:

>>> That is specified in draft-ietf-secsh-transport-07.txt, the
>>> relevant section is
>>> 
>>>: If the key length in longer than the output
>>>: of the HASH, the key is extended by computing HASH of the concatenation
>>>: of K and H and the entire key so far, and appending the resulting bytes
>>>: (as many as HASH generates) to the key.  This process is repeated until
>>>: enough key material is available; the key is taken from the beginning of
>>>: this value.  In other words,
>>>: 
>>>:   K1 = HASH(K || H || X || session_id)   (X is e.g. "A")
>>>:   K2 = HASH(K || H || K1)
>>>:   K3 = HASH(K || H || K1 || K2)
>>>:   ...
>>>:   key = K1 || K2 || K3 || ...
>>> 
>>> Here, K is the secret being stretched, and H is an "exchange hash"
>>> that can probably be ignored in this context. The X is different for
>>> the keys that are generated from the same secret.

>> With usual hash functions (Merkle/Damgrd construction), you're
>> wasting entropy if there are more than  2^B  possible values for  K
>> where  B  is the size of the output of the compression function.
>> The reason is that the hash construct always has the same internal
>> state when  K  is hashed in.

> Ah, thanks, I had not realized that. In the ssh case, the hash
> function used is sha1, and the internal state is 512 bits.

Isn't the chaining size just 160 bits, like the output?
The input is processed in larger chunks, but that doesn't
mean that the state is that large too.

>> This problem would be avoided by setting
>> 
>>       K1 = HASH(K || H || X || session_id)   (X is e.g. "A")
>>       K2 = HASH(K1 || H || K)
>>       K3 = HASH(K2 || H || K)
>>       ...
>>       key = K1 || K2 || K3 || ...
>> 
>> because in this variant  K  is applied at different states of the hash
>> construct.

> Do you think this is a point worth raising on the ietf-ssh list? 

Cc: added.


-- 
Bodo Mller <moeller@cdc.informatik.tu-darmstadt.de>
PGP http://www.informatik.tu-darmstadt.de/TI/Mitarbeiter/moeller/0x36d2c658.html
* TU Darmstadt, Theoretische Informatik, Alexanderstr. 10, D-64283 Darmstadt
* Tel. +49-6151-16-6628, Fax +49-6151-16-6036
