Subject: Question on draft-gont-6man-flowlabel-security-00

From: Shane Amante <[email-masked]>
Date: Tue, 7 Sep 2010 13:58:21 -0600

Hi Fernando,

I have a question on:
http://tools.ietf.org/html/draft-gont-6man-flowlabel-security-00

Unless I misunderstand something, you're proposing that a flow-label be constructed using the IPv6 Source & Destination values as input-keys to a hash function as follows:
   Flow Label = counter + F(Source Address, Destination Address, Secret Key)
If you do the above, then intermediate routers that are performing LAG and/or ECMP load-balancing will not be able to use the flow-label as an input-key for calculating a load-balancing hash.  Instead, intermediate routers will have to fetch a 5-tuple of {Source IP, Destination IP, Protocol, Source Port, Destination Port} from the IPv6 header to calculate a load-balancing hash (and, at the same time, completely ignore the flow-label as an input-key for its flow-based load-balancing hash, since it's redundant).

Why couldn't (or, shouldn't) the hash function instead use the following:
   Flow Label = counter + F(Source Port, Destination Port, [Protocol], Secret Key)

If you did this, then intermediate routers & switches that were performing LAG and/or ECMP load-balancing could easily use the following /fixed-offset/ header fields as input-keys to the load-balancing hash:
   Load Balancing Hash = F(Source IPv6 Address, Destination IPv6 Address, "draft-gont" Flow Label)
IMHO, this would allow draft-gont-6man-flowlabel-security to nicely/peacefully co-exist with widely deployed/used flow-based load-balancing schemes for LAG and ECMP.

Thanks,

-shane

---

From: Steven Blake <[email-masked]>
Date: Tue, 07 Sep 2010 16:17:19 -0400

On Tue, 7 Sep 2010 13:58:21 -0600, Shane Amante <[email-masked]>
wrote:

> Unless I misunderstand something, you're proposing that a flow-label be
> constructed using the IPv6 Source & Destination values as input-keys to
a
> hash function as follows:
> If you do the above, then intermediate routers that are performing LAG
> and/or ECMP load-balancing will not be able to use the flow-label as an
> input-key for calculating a load-balancing hash.  Instead, intermediate
> routers will have to fetch a 5-tuple of {Source IP, Destination IP,
> Protocol, Source Port, Destination Port} from the IPv6 header to
calculate
> a load-balancing hash (and, at the same time, completely ignore the
> flow-label as an input-key for its flow-based load-balancing hash, since
> it's redundant).

Shane,

I don't think your conclusion follows.  One thing you want for LAG/ECMP is
for each flow from a given <src_addr, dst_addr> to have a unique FL value. 
Fernando's algorithm achieves this by incrementing counter for each new
flow from that address pair.

With that said, I don't think this algorithm is necessarily ideal.  The FL
value for any two flows from a <src_addr, dst_addr> pair may only vary by a
few bits, so if a switch/router uses a poor hash algorithm for LAG/ECMP,
you may not get a good load spread.

> If you did this, then intermediate routers & switches that were
performing
> LAG and/or ECMP load-balancing could easily use the following
> /fixed-offset/ header fields as input-keys to the load-balancing hash:
>    Load Balancing Hash = F(Source IPv6 Address, Destination IPv6
Address,
>    "draft-gont" Flow Label)
> IMHO, this would allow draft-gont-6man-flowlabel-security to
> nicely/peacefully co-exist with widely deployed/used flow-based
> load-balancing schemes for LAG and ECMP.

If you include protocol/src_port/dst_port in the hash, there is nothing
preventing two flows from the same <src_add, dst_addr> from sharing the
same FL value, due to a hash collision.

Regards,

// Steve

---

From: Fernando Gont <[email-masked]>
Date: Wed, 08 Sep 2010 01:06:03 -0300

Hi, Shane,

Please find my comments inline....

> Unless I misunderstand something, you're proposing that a flow-label
> be constructed using the IPv6 Source & Destination values as
> input-keys to a hash function as follows: Flow Label = counter +
> F(Source Address, Destination Address, Secret Key) If you do the
> above, then intermediate routers that are performing LAG and/or ECMP
> load-balancing will not be able to use the flow-label as an input-key
> for calculating a load-balancing hash. 

Why?

> Why couldn't (or, shouldn't) the hash function instead use the
> following: Flow Label = counter + F(Source Port, Destination Port,
> [Protocol], Secret Key)

Because the specs require the Flow Label to be unique on a per (src
addr, dst addr) basis. -- hence the flow-selection function needs to
take into account the v6 addresses rather than the src/dst ports.

