Hi,
This should have been a brief draft for DoS resistant introductions to WoT,
but it grew a bit when I added the math.
Its objective in terms of spam prevention is that if I am in good standing
I can authorise a limited number of introductions from my peers,
in such a way that I can't trace who was actually introduced.
Despite its length, this is just a rough draft. Ways to improve it could be
M out of N tokens (N tokens are released. if you hold at least M
uncompromised tokens, you can join. This makes life harder for spammers) and
group decisions (Alice selects 5 other WoT IDs and asks them to issue a
shared introduction-code which can be used for either of them). Also effective
ways to blind tokens would be very useful, so I cannot know who issued them.
I use the term introduction-code or introduction as the means you need to
make a WoT-ID give you a trust of 0. A replacement for CAPTCHAs.
Also it is not cryptographically sophisticated. It is a pretty simple
gossipping scheme. Important is, that it only uses WoT functions.
And now enough pre-talk.
Assumption: WoT works at keeping out spammers.
Therefore the proof-of-work we have is “I am part of the WoT. I have
positive trust, so I am no spammer”.
Using this, we can design a scheme to allow people to introduce new IDs.
One of the goals of this scheme is to provide a limited number of
pre-proved introductions which people can hand out to new users, for
example when they give someone a darknet invite.
Each WoT ID shares a list of introduction codes. It encrypts each of
them to a random sample of WoT IDs to whom the ID manually set a
positive trust-level. These encrypted introduction codes are shared
via the profile (seen when another ID sees an update). If the ID
shares a trust-list, it also shares the list of IDs it encrypted to,
so other IDs only have to download encrypted keys which they can
decrypt (this does not spread information which wasn’t available from
the trustlist).
If a WoT ID sees an introduction key, it checks whether it has been
used. If it has not been used, yet, it stores it.
WoT IDs sort the introduction keys they downloaded in 4 different sets at
random:
- My keys: These are kept for future use to introduce new IDs.
- Forward via WoT: These are passed on to other WoT IDs in the same
way as the initial list. There should be limited hops (a HTL).
- Forward to friends: These are passed on to darknet friends.
- Forward to strangers: These are passed to *new* opennet connections.
Note: While writing the math I realized that more than 4 hops and
forwarding to less than 4 nodes would be a better due to
multistep filtering of those keys which have already been
claimed (either legitimately or in an attack).
Math:
- Assume one introduction generated per week.
- Share to 4 random WoT IDs.
- Hops: 4.
- Lifetime of an introduction: 1 year.
Each WoT-ID has to check 50 keys periodically: One for each week of
the last year.
Each WoT-ID gets 16 introduction keys via WoT-forwarding per week
(4 +4*4/4 + 4*4^2/4^2 + 4*4^3/4^3). It gets 160 introductions if we
add forwards via darknet and via opennet. Adding the keys passed via
darknet and opennet, it has to check at most 1 key per hour - less if
the keys are being used (because only unused introduction keys are
forwarded).
Each key reaches 160 IDs, so each WoT ID has a chance of
160/number-of-wot-ids to receive a given introduction. Let us assume
that the WoT has 3000 IDs and this chance is 5%.
We now want to know how big the chance is that I receive a key which a
given attacker, who owns a certain percentage of the WoT, does not
have yet. To provide an upper estimate, we assume that the attacker
has a way to block a key without stopping its propagation.
For each key I get, the attacker has a 4 in 300 chance per
attacking ID that the key was killed.
- One attacking ID, I have a 296 in 300 chance per key that the key is
still good.
- 2 attacking IDs: I have a 296^2 in 300^2 chance per key that the key is
still good.
- N attacking IDs: I have a 296^N in 300^N chance per key that the key is still
good.
- At 92 attacking IDs, the average number of good keys a given ID gets
is down to 1.
So without checking the validity of keys before passing them on, this
scheme can be foiled by an attacker who owns 3% of the trusted
IDs in the currrent WoT. Note that a trusted ID is one which got manual
trust. An invitation does not give you manual trust. You need to trick
at least one person into marking you as non-spammer.
Now we check how big the chance is that I receive a key which a given
attacker who owns a certain percentage of *opennet* does not have yet.
Any shared key reaches 56 nodes over opennet. So
assuming for the worst case that every opennet node takes part in the
WoT and we have 3000 opennet nodes, any opennet node has a chance of
0.0186 (56 / 3000) to get a given key. An Attacker has to own 213
opennet nodes to reduce the average number of good keys per WoT ID to
1. Still not very safe.
For a realistic opennet of 30000 nodes and only 3000 nodes
participating in WoT, the attacker needs 2154 nodes. If we only pass
the introductions to nodes our node did not see before, the attacker
has to introduce 2154 new nodes per week. This is doable but
considerably more effort.
Finally we check how testing keys for validity before passing them on
affects the chances for attackers. Conditions:
- An attacker has to use an introduction before it can be used by
someone else. This limits the holding time. If a key is used before
the attacker can use it, that is endgame for the attacker.
- We have seen that it is trivial for an attacker to kill all keys at
the last hop. But a key the attacker sees at the last hop is very
likely still at the second hop for many IDs. If the attacker would
only kill keys at the last hop, people could use them at the second
hop. Endgame: The attacker must kill all keys as soon as possible.
- We simplify this scheme to one without keeping keys and only one
method of propagation (WoT).
Let us assume that the attacker owns 6% of the IDs which get
reached. For each key there is a 24% chance per hop that it will reach
an attacker who will kill it. Each WoT ID gets 4 keys from the first
hop. 1 of those keys will have been killed by attackers. The 3 good
keys are held by 12 IDs (who each have two more good keys). Each of
the 12 IDs now forwards the 3 good keys to 4 other IDs. This makes a
total of 48 nodes reached per key. The chance that a key survives is
therefore 5%. Since these 12 IDs send out a total of 36 keys, that
gives 1.8 good keys which arrive at the third hop without having been
intercepted. 10 to 11 of the 12 IDs with good keys have lost all their
good keys due to the forwarding, so we now have 48+1 = 49 IDs with
valid introductions, but only for 1 or 2 new IDs per week. If they
forward the key again and one key will reach 49*4=196 IDs and have a
chance to survive of 0.05%. So with 6% attackers in the WoT, this
scheme can only work with 3 hops. It can accomodate 1 to 2 new IDs per
64 IDs per week, which equals a doubling of users per year.
With 3% attackers these numbers would look wastly better (survival
rate of 88% at the first hop, 37% at the second hop and something
around 23% at the third).
With 12% attackers, it would die at the second hop.
To mitigate that, we could adjust the HTL via the number of unclaimed
vs. claimed introductions. In case of an attack, there will be only
few unclaimed introductions left (just as for a sudden network growth,
but we can test forr that using other metrics). This would allow
reacting to attacks automatically at runtime.
Best wishes,
Arne
Note: This scheme does not take into account that an introduction is
only useful if it connects you to an ID which is interacting in
the context in which you want to communicate. This will likely
be a scaling factor in favor of the attacker.
--
Unpolitisch sein
heißt politisch sein,
ohne es zu merken.
- Arne (http://draketo.de)
_______________________________________________
Devl mailing list
[email protected]
https://emu.freenetproject.org/cgi-bin/mailman/listinfo/devl
