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