> performing LAG and/or ECMP load-balancing could easily use the
> following /fixed-offset/ header fields as input-keys to the
> load-balancing hash: Load Balancing Hash = F(Source IPv6 Address,
> Destination IPv6 Address, "draft-gont" Flow Label) IMHO, this would
> allow draft-gont-6man-flowlabel-security to nicely/peacefully
> co-exist with widely deployed/used flow-based load-balancing schemes
> for LAG and ECMP.

This is actually the intent of the proposed flow-label selection
algorithm in draft-gont-6man-flowlabel-security-00

Please let me know if the above has clarified your concern...

Thanks!

Kind regards,
-- 
Fernando Gont
e-mail: [email-masked] || [email-masked]
PGP Fingerprint: 7809 84F5 322E 45C7 F1C9 3945 96EE A9EF D076 FFF1

---

From: Fernando Gont <[email-masked]>
Date: Wed, 08 Sep 2010 01:20:27 -0300

Hi, Steven,

> you may not get a good load spread.

I think that in this case both the hash algorithm used for generating
the Flow Label and the hash algorithm used at the router would need to
be be "poor".

Nevertheless, if the hash algorithm at the router is poor, you're dead
anyway. Because different hosts could use different algorithms for
generating the Flow Label which on the aggregate could result in Flow
Label values that differ in only a few bits.

Unless I'm missing something....

Thanks!

Kind regards,

---

From: Shane Amante <[email-masked]>
Date: Wed, 8 Sep 2010 11:22:48 -0600

Steve,

> flow from that address pair.

OK, thanks for the clarification.  IMHO, that (last part) wasn't clear in my reading of the draft.

> you may not get a good load spread.

Agreed, I share your concern that the "counter" is a linear sequence.

> following:

I'm not sure I understand.

>>   Flow Label = counter + F(Source Port, Destination Port, [Protocol], Secret Key)

If anything, I would think with new transport connections, using ephemeral ports, being opened all the time, a combination of F(src_port, dst_port, [protocol], secret key) _and_ the counter would provide more entropy to the FL values vs. just using the IPv6 addresses in F().

-shane

---

From: Fernando Gont <[email-masked]>
Date: Wed, 08 Sep 2010 15:18:47 -0300

Hi, Shane,

>> With that said, I don't think this algorithm is necessarily ideal.
>> The FL value for any two flows from a <src_addr, dst_addr> pair may
>> only vary by a few bits, so if a switch/router uses a poor hash
>> algorithm for LAG/ECMP, you may not get a good load spread.
> 

Well, this is actually a feature ;-). i.e., the hash provides the
randomness. the counter provides for the linear increase, such that the
chances of collisions are reused (you only reuse a given flowlabel once
you have already use all the other flowlablel values).

>> If you include protocol/src_port/dst_port in the hash, there is
>> nothing preventing two flows from the same <src_add, dst_addr> from
>> sharing the same FL value, due to a hash collision.
> 
> I thought that, as you pointed out above, the "counter" was the
> method to prevent/reduce collisions of FL values?  

The counter prevents a flow-label to be reused too quickly for a given
(src addr, dst addr).

The hash provides for a random "offset" value such that, while an
attacker knows that flowlabels are generated linearly, he doesn't know
where that line starts.

Think of the function as:

y = a * x + b

Where
y: Flow Label
a: is "1" in this case
x: the counter
b: the result of the hash function

The expression above is that of a line. However, since it's impossible
(*) for an off-path attacker to know "b", it's impossible to predict the
value of "y".

(*) Clearly this depends on the secret, and the hash algorithm, etc.

> From my original
> e-mail:
> If anything, I would think with new transport connections, using
> ephemeral ports, being opened all the time, a combination of
> F(src_port, dst_port, [protocol], secret key) _and_ the counter would
> provide more entropy to the FL values vs. just using the IPv6
> addresses in F().

How do you prevent this function from throwing the same value for the
same pair (src addr, dst addr) in a short period of time?

You want uniqueness on a per (srd addr, dst addr) basis. -- hence the
"offset" (resulting from the hash function) has to be based on the
addresses....

Thanks!

Kind regards,

---

From: Shane Amante <[email-masked]>
Date: Wed, 8 Sep 2010 15:55:31 -0600

Hi Fernando,

> you have already use all the other flowlablel values).

