Subject: [Roll] Signature schemes and IPR in RPL

From: Philip Levis <[email-masked]>
Date: Thu, 22 Jul 2010 16:41:00 -0700

Summary: This mail describes the current status of signature schemes in RPL, presents three options for going forward, and asks the WG to discuss and reach consensus on how to proceed.

Background
-------------

Currently RPL has a single security algorithm configuration:

    +-------+-------------------+--------------------------------------+
    |  ID   |  Encryption/MAC   |              Signature               |
    +-------+-------------------+--------------------------------------+
    |   0   | CCM* with AES-128 | ECPVS with K-283, Matyas-Meyer-Oseas |
    | 1-255 |      Reserved     |               Reserved               |
    +-------+-------------------+--------------------------------------+

The Signature scheme described is encumbered by IPR held by Certicom. Rene, as a major contributor to the security parts of RPL, disclosed this IPR through the standard IETF process. Rene does not currently work for Certicom, although he did in the past. The particular scheme was chosen because of its technical advantages in LLNs: short signatures which are inexpensive to compute compared to many other signature schemes.

Going Forward
--------------------------

The security DT sees three possible paths going forward:

  1) Keep the Algorithm options as they are now: the only signature scheme supported in the base RPL specification is encumbered by IPR. Let's call this the "IPR" option.

  2) Keep a single Algorithm (ID=0) in the base RPL specification, but change Algorithm ID=0's signature scheme to one that we believe is unencumbered by IPR. Let's call this the "No-IPR" option.

  3) Keep the current Algorithm (ID=0), and add a second Algorithm (ID=1) to have the same Encryption/MAC scheme as ID=0 (CCM* with AES-128) but a signature scheme we believe is unencumbered by IPR. Let's call this the "Both" option.

We are currently investigating which signature scheme unencumbered by IPR would best meet the requirements of LLNs. We expect to have reached a conclusion on this by the end of this week. It's our opinion that which exact algorithm is chosen should be considered independently of the three options above (under the assumption that it is unencumbered by IPR).

Discussion
-------------------

The security DT would like guidance from the WG on which of the three options it should pursue. Given that we are in last call and are meeting next week, let's try to keep the discussion focused and on-topic so we can reach consensus quickly.

Phil

---

From: Michael Richardson <[email-masked]>
Date: Thu, 22 Jul 2010 19:55:07 -0400

>>>>> "Philip" == Philip Levis <[email-masked]> writes:
    Philip> The security DT sees three possible paths going forward:

    Philip>   1) Keep the Algorithm options as they are now: the only
    Philip> signature scheme supported in the base RPL specification is
    Philip> encumbered by IPR. Let's call this the "IPR" option.

    Philip>   2) Keep a single Algorithm (ID=0) in the base RPL
    Philip> specification, but change Algorithm ID=0's signature scheme
    Philip> to one that we believe is unencumbered by IPR. Let's call
    Philip> this the "No-IPR" option.

    Philip>   3) Keep the current Algorithm (ID=0), and add a second
    Philip> Algorithm (ID=1) to have the same Encryption/MAC scheme as
    Philip> ID=0 (CCM* with AES-128) but a signature scheme we believe
    Philip> is unencumbered by IPR. Let's call this the "Both" option.

This is not a good explanation of the three options.

a) we can always create another algorithm ID=1 as proposed by option (3).
   That's not what's important.
   What's important is whether or not ID=1 is MUST.
   You did not specify this, but I will assume that this is what you
   mean.

   Given that ID=1 will then become a MUST, you have not specified what
   will happen to ID=0 --- will it be a MUST or not?

b) similarly, for option(2), we can always declare a new ID=n
   option with AES-CCM* + "IPR mode".
   The implicit assumption is that the No-IPR option will be a MUST,
   while some future ID=n option will be a MAY.

So a better choice would be to present the working group with question:
   "Shall the only MUST signature algorithm be IPR-encumbered?"

- -- 
]       He who is tired of Weird Al is tired of life!           |  firewalls  [
]   Michael Richardson, Sandelman Software Works, Ottawa, ON    |net architect[
] [email-masked] http://www.sandelman.ottawa.on.ca/ |device driver[
   Kyoto Plus: watch the video <http://www.youtube.com/watch?v=kzx1ycLXQSE>
	               then sign the petition.

---

From: Michael Richardson <[email-masked]>
Date: Thu, 22 Jul 2010 19:57:34 -0400

