Subject: [saag] Identifier uniqueness and draft-gont-predictable-numeric-ids

From: Martin Thomson <[email-masked]>
Date: Thu, 7 Apr 2016 15:44:10 -0300

I feel that the treatment of identifiers and the resulting taxonomy
needs to be considered differently.

Identifiers inherently need to uniquely identify things.  That is,
each identifier needs to identify a single thing [48].  I believe that
to be constant across these examples, though there might be some
confusion about what is being identified.  The example of v6 flow
labels suggests to me that the thing being labelled is not a single
flow, but the set of flows that will be collated.

What differs is the process by which uniqueness is guaranteed.
Uniqueness in many contexts is assured by fiat: an authority is known
to control a given space and only that authority can generate
identifiers in that space.  For example, a server controls what the
TCP port numbers its servers use identify.

We have a few examples where uniqueness is distributed (e.g., CGA) and
protocol mechanisms are used to ensure uniqueness.  There are specific
privacy and security considerations that arise from having a protocol
mechanism, so this method of arriving at uniqueness warrants some
discussion because it entails a new protocol, but I don't believe that
it justifies the hard/soft distinction in the proposed taxonomy.

Finally, the monotonically increasing category is not particularly
special.  The identifier (e.g., a TCP sequence number) still uniquely
identifies a subject (in this case, the first octet of a segment).
The process for ensuring uniqueness is merely different.

[48] A thing might have multiple identifiers, a fact that might be
exploited by this document.

---

From: Adam Montville <[email-masked]>
Date: Thu, 7 Apr 2016 15:55:19 -0300

> On Apr 7, 2016, at 3:44 PM, Martin Thomson <[email-masked]> wrote:
> 
> each identifier needs to identify a single thing [48].

+1

> I believe that

+1  Additionally, such multiple identifiers might be assigned to one thing by multiple authorities.

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

---

From: Programa STIC <[email-masked]>
Date: Thu, 7 Apr 2016 19:37:00 -0300

Hello Martin, thanks for your comments, see mine inline

El 7/4/16 a las 15:44, Martin Thomson escribió:
> confusion about what is being identified.

Indeed, identifiers identify things _within a given context_. To avoid a
recursive definition and to try to narrow down the scope of the document
just to numeric ids we defined  "identifier" in section 2 as:
	
	A data object in a protocol specification that can be used to
      definetely distinguish a protocol object (a datagram, network
      interface, transport protocol endpoint, session, etc) from all
      other objects of the same type, in a given context.
	Identifiers are usually defined as a series of bits and
      represented using integer values.  We note that different
      identifiers may have additional requirements or properties
      depending on their specific use in a protocol.  We use the term
      "identifier" as a generic term to refer to any data object in a
      protocol specification that satisfies the identification property
      stated above.

We believe the above definition should capture accurately what you
wrote. Note however that we introduced the "within context" qualifier
because an identifier value could be repeated in different contexts and
still identify a unique thing in each of them, i.e. the value of the
IPv4 ip_id generated by an IP stack could be repeated over time its
running but it would still identify a single packet during its lifetime
on the network.

If you feel the above definition needs to be tweaked please let us know
of suggested changes. One possible change could be to substitute
"definetely" with "uniquely" but I don't know if that's strictly necessary.

>  The example of v6 flow

This I will need to look into, for now I defer to Fernando to comment on.
> TCP port numbers its servers use identify.

Centralized, delegated, federated or distributed generation of
identifier values does not guarantee uniquess per se, its all dependent
on the algorithms used. In some scenarios, for example a central
authority that generates identifiers on demand, some algorithms will
guarantee uniqueness (ie. a global variable initialized and incremented
by 1 for each request of a new id) while in other scenarios other
algorithms may accomplish the same (ie. a lookup on a table of
precomputed values). However, the point we are trying to raise is that
from the security & privacy perspective, in many cases uniqueness is not
sufficient. In many cases non-predictability and collision resistance
are additional properties desired or even needed to avoid attack.

