Subject: [Hipsec] replacing DH in HIP

From: Dmitriy Kuptsov <[email-masked]>
Date: Thu, 11 Mar 2010 20:37:24 +0200

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. 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

---

From: Robert Moskowitz <[email-masked]>
Date: Mon, 15 Mar 2010 10:57:23 -0400

On 03/11/2010 01:37 PM, Dmitriy Kuptsov wrote:
> 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                        |
> _______________________________________________
> Hipsec mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/hipsec
>
>

---

From: Robert Moskowitz <[email-masked]>
Date: Mon, 15 Mar 2010 15:18:37 -0400

posting back to the list.

On 03/15/2010 12:03 PM, Dmitriy Kuptsov wrote:
> Hi,
>
> Thank you for the replay. You can find this kind of "key exchange" for
> instance in [2] which was used for wireless sensor networks. There is
> also some background material in [1] and an application in technical
> report [3].
>    

Thank you for this information.

Are there any more recent references?

For sensors vendors that I have been talking to, code size is just as 
much a concern as cpu requirements. How does this approach compare to a 
DH EC implementation?

> Note that in [2] the polynomials are generated before the actual
> deployment, that is for instance node with IDa after deployment stores a
> set of polynomials, e.g., f(IDa, IDb), ..., f(IDa, IDx), such that it
> can only establish a pair wise secure channels with nodes identified by
> IDb, ..., IDx correspondingly. However, this kind of presharing has its
> limitations (frankly speaking it is not scalable). So that is why I
> though whether it can be useful/meaningful to use HIP to agree on a
> common polynomial(s) between 2 sensors nodes during base exchange and
> use the result to derive a common key.
>
> Of course the modification of HIP base exchange below does not necessary
> require the polynomials to be used (they can be interpreted as key
> derivation functions). Instead it can be that initiator and responder
> exchange 2 random strings (which are carried in R1 and I2 and encrypted
> using corresponding public keys), and later use those to derive a common
> key (if it is secure of course).
>
> References:
> [1] Carlo Blundo, Alfredo De Santis, Amir Herzberg, Shay Kutten, Ugo
> Vaccaro, and Moti Yung. "Perfectly-secure key distribution for dynamic
> conferences" In CRYPTO, pages 471–486, 1992.
> [2] DONGGANG LIU, PENG NING and RONGFANG LI, "Establishing Pairwise Keys
> in Distributed Sensor Networks" in Proceedings of ACM Conference on
> Computer and Communications Security 2003 (CCS'03) ***
> [3] Abedelaziz Mohaisen "Password Authentication and Key Exchange
> Protocol" technical report
>
> *** also full paper exist
>
> On Mon, 2010-03-15 at 10:57 -0400, Robert Moskowitz wrote:
>    
>>> implemented really efficiently in sensor nodes over field G(2^16+1) and later

---

From: Dmitriy Kuptsov <[email-masked]>
Date: Tue, 16 Mar 2010 12:15:24 +0200

Hi,

> Are there any more recent references?

Well, at least I am not aware of any other right now.

> much a concern as cpu requirements. How does this approach compare to a 

Talking in terms of energy consumption?

We did not evaluate ECDH on sensors yet (only DH), but we did measure
the polynomial computation which is really efficient (probably we can
provide some figures by the end of this week). According to [4] ECDH key
exchange (not authenticated; 192-bits prime field was used) consumes
57.33 mJ per node on MICAz mote (ATmega128 platform). Also in [4] it was
estimated using model from [5] (where 2 AA batteries with capacity of
2500  mAh are used for power supply) that 117,750 key exchanges are
possible before the battery voltage drops below critical level.

[4] Christian Lederer, Roland Mader, Manuel Koschuch, Johann Großschädl,
Alexander Szekely, and Stefan Tillich : "Energy-Efficient Implementation
of ECDH Key Exchange for Wireless Sensor Networks" 
[5] Krzysztof Piotrowski, Peter Langendoerfer and Steffen Peter : "How
Public Key Cryptography Influences Wireless Sensor Node Lifetime"

---

From: Dmitriy Kuptsov <[email-masked]>
Date: Tue, 16 Mar 2010 12:46:13 +0200

Hi,

> > much a concern as cpu requirements. How does this approach compare to a 

If talking about code size in RAM and comparing just ECDH and
polynomials then i would bet that later requires less.

---

From: Tobias Heer <[email-masked]>
Date: Tue, 16 Mar 2010 12:31:16 +0100

Hello Dimitriy, 

> bivariate polynomials. Consider a modified HIP base exchange:

[...]

> it feasible/secure to do something like this?

HIP is currently very IP-network focused (updates, NAT traversal, address verification in the base exchange, etc.). It can be used in other scenarios, of course. However, I wonder how much of HIP becomes obsolete when you push it into your scenario. What features of HIP do you require?

There are some problems when using polynomial shares that require to use them in a tightly controlled closed system (please correct me if I am wrong). This would considerably change the way HIP works. Maybe you can comment on these issues in the context of HIP: 

a) they require a trust center that holds the basic keying material. Hence, hosts cannot generate their keys by themselves anymore. Moreover, AFAIK there must be one basic keying material, so distributing the role of trust centers is difficult. In HIP hosts can generate their cryptographic keys by themselves without any help from outside. Do we have to give up this property?
b) the protocol is only alpha-secure. This means that the trust center must be careful when handing out keying material. Otherwise there is a chance that all keying material is compromised. Therefore, the approach requires some measures like user registration, etc. to make sure that one user cannot gather more shares than necessary to break the security. Are there established approaches to circumvent this limitation?
c) there is no perfect forward secrecy (as opposed to DH). If the polynomial shares are compromised (for the whole system or just for one node) all previous (recorded) communications are available to attackers. Are there any countermeasures to avoid this?
d) the size of the keying material is related to the maximum numbers of hosts in the system (because of the alpha-secure property). Where are the scalability limits of the approach. Is it sensible to assume 100, 1000, or billions of hosts that can be supported?

