◇ OpenCyber Academy
Engineering · Chapter 2 · English

Chapter 2 — Discrete mathematics

Open, free learning for anyone who wants to protect people and technology. No account is required to read this text or its worked answers.

Chapter 2 — Discrete mathematics

Lesson map

Lesson 02 published. Map, example, EX004.

flowchart TD
  N0["Learning outcomes"]
  N1["2.1 Sets of files"]
  N2["2.2 Boolean logic in search"]
  N3["2.3 Pigeonhole and hashes"]
  N4["2.4 Counting"]
  N5["2.5 Relations and graphs"]
  N6["Proof habits"]
  N7["Synthesis"]
  N0 --> N1 --> N2 --> N3 --> N4 --> N5 --> N6 --> N7
  N7 --> EX["Worked example"]
  EX --> Q["Exercise EX004"]

Logical drawing

flowchart LR
  N0["Learning outcomes"]
  N1["2.1 Sets of files"]
  N2["2.2 Boolean logic in search"]
  N3["2.3 Pigeonhole and hashes"]
  N4["2.4 Counting"]
  N5["2.5 Relations and graphs"]
  N6["Proof habits"]
  N7["Synthesis"]
  N0 --> N1 --> N2 --> N3 --> N4 --> N5 --> N6 --> N7 --> Q["EX004"]

[Learning outcomes]
    |
    v
[2.1 Sets of files]
    |
    v
[2.2 Boolean logic in search]
    |
    v
[2.3 Pigeonhole and hashes]
    |
    v
[2.4 Counting]
    |
    v
[2.5 Relations and graphs]
    |
    v
[Proof habits]
    |
    v
[Synthesis]
    |
    v
[Worked example] --> [Exercise EX004]

Learning outcomes

You will (1) apply sets, logic and counting to evidence; (2) reason about hash collisions with the pigeonhole principle; (3) express filter rules as Boolean logic; (4) count search spaces.

2.1 Sets of files

An image is a set of files. Known files K, files of interest I and the full set F let examiners state operations precisely: the review set is F minus K. Intersection I ∩ K names files of interest that a known-file filter would hide.

Priya builds the sets from hash lists rather than file names, because names change and contents identify the file. A known-file set might contain operating-system files from a reference installation. A file of interest that also appears in that set (I ∩ K) is not suspicious merely because it matched, but it is still not safe to hide it, so the filter writes I ∩ K out separately for review.

2.2 Boolean logic in search

A keyword rule such as (invoice AND NOT template) OR payment is a Boolean expression. Writing it formally avoids ambiguity when another examiner repeats the search, which ISO/IEC 27041 treats as part of assuring that methods are suitable.

Brackets change meaning: invoice AND (NOT template OR payment) selects different documents from the rule above. Priya writes every search with explicit brackets and records it next to its hit count. When a second examiner reruns the identical expression against the same index and gets a different count, the discrepancy points to a tool or index difference rather than a misunderstanding of what was asked.

2.3 Pigeonhole and hashes

SHA-256 maps any input to one of 2^256 outputs. Because there are more possible inputs than outputs, collisions must exist (pigeonhole principle). What matters is that nobody can find one in practice; for MD5 practical collisions are known, so modern guidance prefers SHA-256 for integrity.

The practical point is that integrity checking depends on how hard it is to find a collision, not on whether collisions exist. An MD5 match between an evidence copy and its original is still very likely to be correct when nobody had a chance to tamper with it. Where an adversary might have crafted files, however, MD5 cannot carry the weight, so Northfield records SHA-256 and keeps MD5 only for compatibility with older hash sets.

2.4 Counting

A four-digit PIN has 10^4 = 10,000 possibilities; a six-digit PIN has a million. Counting tells examiners how large a search space is, not how to attack a device; Priya uses it only to explain why device protections matter.

Counting also sizes ordinary workloads. An image with 400,000 files, of which 300,000 match known hashes, leaves 100,000 for review. If a keyword filter keeps one in twenty of those, about 5,000 remain. Priya writes the arithmetic into her plan so that a supervisor can see where the review effort goes and challenge a filter that discards too much.

2.5 Relations and graphs

"Sent message to" is a relation between accounts; drawing it as a graph shows who communicated with whom in a synthetic case.

In the synthetic case the graph has accounts as nodes and an edge from A to B whenever A messaged B. Counting a node's in-edges and out-edges shows who mostly sends and who mostly receives. A path from A to D through B and C shows that information could have travelled indirectly, though not that it did. Priya labels every edge with its earliest and latest message time, so the drawing never implies contact outside the observed period.

Proof habits

Discrete mathematics trains Priya to justify each step. When she claims the review set holds 47 files of interest, she shows the subtraction and the overlap, so a reviewer can check the arithmetic without trusting her.

Worked example

F has 10,000 files, K matches 7,400, and I (planted) has 50, of which 3 are also in K. The review set has 2,600 files and will contain 47 of the 50 files of interest; the 3 in I ∩ K are hidden by filtering.

Synthetic case. The counts are invented.

Errors and limits

Set notation is exact only if the inputs are exact; a mislabelled known set gives a precisely wrong answer.

Exercises

Synthesis

Sets, logic and counting make forensic operations exact and repeatable.

Continue studying — chapter 02 of 50

← Chapter 01 (draft) · Course chapter index · Chapter 03 (draft) →