During the session today somebody (sorry I did not write down your name)
indicated that perhaps it is good to differentiate identifier values
that are generated at "spec time" or/and that remain fixed throughout
the lifetime of the protocol from those that are generated dynamically
at runtime by the protocol's implementation. I concur.

Our draft seeks to analyze S&P issues with the latter and present some
guidelines to both designers and implementors on how to spec identifiers
and how to select suggested algorithms for implementation.

> it justifies the hard/soft distinction in the proposed taxonomy.

The hard/soft distinction in the draft is applied to interoperability.
We what to use the distinction to point out that there isn't bijection
between interop failure modes and S&P failure modes.

What may be considered a "soft failure" for interoperability (ie. a id
collision on a DNS id) may end up being one or more "hard" failures or
serious problems in the security & privacy context (ie. DNS cache
poisoning).

On the other hand, hard failures in interoperability almost always imply
a vulnerability to denial of service attack.

What I took out from today's session is that we may need to make this
mapping more explicit.

> The process for ensuring uniqueness is merely different.

We believe it is indeed special. The point here is that requiring
monotonically increasing values for a identifier introduces additional,
and sometimes unneeded, property: an ordering relationship. The result
is a protocol field that is "semantically overloaded", it is not just
unique but can also be used to order bytes, or even to order sequences
of bytes. In some cases this property is needed or desirable, in other
cases it is totally unneeded. Again, here we can see how a global
counter incremented by 1 per packet does something more than just ensure
uniqueness.

A protocol that defines an Identifier that needs to be unique (within
context) but specifies generation of its values using a monotonically
increasing sequence is "over specifying" the ID definition and should
trigger a warning in a S&P review.

Likewise a a protocol that defines an Identifier that needs to be unique
but does not properly describe the context or provide guidance on how to
achieve is under specified.

Thanks for your feedback,

-ivan

---

From: Martin Thomson <[email-masked]>
Date: Fri, 8 Apr 2016 10:51:39 -0300

> just to numeric ids we defined  "identifier" in section 2 as:

Yes, agree, context matters.

>       other objects of the same type, in a given context.

The word you want is "definitively".

>       represented using integer values.

Be careful.  You are talking about numeric identifiers.

>  We note that different

This is an important point that gets right to the core of the issue,
particularly when it comes to the topic of linkability.  A good
discussion of this would go a long way to forming a good foundation
for the document.

> "definetely" with "uniquely" but I don't know if that's strictly necessary.

I don't have a good answer for the question, but you make a
distinction between fixed sized integer identifiers and other
identifiers.  It's not clear what relevance that delineation has on
this subject.

> are additional properties desired or even needed to avoid attack.

A section/paragraph that says exactly that would be a massive
improvement.  It belongs in the introduction.

> at runtime by the protocol's implementation. I concur.

So do I; my email was - in part - about identifying another
distinction.  That is, between centralized and decentralized
generation.  I think that in this context, the "spec time" vs. runtime
distinction isn't especially relevant to the topic of the draft, but
would be happy to see analysis that suggested otherwise.

> between interop failure modes and S&P failure modes.

Yes, that is a very good point to make.  That establishes that
interoperability constraints on a protocol design are different to
security and private constraints.  Like the previous point on
uniqueness, if you make this point, make it up front, in the intro.

> counter incremented by 1 per packet does something more than just ensure

Fair point.

> trigger a warning in a S&P review.

Interesting perspective.  I'm not convinced that is possible in all
cases.  I'm guessing that it could be difficult to sell that to the
community, even in the current climate, without some strong backing.
That could be perceived as quite a heavy burden.

I would be interested in seeing a case study here.  For example, how
would you apply this principle to TCP sequence numbers?

> achieve is under specified.

Agreed.

On a related note, is this exclusively limited to identifiers that are
sent in a protocol?  Or the subset of those that are sent in the
clear?  Or are you also interested in implicit identifiers as well,
those things that are not put in protocol PDUs, but are conceptually
important for the functioning of the protocol.

Further thoughts: this discussion sort of suggests to me that the
scope of this work is a little ambitious for a single draft.  Maybe
you could think some more about how you might reduce scope or divide
the work into more easily digestible pieces.