I respectfully disagree that "the hash provides the randomness" suitable for a flow-label to be used as an input-key for flow-based load-balancing.  In your draft, you've defined the calculation of a Flow Label value as follows:
   Flow Label = counter + F(Source Address, Destination Address, Secret Key)

Thus, for a given {src_ip, dst_ip} pair, the only thing providing uniqueness to the output of that hash is the secret key.  Assuming the secret key doesn't roll-over [very frequently], won't the output of the hash function be constant?  Only the linearly increasing "counter" is providing **entropy** to a "flow" in the flow-label value.  (Note, I'm looking at this from the perspective of using the above flow label value as an input-key for flow-based load-balancing over LAG/ECMP paths).

Although Section 4 of your draft provides some very high level guidance on when a secret key roll-over /may/ occur, it's unclear what this frequency would (or, should?) boil down to in practice, IMHO.

From what I can tell, your algorithm appears to be OK for providing a unique, "unguessable" flow-label value (given the combination of the "secret-key" and "counter" in your algorithm) that could prevent off-path attacks.  However, (unless I'm misunderstanding something), it would likely provide very poor entropy to the flow-label value for it to be used as an input-key, i.e.: {src_ip, dst_ip, flow-label}, for flow-based load-balancing on LAG and ECMP paths, instead of the usual 5-tuple of: {src_ip, dst_ip, protocol, src_port, dst_port}.

[--snip--]

> same pair (src addr, dst addr) in a short period of time?

Wouldn't that be a function of: a) how often the "secret key" is rolled over; and, b) the counter?  To reduce the risk of collision I would assume you'd decrease the the interval at which the secret key is rolled over and/or increase the size of the counter.

> "offset" (resulting from the hash function) has to be based on the

Why?  Or, said differently, shouldn't the requirement be that there is a very low probability that a given receiver will experience a collision of identical flow-labels?

Thanks,

-shane

---

From: Fernando Gont <[email-masked]>
Date: Wed, 08 Sep 2010 19:29:00 -0300

Hi, Shane,

> I respectfully disagree that "the hash provides the randomness"
> suitable for a flow-label to be used as an input-key for flow-based
> load-balancing.  In your draft, you've defined the calculation of a
> Flow Label value as follows: Flow Label = counter + F(Source Address,
> Destination Address, Secret Key)
> 
> Thus, for a given {src_ip, dst_ip} pair, the only thing providing
> uniqueness to the output of that hash is the secret key.  

I don't know what you mean by "uniqueness" here. If you mean "the
secretkey is what makes it hard for an off-path attacker to predict the
result of the hash function", then I fully agree.

> Assuming
> the secret key doesn't roll-over [very frequently], won't the output
> of the hash function be constant?  

Exactly. That's the intention!  See the tables in draft-gont for
possible sample outputs.

> Only the linearly increasing
> "counter" is providing **entropy** to a "flow" in the flow-label
> value.  (Note, I'm looking at this from the perspective of using the
> above flow label value as an input-key for flow-based load-balancing
> over LAG/ECMP paths).

Agreed.

> Although Section 4 of your draft provides some very high level
> guidance on when a secret key roll-over /may/ occur, it's unclear
> what this frequency would (or, should?) boil down to in practice,
> IMHO.

IMO, it's shouldn't be necessary to roll-over the key frequently. After
all, what's gained by guessing the key or the like is not worth the
effort that would be required.

If anything, change the key when the system has been idle for quite a
while, and that's it.

> From what I can tell, your algorithm appears to be OK for providing a
> unique, "unguessable" flow-label value (given the combination of the
> "secret-key" and "counter" in your algorithm) that could prevent
> off-path attacks.  However, (unless I'm misunderstanding something),
> it would likely provide very poor entropy to the flow-label value for
> it to be used as an input-key, i.e.: {src_ip, dst_ip, flow-label},
> for flow-based load-balancing on LAG and ECMP paths, instead of the
> usual 5-tuple of: {src_ip, dst_ip, protocol, src_port, dst_port}.

There's a refined algorithm that uses multiple counters rather than a
single counter. That algorithm should address your concerns.

ANyway, I cant see how the usual 5-tuple would have more entropy: src
and dst ip are the same as for my algorithm. protocol is most likely tcp
or udp. dst port probably has only a few values (80, 110, etc.), and src
port is generated in some stacks with the same algorithm I'm proposing
for the flow label (see draft-ietf-tsvwg-port-randomization)

>>> From my original e-mail:
>>> F(src_port, dst_port, [protocol], secret key) _and_ the counter
>>> would provide more entropy to the FL values vs. just using the
>>> IPv6 addresses in F().
>> How do you prevent this function from throwing the same value for
>> the same pair (src addr, dst addr) in a short period of time?
> 
> Wouldn't that be a function of: a) how often the "secret key" is
> rolled over; 

The secret key is asumed to not roll-over frequently.

> and, b) the counter?  To reduce the risk of collision I
> would assume you'd decrease the the interval at which the secret key
> is rolled over and/or increase the size of the counter.

I don't follow.

Decreasing the key rollover frequency actually *increases* the
probability of collisions -- hence the advice in my I-D as to when (if
ever) that should be done.

>> You want uniqueness on a per (srd addr, dst addr) basis. -- hence
>> the "offset" (resulting from the hash function) has to be based on
>> the addresses....
> 
> Why?  Or, said differently, shouldn't the requirement be that there
> is a very low probability that a given receiver will experience a
> collision of identical flow-labels?

The flow label spec requires the tuple (src addr, dst addr, flow label)
to be unique at least for 120 seconds since the last packet of the flow
was seen.

Identical flow labels are okay as long as the tuple (src addr, dst addr,
flow label) changes. i.e., you can reuse the same flow label value *if*
the src addr and/or the dst addr change.

Thanks!

Kind regards,

---

From: Steven Blake <[email-masked]>
Date: Wed, 08 Sep 2010 23:44:38 -0400

> > On Tue, 7 Sep 2010 13:58:21 -0600, Shane Amante <[email-masked]>

[snip]

> Agreed, I share your concern that the "counter" is a linear sequence.

That is easily fixed.  Replace counter with a 20-bit, maximum-length
sequence linear feedback shift register (e.g., x^20 + x^17 + 1 or x^20 +
x^19 + x^16 + x^14 + 1).  Initialize it with the 20-bit output of
F(src_addr, dst_addr, Secret_Key).  The LFSR will only repeat after
2^20 - 1 iterations. 

> If anything, I would think with new transport connections, using ephemeral ports, being opened all the time, a combination of F(src_port, dst_port, [protocol], secret key) _and_ the counter would p…

It would provide more entropy (depending on how you define "entropy"),
but it introduces the possibility that two flows from the same
<src_addr, dst_addr> pair could share the same FL value, due to a hash
collision.  That can't happen if you hash on only src_addr/dst_addr as
long as counter doesn't wrap.

draft-gont-6man-flowlabel-security assumes that you keep track of every
allocated <src_addr, dst_addr, FL> tuple (the "if(three-tuple is unique)
return flowlabel;" pseudo-code).  If you are going to the trouble of
doing this, there is really no reason not to just use a good PRNG to
generate the FL value, and retry upon a 3-tuple collision.

Regards,

// Steve

---

From: Fernando Gont <[email-masked]>
Date: Thu, 09 Sep 2010 13:52:50 -0300

> generate the FL value, and retry upon a 3-tuple collision.

Sorry, that part shouldn't be there (will fix this). It's the result of
porting the algorithm from "port randomization" to "flow label
randomization".

The only state that this algorithm should have is the "counter".

Thanks,

---

From: Fernando Gont <[email-masked]>
Date: Thu, 09 Sep 2010 14:24:52 -0300

> generate the FL value, and retry upon a 3-tuple collision.

I checked the algorithm. The "if(three-tuple is unique)
 return flowlabel" thing is there to check that the corresponding
three-tuple is not *currently* in use. -- this is to avoid the case in
which a particular flow lives for such a long period of time that the
flow-lavel sequence for that pair (src addr, dst addr) wraps while that
flow is still alive (and hence there are chances of collisions).

Two comments:
* Consider this a refinement
* The difference between this algorithm (even if it includes the
aforementioned "if()") and the simple PRNG approach is that with the
simple PRNG you could end up selecting a flow label that is not
*curretly* in use, but thatwas in use less than 120 seconds ago -- thus
violating the spec.

Thanks!

Kind regards,

---

From: Shane Amante <[email-masked]>
Date: Thu, 9 Sep 2010 13:51:49 -0600

Hi Fernando,

Apologies for the delay.

> result of the hash function", then I fully agree.

By "uniqueness", I meant that the flow-label contained enough entropy (i.e.: was a substantially unique value, not just a linearly increasing value) that it would result in very good load-spreading if it were used as an input-key for flow-based load-balancing over LAG & ECMP paths.

[--snipping parts we agree on--]

> If anything, change the key when the system has been idle for quite a

While that may be OK from a security POV, that likely means the flow-label value won't contain enough entropy for it to be useful as an input-key for load-spreading on LAG & ECMP paths at intermediate routers along the path.

> single counter. That algorithm should address your concerns.

I'm not sure it does.  At the moment, I like Steve's suggestion (in a subsequent e-mail) of either a Linear Feedback Shift Register or, better yet, using a PRNG.  In theory, with a 20-bit space and a "good" PRNG the risk of choosing the same flow-label value is likely infinitesimally small, which is good enough (for me).

> for the flow label (see draft-ietf-tsvwg-port-randomization)

I haven't looked at that draft you mention before; however, from a cursory glance, there are a variety of algorithms in there at least two of which appear to use a PRNG.  So, if PRNG is good enough for port-randomization, why isn't a PRNG good enough for the flow-label?  (If anything, there's a substantially larger output space in a flow-label, compared to the ephemeral port range).

> ever) that should be done.

Err, sorry.  I meant the shorter/smaller the time interval at which you're rolling over keys, the less risk of collision you have.  So, we agree.  :)

> the src addr and/or the dst addr change.

Thank you!

-shane

---

From: Fernando Gont <[email-masked]>
Date: Thu, 09 Sep 2010 18:48:38 -0300

Hi, Shane,

>> secretkey is what makes it hard for an off-path attacker to predict
>> the result of the hash function", then I fully agree.
> 
> By "uniqueness", I meant that the flow-label contained enough entropy
> (i.e.: was a substantially unique value, not just a linearly
> increasing value) that it would result in very good load-spreading if
> it were used as an input-key for flow-based load-balancing over LAG &
> ECMP paths.

As noted by Steven, this can be easily fixed. Even then, I don't think a
router can rely on the entropy of the flow-label (besides that of a
linear change) for achieving good load-sharing. The hash algorithm at
the router has to be good enough. That's it.

>> If anything, change the key when the system has been idle for quite
>> a while, and that's it.
> 
> While that may be OK from a security POV, that likely means the
> flow-label value won't contain enough entropy for it to be useful as
> an input-key for load-spreading on LAG & ECMP paths at intermediate
> routers along the path.

Can a router actually rely on this?

Anyway, Steven suggested how to fix this, if this is deemed as an
important issue.

>> There's a refined algorithm that uses multiple counters rather than
>> a single counter. That algorithm should address your concerns.
> 
> I'm not sure it does.  At the moment, I like Steve's suggestion (in a
> subsequent e-mail) of either a Linear Feedback Shift Register or,
> better yet, using a PRNG.  In theory, with a 20-bit space and a
> "good" PRNG the risk of choosing the same flow-label value is likely
> infinitesimally small, which is good enough (for me).

The requirement in RFC 3697 is for "MUST" be unique not "SHOULD". So a
simple PRNG does not seem to be enough.

>> ANyway, I cant see how the usual 5-tuple would have more entropy:
>> src and dst ip are the same as for my algorithm. protocol is most
>> likely tcp or udp. dst port probably has only a few values (80,
>> 110, etc.), and src port is generated in some stacks with the same
>> algorithm I'm proposing for the flow label (see
>> draft-ietf-tsvwg-port-randomization)
> 
> I haven't looked at that draft you mention before; however, from a
> cursory glance, there are a variety of algorithms in there at least
> two of which appear to use a PRNG.  So, if PRNG is good enough for
> port-randomization, 

They are not ;-), but the port-randomization was produced by a standards
body, and hence everybody had to be pleased :-(

FWIW, FreeBSD had implemented the trivial PRNG approaches, and had to
implement a hack later due to problems arising from collisions of the
port numbers....

> why isn't a PRNG good enough for the flow-label?
> (If anything, there's a substantially larger output space in a
> flow-label, compared to the ephemeral port range).

Agreeed. But RFC3697 has a "MUST" requirement for avoiding collisions.
(not a "SHOULD")

>>> and, b) the counter?  To reduce the risk of collision I would
>>> assume you'd decrease the the interval at which the secret key is
>>> rolled over and/or increase the size of the counter.
>> I don't follow.
>> 
>> probability of collisions -- hence the advice in my I-D as to when
>> (if ever) that should be done.
> 
> Err, sorry.  I meant the shorter/smaller the time interval at which
> you're rolling over keys, the less risk of collision you have.  So,
> we agree.  :)

Sorry. The shorter/smaller the interval, the higher the chances of
collisions. -- Ideally, you would never roll-over the keys (for lowest
chances of collisions)

Thanks!

Kind regards,