Re: KDF definition and goal [was: [Cfrg] Fwd: Hash-Based Key Derivation]

"D. J. Bernstein" <djb@cr.yp.to> Wed, 26 October 2005 09:09 UTC

Received: from localhost.localdomain ([127.0.0.1] helo=megatron.ietf.org) by megatron.ietf.org with esmtp (Exim 4.32) id 1EUhHl-0004ms-4v; Wed, 26 Oct 2005 05:09:29 -0400
Received: from odin.ietf.org ([132.151.1.176] helo=ietf.org) by megatron.ietf.org with esmtp (Exim 4.32) id 1EUhHj-0004kI-5X for cfrg@megatron.ietf.org; Wed, 26 Oct 2005 05:09:27 -0400
Received: from ietf-mx.ietf.org (ietf-mx [132.151.6.1]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id FAA05639 for <cfrg@ietf.org>; Wed, 26 Oct 2005 05:09:11 -0400 (EDT)
Received: from stoneport.math.uic.edu ([131.193.178.160]) by ietf-mx.ietf.org with smtp (Exim 4.43) id 1EUhUq-00023O-6n for cfrg@ietf.org; Wed, 26 Oct 2005 05:23:01 -0400
Received: (qmail 79963 invoked by uid 1016); 26 Oct 2005 09:09:44 -0000
Date: Wed, 26 Oct 2005 09:09:44 -0000
Message-ID: <20051026090944.79962.qmail@cr.yp.to>
Automatic-Legal-Notices: See http://cr.yp.to/mailcopyright.html.
From: "D. J. Bernstein" <djb@cr.yp.to>
To: cfrg@ietf.org
Subject: Re: KDF definition and goal [was: [Cfrg] Fwd: Hash-Based Key Derivation]
References: <200510260025.j9Q0Pdn4026118@taverner.CS.Berkeley.EDU>
Mime-Version: 1.0
Content-Type: text/plain; charset="us-ascii"
Content-Disposition: inline
X-Spam-Score: 0.0 (/)
X-Scan-Signature: ffa9dfbbe7cc58b3fa6b8ae3e57b0aa3
X-BeenThere: cfrg@ietf.org
X-Mailman-Version: 2.1.5
Precedence: list
List-Id: Crypto Forum Research Group <cfrg.ietf.org>
List-Unsubscribe: <https://www1.ietf.org/mailman/listinfo/cfrg>, <mailto:cfrg-request@ietf.org?subject=unsubscribe>
List-Post: <mailto:cfrg@ietf.org>
List-Help: <mailto:cfrg-request@ietf.org?subject=help>
List-Subscribe: <https://www1.ietf.org/mailman/listinfo/cfrg>, <mailto:cfrg-request@ietf.org?subject=subscribe>
Sender: cfrg-bounces@ietf.org
Errors-To: cfrg-bounces@ietf.org

David Wagner writes:
> The simplest randomized construction is to let UH(.,.) be a 2-universal
> hash, pick R randomly, publish R, and use UH(R,S) as your key, where
> S is the secret input.  This is a KDF with no auxiliary inputs.

For example, if you have a 1024-bit Diffie-Hellman result with 512 bits
of apparent entropy, and you want to convert it into a 256-bit key, you
can view it as a polynomial mod 2, multiply by x^256, and reduce the
result modulo a standard irreducible degree-256 polynomial.

On the other hand, if you have a 256-bit elliptic-curve-Diffie-Hellman
result x with 250 bits of apparent entropy, and you want to convert it
into a 512-bit key, then you'll have to take the time for some serious
cryptographic hashing, such as SHA-256(0,x),SHA-256(1,x).

Fortunately, serious cryptographic hashing isn't a bottleneck here. It
takes only a few thousand cycles, while Diffie-Hellman takes half a
million cycles.

Some people don't trust their cryptosystems to handle many packets under
a single key, so they produce a new key after (say) a megabyte of data.
But this rehashing is much faster than the packet processing, so again
it isn't a bottleneck.

---D. J. Bernstein, Professor, Mathematics, Statistics,
and Computer Science, University of Illinois at Chicago

_______________________________________________
Cfrg mailing list
Cfrg@ietf.org
https://www1.ietf.org/mailman/listinfo/cfrg