commit ed2f54eb77a1fcd12cba8a6934168e3756a422bb
parent e97391fb44c69274ba2c2e6ac276383f20779e24
Author: Elias Summermatter <elias.summermatter@seccom.ch>
Date: Mon, 15 Mar 2021 11:06:48 +0100
Added some more pseudocode in security section
Diffstat:
1 file changed, 164 insertions(+), 32 deletions(-)
diff --git a/draft-summermatter-set-union.xml b/draft-summermatter-set-union.xml
@@ -1989,6 +1989,21 @@ FUNCTION addMessageToStore(store, message)
store.set(key) = 1
return TRUE
+# Check if hash is in store
+FUNCTION markElementAsReceived(store)
+ IF store.get(key) != NULL || store.get(key) != 1
+ return FALSE
+ store.update(key, 0)
+ return TRUE
+
+FUNCTION isStoreComplete(store)
+ FOR elements in store
+ IF elements.value != 0:
+ return FALSE
+ ENDIF
+ ENDFOR
+ return TRUE
+
# Returns the count of message received
FUNCTION getNumberOfMessage(store)
return store.size()
@@ -2011,7 +2026,8 @@ FUNCTION number_elements_last_sync(client_id)
ENDIF
return 0
-FUNCTION saveNumberOfElementsLastSync(client_id, remote_setsize)
+
+FUNCTION save_number_of_elements_last_sync(client_id, remote_setsize)
number_store.update(clientID, remote_setsize)
]]></artwork>
</figure>
@@ -2073,7 +2089,7 @@ FUNCTION validate_messages_request_full(client_id, remote_setsize, local_setsize
ENDIF
# Update number of elements in store
- saveNumberOfElementsLastSync(client_id, remote_setsize)
+ save_number_of_elements_last_sync(client_id, remote_setsize)
# Check for max plausible set size as defined on use case basis (can be infinite)
plausible_setsize = getMaxPlausibleSetSize()
@@ -2168,18 +2184,18 @@ FUNCTION validate_messages_full_element(client_id, remote_setsize, local_setsize
# On first run create store and make initial checks
IF is_undefined(store)
- store = createStore()
+ full_element_msg_store = createStore()
IF ! validate_messages_full_element_init(client_id, remote_setsize, local_setsize, initial_local_size, set_diff)
return FALSE
ENDIF
# Prevent duplication of received message
- IF ! addMessageToStore(store, message)
+ IF ! addMessageToStore(full_element_msg_store, message)
return FALSE
ENDIF
# Prevent to receive more elements than the remote peer has
- number_received_messages = getNumberOfMessage(store)
+ number_received_messages = getNumberOfMessage(full_element_msg_store)
IF ( number_received_messages > remote_setsize )
return FALSE
@@ -2203,7 +2219,7 @@ FUNCTION validate_messages_full_element_init(client_id, remote_setsize, local_se
ENDIF
# Update number of elements in store
- saveNumberOfElementsLastSync(client_id, remote_setsize)
+ save_number_of_elements_last_sync(client_id, remote_setsize)
# Check for max plausible set size as defined on use case basis (can be infinite)
plausible_setsize = getMaxPlausibleSetSize()
@@ -2235,15 +2251,18 @@ FUNCTION validate_messages_full_element_init(client_id, remote_setsize, local_se
<dl>
<dt><xref target="messages_full_element" format="title" /></dt>
<dd>
+ <t>
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. Detail pseudocode implementation
can be found in <xref target="security_states_expecting_ibf" format="title" />
<!-- IMPLEMENT: Is this check already implemented?-->
+ </t>
</dd>
<dt><xref target="messages_full_done" format="title" /></dt>
<dd>
+ <t>
When receiving the full done message its important to check that
not less elements are received as the other peer has committed to
send.
@@ -2252,6 +2271,22 @@ FUNCTION validate_messages_full_element_init(client_id, remote_setsize, local_se
the sets differ a resynchronisation is required. The count of possible
resynchronisation MUST be limited to prevent resource exhaustion attacks.
<!-- IMPLEMENT: Is this check already implemented?-->
+ </t>
+ <figure anchor="security_states_full_sending_full_done_code">
+ <artwork name="" type="" align="left" alt=""><![CDATA[
+FUNCTION validate_messages_full_done(full_done_message, full_element_msg_store, remote_setsize, local_set)
+
+ # Check that correct number of elements has been received
+ number_received_messages = getNumberOfMessage(full_element_msg_store)
+ IF ( number_received_messages != remote_setsize )
+ return FALSE
+ ENDIF
+ IF local_set.getFullHash() != full_done_message.fullSetHash
+ return FALSE
+ ENDIF
+ return TRUE
+ ]]></artwork>
+ </figure>
</dd>
</dl>
</section>
@@ -2262,10 +2297,16 @@ FUNCTION validate_messages_full_element_init(client_id, remote_setsize, local_se
<dl>
<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. The number of expected IBFs can
- be calculated with the knowledge of the set difference as described in the
- performance section.
+ <t>
+ When receiving multiple IBFs its important to check that the other
+ 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.
+ </t>
+ <t>
+ Use pseudocode of the function "validate_messages_ibf" as described in
+ <xref target="security_states_expecting_ibf" format="title" /> section.
+ </t>
</dd>
</dl>
</section>
@@ -2298,43 +2339,134 @@ FUNCTION validate_messages_full_element_init(client_id, remote_setsize, local_se
<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 if an offer is received twice the operation MUST be terminated.
- This requirement can be fulfilled by saving lists that keeps track of the state of
- all send inquiries and offers. When answering offers these lists MUST be checked.
- <!-- IMPLEMENT: Check to keep track of all send Inquiries -->
+ <t>
+ If an offer for an element that never has been requested by
+ an inquiry or if an offer is received twice the operation MUST be terminated.
+ This requirement can be fulfilled by saving lists that keeps track of the state of
+ all send inquiries and offers. When answering offers these lists MUST be checked.
+ <!-- IMPLEMENT: Check to keep track of all send Inquiries -->
+ </t>
+ <figure anchor="security_states_active_decoding_offer_code">
+ <artwork name="" type="" align="left" alt=""><![CDATA[
+FUNCTION validate_messages_offer(offer_message,inquiry_msg_store)
+ IF is_undefined(store)
+ offer_msg_store = createStore()
+ ENDIF
+
+ # Store message to prevent double sending of messages
+ IF ! addMessageToStore(offer_msg_store, offer_message)
+ return FALSE
+ ENDIF
+
+ # Check that for every received offer a inquiry has been sent and non is
+ # sent multiple times
+ IF ! markElementAsReceived(inquiry_msg_store)
+ return FALSE
+ return TRUE
+ ]]></artwork>
+ </figure>
</dd>
<dt><xref target="messages_elements" format="title" /></dt>
<dd>
- If an element that never has been requested by
- a demand or is received double the operation MUST be terminated.
- This requirement can be fulfilled by a simple table that keeps track
- of the state of all send demands.
- <!-- IMPLEMENT: Check to keep track of all send demands -->
- If an invalid element is received the operation has failed and the
- MUST be terminated.
- <!-- IMPLEMENT: Termination if invalid element si revived -->
+ <t>
+ If an element that never has been requested by
+ a demand or is received double the operation MUST be terminated.
+ This requirement can be fulfilled by a simple table that keeps track
+ of the state of all send demands.
+ <!-- IMPLEMENT: Check to keep track of all send demands -->
+ If an invalid element is received the operation has failed and the
+ MUST be terminated.
+ <!-- IMPLEMENT: Termination if invalid element si revived -->
+ </t>
+ <figure anchor="security_states_active_decoding_elements_code">
+ <artwork name="" type="" align="left" alt=""><![CDATA[
+FUNCTION validate_messages_elements(element_message,demand_msg_store)
+ IF is_undefined(store)
+ element_msg_store = createStore()
+ ENDIF
+
+ # Store message to prevent double sending of messages
+ IF ! addMessageToStore(element_msg_store, element_message)
+ return FALSE
+ ENDIF
+
+ # Check that for every received element a demand has been sent and non is
+ # sent multiple times
+ IF ! markElementAsReceived(demand_msg_store)
+ return FALSE
+ return TRUE
+ ]]></artwork>
+ </figure>
</dd>
<dt><xref target="messages_demand" format="title" /></dt>
<dd>
+ <t>
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 the offer already has
been answered with a demand the operation MUST be terminated. Its required to implement
a list which keeps track of the state of all send offers and received demands.
+ </t>
+ <figure anchor="security_states_active_decoding_demand_code">
+ <artwork name="" type="" align="left" alt=""><![CDATA[
+FUNCTION validate_messages_demand(demand_message,offer_msg_store)
+ IF is_undefined(store)
+ demand_msg_store = createStore()
+ ENDIF
+ # Store message to prevent double sending of messages
+ IF ! addMessageToStore(demand_msg_store, demand_message)
+ return FALSE
+ ENDIF
+
+ # Check that for every received demand a offer has been sent and non is
+ # sent multiple times
+ IF ! markElementAsReceived(offer_msg_store)
+ return FALSE
+ return TRUE
+ ]]></artwork>
+ </figure>
<!-- IMPLEMENT: Check to keep track of all send demands -->
</dd>
<dt><xref target="messages_done" format="title" /></dt>
<dd>
- The done message is only received if the IBF has been finished
- decoding and all offers have been sent. If the done message is received before
- the decoding of the IBF is finished or all open offers and demands
- have been answered the operation MUST be terminated.
- <!-- IMPLEMENT: Check that in active decoding no done message is received before ibf has been decoded-->
- The 512-bit hash of the complete reconciled set contained in
- the done message is required to ensures that both sets are truly identical. If
- the sets differ a resynchronisation is required. The count of possible
- resynchronisation MUST be limited to prevent resource exhaustion attacks.
+ <t>
+ The done message is only received if the IBF has been finished
+ decoding and all offers have been sent. If the done message is received before
+ the decoding of the IBF is finished or all open offers and demands
+ have been answered the operation MUST be terminated.
+ <!-- IMPLEMENT: Check that in active decoding no done message is received before ibf has been decoded-->
+ The 512-bit hash of the complete reconciled set contained in
+ the done message is required to ensures that both sets are truly identical. If
+ the sets differ a resynchronisation is required. The count of possible
+ resynchronisation MUST be limited to prevent resource exhaustion attacks.
+ </t>
+ <figure anchor="security_states_active_decoding_demand_code">
+ <artwork name="" type="" align="left" alt=""><![CDATA[
+FUNCTION validate_messages_done(messages_done, offer_msg_store, demand_msg_store, element_msg_store)
+
+ # Check that all offers have been received
+ IF ! isStoreComplete(offer_msg_store)
+ return FALSE
+ ENDIF
+
+ # Check that all demands have been received
+ IF ! isStoreComplete(demand_msg_store)
+ return FALSE
+ ENDIF
+
+ # Check that all elements have been received
+ IF ! isStoreComplete(element_msg_store)
+ return FALSE
+ ENDIF
+
+ # Validate that set is truly identical
+ IF local_set.getFullHash() != full_done_message.fullSetHash
+ return FALSE
+ ENDIF
+
+ return TRUE
+ ]]></artwork>
+ </figure>
</dd>
</dl>
</section>
