Subject: AD Evaluation: draft-ietf-6man-predictable-fragment-id

From: Brian Haberman <[email-masked]>
Date: Fri, 21 Aug 2015 14:16:29 -0400

All,
     I have completed my AD evaluation of this draft as a part of the
publication process.  I only have two comments/questions on this draft.
Once those are resolved, it can move along in the publication process.

* Section 4 says the following:

   As a result, at least during the IPv6/IPv4 transition/co-existence
   phase, it is probably safer to assume that only the low-order 16 bits
   of the IPv6 Fragment Identification are of use to the destination
   system.

I think that statement is making an ill-advised generalization.  The
above is true if one is looking at an atomic fragment. However, even if
we are talking about a transition/co-existence phase, there will still
be significant amounts of fragmented traffic between IPv6 nodes where
the full 32 bits of the fragment id are useful. What was the rationale
for the above generalization?

* Section 5.3's discussion of a hash-based id generation scheme says
this in the drawbacks:

   o  Since the Fragment Identification values are predictable by the
      destination host...

How are the ID values predicted by the destination host?  The source is
using secret values that presumably are not shared with the destination.
So how does this prediction work?

Regards,
Brian

---

From: Fernando Gont <[email-masked]>
Date: Sat, 22 Aug 2015 03:50:47 +0200

Hi, Brian,

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

> for the above generalization?

The rationale is that, since you don't really know whether the remote
endpoint is really an IPv6 node or an IPv4 node behind a translator, the
only safe bet is to assume the worst ("it is a v4 node behind a
translator, and hence only the low order 16 bits are meaningful").

> So how does this prediction work?

These Frag ID values are predictable because the hash-based approach
leads to a monotonically-increasing sequence (e.g., 1, 2, 3, 4) then
it's easy to predict the sequence *by the destination host*. Of course,
such sequence is not predictable by an off-path attacker.

Thanks!

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

---

From: Brian Haberman <[email-masked]>
Date: Mon, 24 Aug 2015 08:18:15 -0400

Hi Fernando,

> translator, and hence only the low order 16 bits are meaningful").

If you are generating atomic fragments, you have a pretty good idea that
the lower 16 bits are the only ones that are meaningful. Has there been
any data collected on the number of fragmented IPv6 packets that are
destined for IPv4 nodes where the PMTU is >1280?  Or is this theoretical
analysis?

> such sequence is not predictable by an off-path attacker.

Monotonically-increasing?  The text in 5.3 clearly says:

   With such a scheme, the Fragment Identification value of
   each fragment datagram would be selected with the expression...

That, to me, indicates that each time a Fragment ID is generated, the
hash function is invoked.  How is it monotonically increasing if the
hash is invoked for each packet being fragmented?

Regards,
Brian

---

From: Fernando Gont <[email-masked]>
Date: Mon, 24 Aug 2015 09:43:30 -0300

Hi, Brian,

On 08/24/2015 09:18 AM, Brian Haberman wrote:
> the lower 16 bits are the only ones that are meaningful.

Yes. But if you're generating, say, 1280-byte or even 1500-byte
fragments, you might still be going through a translator.

(i.e., yes, you're right that for the "I'm generating atomic fragments
case" you could infer that you're going through a translator... but
generating atomic fragments is not a necessary condition for going
through a translator -- e.g., think of an 1500-byte MTU on the IPv4 side).

> Has there been

I think you cannot really measure that, since you cannot really tell
from the IPv6 address that the corresponding packets are being translated.

So the question really boils down to "is the IPv4 Internet's MTU >1280
in many cases?" (and the answer is, of course, "yes")  -- (in such cases
atomic fragments will not be generated).

> hash is invoked for each packet being fragmented?

A simplified version of the expression in Section 5.3 would be:

   Identification = F(Src IP, Dst IP, secret1)  +  counter.

If you're receiviving packets from the same src IP, to your same dst IP,
those two addresses will be constant. secret1 is also constant. Then the
expression results in:

 ID= F() + counter = random_number +  counter

for each (src IP, dst IP) (whre "counter" is a variable that is
incremented for each fragmented packet that is sent). Hence successive
packets will contain monotonically-increasing IDs (say {1, 2, 3..} ,
{345556, 345557, 345558,..} or whatever ).

FWIW, the expression in Section 5.3 replaces the "counter" variable
(from the simplified expression I wrote above) with an array of
counters, such that we can avoid the use of a single global counter (to
avoid e.g.  [Sanfilippo1998b] and [Sanfilippo1999])

Please let me know if this clarifies your question...

Thanks!

Best regards,

---

