Subject: Re: [Roll] sequence number increment and wrap

From: Tzeta Tsao <[email-masked]>
Date: Mon, 01 Feb 2010 10:06:09 -0500

Indeed, replay protection can be a deceptively simple problem. For 
example, here is a security analysis on 802.15.4 and it has a lot to say 
about 15.4's Access Control List, which is based on a counter: 
http://www.cs.berkeley.edu/~daw/papers/15.4-wise04.pdf.

Maintaining a counter for every neighbor may present a problem for some 
devices. Suppose one uses MiniSec's approach: 
http://sparrow.ece.cmu.edu/group/pub/luk_mezzour_perrig_miniSec.pdf. In 
this case, a device sends one-byte counter in the message for sync but 
actually keeps a multi-byte counter per neighbor: in many situations it 
will wind up needing a few k bytes.

Some networks/devices have time, so using timestamp for anti-replay is 
another option. Of course, a complete design will need to address issues 
such as re-sync of states due to power outages, etc.; the question is 
then if it is possible for us to put requirements on the rest of the system.

Tzeta

Michael Richardson wrote:
> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
> 
> 
> Are there any security implications in the sequence number?
> 
> (I realize that the security architecture is not complete. 
> I assume that there will be some kind of per-message authenticator (MAC)
> How this is keyed is really the hard part of the architectured)
> 
> Typically, there is some concern if there is a replay of a lower
> sequence number.  Such an event causes the network to return to some
> earlier state.  The concern is that an attacker can record a previously
> authenticated set of messages and then play them back, intentionally
> causing such a time travel.  
> 
> One question is: is this a threat?
> 
> The usual defense against that is that the sequence number must be
> monotonically increasing.   If a nodes has been out of communication for
> a period of time, it may see a abrupt jump in sequence number, but
> that's okay --- if the authentication checks out, it advances.
> 
> The problem is that we have an 8-bit field, and it isn't clear how much
> it may advance --- advances of 254 for instance, look like going
> backwards 1, and may be disallowed.
> 
> The text in -05 is:
> 
>    Sequence Number:  8-bit unsigned integer set by the DODAG root,
>          incremented according to a policy provisioned at the DODAG
>          root, and propagated with no change down the DODAG.  Each
>          increment SHOULD have a value of 1 and may cause a wrap back to
>          zero.
> 
> 
> It is good that the text tells what the DODAG should do, but we need to
> know what happens if there is an increment of more than 1, and how to
> know when there is an increment of more than 1, when it is a wrap.
> 
> My first suggestion is that increments of up to 127 should be acceptable, as
> can unambiguously be understood to be increments (with possible
> wraps).  Further, any increment which does not cause a wrap can be
> accepted as well.
> 
> What I think would decide this is to understand under what conditions
> the sequence number can and should be incremented? 
> 
> - From my understanding, it's a DAG Iteration, and I think that this will
> happen somewhat often --- not as often as once a second, but certainly
> more often than once an hour.   
> 
> It is also my understanding that many DIO messages will be sent with the
> same sequence number --- it is not incremented each time the DIO is
> sent.
> 
> I therefore suggest renaming this field to "DIO Iteration Number".
> 
> - -- 
> ]       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. 
> 
> 
> 
> 
> 
> 
>    
> 
> 
> -----BEGIN PGP SIGNATURE-----
> Version: GnuPG v1.4.9 (GNU/Linux)
> Comment: Finger me for keys
> 
> iQEVAwUBS2Y2XoCLcPvd0N1lAQL0BwgAvyVovfNupQL7MjNOB/KDM3UaJJS0vVli
> yzKliEF7CvhrT8nxowLKK40XCyDp5vUNIzVMZrZOSknXcfyJdlWgFEVS7E4lcTz6
> mSJJ4pyIAmSiUlBTka5p8YJqtzSDBRsEA4Egz0fRXJyhN2kdbw3kLOcTId6WeB0o
> +MJMnl1DjFryahQP8cuqwBy6nTgshqmPFsMUPFnf4jvUIZsK6L3Ucmp8SjUUndMI
> i8f4JWAsq/3/hMqfaAZYTAqmzlXBscLWh+lpzd5OOvfGS8vCf8/CZr3ewrvkDo7f
> 9iAqcw8DiSqNAmPUu6UT+Bf/MledzDflFCOlKSl5l0v28Y6bE3FccA==
> =6mQT
> -----END PGP SIGNATURE-----
> _______________________________________________
> Roll mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/roll
>

---

