Subject: Another DH approach

From: "Douglas E. Engert" <[email-masked]>
Date: Wed, 04 Dec 2002 15:14:57 -0600

How about this:

k is the user's key, or some function of the user's key.

Alice:   X = g^x mod n
Bob:     Y = g^y mod n

X, Y exchanged, g and n well known.

Alice computes:  K  = Y^xk mod n
Bob computes     K' = X^yk mod n

K = K' = g^xyk mod n

The MITH can not compute the same key, as he does not have k.

But this looks to simple. Any one see any problems?
Have I reinvented another algorithm?

  

-- 

 Douglas E. Engert  <[email-masked]>
 Argonne National Laboratory
 9700 South Cass Avenue
 Argonne, Illinois  60439 
 (630) 252-5444

---

From: Derek Atkins <[email-masked]>
Date: 04 Dec 2002 18:51:37 -0500

I was sort of referring to this earlier.  The only problem is that in
the case of a MitM trying to mount a dictionary attack all they need
to to is take the normally-computed K = g^xy and then try their
dictionary of possible values of k...

Granted, this required one mod-mult per attempt so it is rather
expensive, but it does still allow an offline dictionary attack.

-derek

PS: This is why designing crypto protocols is _hard_ ;)

-- 
       Derek Atkins
       Computer and Internet Security Consultant
       [email-masked]             www.ihtfp.com

---

From: "Douglas E. Engert" <[email-masked]>
Date: Wed, 04 Dec 2002 19:19:52 -0600

> expensive, but it does still allow an offline dictionary attack.

OK, I see now that this is the same as solving for k in K=g^zk mod n

> PS: This is why designing crypto protocols is _hard_ ;)

I agree, that is why people want to patent these things, to make money!

--

---

From: Marcus Watts <[email-masked]>
Date: Thu, 05 Dec 2002 12:53:47 -0500

I liked Doug's "another DH approach".  Maybe I'm missing something
about what Derek says, but I think that what he says only works with an
active attack (see below...)

In any event, I think using it with large primes brings a whole bunch
of unpleasant issues, and that this works out much better with elliptic
curve encryption.  One nice thing about elliptic curve encryption is
that turning random values such as password hashes into keys is
trivial.  Another attractive thing about using elliptic curves here is
they're not protecting any intrinsically valuable long-term data; if a
weakness is found, it's relatively simple to upgrade protocols or
encourage users to change passwords; also, at worst, this should be no
worse than not using preauth.

The following is really just Doug's approach using elliptic curve
encryption.  This uses the same notation as [mrosing]; if you use the
rest of his code (I hacked up his MQV example from pages 188-197 using
sample source from his web page although I assume the code in the book
is capable of the same result) you should get the same or similar
results:

Given global parameters:
	CURVE		IPSEC;
	POINT		Base_Point;
produced by code such as:
	INDEX		error;
	random_seed = 0x1932b5fe;
	
	if (!irreducible(&poly_prime)) return(0);
	print_field("poly_prime = ", &poly_prime);
	
	if (error = init_poly_math())
	{
		printf("Can't initialize S matrix, row = %d\n", error);
		return(-1);
	}
	
	printf("create Base curve and point\n\n");

	rand_curve(&Base_curve);
	print_curve("Public curve", &Base_curve);
	rand_point(&Base_Point, &Base_curve);
	print_point("Base point", &Base_Point);
which might result in:
	poly_prime = 
	    8000        0        0      401 
	create Base curve and point

	Public curve
	form: 0
	a6: 7876 fc01a2ea 920ff4e4 789cf04b 

	Base point
	x:     1302  1d486c8 cf0ec27f ab882021 
	y:     1f1b 30f158f0 70be9ec3 ad09ad02 

and ephemeral key pairs (which could be the kdc & a client):
	struct side {
		FIELD2N private;
		POINT public;
	} side1[1], side2[1];
