From owner-ietf-ssh@clinet.fi  Mon May  8 17:02: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 faui01.informatik.uni-erlangen.de (8.8.8/8.1.16-FAU) with ESMTP id RAA05451
	for <msfriedl@cip.informatik.uni-erlangen.de>; Mon, 8 May 2000 17:02:22 +0200 (MET DST)
From: owner-ietf-ssh@clinet.fi
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 QAA12030
	for <Markus.Friedl@informatik.uni-erlangen.de>; Mon, 8 May 2000 16:21:32 +0200 (MET DST)
Received: (from majordom@localhost)
	by mail.clinet.fi (8.9.3/8.9.3) id OAA22824
	for ietf-ssh-outgoing; Mon, 8 May 2000 14:57:38 +0300
Received: from ausmtp02.au.ibm.com (ausmtp02.au.ibm.COM [202.135.136.105])
	by mail.clinet.fi (8.9.3/8.9.3) with ESMTP id OAA22802
	for <ietf-ssh@clinet.fi>; Mon, 8 May 2000 14:57:34 +0300
Received: from f03n07e.au.ibm.com 
	by ausmtp02.au.ibm.com (IBM AP 1.0) with ESMTP id VAA121170
	for <ietf-ssh@clinet.fi>; Mon, 8 May 2000 21:52:25 +1000
Received: from d73mta05.au.ibm.com (f06n05s [9.185.166.67])
	by f03n07e.au.ibm.com (8.8.8m2/8.8.7) with SMTP id VAA71604
	for <ietf-ssh@clinet.fi>; Mon, 8 May 2000 21:57:23 +1000
Received: by d73mta05.au.ibm.com(Lotus SMTP MTA v4.6.5  (863.2 5-20-1999))  id CA2568D9.0041AD69 ; Mon, 8 May 2000 21:57:22 +1000
X-Lotus-FromDomain: IBMAU@IBMIN@IBMAU
To: ietf-ssh@clinet.fi
Message-ID: <CA2568D9.0041A9B6.00@d73mta05.au.ibm.com>
Date: Mon, 8 May 2000 14:10:29 +0530
Subject: Additional Diffie-Hellman key exchange method
Mime-Version: 1.0
Content-type: text/plain; charset=us-ascii
Content-Disposition: inline
Sender: owner-ietf-ssh@clinet.fi
Precedence: bulk
Content-Length: 7291
Lines: 166




Forgive me if this topic has been discussed before. I found no mention
of it in the archives, but that may be because of my poor eyes. In
either case, I'd like to make a comment about
diffie-hellman-group1-sha1, and suggest that it be supplemented by
another key method:

[For various legal reasons, it's best if I include the following note in
its entirety. I apologize for the length.]

---------

A Suggested Improvement to SSHv2}
Jonathan Herzog
The MITRE Corporation
WN99B000041


The SSH (Secure SHell) protocol has become one of many de-facto
Internet standards for secure log-on and other network services across
an insecure connection. It is commonly used to secure connections such
as telnet or rsh, for secure file transfers (via the scp command), as
a secure tunnel for other connections such as http or X, or as a VPN
component.

A second version of the protocol has been formulated by an IETF
working group, and is being currently being considered for RFC
status. This version of the protocol was the subject of investigation
by the MITRE Corporation, whose analysis identified an area of
concern. In this note, we present a brief overview of the SSHv2
protocol, explain the area of concern, and suggest a solution.

SSH is a client-server protocol. In its second incarnation,
the SSH protocol is actually composed of three sub-protocols, layered
upon each other:

-- The Transport layer, which is the focus of this note, contains two
   exchanges and provides two services:

     * At the beginning of a connection, the two parties negotiate
       the cryptographic algorithms to be used.

     * The client and server engage in "key exchange," which
       includes server authentication as well as key exchange. The
       exact mechanism used is negotiated as part of the exchange
       above.

   Both the algorithm negotiation and the key exchange/server
   authentication are required at the beginning of a connection, but
   can re-occur at any time (as desired by the participants).

   The Transport layer also:

     * Breaks streams of data from higher protocols into packets
       for transmission, and combines incoming packets back into
       streams of data, and

     * Provides cryptographic services
       such as integrity and confidentiality, and non-cryptographic
       services such as compression. The algorithms used for these
       services are negotiated as above.

-- The Authentication layer relies on the secure tunnel established at
   the Transport layer, and provides mechanisms for client
   authentication.  Typically, these mechanisms will be based on a
   name-password pair (traveling within the secure tunnel) but may rely
   on more secure methods.

-- The Connection layer multiplexes many connections through the
   mutually-authenticated tunnel established by the Authentication
layer.


The protocol is designed to be modular, in that the client and server
can negotiate acceptable settings and algorithms for each service
separately. The algorithms for confidentiality can be negotiated
separately from those for integrity, for example, and the algorithms
for client-to-server communication can be different than those for
server-to-client. For inter operability reasons, the specification
contains a set of algorithms which must be supported by all
implementations.

Of concern here is the key exchange algorithm
diffie-hellman-group1-sha1, which is the only key exchange algorithm
defined by the standard. This exchange proceeds as follows:

1. The client chooses a random number x, and sends to the server
the value g^x  mod  p, where p is a large prime number and
p, g are given in the specification.

2. The server chooses its own random number y, and sends to the
client:

-- g^y mod p,
-- its certificate, and
-- a signed hash of
     * all previous messages, and
     * the secret key g^{xy} mod p.


The area of concern focuses upon the fact that the specification fixes
the values of p and g. The key exchange scheme described above is
called Diffie-Hellman (where the certificate and signed hash have been
added to prevent man-in-the-middle attacks), and it relies upon the
difficulty of the discrete logarithm for its security. Under some
conditions, the discrete log is easy to compute, and for this reason
the value of p must be chosen carefully. For example, it is easy to
compute the discrete logarithm when p-1 has only small prime
factors, and hence p is usually chosen so that (p-1)/2 is itself
prime. Likewise, some care must be given to the choice of g so that
the subgroup generated by g is relatively large, but this is usually
an easier choice to make than the choice of p.

Because a poor choice of p or g has potential pitfalls, it is not
inherently a bad decision to re-use the same values in many runs of
Diffie-Hellman. Indeed, it may actually be desirable for
inter operability reasons. (For example, if one were to create
certificates containing Diffie-Hellman values, one might insist on the
use of global values, so that any two certificates can be used
together.)  In the case of SSH, however, there is no performance
considerations that would benefit from the use of a standard p
value. Indeed, prudent design considerations might actually indicate
the opposite.

The best known algorithms for generalized discrete logarithms are
still quite slow, but the majority of time is actually consumed in
easily parallelizable precomputations about the group (choice of p
and g) in general. Once these precomputations are finished, then any
discrete logarithm in that group is easily found. Given that most SSH
connections will be created using the only key exchange algorithm
defined in the specification, the time and expense required to break
the majority of SSH connections is therefore only slightly greater that
the time and expense required to perform the aforementioned
precomputations for the group specified in the standard.

One time-honored rule for security design is that the value of
the data being protected should be less than the expense required to
break the security system. Given that SSH is a popular choice of
security protocol for remote login and VPN applications, the value of
all data protected by SSH might indeed exceed the expense of the
precomputations required above.

For this reason, we believe that it should be recommended to the SSH
IETF working group that the current key exchange algorithm,
diffie-hellman-group1-sha1, be supplemented by another standard key
exchange algorithm that allows the p and g values to be
negotiated. Although it might be advisable to provide a list of
recommended strong values in the specification (or elsewhere), the
recommended algorithm should allow the client and server to negotiate
a pair of mutually acceptable values independent of said list. Just as
the connection terminates if no mutually acceptable encryption scheme
can be found, the connection should terminate if no mutually
acceptable set of Diffie-Hellman values can be found.

The specific details of this algorithm can be left open, to be decided
upon by the members of the SSH IETF working group.

--------------

--
Jonathan C. Herzog  |  business: jherzog@mitre.org  |  "Television is
#include<witty.sig> |  pleasure: jherzog@iname.com  |    furniture."


From owner-ietf-ssh@clinet.fi  Mon May  8 20:50: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 faui01.informatik.uni-erlangen.de (8.8.8/8.1.16-FAU) with ESMTP id UAA23044
	for <msfriedl@cip.informatik.uni-erlangen.de>; Mon, 8 May 2000 20:50:55 +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 UAA04224
	for <Markus.Friedl@informatik.uni-erlangen.de>; Mon, 8 May 2000 20:50:53 +0200 (MET DST)
Received: (from majordom@localhost)
	by mail.clinet.fi (8.9.3/8.9.3) id TAA27954
	for ietf-ssh-outgoing; Mon, 8 May 2000 19:18:28 +0300
Received: from inner.net (avarice.inner.net [199.33.248.2])
	by mail.clinet.fi (8.9.3/8.9.3) with ESMTP id TAA27948
	for <ietf-ssh@clinet.fi>; Mon, 8 May 2000 19:18:26 +0300
Received: from c8-a.snvl1.sfba.home.com ([216.52.8.30])
	by inner.net (8.7.6/8.9.3) with ESMTP id QAA12687;
	Mon, 8 May 2000 16:07:30 GMT
Message-Id: <4.2.0.58.20000508121720.0098ed10@avarice.inner.net>
X-Sender: rja@avarice.inner.net
X-Mailer: QUALCOMM Windows Eudora Pro Version 4.2.0.58 
Date: Mon, 08 May 2000 12:18:36 +0100
To: Markku-Juhani Saarinen <mjos@cc.jyu.fi>
From: RJ Atkinson <rja@inet.org>
Subject: Re: Additional Diffie-Hellman key exchange method
Cc: ietf-ssh@clinet.fi
In-Reply-To: <Pine.GSO.4.10.10005081618340.11046-100000@tukki>
References: <CA2568D9.0041A9B6.00@d73mta05.au.ibm.com>
Mime-Version: 1.0
Content-Type: text/plain; charset="us-ascii"; format=flowed
Sender: owner-ietf-ssh@clinet.fi
Precedence: bulk
Content-Length: 564
Lines: 15

At 14:36 08-05-00 , Markku-Juhani Saarinen wrote:
>If not, the protocol already has this capability: simply define
>diffie-hellman-mygroup2-sha1 (or whatever) that your client and server
>knows about. The rest is an implementation issue.

That approach would not be interoperable.  Defining a standard method
for negotiating the values would be interoperable and hence preferable.
Private extensions, while sometimes good for vendors, are not good
for users (in comparison with having a multi-implementation standard
approach to a given problem).

All IMHO.

Ran

From owner-ietf-ssh@clinet.fi  Mon May  8 17:45:55 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 RAA11530
	for <msfriedl@cip.informatik.uni-erlangen.de>; Mon, 8 May 2000 17:45:54 +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 RAA20343
	for <Markus.Friedl@informatik.uni-erlangen.de>; Mon, 8 May 2000 17:45:53 +0200 (MET DST)
Received: (from majordom@localhost)
	by mail.clinet.fi (8.9.3/8.9.3) id QAA09586
	for ietf-ssh-outgoing; Mon, 8 May 2000 16:36:32 +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 QAA09473;
	Mon, 8 May 2000 16:36:01 +0300
Received: from localhost (mjos@localhost)
	by tukki.cc.jyu.fi (8.9.3/8.9.3/antispam3) with ESMTP id QAA24228;
	Mon, 8 May 2000 16:36:01 +0300 (EET DST)
Date: Mon, 8 May 2000 16:36:01 +0300 (EET DST)
From: Markku-Juhani Saarinen <mjos@cc.jyu.fi>
X-Sender: mjos@tukki
To: owner-ietf-ssh@clinet.fi
cc: ietf-ssh@clinet.fi
Subject: Re: Additional Diffie-Hellman key exchange method
In-Reply-To: <CA2568D9.0041A9B6.00@d73mta05.au.ibm.com>
Message-ID: <Pine.GSO.4.10.10005081618340.11046-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: 1252
Lines: 28


> For this reason, we believe that it should be recommended to the SSH
> IETF working group that the current key exchange algorithm,
> diffie-hellman-group1-sha1, be supplemented by another standard key
> exchange algorithm that allows the p and g values to be
> negotiated. Although it might be advisable to provide a list of
> recommended strong values in the specification (or elsewhere), the
> recommended algorithm should allow the client and server to negotiate
> a pair of mutually acceptable values independent of said list. 

Are you proposing a protocol extension that can negotiate a modp group
that is a priori unknown to one party ?

If so, note that it is computationally expensive to determine if any (p,
g) pair is strong or not. Even with full factorization of p-1 one
needs to do several exponentations and primality testing in order
to determine that a given group is reasonably safe. This negotiation could
take minutes and might be used in DoS attacks.

