1 /*
2 * Copyright (C) 2018 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 <stdlib.h>
18
19 #include <algorithm>
20 #include <memory>
21 #include <string>
22 #include <vector>
23
24 #include <gtest/gtest.h>
25 #include <openssl/evp.h>
26
27 #include "build_verity_tree_utils.h"
28 #include "verity/hash_tree_builder.h"
29
30 // The hex string we are using in build_image.py
31 // aee087a5be3b982978c923f566a94613496b417f2af592639bc80d141e34dfe7
32 constexpr unsigned char kSaltHex[] = {
33 0xae, 0xe0, 0x87, 0xa5, 0xbe, 0x3b, 0x98, 0x29, 0x78, 0xc9, 0x23,
34 0xf5, 0x66, 0xa9, 0x46, 0x13, 0x49, 0x6b, 0x41, 0x7f, 0x2a, 0xf5,
35 0x92, 0x63, 0x9b, 0xc8, 0x0d, 0x14, 0x1e, 0x34, 0xdf, 0xe7};
36
37 class BuildVerityTreeTest : public ::testing::Test {
38 protected:
SetUp()39 void SetUp() override {
40 salt_hex =
41 std::vector<unsigned char>(kSaltHex, kSaltHex + sizeof(kSaltHex));
42 builder.reset(new HashTreeBuilder(4096, EVP_sha256()));
43 }
44
zero_block_hash() const45 const std::vector<unsigned char>& zero_block_hash() const {
46 return builder->zero_block_hash_;
47 }
verity_tree() const48 const std::vector<std::vector<unsigned char>>& verity_tree() const {
49 return builder->verity_tree_;
50 }
51
GenerateHashTree(const std::vector<unsigned char> & data,const std::vector<unsigned char> & salt)52 void GenerateHashTree(const std::vector<unsigned char>& data,
53 const std::vector<unsigned char>& salt) {
54 ASSERT_TRUE(builder->Initialize(data.size(), salt));
55 ASSERT_TRUE(builder->Update(data.data(), data.size()));
56 ASSERT_TRUE(builder->BuildHashTree());
57 }
58
59 std::vector<unsigned char> salt_hex;
60 std::unique_ptr<HashTreeBuilder> builder;
61 };
62
TEST_F(BuildVerityTreeTest,CalculateSize)63 TEST_F(BuildVerityTreeTest, CalculateSize) {
64 // The hash of source data will occupy at least one block
65 ASSERT_EQ(4096u, builder->CalculateSize(1));
66 // Sha256 hash of 128 blocks fits into one block.
67 ASSERT_EQ(4096u, builder->CalculateSize(128 * 4096));
68 // Requires 3 blocks to hold more data.
69 ASSERT_EQ(12288u, builder->CalculateSize(128 * 4096 + 1));
70
71 ASSERT_EQ(20811776u, builder->CalculateSize(2641915904));
72 }
73
TEST_F(BuildVerityTreeTest,InitializeBuilder)74 TEST_F(BuildVerityTreeTest, InitializeBuilder) {
75 // data_size should be divisible by 4096
76 ASSERT_FALSE(builder->Initialize(4095, salt_hex));
77
78 ASSERT_TRUE(builder->Initialize(4096, salt_hex));
79 ASSERT_EQ(1u, verity_tree().size());
80 ASSERT_EQ("6eb8c4e1bce842d137f18b27beb857d3b43899d178090537ad7a0fbe3bf4126a",
81 HashTreeBuilder::BytesArrayToString(zero_block_hash()));
82 }
83
TEST_F(BuildVerityTreeTest,HashSingleBlock)84 TEST_F(BuildVerityTreeTest, HashSingleBlock) {
85 std::vector<unsigned char> data(4096, 1);
86
87 GenerateHashTree(data, salt_hex);
88
89 ASSERT_EQ(1u, verity_tree().size());
90 ASSERT_EQ("e69eb527b16f933483768e92de9bca45f6cc09208525d408436bb362eb865d32",
91 HashTreeBuilder::BytesArrayToString(builder->root_hash()));
92 }
93
TEST_F(BuildVerityTreeTest,HashSingleLevel)94 TEST_F(BuildVerityTreeTest, HashSingleLevel) {
95 std::vector<unsigned char> data(128 * 4096, 0);
96
97 GenerateHashTree(data, salt_hex);
98
99 ASSERT_EQ(1u, verity_tree().size());
100 ASSERT_EQ("62a4fbe8c9036168ba77fe3e3fd78dd6ed963aeb8aaaa36e84f5c7f9107c6b78",
101 HashTreeBuilder::BytesArrayToString(builder->root_hash()));
102 }
103
TEST_F(BuildVerityTreeTest,HashSingleLevel_blake2b256)104 TEST_F(BuildVerityTreeTest, HashSingleLevel_blake2b256) {
105 std::vector<unsigned char> data(128 * 4096, 0x0);
106
107 builder.reset(
108 new HashTreeBuilder(4096, HashTreeBuilder::HashFunction("blake2b-256")));
109
110 GenerateHashTree(data, salt_hex);
111 ASSERT_EQ(1u, verity_tree().size());
112 ASSERT_EQ("6d5b006af5308523f7db6956c60b2650ff3e7edab1e2194cc8ee19b1a1398c03",
113 HashTreeBuilder::BytesArrayToString(builder->root_hash()));
114 }
115
TEST_F(BuildVerityTreeTest,HashMultipleLevels)116 TEST_F(BuildVerityTreeTest, HashMultipleLevels) {
117 std::vector<unsigned char> data(129 * 4096, 0xff);
118
119 GenerateHashTree(data, salt_hex);
120
121 ASSERT_EQ(2u, verity_tree().size());
122 ASSERT_EQ(2 * 4096u, verity_tree()[0].size());
123 ASSERT_EQ("9e74f2d47a990c276093760f01de5e9039883e808286ee9492c9cafe9e4ff825",
124 HashTreeBuilder::BytesArrayToString(builder->root_hash()));
125 }
126
TEST_F(BuildVerityTreeTest,StreamingDataMultipleBlocks)127 TEST_F(BuildVerityTreeTest, StreamingDataMultipleBlocks) {
128 std::vector<unsigned char> data(256 * 4096);
129 for (size_t i = 0; i < 256; i++) {
130 std::fill_n(data.begin() + i * 4096, 4096, i);
131 }
132
133 ASSERT_TRUE(builder->Initialize(data.size(), salt_hex));
134
135 size_t offset = 0;
136 while (offset < data.size()) {
137 size_t data_length =
138 std::min<size_t>(rand() % 10 * 4096, data.size() - offset);
139 ASSERT_TRUE(builder->Update(data.data() + offset, data_length));
140 offset += data_length;
141 }
142
143 ASSERT_TRUE(builder->BuildHashTree());
144 ASSERT_EQ(2u, verity_tree().size());
145 ASSERT_EQ(2 * 4096u, verity_tree()[0].size());
146 ASSERT_EQ("6e73d59b0b6baf026e921814979a7db02244c95a46b869a17aa1310dad066deb",
147 HashTreeBuilder::BytesArrayToString(builder->root_hash()));
148 }
149
TEST_F(BuildVerityTreeTest,StreamingDataPartialBlocks)150 TEST_F(BuildVerityTreeTest, StreamingDataPartialBlocks) {
151 std::vector<unsigned char> data(256 * 4096);
152 for (size_t i = 0; i < 256; i++) {
153 std::fill_n(data.begin() + i * 4096, 4096, i);
154 }
155
156 ASSERT_TRUE(builder->Initialize(data.size(), salt_hex));
157
158 size_t offset = 0;
159 while (offset < data.size()) {
160 size_t data_length = std::min<size_t>(rand() % 40960, data.size() - offset);
161 ASSERT_TRUE(builder->Update(data.data() + offset, data_length));
162 offset += data_length;
163 }
164
165 ASSERT_TRUE(builder->BuildHashTree());
166 ASSERT_EQ(2u, verity_tree().size());
167 ASSERT_EQ(2 * 4096u, verity_tree()[0].size());
168 ASSERT_EQ("6e73d59b0b6baf026e921814979a7db02244c95a46b869a17aa1310dad066deb",
169 HashTreeBuilder::BytesArrayToString(builder->root_hash()));
170 }
171
TEST_F(BuildVerityTreeTest,CalculateRootDigest)172 TEST_F(BuildVerityTreeTest, CalculateRootDigest) {
173 std::vector<unsigned char> data(256 * 4096);
174 for (size_t i = 0; i < 256; i++) {
175 std::fill_n(data.begin() + i * 4096, 4096, i);
176 }
177
178 ASSERT_TRUE(builder->Initialize(data.size(), salt_hex));
179
180 size_t offset = 0;
181 while (offset < data.size()) {
182 size_t data_length = std::min<size_t>(rand() % 40960, data.size() - offset);
183 ASSERT_TRUE(builder->Update(data.data() + offset, data_length));
184 offset += data_length;
185 }
186
187 ASSERT_TRUE(builder->BuildHashTree());
188 ASSERT_EQ(2u, verity_tree().size());
189 ASSERT_EQ(2 * 4096u, verity_tree()[0].size());
190 std::string expected_root_digest = HashTreeBuilder::BytesArrayToString(builder->root_hash());
191
192 std::vector<unsigned char> actual_root_digest;
193 ASSERT_TRUE(builder->CalculateRootDigest(verity_tree().back(), &actual_root_digest));
194 ASSERT_EQ(expected_root_digest, HashTreeBuilder::BytesArrayToString(actual_root_digest));
195 }
196
TEST_F(BuildVerityTreeTest,SHA1MultipleBlocks)197 TEST_F(BuildVerityTreeTest, SHA1MultipleBlocks) {
198 std::vector<unsigned char> data(128 * 4096, 0xff);
199
200 builder.reset(
201 new HashTreeBuilder(4096, HashTreeBuilder::HashFunction("SHA1")));
202
203 GenerateHashTree(data, salt_hex);
204 ASSERT_EQ(1u, verity_tree().size());
205 ASSERT_EQ("7ea287e6167929988810077abaafbc313b2b8593000000000000000000000000",
206 HashTreeBuilder::BytesArrayToString(builder->root_hash()));
207 }
208