using logic like:
	printf("\ncreate each sides private key\n\n");
	random_field(&side1->private);
	print_field("Side 1 secret:", &side1->private);
	random_field(&side2->private);
	print_field("Side 2 secret:", &side2->private);
	printf("\nGenerate each sides public key\n\n");
	poly_elptic_mul( &side1->private, &Base_Point, &side1->public, &Base_curve);
	print_point("Side 1 public key", &side1->public);
	poly_elptic_mul( &side2->private, &Base_Point, &side2->public, &Base_curve);
	print_point("Side 2 public key", &side2->public);
which might result in:
	create each sides private key

	Side 1 secret:
	    5bea 99f1b1a7 9ed55546 6cfa64f5 
	Side 2 secret:
	    5064 4411772e 19516028  a282eb1 

	Generate each sides public key

	Side 1 public key
	x:     50f7 6eb251d0 10bd7ea3 63bcfd0e 
	y:     6291 4c5efee2 d929960c f67bf3f6 
	Side 2 public key
	x:     484b cfa50539 cb4c7304 401ee771 
	y:     752c 7e1396f0 d4bb991e 9ff7ff17 
and a shared hash
	FIELD2N	shared_hash;
which in this case I just used a random value, but in practice this
would be more than likely be either a straight password hash suitably
truncated, expanded, or otherwise mashed:
	random_field(&shared_hash);
	print_field("Shared hash:", &shared_hash);
such as:
	Shared hash:
	    1500  adbf0aa ddc0cead 57fb0487 
The two sides now exchange public keys, in the clear.  Each side, given
the shared hash and the other side's public key
can compute equivalent shared secrets:
	POINT		Shared_Secret1, Shared_Secret2;
using a temp
	POINT		temp;
this way:
	printf("\nExchange data and compute shared secret\n\n");

	poly_elptic_mul( &shared_hash, &side2->public, &temp, &Base_curve);
	poly_elptic_mul( &side1->private, &temp, &Shared_Secret1, &Base_curve);
	print_point("Side 1 shared secret", &Shared_Secret1);

	poly_elptic_mul( &shared_hash, &side1->public, &temp, &Base_curve);
	poly_elptic_mul( &side2->private, &temp, &Shared_Secret2, &Base_curve);
	print_point("Side 2 shared secret", &Shared_Secret2);
resulting in something like this:
	Exchange data and compute shared secret

	Side 1 shared secret
	x:     639b baf01fb2 8b64fdc0 1a04d137 
	y:     6112 6e76731f 71a7ebeb 4a53cbfd 
	Side 2 shared secret
	x:     639b baf01fb2 8b64fdc0 1a04d137 
	y:     6112 6e76731f 71a7ebeb 4a53cbfd 

