Subject: [dtn-security] Including fragment offset in the correlator doesn't prevent all fragment collisions.

From: Amy Alford <[email-masked]>
Date: Tue, 19 Mar 2013 19:24:24 -0400

A bundle can be fragmented multiple times independently, so a node may
receive multiple fragments with the same offset and length that have
traveled different paths (and accumulated different BSP blocks along the
way).  Collisions in the correlator values once the bundle is reassembled
are inevitable.
- Amy

---

From: Peter Lovell <[email-masked]>
Date: Tue, 19 Mar 2013 21:11:14 -0400

>way).  Collisions in the correlator values once the bundle is reassembled

Hi Amy,

my thought is that we have covered the problem of multiple-fragmentation and multi-path, but perhaps not.

Can you describe a bundle scenario that exemplifies the issue you see, so we can think about it.

Thanks.....Peter

---

From: "Ivancic, William D. (GRC-RHN0)" <[email-masked]>
Date: Tue, 19 Mar 2013 20:35:50 -0500

Amy,

I do not believe RFC5050 was designed with secure reactive fragmentation in
mind.  RFC5050 is fine for research.  Hopefully we are learning a lot and
will fix what doesn't work very well on a second or third iteration.

-- Will 

> From: Peter Lovell <[email-masked]>
> Date: Tue, 19 Mar 2013 20:11:14 -0500
> To: Amy Alford <[email-masked]>, dtn-security <[email-masked]>
> Subject: Re: [dtn-security] Including fragment offset in the correlator
> doesn't prevent all fragment collisions.
> 
> _______________________________________________
> dtn-security mailing list
> [email-masked]
> https://www.irtf.org/mailman/listinfo/dtn-security

---

From: Stephen Farrell <[email-masked]>
Date: Wed, 20 Mar 2013 08:59:41 +0000

On 03/20/2013 01:35 AM, Ivancic, William D. (GRC-RHN0) wrote:
> mind.  

I don't believe anything has ever been designed with secure reactive
fragmentation in mind;-) But I may be forgetting - if there has been
something like that done then it'd be good to look at.

> RFC5050 is fine for research.  Hopefully we are learning a lot and

Tend to agree, at least in this respect but I'd put it differently.
I think 5050 is mostly fine, but not wrt security which was added
after the fact in what was required to be a pretty ugly manner.

I do recall the fragmentation issue being discussed when DTNRG met
in Dublin some years ago, if someone found the notes from that those
might be useful. (I've not following the details of this conversation
sorry.)

S.

---

From: Amy Alford <[email-masked]>
Date: Wed, 20 Mar 2013 19:36:32 -0400

A 100 byte bundle is created.  Different nodes independently fragment it
into 50 byte fragments.  A subsequent node adds PIB and PCB (so we have
correlated PCB blocks) to each fragment with a security destination of the
bundle destination.   The correlators can collide. (In DTN2, they will
collide.)

If the fragments are reassembled before the destination, the destination
has no way to distinguish the PCB blocks that should correlate with each
other.