Some more questions: 
Is interoperability with ordinary HIP nodes a goal or will the communication just be between sensors?
Is the puzzle mechanism of importance because of DoS (AFAIK DH computation cost is one of the main reasons to have it)?
How is ID-locator resolution handled in your scenario or is it of any relevance (maybe you only have direct communication anyway)?

Don't get me wrong: the reason I am asking is not to oppose your approach. I just want to understand it better. In general I appreciate all efforts of speeding up HIP and of extending its scope.

BR, 

Tobias

--  

Dipl.-Inform. Tobias Heer, Ph.D. Student
Distributed Systems Group 
RWTH Aachen University, Germany
tel: +49 241 80 207 76
web: http://ds.cs.rwth-aachen.de/members/heer

---

From: Dmitriy Kuptsov <[email-masked]>
Date: Tue, 16 Mar 2010 19:07:02 +0200

Hi Tobias,

Quoting Tobias Heer <[email-masked]>:

> Hello Dimitriy,
> [...]
> HIP is currently very IP-network focused (updates, NAT traversal, address
> verification in the base exchange, etc.). It can be used in other scenarios,
> of course. However, I wonder how much of HIP becomes obsolete when you push
> it into your scenario. What features of HIP do you require?

In my opinion for wireless sensor networks the following should be possible:
(i) node identification (using HITs) and authentication (using host identities)
(ii) shared secret negotiation
(iii) transform suit negotiation

> There are some problems when using polynomial shares that require to use them
> in a tightly controlled closed system (please correct me if I am wrong). This

We might have some misunderstanding, but I am not sure.

Well the scenario I have described in previous email there is no need for
trusted 3rd party (TTP) to generating shared secret between initiator and
responder. The only usage of TTP, which is similar to current HIP I assume, is
to allow nodes to authenticate HITs they see in the base exchange using the
certificates for instance.

The only major modification to HIP base exchange is to carry initiator's host
identity already in I1 message such that responder can use it to pass some
secret in R1 message in a secure way. Here secret is a bivariate polynomial (or
polynomials depending on which size of the secret should be generated) to which
I referred previously. The selection of a bivariate polynomial is just to allow
both initiator and responder introduce randomness in key generation process

In my opinion questions a) through d) are not relevant in this context (please
correct me if I am also misunderstood something here)

> would considerably change the way HIP works. Maybe you can comment on these
> issues in the context of HIP:
>
> a) they require a trust center that holds the basic keying material. Hence,
> hosts cannot generate their keys by themselves anymore. Moreover, AFAIK there
> must be one basic keying material, so distributing the role of trust centers
> is difficult. In HIP hosts can generate their cryptographic keys by
> themselves without any help from outside. Do we have to give up this
> property?
N/A
> b) the protocol is only alpha-secure. This means that the trust center must
> be careful when handing out keying material. Otherwise there is a chance that
> all keying material is compromised. Therefore, the approach requires some
> measures like user registration, etc. to make sure that one user cannot
> gather more shares than necessary to break the security. Are there
> established approaches to circumvent this limitation?
N/A

Trust centre does not generate any polynomials to any nodes in the network (I
think I have mentioned it before). The only usage of trust centre can be to
provide a mean for authenticating HITs (for instance (i) using certificates or
(ii) paths of Merkle trees constructed out of HITs acceptable in the network
(iii) something else if exist).

> c) there is no perfect forward secrecy (as opposed to DH). If the polynomial
> shares are compromised (for the whole system or just for one node) all
> previous (recorded) communications are available to attackers. Are there any
> countermeasures to avoid this? N/A

Since polynomial(s) is (are) generated randomly by responder every time it
receives and R1 message (just as it DH public value is currently generated) and
is used only to derive a key for a session with a particular node there should
be no way to correlate it to other polynomials generated in other base
exchanges, etc.

> d) the size of the keying material is related to the maximum numbers of hosts
> in the system (because of the alpha-secure property). Where are the
> scalability limits of the approach. Is it sensible to assume 100, 1000, or
> billions of hosts that can be supported?
N/A

