From 15047fe480e7cd3fcd7c74d284277b86f71ae306 Mon Sep 17 00:00:00 2001
From: Philipp Gesang <philipp.gesang@intra2net.com>
Date: Mon, 28 Aug 2017 15:29:41 +0200
Subject: [PATCH] detect overlapping objects

The CLI will run one additional pass to determine whether objects
overlap one another. Overlap might indicate bad headers or gaps
in the file (object offsets shifted).
---
 deltatar/crypto.py |   51 +++++++++++++++++++++++++++++++++++++++++++++------
 1 files changed, 45 insertions(+), 6 deletions(-)

diff --git a/deltatar/crypto.py b/deltatar/crypto.py
index 2012a1a..a381d2b 100755
--- a/deltatar/crypto.py
+++ b/deltatar/crypto.py
@@ -1843,6 +1843,35 @@ def noise_output_candidates (cands, indent=8, cols=PDTCRYPT_TT_COLUMNS):
         noise (line)
 
 
+SLICE_START = 1 # ordering is important to have starts of intervals
+SLICE_END   = 0 # sorted before equal ends
+
+def find_overlaps (slices):
+    """
+    Find overlapping slices: iterate open/close points of intervals, tracking
+    the ones open at any time.
+    """
+    bounds = []
+    inside = set () # of indices into bounds
+    ovrlp  = set () # of indices into bounds
+
+    for i, s in enumerate (slices):
+        bounds.append ((s [0], SLICE_START, i))
+        bounds.append ((s [1], SLICE_END  , i))
+    bounds = sorted (bounds)
+
+    for val in bounds:
+        i = val [2]
+        if val [1] == SLICE_START:
+            inside.add (i)
+        else:
+            if len (inside) > 1: # closing one that overlapped
+                ovrlp |= inside
+            inside.remove (i)
+
+    return [ slices [i] for i in ovrlp ]
+
+
 def mode_scan (secret, fname, outs=None, nacl=None):
     """
     Dissect a binary file, looking for PDTCRYPT headers and objects.
@@ -1872,12 +1901,13 @@ def mode_scan (secret, fname, outs=None, nacl=None):
         os.close (ifd)
         raise
 
-    junk, todo = [], []
+    junk, todo, slices = [], [], []
     try:
         nobj = 0
         for cand in cands:
             nobj += 1
             vdt, hdr = inspect_hdr (ifd, cand)
+
             if vdt == HDR_CAND_JUNK:
                 junk.append (cand)
             else:
@@ -1893,23 +1923,26 @@ def mode_scan (secret, fname, outs=None, nacl=None):
                     ofname = PDTCRYPT_RESCUENAME % nobj
                     ofd = open2_dump_file (ofname, outs, force=PDTCRYPT_OVERWRITE)
 
+                ctsize = hdr ["ctsize"]
                 try:
-                    ok = try_decrypt (ifd, off0, hdr, secret, ofd=ofd) == hdr ["ctsize"]
+                    l = try_decrypt (ifd, off0, hdr, secret, ofd=ofd)
+                    ok = l == ctsize
+                    slices.append ((off0, off0 + l))
                 finally:
                     if ofd != -1:
                         os.close (ofd)
                 if vdt == HDR_CAND_GOOD and ok is True:
                     noise ("PDT: %d → ✓ valid object %d–%d"
-                           % (cand, off0, off0 + hdr ["ctsize"]))
+                           % (cand, off0, off0 + ctsize))
                 elif vdt == HDR_CAND_FISHY and ok is True:
                     noise ("PDT: %d → × object %d–%d, corrupt header"
-                           % (cand, off0, off0 + hdr ["ctsize"]))
+                           % (cand, off0, off0 + ctsize))
                 elif vdt == HDR_CAND_GOOD and ok is False:
                     noise ("PDT: %d → × object %d–%d, problematic payload"
-                           % (cand, off0, off0 + hdr ["ctsize"]))
+                           % (cand, off0, off0 + ctsize))
                 elif vdt == HDR_CAND_FISHY and ok is False:
                     noise ("PDT: %d → × object %d–%d, corrupt header, problematic "
-                           "ciphertext" % (cand, off0, off0 + hdr ["ctsize"]))
+                           "ciphertext" % (cand, off0, off0 + ctsize))
                 else:
                     raise Unreachable
     finally:
@@ -1921,6 +1954,12 @@ def mode_scan (secret, fname, outs=None, nacl=None):
         noise ("PDT: %d candidates not parseable as headers:" % len (junk))
         noise_output_candidates (junk)
 
+    overlap = find_overlaps (slices)
+    if len (overlap) > 0:
+        noise ("PDT: %d objects overlapping others" % len (overlap))
+        for slice in overlap:
+            noise ("PDT:    × %d→%d" % (slice [0], slice [1]))
+
 def usage (err=False):
     out = print
     if err is True:
-- 
1.7.1