I will answer on the assumption that:
  a) option 2 means marking ID=0, No-IPR option MUST, and any
     future IPR-option a MAY.

  3b) option 3 means marking ID=1 MUST, and ID=0 MUST.

  3c) option 3 means marking ID=1 MUST, and ID=0 MAY.

My preferences are:
   (2)
   (3c)
   
I consider (1) and (3c) to be completely un-acceptable.

--

---

From: Philip Levis <[email-masked]>
Date: Thu, 22 Jul 2010 17:09:54 -0700

>   "Shall the only MUST signature algorithm be IPR-encumbered?"

Except, of course, that supporting signatures is not a MUST. It is entirely acceptable, within the current specification, to have a RPL implementation that supports only unsecured mode, just as it is acceptable to have a RPL implementation that rejects all unsecured messages. 

This flexibility is because some LLNs have security mechanisms (e.g., link layer) which can render the RPL ones superfluous, therefore optional. One of the stated design goals from the beginning is that RPL should not require security mechanisms when they are not needed.

Phil

---

From: Alexandru Petrescu <[email-masked]>
Date: Fri, 23 Jul 2010 09:30:34 +0200

Le 23/07/2010 01:55, Michael Richardson a écrit :
> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
>
>
>>>>>> "Philip" == Philip Levis<[email-masked]>  writes:

My answer to that question is - no, we should not MUST a signature 
algorithm IPR-encumbered.

Make the default IPR non-encumbered and add IPR'ed extensions.

And then we could also ask about the licensing terms - I guess they exist.

Alex

>     Kyoto Plus: watch the video<http://www.youtube.com/watch?v=kzx1ycLXQSE>
> 	then sign the petition.
>
>
> -----BEGIN PGP SIGNATURE-----
> Version: GnuPG v1.4.10 (GNU/Linux)
> Comment: Finger me for keys
>
> iQEVAwUBTEjaWoCLcPvd0N1lAQLISwf+Iyklzi3Q+uA5RBRgqdcdl4eUquc3mcb3
> 6oHpr/Xu/iOr2o3Sr8fpjAJs8zHF4XMheTaD+aRQt3oIkiEp5vcEOsDJsh7MayzP
> DDnPXVB7zODwxlLblASdQ/x4Ol/YsYWeWyQv7UHQyxgG2EMOzHzS3gz8MYqQlrfF
> hUg9y/makniiI1erU02DEn8jfEQwms7mnaev8E3sFHCsnRnlyXx/o3ha8HHSyMDR
> CQk9mY04AR9bBCCdXfgwub0SecmR1gK57vBo5riuGxoouqWzf0qzzo+aiMKkGAyE
> s07MfslXcqhZGSr47D/Y0pW6w7nAKPMfo1YAU0mJNzEVOog5MvyNHg==
> =6oWx
> -----END PGP SIGNATURE-----
> _______________________________________________
> Roll mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/roll
>

---

From: Alexandru Petrescu <[email-masked]>
Date: Fri, 23 Jul 2010 09:34:11 +0200

Le 23/07/2010 02:09, Philip Levis a écrit :
>> So a better choice would be to present the working group with
>> question: "Shall the only MUST signature algorithm be
>> IPR-encumbered?"
>>
>> - --
>
>
> Except, of course, that supporting signatures is not a MUST. It is
> entirely acceptable, within the current specification, to have a RPL
> implementation that supports only unsecured mode, just as it is
> acceptable to have a RPL implementation that rejects all unsecured
> messages.

This may lead to a situation where the implementations of people who 
don't pay are unsecure... extrapolating, of course, but that sounds so.

It is not a good situation to be in.

And of course people who don't pay could design a default auth mechanism 
which could ensure enough security.

> This flexibility is because some LLNs have security mechanisms (e.g.,
> link layer) which can render the RPL ones superfluous, therefore
> optional.

I agree.  When link layer security is relied upon then we should state 
so, in the draft, with the names of the link layer security.

> One of the stated design goals from the beginning is that
> RPL should not require security mechanisms when they are not needed.

Is this reflected in the draft?

Alex

>
> Phil _______________________________________________ Roll mailing
> list [email-masked] https://www.ietf.org/mailman/listinfo/roll
>

---

From: JP Vasseur <[email-masked]>
Date: Fri, 23 Jul 2010 13:51:55 +0200

On Jul 23, 2010, at 2:09 AM, Philip Levis wrote:

