xref: /aosp_15_r20/hardware/interfaces/rebootescrow/aidl/default/HadamardUtils.cpp (revision 4d7e907c777eeecc4c5bd7cf640a754fac206ff7)
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