From owner-ietf-ssh@clinet.fi Tue Jun 6 20:36:32 2000 Return-Path: Received: from faui45.informatik.uni-erlangen.de (root@faui45.informatik.uni-erlangen.de [131.188.34.45]) by faui01.informatik.uni-erlangen.de (8.8.8/8.1.16-FAU) with ESMTP id UAA01850 for ; Tue, 6 Jun 2000 20:36:32 +0200 (MET DST) Received: from mail.clinet.fi (mail.clinet.fi [194.100.0.7]) by faui45.informatik.uni-erlangen.de (8.9.1/8.1.49-FAU) with ESMTP id UAA04271 for ; Tue, 6 Jun 2000 20:36:30 +0200 (MET DST) Received: (from majordom@localhost) by mail.clinet.fi (8.9.3/8.9.3) id SAA11797 for ietf-ssh-outgoing; Tue, 6 Jun 2000 18:39:17 +0300 Received: from citi.umich.edu (citi.umich.edu [141.211.92.141]) by mail.clinet.fi (8.9.3/8.9.3) with ESMTP id SAA11783 for ; Tue, 6 Jun 2000 18:39:08 +0300 Received: from citi.umich.edu (india.citi.umich.edu [141.211.92.147]) by citi.umich.edu (Postfix) with ESMTP id B75BC207C1 for ; Tue, 6 Jun 2000 11:38:55 -0400 (EDT) From: Niels Provos Subject: Diffie-Hellman Group Exchange To: ietf-ssh@clinet.fi Date: Tue, 06 Jun 2000 11:38:55 -0400 Message-Id: <20000606153855.B75BC207C1@citi.umich.edu> Sender: owner-ietf-ssh@clinet.fi Precedence: bulk Content-Length: 265 Lines: 15 Hi, an internet-draft of the "Diffie-Hellman Group Exchange for the SSH Transport Layer Protocol" is now available as draft-provos-secsh-dh-group-exchange-00.txt Bodo and Markku could you please see if your concerns have been addressed. Greetings, Niels. From owner-ietf-ssh@clinet.fi Tue Jun 6 21:54:44 2000 Return-Path: Received: from faui45.informatik.uni-erlangen.de (root@faui45.informatik.uni-erlangen.de [131.188.34.45]) by faui01.informatik.uni-erlangen.de (8.8.8/8.1.16-FAU) with ESMTP id VAA07901 for ; Tue, 6 Jun 2000 21:54:40 +0200 (MET DST) Received: from mail.clinet.fi (mail.clinet.fi [194.100.0.7]) by faui45.informatik.uni-erlangen.de (8.9.1/8.1.49-FAU) with ESMTP id VAA10327 for ; Tue, 6 Jun 2000 21:54:39 +0200 (MET DST) Received: (from majordom@localhost) by mail.clinet.fi (8.9.3/8.9.3) id UAA23762 for ietf-ssh-outgoing; Tue, 6 Jun 2000 20:28:04 +0300 Received: from ssh.com (fw.hel.fi.ssh.com [193.64.193.124]) by mail.clinet.fi (8.9.3/8.9.3) with ESMTP id UAA23756 for ; Tue, 6 Jun 2000 20:28:03 +0300 Received: from torni.hel.fi.ssh.com (torni.hel.fi.ssh.com [10.1.0.43]) by ssh.com (8.9.3/8.9.3/SSH-1.16) with ESMTP id UAA27256; Tue, 6 Jun 2000 20:28:03 +0300 (EEST) Received: (from mkojo@localhost) by torni.hel.fi.ssh.com (8.9.3/8.9.3/SSH-1.17) id UAA00391; Tue, 6 Jun 2000 20:28:02 +0300 (EET DST) Date: Tue, 6 Jun 2000 20:28:02 +0300 (EET DST) Message-Id: <200006061728.UAA00391@torni.hel.fi.ssh.com> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit From: Mika Kojo To: Niels Provos Cc: ietf-ssh@clinet.fi Subject: Diffie-Hellman Group Exchange In-Reply-To: <20000606153855.B75BC207C1@citi.umich.edu> References: <20000606153855.B75BC207C1@citi.umich.edu> X-Mailer: VM 6.34 under Emacs 19.34.2 Organization: SSH Communications Security, Finland Sender: owner-ietf-ssh@clinet.fi Precedence: bulk Content-Length: 2670 Lines: 69 Hello all, I would like to point out one issue relating to the selection of the Diffie-Hellman group. (My apologies if this has already been discussed here, I joined to this list only very recently.) Let F_q denote the usual finite field of q elements. Then we want to apply Diffie-Hellman over its multiplicative group. If q = p, and g \in F_p, we have g^ord(g) == 1 (in F_p^*), that is, ord(g) | p - 1. Yet the proposal requires that ord(g) = (p-1)/2, and ord(g) to be prime. In Diffie-Hellman, one is interested in computation of g^e (in F_p^*) for e \in (1, c < ord(g)). In practice we usually select c << ord(g) = (p-1)/2, for performance purposes. And indeed there seems to be no known attack which can utilize this iff log c >= B (where B is a security bound for square root attacks) and log p >= I (where I is a security bound for Index calculus). We have B << I for all reasonable selections of p. However, it is clear that the problem of breaking Diffie-Hellman is no longer (if c << ord(g)) the general subgroup discrete logarithm problem. This gives rise to speculation that an attack might be developed which in future requires modification to the bound B. (It seems that e \in (1, (p-1)/2) is claimed in the draft, so my discussion here is perhaps out of place. However, it is likely that implementations wish to choose e \in (1, c << (p-1)/2) for efficiency.) My current opinion (until someone proves me wrong, or too paranoid) is that there should be a possibility for negotiating also ord(g). This would allow the participants to base the difficulty of breaking the D-H on general subgroup discrete logarithm problem, without losing efficiency. (Of course, it is still questionable whether D-H itself is as difficult as general (subgroup) discrete log problem, but questioning D-H difficulty might be too paranoid.) This is perhaps marginal speculation, but I think reasonable when considering e.g. recent problems with IPSec elliptic curves (and the fact that those problems were conjectured years before hand). Of course, if ord(g) << (p-1)/2 then parameter verification may end to be more elaborate than when ord(g) = (p-1)/2. Lastly I must acknowledge that this point is not mine but from a recent sci.crypt discussion, where this was mentioned by Eric Verheul. Best regards, Mika Kojo SSH Communications Security Corp Niels Provos writes: > Hi, > > an internet-draft of the > > "Diffie-Hellman Group Exchange for the SSH Transport Layer Protocol" > > is now available as > > draft-provos-secsh-dh-group-exchange-00.txt > > Bodo and Markku could you please see if your concerns have been > addressed. > > Greetings, > Niels. From owner-ietf-ssh@clinet.fi Wed Jun 7 01:15:58 2000 Return-Path: Received: from faui45.informatik.uni-erlangen.de (root@faui45.informatik.uni-erlangen.de [131.188.34.45]) by faui01.informatik.uni-erlangen.de (8.8.8/8.1.16-FAU) with ESMTP id BAA17892 for ; Wed, 7 Jun 2000 01:15:57 +0200 (MET DST) Received: from mail.clinet.fi (mail.clinet.fi [194.100.0.7]) by faui45.informatik.uni-erlangen.de (8.9.1/8.1.49-FAU) with ESMTP id BAA23226 for ; Wed, 7 Jun 2000 01:15:55 +0200 (MET DST) Received: (from majordom@localhost) by mail.clinet.fi (8.9.3/8.9.3) id XAA12021 for ietf-ssh-outgoing; Tue, 6 Jun 2000 23:52:07 +0300 Received: from citi.umich.edu (citi.umich.edu [141.211.92.141]) by mail.clinet.fi (8.9.3/8.9.3) with ESMTP id XAA12017 for ; Tue, 6 Jun 2000 23:52:05 +0300 Received: from citi.umich.edu (india.citi.umich.edu [141.211.92.147]) by citi.umich.edu (Postfix) with ESMTP id 3E2CD207C1; Tue, 6 Jun 2000 16:52:04 -0400 (EDT) Subject: Re: Diffie-Hellman Group Exchange From: Niels Provos In-Reply-To: Mika Kojo, Tue, 06 Jun 2000 20:28:02 +0300 To: Mika Kojo Cc: ietf-ssh@clinet.fi Date: Tue, 06 Jun 2000 16:52:04 -0400 Message-Id: <20000606205204.3E2CD207C1@citi.umich.edu> Sender: owner-ietf-ssh@clinet.fi Precedence: bulk Content-Length: 1751 Lines: 34 In message <200006061728.UAA00391@torni.hel.fi.ssh.com>, Mika Kojo writes: >Let F_q denote the usual finite field of q elements. Then we want to >apply Diffie-Hellman over its multiplicative group. If q = p, and g >\in F_p, we have g^ord(g) == 1 (in F_p^*), that is, ord(g) | p - >1. Yet the proposal requires that ord(g) = (p-1)/2, and ord(g) to be >prime. The draft actually allows the server to use both type of generators. It can either be for the whole multiplicative group GF(p) with ord(g) = p-1, or for a subgroup of GF(p) with ord(g) = (p-1)/2 and ord(g) prime. This is because the draft only allows safe primes. >In Diffie-Hellman, one is interested in computation of g^e (in F_p^*) >for e \in (1, c < ord(g)). In practice we usually select c << ord(g) = >(p-1)/2, for performance purposes. And indeed there seems to be no >known attack which can utilize this iff log c >= B (where B is a >security bound for square root attacks) and log p >= I (where I is a >security bound for Index calculus). We have B << I for all reasonable >selections of p. The cited paper and the security considerations talk about short exponents: [1] P. C. van Oorschot and M. J. Wiener, On Diffie-Hellman key agreement with short exponents, In Advances in Cryptology - EUROCRYPT'96, LNCS 1070, Springer-Verlag, 1996, pp.332-343. >My current opinion (until someone proves me wrong, or too paranoid) is >that there should be a possibility for negotiating also ord(g). This This doesnt really make sense since there are only two possible orders, either p-1 or (p-1)/2, which are about the size of p. However, if you have wording that explains this issue better, I'd be happy to include it in a future version of the draft. Greetings, Niels. From owner-ietf-ssh@clinet.fi Wed Jun 7 03:49:16 2000 Return-Path: Received: from faui45.informatik.uni-erlangen.de (root@faui45.informatik.uni-erlangen.de [131.188.34.45]) by faui01.informatik.uni-erlangen.de (8.8.8/8.1.16-FAU) with ESMTP id DAA22431 for ; Wed, 7 Jun 2000 03:49:15 +0200 (MET DST) Received: from mail.clinet.fi (mail.clinet.fi [194.100.0.7]) by faui45.informatik.uni-erlangen.de (8.9.1/8.1.49-FAU) with ESMTP id DAA29057 for ; Wed, 7 Jun 2000 03:49:14 +0200 (MET DST) Received: (from majordom@localhost) by mail.clinet.fi (8.9.3/8.9.3) id CAA24158 for ietf-ssh-outgoing; Wed, 7 Jun 2000 02:07:44 +0300 Received: from ssh.com (fw.hel.fi.ssh.com [193.64.193.124]) by mail.clinet.fi (8.9.3/8.9.3) with ESMTP id CAA24153 for ; Wed, 7 Jun 2000 02:07:43 +0300 Received: from torni.hel.fi.ssh.com (torni.hel.fi.ssh.com [10.1.0.43]) by ssh.com (8.9.3/8.9.3/SSH-1.16) with ESMTP id CAA05846; Wed, 7 Jun 2000 02:07:43 +0300 (EEST) Received: (from mkojo@localhost) by torni.hel.fi.ssh.com (8.9.3/8.9.3/SSH-1.17) id CAA21153; Wed, 7 Jun 2000 02:07:43 +0300 (EET DST) Date: Wed, 7 Jun 2000 02:07:43 +0300 (EET DST) Message-Id: <200006062307.CAA21153@torni.hel.fi.ssh.com> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit From: Mika Kojo To: Niels Provos Cc: Mika Kojo , ietf-ssh@clinet.fi Subject: Re: Diffie-Hellman Group Exchange In-Reply-To: <20000606205204.3E2CD207C1@citi.umich.edu> References: <20000606205204.3E2CD207C1@citi.umich.edu> X-Mailer: VM 6.34 under Emacs 19.34.2 Organization: SSH Communications Security, Finland Sender: owner-ietf-ssh@clinet.fi Precedence: bulk Content-Length: 2637 Lines: 61 Niels, my apologies for not being explicit. My point in the previous message was that in the draft the prime p was fixed to be a safe prime (or any pair such that ord(g) ~= p), and it might yield less security at the same efficiency level as when using smaller subgroup (e.g. ord(g) << p). The paper by van Oorschot and Wiener does not claim that the problem with using exponents e << ord(g) to be as strong as e ~= ord(g), in fact they seem to suggest otherwise. However, as the draft indicates you suggest using exponent ~= p. Thus you may lose in efficiency, but also this nullifies the point of my previous message. The practical benefits of fixing p to a safe prime might overweight any (very) theoretical problems. Best regards, Mika Kojo SSH Communications Security Corp Niels Provos writes: > In message <200006061728.UAA00391@torni.hel.fi.ssh.com>, Mika Kojo writes: > >Let F_q denote the usual finite field of q elements. Then we want to > >apply Diffie-Hellman over its multiplicative group. If q = p, and g > >\in F_p, we have g^ord(g) == 1 (in F_p^*), that is, ord(g) | p - > >1. Yet the proposal requires that ord(g) = (p-1)/2, and ord(g) to be > >prime. > The draft actually allows the server to use both type of generators. > It can either be for the whole multiplicative group GF(p) with > ord(g) = p-1, or for a subgroup of GF(p) with ord(g) = (p-1)/2 and > ord(g) prime. This is because the draft only allows safe primes. > > >In Diffie-Hellman, one is interested in computation of g^e (in F_p^*) > >for e \in (1, c < ord(g)). In practice we usually select c << ord(g) = > >(p-1)/2, for performance purposes. And indeed there seems to be no > >known attack which can utilize this iff log c >= B (where B is a > >security bound for square root attacks) and log p >= I (where I is a > >security bound for Index calculus). We have B << I for all reasonable > >selections of p. > The cited paper and the security considerations talk about short > exponents: > > [1] P. C. van Oorschot and M. J. Wiener, On Diffie-Hellman key agreement > with short exponents, In Advances in Cryptology - EUROCRYPT'96, > LNCS 1070, Springer-Verlag, 1996, pp.332-343. > > >My current opinion (until someone proves me wrong, or too paranoid) is > >that there should be a possibility for negotiating also ord(g). This > This doesnt really make sense since there are only two possible orders, > either p-1 or (p-1)/2, which are about the size of p. However, if > you have wording that explains this issue better, I'd be happy to > include it in a future version of the draft. > > Greetings, > Niels. From owner-ietf-ssh@clinet.fi Wed Jun 7 19:12:23 2000 Return-Path: Received: from faui45.informatik.uni-erlangen.de (root@faui45.informatik.uni-erlangen.de [131.188.34.45]) by faui01.informatik.uni-erlangen.de (8.8.8/8.1.16-FAU) with ESMTP id TAA19094 for ; Wed, 7 Jun 2000 19:12:23 +0200 (MET DST) Received: from mail.clinet.fi (mail.clinet.fi [194.100.0.7]) by faui45.informatik.uni-erlangen.de (8.9.1/8.1.49-FAU) with ESMTP id TAA29260 for ; Wed, 7 Jun 2000 19:12:20 +0200 (MET DST) Received: (from majordom@localhost) by mail.clinet.fi (8.9.3/8.9.3) id SAA19259 for ietf-ssh-outgoing; Wed, 7 Jun 2000 18:08:02 +0300 Received: from cdc-info.cdc.informatik.tu-darmstadt.de (cdc-info.cdc.informatik.tu-darmstadt.de [130.83.23.100]) by mail.clinet.fi (8.9.3/8.9.3) with ESMTP id SAA19255 for ; Wed, 7 Jun 2000 18:07:59 +0300 Received: from cdc1.cdc.informatik.tu-darmstadt.de (cdc1 [130.83.23.10]) by cdc-info.cdc.informatik.tu-darmstadt.de (Postfix) with ESMTP id 6DE3E2C4C; Wed, 7 Jun 2000 17:07:49 +0200 (MET DST) Received: by cdc1.cdc.informatik.tu-darmstadt.de (8.8.8+Sun/SMI-SVR4) id RAA00445; Wed, 7 Jun 2000 17:07:48 +0200 (MET DST) Date: Wed, 7 Jun 2000 17:07:47 +0200 From: Bodo Moeller To: Mika Kojo Cc: Niels Provos , ietf-ssh@clinet.fi Subject: Re: Diffie-Hellman Group Exchange Message-ID: <20000607170746.A431@cdc.informatik.tu-darmstadt.de> References: <20000606205204.3E2CD207C1@citi.umich.edu> <200006062307.CAA21153@torni.hel.fi.ssh.com> Mime-Version: 1.0 Content-Type: text/plain; charset=iso-8859-1 Content-Transfer-Encoding: 8bit X-Mailer: Mutt 1.0i In-Reply-To: <200006062307.CAA21153@torni.hel.fi.ssh.com>; from mkojo@ssh.com on Wed, Jun 07, 2000 at 02:07:43AM +0300 Sender: owner-ietf-ssh@clinet.fi Precedence: bulk Content-Length: 9581 Lines: 201 On Wed, Jun 07, 2000 at 02:07:43AM +0300, Mika Kojo wrote: [...] > However, as the draft indicates you suggest using exponent ~= p. Thus > you may lose in efficiency, but also this nullifies the point of my > previous message. > > The practical benefits of fixing p to a safe prime might overweight > any (very) theoretical problems. Requiring safe primes also leads to practical problems; namely, generating them is much slower than generating other usable primes. > Niels Provos: >> The cited paper and the security considerations talk about short >> exponents: >> >> [1] P. C. van Oorschot and M. J. Wiener, On Diffie-Hellman key agreement >> with short exponents, In Advances in Cryptology - EUROCRYPT'96, >> LNCS 1070, Springer-Verlag, 1996, pp.332-343. These security considerations apply when g generates the multiplicative group; if it generates an appropriate sub-group, then "non-safe" primes can be safe to use too. Let me recycle an earlier write-up on these issues. >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> Date: Fri, 7 Apr 2000 11:28:24 +0200 (CEST) From: bmoeller@hrzpub.tu-darmstadt.de (Bodo Moeller) To: "IETF Transport Layer Security WG" Subject: Re: forward secrecy, RSA_EXPORT, D-H, etc. [....] > bmoeller@hrzpub.tu-darmstadt.de (Bodo Moeller): >> Unfortunately, TLS ServerDHParams do not include a recommended >> exponent length; and the client cannot be sure that g is a >> generator of a prime-order subgroup. Thus it is in general >> not safe to assume that short exponents can be used. [...] > That said, I'm not enough of a DH weenie to know what the > result of choosing ephemeral DH keys when g doesn't generate > a prime order subgroup is. Does it just reveal the client > key (which isn't important since it's ephemeral anyway) or > does it compromise the key exchange or the server key or what? If the client's ephemeral DH key is compromised, then obviously the result of the key exchange is compromised too. The server key is ephemeral too, so there's nothing additional to attack there. The relevant details about subgroup structure are as follows: If g is any element of the cyclic group (Z/pZ)*, then it generates a subgroup of some order q where q can be any divisor of p - 1. (Note that I'm not requiring that q be a prime.) Important facts about q are: - its largest prime factor l (more generally, because the complete factorization of q may not be known, its largest non-factorable factor. But let's assume that we know the largest prime factor; often it is explicitly computed in one of the first steps of DH parameter generation.) - the smooth part s of q, i.e. the largest factor that is the product of small primes, where "small" is defined with the Pohlig-Hellmann attack in mind. Now let Q denote the bit length of q, let L denote the bit length of the l, and let S denote the bit length of s. (Note that L + S <= Q. When I speak of bit lengths, I actually mean the base-2 log, but I'll pretend it's always an integer and will ignore the rounding error.) Then, when we're working in the order-q subgroup of (Z/pZ)* generated by g, exponents longer than Q bits obviously don't make sense at all. For attacks that make use the subgroup structure, only exponents up to L bits in length have to be considered (the attacker can use exponentiation by q/l to map any element into the subgroup of l elements; basically, only L exponent bits survive this exponentiation, and after the discrete logarithm in this smaller subgroup has been found, the hardest sub-task for finding the discrete log of the original element is done). And as the smooth part of q makes Pohlig-Hellman attacks possible, S bits of the discrete logarithm cannot be considered secret (these S bits are usually not actual bits in the binary representation of the discrete log, but the knowledge is worth S bits). So what remains to be attacked (this is, roughly, a result by Wiener/van Oorschot, I think) are L - S bits if the exponent has size at least L; if exponents are only E bits long (E <= L), only E - S bits must be attacked. So the requirement to avoid this kind of attacks is E - S >= 160 (or 122 as in your previous example, or whatever; I use 160 because that's what the DSS uses). If you know S (or some upper bound for S), then you can determine how large E should be; but a TLS client cannot do this. Often DH parameters are created such as S = 0 (i.e., q is a prime). Examples: - p is a strong prime, that is, p = 2q + 1. (For strong primes, one might also allow S = 1, i.e. use a quadratic non-residue as g; this one bit does not really matter. In this case, when q is defined as above, p = q + 1 where q/2 is prime.) When strong primes are used, g can be chosen small to allow for efficient exponentation of g. - g generates a large prime-order subgroup, where the order q of this subgroup is somewhat smaller than g; e.g. 1024-bit g, 160-bit q. (Schnorr/DSA) Such parameters are much faster to create than strong primes; however, you cannot force g to be small. But there are other possibilites than S = 0: PGP, for example, makes sure that p - 1 has a prime factor that is only a few bits smaller than p; and it then uses a small g (for efficiency) without insisting that g generate only the prime-order subgroup. I.e., we have S <= 10 or so, and the requirement E - S >= 160 translates to E >= 170. Now assume you take this further and want to achieve two goals when creating DH parameters for use in ephemeral DH: - g should be small to speed up exponentation. - DH parameter generation should be fast so that you can use fresh parameters often (note that index-calculus attacks for discrete logs require a lot of pre-calculation that depends only on p, and once this step has been finished, discrete logs mod p can be computed efficiently). Let P be the length of the prime p that we want to find. To achieve the above goals, one might use L = 2/3 P and S <= 1/3 P. That is, if you want P = 1024, first create a prime of around 683 bits, and then find a 1024-bit prime p that is congruent to 1 modulo this 683-bit prime. The requirement for the exponent length E is E >= 160 + S, i.e. (if we assume the maximum value for S) we need E >= 160 + P/3 = 501. Now if the client were to use only 160-bit exponents for these parameters, then we could not rely on the key-exchange being secure. Bodo M"oller <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<< Thus my proposal is to allow "non-safe" primes and include a "recommended minimum exponent length" field with the DH parameters. Additional note: All of the above assumes that the server and the client use new DH exponents for each exchange even if DH parameters are reused. Otherwise, in addition van Oorschot/Wiener attacks, Lim/Lee attacks have to be taken into account if small subgroups exists. (In Lim/Lee attacks, an attacker ignores the generator -- usually a generator of a prime-order subgroup -- and instead sends a "DH public value" from a small subgroup. If the other party continues as usual using some DH exponent x, then effectively only x mod order-of-subgroup is actually used, and accordingly there are only few possiblities for the apparent outcome of this "DH key exchange", and the attacker can compute all of these. Now if the attacked party uses the DH result to, say, encrypt data, then the attacker can test all possible keys and test-decrypt the encrypted data; as most decryptions will lead to garbage, it's usually easy to tell which key was the correct one, and hence what x mod order-of-subgroup is. By doing this for multiple small subgroups, the attacker can obtain x mod gcd(order-of-subgroup_1, ..., order-of-subgroup_k), and if x is a small exponent, this may suffice to determine x.) If client exponent reuse is desired, then an additional flag or value could be used by the server to notify the client about the properties of the DH parameters, but I don't think this optimization is worth such extra effort -- usually it wouldn't even be used because it requires a client-side cache and reduces forward secrecy. If server exponent reuse is desired, which may make more sense because the server is more likely to be a long-running process handling many connections, then the server has to know whether its parameters are safe against Lim/Lee attacks. If a safe prime is used, for example, then it's OK (except that it limits forward secrecry); similarly, it's OK when a prime p is used such that p-1 is the product of a couple of large primes (this is recommended in the Lim/Lee paper). In general, it's not safe. So my recommendation for this is to explicitly disallow exponent reuse for clients, to recommend that servers not reuse exponents, and to discuss some of the concerns when servers want to reuse exponents anyway (i.e. that they no longer have full forward secrecy, and that certain properties of the modulus can lead to problems). -- Bodo Möller PGP http://www.informatik.tu-darmstadt.de/TI/Mitarbeiter/moeller/0x36d2c658.html * TU Darmstadt, Theoretische Informatik, Alexanderstr. 10, D-64283 Darmstadt * Tel. +49-6151-16-6628, Fax +49-6151-16-6036 From owner-ietf-ssh@clinet.fi Thu Jun 8 08:08:05 2000 Return-Path: Received: from faui45.informatik.uni-erlangen.de (root@faui45.informatik.uni-erlangen.de [131.188.34.45]) by faui01.informatik.uni-erlangen.de (8.8.8/8.1.16-FAU) with ESMTP id IAA14482 for ; Thu, 8 Jun 2000 08:08:05 +0200 (MET DST) Received: from mail.clinet.fi (mail.clinet.fi [194.100.0.7]) by faui45.informatik.uni-erlangen.de (8.9.1/8.1.49-FAU) with ESMTP id IAA09637 for ; Thu, 8 Jun 2000 08:08:04 +0200 (MET DST) Received: (from majordom@localhost) by mail.clinet.fi (8.9.3/8.9.3) id HAA29326 for ietf-ssh-outgoing; Thu, 8 Jun 2000 07:11:15 +0300 Received: from ssh.com (fw.hel.fi.ssh.com [193.64.193.124]) by mail.clinet.fi (8.9.3/8.9.3) with ESMTP id HAA29323 for ; Thu, 8 Jun 2000 07:11:14 +0300 Received: from torni.hel.fi.ssh.com (torni.hel.fi.ssh.com [10.1.0.43]) by ssh.com (8.9.3/8.9.3/SSH-1.16) with ESMTP id HAA07626; Thu, 8 Jun 2000 07:11:14 +0300 (EEST) Received: (from mkojo@localhost) by torni.hel.fi.ssh.com (8.9.3/8.9.3/SSH-1.17) id HAA17939; Thu, 8 Jun 2000 07:11:13 +0300 (EET DST) Date: Thu, 8 Jun 2000 07:11:13 +0300 (EET DST) Message-Id: <200006080411.HAA17939@torni.hel.fi.ssh.com> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit From: Mika Kojo To: Bodo Moeller Cc: Mika Kojo , ietf-ssh@clinet.fi Subject: Re: Diffie-Hellman Group Exchange In-Reply-To: <20000607170746.A431@cdc.informatik.tu-darmstadt.de> References: <20000606205204.3E2CD207C1@citi.umich.edu> <200006062307.CAA21153@torni.hel.fi.ssh.com> <20000607170746.A431@cdc.informatik.tu-darmstadt.de> X-Mailer: VM 6.34 under Emacs 19.34.2 Organization: SSH Communications Security, Finland Sender: owner-ietf-ssh@clinet.fi Precedence: bulk Content-Length: 2443 Lines: 58 Bodo, The analysis you present is interesting, and problems with reusing exponents should certainly be taken into account. At this opportunity I wish to give few comments; * The folk knowledge that g = 2 is best is not always correct. Even g being small does not usually speed up exponentiation (and very possibly it doesn't speed Diffie-Hellman at all, given some black-box exponentiation routine). I back this claim by the well-known speed-ups: Montgomery representation, and fixed base (e.g. Lim-Lee comb) precomputation. (In Montgomery with e.g. R = 2^n, s.t. p < R, we might benefit from using g = (c/R (mod p)), with c small. With Lim-Lee comb method, for example, you precompute g^(a_i) where almost all a_i are very large. Thus it is difficult to see how g small helps.) Further in Diffie-Hellman it is difficult to avoid general base in the second exponentiation. On the otherhand, if g = 2 I could see that on memory poor devices, for example, some benefit could be obtained. Some of the better exponentiation algorithms tend to spend quite a lot of memory. However, SSH2 is not directed to memory poor devices (but this is my opinion and understanding only!) and thus I do not see much interest in special concern for selecting small g. * Using a subgroup of composite order may be beneficial for some purposes, but in theory---as far as I know---it seems that prime order subgroups are better. As primes of form p = 2cq + 1, with c large and q prime, are quite easily generated I think that allowing composite order subgroups is not particularly important. However, even when selecting "small" prime order subgroups one must take into account few security criteria. So it is not entirely clear which approach is the best. * Let lg p ~= 1024, and lg ord(g) ~= 600 as Bodo suggest with exponent e, s.t. lg e <= 160, then the theoretical problem that I mentioned before is present. The problem is that g^e would not be completely random in the group . However, if lg ord(g) ~= lg e ~= 160 then g^e would look like a general element in . I am not suggesting that there exists an efficient attack which utilizes this. My point is just to show that using prime order subgroups that are significantly smaller than p have some benefits. Best regards, Mika Kojo SSH Communications Security Corp From owner-ietf-ssh@clinet.fi Thu Jun 8 13:08:32 2000 Return-Path: Received: from faui45.informatik.uni-erlangen.de (root@faui45.informatik.uni-erlangen.de [131.188.34.45]) by faui01.informatik.uni-erlangen.de (8.8.8/8.1.16-FAU) with ESMTP id NAA04255 for ; Thu, 8 Jun 2000 13:08:31 +0200 (MET DST) Received: from mail.clinet.fi (mail.clinet.fi [194.100.0.7]) by faui45.informatik.uni-erlangen.de (8.9.1/8.1.49-FAU) with ESMTP id NAA03271 for ; Thu, 8 Jun 2000 13:08:25 +0200 (MET DST) Received: (from majordom@localhost) by mail.clinet.fi (8.9.3/8.9.3) id MAA19753 for ietf-ssh-outgoing; Thu, 8 Jun 2000 12:03:07 +0300 Received: from cdc-info.cdc.informatik.tu-darmstadt.de (cdc-info.cdc.informatik.tu-darmstadt.de [130.83.23.100]) by mail.clinet.fi (8.9.3/8.9.3) with ESMTP id MAA19526 for ; Thu, 8 Jun 2000 12:02:03 +0300 Received: from cdc1.cdc.informatik.tu-darmstadt.de (cdc1 [130.83.23.10]) by cdc-info.cdc.informatik.tu-darmstadt.de (Postfix) with ESMTP id B41122C4C; Thu, 8 Jun 2000 11:02:00 +0200 (MET DST) Received: by cdc1.cdc.informatik.tu-darmstadt.de (8.8.8+Sun/SMI-SVR4) id LAA00881; Thu, 8 Jun 2000 11:02:00 +0200 (MET DST) Date: Thu, 8 Jun 2000 11:01:59 +0200 From: Bodo Moeller To: Mika Kojo Cc: ietf-ssh@clinet.fi Subject: Re: Diffie-Hellman Group Exchange Message-ID: <20000608110158.B861@cdc.informatik.tu-darmstadt.de> References: <20000606205204.3E2CD207C1@citi.umich.edu> <200006062307.CAA21153@torni.hel.fi.ssh.com> <20000607170746.A431@cdc.informatik.tu-darmstadt.de> <200006080411.HAA17939@torni.hel.fi.ssh.com> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii X-Mailer: Mutt 1.0i In-Reply-To: <200006080411.HAA17939@torni.hel.fi.ssh.com>; from mkojo@ssh.com on Thu, Jun 08, 2000 at 07:11:13AM +0300 Sender: owner-ietf-ssh@clinet.fi Precedence: bulk Content-Length: 2440 Lines: 51 On Thu, Jun 08, 2000 at 07:11:13AM +0300, Mika Kojo wrote: > At this opportunity I wish to give few comments; > > * The folk knowledge that g = 2 is best is not always correct. Even > g being small does not usually speed up exponentiation (and very > possibly it doesn't speed Diffie-Hellman at all, given some > black-box exponentiation routine). > > I back this claim by the well-known speed-ups: Montgomery > representation, and fixed base (e.g. Lim-Lee comb) precomputation. > (In Montgomery with e.g. R = 2^n, s.t. p < R, we might benefit from > using g = (c/R (mod p)), with c small. I claimed so myself recently, but now I have made experiments and found out that small generators help even when using Montgomery multiplication (using a modified mod_exp routine that uses standard modular multiplication for multiplying with small factors, but Montgomery multiplication for squaring the accumulator.) Thus it seems that using a small g can help even for optimized implementations. > * Using a subgroup of composite order may be beneficial for some > purposes, but in theory---as far as I know---it seems that prime > order subgroups are better. > > As primes of form p = 2cq + 1, with c large and q prime, are quite > easily generated I think that allowing composite order subgroups is > not particularly important. Do you mean they should be ruled out in the specification? In some senses, it makes things easier to allow them -- for example because it means that you can use generator 2 when using p = 2cq + 1 where q is nearly as large as p (such primes are easier to find than safe primes which is why PGP uses them for its ElGamal encryption keys), or when p is a Lim-Lee prime (i.e. p-1 is the product of a couple of primes all of which are large). So I think that such flexibility should be allowed. > [....] My point is just to show that using prime order > subgroups that are significantly smaller than p have some benefits. Yes. The only problem with them is that the client does not know everything about how the DH parameters have been chosen, so it in general it cannot know whether using small exponents is safe. That's why I proposed including a recommended exponent length with the parameters -- the server should know according to which criteria they have been selected, and thus can know how small exponents can be safely made. From owner-ietf-ssh@clinet.fi Thu Jun 8 15:17:07 2000 Return-Path: Received: from faui45.informatik.uni-erlangen.de (root@faui45.informatik.uni-erlangen.de [131.188.34.45]) by faui01.informatik.uni-erlangen.de (8.8.8/8.1.16-FAU) with ESMTP id PAA12308 for ; Thu, 8 Jun 2000 15:17:07 +0200 (MET DST) Received: from mail.clinet.fi (mail.clinet.fi [194.100.0.7]) by faui45.informatik.uni-erlangen.de (8.9.1/8.1.49-FAU) with ESMTP id PAA14630 for ; Thu, 8 Jun 2000 15:17:05 +0200 (MET DST) Received: (from majordom@localhost) by mail.clinet.fi (8.9.3/8.9.3) id NAA11988 for ietf-ssh-outgoing; Thu, 8 Jun 2000 13:54:56 +0300 Received: from tukki.cc.jyu.fi (mjos@tukki.cc.jyu.fi [130.234.1.1]) by mail.clinet.fi (8.9.3/8.9.3) with ESMTP id NAA11971 for ; Thu, 8 Jun 2000 13:54:54 +0300 Received: from localhost (mjos@localhost) by tukki.cc.jyu.fi (8.9.3/8.9.3/antispam3) with ESMTP id NAA19440 for ; Thu, 8 Jun 2000 13:54:53 +0300 (EET DST) Date: Thu, 8 Jun 2000 13:54:53 +0300 (EET DST) From: Markku-Juhani Saarinen X-Sender: mjos@tukki To: ietf-ssh@clinet.fi Subject: RE: Diffie-Hellman Group Exchange Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=ISO-8859-1 Content-Transfer-Encoding: 8BIT Sender: owner-ietf-ssh@clinet.fi Precedence: bulk Content-Length: 1314 Lines: 39 Niels Provos wrote: > "Diffie-Hellman Group Exchange for the SSH Transport Layer Protocol" > >is now available as > > draft-provos-secsh-dh-group-exchange-00.txt > >Bodo and Markku could you please see if your concerns have been >addressed. Niels, The group generator advice is still (IMHO) the wrong way around; secret key bits are leaked. One can counter this by using longer exponents but this will result in a small performance cost. One section reads: "[generator 2] is usable even when it is not a primitive root, as it still covers half of the space of possible residues". From a mathematical point of view this doesn't make much sense: if you use a primitive root as g, an attacker can get one bit of the secret exponent by computing L(x) = x^((p-1)/2) and then put the secret into the subgroup of size (p-1)/2 by simply squaring it. The problem is thus reduced to computing a DL in the smaller subgroup. Also you might consider mentioning that actually smaller exponents (e.g. 256 bits) can be used to boost up performance. This would set the security level around 2^128 (assuming that a subgroup of prime order is used) and quadruple the performance with a 1024-bit prime. Cheers, - mj Markku-Juhani O. Saarinen University of Jyväskylä, Finland From owner-ietf-ssh@clinet.fi Thu Jun 8 15:10:24 2000 Return-Path: Received: from faui45.informatik.uni-erlangen.de (root@faui45.informatik.uni-erlangen.de [131.188.34.45]) by faui01.informatik.uni-erlangen.de (8.8.8/8.1.16-FAU) with ESMTP id PAA11848 for ; Thu, 8 Jun 2000 15:10:24 +0200 (MET DST) Received: from mail.clinet.fi (mail.clinet.fi [194.100.0.7]) by faui45.informatik.uni-erlangen.de (8.9.1/8.1.49-FAU) with ESMTP id PAA13900 for ; Thu, 8 Jun 2000 15:10:23 +0200 (MET DST) Received: (from majordom@localhost) by mail.clinet.fi (8.9.3/8.9.3) id OAA13353 for ietf-ssh-outgoing; Thu, 8 Jun 2000 14:01:09 +0300 Received: from tukki.cc.jyu.fi (mjos@tukki.cc.jyu.fi [130.234.1.1]) by mail.clinet.fi (8.9.3/8.9.3) with ESMTP id OAA13342 for ; Thu, 8 Jun 2000 14:01:06 +0300 Received: from localhost (mjos@localhost) by tukki.cc.jyu.fi (8.9.3/8.9.3/antispam3) with ESMTP id OAA20054 for ; Thu, 8 Jun 2000 14:01:04 +0300 (EET DST) Date: Thu, 8 Jun 2000 14:01:04 +0300 (EET DST) From: Markku-Juhani Saarinen X-Sender: mjos@tukki To: ietf-ssh@clinet.fi Subject: RE: Diffie-Hellman Group Exchange In-Reply-To: Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=ISO-8859-1 Content-Transfer-Encoding: 8BIT Sender: owner-ietf-ssh@clinet.fi Precedence: bulk Content-Length: 627 Lines: 17 I just wrote: > Also you might consider mentioning that actually smaller exponents > (e.g. 256 bits) can be used to boost up performance. This would set > the security level around 2^128 (assuming that a subgroup of prime > order is used) and quadruple the performance with a 1024-bit prime. Actually 2^128 would be the complexity of the Lambda DL method, but the prime size of 1024 bits limits the security to around 2^70 anyway, regardless of the exponent size. A 2^128 security level would require prime p to be around 4100 bits. - mj Markku-Juhani O. Saarinen University of Jyväskylä, Finland From owner-ietf-ssh@clinet.fi Thu Jun 8 15:39:01 2000 Return-Path: Received: from faui45.informatik.uni-erlangen.de (root@faui45.informatik.uni-erlangen.de [131.188.34.45]) by faui01.informatik.uni-erlangen.de (8.8.8/8.1.16-FAU) with ESMTP id PAA14400 for ; Thu, 8 Jun 2000 15:39:00 +0200 (MET DST) Received: from mail.clinet.fi (mail.clinet.fi [194.100.0.7]) by faui45.informatik.uni-erlangen.de (8.9.1/8.1.49-FAU) with ESMTP id PAA16688 for ; Thu, 8 Jun 2000 15:38:56 +0200 (MET DST) Received: (from majordom@localhost) by mail.clinet.fi (8.9.3/8.9.3) id OAA13462 for ietf-ssh-outgoing; Thu, 8 Jun 2000 14:01:53 +0300 Received: from ssh.com (fw.hel.fi.ssh.com [193.64.193.124]) by mail.clinet.fi (8.9.3/8.9.3) with ESMTP id OAA13420 for ; Thu, 8 Jun 2000 14:01:41 +0300 Received: from torni.hel.fi.ssh.com (torni.hel.fi.ssh.com [10.1.0.43]) by ssh.com (8.9.3/8.9.3/SSH-1.16) with ESMTP id OAA27060; Thu, 8 Jun 2000 14:01:41 +0300 (EEST) Received: (from mkojo@localhost) by torni.hel.fi.ssh.com (8.9.3/8.9.3/SSH-1.17) id OAA15283; Thu, 8 Jun 2000 14:01:41 +0300 (EET DST) Date: Thu, 8 Jun 2000 14:01:41 +0300 (EET DST) Message-Id: <200006081101.OAA15283@torni.hel.fi.ssh.com> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit From: Mika Kojo To: Bodo Moeller Cc: Mika Kojo , ietf-ssh@clinet.fi Subject: Re: Diffie-Hellman Group Exchange In-Reply-To: <20000608110158.B861@cdc.informatik.tu-darmstadt.de> References: <20000606205204.3E2CD207C1@citi.umich.edu> <200006062307.CAA21153@torni.hel.fi.ssh.com> <20000607170746.A431@cdc.informatik.tu-darmstadt.de> <200006080411.HAA17939@torni.hel.fi.ssh.com> <20000608110158.B861@cdc.informatik.tu-darmstadt.de> X-Mailer: VM 6.34 under Emacs 19.34.2 Organization: SSH Communications Security, Finland Sender: owner-ietf-ssh@clinet.fi Precedence: bulk Content-Length: 4214 Lines: 92 Bodo Moeller writes: > On Thu, Jun 08, 2000 at 07:11:13AM +0300, Mika Kojo wrote: > > > At this opportunity I wish to give few comments; > > > > * The folk knowledge that g = 2 is best is not always correct. Even > > g being small does not usually speed up exponentiation (and very > > possibly it doesn't speed Diffie-Hellman at all, given some > > black-box exponentiation routine). > > > > I back this claim by the well-known speed-ups: Montgomery > > representation, and fixed base (e.g. Lim-Lee comb) precomputation. > > (In Montgomery with e.g. R = 2^n, s.t. p < R, we might benefit from > > using g = (c/R (mod p)), with c small. > > I claimed so myself recently, but now I have made experiments and > found out that small generators help even when using Montgomery > multiplication (using a modified mod_exp routine that uses standard > modular multiplication for multiplying with small factors, but > Montgomery multiplication for squaring the accumulator.) > Thus it seems that using a small g can help even for optimized > implementations. My apologies for repeating. And yes, benefits of g = 2 appear also in Montgomery representation. However, they are not as great if you have some binary window variant. There multiplying by 2^i, where i \n { 1, 3, ..., 2^k-1 }, can be efficient, but then you'll need also a division routine. Though, I can see that this still could yield good performance. But as mentioned if we assume Montgomery exponentiation routine, then setting g == 2/(2^n) (mod p), say, should give equal (or greater) speed. (Further speed up can be still obtained by suitable selection of the prime number. For example, setting the highest bits to ones gives faster division routine. Also using very low hamming weight primes may give speed-ups, e.g. generalized Mersenne primes.) In Diffie-Hellman it is very effective to use fixed base precomputation ideas. Most of these require using exponents, in the precomputation, larger than lg ord(g), so the structure of g is lost. > > * Using a subgroup of composite order may be beneficial for some > > purposes, but in theory---as far as I know---it seems that prime > > order subgroups are better. > > > > As primes of form p = 2cq + 1, with c large and q prime, are quite > > easily generated I think that allowing composite order subgroups is > > not particularly important. > > Do you mean they should be ruled out in the specification? In some > senses, it makes things easier to allow them -- for example because > it means that you can use generator 2 when using p = 2cq + 1 > where q is nearly as large as p (such primes are easier to find > than safe primes which is why PGP uses them for its ElGamal encryption > keys), or when p is a Lim-Lee prime (i.e. p-1 is the product of a > couple of primes all of which are large). So I think that such > flexibility should be allowed. At the moment I do not see really good reasons why composite group orders should be allowed. However, this is just that I have not yet understood why g = 2 would make life so much easier---but perhaps I will eventually. Wouldn't Lim-Lee primes be almost impossible to verify by anyone? That is, checking that g actually belongs to some large enough subgroup is a bit difficult. (Of course, in the protocol suggested this might not be of importance.) > > [....] My point is just to show that using prime order > > subgroups that are significantly smaller than p have some benefits. > > Yes. The only problem with them is that the client does not know > everything about how the DH parameters have been chosen, so it in > general it cannot know whether using small exponents is safe. That's > why I proposed including a recommended exponent length with the > parameters -- the server should know according to which criteria > they have been selected, and thus can know how small exponents > can be safely made. Why cannot the client just compute the exponent length itself, it should know p,g and ord(g)? A conservative choice is to select exponent size to be approximately equal to the subgroup size. Best regards, Mika Kojo SSH Communications Security Corp From owner-ietf-ssh@clinet.fi Thu Jun 8 15:58:10 2000 Return-Path: Received: from faui45.informatik.uni-erlangen.de (root@faui45.informatik.uni-erlangen.de [131.188.34.45]) by faui01.informatik.uni-erlangen.de (8.8.8/8.1.16-FAU) with ESMTP id PAA15563 for ; Thu, 8 Jun 2000 15:58:09 +0200 (MET DST) Received: from mail.clinet.fi (mail.clinet.fi [194.100.0.7]) by faui45.informatik.uni-erlangen.de (8.9.1/8.1.49-FAU) with ESMTP id PAA18432 for ; Thu, 8 Jun 2000 15:58:05 +0200 (MET DST) Received: (from majordom@localhost) by mail.clinet.fi (8.9.3/8.9.3) id OAA22039 for ietf-ssh-outgoing; Thu, 8 Jun 2000 14:40:15 +0300 Received: from samantha.lysator.liu.se (root@samantha.lysator.liu.se [130.236.254.202]) by mail.clinet.fi (8.9.3/8.9.3) with ESMTP id OAA18463; Thu, 8 Jun 2000 14:24:26 +0300 Received: from sture.lysator.liu.se (nisse@sture.lysator.liu.se [130.236.254.21]) by samantha.lysator.liu.se (8.9.3/8.9.3) with ESMTP id NAA28524; Thu, 8 Jun 2000 13:23:37 +0200 (MET DST) Received: (from nisse@localhost) by sture.lysator.liu.se (8.9.0/8.8.7) id NAA14333; Thu, 8 Jun 2000 13:23:32 +0200 (MET DST) To: "Noel L Yap" Cc: Ietf-Ssh@clinet.fi, Psst@Net.Lut.Ac.Uk, ssh@clinet.fi Subject: Re: Using SRP as a key exchange metod in Secure Shell References: <852568F7.0053F5EC.00@nyc-ntgw-n01.ny.jpmorgan.com> From: nisse@lysator.liu.se (Niels Möller) Date: 08 Jun 2000 13:23:32 +0200 In-Reply-To: "Noel L Yap"'s message of "Wed, 7 Jun 2000 11:17:02 -0400" Message-ID: X-Mailer: Gnus v5.7/Emacs 20.5 Sender: owner-ietf-ssh@clinet.fi Precedence: bulk Content-Length: 1165 Lines: 29 "Noel L Yap" writes: > OK, I've read this, but since I'm a bit of a newbie, I have a couple of > questions: > 1. Can the SRP authentication be used to authenticate the client to the host > without the use of assymetric keys? I understand that this may not be as secure > (since passwords generally have less entropy than keys), but in some situations, > the convenience is worth the risk. Yes. One way to look at SRP is to view it like a assymetric system where the user's private key is derived from a password. But the host-authentication part of it really uses the verifier as a shared (symmetric) secret. > 2. What effects would such a change have on ssh-agent and ssh-add? You would either have to type the SRP password each time, or tell the agent about it. Or just get the hostkey and use the traditional host- and userauthentication mechanisms in ssh. Note that LSH doesn't (yet) have anything like ssh-agent or ssh-add. I'm expecting the gateway feature (once that is implemented) to be able to replace aah-agent in many cases. See http://www.lysator.liu.se/~nisse/lsh/doc/gateway-mode.txt for some ideas about that. /Niels From owner-ietf-ssh@clinet.fi Mon Jun 12 19:43:42 2000 Return-Path: Received: from faui45.informatik.uni-erlangen.de (root@faui45.informatik.uni-erlangen.de [131.188.34.45]) by faui01.informatik.uni-erlangen.de (8.8.8/8.1.16-FAU) with ESMTP id TAA03973 for ; Mon, 12 Jun 2000 19:43:42 +0200 (MET DST) Received: from mail.clinet.fi (mail.clinet.fi [194.100.0.7]) by faui45.informatik.uni-erlangen.de (8.9.1/8.1.49-FAU) with ESMTP id TAA20978 for ; Mon, 12 Jun 2000 19:43:41 +0200 (MET DST) Received: (from majordom@localhost) by mail.clinet.fi (8.9.3/8.9.3) id SAA26087 for ietf-ssh-outgoing; Mon, 12 Jun 2000 18:47:07 +0300 Received: from cdc-info.cdc.informatik.tu-darmstadt.de (cdc-info.cdc.informatik.tu-darmstadt.de [130.83.23.100]) by mail.clinet.fi (8.9.3/8.9.3) with ESMTP id OAA22713 for ; Thu, 8 Jun 2000 14:43:51 +0300 Received: from cdc1.cdc.informatik.tu-darmstadt.de (cdc1 [130.83.23.10]) by cdc-info.cdc.informatik.tu-darmstadt.de (Postfix) with ESMTP id 1D8882C4C; Thu, 8 Jun 2000 13:43:50 +0200 (MET DST) Received: by cdc1.cdc.informatik.tu-darmstadt.de (8.8.8+Sun/SMI-SVR4) id NAA00559; Thu, 8 Jun 2000 13:43:49 +0200 (MET DST) Date: Thu, 8 Jun 2000 13:43:48 +0200 From: Bodo Moeller To: Mika Kojo Cc: ietf-ssh@clinet.fi Subject: Re: Diffie-Hellman Group Exchange Message-ID: <20000608134347.A544@cdc.informatik.tu-darmstadt.de> References: <20000606205204.3E2CD207C1@citi.umich.edu> <200006062307.CAA21153@torni.hel.fi.ssh.com> <20000607170746.A431@cdc.informatik.tu-darmstadt.de> <200006080411.HAA17939@torni.hel.fi.ssh.com> <20000608110158.B861@cdc.informatik.tu-darmstadt.de> <200006081101.OAA15283@torni.hel.fi.ssh.com> Mime-Version: 1.0 Content-Type: text/plain; charset=iso-8859-1 Content-Transfer-Encoding: 8bit X-Mailer: Mutt 1.0i In-Reply-To: <200006081101.OAA15283@torni.hel.fi.ssh.com>; from mkojo@ssh.com on Thu, Jun 08, 2000 at 02:01:41PM +0300 Sender: owner-ietf-ssh@clinet.fi Precedence: bulk Content-Length: 3276 Lines: 72 On Thu, Jun 08, 2000 at 02:01:41PM +0300, Mika Kojo wrote: > And yes, benefits of g = 2 appear also in > Montgomery representation. However, they are not as great if you have > some binary window variant. There multiplying by 2^i, where i \n { 1, > 3, ..., 2^k-1 }, can be efficient, but then you'll need also a > division routine. Though, I can see that this still could yield good > performance. > > But as mentioned if we assume Montgomery exponentiation routine, then > setting g == 2/(2^n) (mod p), say, should give equal (or greater) > speed. Maybe I just made a mistake when trying to determine the performance when g is chosen such that it becomes 2 when converted to Montgomery representation; speed gain was negligible. With g = 2 and a special Montgomery modexp variant for small bases (which requires a division routine), I was able to obtain an about 20 % speed-up. > In Diffie-Hellman it is very effective to use fixed base > precomputation ideas. Most of these require using exponents, in the > precomputation, larger than lg ord(g), so the structure of g is lost. Yes, but this can be used only when the same parameters are used many times. Servers can easily make use of it, but for SSH clients, a small g can be more convenient. (Also if the server wants to optimize g for Montgomery, it cannot really know if the client actually uses Montgomery multiplication, and in case it does, if it uses the same variant of Montgomery multiplication.) [...] > Wouldn't Lim-Lee primes be almost impossible to verify by anyone? That > is, checking that g actually belongs to some large enough subgroup is > a bit difficult. (Of course, in the protocol suggested this might not > be of importance.) You can't verify them, but in this protocol verification is not important. >>> [....] My point is just to show that using prime order >>> subgroups that are significantly smaller than p have some benefits. >> Yes. The only problem with them is that the client does not know >> everything about how the DH parameters have been chosen, so it in >> general it cannot know whether using small exponents is safe. That's >> why I proposed including a recommended exponent length with the >> parameters -- the server should know according to which criteria >> they have been selected, and thus can know how small exponents >> can be safely made. > Why cannot the client just compute the exponent length itself, it should > know p,g and ord(g)? A conservative choice is to select exponent size > to be approximately equal to the subgroup size. If the protocol defines that only prime order subgroups may be used (and if everone follows the specification), then there's no problem. But if other subgroups are allowed, then problems can arise if the client decides to optimize by choosing the exponent smaller than ord(g). If DH parameters include a (minimum) exponent length in addition to or instead of ord(g), then such problems are avoided. -- Bodo Möller PGP http://www.informatik.tu-darmstadt.de/TI/Mitarbeiter/moeller/0x36d2c658.html * TU Darmstadt, Theoretische Informatik, Alexanderstr. 10, D-64283 Darmstadt * Tel. +49-6151-16-6628, Fax +49-6151-16-6036 From owner-ietf-ssh@clinet.fi Thu Jun 8 17:14:52 2000 Return-Path: Received: from faui45.informatik.uni-erlangen.de (root@faui45.informatik.uni-erlangen.de [131.188.34.45]) by faui01.informatik.uni-erlangen.de (8.8.8/8.1.16-FAU) with ESMTP id RAA21287 for ; Thu, 8 Jun 2000 17:14:51 +0200 (MET DST) Received: from mail.clinet.fi (mail.clinet.fi [194.100.0.7]) by faui45.informatik.uni-erlangen.de (8.9.1/8.1.49-FAU) with ESMTP id RAA26459 for ; Thu, 8 Jun 2000 17:14:49 +0200 (MET DST) Received: (from majordom@localhost) by mail.clinet.fi (8.9.3/8.9.3) id PAA01743 for ietf-ssh-outgoing; Thu, 8 Jun 2000 15:31:09 +0300 Received: from ssh.com (fw.hel.fi.ssh.com [193.64.193.124]) by mail.clinet.fi (8.9.3/8.9.3) with ESMTP id PAA01691 for ; Thu, 8 Jun 2000 15:30:59 +0300 Received: from torni.hel.fi.ssh.com (torni.hel.fi.ssh.com [10.1.0.43]) by ssh.com (8.9.3/8.9.3/SSH-1.16) with ESMTP id PAA04065; Thu, 8 Jun 2000 15:30:57 +0300 (EEST) Received: (from mkojo@localhost) by torni.hel.fi.ssh.com (8.9.3/8.9.3/SSH-1.17) id PAA01781; Thu, 8 Jun 2000 15:30:56 +0300 (EET DST) Date: Thu, 8 Jun 2000 15:30:56 +0300 (EET DST) Message-Id: <200006081230.PAA01781@torni.hel.fi.ssh.com> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit From: Mika Kojo To: Bodo Moeller Cc: Mika Kojo , ietf-ssh@clinet.fi Subject: Re: Diffie-Hellman Group Exchange In-Reply-To: <20000608134347.A544@cdc.informatik.tu-darmstadt.de> References: <20000606205204.3E2CD207C1@citi.umich.edu> <200006062307.CAA21153@torni.hel.fi.ssh.com> <20000607170746.A431@cdc.informatik.tu-darmstadt.de> <200006080411.HAA17939@torni.hel.fi.ssh.com> <20000608110158.B861@cdc.informatik.tu-darmstadt.de> <200006081101.OAA15283@torni.hel.fi.ssh.com> <20000608134347.A544@cdc.informatik.tu-darmstadt.de> X-Mailer: VM 6.34 under Emacs 19.34.2 Organization: SSH Communications Security, Finland Sender: owner-ietf-ssh@clinet.fi Precedence: bulk Content-Length: 1181 Lines: 30 Bodo Moeller writes: [snip] > Maybe I just made a mistake when trying to determine the performance > when g is chosen such that it becomes 2 when converted to > Montgomery representation; speed gain was negligible. With g = 2 > and a special Montgomery modexp variant for small bases (which > requires a division routine), I was able to obtain an about 20 % > speed-up. Experiments speak for themselves, although being a bit surprising :) It would be interesting for me to know more about your timings, but it is probably not a topic for this list. [snip] > If the protocol defines that only prime order subgroups may be used > (and if everone follows the specification), then there's no problem. > But if other subgroups are allowed, then problems can arise if the > client decides to optimize by choosing the exponent smaller than > ord(g). If DH parameters include a (minimum) exponent length > in addition to or instead of ord(g), then such problems are avoided. I see the problem. Yet I think it is one reason more for using prime subgroups. Not that one length field would cause much concern, though. Best regards, Mika Kojo SSH Communications Security Corp From owner-ietf-ssh@clinet.fi Thu Jun 8 17:19:00 2000 Return-Path: Received: from faui45.informatik.uni-erlangen.de (root@faui45.informatik.uni-erlangen.de [131.188.34.45]) by faui01.informatik.uni-erlangen.de (8.8.8/8.1.16-FAU) with ESMTP id RAA21415 for ; Thu, 8 Jun 2000 17:18:59 +0200 (MET DST) Received: from mail.clinet.fi (mail.clinet.fi [194.100.0.7]) by faui45.informatik.uni-erlangen.de (8.9.1/8.1.49-FAU) with ESMTP id RAA26836 for ; Thu, 8 Jun 2000 17:18:54 +0200 (MET DST) Received: (from majordom@localhost) by mail.clinet.fi (8.9.3/8.9.3) id PAA05166 for ietf-ssh-outgoing; Thu, 8 Jun 2000 15:45:56 +0300 Received: from cdc-info.cdc.informatik.tu-darmstadt.de (cdc-info.cdc.informatik.tu-darmstadt.de [130.83.23.100]) by mail.clinet.fi (8.9.3/8.9.3) with ESMTP id PAA05050 for ; Thu, 8 Jun 2000 15:45:33 +0300 Received: from cdc1.cdc.informatik.tu-darmstadt.de (cdc1 [130.83.23.10]) by cdc-info.cdc.informatik.tu-darmstadt.de (Postfix) with ESMTP id 4ABAF2C4C; Thu, 8 Jun 2000 14:45:26 +0200 (MET DST) Received: by cdc1.cdc.informatik.tu-darmstadt.de (8.8.8+Sun/SMI-SVR4) id OAA00652; Thu, 8 Jun 2000 14:45:25 +0200 (MET DST) Date: Thu, 8 Jun 2000 14:45:23 +0200 From: Bodo Moeller To: Mika Kojo Cc: ietf-ssh@clinet.fi Subject: Re: Diffie-Hellman Group Exchange Message-ID: <20000608144523.A642@cdc.informatik.tu-darmstadt.de> References: <20000606205204.3E2CD207C1@citi.umich.edu> <200006062307.CAA21153@torni.hel.fi.ssh.com> <20000607170746.A431@cdc.informatik.tu-darmstadt.de> <200006080411.HAA17939@torni.hel.fi.ssh.com> <20000608110158.B861@cdc.informatik.tu-darmstadt.de> <200006081101.OAA15283@torni.hel.fi.ssh.com> <20000608134347.A544@cdc.informatik.tu-darmstadt.de> <200006081230.PAA01781@torni.hel.fi.ssh.com> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii X-Mailer: Mutt 1.0i In-Reply-To: <200006081230.PAA01781@torni.hel.fi.ssh.com>; from mkojo@ssh.com on Thu, Jun 08, 2000 at 03:30:56PM +0300 Sender: owner-ietf-ssh@clinet.fi Precedence: bulk Content-Length: 1229 Lines: 21 On Thu, Jun 08, 2000 at 03:30:56PM +0300, Mika Kojo wrote: >> If the protocol defines that only prime order subgroups may be used >> (and if everone follows the specification), then there's no problem. >> But if other subgroups are allowed, then problems can arise if the >> client decides to optimize by choosing the exponent smaller than >> ord(g). If DH parameters include a (minimum) exponent length >> in addition to or instead of ord(g), then such problems are avoided. > I see the problem. Yet I think it is one reason more for using prime > subgroups. Not that one length field would cause much concern, though. If the length field is not included, then it is a reason for using prime order subgroups (and not only for using them in specific cases, but for specifying that they *must* be used) -- however, such a solution without length field would not be fool-proof: If someone for efficiency reason violates the specification that the subgroup order must be prime, then the assumption that exponents of a certain length are safe may no longer be true. Thus it's safer to include a recommended exponent length, and if this is done, there's no longer a compelling reason to always insist on prime-order subgroups. From owner-ietf-ssh@clinet.fi Thu Jun 8 17:43:08 2000 Return-Path: Received: from faui45.informatik.uni-erlangen.de (root@faui45.informatik.uni-erlangen.de [131.188.34.45]) by faui01.informatik.uni-erlangen.de (8.8.8/8.1.16-FAU) with ESMTP id RAA22319 for ; Thu, 8 Jun 2000 17:43:07 +0200 (MET DST) Received: from mail.clinet.fi (mail.clinet.fi [194.100.0.7]) by faui45.informatik.uni-erlangen.de (8.9.1/8.1.49-FAU) with ESMTP id RAA29272 for ; Thu, 8 Jun 2000 17:43:03 +0200 (MET DST) Received: (from majordom@localhost) by mail.clinet.fi (8.9.3/8.9.3) id PAA07537 for ietf-ssh-outgoing; Thu, 8 Jun 2000 15:56:23 +0300 Received: from jpmorgan.com (threshold3.jpmorgan.com [169.71.1.12]) by mail.clinet.fi (8.9.3/8.9.3) with ESMTP id PAA05352; Thu, 8 Jun 2000 15:46:49 +0300 Received: (from uucp@localhost) by jpmorgan.com (8.8.5/8.8.5) id IAA16397; Thu, 8 Jun 2000 08:46:39 -0400 (EDT) Received: from jpmmailhost4.ny.jpmorgan.com(198.75.231.102) by threshold3.jpmorgan.com via smap (V4.2) id xma016287; Thu, 8 Jun 00 08:46:29 -0400 Received: from nyc-ntgw-n01.ny.jpmorgan.com (nyc_smtpmta_02.ny.jpmorgan.com [146.149.150.22]) by jpmmailhost4.ny.jpmorgan.com (8.9.1a/8.9.1) with SMTP id IAA17174; Thu, 8 Jun 2000 08:46:26 -0400 (EDT) Received: by nyc-ntgw-n01.ny.jpmorgan.com(Lotus SMTP MTA v4.6.4 (830.2 3-23-1999)) id 852568F8.00462A99 ; Thu, 8 Jun 2000 08:46:23 -0400 X-Lotus-FromDomain: JPMORGAN@SMTP From: "Noel L Yap" To: nisse@lysator.liu.se cc: Ietf-Ssh@clinet.fi, Psst@Net.Lut.Ac.Uk, Ssh@clinet.fi Message-ID: <852568F8.00462942.00@nyc-ntgw-n01.ny.jpmorgan.com> Date: Thu, 8 Jun 2000 08:46:20 -0400 Subject: Re: Using SRP as a key exchange metod in Secure Shell Mime-Version: 1.0 Content-type: text/plain; charset=us-ascii Content-Disposition: inline Sender: owner-ietf-ssh@clinet.fi Precedence: bulk Content-Length: 2118 Lines: 55 nisse@lysator.liu.se on 06/08/2000 07:23:32 AM >"Noel L Yap" writes: > >> OK, I've read this, but since I'm a bit of a newbie, I have a couple of >> questions: >> 1. Can the SRP authentication be used to authenticate the client to the host >> without the use of assymetric keys? I understand that this may not be as secure >> (since passwords generally have less entropy than keys), but in some situations, >> the convenience is worth the risk. > >Yes. > >One way to look at SRP is to view it like a assymetric system where >the user's private key is derived from a password. But the >host-authentication part of it really uses the verifier as a shared >(symmetric) secret. > >> 2. What effects would such a change have on ssh-agent and ssh-add? > >You would either have to type the SRP password each time, or tell the >agent about it. Or just get the hostkey and use the traditional host- >and userauthentication mechanisms in ssh. > >Note that LSH doesn't (yet) have anything like ssh-agent or ssh-add. >I'm expecting the gateway feature (once that is implemented) to be >able to replace aah-agent in many cases. See >http://www.lysator.liu.se/~nisse/lsh/doc/gateway-mode.txt for some >ideas about that. This is great! I prefer using SSH to secure CVS, but I don't really like the key management issue (since I really have to trust the clients not to put the keys in a safe place (and, sometimes, unsafe places aren't so obviously unsafe); I would much rather trust them keeping their passphrases secret). Now, what's the expected time frame or turn-around time for such a project? Thanks, Noel This communication is for informational purposes only. It is not intended as an offer or solicitation for the purchase or sale of any financial instrument or as an official confirmation of any transaction. All market prices, data and other information are not warranted as to completeness or accuracy and are subject to change without notice. Any comments or statements made herein do not necessarily reflect those of J.P. Morgan & Co. Incorporated, its subsidiaries and affiliates. From owner-ietf-ssh@clinet.fi Sat Jun 10 03:57:32 2000 Return-Path: Received: from faui45.informatik.uni-erlangen.de (root@faui45.informatik.uni-erlangen.de [131.188.34.45]) by faui01.informatik.uni-erlangen.de (8.8.8/8.1.16-FAU) with ESMTP id DAA23821 for ; Sat, 10 Jun 2000 03:57:32 +0200 (MET DST) Received: from mail.clinet.fi (mail.clinet.fi [194.100.0.7]) by faui45.informatik.uni-erlangen.de (8.9.1/8.1.49-FAU) with ESMTP id DAA11962 for ; Sat, 10 Jun 2000 03:57:31 +0200 (MET DST) Received: (from majordom@localhost) by mail.clinet.fi (8.9.3/8.9.3) id DAA27912 for ietf-ssh-outgoing; Sat, 10 Jun 2000 03:04:05 +0300 Received: from syrinx.oankali.net (syrinx.oankali.net [206.243.169.50]) by mail.clinet.fi (8.9.3/8.9.3) with ESMTP id DAA27909 for ; Sat, 10 Jun 2000 03:04:04 +0300 Received: (from res@localhost) by syrinx.oankali.net (8.9.3/8.9.3) id UAA09375; Fri, 9 Jun 2000 20:01:30 -0400 Date: Fri, 9 Jun 2000 20:01:30 -0400 Message-Id: <200006100001.UAA09375@syrinx.oankali.net> From: "Richard E. Silverman" To: ietf-ssh@clinet.fi Subject: KEXINIT "cookie" (SSH-TRANS) Sender: owner-ietf-ssh@clinet.fi Precedence: bulk Content-Length: 651 Lines: 19 In the SSH-TRANS document, the format of a KEXINIT message includes a 16-byte random cookie, about which is said: The cookie MUST be a random value generated by the sender. Its purpose is to make it impossible for either side to fully determine the keys and the session identifier. After this, though, I can't find any mention of the cookie at all, so it appears not to be used. Can anyone comment on this? Also, this is my first message on this list. If there is a list archive available, or a collection of protocol analyses and comments, I'd be happy to be directed to them. Thanks, - Richard Silverman slade@shore.net From owner-ietf-ssh@clinet.fi Sat Jun 10 13:06:35 2000 Return-Path: Received: from faui45.informatik.uni-erlangen.de (root@faui45.informatik.uni-erlangen.de [131.188.34.45]) by faui01.informatik.uni-erlangen.de (8.8.8/8.1.16-FAU) with ESMTP id NAA12161 for ; Sat, 10 Jun 2000 13:06:34 +0200 (MET DST) Received: from mail.clinet.fi (mail.clinet.fi [194.100.0.7]) by faui45.informatik.uni-erlangen.de (8.9.1/8.1.49-FAU) with ESMTP id NAA00316 for ; Sat, 10 Jun 2000 13:06:33 +0200 (MET DST) Received: (from majordom@localhost) by mail.clinet.fi (8.9.3/8.9.3) id MAA30142 for ietf-ssh-outgoing; Sat, 10 Jun 2000 12:14:10 +0300 Received: from samantha.lysator.liu.se (root@samantha.lysator.liu.se [130.236.254.202]) by mail.clinet.fi (8.9.3/8.9.3) with ESMTP id MAA30139 for ; Sat, 10 Jun 2000 12:14:09 +0300 Received: from sture.lysator.liu.se (nisse@sture.lysator.liu.se [130.236.254.21]) by samantha.lysator.liu.se (8.9.3/8.9.3) with ESMTP id LAA18307; Sat, 10 Jun 2000 11:13:31 +0200 (MET DST) Received: (from nisse@localhost) by sture.lysator.liu.se (8.9.0/8.8.7) id LAA04569; Sat, 10 Jun 2000 11:13:27 +0200 (MET DST) To: "Richard E. Silverman" Cc: ietf-ssh@clinet.fi Subject: Re: KEXINIT "cookie" (SSH-TRANS) References: <200006100001.UAA09375@syrinx.oankali.net> From: nisse@lysator.liu.se (Niels Möller) Date: 10 Jun 2000 11:13:27 +0200 In-Reply-To: "Richard E. Silverman"'s message of "Fri, 9 Jun 2000 20:01:30 -0400" Message-ID: X-Mailer: Gnus v5.7/Emacs 20.5 Sender: owner-ietf-ssh@clinet.fi Precedence: bulk Content-Length: 1446 Lines: 35 "Richard E. Silverman" writes: > In the SSH-TRANS document, the format of a KEXINIT message includes a > 16-byte random cookie, about which is said: > > The cookie MUST be a random value generated by the sender. Its > purpose is to make it impossible for either side to fully > determine the keys and the session identifier. > > After this, though, I can't find any mention of the cookie at all, so it > appears not to be used. Can anyone comment on this? It's included in the exchange hash, as part of "I_C" and "I_S": : The hash H is computed as the HASH hash of the concatenation of the : following: : : string V_C, the client's version string (CR and NL excluded) : string V_S, the server's version string (CR and NL excluded) : string I_C, the payload of the client's SSH_MSG_KEXINIT : string I_S, the payload of the server's SSH_MSG_KEXINIT : string K_S, the host key : mpint e, exchange value sent by the client : mpint f, exchange value sent by the server : mpint K, the shared secret So both host and user authentication depends on the random cookies. Perhaps they are not terribly important for the dh-keyexchange method, but for keyexchange methods where one of the parties doesn't contribute any random values (like in the RSA-based methods used in SSL and (I think) ssh-1), the cookies are needed to make replay attacks more difficult. /Niels From owner-ietf-ssh@clinet.fi Sat Jun 10 16:13:15 2000 Return-Path: Received: from faui45.informatik.uni-erlangen.de (root@faui45.informatik.uni-erlangen.de [131.188.34.45]) by faui01.informatik.uni-erlangen.de (8.8.8/8.1.16-FAU) with ESMTP id QAA20254 for ; Sat, 10 Jun 2000 16:13:14 +0200 (MET DST) Received: from mail.clinet.fi (mail.clinet.fi [194.100.0.7]) by faui45.informatik.uni-erlangen.de (8.9.1/8.1.49-FAU) with ESMTP id QAA06531 for ; Sat, 10 Jun 2000 16:13:13 +0200 (MET DST) Received: (from majordom@localhost) by mail.clinet.fi (8.9.3/8.9.3) id PAA10097 for ietf-ssh-outgoing; Sat, 10 Jun 2000 15:30:49 +0300 Received: from folly.informatik.uni-erlangen.de (IDENT:postfix@nbgdi5-145-253-148-002.arcor-ip.net [145.253.148.2]) by mail.clinet.fi (8.9.3/8.9.3) with ESMTP id PAA10094 for ; Sat, 10 Jun 2000 15:30:47 +0300 Received: by folly.informatik.uni-erlangen.de (Postfix, from userid 31451) id 3D117F9B; Sat, 10 Jun 2000 14:13:43 +0200 (CEST) Date: Sat, 10 Jun 2000 14:13:42 +0200 From: Markus Friedl To: "Richard E. Silverman" Cc: ietf-ssh@clinet.fi Subject: Re: KEXINIT "cookie" (SSH-TRANS) Message-ID: <20000610141342.A13373@folly.informatik.uni-erlangen.de> References: <200006100001.UAA09375@syrinx.oankali.net> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii X-Mailer: Mutt 1.0.1i In-Reply-To: <200006100001.UAA09375@syrinx.oankali.net>; from slade@shore.net on Fri, Jun 09, 2000 at 08:01:30PM -0400 Sender: owner-ietf-ssh@clinet.fi Precedence: bulk Content-Length: 751 Lines: 19 On Fri, Jun 09, 2000 at 08:01:30PM -0400, Richard E. Silverman wrote: > > In the SSH-TRANS document, the format of a KEXINIT message includes a > 16-byte random cookie, about which is said: > > The cookie MUST be a random value generated by the sender. Its > purpose is to make it impossible for either side to fully > determine the keys and the session identifier. > > After this, though, I can't find any mention of the cookie at all, so it > appears not to be used. Can anyone comment on this? the cookie is used when computing the 'hash H', since the full payload of KEXINIT messages is used: string I_C, the payload of the client's SSH_MSG_KEXINIT string I_S, the payload of the server's SSH_MSG_KEXINIT -markus From owner-ietf-ssh@clinet.fi Sun Jun 11 07:47:15 2000 Return-Path: Received: from faui45.informatik.uni-erlangen.de (root@faui45.informatik.uni-erlangen.de [131.188.34.45]) by faui01.informatik.uni-erlangen.de (8.8.8/8.1.16-FAU) with ESMTP id HAA26233 for ; Sun, 11 Jun 2000 07:47:14 +0200 (MET DST) Received: from mail.clinet.fi (mail.clinet.fi [194.100.0.7]) by faui45.informatik.uni-erlangen.de (8.9.1/8.1.49-FAU) with ESMTP id HAA04960 for ; Sun, 11 Jun 2000 07:47:13 +0200 (MET DST) Received: (from majordom@localhost) by mail.clinet.fi (8.9.3/8.9.3) id GAA01484 for ietf-ssh-outgoing; Sun, 11 Jun 2000 06:34:31 +0300 Received: from syrinx.oankali.net (syrinx.oankali.net [206.243.169.50]) by mail.clinet.fi (8.9.3/8.9.3) with ESMTP id GAA01478 for ; Sun, 11 Jun 2000 06:34:29 +0300 Received: (from res@localhost) by syrinx.oankali.net (8.9.3/8.9.3) id XAA10400; Sat, 10 Jun 2000 23:31:54 -0400 Date: Sat, 10 Jun 2000 23:31:53 -0400 (EDT) From: "Richard E. Silverman" X-Sender: res@syrinx.oankali.net Reply-To: "Richard E. Silverman" To: ietf-ssh@clinet.fi Subject: Re: KEXINIT "cookie" (SSH-TRANS) In-Reply-To: Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=X-UNKNOWN Content-Transfer-Encoding: 8bit X-MIME-Autoconverted: from QUOTED-PRINTABLE to 8bit by mail.clinet.fi id GAA01481 Sender: owner-ietf-ssh@clinet.fi Precedence: bulk Content-Length: 955 Lines: 27 On 10 Jun 2000, Niels Möller wrote: > It's included in the exchange hash, as part of "I_C" and "I_S": Oops! I missed that while looking for an explicit mention of the "cookie." Thanks! > but for keyexchange methods where one of the parties doesn't > contribute any random values (like in the RSA-based methods used in > SSL and (I think) ssh-1), Yes, in SSH-1 the client generates the session key entirely on its own and sends it to the server. > the cookies are needed to make replay attacks more difficult. It also prevents a trojaned client from picking gimmicked keys allowing the attacker to guess them (e.g. pick from a reduced keyspace, or with a special form, etc.). A trojaned client is a disaster in any event, but with SSH-2 it would have to find some way to signal the key to the attacker, and that might be noticed. In SSH-1, the trojaned client can behave entirely normally and the compromise will never be noticed. - Richard From owner-ietf-ssh@clinet.fi Mon Jun 12 20:47:36 2000 Return-Path: Received: from faui45.informatik.uni-erlangen.de (root@faui45.informatik.uni-erlangen.de [131.188.34.45]) by faui01.informatik.uni-erlangen.de (8.8.8/8.1.16-FAU) with ESMTP id UAA06420 for ; Mon, 12 Jun 2000 20:47:36 +0200 (MET DST) Received: from mail.clinet.fi (mail.clinet.fi [194.100.0.7]) by faui45.informatik.uni-erlangen.de (8.9.1/8.1.49-FAU) with ESMTP id UAA24476 for ; Mon, 12 Jun 2000 20:47:35 +0200 (MET DST) Received: (from majordom@localhost) by mail.clinet.fi (8.9.3/8.9.3) id TAA00328 for ietf-ssh-outgoing; Mon, 12 Jun 2000 19:55:00 +0300 Received: from samantha.lysator.liu.se (root@samantha.lysator.liu.se [130.236.254.202]) by mail.clinet.fi (8.9.3/8.9.3) with ESMTP id TAA00324 for ; Mon, 12 Jun 2000 19:54:59 +0300 Received: from sture.lysator.liu.se (nisse@sture.lysator.liu.se [130.236.254.21]) by samantha.lysator.liu.se (8.9.3/8.9.3) with ESMTP id SAA00033; Mon, 12 Jun 2000 18:54:57 +0200 (MET DST) Received: (from nisse@localhost) by sture.lysator.liu.se (8.9.0/8.8.7) id SAA29537; Mon, 12 Jun 2000 18:54:54 +0200 (MET DST) To: "Richard E. Silverman" Cc: ietf-ssh@clinet.fi Subject: Re: KEXINIT "cookie" (SSH-TRANS) References: From: nisse@lysator.liu.se (Niels Möller) Date: 12 Jun 2000 18:54:53 +0200 In-Reply-To: "Richard E. Silverman"'s message of "Sat, 10 Jun 2000 23:31:53 -0400 (EDT)" Message-ID: X-Mailer: Gnus v5.7/Emacs 20.5 Sender: owner-ietf-ssh@clinet.fi Precedence: bulk Content-Length: 1338 Lines: 30 "Richard E. Silverman" writes: > On 10 Jun 2000, Niels Möller wrote: > > > the cookies are needed to make replay attacks more difficult. > > It also prevents a trojaned client from picking gimmicked keys allowing > the attacker to guess them (e.g. pick from a reduced keyspace, or with a > special form, etc.). A trojaned client is a disaster in any event, but > with SSH-2 it would have to find some way to signal the key to the > attacker, and that might be noticed. I'm sure I can agree with that. A backdoored ssh2 client could just choose its "secret" DH-exponent from a small space, known to the attacker. If the attcker knows that the client chooses its exponent as a random number between, say, 1000 and 5000, he can get the session key by trying those few thousands of exponents exponents one by one. Or am I missing something? As far as I can see, using a bad randomness source (either by mistake, or by using a backdoored client), is as disastrous to ssh2 security as it is with ssh1 or SSL. There are also other ways information can be leaked. For instance, a backdoored client might use a very good randomness source for creating its cookie, and then choose a the secret exponent as HMAC(attacker's secret key, cookie). I think that would be very hard to detect by just observing the traffic. /Niels From owner-ietf-ssh@clinet.fi Mon Jun 12 22:44:16 2000 Return-Path: Received: from faui45.informatik.uni-erlangen.de (root@faui45.informatik.uni-erlangen.de [131.188.34.45]) by faui01.informatik.uni-erlangen.de (8.8.8/8.1.16-FAU) with ESMTP id WAA11260 for ; Mon, 12 Jun 2000 22:44:15 +0200 (MET DST) Received: from mail.clinet.fi (mail.clinet.fi [194.100.0.7]) by faui45.informatik.uni-erlangen.de (8.9.1/8.1.49-FAU) with ESMTP id WAA01319 for ; Mon, 12 Jun 2000 22:44:14 +0200 (MET DST) Received: (from majordom@localhost) by mail.clinet.fi (8.9.3/8.9.3) id VAA10390 for ietf-ssh-outgoing; Mon, 12 Jun 2000 21:42:40 +0300 Received: from mail.liu.se (wille.unit.liu.se [130.236.1.30]) by mail.clinet.fi (8.9.3/8.9.3) with ESMTP id VAA10387 for ; Mon, 12 Jun 2000 21:42:39 +0300 Received: from sture.lysator.liu.se (sture.lysator.liu.se [130.236.254.21]) by mail.liu.se (Postfix) with ESMTP id EB68B7B85; Mon, 12 Jun 2000 20:42:38 +0200 (MET DST) Received: (from nisse@localhost) by sture.lysator.liu.se (8.9.0/8.8.7) id UAA03563; Mon, 12 Jun 2000 20:42:38 +0200 (MET DST) To: "Richard E. Silverman" Cc: ietf-ssh@clinet.fi Subject: Re: KEXINIT "cookie" (SSH-TRANS) References: From: nisse@lysator.liu.se (Niels Möller) Date: 12 Jun 2000 20:42:38 +0200 In-Reply-To: nisse@lysator.liu.se's message of "12 Jun 2000 18:54:53 +0200" Message-ID: X-Mailer: Gnus v5.7/Emacs 20.5 Sender: owner-ietf-ssh@clinet.fi Precedence: bulk Content-Length: 1466 Lines: 33 Ooops. I missed a negation here. Sorry for any confusion. > "Richard E. Silverman" writes: > > > On 10 Jun 2000, Niels Möller wrote: > > > > > the cookies are needed to make replay attacks more difficult. > > > > It also prevents a trojaned client from picking gimmicked keys allowing > > the attacker to guess them (e.g. pick from a reduced keyspace, or with a > > special form, etc.). A trojaned client is a disaster in any event, but > > with SSH-2 it would have to find some way to signal the key to the > > attacker, and that might be noticed. > > I'm sure I can agree with that. A backdoored ssh2 client could just ^ not > choose its "secret" DH-exponent from a small space, known to the > attacker. If the attcker knows that the client chooses its exponent as > a random number between, say, 1000 and 5000, he can get the session > key by trying those few thousands of exponents exponents one by one. > > Or am I missing something? As far as I can see, using a bad randomness > source (either by mistake, or by using a backdoored client), is as > disastrous to ssh2 security as it is with ssh1 or SSL. > > There are also other ways information can be leaked. For instance, a > backdoored client might use a very good randomness source for creating > its cookie, and then choose a the secret exponent as HMAC(attacker's > secret key, cookie). I think that would be very hard to detect by just > observing the traffic. > > /Niels From owner-ietf-ssh@clinet.fi Wed Jun 14 12:15:59 2000 Return-Path: Received: from faui45.informatik.uni-erlangen.de (root@faui45.informatik.uni-erlangen.de [131.188.34.45]) by faui01.informatik.uni-erlangen.de (8.8.8/8.1.16-FAU) with ESMTP id MAA02870 for ; Wed, 14 Jun 2000 12:15:59 +0200 (MET DST) Received: from mail.clinet.fi (mail.clinet.fi [194.100.0.7]) by faui45.informatik.uni-erlangen.de (8.9.1/8.1.49-FAU) with ESMTP id MAA15413 for ; Wed, 14 Jun 2000 12:15:57 +0200 (MET DST) Received: (from majordom@localhost) by mail.clinet.fi (8.9.3/8.9.3) id JAA07623 for ietf-ssh-outgoing; Wed, 14 Jun 2000 09:53:05 +0300 Received: from syrinx.oankali.net (syrinx.oankali.net [206.243.169.50]) by mail.clinet.fi (8.9.3/8.9.3) with ESMTP id JAA07614 for ; Wed, 14 Jun 2000 09:53:03 +0300 Received: (from res@localhost) by syrinx.oankali.net (8.9.3/8.9.3) id CAA27510; Wed, 14 Jun 2000 02:50:16 -0400 Date: Wed, 14 Jun 2000 02:50:16 -0400 (EDT) From: "Richard E. Silverman" X-Sender: res@syrinx.oankali.net Reply-To: "Richard E. Silverman" To: SECSH Discussion List Subject: Re: KEXINIT "cookie" (SSH-TRANS) In-Reply-To: Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Sender: owner-ietf-ssh@clinet.fi Precedence: bulk Content-Length: 887 Lines: 23 Niels> Or am I missing something? ... Not at all. I had been thinking that the SSH-2 mechanism of generating the session key from the shared secret, rather than using the secret directly, would protect against this kind of attack, specifically when using an SSH-1 style encrypted key exchange in which the session key is chosen by the client. But your comments have shown me that I wasn't thinking clearly about it. Following the example the of the SSH-2 DH exchange, an SSH-1 style exchange in SSH-2 would probably have an exchange hash computed over the client-chosen secret plus a bunch of externally observable data. The attacker has everything he needs to compute actual session key from the compromised secret. It does require more observation and work than it would in SSH-1, but not enough to make any real difference. Thanks! -- Richard Silverman slade@shore.net From owner-ietf-ssh@clinet.fi Thu Jun 15 22:53:22 2000 Return-Path: Received: from faui45.informatik.uni-erlangen.de (root@faui45.informatik.uni-erlangen.de [131.188.34.45]) by faui02.informatik.uni-erlangen.de (8.9.1/8.1.16-FAU) with ESMTP id WAA06545 for ; Thu, 15 Jun 2000 22:53:21 +0200 (MET DST) Received: from mail.clinet.fi (mail.clinet.fi [194.100.0.7]) by faui45.informatik.uni-erlangen.de (8.9.1/8.1.49-FAU) with ESMTP id WAA18793 for ; Thu, 15 Jun 2000 22:53:20 +0200 (MET DST) Received: (from majordom@localhost) by mail.clinet.fi (8.9.3/8.9.3) id VAA12237 for ietf-ssh-outgoing; Thu, 15 Jun 2000 21:50:35 +0300 Received: from syrinx.oankali.net (syrinx.oankali.net [206.243.169.50]) by mail.clinet.fi (8.9.3/8.9.3) with ESMTP id VAA12234 for ; Thu, 15 Jun 2000 21:50:34 +0300 Received: (from res@localhost) by syrinx.oankali.net (8.9.3/8.9.3) id OAA04362; Thu, 15 Jun 2000 14:47:48 -0400 Date: Thu, 15 Jun 2000 14:47:48 -0400 Message-Id: <200006151847.OAA04362@syrinx.oankali.net> From: "Richard E. Silverman" To: SECSH Discussion List Subject: "ssh-rsa" public-key type Sender: owner-ietf-ssh@clinet.fi Precedence: bulk Content-Length: 526 Lines: 15 The commercial version of SSH2 from ssh.com supports RSA as well as DSA keys for publickey authentication. The key format name it uses for this is "ssh-rsa". Unlike "ssh-dss", though, this is not defined in the current draft standard. So I'm curious why this type isn't "ssh-rsa@ssh.com" instead -- has this global name been used in anticipation of its being added to the draft? btw, is there an archive of this mailing list? I went looking for one but didn't find it. Thanks, -- Richard Silverman slade@shore.net From owner-ietf-ssh@clinet.fi Sat Jun 17 03:44:56 2000 Return-Path: Received: from faui45.informatik.uni-erlangen.de (root@faui45.informatik.uni-erlangen.de [131.188.34.45]) by faui02.informatik.uni-erlangen.de (8.9.1/8.1.16-FAU) with ESMTP id DAA16410 for ; Sat, 17 Jun 2000 03:44:56 +0200 (MET DST) Received: from mail.clinet.fi (mail.clinet.fi [194.100.0.7]) by faui45.informatik.uni-erlangen.de (8.9.1/8.1.49-FAU) with ESMTP id DAA00535 for ; Sat, 17 Jun 2000 03:44:55 +0200 (MET DST) Received: (from majordom@localhost) by mail.clinet.fi (8.9.3/8.9.3) id CAA05926 for ietf-ssh-outgoing; Sat, 17 Jun 2000 02:38:24 +0300 Received: from asgard.tky.hut.fi (asgard.tky.hut.fi [130.233.29.146]) by mail.clinet.fi (8.9.3/8.9.3) with ESMTP id CAA05908 for ; Sat, 17 Jun 2000 02:38:22 +0300 Received: (from sjl@localhost) by asgard.tky.hut.fi (8.10.0/8.10.0) id e5GNaj132307; Sat, 17 Jun 2000 02:36:45 +0300 From: Sami Lehtinen MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Message-ID: <14666.47629.645249.255747@asgard.tky.hut.fi> Date: Sat, 17 Jun 2000 02:36:45 +0300 (EEST) To: "Richard E. Silverman" Cc: SECSH Discussion List Subject: "ssh-rsa" public-key type In-Reply-To: <200006151847.OAA04362@syrinx.oankali.net> References: <200006151847.OAA04362@syrinx.oankali.net> X-Mailer: VM 6.72 under 21.1 (patch 9) "Canyonlands" XEmacs Lucid Sender: owner-ietf-ssh@clinet.fi Precedence: bulk Content-Length: 1077 Lines: 26 Richard E. Silverman writes: : : The commercial version of SSH2 from ssh.com supports RSA as well as DSA keys : for publickey authentication. The key format name it uses for this is : "ssh-rsa". Unlike "ssh-dss", though, this is not defined in the current draft : standard. So I'm curious why this type isn't "ssh-rsa@ssh.com" instead -- has : this global name been used in anticipation of its being added to the draft? "ssh-rsa" is supposed to be added to the draft as soon as the patent expires. The only implementation (to my knowledge) that uses this is the one that F-Secure distributes. Our (SSH Communications Security) distribution shouldn't include that algorithm. If it does, it is a serious bug :) : btw, is there an archive of this mailing list? I went looking for one but : didn't find it. Sorry, I don't know of any. Regards, -- [sjl@ssh.com -- Sami J. Lehtinen -- sjl@iki.fi] [work:+358 9 85657425][gsm:+358 50 5170 258][http://www.iki.fi/~sjl] [SSH Communications Security Corp http://www.ssh.com/] From owner-ietf-ssh@clinet.fi Sat Jun 17 05:07:52 2000 Return-Path: Received: from faui45.informatik.uni-erlangen.de (root@faui45.informatik.uni-erlangen.de [131.188.34.45]) by faui02.informatik.uni-erlangen.de (8.9.1/8.1.16-FAU) with ESMTP id FAA22395 for ; Sat, 17 Jun 2000 05:07:52 +0200 (MET DST) Received: from mail.clinet.fi (mail.clinet.fi [194.100.0.7]) by faui45.informatik.uni-erlangen.de (8.9.1/8.1.49-FAU) with ESMTP id FAA03440 for ; Sat, 17 Jun 2000 05:07:51 +0200 (MET DST) Received: (from majordom@localhost) by mail.clinet.fi (8.9.3/8.9.3) id EAA12546 for ietf-ssh-outgoing; Sat, 17 Jun 2000 04:07:37 +0300 Received: from syrinx.oankali.net (syrinx.oankali.net [206.243.169.50]) by mail.clinet.fi (8.9.3/8.9.3) with ESMTP id EAA12543 for ; Sat, 17 Jun 2000 04:07:36 +0300 Received: (from res@localhost) by syrinx.oankali.net (8.9.3/8.9.3) id VAA05319; Fri, 16 Jun 2000 21:04:46 -0400 Date: Fri, 16 Jun 2000 21:04:46 -0400 (EDT) From: "Richard E. Silverman" X-Sender: res@syrinx.oankali.net Reply-To: "Richard E. Silverman" To: SECSH Discussion List Subject: Re: "ssh-rsa" public-key type In-Reply-To: <14666.47629.645249.255747@asgard.tky.hut.fi> Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Sender: owner-ietf-ssh@clinet.fi Precedence: bulk Content-Length: 499 Lines: 18 > "ssh-rsa" is supposed to be added to the draft as soon as the patent > expires. Ah, that makes sense. > The only implementation (to my knowledge) that uses this is the one > that F-Secure distributes. Our (SSH Communications Security) > distribution shouldn't include that algorithm. If it does, it is a > serious bug :) Sorry, you're right; it is the F-Secure commercial product I was looking at. Too many SSH versions sitting on my machines. :) -- Richard Silverman slade@shore.net From owner-ietf-ssh@clinet.fi Wed Jun 21 15:40:19 2000 Return-Path: Received: from faui45.informatik.uni-erlangen.de (root@faui45.informatik.uni-erlangen.de [131.188.34.45]) by faui02.informatik.uni-erlangen.de (8.9.1/8.1.16-FAU) with ESMTP id PAA01472 for ; Wed, 21 Jun 2000 15:40:19 +0200 (MET DST) Received: from mail.clinet.fi (mail.clinet.fi [194.100.0.7]) by faui45.informatik.uni-erlangen.de (8.9.1/8.1.49-FAU) with ESMTP id PAA20084 for ; Wed, 21 Jun 2000 15:40:17 +0200 (MET DST) Received: (from majordom@localhost) by mail.clinet.fi (8.9.3/8.9.3) id OAA04917 for ietf-ssh-outgoing; Wed, 21 Jun 2000 14:24:15 +0300 Received: from cdc-info.cdc.informatik.tu-darmstadt.de (cdc-info.cdc.informatik.tu-darmstadt.de [130.83.23.100]) by mail.clinet.fi (8.9.3/8.9.3) with ESMTP id OAA04911 for ; Wed, 21 Jun 2000 14:24:13 +0300 Received: from cdc1.cdc.informatik.tu-darmstadt.de (cdc1 [130.83.23.10]) by cdc-info.cdc.informatik.tu-darmstadt.de (Postfix) with ESMTP id B3EAC2C4E; Wed, 21 Jun 2000 13:24:09 +0200 (MET DST) Received: by cdc1.cdc.informatik.tu-darmstadt.de (8.8.8+Sun/SMI-SVR4) id NAA02033; Wed, 21 Jun 2000 13:24:08 +0200 (MET DST) Date: Wed, 21 Jun 2000 13:24:08 +0200 From: Bodo Moeller To: =?iso-8859-1?Q?Niels_M=F6ller?= Cc: Ben Laurie , Coderpunks , Cryptography , ietf-ssh@clinet.fi Subject: Re: Extracting Entropy? Message-ID: <20000621132407.C1946@cdc.informatik.tu-darmstadt.de> References: <394E92AA.B40A2274@algroup.co.uk> <20000621120841.A1798@cdc.informatik.tu-darmstadt.de> Mime-Version: 1.0 Content-Type: text/plain; charset=iso-8859-1 Content-Transfer-Encoding: 8bit X-Mailer: Mutt 1.0i In-Reply-To: ; from nisse@lysator.liu.se on Wed, Jun 21, 2000 at 12:19:50PM +0200 Sender: owner-ietf-ssh@clinet.fi Precedence: bulk Content-Length: 2317 Lines: 58 On Wed, Jun 21, 2000 at 12:19:50PM +0200, Niels Möller wrote: > Bodo Moeller writes: >> On Tue, Jun 20, 2000 at 07:50:11PM +0200, Niels Möller wrote: >>> That is specified in draft-ietf-secsh-transport-07.txt, the >>> relevant section is >>> >>>: If the key length in longer than the output >>>: of the HASH, the key is extended by computing HASH of the concatenation >>>: of K and H and the entire key so far, and appending the resulting bytes >>>: (as many as HASH generates) to the key. This process is repeated until >>>: enough key material is available; the key is taken from the beginning of >>>: this value. In other words, >>>: >>>: K1 = HASH(K || H || X || session_id) (X is e.g. "A") >>>: K2 = HASH(K || H || K1) >>>: K3 = HASH(K || H || K1 || K2) >>>: ... >>>: key = K1 || K2 || K3 || ... >>> >>> Here, K is the secret being stretched, and H is an "exchange hash" >>> that can probably be ignored in this context. The X is different for >>> the keys that are generated from the same secret. >> With usual hash functions (Merkle/Damgård construction), you're >> wasting entropy if there are more than 2^B possible values for K >> where B is the size of the output of the compression function. >> The reason is that the hash construct always has the same internal >> state when K is hashed in. > Ah, thanks, I had not realized that. In the ssh case, the hash > function used is sha1, and the internal state is 512 bits. Isn't the chaining size just 160 bits, like the output? The input is processed in larger chunks, but that doesn't mean that the state is that large too. >> This problem would be avoided by setting >> >> K1 = HASH(K || H || X || session_id) (X is e.g. "A") >> K2 = HASH(K1 || H || K) >> K3 = HASH(K2 || H || K) >> ... >> key = K1 || K2 || K3 || ... >> >> because in this variant K is applied at different states of the hash >> construct. > Do you think this is a point worth raising on the ietf-ssh list? Cc: added. -- Bodo Möller 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