If not, the protocol already has this capability: simply define
diffie-hellman-mygroup2-sha1 (or whatever) that your client and server
knows about. The rest is an implementation issue.

Cheers,
- mj

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

From owner-ietf-ssh@clinet.fi  Fri May 19 18:10: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 faui01.informatik.uni-erlangen.de (8.8.8/8.1.16-FAU) with ESMTP id SAA25237
	for <msfriedl@cip.informatik.uni-erlangen.de>; Fri, 19 May 2000 18:10: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 SAA03809
	for <Markus.Friedl@informatik.uni-erlangen.de>; Fri, 19 May 2000 18:10:20 +0200 (MET DST)
Received: (from majordom@localhost)
	by mail.clinet.fi (8.9.3/8.9.3) id QAA16151
	for ietf-ssh-outgoing; Fri, 19 May 2000 16:58:04 +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 QAA16145
	for <ietf-ssh@clinet.fi>; Fri, 19 May 2000 16:58:01 +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 PAA14737;
	Fri, 19 May 2000 15:51:47 +0200 (MET DST)
Received: (from nisse@localhost)
	by sture.lysator.liu.se (8.9.0/8.8.7) id PAA14936;
	Fri, 19 May 2000 15:57:49 +0200 (MET DST)
To: Tero Kivinen <kivinen@niksula.hut.fi>
Cc: RJ Atkinson <rja@inet.org>, Markku-Juhani Saarinen <mjos@cc.jyu.fi>,
        ietf-ssh@clinet.fi
Subject: Re: Additional Diffie-Hellman key exchange method
References: <CA2568D9.0041A9B6.00@d73mta05.au.ibm.com> <4.2.0.58.20000508121720.0098ed10@avarice.inner.net> <nnr9bbewqr.fsf@sture.lysator.liu.se> <14616.30693.474326.913082@hutcs.cs.hut.fi>
From: nisse@lysator.liu.se (Niels Mller)
Date: 19 May 2000 15:57:49 +0200
In-Reply-To: Tero Kivinen's message of "Tue,  9 May 2000 23:56:09 +0300 (EET DST)"
Message-ID: <nnvh0ak5gi.fsf@sture.lysator.liu.se>
X-Mailer: Gnus v5.7/Emacs 20.5
Sender: owner-ietf-ssh@clinet.fi
Precedence: bulk
Content-Length: 898
Lines: 18

Tero Kivinen <kivinen@niksula.hut.fi> writes:

> Would people be satisified if we just define more groups as a separate
> internet draft? At least then people can change to new group if they
> think that the old group has been analyzed too much. You have to also
> remember that the current group in the SSH is also used in the IPsec
> protocol, and perhaps in the other protocols too. In IPsec protocol
> there is a way to negotiate private group with the other party, but
> there exists very few implementations of that feature.

To me, it seems like a good thing to have a specification of few of
well known groups, believed to be suitable for cryptographic purposes.
One might also consider adding some groups that are not simply
subgroups of Z/(q), say some ECC-based group. Preferably, such an
internet draft should also list the methods or criteria behind the
choice of each groups.

/Niels
From owner-ietf-ssh@clinet.fi  Fri May 19 23:23: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 XAA11315
	for <msfriedl@cip.informatik.uni-erlangen.de>; Fri, 19 May 2000 23:23: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 XAA23316
	for <Markus.Friedl@informatik.uni-erlangen.de>; Fri, 19 May 2000 23:23:04 +0200 (MET DST)
Received: (from majordom@localhost)
	by mail.clinet.fi (8.9.3/8.9.3) id WAA08388
	for ietf-ssh-outgoing; Fri, 19 May 2000 22:26:05 +0300
Message-Id: <200005191926.WAA08388@mail.clinet.fi>
Received: from citi.umich.edu (citi.umich.edu [141.211.92.141])
	by mail.clinet.fi (8.9.3/8.9.3) with SMTP id WAA08383
	for <ietf-ssh@clinet.fi>; Fri, 19 May 2000 22:26:02 +0300
Received: from citi.umich.edu [141.211.92.147] by citi.umich.edu for nisse@lysator.liu.se kivinen@niksula.hut.fi rja@inet.org mjos@cc.jyu.fi ietf-ssh@clinet.fi with SMTP; Fri, 19 May 00 15:25:06 -0400
From: Niels Provos <provos@citi.umich.edu>
To: nisse@lysator.liu.se (Niels M ller)
Cc: Tero Kivinen <kivinen@niksula.hut.fi>, RJ Atkinson <rja@inet.org>,
        Markku-Juhani Saarinen <mjos@cc.jyu.fi>, ietf-ssh@clinet.fi
Date: Fri, 19 May 2000 15:25:05 -0400
Subject: Re: Additional Diffie-Hellman key exchange method 
In-Reply-To: Niels M ller, 19 May 2000 15:57:49 +0200
Sender: owner-ietf-ssh@clinet.fi
Precedence: bulk
Content-Length: 991
Lines: 21

In message <nnvh0ak5gi.fsf@sture.lysator.liu.se>, Niels M ller writes:
>Tero Kivinen <kivinen@niksula.hut.fi> writes:
>
>> Would people be satisified if we just define more groups as a separate
>> internet draft? At least then people can change to new group if they
>> think that the old group has been analyzed too much. You have to also
>> remember that the current group in the SSH is also used in the IPsec
>> protocol, and perhaps in the other protocols too. In IPsec protocol
>> there is a way to negotiate private group with the other party, but
>> there exists very few implementations of that feature.
>
>To me, it seems like a good thing to have a specification of few of
>well known groups, believed to be suitable for cryptographic purposes.
>One might also consider adding some groups that are not simply
>subgroups of Z/(q), say some ECC-based group. Preferably, such an
>internet draft should also list the methods or criteria behind the
>choice of each groups.
>
>/Niels
>
>
From owner-ietf-ssh@clinet.fi  Sun May 21 21:26: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 VAA03704
	for <msfriedl@cip.informatik.uni-erlangen.de>; Sun, 21 May 2000 21:26:12 +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 VAA25620
	for <Markus.Friedl@informatik.uni-erlangen.de>; Sun, 21 May 2000 21:26:11 +0200 (MET DST)
Received: (from majordom@localhost)
	by mail.clinet.fi (8.9.3/8.9.3) id SAA27722
	for ietf-ssh-outgoing; Sun, 21 May 2000 18:42:51 +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 SAA27719
	for <ietf-ssh@clinet.fi>; Sun, 21 May 2000 18:42:50 +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 RAA14694;
	Sun, 21 May 2000 17:35:34 +0200 (MET DST)
Received: (from nisse@localhost)
	by sture.lysator.liu.se (8.9.0/8.8.7) id RAA19256;
	Sun, 21 May 2000 17:41:51 +0200 (MET DST)
To: Niels Provos <provos@citi.umich.edu>
Cc: Tero Kivinen <kivinen@niksula.hut.fi>, RJ Atkinson <rja@inet.org>,
        Markku-Juhani Saarinen <mjos@cc.jyu.fi>, ietf-ssh@clinet.fi,
        William Allen Simpson <wsimpson@greendragon.com>,
        Markus.Friedl@informatik.uni-erlangen.de
Subject: Re: Additional Diffie-Hellman key exchange method
References: <200005191917.VAA09534@samantha.lysator.liu.se>
From: nisse@lysator.liu.se (Niels Mller)
Date: 21 May 2000 17:41:51 +0200
In-Reply-To: Niels Provos's message of "Fri, 19 May 2000 15:22:55 -0400"
Message-ID: <nnn1ljkj0g.fsf@sture.lysator.liu.se>
X-Mailer: Gnus v5.7/Emacs 20.5
Sender: owner-ietf-ssh@clinet.fi
Precedence: bulk
Content-Length: 1764
Lines: 36

Niels Provos <provos@citi.umich.edu> writes:

> We need to think for the future.  While having a few known groups is a
> good thing, it is desirable to be able to change the groups without
> having to recompile or reconfigure the ssh servers and clients.

How do you expect this flexibility to be used? Do you see servers and
clients being preconfigured with a set of groups they are willing to
use, or do you expect them to check that proposed groups are
reasonable at run time? As you say that no reconfiguration should be
required, I guess you mean that servers and clients should have the
ability to test the cryptographic quality of a group that is proposed
by the remote end.

>From a first look at the draft, I don't see any mechanism to make
quality assurance of the groups easy. I'm thinking of things like
generating groups by a known algorithm and a seed, and telling the
other end which seed, prime witnesses etc was used, so that it can
verify that the generation algorithm was done right.

One more scenario that might be worth thinking about: Say that for
some reason, I don't want to add group quality testing to my server or
client. On the other hand, I might want to configure it to use any
group the definition of which is certified by a trustworthy third
party.

To me, adding group negotiation and quality testing seems like a lot
of extra complexity (which in itself is a bad thing for any security
related program), for quite a small gain. The alternative I'm
comparing with is having a list of known groups (which could be
expanded with time). Changing group preferences would require
reconfiguration, and adding completely new groups would be either
require a recomplie, or editing of some configuration file listing
known groups.

/Niels
From owner-ietf-ssh@clinet.fi  Mon May 22 00:30: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 AAA09278
	for <msfriedl@cip.informatik.uni-erlangen.de>; Mon, 22 May 2000 00:30: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 AAA03256
	for <Markus.Friedl@informatik.uni-erlangen.de>; Mon, 22 May 2000 00:30:08 +0200 (MET DST)
Received: (from majordom@localhost)
	by mail.clinet.fi (8.9.3/8.9.3) id XAA10941
	for ietf-ssh-outgoing; Sun, 21 May 2000 23:30:01 +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 XAA10936
	for <ietf-ssh@clinet.fi>; Sun, 21 May 2000 23:30:00 +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 WAA07968;
	Sun, 21 May 2000 22:20:16 +0200 (MET DST)
Received: (from nisse@localhost)
	by sture.lysator.liu.se (8.9.0/8.8.7) id WAA22711;
	Sun, 21 May 2000 22:26:35 +0200 (MET DST)
To: ietf-ssh@clinet.fi, psst@net.lut.ac.uk
Cc: Sami Lehtinen <sjl@iki.fi>,
        Markus Friedl <msfriedl@cip.informatik.uni-erlangen.de>
Subject: ssh-dss signatures
From: nisse@lysator.liu.se (Niels Mller)
Date: 21 May 2000 22:26:35 +0200
Message-ID: <nnzopjir9g.fsf@sture.lysator.liu.se>
X-Mailer: Gnus v5.7/Emacs 20.5
Sender: owner-ietf-ssh@clinet.fi
Precedence: bulk
Content-Length: 2408
Lines: 75

Hi,

Sami Lehtinen notified me of a bug in LSH's implementation of ssh-dss
signatures. As I would like to have my interpretation of the spec
confirmed, and as I suspect that also openssh may have the same
problem (as it manages to interoperate with LSH), I'm writing to the
WG list.

The transport draft, draft-ietf-secsh-transport-07.txt, defines an
ssh-dss signature as

  uint32    length
  string    "ssh-dss"
  string    dss_signature_blob

The problem is the first field, which LSH omits. The signature is used
for instance inside the SSH_MSG_KEXDH_REPLY message,

  byte      SSH_MSG_KEXDH_REPLY
  string    server public host key and certificates (K_S)
  mpint     f
  string    signature of H

In LSH, this message looks something like this:

  SSH_MSG_KEXDH_REPLY (byte)
  length of host key  (uint32)
  host key data (byte array)
  length of f
  digits of f
* length of signature (i.e. all below) 
  7 (length of "ssh-dss")
  "ssh-dss" (7 bytes)
  length of signature blob (usually 40, and always even)
  r digits (usually 20 bytes)
  s digits (usually 20 bytes, but always the same length as for r)

It seems that the spec requires yet another length field at *, i.e.

  SSH_MSG_KEXDH_REPLY (byte)
  length of host key  (uint32)
  host key data (byte array)
  length of f
  digits of f
* length of all below (part of the "string    signature of H")
* length of signature (now considered part of the signature itself) 
  7 (length of "ssh-dss")
  "ssh-dss" (7 bytes)
  length of signature blob (usually 40, and always even)
  r digits (usually 20 bytes)
  s digits (usually 20 bytes, but always the same length as for r)

The extra length field is totally redundant here (and I believe it is
equally redundant in all other places where an ssh-dss signature is
used). I'm about to add it in LSH now, in order to comply with the
draft, but I would also like the WG to give some consideration to
removing the redundant length field in the definition of the ssh-dss
signature.

The practical impact of changing this in LSH is

  Compatibility with earlier LSH: spki-style signatures might work,
  but ssh-dss is broken.

  Compatibility with earlier ssh2: Not affected, as older ssh2 doesn't
  use the specified format at all.

  Compatibility with next version of ssh2: Should work fine, if only
  LSH's bug-compatibility is disabled.

  Compatibility with current openssh: Broken.