From: Brian Haberman <[email-masked]>
Date: Mon, 24 Aug 2015 09:00:12 -0400

> those two addresses will be constant. secret1 is also constant. Then the

Where in the text does it say that secret1 is constant?

As I noted in my last comment, it seems like the Fragment ID is
re-generated any time a Fragment Header is needed.  Is there any reason
why secret1 couldn't/shouldn't be changed each time a Fragment Header is
needed?

> avoid e.g.  [Sanfilippo1998b] and [Sanfilippo1999])

Right, the counter[] contains 8K elements or more where an element is
randomly selected via a hash function.  If that is the case, how does
the destination know what the next Fragment ID will be?

Regards,
Brian

---

From: Fernando Gont <[email-masked]>
Date: Mon, 24 Aug 2015 10:35:59 -0300

Hi, Brian,

> Where in the text does it say that secret1 is constant?

You're right: we should mention this explicitly.

> why secret1 couldn't/shouldn't be changed each time a Fragment Header is

Frag ID is generated ("Identification" recomputed) for each fragmented
packet. for any given (src, dst), F() will be constant.

So the idea is that F() provides a radom number/offset, which will
remain constant for each pair (src, dst). Since "counter" is a "line",
"Identification" is esentially:

ID = m x + b = counter + F()

i.e. a line with a random offeset.

The reason for using this algorithm is that it results in a sequence
that is not predictable by an off-path attacker. However, since
sbsequent identifications are simply monotonically-increasing numbers
(as a result of counter), the frag id collision rate will be wayyyy
lower than that of simply randmizing the IDs (the collission rate is the
same as that of a global counter).

> the destination know what the next Fragment ID will be?

They are "randomly selected", but, as with F(), for each (src ip, dst
ip), you will always select the same counter. So unless another flow
happens to use the same counter, if you receive one fragmented packet
with a frag ID of "M", the next frag packet will have an ID of "M+1".

(again, the reason for this is as before: reduce the frag id reuse
frequency, so that yu get the same frequency as a global counter, but
without its sec implications).

Thanks!

Best regards,

---

From: Brian Haberman <[email-masked]>
Date: Mon, 24 Aug 2015 09:55:42 -0400

> "Identification" is esentially:

As with secret1, where does it say that counter[] is a line?  Wouldn't
it make more sense to initialize counter[] to random values?  That makes
things even less guessable.

> i.e. a line with a random offeset.

I think there is a lot of missing explanatory text.  The above argues
that secret2 is also constant given your above statement.  And your
statement about counter[] being a "line" is no where in the draft.  When
I look at this:

ID = F(Src IP, Dst IP, secret1) + counter[G(src IP, Dst Pref, secret2)]

I can see a number of ways that an implementation could completely
randomize the ID selected so that no one could guess it.  For example,
secret1 or secret2 (or both) could be randomized (e.g., TOD).

> same as that of a global counter).

Various research papers have talked about the number of packets
typically involved in a "flow" between a single pair of devices.  The
math would indicate that randomizing the Fragment ID selection across a
32-bit space given the number of packets in a flow provides a very low
probability of collision.

The destination clearly does not need to be able to guess what the next
Fragment ID would be, so there is no functional reason for the IDs to be
sequential.

My suggestion would be to state the assumptions you are making (e.g.,
secretX is constant, counter[] is a line), why you are making those
assumptions (e.g., ease of implementation), and the performance
tradeoffs you are making.

Regards,
Brian

---

From: Fernando Gont <[email-masked]>
Date: Tue, 25 Aug 2015 11:33:08 -0300

Hi, Brian,

On 08/24/2015 10:55 AM, Brian Haberman wrote:
> As with secret1, where does it say that counter[] is a line?

I will clarify this in the next rev.

> Wouldn't

mmm..not really, since the randomness really comes from F(). But it
wouldn't hurt, either.

> secret1 or secret2 (or both) could be randomized (e.g., TOD).

I will clarify this. And also note that this algorithm is designed after
RFC1948.

> probability of collision.

Given the considerations regarding translators, such math should be done
for 16-bit long Frag IDs, rather than 32-bit long Frag IDs (otherwise
you could get a much worse IPv4 frag id when you're dealing with
translators). Besides, while talking with Linux developers at the time,
a completely random() Frag ID wasn't sensible for them. And IIRC, the
same applies to OpenBSD.

> Fragment ID would be, so there is no functional reason for the IDs to be

The only reason for the Frag IDs being sequential is that such approach
minimizes the frag id reuse frequency.

> tradeoffs you are making.

Will do.

Thanks so much!

Best regards,