Subject: RE: PKINIT open issues

From: "Liqiang(Larry) Zhu" <[email-masked]>
Date: Sun, 26 Sep 2004 23:18:53 -0700

1) I'm reviving this thread. Jeff, do you have a ticket tracking the
DH-exponent-size recommendation?
 
2) Boneh's paper indicates that it is fine to use the SQRT(LOG(p)) MSB
bits of the DH shared secrets, thus to produce a shared AES key of size
256 bits via the truncation method, it seems to be me we need to use
64K-128K bit moduli. This modulus size is significantly larger than the
recommended 14K bits in RFC 3766. I am asking the authors of RFC 3766
off-the-list for clarification if the difference is a result of
truncation vs hashing.

3) The current draft also fails to mention how to handle leading zeros
of ZZ, I would assume the leading zero should be removed in order to get
non-zero MSBs, but this should be noted explicitly. 

--Larry

-----Original Message-----
From: [email-masked]
[mailto:[email-masked]] On Behalf Of Jonathan
Trostle
Sent: Friday, April 23, 2004 8:33 AM
To: [email-masked]
Cc: [email-masked]; [email-masked]
Subject: Re: PKINIT open issues

DH truncation is should be fine. See the paper "Hardness of Computing
the Most Significant Bits of Secret Keys in Diffie-Hellman and Related
Schemes"
by D. Boneh and R. Venkatesan. For example, they show that computing the
32 MSB of the DH shared secret is as hard as computing the entire
secret, when using a 1024 bit prime (sqrt(p) = 32 bits).

I can't find any recommendations for sizes of DH parameters in the
current version of the draft. Generally the DH exponent should be twice
as many bits as the resulting shared secret key, e.g. using a 200 bit
exponent corresponds to a 100 bit shared secret. There should be a
statement on this. 

> I realize I'm being incredibly sloppy in the above.  I could be 
> significantly less sloppy, but I believe doing so would focus the 
> discussion on the details of my questions rather than on the 
> information the WG needs in order to evaluate whether DH truncation is

> acceptable.

Jonathan

---

From: Jeffrey Hutzelman <[email-masked]>
Date: Mon, 27 Sep 2004 09:58:54 -0400

> DH-exponent-size recommendation?

The earlier discussion was captured in ticket #509, which also seems to 
cover the work that you and Sam have been doing on caching DH parameters. 
It's possible these should have been handled as separate tickets, but I 
don't think it will be a problem as it is.

-- Jeff

---

From: Nicolas Williams <[email-masked]>
Date: Mon, 27 Sep 2004 11:46:52 -0500

> off-the-list for clarification if the difference is a result of

No, that paper sets a threshhold for how much you can throw away before
what you get is no longer useful.  It does not say that if you truncate
you must truncate at an exact boundary.

> non-zero MSBs, but this should be noted explicitly. 

A good question for a cryptographer.

Nico
--

---

From: Nicolas Williams <[email-masked]>
Date: Mon, 27 Sep 2004 12:02:38 -0500

> A good question for a cryptographer.

OTOH, removing leading zeros means you're making the most significant
bit always a one -- you're losing one bit of key strength.

For PKINIT it is in each party's interest to use exponents which do not
result in small public keys, and that, I think should suffice here for
our puprposes (of course, this needs to be stated).

Nico
--