---

From: Fernando Gont <[email-masked]>
Date: Mon, 11 Apr 2016 19:14:26 -0300

Hi, Martin,

Thanks so much for your feedback! Please find my comments in-line....

> flow, but the set of flows that will be collated.

Not sure what you mean.

In general since an identifier of X length can only uniquely identify
2**X entities, one way or another there's always some probability of
collisions.

> TCP port numbers its servers use identify.

In many cases, guaranteeing uniqueness is tricky. E.g., Frag IDs, or UDP
ports or TCP ports might require keeping state... and in most cases,
that's undesirable.

> protocol mechanisms are used to ensure uniqueness. 

Yet in those cases DAD might succeed, incorrectly (e.g., multicast
packets being dropped), the node being temporarily down, etc.

> There are specific

Not sure what you mean. If you have a way of guaranteeing uniqueness,
then, at least in theory, you don't need to care about uniqueness when
generating the IDs. However, as noted above, in many cases you ned to
rely on uniqueness when you generate the IDs, because checking for
uniqueness is impossible, unreliable, or undesirable.

> The process for ensuring uniqueness is merely different.

For the "monotonically-increasing category", there are two requirements:
1) That the ID is unique.
2) That the ID is larger than the previously generated ID.

If you check uniqueness, you can achieve #1, but not #2.

> exploited by this document.

Could you please elaborate?

Thanks!

Cheers,
-- 
Fernando Gont
SI6 Networks
e-mail: [email-masked]
PGP Fingerprint: 6666 31C6 D484 63B2 8FB1 E3C4 AE25 0D55 1D4E 7492

---

From: Fernando Gont <[email-masked]>
Date: Mon, 11 Apr 2016 19:20:13 -0300

> This I will need to look into, for now I defer to Fernando to comment on.

This would be the "unintended consequence" of the collision, but not an
intended result. A collision of flow labels means that since your
"naming" 2+ entities the same thing, when doing load sharing/ECMP you'll
put all the corresponding packets on the same link.

That's why the failure severity is "none".

Thanks,

---

From: Martin Thomson <[email-masked]>
Date: Tue, 12 Apr 2016 14:03:47 +1000

> 2**X entities, one way or another there's always some probability of

If there are more than 2^x entities, or if identifiers are allocated
randomly, or if you don't have a globally consistent view when
allocating identifiers...

> ports or TCP ports might require keeping state... and in most cases,

My advice is to avoid small spaces if you are allocating at random.
However, I've never (yet) seen a case where a server is unable to
track which port numbers it has allocated.

> Could you please elaborate?

I have multiple email identifiers.  All cause an email packet to
eventually route toward me.  Hosts often have multiple IPs.

If any identifier from a set can be used to achieve the same net
result, you now have an opportunity to remove linkability.  Maybe.

---

From: Fernando Gont <[email-masked]>
Date: Tue, 12 Apr 2016 04:57:00 -0300

> allocating identifiers...

Exactly. Bottom-line is, you resort to reducing the id reuse frequency
as the mechanism to "ensuring" uniqueness.

> track which port numbers it has allocated.

Think about server restarts, cases where the client should be keeping
state but the client goes away, and a new client reusing the same IP
address comes in, etc.

For the IP{v4,v6} the case is even more clear, since the node does not
really record (i.e., keep state) the Frag IDs recently in use.

> eventually route toward me.  Hosts often have multiple IPs.

These things don't really name the same thing. An IP address identifies
the interface. The fact that you don't care on which you receive your
packets if a different thing.

> result, you now have an opportunity to remove linkability.  Maybe.

Agreed. But the usual thing here is that the identifiers in question are
really unrelated, but happen to be usable by some other (usually upper
layer) entity. e.g., a node employing multiple random addresses on the
same interface, or two multiple addresses each on a different (possibly
virtual) interface may remove linkability, not really because you're
naming the same thing in multiple ways, but rather because all
identifiers are usable in a similar way by the same upper-layer entity.

In any case.... are you suggesting that we include some text on the
topic of "linkability", or....?

Thanks!

Best regards,