>> question:
> This flexibility is because some LLNs have security mechanisms  
> (e.g., link layer) which can render the RPL ones superfluous,  
> therefore optional. One of the stated design goals from the  
> beginning is that RPL should not require security mechanisms when  
> they are not needed.
>

Thanks for stressing this important fact.

---

From: JP Vasseur <[email-masked]>
Date: Fri, 23 Jul 2010 13:52:25 +0200

Begin forwarded message:

> From: Michael Richardson <[email-masked]>
> Date: July 23, 2010 1:57:34 AM CEDT
> To: roll WG <[email-masked]>, [email-masked]
> Subject: Re: [Roll] Signature schemes and IPR in RPL
>
>
>   Kyoto Plus: watch the video <http://www.youtube.com/watch?v=kzx1ycLXQSE 
> >
> 	               then sign the petition.
>
>
>
>

---

From: Michael John <[email-masked]>
Date: Fri, 23 Jul 2010 14:51:56 +0200

JP, all,

> I would prefer this.

>    Philip> is unencumbered by IPR. Let's call this the "Both" option.
This is also feasible, but I that case I would suggest to make the second
algorithm the default (use ID=0).

---

From: Michael Richardson <[email-masked]>
Date: Fri, 23 Jul 2010 09:11:54 -0400

My preferences had a typo:

> I consider (1) and (3b) to be completely un-acceptable.
                     ****

---

From: Michael Richardson <[email-masked]>
Date: Fri, 23 Jul 2010 09:15:12 -0400

>> question: "Shall the only MUST signature algorithm be

    Philip> Except, of course, that supporting signatures is not a
    Philip> MUST. It is entirely acceptable, within the current
    Philip> specification, to have a RPL implementation that supports
    Philip> only unsecured mode, just as it is acceptable to have a RPL
    Philip> implementation that rejects all unsecured messages.

This does not change things at all.  You speak about how a specific
network (LLN) is configured.  I speak about what features a device MUST
implement in order to be compliant to the specification.

In fact, this observation makes the problem more acute.  

In the absense of a MUST to implement IPR-unencumbered signature
mechanism, then many devices will be created which do not support any
such mechanism, and nearly all RPL networks that do not have security at
the layer-2, will be insecure. 

- --

---

From: Ulrich Herberg <[email-masked]>
Date: Fri, 23 Jul 2010 16:54:31 +0200

Hi,

I was wondering whether the DT has any specific alternate unencumbered
signature algorithms in mind. It may be easier to decide when having a
concrete alternative, in order to compare performance / length of
signatures.

