# Re: Secure key exchange with hashing and the birthday paradox

*From*: daw@xxxxxxxxxxxxxxxxxxxxxxxx (David Wagner)*Date*: Sat, 18 Mar 2006 21:59:48 +0000 (UTC)

Will Dickson wrote:

Interesting. Does this mean that you couldn't, say, do a DH key exchange,

but use the black-box signature scheme to sign the exchanged messages

in order to prevent an MITM attack?

Sure, you can do that. However, for signed DH to be secure, you have

to assume that the Diffie-Hellman problem is hard. Thus, this is not

a generically secure scheme (i.e., one that is secure, with no added

assumptions, other than that the one-way function/permutation is indeed

one-way). The question here is: Can you build a key exchange that is

secure, where the only assumption used is the one-wayness of the one-way

permutation used in the scheme? For signature schemes, the answer is yes;

for key exchange, the answer is no.

Let me try putting it another way. As Paul Rubin wrote, there is a

scheme S[f] with the following properties:

(i) S is the template of a signature scheme. It is parametrized

by a function f. When you plug in some function f, you get a

signature scheme, denoted by S[f]. In other words, you can think

of S as a mapping from functions to signature schemes.

(ii) S[f] uses f only in a 'black-box' manner. The only thing that

S[f] does with f is evaluate f on some points; S[f] does not look

at the code or description of f, and S[f] does not depend on the

internals of f in any way. In other words, the only way that S[f]

uses f is that, at various points in the computation of a signature,

S[f] computes some value x and needs a way to get the value f(x).

Other than that, S[f] does not depend on f in any way. Another way

to put this is that f is used only as a subroutine that can be

called (but whose implementation cannot be inspected).

(iii) S[f] is generically secure. If f is any one-way permutation,

then S[f] is guaranteed to be secure. Put another way, there is

a security theorem of the following form:

Theorem. For all functions f, if f is a one-way permutation,

then S[f] is a secure signature scheme.

Note that the security of S[f] does not rely on any unproven

assumptions (e.g., that factoring is hard; that DDH is hard),

other than the assumption that f is one-way. Also S[f] can be

handed *any* one-way permutation f, and must work no matter what

kind of one-way permutation it is given.

At this point, you might wonder whether it is possible to do the same

sort of thing for key-exchange protocols. What Impagliazzo and Rudich

showed is that, in fact, you cannot. There is no corresponding scheme

KE such that: (i) KE[f] is a key-exchange protocol; (ii) KE[f] uses f

only in a 'black-box' manner; (iii) KE[f] is generically secure: one can

prove that if f is any one-way permutation, then KE[f] is a secure

key-exchange protocol (with no further assumptions needed).

Signed DH fails the third condition above: its security relies on an

extra unproven hardness assumption, e.g., that the Diffie-Hellman problem

is hard.

.

**Follow-Ups**:**Re: Secure key exchange with hashing and the birthday paradox***From:*Will Dickson

**References**:**Secure key exchange with hashing and the birthday paradox***From:*Luc The ***e

**Re: Secure key exchange with hashing and the birthday paradox***From:*Paul Rubin

**Re: Secure key exchange with hashing and the birthday paradox***From:*David Wagner

**Re: Secure key exchange with hashing and the birthday paradox***From:*Will Dickson

- Prev by Date:
**Re: GMP versus TFM on an AMD64** - Next by Date:
**Re: Newbie data size encryption questions** - Previous by thread:
**Re: Secure key exchange with hashing and the birthday paradox** - Next by thread:
**Re: Secure key exchange with hashing and the birthday paradox** - Index(es):