Re: [Hipsec] replacing DH in HIP

Robert Moskowitz <rgm@htt-consult.com> Mon, 15 March 2010 14:57 UTC

Return-Path: <rgm@htt-consult.com>
X-Original-To: hipsec@core3.amsl.com
Delivered-To: hipsec@core3.amsl.com
Received: from localhost (localhost [127.0.0.1]) by core3.amsl.com (Postfix) with ESMTP id 4DC253A6B64 for <hipsec@core3.amsl.com>; Mon, 15 Mar 2010 07:57:41 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: 0.001
X-Spam-Level:
X-Spam-Status: No, score=0.001 tagged_above=-999 required=5 tests=[BAYES_50=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 td87ShBEDfZV for <hipsec@core3.amsl.com>; Mon, 15 Mar 2010 07:57:40 -0700 (PDT)
Received: from klovia.htt-consult.com (klovia.htt-consult.com [208.83.67.149]) by core3.amsl.com (Postfix) with ESMTP id 7ADAD3A67B3 for <hipsec@ietf.org>; Mon, 15 Mar 2010 07:57:38 -0700 (PDT)
Received: from localhost (unknown [127.0.0.1]) by klovia.htt-consult.com (Postfix) with ESMTP id D566768B69; Mon, 15 Mar 2010 15:53:11 +0000 (UTC)
X-Virus-Scanned: amavisd-new at localhost
Received: from klovia.htt-consult.com ([127.0.0.1]) by localhost (klovia.htt-consult.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id 5bleeAIhdDtj; Mon, 15 Mar 2010 11:53:02 -0400 (EDT)
Received: from nc2400.htt-consult.com (unknown [199.72.57.111]) (Authenticated sender: rgm@htt-consult.com) by klovia.htt-consult.com (Postfix) with ESMTPSA id E5F4768B4E; Mon, 15 Mar 2010 11:53:01 -0400 (EDT)
Message-ID: <4B9E4AD3.6020601@htt-consult.com>
Date: Mon, 15 Mar 2010 10:57:23 -0400
From: Robert Moskowitz <rgm@htt-consult.com>
User-Agent: Mozilla/5.0 (X11; U; Linux i686; en-US; rv:1.9.1.8) Gecko/20100301 Fedora/3.0.3-1.fc12 Thunderbird/3.0.3
MIME-Version: 1.0
To: Dmitriy Kuptsov <Dmitriy.Kuptsov@hiit.fi>
References: <1268332644.4b993864212f8@webmail.otaverkko.fi>
In-Reply-To: <1268332644.4b993864212f8@webmail.otaverkko.fi>
Content-Type: text/plain; charset="us-ascii"; format="flowed"
Content-Transfer-Encoding: 7bit
Cc: hipsec@ietf.org
Subject: Re: [Hipsec] replacing DH in HIP
X-BeenThere: hipsec@ietf.org
X-Mailman-Version: 2.1.9
Precedence: list
List-Id: "This is the official IETF Mailing List for the HIP Working Group." <hipsec.ietf.org>
List-Unsubscribe: <https://www.ietf.org/mailman/listinfo/hipsec>, <mailto:hipsec-request@ietf.org?subject=unsubscribe>
List-Archive: <http://www.ietf.org/mail-archive/web/hipsec>
List-Post: <mailto:hipsec@ietf.org>
List-Help: <mailto:hipsec-request@ietf.org?subject=help>
List-Subscribe: <https://www.ietf.org/mailman/listinfo/hipsec>, <mailto:hipsec-request@ietf.org?subject=subscribe>
X-List-Received-Date: Mon, 15 Mar 2010 14:57:41 -0000

On 03/11/2010 01:37 PM, Dmitriy Kuptsov wrote:
> Hi all,
>
> Recently, at Helsinki Institute for Information Technology, we were trying to
> run HIP on sensor nodes, even though computing DH public values and secret is
> not a problem in terms of time, such operation consumes a lot of energy. So I
> was wondering if DH can be replace with something more lightweight, e.g,
> bivariate polynomials.

Can you provide some literature references for this algorithm? And where 
else it is used?

>   Consider a modified HIP base exchange:
>
> I                                                            R
> |                 HITi, HITr, HostIDi                        |
> |----------------------------------------------------------->|
> |   HITi, HITr, HostIDr, Puzzle, Enc_pubI(Poly_r), Sig       |
> |<-----------------------------------------------------------|
> |    HITi, HITr, Solution, Enc_pubR(Poly_i), Sig, HMAC       |
> |----------------------------------------------------------->|
> |                HITi, HITr, HMAC, Sig                       |
> |<-----------------------------------------------------------|
>
> Where the modifications are:
> (i) I1 carries the host identity, aka public key, of the initiator as parameter
> (ii) R1 carries additional encrypted using Initiators public key (found in I1)
> parameter which contains a randomly generated (by responder) bivariate
> polynomial of form for instance f(rand_r XOR HITr, y). Probably here it is
> impossible to have pre-generate R1's.
> (iii) I2 carries the encrypted using Responder's public key bivariate polynomial
> of form for instance f(rand_r XOR HITr, rand_i XOR HIT i) such that R gets now
> the secret key.
> (iv) R2 remains the unmodified.
>
> Here Enc function can be RSA or ECC using public key of receiver of a message
> such that eavesdropper cannot obtain the polynomial send in R1 or I2 messages.
>
> The bivariate polynomials f(x, y) = a0+a1xy+a2x^2y^2+...+anx^ny^n can be
> implemented really efficiently in sensor nodes over field G(2^16) and later
> using several such polynomials to construct a key of needed size. For instance,
> to construct a shared key of 80 bits Responder randomly selects 5 bivariate
> polynomials (all with different coefficients):
> f_1(rand_r_1 XOR HITr, y)
> f_2(rand_r_2 XOR HITr, y)
> f_3(rand_r_3 XOR HITr, y)
> f_4(rand_r_4 XOR HITr, y)
> f_5(rand_r_5 XOR HITr, y)
> Or may be even consecutive polynomials can be derived using some key derivation
> function...
>
> Then the initiator computes all 5 polynomials and gets the key as
> Key = (f_1(rand_r_1 XOR HITr, rand_r_1 XOR HITi) || ... ||f_5(rand_r_5 XOR HITr,
> rand_r_5 XOR HITi))
>
> The same key is obtained by responder once it receives an I2 message.
>
> Of course such approach does not comply with HIP specs in many ways. However, is
> it feasible/secure to do something like this?
>
> Kind regards,
> Dmitriy Kuptsov
>
>
> _______________________________________________
> Hipsec mailing list
> Hipsec@ietf.org
> https://www.ietf.org/mailman/listinfo/hipsec
>
>