[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Is my DH exchange secure?
-----BEGIN PGP SIGNED MESSAGE-----
[email protected] describes some of the precautions required to use DH
exchange safely:
** begin quoted text ***
The prime p wants to be chosen with a little care,
and the "random" numbers a and b may want to be "selected" to
eliminate certain undesirable values. I'll explain below.
Within the field Z_p (the set of integers 0..p-1) where p is prime,
there are elements whose successive powers make up all the elements of
the field Z_p. These numbers are called "primitive" elements or
"generators" of the field Z_p. That is, if g is a generator of the field
Z_p, then the successive powers g, g^2, g^3, ... g^(p-2), g^(p-1) mod p
include all the p-1 non-zero elements of Z_p.
The set of unique numbers produced by taking succesive powers mod p of an
element m of Z_p is a group, the "multiplicative span" of m, which is a
subgroup of Z_p. The number of elements in the group generated by m
is called the "order" of m. Primitive elements of Z_p have order p-1.
Not all of the elements of Z_p are primitive.
Some elements of Z_p have very small orders.
At least one element will have order 2.
Given that p is prime, the orders of the elements of Z_p will all have
values that are products of some or all of the prime factors of p-1.
Since p is prime (and p=2 is not interesting ;-), p-1 will contain the
factor 2.
An small example may make this point clear. Let p == 11.
The prime factors of p-1 are 2 and 5. Hence we expect the orders of
the elements of Z_11 to be 2, 5, or 10. By enumerating the groups of
the elements of Z_11 we see this is so (for Z_11). E.g.
Element Ring Order
- ------ ----------------------------- -----
1 1 1
2 2, 4, 8, 5, 10, 9, 7, 3, 6, 1 10
3 3, 9, 5, 4, 1 5
4 4, 5, 9, 3, 1 5
5 5, 3, 4, 9, 1 5
6 6, 3, 7, 9, 10, 5, 8, 4, 2, 1 10
7 7, 5, 2, 3, 10, 4, 6, 9, 8, 1 10
8 8, 9, 6, 4, 10, 3, 2, 5, 7, 1 10
9 9, 4, 3, 5, 1 5
10 10, 1 2
There are 4 primitive elements in Z_11, 2, 6, 7, & 8.
The orders of all the elements are as predicted by Euler.
Now, let us imagine that Alice and Bob have chosen 11 as their prime
and 7 as "g", their generator.
Following the steps outlined above:
> Alice generates a random number a.
say 3
> Bob generates a random number b.
say 5.
> Bob tells alice g^b, Alice tells Bob g^a.
10 2
> Alice knows a and g^b, and thus generates g^(ab) trivially.
10
> Similarly, Bob knows g^a and b, and trivially generates g^(ab).
also 10.
> An interceptor only knows g^a and g^b, and because the discrete log
> problem is hard cannot get a or b easily, and thus cannot generate g^(ab).
Except that the interceptor, evil Eve, took g^a and g^b and tested them
for short order, and found that one of them, g^b, had a very short order
indeed. So, without knowing a or b, Eve knows that g^(ab) is one of a
very few numbers, the elements of the group of g^b. She can now try the
elements of that group until, by exhaustion, she finds the value that
reveals the key g^(ab).
> g^(ab) is now a shared secret of Alice and Bob.
And Eve, too.
Some primes produce lots and lots of elements with small orders.
For example, Z_37 has 12 primitives, 6 elements of order 18, and all
the rest have order 9 or less.
So, is DH all wet (insecure)?
No. There are some simple steps to prevent this problem.
First, pick p to minimize the number of elements with small order.
This means that we need to know the factorization of p-1. Of course,
factoring large numbers is a hard problem, but there are several
ways to pick p with known factorization of p-1.
The simplest seems to be to pick p such that (p-1)/2 is prime; that is,
such that p-1 has two factors, 2 and (p-1)/2. Now, all the elements of
Z_p will have orders of either 2, or (p-1)/2, or p-1. There are other
methods, that permit other small orders, but we won't explore them here.
Second, after "randomly" choosing a, and computing g^a, Alice takes the
additional step of making sure that the order of g^a is not small (i.e.
is more than 2). If g^a is of small order, she picks another random a,
and repeats the process. This is trivial indeed. Bob does likewise for
his numbers b and g^b.
Since Alice and Bob have eliminated the small groups, Eve will never
encounter a g^a or g^b number whose order is less than (p-1)/2, and
given that (p-1)/2 is a _very_ large prime number, Eve won't live long
enough to try all of the elements of groups of that order.
I haven't checked to see if the RSAREF code takes these precautions.
*** end quoted text ***
I wrote a Diffie-Hellman exchange program as an extension to PGP Tools.
It uses the PGP MPILIB and does up to 1024-bit key exchange, then MD5's
the shared secret to get an IDEA key. I took most of the precautions above.
- From the DHEX10A manual (csn.org):
>To use DH, we need a modulus n and a generator g. Unlike an RSA modulus,
>which is a product of two primes, a DH modulus must be prime. (n-1)/2 must
>also be prime. This makes the moduli slightly painful to find, but they can
>be reused indefinitely. DHEX tests a modulus by first testing both n and
>(n-1)/2 with fastsieve. Only if both pass is slowtest used. It still took
>me a whole day to find the 1024-bit modulus in the demo. There is also a
>512-bit modulus there.
>
>To find the generator, we need the factors of n-1. They are 2 and (n-1)/2.
>For each factor f, we compute ((g^((n-1)/f)) mod n). If this is 1 for
>either factor, the number is NOT a generator. Generators are easy to find,
>usually in one to three tries.
The one precaution I did not take is: (from discussion above)
>Second, after "randomly" choosing a, and computing g^a, Alice takes the
>additional step of making sure that the order of g^a is not small (i.e.
>is more than 2). If g^a is of small order, she picks another random a,
>and repeats the process. This is trivial indeed. Bob does likewise for
>his numbers b and g^b.
Does the careful choosing of n and g eliminate this problem, or do I need
to modify my Diffie-Hellman code to check g^a for short order? How do you
check a number for short order?
Pr0duct Cypher
-----BEGIN PGP SIGNATURE-----
Version: 2.3a
iQCVAgUBLd1CL8GoFIWXVYodAQGnhAP+KI+w8ihQCrwKorBpkshwxBOLStIsC1uo
0e/weUyl6SqIaPCvPbYdhoKXfwpMkLxTJLvwb0wCZPtrfUDWJiCao4H7dV8VCh/q
ksWDYdVBpxupdMni+vkbuewQz105FaSTz1tHXiy1hgWYO+/OrHXy2r3WEEx8+zcF
ZqDMDbdvToU=
=sZT1
-----END PGP SIGNATURE-----