Regards,
/Niels

From owner-ietf-ssh@clinet.fi  Mon May 22 02:10:03 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 CAA11873
	for <msfriedl@cip.informatik.uni-erlangen.de>; Mon, 22 May 2000 02:10:03 +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 CAA06533
	for <Markus.Friedl@informatik.uni-erlangen.de>; Mon, 22 May 2000 02:10:02 +0200 (MET DST)
Received: (from majordom@localhost)
	by mail.clinet.fi (8.9.3/8.9.3) id BAA16124
	for ietf-ssh-outgoing; Mon, 22 May 2000 01:16:12 +0300
Received: from folly.informatik.uni-erlangen.de (IDENT:postfix@nbgdi6-212-144-224-019.arcor-ip.net [212.144.224.19])
	by mail.clinet.fi (8.9.3/8.9.3) with ESMTP id BAA16120
	for <ietf-ssh@clinet.fi>; Mon, 22 May 2000 01:16:06 +0300
Received: by folly.informatik.uni-erlangen.de (Postfix, from userid 31451)
	id 901DC107F; Mon, 22 May 2000 00:13:42 +0200 (CEST)
Date: Mon, 22 May 2000 00:13:41 +0200
From: Markus Friedl <markus.friedl@informatik.uni-erlangen.de>
To: =?iso-8859-1?Q?Niels_M=F6ller?= <nisse@lysator.liu.se>
Cc: ietf-ssh@clinet.fi, psst@net.lut.ac.uk, Sami Lehtinen <sjl@iki.fi>,
        niels@openbsd.org, deraadt@openbsd.org
Subject: Re: ssh-dss signatures
Message-ID: <20000522001341.A360@folly.informatik.uni-erlangen.de>
References: <nnzopjir9g.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.0.1i
In-Reply-To: <nnzopjir9g.fsf@sture.lysator.liu.se>; from nisse@lysator.liu.se on Sun, May 21, 2000 at 10:26:35PM +0200
Sender: owner-ietf-ssh@clinet.fi
Precedence: bulk
Content-Length: 3694
Lines: 104

Hello,

On Sun, May 21, 2000 at 10:26:35PM +0200, Niels Mller wrote:
> Sami Lehtinen notified me of a bug in LSH's implementation of ssh-dss
> signatures. As I would like to have my interpretation of the spec
> confirmed, and as I suspect that also openssh may have the same
> problem (as it manages to interoperate with LSH), I'm writing to the
> WG list.
> 
> The transport draft, draft-ietf-secsh-transport-07.txt, defines an
> ssh-dss signature as
> 
>   uint32    length
>   string    "ssh-dss"
>   string    dss_signature_blob

The first field is omitted by OpenSSH as well as by SecureCRT
and from my experiments with other implementations of SSH2
it seems that ssh-2.1.0 and ssh-2.0.13 both omit everything but
	 dss_signature_blob
not even the size of the dss_signature_blob is included.

IMHO, the redundant field
	uint32    length
seems inconsistent with the overall design of all other
parts of the SSH2 specification so I would strongly support
the change of the signature specification to

	string    "ssh-dss"
	string    dss_signature_blob

Moreover, from reading the drafts now again it seems to me that the
above mentioned (redundant) uint32 length is identical to the uint32
length field from the "string signature of H".

Similar to this is the definition for "ssh-dss" from the same
transport draft:

	uint32    length
	string    "ssh-dss"
	mpint     p
	mpint     q
	mpint     g
	mpint     y

In all implementations that I could test (ssh-2.1.0, ssh-2.0.13,
lsh, SecureCRT, OpenSSH) the specified (redundant) length field is
_never_ sent across the wire.  e.g., in SSH_MSG_KEXDH_REPLY length
field from the string
	string    K_S, the host key
is again identical to the length field from the "ssh-dss" definition.

> The problem is the first field, which LSH omits. The signature is used
> for instance inside the SSH_MSG_KEXDH_REPLY message,
> 
>   byte      SSH_MSG_KEXDH_REPLY
>   string    server public host key and certificates (K_S)
>   mpint     f
>   string    signature of H
> 
> In LSH, this message looks something like this:
> 
>   SSH_MSG_KEXDH_REPLY (byte)
>   length of host key  (uint32)
>   host key data (byte array)
>   length of f
>   digits of f
> * length of signature (i.e. all below) 
>   7 (length of "ssh-dss")
>   "ssh-dss" (7 bytes)
>   length of signature blob (usually 40, and always even)
>   r digits (usually 20 bytes)
>   s digits (usually 20 bytes, but always the same length as for r)

This is the same encoding OpenSSH generates and expects.
SecureCRT expects the same format and it seems consistent
with there overall design (there is never a explicit length
field, only 'string'-type data has length fileds).

And again: I would strongly favour the removal of the
redundant length fields from the drafts since:
	1) They are not usefull at all. Why should n bytes of data
	   be encoded as: 
		uint32	n+4
		uint32	n
		n bytes data
	2) There is no public implementation of the drafts that includes
	   the redundant length field so
	3) Requiring the length field breaks all public implementations
	   of the drafts. This would hurt the acceptance of SSH2 much,
	   since it adds yet another layer of incompatibility.

> The extra length field is totally redundant here (and I believe it is
> equally redundant in all other places where an ssh-dss signature is
> used). I'm about to add it in LSH now, in order to comply with the
> draft, but I would also like the WG to give some consideration to
> removing the redundant length field in the definition of the ssh-dss
> signature.

As I said before, I see no reason why the length field is in the
drafts and I even think it refers to the length field from the
string encoding.

-markus
From owner-ietf-ssh@clinet.fi  Mon May 22 03:48:02 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 DAA15069
	for <msfriedl@cip.informatik.uni-erlangen.de>; Mon, 22 May 2000 03:48:02 +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 DAA09522
	for <Markus.Friedl@informatik.uni-erlangen.de>; Mon, 22 May 2000 03:48:01 +0200 (MET DST)
Received: (from majordom@localhost)
	by mail.clinet.fi (8.9.3/8.9.3) id CAA20097
	for ietf-ssh-outgoing; Mon, 22 May 2000 02:48:05 +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 CAA20094
	for <ietf-ssh@clinet.fi>; Mon, 22 May 2000 02:48:04 +0300
Received: (from sjl@localhost)
	by asgard.tky.hut.fi (8.10.0/8.10.0) id e4LNlIB13139;
	Mon, 22 May 2000 02:47:18 +0300
From: Sami Lehtinen <sjl@iki.fi>
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
Message-ID: <14632.30086.270536.229470@asgard.tky.hut.fi>
Date: Mon, 22 May 2000 02:47:18 +0300 (EEST)
To: Markus Friedl <markus.friedl@informatik.uni-erlangen.de>
Cc: =?iso-8859-1?Q?Niels_M=F6ller?= <nisse@lysator.liu.se>, ietf-ssh@clinet.fi,
        psst@net.lut.ac.uk, niels@openbsd.org, deraadt@openbsd.org,
        sjl@ssh.com
Subject: Re: ssh-dss signatures
In-Reply-To: <20000522001341.A360@folly.informatik.uni-erlangen.de>
References: <nnzopjir9g.fsf@sture.lysator.liu.se>
	<20000522001341.A360@folly.informatik.uni-erlangen.de>
X-Mailer: VM 6.72 under 21.1 (patch 9) "Canyonlands" XEmacs Lucid
Sender: owner-ietf-ssh@clinet.fi
Precedence: bulk
Content-Length: 1081
Lines: 28

For some reason, it takes very long for these messages to get to the
list. Moderator asleep ?-)

Markus Friedl writes:
  : And again: I would strongly favour the removal of the
  : redundant length fields from the drafts since:
  : 	1) They are not usefull at all. Why should n bytes of data
  : 	   be encoded as: 
  : 		uint32	n+4
  : 		uint32	n
  : 		n bytes data
  : 	2) There is no public implementation of the drafts that includes
  : 	   the redundant length field so
  : 	3) Requiring the length field breaks all public implementations
  : 	   of the drafts. This would hurt the acceptance of SSH2 much,
  : 	   since it adds yet another layer of incompatibility.

I wholeheartedly agree.

I will remove those unnecessary fields from the draft, and fix our
current implementation (which will be 2.2.0 when it is released) to
comply with these changes.

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  Mon May 22 14:43:57 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 OAA28246
	for <msfriedl@cip.informatik.uni-erlangen.de>; Mon, 22 May 2000 14:43: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 OAA20823
	for <Markus.Friedl@informatik.uni-erlangen.de>; Mon, 22 May 2000 14:43:55 +0200 (MET DST)
Received: (from majordom@localhost)
	by mail.clinet.fi (8.9.3/8.9.3) id NAA01414
	for ietf-ssh-outgoing; Mon, 22 May 2000 13:33:41 +0300
Received: from inner.net (avarice.inner.net [199.33.248.2])
	by mail.clinet.fi (8.9.3/8.9.3) with ESMTP id NAA01372
	for <ietf-ssh@clinet.fi>; Mon, 22 May 2000 13:33:33 +0300
Received: from wasp.inet.org ([216.52.8.30])
	by inner.net (8.7.6/8.9.3) with ESMTP id KAA28750;
	Mon, 22 May 2000 10:27:37 GMT
Message-Id: <4.2.0.58.20000522062938.00965e90@avarice.inner.net>
X-Sender: rja@avarice.inner.net
X-Mailer: QUALCOMM Windows Eudora Pro Version 4.2.0.58 
Date: Mon, 22 May 2000 06:33:25 +0100
To: Markku-Juhani Saarinen <mjos@cc.jyu.fi>
From: RJ Atkinson <rja@inet.org>
Subject: Re: Additional Diffie-Hellman key exchange method
Cc: ietf-ssh@clinet.fi
In-Reply-To: <Pine.GSO.4.10.10005221305490.27438-100000@tukki>
References: <Pine.GSO.4.10.10005221114180.20413-100000@tukki>
Mime-Version: 1.0
Content-Type: text/plain; charset="us-ascii"; format=flowed
Sender: owner-ietf-ssh@clinet.fi
Precedence: bulk
Content-Length: 1701
Lines: 45

At 11:23 22-05-00 , Markku-Juhani Saarinen wrote:

>Bodo,
>
>   Thank you for your comments.
>
>   It is my understanding that the security goal of SSH 2 is
>   that breaking even one session would not be possible with current or
>   foreseeable technology. I'd like to keep it this way.

It is impossible for this group to know whether the currently preferred group
is strong or not.  So your argument is flawed.

>   Should the technology proceed to a point where a 1024-bit strong group
>   can be broken:
>
>   -> our digital signatures are broken
>   -> our symmetric ciphers and hash functions are likely to be broken
>   -> IPSec and many other security protocols are totally broken
>
>   There's also the issue of "cleanness". It is quite easy to perform a
>   formal analysis of the current SSH 2, but it appears that after the
>   proposed modifications _a_lot_less_ can be said about the security
>   of the protocol.

This isn't clear.  A formal analysis was performed (and published in
IEEE SoSP) on IKE, which is MUCH MUCH more complex.

>   But we might considering adding longer "safe" groups and definitely AES
>   into SSH (once we know which algorithm it is).

If this is an IETF working group, which I think it is, then one CAN NOT
unilaterally say no to a reasonable suggestion with support from the working
group.  SSH Communications Security cannot unilaterally specify the SSH2
protocol IF you are claiming to be doing this within the IETF context.

There are a number of people who believe that being able to negotiate groups
is an important feature.  Shutting off discussion, as you seem to be doing,
violates the IETF standards process.

Please back off.

Ran
rja@inet.org

From owner-ietf-ssh@clinet.fi  Mon May 22 12:13:57 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 MAA10896
	for <msfriedl@cip.informatik.uni-erlangen.de>; Mon, 22 May 2000 12:13: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 MAA08238
	for <Markus.Friedl@informatik.uni-erlangen.de>; Mon, 22 May 2000 12:13:50 +0200 (MET DST)
Received: (from majordom@localhost)
	by mail.clinet.fi (8.9.3/8.9.3) id LAA00643
	for ietf-ssh-outgoing; Mon, 22 May 2000 11:02:44 +0300
Received: from cdc-info.cdc.informatik.tu-darmstadt.de ([130.83.23.100])
	by mail.clinet.fi (8.9.3/8.9.3) with ESMTP id LAA09478
	for <ietf-ssh@clinet.fi>; Mon, 22 May 2000 11:00:31 +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 ADB9F2C4D; Mon, 22 May 2000 10:00:35 +0200 (MET DST)
