[Cfrg] CMAC for extraction
Hugo Krawczyk <hugo@ee.technion.ac.il> Wed, 14 July 2010 01:50 UTC
Return-Path: <hugokraw@gmail.com>
X-Original-To: cfrg@core3.amsl.com
Delivered-To: cfrg@core3.amsl.com
Received: from localhost (localhost [127.0.0.1]) by core3.amsl.com (Postfix) with ESMTP id 85ED03A68D4 for <cfrg@core3.amsl.com>; Tue, 13 Jul 2010 18:50:39 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: 0.624
X-Spam-Level:
X-Spam-Status: No, score=0.624 tagged_above=-999 required=5 tests=[BAYES_50=0.001, FM_FORGED_GMAIL=0.622, HTML_MESSAGE=0.001]
Received: from mail.ietf.org ([64.170.98.32]) by localhost (core3.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id T4l5tvsnstGu for <cfrg@core3.amsl.com>; Tue, 13 Jul 2010 18:50:35 -0700 (PDT)
Received: from mail-pv0-f182.google.com (mail-pv0-f182.google.com [74.125.83.182]) by core3.amsl.com (Postfix) with ESMTP id 837AF3A695A for <cfrg@irtf.org>; Tue, 13 Jul 2010 18:50:35 -0700 (PDT)
Received: by pvh1 with SMTP id 1so2765924pvh.13 for <cfrg@irtf.org>; Tue, 13 Jul 2010 18:50:43 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=gamma; h=domainkey-signature:received:mime-version:sender:received:from:date :x-google-sender-auth:message-id:subject:to:content-type; bh=ZaoIrbtrlqiULLldfVKCBtoUFJdwVAkkpZKRnvZckFY=; b=E3VjLNp0jVwXrm1+ZVjS2idzlr2XKUpP8iNk2yKmYl6WkzE4uMzw/cR+frEWVg8wTI Soy+YLdZJbo3Ie8yRRWFEj1iT9vFfLv73v4tTKhc1H2iP7Uyltfwj3fCHp6FLwPIxTKI DmQm3czI0YFAqbW6BtVsp3B3vJFjxbR8dFDKw=
DomainKey-Signature: a=rsa-sha1; c=nofws; d=gmail.com; s=gamma; h=mime-version:sender:from:date:x-google-sender-auth:message-id :subject:to:content-type; b=fnsUIJTTKosLrGkk9fa1V6dasKlJ6P5l29BvMcfdMArxQJyaqX4j3ih8kWAn9x603R kbjf6/B5tAJFibi0vjvXN7HOk0mkYI3gBTyNsTDIZbYIy1LrX5+xDoTkDWVc9s/HZROH dkjIyysYfdxz+MAPz3imY112emFPXiKtfTzPg=
Received: by 10.142.144.2 with SMTP id r2mr4612835wfd.183.1279072242719; Tue, 13 Jul 2010 18:50:42 -0700 (PDT)
MIME-Version: 1.0
Sender: hugokraw@gmail.com
Received: by 10.142.191.2 with HTTP; Tue, 13 Jul 2010 18:50:21 -0700 (PDT)
From: Hugo Krawczyk <hugo@ee.technion.ac.il>
Date: Tue, 13 Jul 2010 21:50:21 -0400
X-Google-Sender-Auth: OIOfq025-1Jrw__2yoa5CPza9do
Message-ID: <AANLkTimQs4s69bM2okrETKQUIf9r33wu7wEeMR8WK265@mail.gmail.com>
To: Robert Moskowitz <rgm-sec@htt-consult.com>, cfrg@irtf.org
Content-Type: multipart/alternative; boundary="000e0cd3291cab5b10048b4f3615"
Subject: [Cfrg] CMAC for extraction
X-BeenThere: cfrg@irtf.org
X-Mailman-Version: 2.1.9
Precedence: list
List-Id: Crypto Forum Research Group <cfrg.irtf.org>
List-Unsubscribe: <http://www.irtf.org/mailman/listinfo/cfrg>, <mailto:cfrg-request@irtf.org?subject=unsubscribe>
List-Archive: <http://www.irtf.org/mail-archive/web/cfrg>
List-Post: <mailto:cfrg@irtf.org>
List-Help: <mailto:cfrg-request@irtf.org?subject=help>
List-Subscribe: <http://www.irtf.org/mailman/listinfo/cfrg>, <mailto:cfrg-request@irtf.org?subject=subscribe>
X-List-Received-Date: Wed, 14 Jul 2010 01:50:39 -0000
Bob, I cannot give an assessment of protocols or standards that I am not familiar with, and IEEE 802.15.6 is one of them. So let me give you a generic answer to your question (quoted at the end of this message) that does not take into account the specifics of IEEE 802.15.6 but only the question of how to use a block cipher in CMAC mode to process a DH key (the details of IEEE 802.15.6 may or may not interfere with this advise). There are two obvious problems with inputting the DH key directly as CMAC key: (1) the DH key is likely to be of a different size than the CMAC key, (2) the DH key is not a uniformly distributed string (but rather a uniformly distributed element in some algebraic group -- more precisely, assuming the Decisional Diffie-Hellman assumption, the distribution of DH keys is computationally indistinguishable from the uniform distribution on the DH group). A trivial way to resolve the first issue (assuming the DH key is longer than the CMAC one) is to truncate the DH key to the number of CMAC key bits. There are theoretical reasons (though not necessarily an attack) NOT to do so (e.g., since the DH key is not a uniform string of bits, a subset of it may not be uniform either). A better way would be to apply an extractor to the DH key and use the output as the CMAC key (much as in the HKDF design). Since you do not want to use a hash function then you need to do the extraction using the block cipher itself. I only know of one work that analyzes such a scheme and it is the Dodis-Gennaro-Hastad-Krawczyk-Rabin paper from Crypto'04. There we show that if the block cipher acts as a family of random permutations then you can use CMAC with that block cipher as an extractor. The security bounds guaranteed by that analysis are not great (and the random permutation assumption is an idealized one), yet it is the best analysis we have for such a beast. NOTE: Our revised analysis of the CBC case replaces the expression e(L,K) in the proceedings version of the paper with L^4/K^2 which is worse than the original bound but of little consequence in the application below where L is a very small number (i.e., L= the number of blocks in the representation of DHK, where the length of a block is determined by the underlying block cipher). The available version of the paper (with the old bound) is http://cs.nyu.edu/~dodis/ps/hmac.ps. If you want to buy that analysis as an indication of security then I can suggest the following. Let DHK be the DH key that is output by your protocol and let CK be the CMAC key that you want to generate. (a) Assuming that you are running an authenticated Diffie-Hellman protocol between the parties to generate the DH key DHK, add to the protocol the generation of a nonce that is exchanged and AUTHENTICATED by the parties. This nonce, call it N, is to be of the length of the CMAC key (and it should be independent of the DH key DHK). (b) Apply CMAC with N as the key and DHK as the input (i.e., DHK acts as the message, or plaintext, for the CMAC function and N acts as the key). (c) Use the value output by (b) as the key CK (this assumes that the output length from CMAC is the same as the length of a CMAC key -- this is the case for AES-128 but not for AES-256). IMPORTANT: If your protocol cannot exchange a nonce, or can exchange it but cannot authenticate it (in which case the nonce can be chosen by an attacker) then replace N with a fixed value that is defined and wired it into the protocol as a constant. Choose N to be any "random" string of the length of a CMAC key. (I prefer to use a random-looking N rather than something like all-zero string in case that such a structured key may turn to be a "weak key" of the underlying cipher). Hugo > Hugo, > > In the proposed IEEE 802.15.6 standard, an ECDH derived key is expanded via CMAC > to produce the actual keying material. No cryptographic hash is used in this > protocol. > > This seems to go contrary to the recommendation in > http://www.ietf.org/id/draft-irtf-cfrg-kdf-uses-00.txt that DH derived keys are > NOT uniformly distributed and MUST be passed through an extract phase (eg as in > HKDF). > > Can you please point me to a reference to the nature of the attack in this > usage. This method will end up in medical devices like Insulin pumps, > Pacemakers, etc and I am looking for hard references to get the authors to make > needed changes.
- [Cfrg] CMAC for extraction Hugo Krawczyk
- Re: [Cfrg] CMAC for extraction Robert Moskowitz
- Re: [Cfrg] CMAC for extraction Robert Moskowitz