[dtn-security] Re(2): Including fragment offset in the correlator doesn't prevent all fragment collisions.

Peter Lovell <plovell@mac.com> Sat, 23 March 2013 00:58 UTC

Return-Path: <plovell@mac.com>
X-Original-To: dtn-security@ietfa.amsl.com
Delivered-To: dtn-security@ietfa.amsl.com
Received: from localhost (localhost []) by ietfa.amsl.com (Postfix) with ESMTP id EF48721F8FE8 for <dtn-security@ietfa.amsl.com>; Fri, 22 Mar 2013 17:58:41 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2.901
X-Spam-Status: No, score=-2.901 tagged_above=-999 required=5 tests=[AWL=-0.698, BAYES_00=-2.599, MIME_QP_LONG_LINE=1.396, RCVD_IN_DNSWL_LOW=-1]
Received: from mail.ietf.org ([]) by localhost (ietfa.amsl.com []) (amavisd-new, port 10024) with ESMTP id 8ZwGEs7Chgod for <dtn-security@ietfa.amsl.com>; Fri, 22 Mar 2013 17:58:40 -0700 (PDT)
Received: from st11p00mm-asmtp003.mac.com (st11p00mm-asmtpout003.mac.com []) by ietfa.amsl.com (Postfix) with ESMTP id E6DBE21F8E84 for <dtn-security@irtf.org>; Fri, 22 Mar 2013 17:58:39 -0700 (PDT)
Received: from [] (pool-96-241-42-32.washdc.fios.verizon.net []) by st11p00mm-asmtp003.mac.com (Oracle Communications Messaging Server 7u4-23.01( 64bit (built Aug 10 2011)) with ESMTPSA id <0MK300I3N9DPNJ70@st11p00mm-asmtp003.mac.com> for dtn-security@irtf.org; Sat, 23 Mar 2013 00:58:38 +0000 (GMT)
X-Proofpoint-Virus-Version: vendor=fsecure engine=2.50.10432:5.10.8626, 1.0.431, 0.0.0000 definitions=2013-03-22_06:2013-03-22, 2013-03-22, 1970-01-01 signatures=0
X-Proofpoint-Spam-Details: rule=notspam policy=default score=0 spamscore=0 ipscore=0 suspectscore=0 phishscore=0 bulkscore=0 adultscore=0 classifier=spam adjust=0 reason=mlx scancount=1 engine=6.0.2-1302030000 definitions=main-1303220244
From: Peter Lovell <plovell@mac.com>
To: Amy Alford <aloomis@sarn.org>, dtn-security <dtn-security@irtf.org>
Date: Fri, 22 Mar 2013 20:58:38 -0400
Message-id: <20130323005838.947157858@smtp.mail.me.com>
In-reply-to: <CAB9rx+_EK7u8kkDhscBdqnGHYSeoROTSfhNaALZUodMt4em=_Q@mail.gmail.com>
References: <CAB9rx+85HHsNj=EhmsqhCdtY5k=S4p1Jgzz4VsmEC+43ERygWA@mail.gmail.com> <20130320011114.1072992195@smtp.mail.me.com> <CAB9rx+_EK7u8kkDhscBdqnGHYSeoROTSfhNaALZUodMt4em=_Q@mail.gmail.com>
X-Mailer: CTM PowerMail version 6.1.5b1 build 4653 English (intel) <http://www.ctmdev.com>
MIME-version: 1.0
Content-type: text/plain; charset=US-ASCII
Content-transfer-encoding: quoted-printable
Subject: [dtn-security] Re(2): Including fragment offset in the correlator doesn't prevent all fragment collisions.
X-BeenThere: dtn-security@irtf.org
X-Mailman-Version: 2.1.12
Precedence: list
List-Id: "The Delay-Tolerant Networking Research Group \(DTNRG\) - Security." <dtn-security.irtf.org>
List-Unsubscribe: <https://www.irtf.org/mailman/options/dtn-security>, <mailto:dtn-security-request@irtf.org?subject=unsubscribe>
List-Archive: <http://www.irtf.org/mail-archive/web/dtn-security>
List-Post: <mailto:dtn-security@irtf.org>
List-Help: <mailto:dtn-security-request@irtf.org?subject=help>
List-Subscribe: <https://www.irtf.org/mailman/listinfo/dtn-security>, <mailto:dtn-security-request@irtf.org?subject=subscribe>
X-List-Received-Date: Sat, 23 Mar 2013 00:58:42 -0000

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. 


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

Amy Alford <aloomis@sarn.org> 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
>If the fragments are reassembled before the destination, the destination
>has no way to distinguish the PCB blocks that should correlate with each
>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
>On Tue, Mar 19, 2013 at 9:11 PM, Peter Lovell <plovell@mac.com> wrote:
>> Amy Alford <aloomis@sarn.org> wrote:
>> >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
>> 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