Received: by cdc1.cdc.informatik.tu-darmstadt.de (8.8.8+Sun/SMI-SVR4)
	id KAA18946; Mon, 22 May 2000 10:00:30 +0200 (MET DST)
Date: Mon, 22 May 2000 10:00:29 +0200
From: Bodo Moeller <moeller@cdc.informatik.tu-darmstadt.de>
To: =?iso-8859-1?Q?Niels_M=F6ller?= <nisse@lysator.liu.se>
Cc: Niels Provos <provos@citi.umich.edu>,
        Tero Kivinen <kivinen@niksula.hut.fi>, RJ Atkinson <rja@inet.org>,
        Markku-Juhani Saarinen <mjos@cc.jyu.fi>, ietf-ssh@clinet.fi,
        William Allen Simpson <wsimpson@greendragon.com>,
        Markus.Friedl@informatik.uni-erlangen.de
Subject: Re: Additional Diffie-Hellman key exchange method
Message-ID: <20000522100028.A18938@cdc.informatik.tu-darmstadt.de>
References: <200005191917.VAA09534@samantha.lysator.liu.se> <nnn1ljkj0g.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: <nnn1ljkj0g.fsf@sture.lysator.liu.se>; from nisse@lysator.liu.se on Sun, May 21, 2000 at 05:41:51PM +0200
Sender: owner-ietf-ssh@clinet.fi
Precedence: bulk
Content-Length: 1555
Lines: 30

On Sun, May 21, 2000 at 05:41:51PM +0200, Niels Mller wrote:
> Niels Provos <provos@citi.umich.edu> writes:

>> We need to think for the future.  While having a few known groups is a
>> good thing, it is desirable to be able to change the groups without
>> having to recompile or reconfigure the ssh servers and clients.

> How do you expect this flexibility to be used? Do you see servers and
> clients being preconfigured with a set of groups they are willing to
> use, or do you expect them to check that proposed groups are
> reasonable at run time? As you say that no reconfiguration should be
> required, I guess you mean that servers and clients should have the
> ability to test the cryptographic quality of a group that is proposed
> by the remote end.

If one party provides the DH group, why should the other party test
that group's "quality"?  Sure, they might choose a bad group; but they
might just as well use bad random numbers when generating their
private DH exponent, and there's nothing you can do about this.
Note that host authentication as per section 6 (Diffie-Hellman
Key Exchange) of draft-ietf-secsh-transport-07.txt uses a hash
including both individual DH shares, not just the DH result; so you'd
notice if a MITM substitutes small groups for the original ones.


-- 
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  Mon May 22 13:03:21 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 NAA16615
	for <msfriedl@cip.informatik.uni-erlangen.de>; Mon, 22 May 2000 13:03: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 NAA11865
	for <Markus.Friedl@informatik.uni-erlangen.de>; Mon, 22 May 2000 13:03:14 +0200 (MET DST)
Received: (from majordom@localhost)
	by mail.clinet.fi (8.9.3/8.9.3) id LAA12116
	for ietf-ssh-outgoing; Mon, 22 May 2000 11:51:31 +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 LAA12108
	for <ietf-ssh@clinet.fi>; Mon, 22 May 2000 11:51:28 +0300
Received: from localhost (mjos@localhost)
	by tukki.cc.jyu.fi (8.9.3/8.9.3/antispam3) with ESMTP id LAA27093;
	Mon, 22 May 2000 11:52:01 +0300 (EET DST)
Date: Mon, 22 May 2000 11:52:01 +0300 (EET DST)
From: Markku-Juhani Saarinen <mjos@cc.jyu.fi>
X-Sender: mjos@tukki
To: Bodo Moeller <moeller@cdc.informatik.tu-darmstadt.de>
cc: =?iso-8859-1?Q?Niels_M=F6ller?= <nisse@lysator.liu.se>,
        Niels Provos <provos@citi.umich.edu>,
        Tero Kivinen <kivinen@niksula.hut.fi>, RJ Atkinson <rja@inet.org>,
        ietf-ssh@clinet.fi, William Allen Simpson <wsimpson@greendragon.com>,
        Markus.Friedl@informatik.uni-erlangen.de
Subject: Re: Additional Diffie-Hellman key exchange method
In-Reply-To: <20000522100028.A18938@cdc.informatik.tu-darmstadt.de>
Message-ID: <Pine.GSO.4.10.10005221114180.20413-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: 1816
Lines: 42

On Mon, 22 May 2000, Bodo Moeller wrote:

> If one party provides the DH group, why should the other party test
> that group's "quality"?  Sure, they might choose a bad group; but they
> might just as well use bad random numbers when generating their
> private DH exponent, and there's nothing you can do about this.
> Note that host authentication as per section 6 (Diffie-Hellman
> Key Exchange) of draft-ietf-secsh-transport-07.txt uses a hash
> including both individual DH shares, not just the DH result; so you'd
> notice if a MITM substitutes small groups for the original ones.

Yep, actually this feature was missing from one of the original SSH 2
DH drafts, but a potential attack was discovered during analysis and we
made the hash to cover the DH shares also.

But let me ask some questions:

* Why should either party have the freedom to use bad groups ?

* Someone is logging in using password authentication and proposes a new
  group. My security policy forbids entry without strong encryption.
  How do I know that the connection is secure ?

* How do I protect my server against a denial of service attack
  that makes it do a series of time-consuming exponentiations while
  negotiating the group ?

* What are the actual gains in letting (mostly crypto-clueless) users
  define their own groups ? Are there any real attacks that are countered
  with this measure ? 

* We're using a PKI of some sort. Our CA has a root-DSA key that is used
  for signing certificates. This key has a *fixed* prime p and a generator
  g that defines a group of prime order ~= 2^160. By solving DLP in this
  group we could forge all the certificates that we need to gain access.
  Why should we care about Diffie-Hellman ?

Cheers,
- mj

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

From owner-ietf-ssh@clinet.fi  Mon May 22 13:24:51 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 NAA18990
	for <msfriedl@cip.informatik.uni-erlangen.de>; Mon, 22 May 2000 13:24:50 +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 NAA14001
	for <Markus.Friedl@informatik.uni-erlangen.de>; Mon, 22 May 2000 13:24:48 +0200 (MET DST)
Received: (from majordom@localhost)
	by mail.clinet.fi (8.9.3/8.9.3) id MAA15600
	for ietf-ssh-outgoing; Mon, 22 May 2000 12:08:45 +0300
Received: from samantha.lysator.liu.se (samantha.lysator.liu.se [130.236.254.202])
	by mail.clinet.fi (8.9.3/8.9.3) with ESMTP id MAA15584
	for <ietf-ssh@clinet.fi>; Mon, 22 May 2000 12:08:43 +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 LAA06978;
	Mon, 22 May 2000 11:01:58 +0200 (MET DST)
Received: (from nisse@localhost)
	by sture.lysator.liu.se (8.9.0/8.8.7) id LAA01479;
	Mon, 22 May 2000 11:08:20 +0200 (MET DST)
To: Bodo Moeller <moeller@cdc.informatik.tu-darmstadt.de>
Cc: Niels Provos <provos@citi.umich.edu>,
        Tero Kivinen <kivinen@niksula.hut.fi>, RJ Atkinson <rja@inet.org>,
        Markku-Juhani Saarinen <mjos@cc.jyu.fi>, ietf-ssh@clinet.fi,
        William Allen Simpson <wsimpson@greendragon.com>,
        Markus.Friedl@informatik.uni-erlangen.de
Subject: Re: Additional Diffie-Hellman key exchange method
References: <200005191917.VAA09534@samantha.lysator.liu.se> <nnn1ljkj0g.fsf@sture.lysator.liu.se> <20000522100028.A18938@cdc.informatik.tu-darmstadt.de>
From: nisse@lysator.liu.se (Niels Mller)
Date: 22 May 2000 11:08:20 +0200
In-Reply-To: Bodo Moeller's message of "Mon, 22 May 2000 10:00:29 +0200"
Message-ID: <nnln13hrzv.fsf@sture.lysator.liu.se>
X-Mailer: Gnus v5.7/Emacs 20.5
Sender: owner-ietf-ssh@clinet.fi
Precedence: bulk
Content-Length: 1624
Lines: 32

Bodo Moeller <moeller@cdc.informatik.tu-darmstadt.de> writes:

> If one party provides the DH group, why should the other party test
> that group's "quality"?  Sure, they might choose a bad group; but they
> might just as well use bad random numbers when generating their
> private DH exponent, and there's nothing you can do about this.

Because of conservatism. When the protocol was designed, an underlying
assumption was that the discrete log problem (or more precisely, the
dh problem) is hard for the particular group being used. Relaxing that
assumption later might lead to subtle problems. 

> Note that host authentication as per section 6 (Diffie-Hellman
> Key Exchange) of draft-ietf-secsh-transport-07.txt uses a hash
> including both individual DH shares, not just the DH result; so you'd
> notice if a MITM substitutes small groups for the original ones.

That's good, and it stops the attacks I can think of, but I don't
claim to be a good at cryptanalysis. Nevertheless, I feel uneasy about
relaxing the requirement on the group. There may be other scenarios
(say, some one-time tweaking of the configuration or software, that
does not imply a complete break) where accepting a group without
quality testing can help the attacker.

One more detail: I'd prefer that the group parameters were included in
the signature as well, though. SSL takes the approach that all the raw
keyexchange messages are signed at the end. In ssh, we only sign the
"relevant" information from those messages. If I understand you
correctly, the parameters of the proposed and selected groups are not
considered "relevant"?

/Niels
From owner-ietf-ssh@clinet.fi  Mon May 22 14:13: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 OAA25758
	for <msfriedl@cip.informatik.uni-erlangen.de>; Mon, 22 May 2000 14:13: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 OAA18605
	for <Markus.Friedl@informatik.uni-erlangen.de>; Mon, 22 May 2000 14:13:30 +0200 (MET DST)
Received: (from majordom@localhost)
	by mail.clinet.fi (8.9.3/8.9.3) id MAA23004
	for ietf-ssh-outgoing; Mon, 22 May 2000 12:41:50 +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 MAA22995
	for <ietf-ssh@clinet.fi>; Mon, 22 May 2000 12:41:48 +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 AF8482C4D; Mon, 22 May 2000 11:41:48 +0200 (MET DST)
Received: by cdc1.cdc.informatik.tu-darmstadt.de (8.8.8+Sun/SMI-SVR4)
	id LAA19011; Mon, 22 May 2000 11:41:43 +0200 (MET DST)
Date: Mon, 22 May 2000 11:41:42 +0200
From: Bodo Moeller <moeller@cdc.informatik.tu-darmstadt.de>
To: Markku-Juhani Saarinen <mjos@cc.jyu.fi>
Cc: =?iso-8859-1?Q?Niels_M=F6ller?= <nisse@lysator.liu.se>,
        Niels Provos <provos@citi.umich.edu>,
        Tero Kivinen <kivinen@niksula.hut.fi>, RJ Atkinson <rja@inet.org>,
        ietf-ssh@clinet.fi, William Allen Simpson <wsimpson@greendragon.com>,
        Markus.Friedl@informatik.uni-erlangen.de
Subject: Re: Additional Diffie-Hellman key exchange method
Message-ID: <20000522114142.A19000@cdc.informatik.tu-darmstadt.de>
References: <20000522100028.A18938@cdc.informatik.tu-darmstadt.de> <Pine.GSO.4.10.10005221114180.20413-100000@tukki>
Mime-Version: 1.0
Content-Type: text/plain; charset=iso-8859-1
Content-Transfer-Encoding: 8bit
X-Mailer: Mutt 1.0i
In-Reply-To: <Pine.GSO.4.10.10005221114180.20413-100000@tukki>; from mjos@cc.jyu.fi on Mon, May 22, 2000 at 11:52:01AM +0300
Sender: owner-ietf-ssh@clinet.fi
Precedence: bulk
Content-Length: 3976
Lines: 83

On Mon, May 22, 2000 at 11:52:01AM +0300, Markku-Juhani Saarinen wrote:
> On Mon, 22 May 2000, Bodo Moeller wrote:

>> If one party provides the DH group, why should the other party test
>> that group's "quality"?  Sure, they might choose a bad group; but they
>> might just as well use bad random numbers when generating their
>> private DH exponent, and there's nothing you can do about this.
>> Note that host authentication as per section 6 (Diffie-Hellman
>> Key Exchange) of draft-ietf-secsh-transport-07.txt uses a hash
>> including both individual DH shares, not just the DH result; so you'd
>> notice if a MITM substitutes small groups for the original ones.

> Yep, actually this feature was missing from one of the original SSH 2
> DH drafts, but a potential attack was discovered during analysis and we
> made the hash to cover the DH shares also.