From: "Rene Struik" <[email-masked]>
Date: Mon, 1 Feb 2010 13:11:40 -0500

Dear Michael:

For a summary of security considerations, please also cf. the slides of
my presentation at the IETF-76 meeting, Hiroshima, Japan, November 9-13,
2010.
The requirement for replay protection and timeliness is captured on
Slide 4; structure of keying material on Slide 7. Here, timeliness would
imply that one can detect stale frames (e.g., those that have been
captured somewhere else in the network and are propagated elsewhere with
a large delay).

One cautionary note on references to 802.15.4: this term is really
ambiguous, since 802.15.4-2006 totally rewrote the "security" provisions
of 802.15.4-2003 (to which the 2004 paper by David Wagner and Naveen
Sestry that Tzeta Tsao referenced below refers to). Ironically, IETF
still overwhelmingly uses 802.15.4-2003. For a summary of changes to
802.15.4 currently underway, cf. the slides of my presentation at the
IETF-75 meeting, Stockholm, Sweden, July 27-31, 2009. The suggestion to
move away from 802.15.4-2003 (which has been deprecated since 2006
anyway) is captured on Slide 15 of the consolidated slide deck.

Best regards, Rene

Rene Struik, Update on IEEE 802.15.4e, IETF-75, Stockholm, Sweden, July
27-31, 2009
http://www.ietf.org/proceedings/75/slides/6lowpan-0.pdf 

Rene Struik, Reflections on Security Architectural Framework RoLL,
IETF-76, Hiroshima, Japan, November 9-13, 2009
http://www.ietf.org/proceedings/76/slides/roll-0/roll-0_files/frame.htm

-----Original Message-----
From: [email-masked] [mailto:[email-masked]] On Behalf Of
Tzeta Tsao
Sent: Monday, February 01, 2010 10:06 AM
To: Michael Richardson
Cc: IETF ROLL
Subject: Re: [Roll] sequence number increment and wrap

such as re-sync of states due to power outages, etc.; the question is 
then if it is possible for us to put requirements on the rest of the
system.

Tzeta

Michael Richardson wrote:
>    Kyoto Plus: watch the video
<http://www.youtube.com/watch?v=kzx1ycLXQSE>

---

From: Michael Richardson <[email-masked]>
Date: Thu, 04 Feb 2010 03:23:45 -0500

>>>>> "Tzeta" == Tzeta Tsao <[email-masked]> writes:
    Tzeta> Indeed, replay protection can be a deceptively simple
    Tzeta> problem. For example, here is a security analysis on 802.15.4
    Tzeta> and it has a lot to say about 15.4's Access Control List,
    Tzeta> which is based on a counter:
    Tzeta> http://www.cs.berkeley.edu/~daw/papers/15.4-wise04.pdf.

    Tzeta> Maintaining a counter for every neighbor may present a
    Tzeta> problem for some devices. Suppose one uses MiniSec's

Yes, it certainly is a problem.

    Tzeta> approach:
    Tzeta> http://sparrow.ece.cmu.edu/group/pub/luk_mezzour_perrig_miniSec.pdf. In
    Tzeta> this case, a device sends one-byte counter in the message for
    Tzeta> sync but actually keeps a multi-byte counter per neighbor: in
    Tzeta> many situations it will wind up needing a few k bytes.

That's the method that RFC4301 (IPSEC) style ESP uses to get 64-bit replay
counters for very high speed networks, where a 32-bit replay counters
rolls in a matter of minutes.   A counter roll otherwise causes a rekey.

In the case of RPL, the SequenceNumber in the DAG header in the DIO is
incremented only when there is some material change to the network.  I'm
not yet clear what this might be --- the information is, however,
retransmitted multiple times by the DAG root (and subsequent nodes).  

When the information changes, there is a new SequenceNumber, which
causes a DAG Iteration, and nodes have to re-evaluate their situation,
moving to the new DAG Iteration in an organized way.
 
I'm pretty sure that the subsequent nodes need to add/modify to the DIO
as it it passed out --- I do not think the L4 payload can be just
resent. (Clearly the L2 and L3 information changes).  That is, any
authentication placed on the packet has to be recalculated by each node
on a hop-by-hop basis.

This is important, because it implies that there are many messages which
can be replayed, and each one needs some seperate tracking.

But, so far nobody has answered my key question:

     what happens to a DAG at Iteration N when information
     from DAG Iteration <N is resent.

Specifically, what happens to a node that last heard DAG Iteration 252,
and next hears DAG Iteration 3?  Is that a replay, or is it a counter
roll?

- --