Alternatively, if we assume reassembly only happens at the destination
(which 5050 doesn't guarantee), we still have a problem if we use a two
block PIB ciphersuite where one block comes before the payload and one
comes after.

A node creates a 100 byte bundle.  It's independently fragmented into 50
byte bundles.  A subsequent node adds a PIB ciphersuite with a correlated
block trailing the payload.  Again, the correlators collide.  Now, each 50
byte fragment is fragmented again.  So, we have fragments:

(I'm numbering the PIB instances so that we can distinguish them in the
discussion.  The numbers don't correspond to anything identifiable in the
blocks themselves.)

PIB 1 with correlator x -> 0-25
25-50 -> PIB 1 with correlator x
PIB 2 with correlator y -> 50-75
75-100 -> PIB 2 with correlator y

PIB 3 with correlator x -> 0-25
25-50 -> PIB 3 with correlator x
PIB 4 with correlator y -> 50-75
75-100 -> PIB 4 with correlator y

The receiving node has no way to realize that that pre-payload PIB 1 with
correlator x doesn't match up to the post-payload PIB 3 with correlator x.

- Amy

---

From: Elwyn Davies <[email-masked]>
Date: Thu, 21 Mar 2013 00:56:59 +0000

Hi, Amy.

I grok the problem properly now (I hope).

Does pushing a metadata block into the bundle with the EID (or if too
long) a short nonce or abbreviated digest of some part of the bundle
(e.g. some part of the PIB) into all the fragments at the node where it
is fragmented help?

Not a very satisfactory solution but it would help tie the two parts of
the PIB together.

/Elwyn

On Wed, 2013-03-20 at 19:36 -0400, Amy Alford wrote:
> A 100 byte bundle is created.  Different nodes independently fragment
> it into 50 byte fragments.  A subsequent node adds PIB and PCB (so we
> have correlated PCB blocks) to each fragment with a security
> destination of the bundle destination.   The correlators can collide.
> (In DTN2, they will collide.)     
> 
> 
> If the fragments are reassembled before the destination, the
> destination has no way to distinguish the PCB blocks that should
> correlate with each other.
> 
> 
> (which 5050 doesn't guarantee), we still have a problem if we use a
> two block PIB ciphersuite where one block comes before the payload and
> one comes after.  
> 
> 
> A node creates a 100 byte bundle.  It's independently fragmented into
> 50 byte bundles.  A subsequent node adds a PIB ciphersuite with a
> correlated block trailing the payload.  Again, the correlators
> collide.  Now, each 50 byte fragment is fragmented again.  So, we have
> fragments:
> 
> 
> (I'm numbering the PIB instances so that we can distinguish them in
> the discussion.  The numbers don't correspond to anything identifiable
> in the blocks themselves.)
> 
> 
> The receiving node has no way to realize that that pre-payload PIB 1
> with correlator x doesn't match up to the post-payload PIB 3 with
> correlator x.
> 
> 
> - Amy
> 
>         my thought is that we have covered the problem of
>         multiple-fragmentation and multi-path, but perhaps not.
>

---

From: Amy Alford <[email-masked]>
Date: Wed, 20 Mar 2013 21:11:51 -0400

A metadata block that tied the fragments together (and was unique to that
fragmentation event: perhaps EID and time) would help, as long as
reassembly is handled by the destination (so that it can take advantage of
this info).

- Amy

---

From: "Ivancic, William D. (GRC-RHN0)" <[email-masked]>
Date: Wed, 20 Mar 2013 23:19:58 -0500

A 5 GB bundle come forms Mr. Bad.  You don’t want to store anything from Mr. Bad, but you cannot confirm the source  using PIB until you receive the entire bundle thus eating up 5 GB of resources.

It is broken.

-- Will

________________________________
From: Amy Alford <[email-masked]>
Date: Wed, 20 Mar 2013 18:36:32 -0500
To: Peter Lovell <[email-masked]>
Cc: dtn-security <[email-masked]>
Subject: Re: [dtn-security] Including fragment offset in the correlator doesn't prevent all fragment collisions.

A 100 byte bundle is created.  Different nodes independently fragment it into 50 byte fragments.  A subsequent node adds PIB and PCB (so we have correlated PCB blocks) to each fragment with a security destination of the bundle destination.   The correlators can collide. (In DTN2, they will collide.)

If the fragments are reassembled before the destination, the destination has no way to distinguish the PCB blocks that should correlate with each other.

Alternatively, if we assume reassembly only happens at the destination (which 5050 doesn't guarantee), we still have a problem if we use a two block PIB ciphersuite where one block comes before the payload and one comes after.

A node creates a 100 byte bundle.  It's independently fragmented into 50 byte bundles.  A subsequent node adds a PIB ciphersuite with a correlated block trailing the payload.  Again, the correlators collide.  Now, each 50 byte fragment is fragmented again.  So, we have fragments:

(I'm numbering the PIB instances so that we can distinguish them in the discussion.  The numbers don't correspond to anything identifiable in the blocks themselves.)

The receiving node has no way to realize that that pre-payload PIB 1 with correlator x doesn't match up to the post-payload PIB 3 with correlator x.

- Amy

Hi Amy,

Thanks.....Peter

---

From: Amy Alford <[email-masked]>
Date: Thu, 21 Mar 2013 10:43:30 -0400

Isn't this fixable by defining a PIB ciphersuite that only protects the
primary block?
- Amy

On Thu, Mar 21, 2013 at 12:19 AM, Ivancic, William D. (GRC-RHN0) <
[email-masked]> wrote:

>  A 5 GB bundle come forms Mr. Bad.  You don’t want to store anything from
> Mr. Bad, but you cannot confirm the source  using PIB until you receive the
> entire bundle thus eating up 5 GB of resources.
>
> It is broken.
>
> -- Will
>
>
> ------------------------------
> *From: *Amy Alford <[email-masked]>
> *Date: *Wed, 20 Mar 2013 18:36:32 -0500
> *To: *Peter Lovell <[email-masked]>
> *Cc: *dtn-security <[email-masked]>
>
> *Subject: *Re: [dtn-security] Including fragment offset in the correlator

---

From: Amy Alford <[email-masked]>
Date: Thu, 21 Mar 2013 10:49:01 -0400

To make reassembly somewhere other than the destination succeed, either
reassembling nodes need to be required to understand all the extension
blocks (so they can recombine them sensibly), or the reassembly process
needs to somehow preserve information about the fragment structure.  In the
latter case, reassembly seems useless anyway.  You're unlikely to save any
space over just forwarding the fragments.

---

From: Peter Lovell <[email-masked]>
Date: Fri, 22 Mar 2013 20:58:38 -0400

Hi Amy,

thanks for your example. 

One thing I discovered in looking at the 2.9 code is that there's a bug, and fixing that would help things.

In Ciphersuite::create_correlator( ) [file ~/dtn-2.9.0/servlib/security/Ciphersuite.cc] we intend to make the new correlator bigger than any existing one. But we don't quite do that. Line 480 reads
    result |= high_val;     // put high_val into low-order two bytes
and that should be 
    result |= high_val + 1;     // put high_val into low-order two bytes
For the following discussion, let's assume that change.

The correlator is a triple, comprising the fragment-offset, ciphersuite number, and sequence number. The sequence number allows us to differentiate between separate applications of the same ciphersuite, such as signing with both an old and a new key (one may debate the wisdom of such cryptographic usage, but that's a different discussion). One important item to remember is that a correlator is only present if there are two or more related blocks in a bundle. If there are multiple security blocks but they're unrelated then they don't have correlators.

Looking at your second example, four bundles eventually arrive at the destination (assuming destination-reassembly, for the moment). For the sake of discussion, let's hypothetically have the PI ciphersuite number be 7 using trailing block.

Bundle A 
data 0 - 24

Bundle B
data 50 - 74

Bundle C
data 25 - 49
PIB with range 0-49

Bundle D
data 75 - 99
PIB with range 50 - 99

When the two 50-blocks are split into four 25-blocks, the PIBs are replicated into the second block in each case because the PIBs trailed the payload (see 5050 sec. 5.8). Each of the PI operations resulted in a single PI block so there is no correlator needed (in fact, it's prohibited). 

So let's create a more problematic scenario with the hundred-byte message. The first node it encounters has known 60-byte limits for onforwarding so we get one 60- and one 40-byte bundle. The outbound policy requires PI so both fragments will have a trailing PIB without a correlator. The two bundles are sent on their way, but the node is unsure whether the first was properly received (let's say that the CL ACK was lost) so it sends the first one again on a different link. Whatever the mechanism, we now have two copies of this bundle A (bytes 0 - 59) in flight via two separate nodes. 

At this second stage, one node has a 40-byte outgoing limit so fragments bundle A into 40- and 20-byte fragments, with the PIB in the second fragment. Per this node's policy, it applies PC3 to both outgoing bundles Aa and Ab and sends them on. These contents are ...

Bundle Aa
PCBa with range 0 - 39
encrypted data 0 - 39

Bundle Ab
PCBb with range 40 - 59, correlator 40 - 3 - 1
encrypted data 40 - 59
encrypted PIB, with correlator 40 - 3 - 1

The other node, quite unaware that the bundle exists elsewhere, processes it too. By perverse chance, its outgoing links also have 40-byte limits, so the outgoing stream is ...

Bundle Ac
PCBc with range 0 - 39
encrypted data 0 - 39

Bundle Ad
PCBd with range 40 - 59, correlator 40 - 3 - 1
encrypted data 40 - 59
encrypted PIB, with correlator 40 - 3 - 1

I wonder if any DTN code today will nicely handle this case but it's quite possible. The decryption is contained within each bundle and is not complex.

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

A more difficult setup is to change the PI above to PC3. We have two copies of bundle A at separate nodes, unaware of one another. Each has the PC3 block containing the parameters etc for the encryption of bytes 0-59 of the original bundle, i.e. bundle A. Bundle A contains ...

PCB-k with range 0 - 59 (w/o correlator)
encrypted data 0 - 59

The "PCB-k" indicates a "first-block" PCB, containing key-info. Such a block MUST be replicated in every fragment. The 40-byte limit applies so this bundle, at each node, is now fragmented 40 + 20. We assume that the security-dest is the bundle-dest, for simplicity (yeah, right :)  So these two independent copies of bundle A become new bundles Aa/Ab and Ac/Ad

The contents will be ...

Bundle Aa
PCBa-k with range 0 - 39, correlator 0 - 3 - 1
encrypted (PCB-k with range 0 - 59 w/o corr), correlator 0 - 3 - 1
doubly-encrypted data 0 - 39

Bundle Ab 
PCBb-k with range 40 - 59, correlator 0 - 3 - 1
encrypted (PCB-k with range 0 - 59 w/o corr), correlator 0 - 3 - 1
doubly-encrypted data 40-59

The other copy of bundle A will look very much the same ...

PCBc-k with range 0 - 39, correlator 0 - 3 - 1
encrypted (PCB-k with range 0 - 59 w/o corr), correlator 0 - 3 - 1
doubly-encrypted data 0 - 39

Bundle Ab 
PCBd-k with range 40 - 59, correlator 0 - 3 - 1
encrypted (PCB-k with range 0 - 59 w/o corr), correlator 0 - 3 - 1
doubly-encrypted data 40-59

It's fairly clear that there's no possibility that merge-and-reassemble will work. The sequence that must happen is to first unwrap PC from each bundle. The attempt to do the second PC unwrap will fail since no bundle has the data range to match the range of the PCBs (0 - 59). So reassembly looks for suitable data and finds two copies of both 0 - 39 and 40 - 59. Fortunately, these respective copies are identical, so reassembly happens and the duplicates are discarded, along with a duplicate copy of PCB-k. 

Decryption of bytes 0 - 59 now proceeds and hopefully the bundle containing 60 - 99 has also arrived. These two are reassembled and we have our original message.

As you can see, this is a quite involved process. A couple of things are worthy of note:
1. correlators are local to their bundle
2. a block with a correlator may be encapsulated, with PCB for example. The original correlator is hidden until decapsulation occurs (not shown above for sake of brevity :)
3. reassembly is a very, very complex process. 

Regards.....Peter

p.s. the descriptions above are believed to be correct but it has been a while since I did this for real and I may be rusty. Please let me know if there are errors

---

From: Peter Lovell <[email-masked]>
Date: Sat, 23 Mar 2013 17:32:52 -0400

Hi Amy,

Amy Alford <[email-masked]> wrote:

>Yes, my example was assuming a PIB ciphersuite that used two blocks
>(similar to BAB).  That case is the most problematic, because when the
>bundle is fragmented, the two blocks will end up in separate fragments.
> Otherwise, the correlator collision isn't a problem as long as reassembly
>happens at the destination.

PIB is, in some ways, a more difficult scenario than PCB. When a bundle with PCB arrives at the security-dest, the payload is decrypted (and other blocks as appropriate) and the PCB itself is deleted. But some folks want to have PIBs remain even after verification, as evidence I guess. That is messy.

Is there a specific reason for a two-block PIB?

>> 2. a block with a correlator may be encapsulated, with PCB for example.
>> The original correlator is hidden until decapsulation occurs (not shown
>> above for sake of brevity :)
>I was pondering how to support these sorts of cases (which end up needing
>validation and reassembly interleaved somehow).  In thinking about it, I
>started running into scenarios that aren't supportable.  The example I gave
>is one (which I think shows that bundles with two block PIBs need to have
>the do not fragment flag set).

It may be sufficient to apply the replicate-key-info-in-every-block rule. I don't know without thinking about it some more.

>Additionally, in general, if an intermediate node reassembles fragments
>that have had BSP blocks added after fragmentation, we can't validate.  Too
>much information is lost on reassembly (even if it's done sensibly).  5050
>allows intermediate nodes to reassemble, but doesn't mandate a procedure
>for reassembling the extension blocks (so it may not be done sensibly).

It's not just an issue of reassembling/reordering extension blocks. As the final example shows, any attempt to reassemble-first is doomed to failure because the two parts were encrypted under different second-stage keys. 

It's clear to me that reassembly of bundles containing security blocks must be done in concert with security processing. This needs to be incorporated into any update to 5050. And, as you say, there are cases that aren't supportable with the capabilities we now have.

Regards.....Peter

---

From: Amy Alford <[email-masked]>
Date: Mon, 25 Mar 2013 15:58:33 -0400

On Sat, Mar 23, 2013 at 5:32 PM, Peter Lovell <[email-masked]> wrote:

> PIB is, in some ways, a more difficult scenario than PCB. When a bundle
> with PCB arrives at the security-dest, the payload is decrypted (and other
> blocks as appropriate) and the PCB itself is deleted. But some folks want
> to have PIBs remain even after verification, as evidence I guess. That is
> messy.
>
Leaving PIBs on after verification is problematic anyway, if the PIB was
added after a PCB.  Once the PCB reaches it's security destination, the PIB
is invalid anyhow.

> Is there a specific reason for a two-block PIB?

6257 mentions the idea of PIB ciphersuites that use a trailing block
similar to BAB.  I assume you'd still want an up front block to warn nodes
that are doing one pass processing that they need to start hashing.

> It may be sufficient to apply the replicate-key-info-in-every-block rule.
> I don't know without thinking about it some more.
>

I think it would fix the example I gave.  The last fragment would contain
both the leading and trailing PIB blocks.  The leading block could be used
to match this up with the corresponding fragment (which also has a leading
PIB block but is missing the trailing one).  It would be a pain in terms of
processing, since defragmentation would need to match up the corresponding
fragments by comparing their leading PIB blocks.

> It's not just an issue of reassembling/reordering extension blocks. As the
> final example shows, any attempt to reassemble-first is doomed to failure
> because the two parts were encrypted under different second-stage keys.

> It's clear to me that reassembly of bundles containing security blocks
> must be done in concert with security processing. This needs to be
> incorporated into any update to 5050. And, as you say, there are cases that
> aren't supportable with the capabilities we now have.
>

Yes.  In general, nodes shouldn't reassemble a bundle if they don't
understand all the extension blocks.  BSP aware nodes shouldn't reassemble
fragments except in concert with security processing.