Funny.  It seems that about 50 % of all DH-based protocol developments
don't get this right the first time, the same mistake being made
over and over again.

> But let me ask some questions:

> * Why should either party have the freedom to use bad groups ?

It should not, but given that having a "good" group does not guarantee
that DH shares are also "good", the overhead probably is not worth it.
(To allow for relatively efficient validation of DH parameters,
you'd have to restrict DH parameters somewhat -- so one might ask:
Why shouldn't the parties have the freedom to use certain good
groups?)

> * Someone is logging in using password authentication and proposes a new
>   group. My security policy forbids entry without strong encryption.
>   How do I know that the connection is secure ?

You don't, no matter if it's a pre-defined group or not.  If the
client's PRNG is bad, for example, you're lost.  (Also probably
it makes more sense to have the server define the group according
to its needs.  Efficiency may be more of an issue for the server
than for the client because often there will be many clients at
the same server, while each client will connect to only very few
servers.)

> * How do I protect my server against a denial of service attack
>   that makes it do a series of time-consuming exponentiations while
>   negotiating the group ?

If the server defines the group, then this is not an issue at all.  If
the client defines the group, then it's not much of an issue (or no
issue, depending on the implementation) unless the server tries to
"validate" the groups.

> * What are the actual gains in letting (mostly crypto-clueless) users
>   define their own groups ? Are there any real attacks that are countered
>   with this measure ? 

The efficient algorithms for discrete logarithms work by first doing a
lot of pre-computations, which results in tables that can be used to
compute arbitrary logs in the given group relatively efficiently.
If everyone uses the same group, then there is one enormously valuable
target to attack.

As for crypto-cluess users, they won't define their own groups
just as they don't write their one PRNGs.  All this is the client
software's business.

> * We're using a PKI of some sort. Our CA has a root-DSA key that is used
>   for signing certificates. This key has a *fixed* prime p and a generator
>   g that defines a group of prime order ~= 2^160. By solving DLP in this
>   group we could forge all the certificates that we need to gain access.
>   Why should we care about Diffie-Hellman ?

Forward secrecy.  Assume someone records all your connections this
year that use DH.  If they break the standard DH group in five years,
they will be able to decrypt everything.  If you use different groups,
then breaking one group will give them access to only a couple
of connections.

-- 
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  Mon May 22 14:27:53 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 OAA27009
	for <msfriedl@cip.informatik.uni-erlangen.de>; Mon, 22 May 2000 14:27:53 +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 OAA19656
	for <Markus.Friedl@informatik.uni-erlangen.de>; Mon, 22 May 2000 14:27:51 +0200 (MET DST)
Received: (from majordom@localhost)
	by mail.clinet.fi (8.9.3/8.9.3) id MAA26720
	for ietf-ssh-outgoing; Mon, 22 May 2000 12:59:14 +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 MAA26696
	for <ietf-ssh@clinet.fi>; Mon, 22 May 2000 12:59:05 +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 77D9E2C4D; Mon, 22 May 2000 11:59:04 +0200 (MET DST)
Received: by cdc1.cdc.informatik.tu-darmstadt.de (8.8.8+Sun/SMI-SVR4)
	id LAA19019; Mon, 22 May 2000 11:58:59 +0200 (MET DST)
Date: Mon, 22 May 2000 11:58:58 +0200
From: Bodo Moeller <moeller@cdc.informatik.tu-darmstadt.de>
To: =?iso-8859-1?Q?Niels_M=F6ller?= <nisse@lysator.liu.se>
Cc: Niels Provos <provos@citi.umich.edu>,
        Tero Kivinen <kivinen@niksula.hut.fi>, RJ Atkinson <rja@inet.org>,
        Markku-Juhani Saarinen <mjos@cc.jyu.fi>, ietf-ssh@clinet.fi,
        William Allen Simpson <wsimpson@greendragon.com>,
        Markus.Friedl@informatik.uni-erlangen.de
Subject: Re: Additional Diffie-Hellman key exchange method
Message-ID: <20000522115858.B19000@cdc.informatik.tu-darmstadt.de>
References: <200005191917.VAA09534@samantha.lysator.liu.se> <nnn1ljkj0g.fsf@sture.lysator.liu.se> <20000522100028.A18938@cdc.informatik.tu-darmstadt.de> <nnln13hrzv.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: <nnln13hrzv.fsf@sture.lysator.liu.se>; from nisse@lysator.liu.se on Mon, May 22, 2000 at 11:08:20AM +0200
Sender: owner-ietf-ssh@clinet.fi
Precedence: bulk
Content-Length: 2727
Lines: 50

On Mon, May 22, 2000 at 11:08:20AM +0200, Niels Mller wrote:
> Bodo Moeller <moeller@cdc.informatik.tu-darmstadt.de> writes:

>> If one party provides the DH group, why should the other party test
>> that group's "quality"?  Sure, they might choose a bad group; but they
>> might just as well use bad random numbers when generating their
>> private DH exponent, and there's nothing you can do about this.

> Because of conservatism. When the protocol was designed, an underlying
> assumption was that the discrete log problem (or more precisely, the
> dh problem) is hard for the particular group being used. Relaxing that
> assumption later might lead to subtle problems. 

Another aspect of conservatism is that using the same DH group for
everything is a bad idea because the most efficient attacks known now
attack complete groups, not individual logarithms.  Of course one has
to look at all parts of the protocol that now use that DH group --
is there more to it than draft-ietf-secsh-transport-07.txt, section 6?

> One more detail: I'd prefer that the group parameters were included in
> the signature as well, though. SSL takes the approach that all the raw
> keyexchange messages are signed at the end. In ssh, we only sign the
> "relevant" information from those messages. If I understand you
> correctly, the parameters of the proposed and selected groups are not
> considered "relevant"?

They are relevant.  I think, however, that the group used is
implicitly covered in the two party's DH shares -- provided that the
protocol prescribes that it's always the server (or always the client)
that provides the group to be used.  If the protocol is changed,
then definitely the group should be included in that hash, though.

