Subject: [core] [Technical Errata Reported] RFC7252 (5429)

From: RFC Errata System <[email-masked]>
Date: Wed, 18 Jul 2018 07:47:54 -0700 (PDT)

The following errata report has been submitted for RFC7252,
"The Constrained Application Protocol (CoAP)".

--------------------------------------
You may review the report below and at:
http://www.rfc-editor.org/errata/eid5429

--------------------------------------
Type: Technical
Reported by: Marian Buschsieweke <[email-masked]>

Section: 4.4

Original Text
-------------
An Acknowledgement or Reset message is related to a Confirmable
message or Non-confirmable message by means of a Message ID along
with additional address information of the corresponding endpoint.
The Message ID is a 16-bit unsigned integer that is generated by the
sender of a Confirmable or Non-confirmable message and included in
the CoAP header.  The Message ID MUST be echoed in the
Acknowledgement or Reset message by the recipient.

The same Message ID MUST NOT be reused (in communicating with the
same endpoint) within the EXCHANGE_LIFETIME (Section 4.8.2).

Implementation Note:  Several implementation strategies can be
  employed for generating Message IDs.  In the simplest case, a CoAP
  endpoint generates Message IDs by keeping a single Message ID
  variable, which is changed each time a new Confirmable or Non-
  confirmable message is sent, regardless of the destination address
  or port.  Endpoints dealing with large numbers of transactions
  could keep multiple Message ID variables, for example, per prefix
  or destination address.  (Note that some receiving endpoints may
  not be able to distinguish unicast and multicast packets addressed
  to it, so endpoints generating Message IDs need to make sure these
  do not overlap.)  It is strongly recommended that the initial
  value of the variable (e.g., on startup) be randomized, in order
  to make successful off-path attacks on the protocol less likely.

Corrected Text
--------------
An Acknowledgement or Reset message is related to a Confirmable
message or Non-confirmable message by means of a Message ID along
with additional address information of the corresponding endpoint.
The Message ID is a 16-bit unsigned integer that is generated by the
sender of a Confirmable or Non-confirmable message and included in
the CoAP header.  Message IDs of subsequence messages send to the
same endpoint within EXCHANGE_LIFETIME MUST be strictly ascending
(wrapping around at a value of 65535).  Additionally, two
subsequently send Message IDs to the same endpoint SHOULD have a
difference of at most 16.  The Message ID MUST be echoed in the
Acknowledgement or Reset message by the recipient.

The same Message ID MUST NOT be reused (in communicating with the
same endpoint) within the EXCHANGE_LIFETIME (Section 4.8.2).

Implementation Note:  Several implementation strategies can be
  employed for generating Message IDs.  In the simplest case, a CoAP
  endpoint generates Message IDs by keeping a single Message ID
  variable, which is incremented each time a new Confirmable or Non-
  confirmable message is sent, regardless of the destination address
  or port.  Endpoints dealing with large numbers of transactions
  could keep multiple Message ID variables, for example, per prefix
  or destination address.  (Note that some receiving endpoints may
  not be able to distinguish unicast and multicast packets addressed
  to it, so endpoints generating Message IDs need to make sure these
  do not overlap.)  It is strongly recommended that the initial
  value of the variable (e.g., on startup) be randomized, in order
  to make successful off-path attacks on the protocol less likely.

Notes
-----
Without any restrictions on how Message IDs are generated, an implementation of CoAP duplication detection must be prepared to receive a random sequence of Message IDs.
One simple implementation strategy would be to store the received Message IDs along with a timestamp when they were received.
If a 16 bit time stamp would be used, 4 Bytes per tracked Message ID would be required.
If additionaly a CoAP server expects requests to be received at a rate of 1 message per second, at least 247 * 4 Byte or approximately 1 KiB have to be allocated per client.
A class 1 (see RFC 7228 Section 3) server could handle at most 10 clients in parallel, if anything apart duplicate detection could be implemented without using any memory at all.

If instead Message IDs have to be generated by incrementing a (global or per endpoint/network prefix/...) counter variable, duplicate detection can be implemented in a time and memory efficient way without limiting the rate of the message exchange between to nodes.

Instructions:
-------------
This erratum is currently posted as "Reported". If necessary, please
use "Reply All" to discuss whether it should be verified or
rejected. When a decision is reached, the verifying party  
can log in to change the status and edit the report, if necessary. 

--------------------------------------
RFC7252 (draft-ietf-core-coap-18)
--------------------------------------
Title               : The Constrained Application Protocol (CoAP)
Publication Date    : June 2014
Author(s)           : Z. Shelby, K. Hartke, C. Bormann
Category            : PROPOSED STANDARD
Source              : Constrained RESTful Environments APP
Area                : Applications
Stream              : IETF
Verifying Party     : IESG

---

From: Christian Amsüss <[email-masked]>
Date: Thu, 19 Jul 2018 18:02:22 +0200

Hello Marian, hello CoRE WG,

(CC list stripped expecting that the authors are subscribed to CoRE)

