dArchive is distributed under GPL3 license 📘 Check out our GitDatura public repository: /d/archive/wiki?id=6dcf7dc9
🪚 The forgery challenge
dArchive suffers from a forgery issue: all contributions are anonymous; and there is no way to know what to expect within a single snapshot.
This, obviously, opens the door for abuse. How to make sure contributors do not hijack snapshots to include or update content (promotional images, phishing links, etc.)?
- We simply can't trace the content to the server from where it originated (HTTPS everywhere could change this, but bad luck - this is the DN).
- Blacklisting contributors is not a possibility - they're anonymous in the very first degree: they do not have an attachable identity we could list in the first place.
- The administrator can't be expected to check each submission individually or follow up with extended recognition mechanisms (like templates to challenge the content).
At the meantime, the technical proposal to solve this issue should be realistic in regard to the actual capacity of a VPS, meaning the algorithm must be able to follow up with a large number of snapshots without increasing the exploitation cost too much. This, unfortunately, puts AI out of the way (while it could have been a viable solution).
🌿 Towards tree diffs
A mirror receive snapshots over time, some of which origin in the same URL. What we try to achieve is to detect anomalies in a new entry, that could indicate an attempt to forge content. Let's consider an imaginary and oversimplified HTML document over four consecutive snapshots S1 to S4.
<!-- Snapshot 1 (S1) -->
<html>
<body>
<p>A list will display bellow</p>
</body>
</html>
<!-- Snapshot 2 (S2) -->
<html>
<body>
<p>A list of 2 items is displayed bellow</p>
<ul>
<li>Item 1</li>
<li>Item 2</li>
</ul>
</body>
</html>
<!-- Snapshot 3 (S3) -->
<html>
<body>
<p>A list of 3 items is displayed bellow</p>
<ul>
<li>Item 1</li>
<li>Item 2</li>
<li>Item 3</li>
</ul>
</body>
</html>
<!-- Snapshot 4 (S4) -->
<html>
<body>
<p>A list of 3 items is displayed bellow</p>
<ul>
<li>Item 1 (definitive)</li>
<li>Item 2 (definitive)</li>
<li>Item 3 (definitive)</li>
</ul>
<p>This list will not move anymore</p>
</body>
</html>As you can see, some elements appear over time, other change.
- The html root tag is immutable, as is html>body tag;
- The html>body>p tag is present from the start, changes content on S2 and S3, and grows in number on S4;
- The html>body>p>ul tag only appears from S2;
- The html>body>p>ul>li tag only appears from S2 and grows in number on S3.
Observing each change allows to draw a probability matrix for each event that may happen to the tree.
Item
Type
Probability for...
S1
S2
S3
S4
html
Branch
Item appearing
N/A
N/A
N/A
N/A
html>body
Branch
Item appearing
N/A
0%
0%
0%
html>body>p
Branch
Item appearing
N/A
0%
0%
0%
html>body>p:text
Leaf
Content changing
N/A
100%
100%
66%
html>body>p>ul
Branch
Item appearing
N/A
100%
50%
33%
html>body>p>ul>li
Branch
Item appearing
N/A
N/A%
100%
50%
html>body>p>u>li:text
Leaf
Content changing
N/A
N/A
0%
50%
Variation
N/A
N/A
12.5%
30%
During S1, no probability is available for any of the items into the snapshots - no comparison can be drawn from a single tree. This extends to S2 for the few items that only appears on the second snapshot.
- html>body>p content changes on 3 steps over 4, making this event a 66% chance of occurring (two positives, one negative);
- html>body>ul only appear once on S2 and sticks around during S3 and S4, ultimately leading of a 33% chance of the event happening (one positive, two negatives);
- html>body>ul>li appear on S3 but not on S4, leading to a 50% of this event happening;
- html>body>ul>li change content on S4 but not on S3, also leading to a 50% of this event happening;
- And so on.
Now, how can we use those for forgery protection?
Well, each new submission (here S5) either fits the statistics (events with a 100% probability keeps happening, events with a 0% still don't happen, and the average of in-between events fits the probabilistic frame), or it doesn't. Accordingly, forgeries are mostly to happen in the later case: simply because unexpected content is the one to be worrying of. Having the ability of calculating a confidence level for each snapshot creates leverage to better inform the user and, in the most blatant cases, trigger human moderation or blacklist the content altogether. Here, for instance:
- S1 can't be scored (it's the first snapshot);
- S2 can't be scored either (as no comparison was made yet, it's impossible to know which event may happen);
- S3 has a 12.5% variation (because of the additional item in the list);
- S4 has an approximate 25% variation (because of the various changes in the tree).
To this regard, S3 may be consider as a safer snapshot than S4. Which, looking at the content itself, seems coherent: S3 only introduced an additional li tag, while S4 went with several content modifications. Nice and simple 🤗
🍃 Wrapping it up
dArchive implementation is, obviously, a bit more complicated than the example bellow - but the good news is: it runs down to a very few basic concepts.
1️⃣ Snapshot content is either branch or leaf.
- Branches are HTML tags. They can have branches and leaves as children.
- Leaves are either HTML text content or HTML attributes.
2️⃣ Branches and leaves are fingerprinted so they can be compared amongst consecutive snapshots. Fingerprint includes the path to access the element, such as additional information derived from it.
3️⃣ Branches and leaves are affected by different events. The former can have their inner content change, they can be moved around, multiplied, removed, and so on. The later is mostly about text content.
That's for the overall design. Everything else is mathematics, and a few additional features.
🌱 Growing the trust
To be fully efficient, the baseline algorithm has to be increased through a couple of key mechanisms.
- Snapshots must be as frequent as possible. The more images are collected over time, the more precise the probabilistic tree becomes.
- Snapshot collection has to be randomized between contributors. In order to avoid a single attacker to "spam" a mirror with fake snapshots to distort the probabilistic profile of a specific content, snapshot collection is distributed amongst (anonymous) contributors on a randomized basis.
- Snapshot are grouped by domain and URI. Pages of a specific type (like tforum threads, vendor listings, etc.) are supposed to share similarities. Therefore, the probabilistic model can be consolidated (and made stronger) by grouping them together.
Moreover, the tree is monitored to cover a large variety of events, some of which based - like the ones in the example above - on comparisons over S-1 to S versions of a same snapshot, but also S-f(t) to S (f(t) being a correlated to a time period), S-1 to S+1 (to detect anomalies), and so on.
In the next post, we'll discuss implementation using Rust and a simple relational database. Stay tuned!
More tech talk & DN tweaks 📚 On /d/archive
🎖️ Contributed by /d/pgpfreaks and /d/b1ackExchange.