(As an aside, don't assume that the SSL and TLS 1.0 handshake
protocols are sound.  They are not.  The raw key exchange messages are
not signed at the end as you write, rather there's symmetric
authentication over all of the handshake, using a MAC key derived from
the handshake.  A public-key signature is used if the server sends a
ServerKeyExchange message [this message is not used if the client
encrypts directly to the server's RSA key], and this signature does
not cover everything that it should cover: An attacker that can
break 512-bit RSA or 512-bit DH would be able to force full-strength
servers and clients to use weak "export" ciphersuites because the
final authentication relies on the 512-bit key's security.)


-- 
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  Mon May 22 14:37:41 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 OAA27832
	for <msfriedl@cip.informatik.uni-erlangen.de>; Mon, 22 May 2000 14:37: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 OAA20347
	for <Markus.Friedl@informatik.uni-erlangen.de>; Mon, 22 May 2000 14:37:39 +0200 (MET DST)
Received: (from majordom@localhost)
	by mail.clinet.fi (8.9.3/8.9.3) id NAA31983
	for ietf-ssh-outgoing; Mon, 22 May 2000 13:24:47 +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 NAA31978
	for <ietf-ssh@clinet.fi>; Mon, 22 May 2000 13:24:44 +0300
Received: from localhost (mjos@localhost)
	by tukki.cc.jyu.fi (8.9.3/8.9.3/antispam3) with ESMTP id NAA08521;
	Mon, 22 May 2000 13:23:28 +0300 (EET DST)
Date: Mon, 22 May 2000 13:23:28 +0300 (EET DST)
From: Markku-Juhani Saarinen <mjos@cc.jyu.fi>
X-Sender: mjos@tukki
To: Bodo Moeller <moeller@cdc.informatik.tu-darmstadt.de>
cc: =?iso-8859-1?Q?Niels_M=F6ller?= <nisse@lysator.liu.se>,
        Niels Provos <provos@citi.umich.edu>,
        Tero Kivinen <kivinen@niksula.hut.fi>, RJ Atkinson <rja@inet.org>,
        ietf-ssh@clinet.fi, William Allen Simpson <wsimpson@greendragon.com>,
        Markus.Friedl@informatik.uni-erlangen.de
Subject: Re: Additional Diffie-Hellman key exchange method
In-Reply-To: <Pine.GSO.4.10.10005221114180.20413-100000@tukki>
Message-ID: <Pine.GSO.4.10.10005221305490.27438-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: 942
Lines: 29


Bodo,

  Thank you for your comments. 

  It is my understanding that the security goal of SSH 2 is
  that breaking even one session would not be possible with current or
  foreseeable technology. I'd like to keep it this way.

  Should the technology proceed to a point where a 1024-bit strong group
  can be broken:

  -> our digital signatures are broken
  -> our symmetric ciphers and hash functions are likely to be broken
  -> IPSec and many other security protocols are totally broken 

  There's also the issue of "cleanness". It is quite easy to perform a
  formal analysis of the current SSH 2, but it appears that after the
  proposed modifications _a_lot_less_ can be said about the security
  of the protocol. 

  But we might considering adding longer "safe" groups and definitely AES
  into SSH (once we know which algorithm it is).

Cheers,
- mj  

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

From owner-ietf-ssh@clinet.fi  Mon May 22 15:15:50 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 PAA00825
	for <msfriedl@cip.informatik.uni-erlangen.de>; Mon, 22 May 2000 15:15:50 +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 PAA23740
	for <Markus.Friedl@informatik.uni-erlangen.de>; Mon, 22 May 2000 15:15:47 +0200 (MET DST)
Received: (from majordom@localhost)
	by mail.clinet.fi (8.9.3/8.9.3) id OAA07589
	for ietf-ssh-outgoing; Mon, 22 May 2000 14:01:03 +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 OAA07581
	for <ietf-ssh@clinet.fi>; Mon, 22 May 2000 14:01:02 +0300
Received: from localhost (mjos@localhost)
	by tukki.cc.jyu.fi (8.9.3/8.9.3/antispam3) with ESMTP id OAA13083;
	Mon, 22 May 2000 14:00:58 +0300 (EET DST)
Date: Mon, 22 May 2000 14:00:57 +0300 (EET DST)
From: Markku-Juhani Saarinen <mjos@cc.jyu.fi>
X-Sender: mjos@tukki
To: RJ Atkinson <rja@inet.org>
cc: ietf-ssh@clinet.fi
Subject: Re: Additional Diffie-Hellman key exchange method
In-Reply-To: <4.2.0.58.20000522062938.00965e90@avarice.inner.net>
Message-ID: <Pine.GSO.4.10.10005221338140.27438-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: 2480
Lines: 59

> It is impossible for this group to know whether the currently preferred group
> is strong or not.  So your argument is flawed.

It is resistant to all of the attacks that the scientific community knows
about and that is the best we can do. But let's not go further into that
discussion.

I wrote:
> >   There's also the issue of "cleanness". It is quite easy to perform a
> >   formal analysis of the current SSH 2, but it appears that after the
> >   proposed modifications _a_lot_less_ can be said about the security
> >   of the protocol.

RJ Atkinson:
> This isn't clear.  A formal analysis was performed (and published in
> IEEE SoSP) on IKE, which is MUCH MUCH more complex.

As I said, a formal analysis can be performed but it will not give 
as much useful results.

But let me quote Schneier and Ferguson, "A Cryptographic Evaluation of
IPSec" (http://www.counterpane.com/ipsec.html):

 "Our main criticism of IPsec is its complexity. IPsec contains too many
  options and too much exibility; there are often several ways of doing
  the same or similar ect. Committees are notorious for adding
  features, options, and additional flexibility to satisfy various
  factions within the committee. As we all know, this additional
  complexity and bloat is seriously detrimental to a normal (functional)
  standard. However, it has a devastating effect on a security standard."

(and in the conclusions section:)

 "What worries us more than the weaknesses we have identied is the 
  complexity of the system. In our opinion, current evaluation methods
  cannot handle systems of such a high complexity, and current
  implementation methods are not capable of creating a secure
  implementation of a system as complex as this."
  
> >   But we might considering adding longer "safe" groups and definitely AES
> >   into SSH (once we know which algorithm it is).
> If this is an IETF working group, which I think it is, then one CAN NOT
> unilaterally say no to a reasonable suggestion with support from the working
> group.  SSH Communications Security cannot unilaterally specify the SSH2
> protocol IF you are claiming to be doing this within the IETF context.

FYI: I have not been working for SSH Communications Security since beginning 
of 1999. SSH 2 is only of scientific interest to me. I can speak for
myself only.

I apologise to SSH if there has been any confusion about this.

- mj

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




From owner-ietf-ssh@clinet.fi  Mon May 22 15:48: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 PAA04401
	for <msfriedl@cip.informatik.uni-erlangen.de>; Mon, 22 May 2000 15:48: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 PAA26398
	for <Markus.Friedl@informatik.uni-erlangen.de>; Mon, 22 May 2000 15:48:55 +0200 (MET DST)
Received: (from majordom@localhost)
	by mail.clinet.fi (8.9.3/8.9.3) id OAA15048
	for ietf-ssh-outgoing; Mon, 22 May 2000 14:35:22 +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 OAA15041
	for <ietf-ssh@clinet.fi>; Mon, 22 May 2000 14:35:21 +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 NAA21152;
	Mon, 22 May 2000 13:28:37 +0200 (MET DST)
Received: (from nisse@localhost)
	by sture.lysator.liu.se (8.9.0/8.8.7) id NAA03271;
	Mon, 22 May 2000 13:35:00 +0200 (MET DST)
To: Bodo Moeller <moeller@cdc.informatik.tu-darmstadt.de>
Cc: Niels Provos <provos@citi.umich.edu>,
        Tero Kivinen <kivinen@niksula.hut.fi>, RJ Atkinson <rja@inet.org>,
        Markku-Juhani Saarinen <mjos@cc.jyu.fi>, ietf-ssh@clinet.fi,
        William Allen Simpson <wsimpson@greendragon.com>,
        Markus.Friedl@informatik.uni-erlangen.de
Subject: Re: Additional Diffie-Hellman key exchange method
References: <200005191917.VAA09534@samantha.lysator.liu.se> <nnn1ljkj0g.fsf@sture.lysator.liu.se> <20000522100028.A18938@cdc.informatik.tu-darmstadt.de> <nnln13hrzv.fsf@sture.lysator.liu.se> <20000522115858.B19000@cdc.informatik.tu-darmstadt.de>
From: nisse@lysator.liu.se (Niels Mller)
Date: 22 May 2000 13:35:00 +0200
In-Reply-To: Bodo Moeller's message of "Mon, 22 May 2000 11:58:58 +0200"
Message-ID: <nnem6uizrv.fsf@sture.lysator.liu.se>
X-Mailer: Gnus v5.7/Emacs 20.5
Sender: owner-ietf-ssh@clinet.fi
Precedence: bulk
Content-Length: 2679
Lines: 58

Bodo Moeller <moeller@cdc.informatik.tu-darmstadt.de> writes:

> Another aspect of conservatism is that using the same DH group for
> everything is a bad idea because the most efficient attacks known now
> attack complete groups, not individual logarithms.

I agree with this. I'm not primarily comparing the group negotiation
proposal with the current state of affairs, where there is a signel
group that everybody is using. Rather, I'm comparing it with a
situation where we have, say, a dozen of well known groups (and
occasionally add another one, as need arises), and use the usual
keyexchange algorithm negotiation. I.e. there are several groups, but
for a group to be used it must be known in advance by both parties.

> Of course one has to look at all parts of the protocol that now use
> that DH group -- is there more to it than
> draft-ietf-secsh-transport-07.txt, section 6?

I don't know. Perhaps looking up the referense for that group,

[Orm96] Orman, H., "The Oakley Key Determination Protocol", version 1,
TR97-92, Department of Computer Science Technical Report, University of
Arizona.

might provide some information? 

> They are relevant.  I think, however, that the group used is
> implicitly covered in the two party's DH shares -- provided that the
> protocol prescribes that it's always the server (or always the client)
> that provides the group to be used.  If the protocol is changed,
> then definitely the group should be included in that hash, though.

I think the parameters for the groups that were proposed, but *not*
selected, should also be authenticated is some way. Hmm, on second
reading the proposed addition seems do get that right:

   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    G_S, the payload of the server's SSH_MSG_KEX_DH_MOD_GROUPS
     string    K_S, the host key
*    uint32    i, chosen group from server proposal
     mpint     e, exchange value sent by the client
     mpint     f, exchange value sent by the server
     mpint     K, the shared secret

> (As an aside, don't assume that the SSL and TLS 1.0 handshake
> protocols are sound.  They are not.  The raw key exchange messages are
> not signed at the end as you write, rather there's symmetric
> authentication over all of the handshake, using a MAC key derived from
> the handshake.

You're right. It's some time since I implemented SSL.

/Niels
From owner-ietf-ssh@clinet.fi  Mon May 22 16:08: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 faui01.informatik.uni-erlangen.de (8.8.8/8.1.16-FAU) with ESMTP id QAA05641
	for <msfriedl@cip.informatik.uni-erlangen.de>; Mon, 22 May 2000 16:08:22 +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 QAA28098
	for <Markus.Friedl@informatik.uni-erlangen.de>; Mon, 22 May 2000 16:08:21 +0200 (MET DST)
Received: (from majordom@localhost)
	by mail.clinet.fi (8.9.3/8.9.3) id OAA19841
	for ietf-ssh-outgoing; Mon, 22 May 2000 14:57:41 +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 OAA19829
	for <ietf-ssh@clinet.fi>; Mon, 22 May 2000 14:57:37 +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 512F62C4D; Mon, 22 May 2000 13:57:41 +0200 (MET DST)
Received: by cdc1.cdc.informatik.tu-darmstadt.de (8.8.8+Sun/SMI-SVR4)
	id NAA19066; Mon, 22 May 2000 13:57:36 +0200 (MET DST)
Date: Mon, 22 May 2000 13:57:35 +0200
From: Bodo Moeller <moeller@cdc.informatik.tu-darmstadt.de>
To: =?iso-8859-1?Q?Niels_M=F6ller?= <nisse@lysator.liu.se>
Cc: Niels Provos <provos@citi.umich.edu>,
        Tero Kivinen <kivinen@niksula.hut.fi>, RJ Atkinson <rja@inet.org>,
        Markku-Juhani Saarinen <mjos@cc.jyu.fi>, ietf-ssh@clinet.fi,
        William Allen Simpson <wsimpson@greendragon.com>,
        Markus.Friedl@informatik.uni-erlangen.de
Subject: Re: Additional Diffie-Hellman key exchange method
Message-ID: <20000522135735.A19033@cdc.informatik.tu-darmstadt.de>
References: <200005191917.VAA09534@samantha.lysator.liu.se> <nnn1ljkj0g.fsf@sture.lysator.liu.se> <20000522100028.A18938@cdc.informatik.tu-darmstadt.de> <nnln13hrzv.fsf@sture.lysator.liu.se> <20000522115858.B19000@cdc.informatik.tu-darmstadt.de> <nnem6uizrv.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: <nnem6uizrv.fsf@sture.lysator.liu.se>; from nisse@lysator.liu.se on Mon, May 22, 2000 at 01:35:00PM +0200
Sender: owner-ietf-ssh@clinet.fi
Precedence: bulk
Content-Length: 2924
Lines: 60

On Mon, May 22, 2000 at 01:35:00PM +0200, Niels Mller wrote:
> Bodo Moeller <moeller@cdc.informatik.tu-darmstadt.de> writes:

>> Another aspect of conservatism is that using the same DH group for
>> everything is a bad idea because the most efficient attacks known now
>> attack complete groups, not individual logarithms.

> I agree with this. I'm not primarily comparing the group negotiation
> proposal with the current state of affairs, where there is a signel
> group that everybody is using. Rather, I'm comparing it with a
> situation where we have, say, a dozen of well known groups (and
> occasionally add another one, as need arises), and use the usual
> keyexchange algorithm negotiation. I.e. there are several groups, but
> for a group to be used it must be known in advance by both parties.

This would still mean that each group gets used for unbounded amounts
of connections.  I.e., cracking one group allows decrypting a
significant amount of encrypted data.  Without pre-defined groups,
the number of groups would be proportional to the number of connections;
we wouldn't put an unlimited number of eggs in each basket.

>> Of course one has to look at all parts of the protocol that now use
>> that DH group -- is there more to it than
>> draft-ietf-secsh-transport-07.txt, section 6?

> I don't know. Perhaps looking up the referense for that group,
> 
> [Orm96] Orman, H., "The Oakley Key Determination Protocol", version 1,
> TR97-92, Department of Computer Science Technical Report, University of
> Arizona.
> 
> might provide some information? 

That's not what I meant.  What I meant is: Does the DH group affect
other parts of the secsh protocol suite, are there other parts of the
protocol suite that depend on certain properties of that group?

>> They are relevant.  I think, however, that the group used is
>> implicitly covered in the two party's DH shares -- provided that the
>> protocol prescribes that it's always the server (or always the client)
>> that provides the group to be used.  If the protocol is changed,
>> then definitely the group should be included in that hash, though.

> I think the parameters for the groups that were proposed, but *not*
> selected, should also be authenticated is some way.

Assuming that you really want to allow multiple groups in the
negotiation.  An easier method to handle things is to just have the
server provide a group, and let the client use it.  Or, if modulus
lengths have to be negotiated, let the client send its preferred key
ength (and possibly lower and upper bounds) first.  I don't know the
secsh protocols in enough detail to tell what approach suites the
needs best.


-- 
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  Mon May 22 16:27:54 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 QAA07101
	for <msfriedl@cip.informatik.uni-erlangen.de>; Mon, 22 May 2000 16:27:54 +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 QAA29804
	for <Markus.Friedl@informatik.uni-erlangen.de>; Mon, 22 May 2000 16:27:52 +0200 (MET DST)
Received: (from majordom@localhost)
	by mail.clinet.fi (8.9.3/8.9.3) id PAA26239
	for ietf-ssh-outgoing; Mon, 22 May 2000 15:25:07 +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 PAA26232
	for <ietf-ssh@clinet.fi>; Mon, 22 May 2000 15:25:05 +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 OAA26319;
	Mon, 22 May 2000 14:18:28 +0200 (MET DST)
Received: (from nisse@localhost)
	by sture.lysator.liu.se (8.9.0/8.8.7) id OAA03853;
	Mon, 22 May 2000 14:24:52 +0200 (MET DST)
To: Bodo Moeller <moeller@cdc.informatik.tu-darmstadt.de>
Cc: Niels Provos <provos@citi.umich.edu>,
        Tero Kivinen <kivinen@niksula.hut.fi>, RJ Atkinson <rja@inet.org>,
        Markku-Juhani Saarinen <mjos@cc.jyu.fi>, ietf-ssh@clinet.fi,
        William Allen Simpson <wsimpson@greendragon.com>,
        Markus.Friedl@informatik.uni-erlangen.de
Subject: Re: Additional Diffie-Hellman key exchange method
References: <200005191917.VAA09534@samantha.lysator.liu.se> <nnn1ljkj0g.fsf@sture.lysator.liu.se> <20000522100028.A18938@cdc.informatik.tu-darmstadt.de> <nnln13hrzv.fsf@sture.lysator.liu.se> <20000522115858.B19000@cdc.informatik.tu-darmstadt.de> <nnem6uizrv.fsf@sture.lysator.liu.se> <20000522135735.A19033@cdc.informatik.tu-darmstadt.de>
From: nisse@lysator.liu.se (Niels Mller)
Date: 22 May 2000 14:24:52 +0200
In-Reply-To: Bodo Moeller's message of "Mon, 22 May 2000 13:57:35 +0200"
Message-ID: <nnbt1yixgr.fsf@sture.lysator.liu.se>
X-Mailer: Gnus v5.7/Emacs 20.5
Sender: owner-ietf-ssh@clinet.fi
Precedence: bulk
Content-Length: 1406
Lines: 30

Bodo Moeller <moeller@cdc.informatik.tu-darmstadt.de> writes:

> This would still mean that each group gets used for unbounded amounts
> of connections.  I.e., cracking one group allows decrypting a
> significant amount of encrypted data.  Without pre-defined groups,
> the number of groups would be proportional to the number of connections;
> we wouldn't put an unlimited number of eggs in each basket.

Ok. That is quite different. I'm not sure if that is the expected use
for the proposed addition. If so, guidelines for generation of the
groups are even more important (as each server would have to lots of
them, at run-time).

> That's not what I meant.  What I meant is: Does the DH group affect
> other parts of the secsh protocol suite, are there other parts of the
> protocol suite that depend on certain properties of that group?

Then the answer is no. It is used only for the dh key exchange.

> Assuming that you really want to allow multiple groups in the
> negotiation.  An easier method to handle things is to just have the
> server provide a group, and let the client use it.

The proposal lets the server offer n groups. I think it makes sense
to say that a server SHOULD include the standard "group1" in the group
list (so that it really works as an extension to the keyexchange
method using that fixed group). If so, then the common case would be
to offer at least two groups.

/Niels
From owner-ietf-ssh@clinet.fi  Mon May 22 16:59:40 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 QAA09958
	for <msfriedl@cip.informatik.uni-erlangen.de>; Mon, 22 May 2000 16:59: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 QAA02848
	for <Markus.Friedl@informatik.uni-erlangen.de>; Mon, 22 May 2000 16:59:34 +0200 (MET DST)
Received: (from majordom@localhost)
	by mail.clinet.fi (8.9.3/8.9.3) id PAA29509
	for ietf-ssh-outgoing; Mon, 22 May 2000 15:38:39 +0300
Received: from max5.rrze.uni-erlangen.de (root@max5.rrze.uni-erlangen.de [131.188.3.50])
	by mail.clinet.fi (8.9.3/8.9.3) with ESMTP id PAA29469
	for <ietf-ssh@clinet.fi>; Mon, 22 May 2000 15:38:33 +0300
Received: from medmax.ivmed.med.uni-erlangen.de by max5.rrze.uni-erlangen.de with ESMTP for ietf-ssh@clinet.fi; Mon, 22 May 2000 14:29:58 +0200
Received: from joe.frauen.med.uni-erlangen.de by medmax.ivmed.med.uni-erlangen.de with ESMTP; Mon, 22 May 2000 14:29:56 +0200
Received: from folly.informatik.uni-erlangen.de (postfix@friedl.frauen.med.uni-erlangen.de [141.67.155.251])
	by joe.frauen.med.uni-erlangen.de (8.8.7/8.8.5/FD) with ESMTP id OAA05492;
	Mon, 22 May 2000 14:29:48 +0200 (CEST)
Received: by folly.informatik.uni-erlangen.de (Postfix, from userid 31451)
	id CAAA1107F; Mon, 22 May 2000 14:29:41 +0200 (CEST)
Date: Mon, 22 May 2000 14:29:41 +0200
From: Markus Friedl <markus.friedl@informatik.uni-erlangen.de>
To: Bodo Moeller <moeller@cdc.informatik.tu-darmstadt.de>
Cc: =?iso-8859-1?Q?Niels_M=F6ller?= <nisse@lysator.liu.se>,
        Niels Provos <provos@citi.umich.edu>,
        Tero Kivinen <kivinen@niksula.hut.fi>, RJ Atkinson <rja@inet.org>,
        Markku-Juhani Saarinen <mjos@cc.jyu.fi>, ietf-ssh@clinet.fi,
        William Allen Simpson <wsimpson@greendragon.com>
Subject: Re: Additional Diffie-Hellman key exchange method
Message-Id: <20000522142941.A19557@folly.informatik.uni-erlangen.de>
References: <200005191917.VAA09534@samantha.lysator.liu.se> <nnn1ljkj0g.fsf@sture.lysator.liu.se> <20000522100028.A18938@cdc.informatik.tu-darmstadt.de> <nnln13hrzv.fsf@sture.lysator.liu.se> <20000522115858.B19000@cdc.informatik.tu-darmstadt.de>
Mime-Version: 1.0
Content-Type: text/plain; charset=us-ascii
X-Mailer: Mutt 1.0.1i
In-Reply-To: <20000522115858.B19000@cdc.informatik.tu-darmstadt.de>; from moeller@cdc.informatik.tu-darmstadt.de on Mon, May 22, 2000 at 11:58:58AM +0200
Sender: owner-ietf-ssh@clinet.fi
Precedence: bulk
Content-Length: 347
Lines: 9

On Mon, May 22, 2000 at 11:58:58AM +0200, Bodo Moeller wrote:
> Of course one has
> to look at all parts of the protocol that now use that DH group --
> is there more to it than draft-ietf-secsh-transport-07.txt, section 6?

no, the DH group is only used in the transport layer
during the session key agreement (and later for re-keying).

-markus
From owner-ietf-ssh@clinet.fi  Mon May 22 17:52: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 RAA13104
	for <msfriedl@cip.informatik.uni-erlangen.de>; Mon, 22 May 2000 17:52:41 +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 RAA08662
	for <Markus.Friedl@informatik.uni-erlangen.de>; Mon, 22 May 2000 17:52:39 +0200 (MET DST)
Received: (from majordom@localhost)
	by mail.clinet.fi (8.9.3/8.9.3) id QAA08672
	for ietf-ssh-outgoing; Mon, 22 May 2000 16:35:10 +0300
Message-Id: <200005221335.QAA08672@mail.clinet.fi>
Received: from citi.umich.edu (citi.umich.edu [141.211.92.141])
	by mail.clinet.fi (8.9.3/8.9.3) with SMTP id QAA08668
	for <ietf-ssh@clinet.fi>; Mon, 22 May 2000 16:35:08 +0300
Received: from citi.umich.edu [141.211.92.147] by citi.umich.edu for moeller@cdc.informatik.tu-darmstadt.de mjos@cc.jyu.fi nisse@lysator.liu.se kivinen@niksula.hut.fi rja@inet.org ietf-ssh@clinet.fi wsimpson@greendragon.com Markus.Friedl@informatik.uni-erlangen.de with SMTP; Mon, 22 May 00 09:34:40 -0400
From: Niels Provos <provos@citi.umich.edu>
To: Bodo Moeller <moeller@cdc.informatik.tu-darmstadt.de>
Cc: Markku-Juhani Saarinen <mjos@cc.jyu.fi>,
        =?iso-8859-1?Q?Niels_M=F6ller?= <nisse@lysator.liu.se>,
        Tero Kivinen <kivinen@niksula.hut.fi>, RJ Atkinson <rja@inet.org>,
        ietf-ssh@clinet.fi, William Allen Simpson <wsimpson@greendragon.com>,
        Markus.Friedl@informatik.uni-erlangen.de
Date: Mon, 22 May 2000 09:34:40 -0400
Subject: Re: Additional Diffie-Hellman key exchange method 
In-Reply-To: Bodo Moeller, Mon, 22 May 2000 11:41:42 +0200
Sender: owner-ietf-ssh@clinet.fi
Precedence: bulk
Content-Length: 868
Lines: 18

In message <20000522114142.A19000@cdc.informatik.tu-darmstadt.de>, Bodo Moeller
 writes:
>> * How do I protect my server against a denial of service attack
>>   that makes it do a series of time-consuming exponentiations while
>>   negotiating the group ?
>If the server defines the group, then this is not an issue at all.  If
>the client defines the group, then it's not much of an issue (or no
>issue, depending on the implementation) unless the server tries to
>"validate" the groups.
As we wrote in the draft, the server offers the groups to the client.
The client can choose from the offered groups.

The idea was that each server can at least generate one safe prime at
installation time.  More safe primes can be generated in the
background.  Something similiar is already done in the v1
implementations.  They generate new RSA keys in the background.

Niels.
From owner-ietf-ssh@clinet.fi  Mon May 22 17:52: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 RAA13113
	for <msfriedl@cip.informatik.uni-erlangen.de>; Mon, 22 May 2000 17:52:44 +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 RAA08669
	for <Markus.Friedl@informatik.uni-erlangen.de>; Mon, 22 May 2000 17:52:42 +0200 (MET DST)
Received: (from majordom@localhost)
	by mail.clinet.fi (8.9.3/8.9.3) id QAA10247
	for ietf-ssh-outgoing; Mon, 22 May 2000 16:43:59 +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 QAA10243
	for <ietf-ssh@clinet.fi>; Mon, 22 May 2000 16:43:58 +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 PAA03176;
	Mon, 22 May 2000 15:37:28 +0200 (MET DST)
Received: (from nisse@localhost)
	by sture.lysator.liu.se (8.9.0/8.8.7) id PAA04947;
	Mon, 22 May 2000 15:43:52 +0200 (MET DST)
To: RJ Atkinson <rja@inet.org>
Cc: Markku-Juhani Saarinen <mjos@cc.jyu.fi>, ietf-ssh@clinet.fi
Subject: Re: Additional Diffie-Hellman key exchange method
References: <Pine.GSO.4.10.10005221114180.20413-100000@tukki> <4.2.0.58.20000522062938.00965e90@avarice.inner.net>
From: nisse@lysator.liu.se (Niels Mller)
Date: 22 May 2000 15:43:52 +0200
In-Reply-To: RJ Atkinson's message of "Mon, 22 May 2000 06:33:25 +0100"
Message-ID: <nn8zx2itt3.fsf@sture.lysator.liu.se>
X-Mailer: Gnus v5.7/Emacs 20.5
Sender: owner-ietf-ssh@clinet.fi
Precedence: bulk
Content-Length: 2590
Lines: 55

RJ Atkinson <rja@inet.org> writes:

> At 11:23 22-05-00 , Markku-Juhani Saarinen wrote:

> >   There's also the issue of "cleanness". It is quite easy to perform a
> >   formal analysis of the current SSH 2, but it appears that after the
> >   proposed modifications _a_lot_less_ can be said about the security
> >   of the protocol.
> 
> This isn't clear.  A formal analysis was performed (and published in
> IEEE SoSP) on IKE, which is MUCH MUCH more complex.