The code to do the above is short -- my test program was 20K, and
totaled only 1800 lines of code (which other than the above is just
mrosing's stuff...)  I believe little more than this is needed.  The
curve & all can be selected way ahead of time and treated like des
s-boxes - a constant of the implementation (which would save runtime
code space too).  To ship points across the wire it is useful to do
point compression
	(basically, given point x,y; there are only 2 y's for any
	possible x, so x + 1 bit suffices to represent a point.)
That's not necessary for this, but it saves some space, and if a more
complicated algorithm were desired, compressed points with suitable
noise have a cryptographic advantage (less redundancy).  To tie this
into a complete protocol, some notion of proofs should be exchanged--
such as using a double hash of the first result on the wire (client
proves to kdc it knows the pw) and a single hash to return the
encrypted key (kdc proves to client it knows the pw too.)

Since a passive Mitm attacker shouldn't know either side's ephemeral
secret key, he shouldn't have enough to try to derive the shared
secret.  The only kind of Mitm attack I can think of is an active one;
someone posing as a KDC could supply a different public key and gain
enough information to do an offline crack, at the cost of breaking one
authentication attempt in the process  I don't see any way to stop this
sort of active attack without storing *some* sort of kdc verification
information on the client, such as storing a public key information in
/etc/krb5.conf, or using a keytab.  [Although Schneier's fortified key
exchange idea might have merit here.]  Does anyone seriously hope to
stop or discourage this kind of attack?

I believe this is not subject to the Lucent EKE patents, since it
doesn't use symmetric encryption.  It's certainly not what Jablon calls
DH-EKE at any rate.  It should also be separate from Jablon's SPEKE
since this doesn't use a one-way hash on the output and the pw.

It's still necessary to to see if this is secure, and to do some sort
of bloody patent search.  For that matter a lawyer might see something
in the Lucent patents that I failed to understand.  I'd like to claim
that the above is at least "obvious" (it was at least obvious to me, I
didn't actually bother to read Doug's message until I went home and
thought about something somebody said about a 3-way DH exchange and
came up with the above code) but it might be worth patenting all the
same and assigning it to something willing to grant a universal
unrestricted free license yet fight court cases to keep it free, merely
to create a legal entity with standing.

					-Marcus Watts
					UM ITCS Umich Systems Group

[mrosing]
Michael Rosing
_Implementing Elliptic Curve Cryptography_
1999 Manning isbn 1-884777-69-4

---

From: Sam Hartman <[email-masked]>
Date: Thu, 05 Dec 2002 15:25:07 -0500

>>>>> "Marcus" == Marcus Watts <[email-masked]> writes:

    Marcus> In any event, I think using it with large primes brings a
    Marcus> whole bunch of unpleasant issues, and that this works out
    Marcus> much better with elliptic curve encryption.  One nice
    Marcus> thing about elliptic curve encryption is that turning
    Marcus> random values such as password hashes into keys is
    Marcus> trivial.  Another attractive thing about using elliptic
    Marcus> curves here is they're not protecting any intrinsically
    Marcus> valuable long-term data; if a weakness is found, it's
    Marcus> relatively simple to upgrade protocols or encourage users
    Marcus> to change passwords; also, at worst, this should be no
    Marcus> worse than not using preauth.

I thought there were significant patent issues with elliptic curves.
If we're going to use a patented technology let's use EKE and be done
with the problem.

---

From: Marcus Watts <[email-masked]>
Date: Thu, 05 Dec 2002 17:48:13 -0500

> If we're going to use a patented technology let's use EKE and be done

I think there's patent problems with everything.  My understanding
about elliptic curves is that there isn't any global patent over
everything (like RSA) but that many specific things had patents.
Figuring out which specific thing is an issue may be a problem, but I
don't think that's reason to avoid the whole area - usually there are
enough other ways to do it that a specific patent may not be that big
an issue.  There really are some attractive benefits - and I'm not at
all convinced the problem is any worse than with anything else.

The latest version of openssl seems to have an elliptic curve library
built in.  It might be worth checking out the use of that; I heard
rumours of sun patent issues, but if they're distributing code perhaps
that's all resolved now.

					-Marcus Watts

---

From: Sam Hartman <[email-masked]>
Date: Thu, 05 Dec 2002 18:24:48 -0500

>>>>> "Marcus" == Marcus Watts <[email-masked]> writes:

    Marcus> I think there's patent problems with everything.  My
    Marcus> understanding about elliptic curves is that there isn't
    Marcus> any global patent over everything (like RSA) but that many
    Marcus> specific things had patents.  Figuring out which specific
    Marcus> thing is an issue may be a problem, but I don't think
    Marcus> that's reason to avoid the whole area - usually there are
    Marcus> enough other ways to do it that a specific patent may not
    Marcus> be that big an issue.  There really are some attractive
    Marcus> benefits - and I'm not at all convinced the problem is any
    Marcus> worse than with anything else.

I think that if you come up with a specific suggestion you believe has
no patent issues we should evaluate that suggestion.  People I've
talked to seem to think that will be a difficult task, so I'm
reluctant to focus any effort on it unless I have strong reason to
believe there aren't patent problems.

    Marcus> The latest version of openssl seems to have an elliptic
    Marcus> curve library built in.  It might be worth checking out
    Marcus> the use of that; I heard rumours of sun patent issues, but
    Marcus> if they're distributing code perhaps that's all resolved
    Marcus> now.

OpenSSL has included problematic ciphers in the past.