1 ///////////////////////////////////////////////////////////////////////////////
2 //
3 /// \file       index_hash.c
4 /// \brief      Validates Index by using a hash function
5 //
6 //  Author:     Lasse Collin
7 //
8 //  This file has been put into the public domain.
9 //  You can do whatever you want with this file.
10 //
11 ///////////////////////////////////////////////////////////////////////////////
12 
13 #include "common.h"
14 #include "index.h"
15 #include "check.h"
16 
17 
18 typedef struct {
19 	/// Sum of the Block sizes (including Block Padding)
20 	lzma_vli blocks_size;
21 
22 	/// Sum of the Uncompressed Size fields
23 	lzma_vli uncompressed_size;
24 
25 	/// Number of Records
26 	lzma_vli count;
27 
28 	/// Size of the List of Index Records as bytes
29 	lzma_vli index_list_size;
30 
31 	/// Check calculated from Unpadded Sizes and Uncompressed Sizes.
32 	lzma_check_state check;
33 
34 } lzma_index_hash_info;
35 
36 
37 struct lzma_index_hash_s {
38 	enum {
39 		SEQ_BLOCK,
40 		SEQ_COUNT,
41 		SEQ_UNPADDED,
42 		SEQ_UNCOMPRESSED,
43 		SEQ_PADDING_INIT,
44 		SEQ_PADDING,
45 		SEQ_CRC32,
46 	} sequence;
47 
48 	/// Information collected while decoding the actual Blocks.
49 	lzma_index_hash_info blocks;
50 
51 	/// Information collected from the Index field.
52 	lzma_index_hash_info records;
53 
54 	/// Number of Records not fully decoded
55 	lzma_vli remaining;
56 
57 	/// Unpadded Size currently being read from an Index Record.
58 	lzma_vli unpadded_size;
59 
60 	/// Uncompressed Size currently being read from an Index Record.
61 	lzma_vli uncompressed_size;
62 
63 	/// Position in variable-length integers when decoding them from
64 	/// the List of Records.
65 	size_t pos;
66 
67 	/// CRC32 of the Index
68 	uint32_t crc32;
69 };
70 
71 
72 extern LZMA_API(lzma_index_hash *)
73 lzma_index_hash_init(lzma_index_hash *index_hash,
74 		const lzma_allocator *allocator)
75 {
76 	if (index_hash == NULL) {
77 		index_hash = lzma_alloc(sizeof(lzma_index_hash), allocator);
78 		if (index_hash == NULL)
79 			return NULL;
80 	}
81 
82 	index_hash->sequence = SEQ_BLOCK;
83 	index_hash->blocks.blocks_size = 0;
84 	index_hash->blocks.uncompressed_size = 0;
85 	index_hash->blocks.count = 0;
86 	index_hash->blocks.index_list_size = 0;
87 	index_hash->records.blocks_size = 0;
88 	index_hash->records.uncompressed_size = 0;
89 	index_hash->records.count = 0;
90 	index_hash->records.index_list_size = 0;
91 	index_hash->unpadded_size = 0;
92 	index_hash->uncompressed_size = 0;
93 	index_hash->pos = 0;
94 	index_hash->crc32 = 0;
95 
96 	// These cannot fail because LZMA_CHECK_BEST is known to be supported.
97 	(void)lzma_check_init(&index_hash->blocks.check, LZMA_CHECK_BEST);
98 	(void)lzma_check_init(&index_hash->records.check, LZMA_CHECK_BEST);
99 
100 	return index_hash;
101 }
102 
103 
104 extern LZMA_API(void)
105 lzma_index_hash_end(lzma_index_hash *index_hash,
106 		const lzma_allocator *allocator)
107 {
108 	lzma_free(index_hash, allocator);
109 	return;
110 }
111 
112 
113 extern LZMA_API(lzma_vli)
114 lzma_index_hash_size(const lzma_index_hash *index_hash)
115 {
116 	// Get the size of the Index from ->blocks instead of ->records for
117 	// cases where application wants to know the Index Size before
118 	// decoding the Index.
119 	return index_size(index_hash->blocks.count,
120 			index_hash->blocks.index_list_size);
121 }
122 
123 
124 /// Updates the sizes and the hash without any validation.
125 static void
126 hash_append(lzma_index_hash_info *info, lzma_vli unpadded_size,
127 		lzma_vli uncompressed_size)
128 {
129 	info->blocks_size += vli_ceil4(unpadded_size);
130 	info->uncompressed_size += uncompressed_size;
131 	info->index_list_size += lzma_vli_size(unpadded_size)
132 			+ lzma_vli_size(uncompressed_size);
133 	++info->count;
134 
135 	const lzma_vli sizes[2] = { unpadded_size, uncompressed_size };
136 	lzma_check_update(&info->check, LZMA_CHECK_BEST,
137 			(const uint8_t *)(sizes), sizeof(sizes));
138 
139 	return;
140 }
141 
142 
143 extern LZMA_API(lzma_ret)
144 lzma_index_hash_append(lzma_index_hash *index_hash, lzma_vli unpadded_size,
145 		lzma_vli uncompressed_size)
146 {
147 	// Validate the arguments.
148 	if (index_hash == NULL || index_hash->sequence != SEQ_BLOCK
149 			|| unpadded_size < UNPADDED_SIZE_MIN
150 			|| unpadded_size > UNPADDED_SIZE_MAX
151 			|| uncompressed_size > LZMA_VLI_MAX)
152 		return LZMA_PROG_ERROR;
153 
154 	// Update the hash.
155 	hash_append(&index_hash->blocks, unpadded_size, uncompressed_size);
156 
157 	// Validate the properties of *info are still in allowed limits.
158 	if (index_hash->blocks.blocks_size > LZMA_VLI_MAX
159 			|| index_hash->blocks.uncompressed_size > LZMA_VLI_MAX
160 			|| index_size(index_hash->blocks.count,
161 					index_hash->blocks.index_list_size)
162 				> LZMA_BACKWARD_SIZE_MAX
163 			|| index_stream_size(index_hash->blocks.blocks_size,
164 					index_hash->blocks.count,
165 					index_hash->blocks.index_list_size)
166 				> LZMA_VLI_MAX)
167 		return LZMA_DATA_ERROR;
168 
169 	return LZMA_OK;
170 }
171 
172 
173 extern LZMA_API(lzma_ret)
174 lzma_index_hash_decode(lzma_index_hash *index_hash, const uint8_t *in,
175 		size_t *in_pos, size_t in_size)
176 {
177 	// Catch zero input buffer here, because in contrast to Index encoder
178 	// and decoder functions, applications call this function directly
179 	// instead of via lzma_code(), which does the buffer checking.
180 	if (*in_pos >= in_size)
181 		return LZMA_BUF_ERROR;
182 
183 	// NOTE: This function has many similarities to index_encode() and
184 	// index_decode() functions found from index_encoder.c and
185 	// index_decoder.c. See the comments especially in index_encoder.c.
186 	const size_t in_start = *in_pos;
187 	lzma_ret ret = LZMA_OK;
188 
189 	while (*in_pos < in_size)
190 	switch (index_hash->sequence) {
191 	case SEQ_BLOCK:
192 		// Check the Index Indicator is present.
193 		if (in[(*in_pos)++] != INDEX_INDICATOR)
194 			return LZMA_DATA_ERROR;
195 
196 		index_hash->sequence = SEQ_COUNT;
197 		break;
198 
199 	case SEQ_COUNT: {
200 		ret = lzma_vli_decode(&index_hash->remaining,
201 				&index_hash->pos, in, in_pos, in_size);
202 		if (ret != LZMA_STREAM_END)
203 			goto out;
204 
205 		// The count must match the count of the Blocks decoded.
206 		if (index_hash->remaining != index_hash->blocks.count)
207 			return LZMA_DATA_ERROR;
208 
209 		ret = LZMA_OK;
210 		index_hash->pos = 0;
211 
212 		// Handle the special case when there are no Blocks.
213 		index_hash->sequence = index_hash->remaining == 0
214 				? SEQ_PADDING_INIT : SEQ_UNPADDED;
215 		break;
216 	}
217 
218 	case SEQ_UNPADDED:
219 	case SEQ_UNCOMPRESSED: {
220 		lzma_vli *size = index_hash->sequence == SEQ_UNPADDED
221 				? &index_hash->unpadded_size
222 				: &index_hash->uncompressed_size;
223 
224 		ret = lzma_vli_decode(size, &index_hash->pos,
225 				in, in_pos, in_size);
226 		if (ret != LZMA_STREAM_END)
227 			goto out;
228 
229 		ret = LZMA_OK;
230 		index_hash->pos = 0;
231 
232 		if (index_hash->sequence == SEQ_UNPADDED) {
233 			if (index_hash->unpadded_size < UNPADDED_SIZE_MIN
234 					|| index_hash->unpadded_size
235 						> UNPADDED_SIZE_MAX)
236 				return LZMA_DATA_ERROR;
237 
238 			index_hash->sequence = SEQ_UNCOMPRESSED;
239 		} else {
240 			// Update the hash.
241 			hash_append(&index_hash->records,
242 					index_hash->unpadded_size,
243 					index_hash->uncompressed_size);
244 
245 			// Verify that we don't go over the known sizes. Note
246 			// that this validation is simpler than the one used
247 			// in lzma_index_hash_append(), because here we know
248 			// that values in index_hash->blocks are already
249 			// validated and we are fine as long as we don't
250 			// exceed them in index_hash->records.
251 			if (index_hash->blocks.blocks_size
252 					< index_hash->records.blocks_size
253 					|| index_hash->blocks.uncompressed_size
254 					< index_hash->records.uncompressed_size
255 					|| index_hash->blocks.index_list_size
256 					< index_hash->records.index_list_size)
257 				return LZMA_DATA_ERROR;
258 
259 			// Check if this was the last Record.
260 			index_hash->sequence = --index_hash->remaining == 0
261 					? SEQ_PADDING_INIT : SEQ_UNPADDED;
262 		}
263 
264 		break;
265 	}
266 
267 	case SEQ_PADDING_INIT:
268 		index_hash->pos = (LZMA_VLI_C(4) - index_size_unpadded(
269 				index_hash->records.count,
270 				index_hash->records.index_list_size)) & 3;
271 		index_hash->sequence = SEQ_PADDING;
272 
273 	// Fall through
274 
275 	case SEQ_PADDING:
276 		if (index_hash->pos > 0) {
277 			--index_hash->pos;
278 			if (in[(*in_pos)++] != 0x00)
279 				return LZMA_DATA_ERROR;
280 
281 			break;
282 		}
283 
284 		// Compare the sizes.
285 		if (index_hash->blocks.blocks_size
286 				!= index_hash->records.blocks_size
287 				|| index_hash->blocks.uncompressed_size
288 				!= index_hash->records.uncompressed_size
289 				|| index_hash->blocks.index_list_size
290 				!= index_hash->records.index_list_size)
291 			return LZMA_DATA_ERROR;
292 
293 		// Finish the hashes and compare them.
294 		lzma_check_finish(&index_hash->blocks.check, LZMA_CHECK_BEST);
295 		lzma_check_finish(&index_hash->records.check, LZMA_CHECK_BEST);
296 		if (memcmp(index_hash->blocks.check.buffer.u8,
297 				index_hash->records.check.buffer.u8,
298 				lzma_check_size(LZMA_CHECK_BEST)) != 0)
299 			return LZMA_DATA_ERROR;
300 
301 		// Finish the CRC32 calculation.
302 		index_hash->crc32 = lzma_crc32(in + in_start,
303 				*in_pos - in_start, index_hash->crc32);
304 
305 		index_hash->sequence = SEQ_CRC32;
306 
307 	// Fall through
308 
309 	case SEQ_CRC32:
310 		do {
311 			if (*in_pos == in_size)
312 				return LZMA_OK;
313 
314 			if (((index_hash->crc32 >> (index_hash->pos * 8))
315 					& 0xFF) != in[(*in_pos)++]) {
316 #ifndef FUZZING_BUILD_MODE_UNSAFE_FOR_PRODUCTION
317 				return LZMA_DATA_ERROR;
318 #endif
319 			}
320 
321 		} while (++index_hash->pos < 4);
322 
323 		return LZMA_STREAM_END;
324 
325 	default:
326 		assert(0);
327 		return LZMA_PROG_ERROR;
328 	}
329 
330 out:
331 	// Update the CRC32,
332 	index_hash->crc32 = lzma_crc32(in + in_start,
333 			*in_pos - in_start, index_hash->crc32);
334 
335 	return ret;
336 }
337