commit 3217f39e11167ccf51517996642001c9ef3ce3af
parent cc73546624d723535ac90fe2e293a7e08b2c1fc6
Author: Elias Summermatter <elias.summermatter@seccom.ch>
Date: Wed, 16 Jun 2021 10:22:35 +0200
Resolved some pseudocode inconsistencies
Diffstat:
3 files changed, 48 insertions(+), 43 deletions(-)
diff --git a/.gitignore b/.gitignore
@@ -1,4 +1,6 @@
/.idea/
*.xml.swp
*.html
-*.min.js
-\ No newline at end of file
+*.min.js
+*.pdf
+*.txt
+\ No newline at end of file
diff --git a/draft-summermatter-set-union.pdf b/draft-summermatter-set-union.pdf
Binary files differ.
diff --git a/draft-summermatter-set-union.xml b/draft-summermatter-set-union.xml
@@ -409,6 +409,7 @@ FUNCTION salt_key(key,ibf_salt):
s = (ibf_salt * 7) modulo 64;
/* rotate key */
return (key >> s) | (key << (64 - s))
+END FUNCTION
# INPUTS:
@@ -422,6 +423,7 @@ FUNCTION id_calculation (element,ibf_salt):
PRF=HMAC-SHA256
key = HKDF(XTR, PRF, kdf_salt, element) modulo 2^64
return salt_key(key, ibf_salt)
+END FUNCTION
]]></artwork>
</figure>
</section>
@@ -465,27 +467,28 @@ FUNCTION get_bucket_id (key, k, L)
bucket = CRC32(key)
i = 0 // unsigned 32-bit index
filled = 0
- WHILE filled < k
+ WHILE filled < k DO
element_already_in_bucket = false
j = 0
- WHILE j < filled
+ WHILE j < filled DO
IF dst[j] == bucket modulo L THEN
element_already_in_bucket = true
- ENDIF
+ END IF
j++
- ENDWHILE
+ END WHILE
IF !element_already_in_bucket THEN
dst[filled] = bucket modulo L
filled = filled + 1
- ENDIF
+ END IF
x = (bucket << 32) | i // 64 bit result
bucket = CRC32(x)
i = i + 1
- ENDWHILE
+ END WHILE
return dst
+END FUNCTION
]]></artwork>
</figure>
</section>
@@ -2066,10 +2069,10 @@ FUNCTION decide_operation_mode(avg_es,
# this check at the beginning the logic below
# should always yield the same result for these
# extreme cases, allowing us to omit this code.
- IF (0 == rss)
+ IF 0 == rss THEN
RETURN FULL_SYNC_LOCAL_SENDING_FIRST
END IF
- IF (0 == lss)
+ IF 0 == lss THEN
RETURN FULL_SYNC_REMOTE_SENDING_FIRST
END IF
@@ -2095,7 +2098,7 @@ FUNCTION decide_operation_mode(avg_es,
# Estimate messages required to transfer IBF
ibf_bucket_count = estimated_total_diff * IBF_BUCKET_NUMBER_FACTOR
- IF (ibf_bucket_count <= IBF_MIN_SIZE)
+ IF ibf_bucket_count <= IBF_MIN_SIZE THEN
ibf_bucket_count = IBF_MIN_SIZE
END IF
ibf_message_count = ceil (ibf_bucket_count / MAX_BUCKETS_PER_MESSAGE)
@@ -2135,8 +2138,8 @@ FUNCTION decide_operation_mode(avg_es,
# Decide for a optimal mode of operation
full_cost_min = MIN (cost_local_full_sync,
cost_remote_full_sync)
- IF (full_cost_min < diff_cost)
- IF (cost_remote_full_sync > cost_local_full_sync)
+ IF full_cost_min < diff_cost THEN
+ IF cost_remote_full_sync > cost_local_full_sync THEN
RETURN FULL_SYNC_LOCAL_SENDING_FIRST
ELSE
RETURN FULL_SYNC_REMOTE_SENDING_FIRST
@@ -2144,6 +2147,7 @@ FUNCTION decide_operation_mode(avg_es,
ELSE
RETURN DIFFERENTIAL_SYNC
END IF
+END FUNCTION
]]></artwork>
</figure>
</section>
@@ -2172,8 +2176,8 @@ FUNCTION initial_ibf_size(sd)
# basically always be below one MTU, so there is
# little to be gained, while a smaller IBF would
# increase the chance of a decoding failure.
- return MAX(37, IBF_BUCKET_NUMBER_FACTOR * sd);
-FUNCTION END
+ RETURN MAX(37, IBF_BUCKET_NUMBER_FACTOR * sd);
+END FUNCTION
# CONSTANTS:
# IBF_BUCKET_NUMBER_FACTOR = 2: The amount the IBF gets increased if decoding fails
@@ -2187,8 +2191,8 @@ FUNCTION get_next_ibf_size(de, lis)
next_size = IBF_BUCKET_NUMBER_FACTOR * (lis - de)
# The MAX operation here also ensures that the
# result is positive.
- return MAX(37, next_size);
-FUNCTION END
+ RETURN MAX(37, next_size);
+END FUNCTION
]]></artwork>
</figure>
</section>
@@ -2244,13 +2248,14 @@ FUNCTION END
FUNCTION ibf_get_max_counter(ibf)
max_counter=1 # convince static analysis that we never take log2(0)
- FOR bucket IN ibf
- IF bucket.counter > max_counter
+ FOR bucket IN ibf DO
+ IF bucket.counter > max_counter THEN
max_counter = bucket.counter
END IF
END FOR
# next bigger discrete number of the binary logarithm of the max counter
- RETURN CEILING( log2 ( max_counter ) )
+ RETURN CEILING( LOG2( max_counter ) )
+END FUNCTION
# INPUTS:
# ibf: The IBF
@@ -2275,14 +2280,14 @@ FUNCTION pack_counter(ibf, offset, count)
byte_ctr = 0
buffer=[]
- FOR bucket IN ibf[offset] to ibf[count]
+ FOR bucket IN ibf[offset] TO ibf[count] DO
counter = bucket.counter
byte_len = counter_bytes
- WHILE byte_len + store_bits < 8
+ WHILE byte_len + store_bits < 8 DO
bit_to_shift = 0
- IF store_bits > 0 OR byte_len > 8
+ IF store_bits > 0 OR byte_len > 8 THEN
bit_free = 8 - store_bits
bit_to_shift = byte_len - bit_free
store = store << bit_free
@@ -2300,7 +2305,7 @@ FUNCTION pack_counter(ibf, offset, count)
END FOR
# Write the last partial packed byte to the buffer
- IF store_bits > 0
+ IF store_bits > 0 THEN
buffer[byte_ctr] = store << (8 - store_bits)
byte_ctr = byte_ctr + 1
END IF
@@ -2331,17 +2336,17 @@ FUNCTION unpack_counter(ibf, offset, count, cbl, pd)
bit_to_pack_left = 8
byte_ctr++
- WHILE bit_to_pack_left >= 0
+ WHILE bit_to_pack_left >= 0 DO
# Prevent packet from reading more than required
- IF ibf_bucket_ctr > (count - 1)
+ IF ibf_bucket_ctr > (count - 1) THEN
RETURN
END IF
- IF store_bits + bit_to_pack_left >= cbl
+ IF store_bits + bit_to_pack_left >= cbl THEN
bit_use = cbl - store_bits
- IF store_bits > 0
+ IF store_bits > 0 THEN
store = store << bit_use
END IF
bytes_to_shift = bit_to_pack_left - bit_use
@@ -2357,7 +2362,7 @@ FUNCTION unpack_counter(ibf, offset, count, cbl, pd)
ELSE
store_bits = store_bits + bit_to_pack_left
- IF 0 == store_bits
+ IF 0 == store_bits THEN
store = byte_to_read
ELSE
store = store << bit_to_pack_left
@@ -2410,7 +2415,7 @@ END FUNCTION
FUNCTION se_key_salting(value, salt)
s = (salt * 7) modulo 64
- return (value >> s) | (value << (64 - s))
+ RETURN (value >> s) | (value << (64 - s))
END FUNCTION
]]></artwork>
@@ -2481,17 +2486,17 @@ END FUNCTION
# Output:
# returns TRUE if parameters in byzantine bounds otherwise returns FALSE
FUNCTION check_byzantine_bounds (rec,rsd,lec,lsd)
- IF rec + rsd > UPPER_BOUND
+ IF rec + rsd > UPPER_BOUND THEN
RETURN FALSE
- IF END
- IF lec + lsd > UPPER_BOUND
+ END IF
+ IF lec + lsd > UPPER_BOUND THEN
RETURN FALSE
- IF END
- IF rec < LOWER_BOUND
+ END IF
+ IF rec < LOWER_BOUND THEN
RETURN FALSE
- IF END
+ END IF
RETURN TRUE
-FUNCTION END
+END FUNCTION
]]></artwork>
</figure>
</section>
@@ -2631,16 +2636,16 @@ FUNCTION full_sync_plausibility_check (state,rs,lis,rd,rf)
# Make sure that no element is received double when
# all elements already are transmitted to the oder side.
- IF FULL_SENDING == state AND rd > 0
+ IF FULL_SENDING == state AND rd > 0 THEN
RETURN FALSE
END IF
# Probabilistic algorithm to check for plausible
# element distribution
- IF FULL_RECEIVING == state
+ IF FULL_RECEIVING == state THEN
# Prevent division by 0
- IF 0 <= rs
+ IF 0 <= rs THEN
rs = 1
END IF
@@ -2648,7 +2653,7 @@ FUNCTION full_sync_plausibility_check (state,rs,lis,rd,rf)
base = 1 - (rs / (lis + rs))
exponent = rd - rf * lis / rs
value = exponent * (LOG2(base)/LOG2(2))
- IF value < security_level_lb OR value > SECURITY_LEVEL
+ IF value < security_level_lb OR value > SECURITY_LEVEL THEN
RETURN FALSE
END IF
END IF
@@ -2744,7 +2749,6 @@ END FUNCTION
exceeded, or if the size is implausible for the given operation.
</t>
<!-- CORRECT -->
- <!-- BUGTRACKER -->
<t>
It needs to be checked that that the offset (message field "OFFSET")
for every received <em><xref target="messages_ibf" format="title" /></em> message
@@ -2768,7 +2772,6 @@ END FUNCTION
phase should be ensured.
</t>
<!-- CORRECT -->
- <!-- BUGTRACKER -->
<t>
To verify that all IBFs have been received a simple validation can be made
the number of buckets in the <em><xref target="messages_ibf_last" format="title" /></em> message