Also, are there any such similar "reasonable non-discriminatory IPR
terms" with Certicom, as with Cisco?
(https://datatracker.ietf.org/ipr/720/)

Ulrich

On Fri, Jul 23, 2010 at 3:15 PM, Michael Richardson <[email-masked]> wrote:
>    >> So a better choice would be to present the working group with
>    >> question: "Shall the only MUST signature algorithm be
>    >> IPR-encumbered?"
>
> iQEVAwUBTEmV34CLcPvd0N1lAQLZ5QgAh0ud8ASJVkBj9vhgMieRDNOboy/ke5mE
> M7XXZH5bmBYPJkuQW0HuHwGP5xZEYPhRgpx+piAjsi9WZttTNXXipdr7g9vCXqB0
> duj4OuY/wLONHZJpw/PBVtWbZ5laq56+VieH09D/5lxUGhkd/iRNsoiKNSDvXkSq
> FkU5Wr/D8D6GAbc4efOrbNqYfuxehKB83PcxuchVWPfm1sShkQxfZOxrw+uMKctJ
> 1Qzws4E8auX9J+ja49xn4kxeproz5UzdjgHI/5RHSMlup2qmOtMJ/H1VbkQYrcDW
> GeD1ie5Us0QqC84259gLAzCklwcEqA0QpmQvo6CV0mZbjk0jgdhk1A==
> =DZY4

---

From: Philip Levis <[email-masked]>
Date: Fri, 23 Jul 2010 09:22:28 -0700

> I agree.  When link layer security is relied upon then we should state so, in the draft, with the names of the link layer security.
> 

Alex, I think these discussions might be more productive if you read the RPL draft, as well as the motivating application drafts, before making forceful comments about how RPL should work.

3.3.3.  Security

   RPL supports message confidentiality and integrity.  It is designed
   such that link-layer mechanisms can be used when available and
   appropriate, yet in their absence RPL can use its own mechanisms.
   RPL has three basic security modes.

Phil

---

From: David Culler <[email-masked]>
Date: Fri, 23 Jul 2010 11:47:15 -0700

While the various companies that have disclosed IPR relative to RPL have been generous in enabling the standard to move forward, it behooves us to do everything we can to create  standards that do not require proprietary IP to achieve interoperable implementations.  It seems clear that we should pursue a variant of 2.  We should complete the core spec utilizing a security scheme that is unencumbered.  We should make sure that there is enough room in the encoding that we may consider more highly optimized schemes later.  In that time, we can sort out IPR issues.    With so many signature schemes already well established it would be very surprising that we simply cannot use any of them.  The disclosed IPR may provide substantial improvements, but that is certainly a secondary concern.

Can the security DT suggest one or more such openly available options.

---

From: Alexandru Petrescu <[email-masked]>
Date: Sat, 24 Jul 2010 11:20:25 +0200

Le 23/07/2010 18:22, Philip Levis a écrit :
>>> therefore optional.
>> I agree.  When link layer security is relied upon then we should
>> state so, in the draft, with the names of the link layer security.
>>
>>> One of the stated design goals from the beginning is that RPL
>>> should not require security mechanisms when they are not needed.
>>
> Alex, I think these discussions might be more productive if you read
> the RPL draft, as well as the motivating application drafts, before
> making forceful comments about how RPL should work.
>
> 3.3.3.  Security
>
> appropriate, yet in their absence RPL can use its own mechanisms. RPL
> has three basic security modes.

Thanks Phil for pointing to this text specifically.  I will also follow
private indications to read the document.

Link layer security being reflected in the draft would mean to name that
link layer security, the protocol and algorithm names specific to that
link layer security.  I think currently it doesn't...

For example it never says the name of that particular link layer, or at
least I can not find it.  I may need to search more.

Alex

---

From: JP Vasseur <[email-masked]>
Date: Sat, 24 Jul 2010 12:23:50 +0200

[snip]

> least I can not find it.  I may need to search more.

We do not name the link layer and should not. RPL is L3, link layer  
"agnostic".
As pointed out, one may choose to implement the routing security  
mechanisms
specified in the draft, depending on what is available at the link  
layer. This should
go in some "deployment" guide, not here.

Thanks.

JP.

---

From: Ulrich Herberg <[email-masked]>
Date: Sat, 24 Jul 2010 14:57:36 +0200

> Can the security DT suggest one or more such openly available options.

I fully agree. There should be other, unencumbered algorithms, which
provide similar levels of performance and signature lengths. It would
be good to investigate these.

Ulrich

---

From: Philip Levis <[email-masked]>
Date: Sat, 24 Jul 2010 06:06:58 -0700

> be good to investigate these.

Ulrich,

I fully agree as well. It turns out that such algorithms which are unencumbered by IPR are not *that* easy to find, however. I consulted with my resident cryptographic expert, Dan Boneh[1]. He suggested an algorithm which he developed in 2001 or so, based on the Weil pairing[2], which is completely open and has no encumbering IPR. At first glance, it seems to possibly be technically superior than the Certicom-encumbered one in terms of factors we care about (e.g., signature length), which was already very attractive. There are reference implementations[3], and the FAA is beginning to incorporate it into some of their systems. The security DT is currently examining the algorithm. I hope to give an update soon.

Phil

[1] http://crypto.stanford.edu/
[2] http://crypto.stanford.edu/~dabo/pubs/abstracts/weilsigs.html
[3] http://crypto.stanford.edu/pbc/

---

From: Alexandru Petrescu <[email-masked]>
Date: Sat, 24 Jul 2010 23:15:01 +0200

Le 24/07/2010 15:06, Philip Levis a écrit :
>> On Fri, Jul 23, 2010 at 8:47 PM, David
>> Culler<[email-masked]>  wrote:
>>> While the various companies that have disclosed IPR relative to
>>> RPL have been generous in enabling the standard to move forward,
>>>  it behooves us to do everything we can to create  standards that
>>>  do not require proprietary IP to achieve interoperable
>>> implementations.  It seems clear that we should pursue a variant
>>>  of 2.  We should complete the core spec utilizing a security
>>> scheme that is unencumbered.  We should make sure that there is
>>> enough room in the encoding that we may consider more highly
>>> optimized schemes later.  In that time, we can sort out IPR
>>> issues.    With so many signature schemes already well
>>> established it would be very surprising that we simply cannot use
>>> any of them.  The disclosed IPR may provide substantial
>>> improvements, but that is certainly a secondary concern.
>>>
>> I fully agree. There should be other, unencumbered algorithms,
>> which provide similar levels of performance and signature lengths.
>>  It would be good to investigate these.
>
> Ulrich,
>
> I fully agree as well. It turns out that such algorithms which are
> unencumbered by IPR are not *that* easy to find, however.

WEll, I wonder about MD4 and MD5: are they free of IPR and easier to
export control? ("export control" is the US or other country law making
it difficult to export to other countries, thus hard to use Internet-wide).

This question may be off the current security thinking in RPL, and it
may show I have no experience at all, but I felt I would just ask -
sorry for disturbing.

> I consulted with my resident cryptographic expert, Dan Boneh[1]. He
> suggested an algorithm which he developed in 2001 or so, based on
> the Weil pairing[2], which is completely open and has no encumbering
> IPR. At first glance, it seems to possibly be technically superior
> than the Certicom-encumbered one in terms of factors we care about
> (e.g., signature length), which was already very attractive. There
> are reference implementations[3], and the FAA is beginning to
> incorporate it into some of their systems. The security DT is
> currently examining the algorithm. I hope to give an update soon.

WEll the first questions I'd ask is - is it a published or a secret
algorithm?  Is it implemented?  Is the implementation available under
some good license?  Have many eye-balls read and tried to attack?  Etc.

(not to ask whether it's been already documented in a draft, that could
come later).

Alex

>
> Phil
>
> [1] http://crypto.stanford.edu/ [2]
> http://crypto.stanford.edu/~dabo/pubs/abstracts/weilsigs.html [3]
> http://crypto.stanford.edu/pbc/
>
>
> _______________________________________________ Roll mailing list
> [email-masked] https://www.ietf.org/mailman/listinfo/roll
>

---

From: Alexandru Petrescu <[email-masked]>
Date: Sun, 25 Jul 2010 00:08:58 +0200

But earlier the draft says:

> In compliance with the layered architecture of IP, RPL does not rely
> on any particular features of a specific link layer technology.

which I interpret as saying RPL does not use any feature from the link
layer (e.g. security).

I think these two paragraphs sound contradictory(?)

Alex

---

From: Philip Levis <[email-masked]>
Date: Sun, 25 Jul 2010 12:53:01 -0700

> which I interpret as saying RPL does not use any feature from the link

Rely and use have distinct meanings. From the OED:

rely verb ( -lies, -lied) [ intrans. ] ( rely on/upon)
depend on with full trust or confidence : I know I can rely on your discretion.
• be dependent on : the charity has to rely entirely on public donations.

use verb 
1 |yoōz| [ trans. ]  take, hold, or deploy (something) as a means of accomplishing a purpose or achieving a result; employ : she used her key to open the front door | the poem uses simple language.
• take or consume (an amount) from a limited supply of something : we have used all the available funds.
• exploit (a person or situation) for one's own advantage : I couldn't help feeling that she was using me.

RPL does not *rely* on particular link layer technologies: it does not depend on them, and can, in this context, meet its security requirements without link layer security mechanisms. 

However, a given RPL application can *use* security capabilities of the link layer (or other layers), if they are available, instead of RPL's security mechanisms, if doing so is advantageous to meeting application requirements. 

As a trivial example, let's suppose there is a RPL application that needs message integrity, and the link layer provides sufficient integrity guarantees to meet the application requirements. RPL allows the application developer to use the link layer mechanisms, rather than force the RPL Instance to employ RPL-level integrity. Does that make sense? Recall, many RPL applications are closed networks under a single administrative domain.

> I think these two paragraphs sound contradictory(?)

Does this clear it up?

Phil

---

From: Ulrich Herberg <[email-masked]>
Date: Sun, 25 Jul 2010 22:30:41 +0200

On Sat, Jul 24, 2010 at 3:06 PM, Philip Levis <[email-masked]> wrote:
>[...]

Phil,

thanks for these references. That sounds like an interesting
alternative to the Certicom-encumbered algorithm. Are you aware how
this algorithm would perform on typical devices which are intended to
run RPL?

Ulrich

---

From: David Culler <[email-masked]>
Date: Mon, 26 Jul 2010 03:03:29 -0700

Indeed.  We run IP over ieee 802.11 links.  Layer 3 does not depend on particular properties of the links, but that does not mean the we cannot use WiFi encryption.  The same would apply to IEEE 802.15.4.  Furthermore, the IETF did not have to specify WPA in order to utilize it.