Do you have an URL for that? I haven't read the evaluation, but I seem
to remember Bruce Schneier's comments on it, which was basically
"seems reasonable, but it is too complex to be really comfortable,
signs of design-by-comitteee, etc". I'm not sure how much of that
applies to the IKE part. But simplicity *is* important for security
protocols.
 
> >   But we might considering adding longer "safe" groups and definitely AES
> >   into SSH (once we know which algorithm it is).
> 
> If this is an IETF working group, which I think it is, then one CAN NOT
> unilaterally say no to a reasonable suggestion with support from the working
> group.  SSH Communications Security cannot unilaterally specify the SSH2
> protocol IF you are claiming to be doing this within the IETF context.

I don't think you have to read Markku-Johani that way. As long as the
WG does not decide to make the group negotiation a REQUIRED part of
the protocol, each implementor (including SSH Inc) has the freedom to
decide whether or not to support it. Personally, I'm not yet convinced
that the benefits outweights the added complexity, which means that it
will probably stay quite low on the TODO list for LSH.

Implementations supporting only the current keyexchange method,
implementations supporting additional named groups, and
implementations supporting group negotiation, should be able to
coexist nicely.

> There are a number of people who believe that being able to negotiate groups
> is an important feature.  Shutting off discussion, as you seem to be doing,
> violates the IETF standards process.

I hope nobody is doing that.

I also believe that an important aspect of design is to be able to say
NO to some features, otherwise we get feeping creaturism. And the IETF
process should be able to deal with both positive and negative
decisions. (This last comment should be read on a the meta-discussion
level. It's premature to say definitely that group negotiation is a
feature best avoided, so I don't want to do that. I just want to point
out that rejection is a possible outcome, and that it must be ok to
argue for that).

/Niels
From owner-ietf-ssh@clinet.fi  Mon May 22 18:20:34 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 SAA15453
	for <msfriedl@cip.informatik.uni-erlangen.de>; Mon, 22 May 2000 18:20: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 SAA11117
	for <Markus.Friedl@informatik.uni-erlangen.de>; Mon, 22 May 2000 18:20:33 +0200 (MET DST)
Received: (from majordom@localhost)
	by mail.clinet.fi (8.9.3/8.9.3) id RAA15323
	for ietf-ssh-outgoing; Mon, 22 May 2000 17:11:25 +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 RAA15319
	for <ietf-ssh@clinet.fi>; Mon, 22 May 2000 17:11:24 +0300
Received: from localhost (mjos@localhost)
	by tukki.cc.jyu.fi (8.9.3/8.9.3/antispam3) with ESMTP id RAA04256;
	Mon, 22 May 2000 17:11:22 +0300 (EET DST)
Date: Mon, 22 May 2000 17:11:22 +0300 (EET DST)
From: Markku-Juhani Saarinen <mjos@cc.jyu.fi>
X-Sender: mjos@tukki
To: Niels Provos <provos@citi.umich.edu>
cc: ietf-ssh@clinet.fi
Subject: diffie-hellman: back to basics
In-Reply-To: <200005221329.QAA03731@cc.jyu.fi>
Message-ID: <Pine.GSO.4.10.10005221646320.28459-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: 2492
Lines: 59


> You always use a group generator for the Diffie-Hellman key exchange,
> otherwise you would confine your exchange to a potentially small
> subgroup.

IMO you have it backwards: we want to use subgroup that is large and
has a prime order, because that lets us use smaller exponents. See below.

> The order of the multiplicative group Z^\ast_p is given by \Phi(p), which is 
> p - 1 if p is prime.  The number of keys which can result is \Phi(p - 1).
> That is why we need to choose safe primes, p = 2q + 1 with q prime.

Note that SSH's current group has order (p-1)/2 = q, not p-1 which is
the "entire group". Otherwise one could recover the LSB of the secret
exponent by computing the Legendre / Jacobi symbol. Go ahead and check:
this is what everyone (SSL, TLS, IKE, KEA, etc) is doing nowadays and for
a good reason.

The term "generator" mey be somewhat misleading, but it is often used in
cryptography to actually mean a generator of a subgroup. For example DSA
"generators" create a subgroup of prime order around 2^160.

