Merge "Add hadamard utilities to encode keys"
diff --git a/rebootescrow/aidl/default/Android.bp b/rebootescrow/aidl/default/Android.bp
new file mode 100644
index 0000000..eb228ad
--- /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 0000000..5853d2d
--- /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 0000000..21cfc78
--- /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 0000000..e397e76
--- /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);
+}