1*4d7e907cSAndroid Build Coastguard Worker /*
2*4d7e907cSAndroid Build Coastguard Worker * Copyright (C) 2019 The Android Open Source Project
3*4d7e907cSAndroid Build Coastguard Worker *
4*4d7e907cSAndroid Build Coastguard Worker * Licensed under the Apache License, Version 2.0 (the "License");
5*4d7e907cSAndroid Build Coastguard Worker * you may not use this file except in compliance with the License.
6*4d7e907cSAndroid Build Coastguard Worker * You may obtain a copy of the License at
7*4d7e907cSAndroid Build Coastguard Worker *
8*4d7e907cSAndroid Build Coastguard Worker * http://www.apache.org/licenses/LICENSE-2.0
9*4d7e907cSAndroid Build Coastguard Worker *
10*4d7e907cSAndroid Build Coastguard Worker * Unless required by applicable law or agreed to in writing, software
11*4d7e907cSAndroid Build Coastguard Worker * distributed under the License is distributed on an "AS IS" BASIS,
12*4d7e907cSAndroid Build Coastguard Worker * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13*4d7e907cSAndroid Build Coastguard Worker * See the License for the specific language governing permissions and
14*4d7e907cSAndroid Build Coastguard Worker * limitations under the License.
15*4d7e907cSAndroid Build Coastguard Worker */
16*4d7e907cSAndroid Build Coastguard Worker
17*4d7e907cSAndroid Build Coastguard Worker #include <HadamardUtils.h>
18*4d7e907cSAndroid Build Coastguard Worker
19*4d7e907cSAndroid Build Coastguard Worker #include <android-base/logging.h>
20*4d7e907cSAndroid Build Coastguard Worker
21*4d7e907cSAndroid Build Coastguard Worker namespace aidl {
22*4d7e907cSAndroid Build Coastguard Worker namespace android {
23*4d7e907cSAndroid Build Coastguard Worker namespace hardware {
24*4d7e907cSAndroid Build Coastguard Worker namespace rebootescrow {
25*4d7e907cSAndroid Build Coastguard Worker namespace hadamard {
26*4d7e907cSAndroid Build Coastguard Worker
read_bit(const std::vector<uint8_t> & input,size_t bit)27*4d7e907cSAndroid Build Coastguard Worker static inline uint8_t read_bit(const std::vector<uint8_t>& input, size_t bit) {
28*4d7e907cSAndroid Build Coastguard Worker return (input[bit >> 3] >> (bit & 7)) & 1u;
29*4d7e907cSAndroid Build Coastguard Worker }
30*4d7e907cSAndroid Build Coastguard Worker
31*4d7e907cSAndroid Build Coastguard Worker // Use a simple LCG which is easy to run in reverse.
32*4d7e907cSAndroid Build Coastguard Worker // https://www.johndcook.com/blog/2017/07/05/simple-random-number-generator/
33*4d7e907cSAndroid Build Coastguard Worker constexpr uint64_t RNG_MODULUS = 0x7fffffff;
34*4d7e907cSAndroid Build Coastguard Worker constexpr uint64_t RNG_MUL = 742938285;
35*4d7e907cSAndroid Build Coastguard Worker constexpr uint64_t RNG_SEED = 20170705;
36*4d7e907cSAndroid Build Coastguard Worker constexpr uint64_t RNG_INV_MUL = 1413043504; // (mul * inv_mul) % modulus == 1
37*4d7e907cSAndroid Build Coastguard Worker constexpr uint64_t RNG_INV_SEED = 1173538311; // (seed * mul**65534) % modulus
38*4d7e907cSAndroid Build Coastguard Worker
39*4d7e907cSAndroid Build Coastguard Worker // Apply an error correcting encoding.
40*4d7e907cSAndroid Build Coastguard Worker //
41*4d7e907cSAndroid Build Coastguard Worker // The error correcting code used is an augmented Hadamard code with
42*4d7e907cSAndroid Build Coastguard Worker // k=15, so it takes a 16-bit input and produces a 2^15-bit output.
43*4d7e907cSAndroid Build Coastguard Worker // We break the 32-byte key into 16 16-bit codewords and encode
44*4d7e907cSAndroid Build Coastguard Worker // each codeword to a 2^15-bit output.
45*4d7e907cSAndroid Build Coastguard Worker //
46*4d7e907cSAndroid Build Coastguard Worker // To better defend against clustered errors, we stripe together the encoded
47*4d7e907cSAndroid Build Coastguard Worker // codewords. Thus if a single 512-byte DRAM line is lost, instead of losing
48*4d7e907cSAndroid Build Coastguard Worker // 2^11 bits from the encoding of a single code word, we lose 2^7 bits
49*4d7e907cSAndroid Build Coastguard Worker // from the encoding of each of the 16 codewords.
50*4d7e907cSAndroid Build Coastguard Worker // In addition we apply a Fisher-Yates shuffle to the bytes of the encoding;
51*4d7e907cSAndroid Build Coastguard Worker // Hadamard encoding recovers much better from random errors than systematic
52*4d7e907cSAndroid Build Coastguard Worker // ones, and this ensures that errors will be random.
EncodeKey(const std::vector<uint8_t> & input)53*4d7e907cSAndroid Build Coastguard Worker std::vector<uint8_t> EncodeKey(const std::vector<uint8_t>& input) {
54*4d7e907cSAndroid Build Coastguard Worker CHECK_EQ(input.size(), KEY_SIZE_IN_BYTES);
55*4d7e907cSAndroid Build Coastguard Worker std::vector<uint8_t> result(OUTPUT_SIZE_BYTES, 0);
56*4d7e907cSAndroid Build Coastguard Worker static_assert(OUTPUT_SIZE_BYTES == 64 * 1024);
57*4d7e907cSAndroid Build Coastguard Worker // Transpose the key so that each row contains one bit from each codeword
58*4d7e907cSAndroid Build Coastguard Worker uint16_t wordmatrix[CODEWORD_BITS];
59*4d7e907cSAndroid Build Coastguard Worker for (size_t i = 0; i < CODEWORD_BITS; i++) {
60*4d7e907cSAndroid Build Coastguard Worker uint16_t word = 0;
61*4d7e907cSAndroid Build Coastguard Worker for (size_t j = 0; j < KEY_CODEWORDS; j++) {
62*4d7e907cSAndroid Build Coastguard Worker word |= read_bit(input, i + j * CODEWORD_BITS) << j;
63*4d7e907cSAndroid Build Coastguard Worker }
64*4d7e907cSAndroid Build Coastguard Worker wordmatrix[i] = word;
65*4d7e907cSAndroid Build Coastguard Worker }
66*4d7e907cSAndroid Build Coastguard Worker // Fill in the encodings in Gray code order for speed.
67*4d7e907cSAndroid Build Coastguard Worker uint16_t val = wordmatrix[CODEWORD_BITS - 1];
68*4d7e907cSAndroid Build Coastguard Worker size_t ix = 0;
69*4d7e907cSAndroid Build Coastguard Worker for (size_t i = 0; i < ENCODE_LENGTH; i++) {
70*4d7e907cSAndroid Build Coastguard Worker for (size_t b = 0; b < CODEWORD_BITS; b++) {
71*4d7e907cSAndroid Build Coastguard Worker if (i & (1 << b)) {
72*4d7e907cSAndroid Build Coastguard Worker ix ^= (1 << b);
73*4d7e907cSAndroid Build Coastguard Worker val ^= wordmatrix[b];
74*4d7e907cSAndroid Build Coastguard Worker break;
75*4d7e907cSAndroid Build Coastguard Worker }
76*4d7e907cSAndroid Build Coastguard Worker }
77*4d7e907cSAndroid Build Coastguard Worker result[ix * KEY_CODEWORD_BYTES] = val & 0xffu;
78*4d7e907cSAndroid Build Coastguard Worker result[ix * KEY_CODEWORD_BYTES + 1] = val >> 8u;
79*4d7e907cSAndroid Build Coastguard Worker }
80*4d7e907cSAndroid Build Coastguard Worker // Apply the inverse shuffle here; we apply the forward shuffle in decoding.
81*4d7e907cSAndroid Build Coastguard Worker uint64_t rng_state = RNG_INV_SEED;
82*4d7e907cSAndroid Build Coastguard Worker for (size_t i = OUTPUT_SIZE_BYTES - 1; i > 0; i--) {
83*4d7e907cSAndroid Build Coastguard Worker auto j = rng_state % (i + 1);
84*4d7e907cSAndroid Build Coastguard Worker auto t = result[i];
85*4d7e907cSAndroid Build Coastguard Worker result[i] = result[j];
86*4d7e907cSAndroid Build Coastguard Worker result[j] = t;
87*4d7e907cSAndroid Build Coastguard Worker rng_state *= RNG_INV_MUL;
88*4d7e907cSAndroid Build Coastguard Worker rng_state %= RNG_MODULUS;
89*4d7e907cSAndroid Build Coastguard Worker }
90*4d7e907cSAndroid Build Coastguard Worker return result;
91*4d7e907cSAndroid Build Coastguard Worker }
92*4d7e907cSAndroid Build Coastguard Worker
93*4d7e907cSAndroid Build Coastguard Worker // Constant-time conditional copy, to fix b/146520538
94*4d7e907cSAndroid Build Coastguard Worker // ctl must be 0 or 1; we do the copy if it's 1.
CondCopy(uint32_t ctl,void * dest,const void * src,size_t len)95*4d7e907cSAndroid Build Coastguard Worker static void CondCopy(uint32_t ctl, void* dest, const void* src, size_t len) {
96*4d7e907cSAndroid Build Coastguard Worker const auto cdest = reinterpret_cast<uint8_t*>(dest);
97*4d7e907cSAndroid Build Coastguard Worker const auto csrc = reinterpret_cast<const uint8_t*>(src);
98*4d7e907cSAndroid Build Coastguard Worker for (size_t i = 0; i < len; i++) {
99*4d7e907cSAndroid Build Coastguard Worker const uint32_t d = cdest[i];
100*4d7e907cSAndroid Build Coastguard Worker const uint32_t s = csrc[i];
101*4d7e907cSAndroid Build Coastguard Worker cdest[i] = d ^ (-ctl & (s ^ d));
102*4d7e907cSAndroid Build Coastguard Worker }
103*4d7e907cSAndroid Build Coastguard Worker }
104*4d7e907cSAndroid Build Coastguard Worker
105*4d7e907cSAndroid Build Coastguard Worker struct CodewordWinner {
106*4d7e907cSAndroid Build Coastguard Worker uint16_t codeword;
107*4d7e907cSAndroid Build Coastguard Worker int32_t score;
108*4d7e907cSAndroid Build Coastguard Worker };
109*4d7e907cSAndroid Build Coastguard Worker
110*4d7e907cSAndroid Build Coastguard Worker // Replace dest with src if it has a higher score
CopyWinner(CodewordWinner * dest,const CodewordWinner & src)111*4d7e907cSAndroid Build Coastguard Worker static void CopyWinner(CodewordWinner* dest, const CodewordWinner& src) {
112*4d7e907cSAndroid Build Coastguard Worker // Scores are between - 2^15 and 2^15, so taking the difference won't
113*4d7e907cSAndroid Build Coastguard Worker // overflow; we use the sign bit of the difference here.
114*4d7e907cSAndroid Build Coastguard Worker CondCopy(static_cast<uint32_t>(dest->score - src.score) >> 31, dest, &src,
115*4d7e907cSAndroid Build Coastguard Worker sizeof(CodewordWinner));
116*4d7e907cSAndroid Build Coastguard Worker }
117*4d7e907cSAndroid Build Coastguard Worker
118*4d7e907cSAndroid Build Coastguard Worker // Decode a single codeword. Because of the way codewords are striped together
119*4d7e907cSAndroid Build Coastguard Worker // this takes the entire input, plus an offset telling it which word to decode.
DecodeWord(size_t word,const std::vector<uint8_t> & encoded)120*4d7e907cSAndroid Build Coastguard Worker static uint16_t DecodeWord(size_t word, const std::vector<uint8_t>& encoded) {
121*4d7e907cSAndroid Build Coastguard Worker std::vector<int32_t> scores;
122*4d7e907cSAndroid Build Coastguard Worker scores.reserve(ENCODE_LENGTH);
123*4d7e907cSAndroid Build Coastguard Worker // Convert x -> -1^x in the encoded bits. e.g [1, 0, 0, 1] -> [-1, 1, 1, -1]
124*4d7e907cSAndroid Build Coastguard Worker for (uint32_t i = 0; i < ENCODE_LENGTH; i++) {
125*4d7e907cSAndroid Build Coastguard Worker scores.push_back(1 - 2 * read_bit(encoded, i * KEY_CODEWORDS + word));
126*4d7e907cSAndroid Build Coastguard Worker }
127*4d7e907cSAndroid Build Coastguard Worker
128*4d7e907cSAndroid Build Coastguard Worker // Multiply the hadamard matrix by the transformed input.
129*4d7e907cSAndroid Build Coastguard Worker // |1 1 1 1| |-1| | 0|
130*4d7e907cSAndroid Build Coastguard Worker // |1 -1 1 -1| * | 1| = | 0|
131*4d7e907cSAndroid Build Coastguard Worker // |1 1 -1 -1| | 1| | 0|
132*4d7e907cSAndroid Build Coastguard Worker // |1 -1 -1 1| |-1| |-4|
133*4d7e907cSAndroid Build Coastguard Worker for (uint32_t i = 0; i < CODE_K; i++) {
134*4d7e907cSAndroid Build Coastguard Worker uint16_t step = 1u << i;
135*4d7e907cSAndroid Build Coastguard Worker for (uint32_t j = 0; j < ENCODE_LENGTH; j += 2 * step) {
136*4d7e907cSAndroid Build Coastguard Worker for (uint32_t k = j; k < j + step; k++) {
137*4d7e907cSAndroid Build Coastguard Worker auto a0 = scores[k];
138*4d7e907cSAndroid Build Coastguard Worker auto a1 = scores[k + step];
139*4d7e907cSAndroid Build Coastguard Worker scores[k] = a0 + a1;
140*4d7e907cSAndroid Build Coastguard Worker scores[k + step] = a0 - a1;
141*4d7e907cSAndroid Build Coastguard Worker }
142*4d7e907cSAndroid Build Coastguard Worker }
143*4d7e907cSAndroid Build Coastguard Worker }
144*4d7e907cSAndroid Build Coastguard Worker // -ENCODE_LENGTH is least possible score, so start one less than that
145*4d7e907cSAndroid Build Coastguard Worker auto best = CodewordWinner{0, -static_cast<int32_t>(ENCODE_LENGTH + 1)};
146*4d7e907cSAndroid Build Coastguard Worker // For every possible codeword value, look at its score, and replace best if it's higher,
147*4d7e907cSAndroid Build Coastguard Worker // in constant time.
148*4d7e907cSAndroid Build Coastguard Worker for (size_t i = 0; i < ENCODE_LENGTH; i++) {
149*4d7e907cSAndroid Build Coastguard Worker CopyWinner(&best, CodewordWinner{static_cast<uint16_t>(i), scores[i]});
150*4d7e907cSAndroid Build Coastguard Worker CopyWinner(&best, CodewordWinner{static_cast<uint16_t>(i | (1 << CODE_K)), -scores[i]});
151*4d7e907cSAndroid Build Coastguard Worker }
152*4d7e907cSAndroid Build Coastguard Worker return best.codeword;
153*4d7e907cSAndroid Build Coastguard Worker }
154*4d7e907cSAndroid Build Coastguard Worker
DecodeKey(const std::vector<uint8_t> & shuffled)155*4d7e907cSAndroid Build Coastguard Worker std::vector<uint8_t> DecodeKey(const std::vector<uint8_t>& shuffled) {
156*4d7e907cSAndroid Build Coastguard Worker CHECK_EQ(OUTPUT_SIZE_BYTES, shuffled.size());
157*4d7e907cSAndroid Build Coastguard Worker // Apply the forward Fisher-Yates shuffle.
158*4d7e907cSAndroid Build Coastguard Worker std::vector<uint8_t> encoded(OUTPUT_SIZE_BYTES, 0);
159*4d7e907cSAndroid Build Coastguard Worker encoded[0] = shuffled[0];
160*4d7e907cSAndroid Build Coastguard Worker uint64_t rng_state = RNG_SEED;
161*4d7e907cSAndroid Build Coastguard Worker for (size_t i = 1; i < OUTPUT_SIZE_BYTES; i++) {
162*4d7e907cSAndroid Build Coastguard Worker auto j = rng_state % (i + 1);
163*4d7e907cSAndroid Build Coastguard Worker encoded[i] = encoded[j];
164*4d7e907cSAndroid Build Coastguard Worker encoded[j] = shuffled[i];
165*4d7e907cSAndroid Build Coastguard Worker rng_state *= RNG_MUL;
166*4d7e907cSAndroid Build Coastguard Worker rng_state %= RNG_MODULUS;
167*4d7e907cSAndroid Build Coastguard Worker }
168*4d7e907cSAndroid Build Coastguard Worker std::vector<uint8_t> result(KEY_SIZE_IN_BYTES, 0);
169*4d7e907cSAndroid Build Coastguard Worker for (size_t i = 0; i < KEY_CODEWORDS; i++) {
170*4d7e907cSAndroid Build Coastguard Worker uint16_t val = DecodeWord(i, encoded);
171*4d7e907cSAndroid Build Coastguard Worker result[i * CODEWORD_BYTES] = val & 0xffu;
172*4d7e907cSAndroid Build Coastguard Worker result[i * CODEWORD_BYTES + 1] = val >> 8u;
173*4d7e907cSAndroid Build Coastguard Worker }
174*4d7e907cSAndroid Build Coastguard Worker return result;
175*4d7e907cSAndroid Build Coastguard Worker }
176*4d7e907cSAndroid Build Coastguard Worker
177*4d7e907cSAndroid Build Coastguard Worker } // namespace hadamard
178*4d7e907cSAndroid Build Coastguard Worker } // namespace rebootescrow
179*4d7e907cSAndroid Build Coastguard Worker } // namespace hardware
180*4d7e907cSAndroid Build Coastguard Worker } // namespace android
181*4d7e907cSAndroid Build Coastguard Worker } // namespace aidl
182