Repository: randombit/botan
Pull request #3196 (2023-01-19 17:13:13)

Add an FFI-friendly interface for ZFEC encoding and decoding
Relates to #3190 

codecov-commenter: # [Codecov](https://codecov.io/gh/randombit/botan/pull/3196?src=pr&el=h1&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=Jack+Lloyd) Report
Base: **88.08**% // Head: **88.09**% // Increases project coverage by **`+0.00%`** :tada:
> Coverage data is based on head [(`342e254`)](https://codecov.io/gh/randombit/botan/pull/3196?src=pr&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=Jack+Lloyd) compared to base [(`70153f5`)](https://codecov.io/gh/randombit/botan/commit/70153f522c113a4be6b91960823b02832d33aad7?el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=Jack+Lloyd).
> Patch coverage: 100.00% of modified lines in pull request are covered.

> :exclamation: Current head 342e254 differs from pull request most recent head ca9b221. Consider uploading reports for the commit ca9b221 to get more accurate results

<details><summary>Additional details and impacted files</summary>


```diff
@@           Coverage Diff            @@
##           master    #3196    +/-   ##
========================================
  Coverage   88.08%   88.09%            
========================================
  Files         604      605     +1     
  Lines       67329    67437   +108     
  Branches     6735     6750    +15     
========================================
+ Hits        59310    59406    +96     
- Misses       5202     5210     +8     
- Partials     2817     2821     +4     
```


| [Impacted Files](https://codecov.io/gh/randombit/botan/pull/3196?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=Jack+Lloyd) | Coverage Δ | |
|---|---|---|
| [src/lib/ffi/ffi\_zfec.cpp](https://codecov.io/gh/randombit/botan/pull/3196?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=Jack+Lloyd#diff-c3JjL2xpYi9mZmkvZmZpX3pmZWMuY3Bw) | `100.00% <100.00%> (ø)` | |
| [src/tests/test\_ffi.cpp](https://codecov.io/gh/randombit/botan/pull/3196?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=Jack+Lloyd#diff-c3JjL3Rlc3RzL3Rlc3RfZmZpLmNwcA==) | `96.38% <100.00%> (+0.05%)` | :arrow_up: |
| [src/tests/tests.h](https://codecov.io/gh/randombit/botan/pull/3196?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=Jack+Lloyd#diff-c3JjL3Rlc3RzL3Rlc3RzLmg=) | `56.25% <0.00%> (-43.75%)` | :arrow_down: |
| [src/tests/test\_rng.h](https://codecov.io/gh/randombit/botan/pull/3196?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=Jack+Lloyd#diff-c3JjL3Rlc3RzL3Rlc3Rfcm5nLmg=) | `0.00% <0.00%> (-13.52%)` | :arrow_down: |
| [src/lib/pk\_pad/emsa\_raw/emsa\_raw.cpp](https://codecov.io/gh/randombit/botan/pull/3196?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=Jack+Lloyd#diff-c3JjL2xpYi9wa19wYWQvZW1zYV9yYXcvZW1zYV9yYXcuY3Bw) | `54.54% <0.00%> (-6.07%)` | :arrow_down: |
| [src/fuzzer/barrett.cpp](https://codecov.io/gh/randombit/botan/pull/3196?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=Jack+Lloyd#diff-c3JjL2Z1enplci9iYXJyZXR0LmNwcA==) | `66.66% <0.00%> (-5.56%)` | :arrow_down: |
| [src/fuzzer/uri.cpp](https://codecov.io/gh/randombit/botan/pull/3196?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=Jack+Lloyd#diff-c3JjL2Z1enplci91cmkuY3Bw) | `75.00% <0.00%> (-5.00%)` | :arrow_down: |
| [src/cli/speed.cpp](https://codecov.io/gh/randombit/botan/pull/3196?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=Jack+Lloyd#diff-c3JjL2NsaS9zcGVlZC5jcHA=) | `90.32% <0.00%> (-0.50%)` | :arrow_down: |
| [src/fuzzer/mode\_padding.cpp](https://codecov.io/gh/randombit/botan/pull/3196?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=Jack+Lloyd#diff-c3JjL2Z1enplci9tb2RlX3BhZGRpbmcuY3Bw) | `90.90% <0.00%> (-0.32%)` | :arrow_down: |
| [src/cli/cli.h](https://codecov.io/gh/randombit/botan/pull/3196?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=Jack+Lloyd#diff-c3JjL2NsaS9jbGkuaA==) | `100.00% <0.00%> (ø)` | |
| ... and [15 more](https://codecov.io/gh/randombit/botan/pull/3196?src=pr&el=tree-more&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=Jack+Lloyd) | |

Help us with your feedback. Take ten seconds to tell us [how you rate us](https://about.codecov.io/nps?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=Jack+Lloyd). Have a feature suggestion? [Share it here.](https://app.codecov.io/gh/feedback/?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=Jack+Lloyd)

</details>

[:umbrella: View full report at Codecov](https://codecov.io/gh/randombit/botan/pull/3196?src=pr&el=continue&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=Jack+Lloyd).   
:loudspeaker: Do you have feedback about the report comment? [Let us know in this issue](https://about.codecov.io/codecov-pr-comment-feedback/?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=Jack+Lloyd).

exarkun: @randombit I think this is ready for another look.  Thanks!
randombit: @exarkun Great! I'll review asap. One immediate comment: please rebase and remove the merge commit.

Patch:
diff --git a/src/lib/ffi/ffi.h b/src/lib/ffi/ffi.h
index 0d84c2072..08fb2f7eb 100644
--- a/src/lib/ffi/ffi.h
+++ b/src/lib/ffi/ffi.h
@@ -15,7 +15,7 @@ extern "C" {
 
 /*
 This header exports some of botan's functionality via a C89 interface. This API
-is uesd by the Python, OCaml, Rust and Ruby bindings via those languages
+is uesd by the Python, OCaml, Rust, Ruby, and Haskell bindings via those languages
 respective ctypes/FFI libraries.
 
 The API is intended to be as easy as possible to call from other
@@ -1637,14 +1637,14 @@ BOTAN_PUBLIC_API(2,13) int botan_x509_crl_load(botan_x509_crl_t* crl_obj, const
 BOTAN_PUBLIC_API(2,13) int botan_x509_crl_destroy(botan_x509_crl_t crl);
 
 /**
- * Given a CRL and a certificate, 
+ * Given a CRL and a certificate,
  * check if the certificate is revoked on that particular CRL
  */
 BOTAN_PUBLIC_API(2,13) int botan_x509_is_revoked(botan_x509_crl_t crl, botan_x509_cert_t cert);
 
 /**
  * Different flavor of `botan_x509_cert_verify`, supports revocation lists.
- * CRLs are passed as an array, same as intermediates and trusted CAs 
+ * CRLs are passed as an array, same as intermediates and trusted CAs
  */
 BOTAN_PUBLIC_API(2,13) int botan_x509_cert_verify_with_crl(
    int* validation_result,
@@ -1884,6 +1884,48 @@ int botan_srp6_client_agree(const char *username, const char *password,
                             uint8_t A[], size_t *A_len, uint8_t K[],
                             size_t *K_len);
 
+/**
+ * ZFEC
+ */
+
+/**
+ * Encode some bytes with certain ZFEC parameters.
+ *
+ * @param K the number of shares needed for recovery
+ * @param N the number of shares generated
+ * @param input the data to FEC
+ * @param size the length in bytes of input
+ *
+ * @param outputs An out parameter pointing to a fully allocated array of size
+ *                [N][size / K].  For all n in range, an encoded block will be
+ *                written to the memory starting at outputs[n][0].
+ *
+ * @return 0 on success, negative on failure
+ */
+BOTAN_PUBLIC_API(3, 0)
+int botan_zfec_encode(size_t K, size_t N, const uint8_t *input, size_t size, uint8_t **outputs);
+
+/**
+ * Decode some previously encoded shares using certain ZFEC parameters.
+ *
+ * @param K the number of shares needed for recovery
+ * @param N the total number of shares
+ *
+ * @param indexes The index into the encoder's outputs for the corresponding
+ *                element of the inputs array.
+ *
+ * @param inputs K previously encoded shares to decode
+ * @param shareSize the length in bytes of each input
+ *
+ * @param outputs An out parameter pointing to a fully allocated array of size
+ *                [K][shareSize].  For all k in range, a decoded block will
+ *                written to the memory starting at outputs[k][0].
+ *
+ * @return 0 on success, negative on failure
+ */
+BOTAN_PUBLIC_API(3, 0)
+int botan_zfec_decode(size_t K, size_t N, const size_t *indexes, uint8_t *const*const inputs, size_t shareSize, uint8_t **outputs);
+
 #ifdef __cplusplus
 }
 #endif
diff --git a/src/lib/ffi/ffi_zfec.cpp b/src/lib/ffi/ffi_zfec.cpp
new file mode 100644
index 000000000..aecc33fd1
--- /dev/null
+++ b/src/lib/ffi/ffi_zfec.cpp
@@ -0,0 +1,44 @@
+/*
+* (C) 2023 Least Authority TFA GmbH
+*
+* Botan is released under the Simplified BSD License (see license.txt)
+*/
+
+#include <botan/ffi.h>
+#include <botan/internal/ffi_util.h>
+
+#if defined(BOTAN_HAS_ZFEC)
+#include <botan/zfec.h>
+#endif
+
+extern "C" {
+  int botan_zfec_encode(size_t K, size_t N, const uint8_t *input, size_t size, uint8_t** outputs) {
+#if defined(BOTAN_HAS_ZFEC)
+    return Botan_FFI::ffi_guard_thunk(__func__, [=]() -> int {
+      Botan::ZFEC(K, N).encode(input, size, [=](size_t index, const uint8_t block[], size_t blockSize) -> void {
+	  std::copy(block, block + blockSize, outputs[index]);
+	});
+      return BOTAN_FFI_SUCCESS;
+    });
+#else
+    return BOTAN_FFI_ERROR_NOT_IMPLEMENTED;
+#endif
+  }
+
+  int botan_zfec_decode(size_t K, size_t N, const size_t *indexes, uint8_t *const*const inputs, size_t shareSize, uint8_t **outputs) {
+#if defined(BOTAN_HAS_ZFEC)
+    return Botan_FFI::ffi_guard_thunk(__func__, [=]() -> int {
+      std::map<size_t, const uint8_t*> shares;
+      for (size_t k = 0; k < K; ++k) {
+	shares.insert(std::pair<size_t, const uint8_t*>(indexes[k], inputs[k]));
+      }
+      Botan::ZFEC(K, N).decode_shares(shares, shareSize, [=](size_t index, const uint8_t block[], size_t blockSize) -> void {
+	  std::copy(block, block + blockSize, outputs[index]);
+	});
+      return BOTAN_FFI_SUCCESS;
+    });
+#else
+    return BOTAN_FFI_ERROR_NOT_IMPLEMENTED;
+#endif
+  }
+}
diff --git a/src/python/botan3.py b/src/python/botan3.py
index 44c349704..bca8d2ea7 100755
--- a/src/python/botan3.py
+++ b/src/python/botan3.py
@@ -19,7 +19,7 @@ introduced in Botan 3.0.0
 """
 
 from ctypes import CDLL, POINTER, byref, create_string_buffer, \
-    c_void_p, c_size_t, c_uint8, c_uint32, c_uint64, c_int, c_uint, c_char_p
+    c_void_p, c_size_t, c_uint8, c_uint32, c_uint64, c_int, c_uint, c_char_p, addressof
 
 from sys import platform
 from time import strptime, mktime, time as system_time
@@ -443,6 +443,12 @@ def _set_prototypes(dll):
             [c_char_p, c_char_p, c_char_p, c_char_p, c_char_p, c_size_t, c_char_p, c_size_t, c_void_p,
              c_char_p, POINTER(c_size_t), c_char_p, POINTER(c_size_t)])
 
+    # ZFEC
+    ffi_api(dll.botan_zfec_encode,
+            [c_size_t, c_size_t, c_char_p, c_size_t, POINTER(c_char_p)])
+    ffi_api(dll.botan_zfec_decode,
+            [c_size_t, c_size_t, POINTER(c_size_t), POINTER(c_char_p), c_size_t, POINTER(c_char_p)])
+
     return dll
 
 #
@@ -1825,3 +1831,80 @@ def srp6_client_agree(username, password, group, hsh, salt, b, rng):
                                                                     rng.handle_(),
                                                                     a, al,
                                                                     k, kl))
+
+def zfec_encode(k, n, input_bytes):
+    """
+    ZFEC-encode an input message according to the given parameters
+
+    :param int k: the number of shares required to recover the original
+    :param int n: the total number of shares
+    :param bytes input_bytes: the input message, in bytes
+
+    :returns: n arrays of bytes, each one containing a single share
+    """
+    input_size = len(input_bytes)
+    # note: the C++ code checks that input_bytes is a multiple of k
+    outsize = input_size // k
+    p_p_nbytes = c_char_p * n
+
+    # allocate memory for the outputs (create_string_buffer makes bytes)
+    outputs = [
+        create_string_buffer(outsize)
+        for a in range(n)
+    ]
+
+    c_outputs = p_p_nbytes(*[
+        addressof(output)
+        for output in outputs
+    ])
+
+    # actual C call
+    _DLL.botan_zfec_encode(
+        c_size_t(k), c_size_t(n), input_bytes, c_size_t(input_size), c_outputs
+    )
+    return [output.raw for output in outputs]
+
+
+def zfec_decode(k, n, indexes, inputs):
+    """
+    ZFEC decode
+
+    :param int k: the number of shares required to recover the original
+    :param int n: the total number of shares
+    :param list[int] indexes: which of the shares are we giving the decoder
+    :param list[bytes] inputs: the input shares (e.g. from a previous
+        call to zfec_encode) which all must be the same length
+
+    :returns: a list of bytes containing the original shares decoded
+        from the provided shares (in `inputs`)
+    """
+
+    p_size_t = c_size_t * len(indexes)
+    c_indexes = p_size_t(*[c_size_t(index) for index in indexes])
+    p_p_nbytes = c_char_p * n
+    c_inputs = p_p_nbytes(*[c_char_p(inp) for inp in inputs])
+    # all inputs must be the same length
+    share_size = len(inputs[0])
+    for i in inputs:
+        if len(i) != share_size:
+            raise ValueError(
+                "Share size mismatch: {} != {}".format(len(i), share_size)
+            )
+
+    # allocate memory for our outputs (create_string_buffer creates
+    # bytes)
+    outputs = [
+        create_string_buffer(share_size)
+        for _ in range(k)
+    ]
+    p_p_kbytes = c_char_p * k
+    c_outputs = p_p_kbytes(*[
+        addressof(output)
+        for output in outputs
+    ])
+
+    # actual C call
+    _DLL.botan_zfec_decode(
+        c_size_t(k), c_size_t(n), c_indexes, c_inputs, c_size_t(share_size), c_outputs
+    )
+    return [output.raw for output in outputs]


Test patch:
diff --git a/src/scripts/test_python.py b/src/scripts/test_python.py
index 9d307938d..e5d85ca28 100644
--- a/src/scripts/test_python.py
+++ b/src/scripts/test_python.py
@@ -12,6 +12,7 @@ import os
 import platform
 import argparse
 import sys
+from itertools import permutations
 
 # Starting with Python 3.8 DLL search locations are more restricted on Windows.
 # Hence, we need to explicitly add the current working directory before trying
@@ -718,6 +719,67 @@ ofvkP1EDmpx50fHLawIDAQAB
         key_s = server.step2(a)
         self.assertEqual(key_c, key_s)
 
+
+class BotanPythonZfecTests(unittest.TestCase):
+    """
+    Tests relating to the ZFEC bindings
+    """
+
+    def test_encode(self):
+        """
+        Simple encoder test.
+
+        Could benefit from more variations
+        """
+        n = 3
+        k = 2
+        input_bytes = b"abcdefgh" + b"ijklmnop"
+        output_shares = botan.zfec_encode(k, n, input_bytes)
+        self.assertEqual(
+            output_shares,
+            [b'abcdefgh', b'ijklmnop', b'qrstuvwX']
+        )
+
+    def test_encode_decode(self):
+        """
+        Simple round-trip tests.
+        """
+        def byte_iter():
+            b = 0
+            while True:
+                yield bytes([b])
+                b = (b + 1) % 256
+
+        random_bytes = byte_iter()
+
+        for k in range(1, 5):
+            for n in range(k, k + 5):
+                for x in range(128, 256, 5):
+                    input_bytes = b"".join([
+                        next(random_bytes)
+                        for _ in range(x * k)
+                    ])
+                    with self.subTest("encode_decode variant", n=n, k=k, size=x):
+                        self._encode_decode_test(n, k, input_bytes)
+
+    def _encode_decode_test(self, n, k, input_bytes):
+        """
+        one instance of a round-trip test
+        """
+        output_shares = botan.zfec_encode(k, n, input_bytes)
+        # want to check that every permutation of the inputs decodes to the
+        # correct input bytes
+
+        for inputs in permutations(enumerate(output_shares), k):
+            # "unzip" the enumerated permutation
+            indexes, shares = zip(*inputs)
+            decoded = botan.zfec_decode(k, n, indexes, shares)
+            self.assertEqual(
+                b"".join(decoded),
+                input_bytes
+            )
+
+
 def main():
     parser = argparse.ArgumentParser()
     parser.add_argument('--test-data-dir', default='.')
diff --git a/src/tests/test_ffi.cpp b/src/tests/test_ffi.cpp
index 9b478af92..067c22200 100644
--- a/src/tests/test_ffi.cpp
+++ b/src/tests/test_ffi.cpp
@@ -62,6 +62,7 @@ class FFI_Unit_Tests final : public Test
          results.push_back(ffi_test_pkcs_hash_id());
          results.push_back(ffi_test_cert_validation());
          results.push_back(ffi_test_crl());
+         results.push_back(ffi_test_zfec());
 
 #if defined(BOTAN_HAS_AES)
          results.push_back(ffi_test_block_ciphers());
@@ -325,6 +326,97 @@ class FFI_Unit_Tests final : public Test
          return result;
          }
 
+      static Test::Result ffi_test_zfec()
+         {
+         Test::Result result("FFI ZFEC");
+
+#if defined(BOTAN_HAS_ZFEC)
+         /* exercise a simple success case
+          */
+
+         // Select some arbitrary, valid encoding parameters.  There is
+         // nothing special about them but some relationships between these
+         // values and other inputs must hold.
+         const size_t K = 3;
+         const size_t N = 11;
+
+         // The decoder needs to know the indexes of the blocks being passed
+         // in to it.  This array must equal [0..N) for the logic in the
+         // decoding loop below to hold.
+         const std::vector<size_t> indexes = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
+
+         // This will be the size of each encoded (or decoded) block.  This is
+         // an arbitrary value but it must match up with the length of the
+         // test data given in `input`.
+         const size_t blockSize = 15;
+
+         // K of the blocks are required so the total information represented
+         // can be this multiple.  totalSize must be a multiple of K and it
+         // always will be using this construction.
+         const size_t totalSize = blockSize * K;
+
+         // Here's the complete original input (plus a trailing NUL that we
+         // won't pass through ZFEC).  These are arbitrary bytes.
+         const uint8_t input[totalSize + 1] = "Does this work?AAAAAAAAAAAAAAAzzzzzzzzzzzzzzz";
+
+         // Allocate memory for the encoding and decoding output parameters.
+         std::vector<uint8_t*> encoded(N);
+         std::vector<uint8_t*> decoded(K);
+         for (size_t n = 0; n < N; ++n) {
+            encoded[n] = new uint8_t[blockSize];
+         };
+         for (size_t k = 0; k < K; ++k) {
+            decoded[k] = new uint8_t[blockSize];
+         };
+
+         // First encode the complete input string into N blocks where K are
+         // required for reconstruction.  The N encoded blocks will end up in
+         // `encoded`.
+         REQUIRE_FFI_OK(botan_zfec_encode, (K, N, input, totalSize, encoded.data()));
+
+         // Any K blocks can be decoded to reproduce the original input (split
+         // across an array of K strings of blockSize bytes each).  This loop
+         // only exercises decoding with consecutive blocks because it's
+         // harder to pick non-consecutive blocks out for a test.
+         for (size_t offset = 0; offset < N - K; ++offset) {
+            result.test_note("About to decode with offset " + std::to_string(offset));
+            // Pass in the K shares starting from `offset` (and their indexes)
+            // so that we can try decoding a certain group of blocks here.  Any
+            // K shares *should* work.
+            REQUIRE_FFI_OK(botan_zfec_decode, (K, N, indexes.data() + offset, encoded.data() + offset, blockSize, decoded.data()));
+
+            // Check that the original input bytes have been written to the
+            // output parameter.
+            for (size_t k = 0, pos = 0; k < K; ++k, pos += blockSize) {
+               TEST_FFI_RC(0, botan_same_mem, (input + pos, decoded[k], blockSize));
+            }
+         }
+
+         // Clean up the memory we allocated at the top.
+         for (size_t n = 0; n < N; ++n) {
+            delete[] encoded[n];
+         }
+         for (size_t k = 0; k < K; ++k) {
+            delete[] decoded[k];
+         }
+
+         /* Exercise a couple basic failure cases, such as you encounter if
+          * the caller supplies invalid parameters.  We don't try to
+          * exhaustively prove invalid parameters are handled through this
+          * interface since the implementation only passes them through to
+          * ZFEC::{encode,decode} where the real checking is.  We just want to
+          * see that errors can propagate.
+          */
+         TEST_FFI_FAIL("encode with out-of-bounds encoding parameters should have failed",
+                       botan_zfec_encode,
+                       (0, 0, NULL, 0, NULL));
+         TEST_FFI_FAIL("decode with out-of-bounds encoding parameters should have failed",
+                       botan_zfec_decode,
+                       (0, 0, NULL, NULL, 0, NULL));
+#endif
+
+         return result;
+         }
 
       static Test::Result ffi_test_crl()
          {