Add hadamard utilities to encode keys

Add the utility functions to encode & decode 32 bytes keys. The
hadamard encoding will expand a 2 bytes word to 2^15 bits. And thus the
32 byte key will expand to 64KiB in space. The encoded value is more
robust and we will be able to recover the key even if there is some
corruption.

Test: unittest pass
Change-Id: Iae8a28a8c7c1699f8641f9250f0eccde5c2ff138

4 files changed, 392 insertions, 0 deletions

diff --git a/rebootescrow/aidl/default/Android.bp b/rebootescrow/aidl/default/Android.bp
new file mode 100644
index 0000000000..eb228ad827
--- /dev/null
+++ b/rebootescrow/aidl/default/Android.bp
@@ -0,0 +1,47 @@
+//
+// Copyright (C) 2019 The Android Open Source Project
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//      http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+//
+
+cc_library_static {
+    name: "libhadamardutils",
+    vendor_available: true,
+    host_supported: true,
+    shared_libs: [
+        "libbase",
+    ],
+    srcs: [
+        "HadamardUtils.cpp",
+    ],
+    visibility: [
+        ":__subpackages__",
+    ],
+}
+
+cc_test {
+    name: "HadamardUtilsTest",
+    host_supported: true,
+    srcs: [
+        "HadamardUtilsTest.cpp",
+    ],
+    static_libs: [
+        "libhadamardutils",
+        "libgtest_prod",
+    ],
+    shared_libs: [
+        "liblog",
+        "libbase",
+    ],
+    test_suites: ["device-tests"],
+}
diff --git a/rebootescrow/aidl/default/HadamardUtils.cpp b/rebootescrow/aidl/default/HadamardUtils.cpp
new file mode 100644
index 0000000000..5853d2def5
--- /dev/null
+++ b/rebootescrow/aidl/default/HadamardUtils.cpp
@@ -0,0 +1,157 @@
+/*
+ * Copyright (C) 2019 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#include <HadamardUtils.h>
+
+#include <android-base/logging.h>
+
+namespace aidl {
+namespace android {
+namespace hardware {
+namespace rebootescrow {
+namespace hadamard {
+
+constexpr auto BYTE_LENGTH = 8u;
+
+std::vector<uint8_t> BitsetToBytes(const std::bitset<ENCODE_LENGTH>& encoded_bits) {
+    CHECK_EQ(0, (encoded_bits.size() % BYTE_LENGTH));
+    std::vector<uint8_t> result;
+    for (size_t i = 0; i < encoded_bits.size(); i += 8) {
+        uint8_t current = 0;
+        // Set each byte starting from the LSB.
+        for (size_t j = 0; j < BYTE_LENGTH; j++) {
+            CHECK_LE(i + j, encoded_bits.size());
+            if (encoded_bits[i + j]) {
+                current |= (1u << j);
+            }
+        }
+        result.push_back(current);
+    }
+    return result;
+}
+
+std::bitset<ENCODE_LENGTH> BytesToBitset(const std::vector<uint8_t>& encoded) {
+    CHECK_EQ(ENCODE_LENGTH, encoded.size() * BYTE_LENGTH);
+
+    std::bitset<ENCODE_LENGTH> result;
+    size_t offset = 0;
+    for (const auto& byte : encoded) {
+        // Set each byte starting from the LSB.
+        for (size_t j = 0; j < BYTE_LENGTH; j++) {
+            result[offset + j] = byte & (1u << j);
+        }
+        offset += BYTE_LENGTH;
+    }
+    return result;
+}
+
+// The encoding is equivalent to multiply the word with the generator matrix (and take the module
+// of 2). Here is an example of encoding a number with 3 bits. The encoded length is thus
+// 2^(3-1) = 4 bits.
+//              |1 1 1 1|     |0|
+//  |0 1 1|  *  |0 0 1 1|  =  |1|
+//              |0 1 0 1|     |1|
+//                            |0|
+std::bitset<ENCODE_LENGTH> EncodeWord(uint16_t word) {
+    std::bitset<ENCODE_LENGTH> result;
+    for (uint64_t i = ENCODE_LENGTH; i < 2 * ENCODE_LENGTH; i++) {
+        uint32_t wi = word & i;
+        // Sum all the bits in the word and check its parity.
+        wi ^= wi >> 8u;
+        wi ^= wi >> 4u;
+        wi ^= wi >> 2u;
+        wi ^= wi >> 1u;
+        result[i - ENCODE_LENGTH] = wi & 1u;
+    }
+    return result;
+}
+
+std::vector<uint8_t> EncodeKey(const std::vector<uint8_t>& key) {
+    CHECK_EQ(KEY_SIZE_IN_BYTES, key.size());
+
+    std::vector<uint8_t> result;
+    for (size_t i = 0; i < key.size(); i += 2) {
+        uint16_t word = static_cast<uint16_t>(key[i + 1]) << BYTE_LENGTH | key[i];
+        auto encoded_bits = EncodeWord(word);
+        auto byte_array = BitsetToBytes(encoded_bits);
+        std::move(byte_array.begin(), byte_array.end(), std::back_inserter(result));
+    }
+    return result;
+}
+
+std::vector<uint8_t> DecodeKey(const std::vector<uint8_t>& encoded) {
+    CHECK_EQ(0, (encoded.size() * 8) % ENCODE_LENGTH);
+    std::vector<uint8_t> result;
+    for (size_t i = 0; i < encoded.size(); i += ENCODE_LENGTH / 8) {
+        auto current =
+                std::vector<uint8_t>{encoded.begin() + i, encoded.begin() + i + ENCODE_LENGTH / 8};
+        auto bits = BytesToBitset(current);
+        auto candidates = DecodeWord(bits);
+        CHECK(!candidates.empty());
+        // TODO(xunchang) Do we want to try other candidates?
+        uint16_t val = candidates.top().second;
+        result.push_back(val & 0xffu);
+        result.push_back(val >> BYTE_LENGTH);
+    }
+
+    return result;
+}
+
+std::priority_queue<std::pair<int32_t, uint16_t>> DecodeWord(
+        const std::bitset<ENCODE_LENGTH>& encoded) {
+    std::vector<int32_t> scores;
+    scores.reserve(ENCODE_LENGTH);
+    // Convert 0 -> -1 in the encoded bits. e.g [0, 1, 1, 0] -> [-1, 1, 1, -1]
+    for (uint32_t i = 0; i < ENCODE_LENGTH; i++) {
+        scores.push_back(2 * encoded[i] - 1);
+    }
+
+    // Multiply the hadamard matrix by the transformed input.
+    // |1  1  1  1|     |-1|     | 0|
+    // |1 -1  1 -1|  *  | 1|  =  | 0|
+    // |1  1 -1 -1|     | 1|     | 0|
+    // |1 -1 -1  1|     |-1|     |-4|
+    for (uint32_t i = 0; i < CODE_K; i++) {
+        uint16_t step = 1u << i;
+        for (uint32_t j = 0; j < ENCODE_LENGTH; j += 2 * step) {
+            for (uint32_t k = j; k < j + step; k++) {
+                auto a0 = scores[k];
+                auto a1 = scores[k + step];
+                scores[k] = a0 + a1;
+                scores[k + step] = a0 - a1;
+            }
+        }
+    }
+
+    // Assign the corresponding score to each index; larger score indicates higher probability. e.g.
+    // value 3, encoding [0, 1, 1, 0] -> score: 4
+    // value 7, encoding [1, 0, 0, 1] (3's complement) -> score: -4
+    std::priority_queue<std::pair<int32_t, uint16_t>> candidates;
+    // TODO(xunchang) limit the candidate size since we don't need all of them?
+    for (uint32_t i = 0; i < scores.size(); i++) {
+        candidates.emplace(-scores[i], i);
+        candidates.emplace(scores[i], (1u << CODE_K) | i);
+    }
+
+    CHECK_EQ(2 * ENCODE_LENGTH, candidates.size());
+    return candidates;
+}
+
+}  // namespace hadamard
+}  // namespace rebootescrow
+}  // namespace hardware
+}  // namespace android
+}  // namespace aidl
diff --git a/rebootescrow/aidl/default/HadamardUtils.h b/rebootescrow/aidl/default/HadamardUtils.h
new file mode 100644
index 0000000000..21cfc787e3
--- /dev/null
+++ b/rebootescrow/aidl/default/HadamardUtils.h
@@ -0,0 +1,62 @@
+/*
+ * Copyright (C) 2019 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#pragma once
+
+#include <stdint.h>
+
+#include <bitset>
+#include <queue>
+#include <utility>
+#include <vector>
+
+namespace aidl {
+namespace android {
+namespace hardware {
+namespace rebootescrow {
+namespace hadamard {
+
+constexpr uint32_t CODE_K = 15;
+constexpr uint32_t ENCODE_LENGTH = 1u << CODE_K;
+constexpr auto KEY_SIZE_IN_BYTES = 32u;
+
+// Encodes a 2 bytes word with hadamard code. The encoding expands a word of k+1 bits to a 2^k
+// bitset. Returns the encoded bitset.
+std::bitset<ENCODE_LENGTH> EncodeWord(uint16_t word);
+
+// Decodes the input bitset, and returns a sorted list of pair with (score, value). The value with
+// a higher score indicates a greater likehood.
+std::priority_queue<std::pair<int32_t, uint16_t>> DecodeWord(
+        const std::bitset<ENCODE_LENGTH>& encoded);
+
+// Encodes a key that has a size of KEY_SIZE_IN_BYTES. Returns a byte array representation of the
+// encoded bitset. So a 32 bytes key will expand to 16*(2^15) bits = 64KiB.
+std::vector<uint8_t> EncodeKey(const std::vector<uint8_t>& input);
+
+// Given a byte array representation of the encoded keys, decodes it and return the result.
+std::vector<uint8_t> DecodeKey(const std::vector<uint8_t>& encoded);
+
+// Converts a bitset of length |ENCODE_LENGTH| to a byte array.
+std::vector<uint8_t> BitsetToBytes(const std::bitset<ENCODE_LENGTH>& encoded_bits);
+
+// Converts a byte array of encoded words back to the bitset.
+std::bitset<ENCODE_LENGTH> BytesToBitset(const std::vector<uint8_t>& encoded);
+
+}  // namespace hadamard
+}  // namespace rebootescrow
+}  // namespace hardware
+}  // namespace android
+}  // namespace aidl
diff --git a/rebootescrow/aidl/default/HadamardUtilsTest.cpp b/rebootescrow/aidl/default/HadamardUtilsTest.cpp
new file mode 100644
index 0000000000..e397e7624e
--- /dev/null
+++ b/rebootescrow/aidl/default/HadamardUtilsTest.cpp
@@ -0,0 +1,126 @@
+/*
+ * Copyright (C) 2019 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#include <stdint.h>
+#include <random>
+
+#include <bitset>
+#include <utility>
+#include <vector>
+
+#include <gtest/gtest.h>
+
+#include <HadamardUtils.h>
+
+using namespace aidl::android::hardware::rebootescrow::hadamard;
+
+class HadamardTest : public testing::Test {
+  protected:
+    void SetUp() override {
+        auto ones = std::bitset<ENCODE_LENGTH>{}.set();
+        // Expects 0x4000 to encode as top half as ones, and lower half as zeros. i.e.
+        // [1, 1 .. 1, 0, 0 .. 0]
+        expected_half_size_ = ones << half_size_;
+
+        // Expects 0x1 to encode as interleaved 1 and 0s  i.e. [1, 0, 1, 0 ..]
+        expected_one_ = ones;
+        for (uint32_t i = ENCODE_LENGTH / 2; i >= 1; i /= 2) {
+            expected_one_ ^= (expected_one_ >> i);
+        }
+    }
+
+    uint16_t half_size_ = ENCODE_LENGTH / 2;
+    std::bitset<ENCODE_LENGTH> expected_one_;
+    std::bitset<ENCODE_LENGTH> expected_half_size_;
+};
+
+static void AddError(std::bitset<ENCODE_LENGTH>* corrupted_bits) {
+    // The hadamard code has a hamming distance of ENCODE_LENGTH/2. So we should always be able to
+    // correct the data if less than a quarter of the encoded bits are corrupted.
+    auto corrupted_max = 0.24f * corrupted_bits->size();
+    auto corrupted_num = 0;
+    for (size_t i = 0; i < corrupted_bits->size() && corrupted_num < corrupted_max; i++) {
+        if (random() % 2 == 0) {
+            (*corrupted_bits)[i] = !(*corrupted_bits)[i];
+            corrupted_num += 1;
+        }
+    }
+}
+
+static void EncodeAndDecodeKeys(const std::vector<uint8_t>& key) {
+    auto encoded = EncodeKey(key);
+    ASSERT_EQ(64 * 1024, encoded.size());
+    auto decoded = DecodeKey(encoded);
+    ASSERT_EQ(key, std::vector<uint8_t>(decoded.begin(), decoded.begin() + key.size()));
+}
+
+TEST_F(HadamardTest, Encode_smoke) {
+    ASSERT_EQ(expected_half_size_, EncodeWord(half_size_));
+    ASSERT_EQ(expected_one_, EncodeWord(1));
+    // Check the complement of 1.
+    ASSERT_EQ(~expected_one_, EncodeWord(1u << CODE_K | 1u));
+}
+
+TEST_F(HadamardTest, Decode_smoke) {
+    auto candidate = DecodeWord(expected_half_size_);
+    auto expected = std::pair<int32_t, uint16_t>{ENCODE_LENGTH, half_size_};
+    ASSERT_EQ(expected, candidate.top());
+
+    candidate = DecodeWord(expected_one_);
+    expected = std::pair<int32_t, uint16_t>{ENCODE_LENGTH, 1};
+    ASSERT_EQ(expected, candidate.top());
+}
+
+TEST_F(HadamardTest, Decode_error_correction) {
+    constexpr auto iteration = 10;
+    for (int i = 0; i < iteration; i++) {
+        uint16_t word = random() % (ENCODE_LENGTH * 2);
+        auto corrupted_bits = EncodeWord(word);
+        AddError(&corrupted_bits);
+
+        auto candidate = DecodeWord(corrupted_bits);
+        ASSERT_EQ(word, candidate.top().second);
+    }
+}
+
+TEST_F(HadamardTest, BytesToBitset_smoke) {
+    auto bytes = BitsetToBytes(expected_one_);
+
+    auto read_back = BytesToBitset(bytes);
+    ASSERT_EQ(expected_one_, read_back);
+}
+
+TEST_F(HadamardTest, EncodeAndDecodeKey) {
+    std::vector<uint8_t> KEY_1{
+            0xA5, 0x00, 0xFF, 0x01, 0xA5, 0x5a, 0xAA, 0x55, 0x00, 0xD3, 0x2A,
+            0x8C, 0x2E, 0x83, 0x0E, 0x65, 0x9E, 0x8D, 0xC6, 0xAC, 0x1E, 0x83,
+            0x21, 0xB3, 0x95, 0x02, 0x89, 0x64, 0x64, 0x92, 0x12, 0x1F,
+    };
+    std::vector<uint8_t> KEY_2{
+            0xFF, 0x00, 0x00, 0xAA, 0x5A, 0x19, 0x20, 0x71, 0x9F, 0xFB, 0xDA,
+            0xB6, 0x2D, 0x06, 0xD5, 0x49, 0x7E, 0xEF, 0x63, 0xAC, 0x18, 0xFF,
+            0x5A, 0xA3, 0x40, 0xBB, 0x64, 0xFA, 0x67, 0xC1, 0x10, 0x18,
+    };
+
+    EncodeAndDecodeKeys(KEY_1);
+    EncodeAndDecodeKeys(KEY_2);
+
+    std::vector<uint8_t> key;
+    for (uint8_t i = 0; i < KEY_SIZE_IN_BYTES; i++) {
+        key.push_back(i);
+    };
+    EncodeAndDecodeKeys(key);
+}