> Is interoperability with ordinary HIP nodes a goal or will the communication

Well it is probably favourable to have interoperability with ordinary HIP nodes
for a number of reasons; such as integration of sensor network with Internet,
etc.

> Is the puzzle mechanism of importance because of DoS (AFAIK DH computation
> cost is one of the main reasons to have it)?

Puzzle mechanism probably not so important for sensor networks.

> How is ID-locator resolution handled in your scenario or is it of any
> relevance (maybe you only have direct communication anyway)?

Well it depends on the application it can also be so that nodes are several hops
away.

> Don't get me wrong: the reason I am asking is not to oppose your approach. I
> just want to understand it better. In general I appreciate all efforts of
> speeding up HIP and of extending its scope.

Actually I love to see response to my questions, so no problem. Thank you!

Kind regards,
Dmitriy

---

From: Robert Moskowitz <[email-masked]>
Date: Tue, 16 Mar 2010 13:33:25 -0400

On 03/16/2010 01:07 PM, Dmitriy Kuptsov wrote:
> Hi Tobias,
>
> Quoting Tobias Heer<[email-masked]>:
>
>    
>> Hello Dimitriy,
>> [...]

There will still be the HIT so if the system supports IP, there should 
be no need to run HIP again for IP security.
> responder.

In my investigations, I am finding out that 'traditionally' bivariate 
polynomials are used to distribute keys from a TTP. Perhaps others are 
assuming this senario. I see that is not your intent, but I am not sure 
of your whole process.

>   The only usage of TTP, which is similar to current HIP I assume, is

---

From: Dmitriy Kuptsov <[email-masked]>
Date: Thu, 18 Mar 2010 12:06:19 +0200

Hi Tobias,

> Don't get me wrong: the reason I am asking is not to oppose your approach. I just want to understand it better. In general I appreciate all efforts of speeding up HIP and of extending its scope.

I apologies for being somewhat awkward. 

So the whole process of "optimized" secret key negotiation for
lightweight sensors can look as follows:

1. Each node (similar as what it is in current HIP) have they
public-private key pair (this can be a self-generated or generated and
signed by TTP -  a network operator, depending whether the network
should be an open or closed group). I am not sure whether HITs should
play some other role other than identifiers (in a context of sensor
network), but lets not concentrate on this right now.

2. The goal is for any given 2 nodes (no matter whether they are just 1
hop or several hops away) in the network to establish (or update) a
secret session key in more "lightweight" manner as compared to DH which
is used currently in HIP.

3. To do so, the initiator sends an I1 packet containing common HIP
header, as well as it also sends its public key (corresponding to its
HIT) in a form of HostID parameter. 

4. The responder constructs R1 packet containing the following
parameters (of course common HIP header is still present):
	(i) New parameter that carries some secret, call it ENC(S), where S can
be anything some function, random string, etc., that later will allow
both initiator and responder to agree on some common secret (of way is
to use bivariate polynomials, see bellow the explanation how those can
be used to derive a common secret). The ENC parameter is encrypted using
initiators public key (I assume that encryption is more efficient than
DH or ECDH computation)
	(ii) Responder's HostID
	(iii) Signature that covers the entire HIP packet.

5. Once the initiator receives R1 packet proceeds with normal steps,
such as signature verification, etc. It then decrypts the ENC parameter
with is private key and obtains S. Using S initiator computes a secret
key. Once this is done the initiator constructs I2 packet with the
following parameters:
	(i) The ENC parameter which carries let say S', which will allow the
responder to derive the same secret key. This parameter is encrypted
using responder public key.
	(ii) HMAC parameter as usual 
	(iii) Signature parameter as usual (I am not sure whether HMAC is
sufficient and we can omit using signatures in I2 and R2 packets for
wireless sensor networks)

6. Responder upon receiving I2 decrypts ENC parameter (i) computes the
session key and (ii) verifies HMAC. It then construct an R2 packet with
follwing parameters:
	(i) HMAC 
	(ii) Signature (may HMAC is sufficient and signature parameter can be
omitted in sensor networks?)

Session key deviation function (using bivariate polynomials) can look as
following:

1. Responder randomly selects coefficients {a0, a1, ..., at} and point x
for a bivariate polynomial of form:

F(x, y) = a0*b0 + a1*b1*x*y + ... + at*bt*x^t*y^t 

(Note that this happens when I1 is received)

2. Initiator uses the F(x, y) (found in R1 message) and randomly selects
coefficients {b0, b1, ..., bt} and point y. The initiator now can 
evaluate F(x, y) and get common secret. It then sends back to responder
the evaluated at point y and using coefficients {b0, b1, ..., bt}
polynomial F(x, y).

3. Responder now can also evaluate F(x, y) (knowing both coefficients
{a0, a1, ..., at}, {b0, b1, ..., bt}, x and y points) and get the same
session key as initiator.

Kind regards,
Dmitriy Kuptsov