commit ce45a60f30d18650e9a45d7945ba1fa8870a93dd
parent ca768835d708964f74305ffb20862e3be6dd32c8
Author: Elias Summermatter <elias.summermatter@seccom.ch>
Date: Sun, 28 Feb 2021 15:36:57 +0100
Improved
Diffstat:
1 file changed, 60 insertions(+), 22 deletions(-)
diff --git a/draft-summermatter-set-union.xml b/draft-summermatter-set-union.xml
@@ -1898,25 +1898,42 @@ FUNCTION get_bucket_id (key, number_of_buckets_per_element, ibf_size)
<dl>
<dt><xref target="messages_request_full" format="title" /></dt>
<dd>
- This message does offer a small attack surface to an attacker because
- its a fixed-size message and no custom content can be passed.
- Its important to check that its not possible for an attacker to request
- the full set multiple times.
+ It needs to be checked that the full synchronisation is
+ plausible according to the formula deciding which operation mode
+ is applicable this is achieved by calculating the upper and lower
+ boundaries of the number of elements in the other peers set.
+ The lower boundary of number of elements can be easily
+ memorized as result from the last synchronisation and the upper
+ boundary can be estimated with prior knowledge of the maximal
+ plausible increase of element since the last reconciliation and
+ the maximal plausible number of elements.
<!-- IMPLEMENT: Check if this two checks already exists -->
</dd>
<dt><xref target="messages_ibf" format="title" /></dt>
<dd>
- This message contains variable content and needs to be checked for
- a valid formal format of an IBF. Its important do define a threshold to limit
+ Its important do define a threshold to limit
the maximal count of IBFs that are expected from the other peer.
+ This maximal plausible size can be calculated with the known inputs:
+ number of elements in my set and the pre defined applications upper
+ limit as described in the performance section.
+ <!-- IMPLEMENT: Is this already checked?-->
+ <!-- TODO: Link performance section -->
+ That the other peer chooses the correct mode of operation MUST
+ be checked as described in the section above.
<!-- IMPLEMENT: Is this already checked?-->
</dd>
<dt><xref target="messages_full_element" format="title" /></dt>
<dd>
- If a valid full element is received in this state there are
- no additional security measurement that need to be implemented in this
- state.
+ If a full element is received the set of the other peer
+ is smaller than the set of the peer in the <strong>Expecting IBF</strong>
+ state and the set difference is smaller than threshold for
+ full synchronisation as described in the performance section.
+ <!-- TODO: Add performance section -->
+ This can be verified by calculating the plausible upper and lower boundaries
+ of the number of elements in the other peers set as described in
+ the first section.
+ <!-- if valid ok otherwise cancel connection! -->
</dd>
</dl>
</section>
@@ -1927,14 +1944,18 @@ FUNCTION get_bucket_id (key, number_of_buckets_per_element, ibf_size)
<dl>
<dt><xref target="messages_full_element" format="title" /></dt>
<dd>
- When receiving full elements there needs to be checked that not
- more elements are received from the other peer that plausibly can
- be in the set.
+ When receiving full elements there needs to be checked that every
+ element is a valid element, no element is resized more than once and
+ not more or less elements are received as the other peer has committed
+ to in the beginning of the operation.
<!-- IMPLEMENT: Is this check already implemented?-->
</dd>
<dt><xref target="messages_full_done" format="title" /></dt>
<dd>
- Beside the formal message validity check no future check is required.
+ When receiving the full done message its important to check that
+ not less elements are received as the other peer has committed to
+ send.
+ <!-- IMPLEMENT: Is this check already implemented?-->
</dd>
</dl>
</section>
@@ -1946,8 +1967,9 @@ FUNCTION get_bucket_id (key, number_of_buckets_per_element, ibf_size)
<dt><xref target="messages_ibf" format="title" /></dt>
<dd>
When receiving multiple IBFs its important to check that the other
- peer can only send as many IBFs as expected, otherwise its possible
- for an attacker to keep a connection open for ever.
+ peer can only send as many IBFs as expected. The number of expected IBFs can
+ be calculated with the knowledge of the set difference as described in the
+ performance section.
</dd>
</dl>
</section>
@@ -1956,28 +1978,40 @@ FUNCTION get_bucket_id (key, number_of_buckets_per_element, ibf_size)
<t>
In the Active Decoding state its important to prevent an attacker from
generating and passing unlimited amount of IBF that do not decode or
- even worse generate an IBF that decoding sends the peers in an endless loop.
+ even worse generate an IBF that is constructed to sends the peers in an endless loop.
To prevent an endless loop in decoding a loop detection should be implemented
the simplest solution would be to prevent decoding of more than a given amount of elements,
- a little more robust solution is be to implement a algorithm to detect a loop by
- analyzing past partially decoded IBFs.
+ a more robust solution is to implement a algorithm that detects a loop by
+ analyzing past partially decoded IBFs to detect cycles. This can be archived
+ by saving the hash of all prior partly decoded IBFs hashes in a hashmap and check
+ for every inserted hash if it is already in the hashmap.
+ <!-- TODO: Link some algo to find loops in directed graph -->
<!-- IMPLEMENT: Implement an algo that detects loops in IBF decoding -->
</t>
+ <t>
+ If the IBF decodes more or less elements than are plausible the
+ operation MUST be terminated. The upper and lower threshold
+ for the decoded elements can be calculated with the peers set size
+ and the other peer committed set sizes from the <strong>Expecting IBF</strong>
+ State.
+ </t>
+
+ <!-- Wenne element mehrfach decodiert seitenwechseln daher detecten. -->
<t>Security considerations for received messages:</t>
<dl>
<dt><xref target="messages_offer" format="title" /></dt>
<dd>
If an offer for an element that never has been requested by
- an inquiry or the demand has already been send the offer MUST be discarded.
- This requirement can be fulfilled by a simple table that keeps track of all send inquiries
+ an inquiry or if an offer is received twice the operation MUST be terminated.
+ This requirement can be fulfilled by a table that keeps track of all send inquiries
and if they already have been answered.
<!-- IMPLEMENT: Check to keep track of all send Inquiries -->
</dd>
<dt><xref target="messages_elements" format="title" /></dt>
<dd>
If an element that never has been requested by
- a demand or is already part of the set it MUST be discarded.
+ a demand or is already part of the set the connection MUST be dropped.
This requirement can be fulfilled by a simple table that keeps track
of all send demands and checking for every received elements that
its not already part of the set.
@@ -1990,7 +2024,7 @@ FUNCTION get_bucket_id (key, number_of_buckets_per_element, ibf_size)
<dd>
For every received demand a offer has to be send in advance. If an demand
for an element is received that never has been offered or already has
- been answered the demand MUST be discarded. Its required to implement
+ been answered the connection MUST be dropped. Its required to implement
a list which keeps track of all send and answered offers.
<!-- IMPLEMENT: Check to keep track of all send demands -->
@@ -2038,6 +2072,10 @@ FUNCTION get_bucket_id (key, number_of_buckets_per_element, ibf_size)
unpassable large, in case its to large the operation MUST be terminated.
<!-- IMPLEMENT: Terminate if in check expect se state for a max size difference is exceeded -->
</dd>
+ <dd>
+ In case of compressed strata estimators the decompression algorithm has to
+ be protected against
+ </dd>
</dl>
</section>
<section anchor="security_states_full_receiving" numbered="true" toc="default">