> "... in the best case (when p is a safe prime), the most probable
> Diffie-Hellman key is only 6 times more likely than the least probable,
> and the key entropy is less than 2 bits shy of the maximum, lg(p-1).

Consider a situation where we are using 256-bit secret exponents (180 bits
is recommended for IKE). This is about four times faster than using
1024-bit exponents and about equally safe:

1) general discrete logarithm would take approximately 2^80 steps
   using the index-calculus method or its number field sieve variant.
   The length of the exponent does not significantly affect the efficiency
   of these "general" DL algorithms.

2) Pollard's distributed Lambda method would require approximately 2^128
   steps to break the short exponent.

-- but if the group order is divisible with factors that are smaller than
2^256, a shortcut is possible by using Pohlig-Hellman reduction combined
with Pollard's Rho or Lambda methods.

> So, as you say, with a generator of 3, two bits of the key can be recovered.
> Those are the two bits we are mssing in the key entropy from above. This
> does not pose a problem.

Yes, but you are doing at least 2 totally redundant modular multiplications.
No entropy is leaked when the group order is prime.

> Yes, I will write a paragraph or two about finding primes and those that
> are safe.

Ok, I'm interested.

Cheers,
- mj

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

From owner-ietf-ssh@clinet.fi  Mon May 22 19:26:13 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 TAA20576
	for <msfriedl@cip.informatik.uni-erlangen.de>; Mon, 22 May 2000 19:26:13 +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 TAA16640
	for <Markus.Friedl@informatik.uni-erlangen.de>; Mon, 22 May 2000 19:26:12 +0200 (MET DST)
Received: (from majordom@localhost)
	by mail.clinet.fi (8.9.3/8.9.3) id SAA21945
	for ietf-ssh-outgoing; Mon, 22 May 2000 18:04:07 +0300
Message-Id: <200005221504.SAA21945@mail.clinet.fi>
Received: from citi.umich.edu (citi.umich.edu [141.211.92.141])
	by mail.clinet.fi (8.9.3/8.9.3) with SMTP id SAA21942
	for <ietf-ssh@clinet.fi>; Mon, 22 May 2000 18:04:06 +0300
Received: from citi.umich.edu [141.211.92.147] by citi.umich.edu for mjos@cc.jyu.fi ietf-ssh@clinet.fi with SMTP; Mon, 22 May 00 11:03:36 -0400
From: Niels Provos <provos@citi.umich.edu>
To: Markku-Juhani Saarinen <mjos@cc.jyu.fi>
Cc: ietf-ssh@clinet.fi
Date: Mon, 22 May 2000 11:03:36 -0400
Subject: Re: diffie-hellman: back to basics 
In-Reply-To: Markku-Juhani Saarinen, Mon, 22 May 2000 17:11:22 +0300
Sender: owner-ietf-ssh@clinet.fi
Precedence: bulk
Content-Length: 1896
Lines: 40

In message <Pine.GSO.4.10.10005221646320.28459-100000@tukki>, Markku-Juhani Saa
rinen writes:
>> The order of the multiplicative group Z^\ast_p is given by \Phi(p), whch is
>> p - 1 if p is prime.  The number of keys which can result is \Phi(p - 1).
>> That is why we need to choose safe primes, p = 2q + 1 with q prime.
>
>Note that SSH's current group has order (p-1)/2 = q, not p-1 which is
>the "entire group". Otherwise one could recover the LSB of the secret
>exponent by computing the Legendre / Jacobi symbol. Go ahead and check:
>this is what everyone (SSL, TLS, IKE, KEA, etc) is doing nowadays and for
>a good reason.
Can you refer me to any publications that recommend not to use the group
generator and safe primes for Diffie-Hellman?

The Pohlig-Hellman decomposition has time complexity bounded by the
largest prime factor of the group order.  For a safe prime, p = 2q +
1, that would be q.  The time complexity is thus the same for both
methods (one where the generator creates the whole group, and the
other where the generator generates only the subgroup with order q).

Furthermore, the analysis given in Oorshot's and Wiener's paper
applies to randomly chosen primes.  If we use safe primes there is no
problem.  In fact, they say in section 4:

The use of safe primes p precludes the attack of Lemma 2 because a
partial Pohlig-Hellman decomposition yields only a single bit of
information about an exponent x.  [...]  It should be emphasized,
however, that when using short exponents, it is not the single very
large prime q that provides protection against Lemma 2, but rather the
total bitlength of smooth factors is k = 1.

So, I conclude there is no problem using short exponents if the prime
is a safe prime.

As I said, I will add a discussion about this to the draft.

 Niels.

Ps.:  The draft apparently never made it to the mailing list.  Should I
try to resend it?
From owner-ietf-ssh@clinet.fi  Mon May 22 19:36:38 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 TAA21289
	for <msfriedl@cip.informatik.uni-erlangen.de>; Mon, 22 May 2000 19:36:37 +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 TAA17060
	for <Markus.Friedl@informatik.uni-erlangen.de>; Mon, 22 May 2000 19:32:24 +0200 (MET DST)
Received: (from majordom@localhost)
	by mail.clinet.fi (8.9.3/8.9.3) id SAA22550
	for ietf-ssh-outgoing; Mon, 22 May 2000 18:10:12 +0300
Message-Id: <200005221510.SAA22550@mail.clinet.fi>
Received: from citi.umich.edu (citi.umich.edu [141.211.92.141])
	by mail.clinet.fi (8.9.3/8.9.3) with SMTP id SAA22545
	for <ietf-ssh@clinet.fi>; Mon, 22 May 2000 18:10:11 +0300
Received: from citi.umich.edu [141.211.92.147] by citi.umich.edu for nisse@lysator.liu.se moeller@cdc.informatik.tu-darmstadt.de kivinen@niksula.hut.fi rja@inet.org mjos@cc.jyu.fi ietf-ssh@clinet.fi wsimpson@greendragon.com Markus.Friedl@informatik.uni-erlangen.de with SMTP; Mon, 22 May 00 11:09:20 -0400
From: Niels Provos <provos@citi.umich.edu>
To: nisse@lysator.liu.se (Niels M ller)
Cc: Bodo Moeller <moeller@cdc.informatik.tu-darmstadt.de>,
        Tero Kivinen <kivinen@niksula.hut.fi>, RJ Atkinson <rja@inet.org>,
        Markku-Juhani Saarinen <mjos@cc.jyu.fi>, ietf-ssh@clinet.fi,
        William Allen Simpson <wsimpson@greendragon.com>,
        Markus.Friedl@informatik.uni-erlangen.de
Date: Mon, 22 May 2000 11:09:20 -0400
Subject: Re: Additional Diffie-Hellman key exchange method 
In-Reply-To: Niels M ller, 22 May 2000 14:24:52 +0200
Sender: owner-ietf-ssh@clinet.fi
Precedence: bulk
Content-Length: 1184
Lines: 22

In message <nnbt1yixgr.fsf@sture.lysator.liu.se>, Niels M ller writes:
>Bodo Moeller <moeller@cdc.informatik.tu-darmstadt.de> writes:
>> This would still mean that each group gets used for unbounded amounts
>> of connections.  I.e., cracking one group allows decrypting a
>> significant amount of encrypted data.  Without pre-defined groups,
>> the number of groups would be proportional to the number of connections;
>> we wouldn't put an unlimited number of eggs in each basket.
>Ok. That is quite different. I'm not sure if that is the expected use
>for the proposed addition. If so, guidelines for generation of the
>groups are even more important (as each server would have to lots of
>them, at run-time).
This is the main idea behind the draft.  You do not want a limited
number of groups.  Servers should be able to generate new groups all
the time and offer them to the clients.  The best scenario would be
where every server has at least one own group.

I posted a few messages to the mailing list that have further
rationale for selecting groups.  The next draft will include
generation guidelines, algorithms and maybe a short C program that
generates safe primes.

Niels.
From owner-ietf-ssh@clinet.fi  Wed May 24 01:26:06 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 BAA29727
	for <msfriedl@cip.informatik.uni-erlangen.de>; Wed, 24 May 2000 01:26:06 +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 BAA00988
	for <Markus.Friedl@informatik.uni-erlangen.de>; Wed, 24 May 2000 01:26:05 +0200 (MET DST)
Received: (from majordom@localhost)
	by mail.clinet.fi (8.9.3/8.9.3) id AAA09035
	for ietf-ssh-outgoing; Wed, 24 May 2000 00:16:52 +0300
Received: from inner.net (avarice.inner.net [199.33.248.2])
	by mail.clinet.fi (8.9.3/8.9.3) with ESMTP id AAA09032
	for <ietf-ssh@clinet.fi>; Wed, 24 May 2000 00:16:51 +0300
Received: from wasp.inet.org ([216.52.8.30])
	by inner.net (8.7.6/8.9.3) with ESMTP id VAA00547
	for <ietf-ssh@clinet.fi>; Tue, 23 May 2000 21:10:00 GMT
Message-Id: <4.2.0.58.20000523170519.0096be50@avarice.inner.net>
X-Sender: rja@avarice.inner.net
X-Mailer: QUALCOMM Windows Eudora Pro Version 4.2.0.58 
Date: Tue, 23 May 2000 17:16:39 +0100
To: ietf-ssh@clinet.fi
From: RJ Atkinson <rja@inet.org>
Subject: Re: Additional Diffie-Hellman key exchange method
In-Reply-To: <20000522114142.A19000@cdc.informatik.tu-darmstadt.de>
References: <Pine.GSO.4.10.10005221114180.20413-100000@tukki>
 <20000522100028.A18938@cdc.informatik.tu-darmstadt.de>
 <Pine.GSO.4.10.10005221114180.20413-100000@tukki>
Mime-Version: 1.0
Content-Type: text/plain; charset="us-ascii"; format=flowed
Sender: owner-ietf-ssh@clinet.fi
Precedence: bulk
Content-Length: 553
Lines: 19

Upon further reflection and some offline education,
I have a modest suggestion.

Perhaps one or more of the folks who think D-H group negotiation
capability is a good idea could write up an Internet-Draft
as draft-ietf-secsh-*.txt and submit it to the I-D folks.
For what its worth, I think this capability is a good idea.

At a minimum, that might help focus the conversation.  It also
would be motion in the direction of getting this formally included
with SSHv2 if/when that goes to being an IETF standard of some
sort.

Regards,

Ran
rja@inet.org


From owner-ietf-ssh@clinet.fi  Wed May 24 18:43:27 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 SAA05866
	for <msfriedl@cip.informatik.uni-erlangen.de>; Wed, 24 May 2000 18:43:27 +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 SAA11579
	for <Markus.Friedl@informatik.uni-erlangen.de>; Wed, 24 May 2000 18:43:26 +0200 (MET DST)
Received: (from majordom@localhost)
	by mail.clinet.fi (8.9.3/8.9.3) id RAA29884
	for ietf-ssh-outgoing; Wed, 24 May 2000 17:29:05 +0300
Message-Id: <200005241429.RAA29884@mail.clinet.fi>
Received: from citi.umich.edu (citi.umich.edu [141.211.92.141])
	by mail.clinet.fi (8.9.3/8.9.3) with SMTP id RAA29878
	for <ietf-ssh@clinet.fi>; Wed, 24 May 2000 17:29:04 +0300
Received: from citi.umich.edu [141.211.92.147] by citi.umich.edu for rja@inet.org ietf-ssh@clinet.fi with SMTP; Wed, 24 May 00 10:28:21 -0400
From: Niels Provos <provos@citi.umich.edu>
To: RJ Atkinson <rja@inet.org>
Cc: ietf-ssh@clinet.fi
Date: Wed, 24 May 2000 10:28:21 -0400
Subject: Re: Additional Diffie-Hellman key exchange method 
In-Reply-To: RJ Atkinson, Tue, 23 May 2000 17:16:39 BST
Sender: owner-ietf-ssh@clinet.fi
Precedence: bulk
Content-Length: 779
Lines: 18

In message <4.2.0.58.20000523170519.0096be50@avarice.inner.net>, RJ Atkinson wr
ites:
>Perhaps one or more of the folks who think D-H group negotiation
>capability is a good idea could write up an Internet-Draft
>as draft-ietf-secsh-*.txt and submit it to the I-D folks.
>For what its worth, I think this capability is a good idea.
Markus Friedl, Bill Simpson and I have written such a draft.  It also
includes the working group feedback from the last couple of days.

Unfortunately, it seems that the mailing list has a size limit, so that
the drafts do not come through.  We are trying to submit the draft as
working group internet-draft now.  In the meanwhile, I put a draft up
at

http://www.citi.umich.edu/u/provos/tmp/dh-group-exchange-x.txt

Comments are welcome,
 Niels.