On Wed, Jul 18, 2018 at 07:47:54AM -0700, RFC Errata System wrote:
> [...] Message IDs of subsequence messages send to the
> difference of at most 16.
> [...]
> 
> Notes
> -----
> Without any restrictions on how Message IDs are generated, an
> implementation of CoAP duplication detection must be prepared to
> receive a random sequence of Message IDs.
>
> One simple implementation strategy would be to store the received
> Message IDs along with a timestamp when they were received.
>
> If additionaly a CoAP server expects requests to be received at a rate
> of 1 message per second, at least 247 * 4 Byte or approximately 1 KiB
> have to be allocated per client.
>
> A class 1 (see RFC 7228 Section 3) server could handle at most 10
> clients in parallel, if anything apart duplicate detection could be
> implemented without using any memory at all.
> 
> If instead Message IDs have to be generated by incrementing a (global
> or per endpoint/network prefix/...) counter variable, duplicate
> detection can be implemented in a time and memory efficient way
> without limiting the rate of the message exchange between to nodes.

The memory requirements may have their point, but I think that this
change would be far too severe for an erratum. If servers started
relying on this change, that would easily invalidate duplicate message
detection with existing implementations that use a single increasing
message ID counter for all their peers.

That aside, I'm not sure the overhead estimations work that way.
Duplicate message detection not only means that the message ID and the
timestamp must be stored (your 4 bytes), but also the often much larger
response message. As that is costly and should be avoided, constrained
implementations will look into whether they need to deduplicate at all:

* For safe or idempotent request messages, message deduplication can be
  skipped. (You'd build the response to a GET once again when a
  duplicate hits you rather than storing the old response. For PUT,
  you'll set the resource's state anew, and if that's part of a race
  condition, so would a delayed package have been).

  Even some cases of POST can be treated like that (the application
  would need to let the library know that).

* For observe notifications, the recipient would silently disregard the
  apparently out-of-order package.

* For non-observe non-piggy-backed responses, the client would RST the
  duplicate response rather than ACK it, which is just as good. (There
  are no "The client received the response" semantics to the ACK).

Constrained implementations should avoid keeping MIDs and timestamps
around for any of those.

Only non-idempotent (POST; which most applications will try to avoid)
requests actually need the duplicate detection -- and then, there is
also a response message to store, and then the overhead of actually
storing the MID becomes far less significant.

I'd be happy to be shown wrong, so please let's have the discussion if I
am, but this is not something that should easily go into the errata.

Best regards
Christian

-- 
To use raw power is to make yourself infinitely vulnerable to greater powers.
  -- Bene Gesserit axiom

---

From: Marian Buschsieweke <[email-masked]>
Date: Thu, 19 Jul 2018 22:01:47 +0200

Dear Christian,

thanks for the fast reply.

> message ID counter for all their peers.

The suggested change does not make it mandatory to have more than one counter.
The only mandatory change would be to actually use counters (one or more)
at all and to increment them for generating a new Message ID. It is
suggested to use more than one counter if a node is communicating with many
nodes at the same time, as it SHOULD keep jumps in Message IDs less than or
equal to 16. With messages coming in out of order or being lost a server still
expects jumps to be potentially bigger. But it is extremely likely that
Message IDs will remain in a range of lets say 64 consecutively numbers
(wrapping around at 65535). As a result, only the number of the lowest
expected Message ID needs to be stored and a 64 bit bitmask can be used to
store which Messages IDs have so far been used. This "window" can be moved
upwards as needed and any Message ID below that "window" is almost certainly a
duplicate. (I can provide more details how an efficient implementation could
look like and how also the time can be tracked efficiently regarding memory and
computational requirements - but I believe that might not be relevant for the
discussion.)

As far as I know, no CoAP implementation that is actively used employs a
different strategy than using counter(s) and increments it/them. If that is
true, it wouldn't hurt to make that behavior mandatory.

> response message.

This is only partly true. With NSTART = 1 at most one request is outstanding. As
a result, at most one response needs to be cached per client - a client would
not send a new request without having the last response received or no longer
expecting to receive the response. The required memory for a single response is
usually much less than the 1 KiB for duplicate detection.

> requests actually need the duplicate detection

In a scenario with many simultaneous clients this might not be true. E.g. if
Client A turns smart light on and Client B turns it off (e.g. "PUT /light on"
and "PUT /light off"), both requests would be idempotent. The expected result
would be that on requests comes in first - let's say the one of client A. So
the light turns first on and than off. But with many duplicates and no
duplicate detection, the light would be constantly switching on and off.

Kind regards,
Marian

-------------------------------------------------------------
M.Sc. Marian Buschsieweke
Dept. Communication and Networked Systems (ComSys)
Institute for Intelligent Cooperating Systems (IKS)
Otto-von-Guericke-University of Magdeburg
Universitätsplatz 2, Building 29, Room 314
39106 Magdeburg
Germany

http://www.comsys.ovgu.de/Team/Marian+Buschsieweke.html
Tel.: +49 - 391 - 67 - 52673
Fax:  +49 - 391 - 67 - 41161

-------------------------------------------------------------

On Thu, 19 Jul 2018 18:02:22 +0200