From a0a12cfcf216c7ba3ee43ec86e81e708a8db2519 Mon Sep 17 00:00:00 2001 From: Tianjie Xu Date: Thu, 5 Dec 2019 21:50:22 -0800 Subject: 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 --- rebootescrow/aidl/default/Android.bp | 47 +++++++ rebootescrow/aidl/default/HadamardUtils.cpp | 157 ++++++++++++++++++++++++ rebootescrow/aidl/default/HadamardUtils.h | 62 ++++++++++ rebootescrow/aidl/default/HadamardUtilsTest.cpp | 126 +++++++++++++++++++ 4 files changed, 392 insertions(+) create mode 100644 rebootescrow/aidl/default/Android.bp create mode 100644 rebootescrow/aidl/default/HadamardUtils.cpp create mode 100644 rebootescrow/aidl/default/HadamardUtils.h create mode 100644 rebootescrow/aidl/default/HadamardUtilsTest.cpp (limited to 'rebootescrow') 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 + +#include + +namespace aidl { +namespace android { +namespace hardware { +namespace rebootescrow { +namespace hadamard { + +constexpr auto BYTE_LENGTH = 8u; + +std::vector BitsetToBytes(const std::bitset& encoded_bits) { + CHECK_EQ(0, (encoded_bits.size() % BYTE_LENGTH)); + std::vector 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 BytesToBitset(const std::vector& encoded) { + CHECK_EQ(ENCODE_LENGTH, encoded.size() * BYTE_LENGTH); + + std::bitset 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 EncodeWord(uint16_t word) { + std::bitset 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 EncodeKey(const std::vector& key) { + CHECK_EQ(KEY_SIZE_IN_BYTES, key.size()); + + std::vector result; + for (size_t i = 0; i < key.size(); i += 2) { + uint16_t word = static_cast(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 DecodeKey(const std::vector& encoded) { + CHECK_EQ(0, (encoded.size() * 8) % ENCODE_LENGTH); + std::vector result; + for (size_t i = 0; i < encoded.size(); i += ENCODE_LENGTH / 8) { + auto current = + std::vector{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> DecodeWord( + const std::bitset& encoded) { + std::vector 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> 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 + +#include +#include +#include +#include + +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 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> DecodeWord( + const std::bitset& 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 EncodeKey(const std::vector& input); + +// Given a byte array representation of the encoded keys, decodes it and return the result. +std::vector DecodeKey(const std::vector& encoded); + +// Converts a bitset of length |ENCODE_LENGTH| to a byte array. +std::vector BitsetToBytes(const std::bitset& encoded_bits); + +// Converts a byte array of encoded words back to the bitset. +std::bitset BytesToBitset(const std::vector& 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 +#include + +#include +#include +#include + +#include + +#include + +using namespace aidl::android::hardware::rebootescrow::hadamard; + +class HadamardTest : public testing::Test { + protected: + void SetUp() override { + auto ones = std::bitset{}.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 expected_one_; + std::bitset expected_half_size_; +}; + +static void AddError(std::bitset* 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& key) { + auto encoded = EncodeKey(key); + ASSERT_EQ(64 * 1024, encoded.size()); + auto decoded = DecodeKey(encoded); + ASSERT_EQ(key, std::vector(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{ENCODE_LENGTH, half_size_}; + ASSERT_EQ(expected, candidate.top()); + + candidate = DecodeWord(expected_one_); + expected = std::pair{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 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 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 key; + for (uint8_t i = 0; i < KEY_SIZE_IN_BYTES; i++) { + key.push_back(i); + }; + EncodeAndDecodeKeys(key); +} -- cgit v1.2.3