diff options
author | Elias Summermatter <elias.summermatter@seccom.ch> | 2021-06-16 10:22:35 +0200 |
---|---|---|
committer | Elias Summermatter <elias.summermatter@seccom.ch> | 2021-06-16 10:22:35 +0200 |
commit | 3217f39e11167ccf51517996642001c9ef3ce3af (patch) | |
tree | 86632f5ae4c5cedd45a47ed08a2c965eebb7ee17 | |
parent | cc73546624d723535ac90fe2e293a7e08b2c1fc6 (diff) | |
download | lsd0003-3217f39e11167ccf51517996642001c9ef3ce3af.tar.gz lsd0003-3217f39e11167ccf51517996642001c9ef3ce3af.zip |
Resolved some pseudocode inconsistencies
-rw-r--r-- | .gitignore | 4 | ||||
-rw-r--r-- | draft-summermatter-set-union.pdf | bin | 516646 -> 0 bytes | |||
-rw-r--r-- | draft-summermatter-set-union.xml | 85 |
3 files changed, 47 insertions, 42 deletions
@@ -1,4 +1,6 @@ | |||
1 | /.idea/ | 1 | /.idea/ |
2 | *.xml.swp | 2 | *.xml.swp |
3 | *.html | 3 | *.html |
4 | *.min.js \ No newline at end of file | 4 | *.min.js |
5 | |||
6 | *.txt \ No newline at end of file | ||
diff --git a/draft-summermatter-set-union.pdf b/draft-summermatter-set-union.pdf deleted file mode 100644 index 22b0a80..0000000 --- a/draft-summermatter-set-union.pdf +++ /dev/null | |||
Binary files differ | |||
diff --git a/draft-summermatter-set-union.xml b/draft-summermatter-set-union.xml index 95f94a2..10a5ce0 100644 --- a/draft-summermatter-set-union.xml +++ b/draft-summermatter-set-union.xml | |||
@@ -409,6 +409,7 @@ FUNCTION salt_key(key,ibf_salt): | |||
409 | s = (ibf_salt * 7) modulo 64; | 409 | s = (ibf_salt * 7) modulo 64; |
410 | /* rotate key */ | 410 | /* rotate key */ |
411 | return (key >> s) | (key << (64 - s)) | 411 | return (key >> s) | (key << (64 - s)) |
412 | END FUNCTION | ||
412 | 413 | ||
413 | 414 | ||
414 | # INPUTS: | 415 | # INPUTS: |
@@ -422,6 +423,7 @@ FUNCTION id_calculation (element,ibf_salt): | |||
422 | PRF=HMAC-SHA256 | 423 | PRF=HMAC-SHA256 |
423 | key = HKDF(XTR, PRF, kdf_salt, element) modulo 2^64 | 424 | key = HKDF(XTR, PRF, kdf_salt, element) modulo 2^64 |
424 | return salt_key(key, ibf_salt) | 425 | return salt_key(key, ibf_salt) |
426 | END FUNCTION | ||
425 | ]]></artwork> | 427 | ]]></artwork> |
426 | </figure> | 428 | </figure> |
427 | </section> | 429 | </section> |
@@ -465,27 +467,28 @@ FUNCTION get_bucket_id (key, k, L) | |||
465 | bucket = CRC32(key) | 467 | bucket = CRC32(key) |
466 | i = 0 // unsigned 32-bit index | 468 | i = 0 // unsigned 32-bit index |
467 | filled = 0 | 469 | filled = 0 |
468 | WHILE filled < k | 470 | WHILE filled < k DO |
469 | 471 | ||
470 | element_already_in_bucket = false | 472 | element_already_in_bucket = false |
471 | j = 0 | 473 | j = 0 |
472 | WHILE j < filled | 474 | WHILE j < filled DO |
473 | IF dst[j] == bucket modulo L THEN | 475 | IF dst[j] == bucket modulo L THEN |
474 | element_already_in_bucket = true | 476 | element_already_in_bucket = true |
475 | ENDIF | 477 | END IF |
476 | j++ | 478 | j++ |
477 | ENDWHILE | 479 | END WHILE |
478 | 480 | ||
479 | IF !element_already_in_bucket THEN | 481 | IF !element_already_in_bucket THEN |
480 | dst[filled] = bucket modulo L | 482 | dst[filled] = bucket modulo L |
481 | filled = filled + 1 | 483 | filled = filled + 1 |
482 | ENDIF | 484 | END IF |
483 | 485 | ||
484 | x = (bucket << 32) | i // 64 bit result | 486 | x = (bucket << 32) | i // 64 bit result |
485 | bucket = CRC32(x) | 487 | bucket = CRC32(x) |
486 | i = i + 1 | 488 | i = i + 1 |
487 | ENDWHILE | 489 | END WHILE |
488 | return dst | 490 | return dst |
491 | END FUNCTION | ||
489 | ]]></artwork> | 492 | ]]></artwork> |
490 | </figure> | 493 | </figure> |
491 | </section> | 494 | </section> |
@@ -2066,10 +2069,10 @@ FUNCTION decide_operation_mode(avg_es, | |||
2066 | # this check at the beginning the logic below | 2069 | # this check at the beginning the logic below |
2067 | # should always yield the same result for these | 2070 | # should always yield the same result for these |
2068 | # extreme cases, allowing us to omit this code. | 2071 | # extreme cases, allowing us to omit this code. |
2069 | IF (0 == rss) | 2072 | IF 0 == rss THEN |
2070 | RETURN FULL_SYNC_LOCAL_SENDING_FIRST | 2073 | RETURN FULL_SYNC_LOCAL_SENDING_FIRST |
2071 | END IF | 2074 | END IF |
2072 | IF (0 == lss) | 2075 | IF 0 == lss THEN |
2073 | RETURN FULL_SYNC_REMOTE_SENDING_FIRST | 2076 | RETURN FULL_SYNC_REMOTE_SENDING_FIRST |
2074 | END IF | 2077 | END IF |
2075 | 2078 | ||
@@ -2095,7 +2098,7 @@ FUNCTION decide_operation_mode(avg_es, | |||
2095 | 2098 | ||
2096 | # Estimate messages required to transfer IBF | 2099 | # Estimate messages required to transfer IBF |
2097 | ibf_bucket_count = estimated_total_diff * IBF_BUCKET_NUMBER_FACTOR | 2100 | ibf_bucket_count = estimated_total_diff * IBF_BUCKET_NUMBER_FACTOR |
2098 | IF (ibf_bucket_count <= IBF_MIN_SIZE) | 2101 | IF ibf_bucket_count <= IBF_MIN_SIZE THEN |
2099 | ibf_bucket_count = IBF_MIN_SIZE | 2102 | ibf_bucket_count = IBF_MIN_SIZE |
2100 | END IF | 2103 | END IF |
2101 | ibf_message_count = ceil (ibf_bucket_count / MAX_BUCKETS_PER_MESSAGE) | 2104 | ibf_message_count = ceil (ibf_bucket_count / MAX_BUCKETS_PER_MESSAGE) |
@@ -2135,8 +2138,8 @@ FUNCTION decide_operation_mode(avg_es, | |||
2135 | # Decide for a optimal mode of operation | 2138 | # Decide for a optimal mode of operation |
2136 | full_cost_min = MIN (cost_local_full_sync, | 2139 | full_cost_min = MIN (cost_local_full_sync, |
2137 | cost_remote_full_sync) | 2140 | cost_remote_full_sync) |
2138 | IF (full_cost_min < diff_cost) | 2141 | IF full_cost_min < diff_cost THEN |
2139 | IF (cost_remote_full_sync > cost_local_full_sync) | 2142 | IF cost_remote_full_sync > cost_local_full_sync THEN |
2140 | RETURN FULL_SYNC_LOCAL_SENDING_FIRST | 2143 | RETURN FULL_SYNC_LOCAL_SENDING_FIRST |
2141 | ELSE | 2144 | ELSE |
2142 | RETURN FULL_SYNC_REMOTE_SENDING_FIRST | 2145 | RETURN FULL_SYNC_REMOTE_SENDING_FIRST |
@@ -2144,6 +2147,7 @@ FUNCTION decide_operation_mode(avg_es, | |||
2144 | ELSE | 2147 | ELSE |
2145 | RETURN DIFFERENTIAL_SYNC | 2148 | RETURN DIFFERENTIAL_SYNC |
2146 | END IF | 2149 | END IF |
2150 | END FUNCTION | ||
2147 | ]]></artwork> | 2151 | ]]></artwork> |
2148 | </figure> | 2152 | </figure> |
2149 | </section> | 2153 | </section> |
@@ -2172,8 +2176,8 @@ FUNCTION initial_ibf_size(sd) | |||
2172 | # basically always be below one MTU, so there is | 2176 | # basically always be below one MTU, so there is |
2173 | # little to be gained, while a smaller IBF would | 2177 | # little to be gained, while a smaller IBF would |
2174 | # increase the chance of a decoding failure. | 2178 | # increase the chance of a decoding failure. |
2175 | return MAX(37, IBF_BUCKET_NUMBER_FACTOR * sd); | 2179 | RETURN MAX(37, IBF_BUCKET_NUMBER_FACTOR * sd); |
2176 | FUNCTION END | 2180 | END FUNCTION |
2177 | 2181 | ||
2178 | # CONSTANTS: | 2182 | # CONSTANTS: |
2179 | # IBF_BUCKET_NUMBER_FACTOR = 2: The amount the IBF gets increased if decoding fails | 2183 | # 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) | |||
2187 | next_size = IBF_BUCKET_NUMBER_FACTOR * (lis - de) | 2191 | next_size = IBF_BUCKET_NUMBER_FACTOR * (lis - de) |
2188 | # The MAX operation here also ensures that the | 2192 | # The MAX operation here also ensures that the |
2189 | # result is positive. | 2193 | # result is positive. |
2190 | return MAX(37, next_size); | 2194 | RETURN MAX(37, next_size); |
2191 | FUNCTION END | 2195 | END FUNCTION |
2192 | ]]></artwork> | 2196 | ]]></artwork> |
2193 | </figure> | 2197 | </figure> |
2194 | </section> | 2198 | </section> |
@@ -2244,13 +2248,14 @@ FUNCTION END | |||
2244 | 2248 | ||
2245 | FUNCTION ibf_get_max_counter(ibf) | 2249 | FUNCTION ibf_get_max_counter(ibf) |
2246 | max_counter=1 # convince static analysis that we never take log2(0) | 2250 | max_counter=1 # convince static analysis that we never take log2(0) |
2247 | FOR bucket IN ibf | 2251 | FOR bucket IN ibf DO |
2248 | IF bucket.counter > max_counter | 2252 | IF bucket.counter > max_counter THEN |
2249 | max_counter = bucket.counter | 2253 | max_counter = bucket.counter |
2250 | END IF | 2254 | END IF |
2251 | END FOR | 2255 | END FOR |
2252 | # next bigger discrete number of the binary logarithm of the max counter | 2256 | # next bigger discrete number of the binary logarithm of the max counter |
2253 | RETURN CEILING( log2 ( max_counter ) ) | 2257 | RETURN CEILING( LOG2( max_counter ) ) |
2258 | END FUNCTION | ||
2254 | 2259 | ||
2255 | # INPUTS: | 2260 | # INPUTS: |
2256 | # ibf: The IBF | 2261 | # ibf: The IBF |
@@ -2275,14 +2280,14 @@ FUNCTION pack_counter(ibf, offset, count) | |||
2275 | byte_ctr = 0 | 2280 | byte_ctr = 0 |
2276 | buffer=[] | 2281 | buffer=[] |
2277 | 2282 | ||
2278 | FOR bucket IN ibf[offset] to ibf[count] | 2283 | FOR bucket IN ibf[offset] TO ibf[count] DO |
2279 | counter = bucket.counter | 2284 | counter = bucket.counter |
2280 | byte_len = counter_bytes | 2285 | byte_len = counter_bytes |
2281 | 2286 | ||
2282 | WHILE byte_len + store_bits < 8 | 2287 | WHILE byte_len + store_bits < 8 DO |
2283 | bit_to_shift = 0 | 2288 | bit_to_shift = 0 |
2284 | 2289 | ||
2285 | IF store_bits > 0 OR byte_len > 8 | 2290 | IF store_bits > 0 OR byte_len > 8 THEN |
2286 | bit_free = 8 - store_bits | 2291 | bit_free = 8 - store_bits |
2287 | bit_to_shift = byte_len - bit_free | 2292 | bit_to_shift = byte_len - bit_free |
2288 | store = store << bit_free | 2293 | store = store << bit_free |
@@ -2300,7 +2305,7 @@ FUNCTION pack_counter(ibf, offset, count) | |||
2300 | END FOR | 2305 | END FOR |
2301 | 2306 | ||
2302 | # Write the last partial packed byte to the buffer | 2307 | # Write the last partial packed byte to the buffer |
2303 | IF store_bits > 0 | 2308 | IF store_bits > 0 THEN |
2304 | buffer[byte_ctr] = store << (8 - store_bits) | 2309 | buffer[byte_ctr] = store << (8 - store_bits) |
2305 | byte_ctr = byte_ctr + 1 | 2310 | byte_ctr = byte_ctr + 1 |
2306 | END IF | 2311 | END IF |
@@ -2331,17 +2336,17 @@ FUNCTION unpack_counter(ibf, offset, count, cbl, pd) | |||
2331 | bit_to_pack_left = 8 | 2336 | bit_to_pack_left = 8 |
2332 | byte_ctr++ | 2337 | byte_ctr++ |
2333 | 2338 | ||
2334 | WHILE bit_to_pack_left >= 0 | 2339 | WHILE bit_to_pack_left >= 0 DO |
2335 | 2340 | ||
2336 | # Prevent packet from reading more than required | 2341 | # Prevent packet from reading more than required |
2337 | IF ibf_bucket_ctr > (count - 1) | 2342 | IF ibf_bucket_ctr > (count - 1) THEN |
2338 | RETURN | 2343 | RETURN |
2339 | END IF | 2344 | END IF |
2340 | 2345 | ||
2341 | IF store_bits + bit_to_pack_left >= cbl | 2346 | IF store_bits + bit_to_pack_left >= cbl THEN |
2342 | bit_use = cbl - store_bits | 2347 | bit_use = cbl - store_bits |
2343 | 2348 | ||
2344 | IF store_bits > 0 | 2349 | IF store_bits > 0 THEN |
2345 | store = store << bit_use | 2350 | store = store << bit_use |
2346 | END IF | 2351 | END IF |
2347 | bytes_to_shift = bit_to_pack_left - bit_use | 2352 | bytes_to_shift = bit_to_pack_left - bit_use |
@@ -2357,7 +2362,7 @@ FUNCTION unpack_counter(ibf, offset, count, cbl, pd) | |||
2357 | ELSE | 2362 | ELSE |
2358 | store_bits = store_bits + bit_to_pack_left | 2363 | store_bits = store_bits + bit_to_pack_left |
2359 | 2364 | ||
2360 | IF 0 == store_bits | 2365 | IF 0 == store_bits THEN |
2361 | store = byte_to_read | 2366 | store = byte_to_read |
2362 | ELSE | 2367 | ELSE |
2363 | store = store << bit_to_pack_left | 2368 | store = store << bit_to_pack_left |
@@ -2410,7 +2415,7 @@ END FUNCTION | |||
2410 | 2415 | ||
2411 | FUNCTION se_key_salting(value, salt) | 2416 | FUNCTION se_key_salting(value, salt) |
2412 | s = (salt * 7) modulo 64 | 2417 | s = (salt * 7) modulo 64 |
2413 | return (value >> s) | (value << (64 - s)) | 2418 | RETURN (value >> s) | (value << (64 - s)) |
2414 | END FUNCTION | 2419 | END FUNCTION |
2415 | 2420 | ||
2416 | ]]></artwork> | 2421 | ]]></artwork> |
@@ -2481,17 +2486,17 @@ END FUNCTION | |||
2481 | # Output: | 2486 | # Output: |
2482 | # returns TRUE if parameters in byzantine bounds otherwise returns FALSE | 2487 | # returns TRUE if parameters in byzantine bounds otherwise returns FALSE |
2483 | FUNCTION check_byzantine_bounds (rec,rsd,lec,lsd) | 2488 | FUNCTION check_byzantine_bounds (rec,rsd,lec,lsd) |
2484 | IF rec + rsd > UPPER_BOUND | 2489 | IF rec + rsd > UPPER_BOUND THEN |
2485 | RETURN FALSE | 2490 | RETURN FALSE |
2486 | IF END | 2491 | END IF |
2487 | IF lec + lsd > UPPER_BOUND | 2492 | IF lec + lsd > UPPER_BOUND THEN |
2488 | RETURN FALSE | 2493 | RETURN FALSE |
2489 | IF END | 2494 | END IF |
2490 | IF rec < LOWER_BOUND | 2495 | IF rec < LOWER_BOUND THEN |
2491 | RETURN FALSE | 2496 | RETURN FALSE |
2492 | IF END | 2497 | END IF |
2493 | RETURN TRUE | 2498 | RETURN TRUE |
2494 | FUNCTION END | 2499 | END FUNCTION |
2495 | ]]></artwork> | 2500 | ]]></artwork> |
2496 | </figure> | 2501 | </figure> |
2497 | </section> | 2502 | </section> |
@@ -2631,16 +2636,16 @@ FUNCTION full_sync_plausibility_check (state,rs,lis,rd,rf) | |||
2631 | 2636 | ||
2632 | # Make sure that no element is received double when | 2637 | # Make sure that no element is received double when |
2633 | # all elements already are transmitted to the oder side. | 2638 | # all elements already are transmitted to the oder side. |
2634 | IF FULL_SENDING == state AND rd > 0 | 2639 | IF FULL_SENDING == state AND rd > 0 THEN |
2635 | RETURN FALSE | 2640 | RETURN FALSE |
2636 | END IF | 2641 | END IF |
2637 | 2642 | ||
2638 | # Probabilistic algorithm to check for plausible | 2643 | # Probabilistic algorithm to check for plausible |
2639 | # element distribution | 2644 | # element distribution |
2640 | IF FULL_RECEIVING == state | 2645 | IF FULL_RECEIVING == state THEN |
2641 | 2646 | ||
2642 | # Prevent division by 0 | 2647 | # Prevent division by 0 |
2643 | IF 0 <= rs | 2648 | IF 0 <= rs THEN |
2644 | rs = 1 | 2649 | rs = 1 |
2645 | END IF | 2650 | END IF |
2646 | 2651 | ||
@@ -2648,7 +2653,7 @@ FUNCTION full_sync_plausibility_check (state,rs,lis,rd,rf) | |||
2648 | base = 1 - (rs / (lis + rs)) | 2653 | base = 1 - (rs / (lis + rs)) |
2649 | exponent = rd - rf * lis / rs | 2654 | exponent = rd - rf * lis / rs |
2650 | value = exponent * (LOG2(base)/LOG2(2)) | 2655 | value = exponent * (LOG2(base)/LOG2(2)) |
2651 | IF value < security_level_lb OR value > SECURITY_LEVEL | 2656 | IF value < security_level_lb OR value > SECURITY_LEVEL THEN |
2652 | RETURN FALSE | 2657 | RETURN FALSE |
2653 | END IF | 2658 | END IF |
2654 | END IF | 2659 | END IF |
@@ -2744,7 +2749,6 @@ END FUNCTION | |||
2744 | exceeded, or if the size is implausible for the given operation. | 2749 | exceeded, or if the size is implausible for the given operation. |
2745 | </t> | 2750 | </t> |
2746 | <!-- CORRECT --> | 2751 | <!-- CORRECT --> |
2747 | <!-- BUGTRACKER --> | ||
2748 | <t> | 2752 | <t> |
2749 | It needs to be checked that that the offset (message field "OFFSET") | 2753 | It needs to be checked that that the offset (message field "OFFSET") |
2750 | for every received <em><xref target="messages_ibf" format="title" /></em> message | 2754 | for every received <em><xref target="messages_ibf" format="title" /></em> message |
@@ -2768,7 +2772,6 @@ END FUNCTION | |||
2768 | phase should be ensured. | 2772 | phase should be ensured. |
2769 | </t> | 2773 | </t> |
2770 | <!-- CORRECT --> | 2774 | <!-- CORRECT --> |
2771 | <!-- BUGTRACKER --> | ||
2772 | <t> | 2775 | <t> |
2773 | To verify that all IBFs have been received a simple validation can be made | 2776 | To verify that all IBFs have been received a simple validation can be made |
2774 | the number of buckets in the <em><xref target="messages_ibf_last" format="title" /></em> message | 2777 | the number of buckets in the <em><xref target="messages_ibf_last" format="title" /></em> message |