ObjFW  Check-in [4857107479]

Overview
Comment:OFMapTable: Rotate hash by a random number of bits

By rotating the hash by a random number of bits, an attacker needs to
find collisions on the full 32 bits of the hash and not only on the
lower n bits that are actually used by the map table, as an attacker
can't know which bits are actually used for the map table.

Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA3-256: 4857107479fb6749a6aa9b749276d01aa5083ec139c9ada9d121cc102dd57387
User & Date: js on 2012-12-06 11:00:54
Other Links: manifest | tags
Context
2012-12-06
16:20
OFHTTPRequestDelegate: Method name improvement. check-in: c64cb4c5f2 user: js tags: trunk
11:00
OFMapTable: Rotate hash by a random number of bits check-in: 4857107479 user: js tags: trunk
11:00
Add of_random(). check-in: f675979cf0 user: js tags: trunk
Changes
Hide Diffs Side-by-Side Diffs Ignore Whitespace Patch

Modified src/OFMapTable.h from [5b6730706a] to [91b9317d21].

︙
47
48
49
50
51
52
53

54
55
56
57
58
59
60

47
48
49
50
51
52
53
54
55
56
57
58
59
60
61








+








@interface OFMapTable: OFObject <OFCopying, OFFastEnumeration>
{
	of_map_table_functions_t keyFunctions, valueFunctions;
	struct of_map_table_bucket **buckets;
	uint32_t minCapacity, capacity, count;
	unsigned long mutations;
	uint32_t seed;
	uint8_t rotate;
}

/*!
 * @brief Creates a new OFMapTable with the specified key and value functions.
 *
 * @param keyFunctions A structure of functions for handling keys
 * @param valueFunctions A structure of functions for handling values
︙

Modified src/OFMapTable.m from [ecdbc341ea] to [fda4d04529].

︙
149
150
151
152
153
154
155
156

157


158
159
160
161
162
163
164

149
150
151
152
153
154
155

156
157
158
159
160
161
162
163
164
165
166








-
+

+
+








		minCapacity = capacity;

		buckets = [self allocMemoryWithSize: sizeof(*buckets)
					      count: capacity];

		memset(buckets, 0, capacity * sizeof(*buckets));

		if (of_hash_seed != 0)
		if (of_hash_seed != 0) {
			seed = of_random();
			rotate = of_random() & 0x1F;
		}
	} @catch (id e) {
		[self release];
		@throw e;
	}

	return self;
}
︙
228
229
230
231
232
233
234

235


236
237
238
239
240
241
242

230
231
232
233
234
235
236
237

238
239
240
241
242
243
244
245
246








+
-
+
+








	@try {
		uint32_t i;

		for (i = 0; i < capacity; i++)
			if (buckets[i] != NULL && buckets[i] != &deleted)
				[copy OF_setValue: buckets[i]->value
					   forKey: buckets[i]->key
					     hash: OF_ROR(
					     hash: buckets[i]->hash ^ seed];
						       buckets[i]->hash ^ seed,
						       rotate)];
	} @catch (id e) {
		[copy release];
		@throw e;
	}

	copy->minCapacity = MIN_CAPACITY;
︙
253
254
255
256
257
258
259
260

261
262
263
264
265
266
267

257
258
259
260
261
262
263

264
265
266
267
268
269
270
271








-
+








	uint32_t i, hash, last;

	if (key == NULL)
		@throw [OFInvalidArgumentException
		    exceptionWithClass: [self class]
			      selector: _cmd];

	hash = keyFunctions.hash(key) ^ seed;
	hash = OF_ROL(keyFunctions.hash(key) ^ seed, rotate);
	last = capacity;

	for (i = hash & (capacity - 1); i < last && buckets[i] != NULL; i++) {
		if (buckets[i] == &deleted)
			continue;

		if (keyFunctions.equal(buckets[i]->key, key))
︙
285
286
287
288
289
290
291

292
293
294
295
296
297
298

289
290
291
292
293
294
295
296
297
298
299
300
301
302
303








+








	return NULL;
}

- (void)OF_resizeForCount: (uint32_t)newCount
{
	uint32_t i, fullness, newCapacity, newSeed = 0, seedUpdate = 0;
	struct of_map_table_bucket **newBuckets;
	uint8_t newRotate = 0;

	if (newCount > UINT32_MAX || newCount > UINT32_MAX / sizeof(*buckets) ||
	    newCount > UINT32_MAX / 8)
		@throw [OFOutOfRangeException exceptionWithClass: [self class]];

	fullness = newCount * 8 / capacity;
︙
311
312
313
314
315
316
317


318
319
320
321
322
323
324



325
326
327
328
329
330
331

316
317
318
319
320
321
322
323
324
325
326
327
328
329
330

331
332
333
334
335
336
337
338
339
340








+
+






-
+
+
+









	for (i = 0; i < newCapacity; i++)
		newBuckets[i] = NULL;

	if (of_hash_seed != 0) {
		newSeed = of_random();
		seedUpdate = seed ^ newSeed;

		newRotate = of_random() & 0x1F;
	}

	for (i = 0; i < capacity; i++) {
		if (buckets[i] != NULL && buckets[i] != &deleted) {
			uint32_t j, last;

			buckets[i]->hash ^= seedUpdate;
			buckets[i]->hash = OF_ROL(
			    OF_ROR(buckets[i]->hash, rotate) ^ seedUpdate,
			    newRotate);

			last = newCapacity;

			j = buckets[i]->hash & (newCapacity - 1);
			for (; j < last && newBuckets[j] != NULL; j++);

			/* In case the last bucket is already used */
︙
342
343
344
345
346
347
348

349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364

365
366
367
368
369
370
371

351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373

374
375
376
377
378
379
380
381








+















-
+








		}
	}

	[self freeMemory: buckets];
	buckets = newBuckets;
	capacity = newCapacity;
	seed = newSeed;
	rotate = newRotate;
}

- (void)OF_setValue: (void*)value
	     forKey: (void*)key
	       hash: (uint32_t)hash
{
	uint32_t i, last, seededHash;
	void *old;

	if (key == NULL || value == NULL)
		@throw [OFInvalidArgumentException
		    exceptionWithClass: [self class]
			      selector: _cmd];

	last = capacity;
	seededHash = hash ^ seed;
	seededHash = OF_ROL(hash ^ seed, rotate);

	for (i = seededHash & (capacity - 1); i < last && buckets[i] != NULL;
	    i++) {
		if (buckets[i] == &deleted)
			continue;

		if (keyFunctions.equal(buckets[i]->key, key))
︙
387
388
389
390
391
392
393
394

395
396
397
398
399
400
401

397
398
399
400
401
402
403

404
405
406
407
408
409
410
411








-
+









	/* Key not in dictionary */
	if (i >= last || buckets[i] == NULL || buckets[i] == &deleted ||
	    !keyFunctions.equal(buckets[i]->key, key)) {
		struct of_map_table_bucket *bucket;

		[self OF_resizeForCount: count + 1];
		seededHash = hash ^ seed;
		seededHash = OF_ROL(hash ^ seed, rotate);

		mutations++;
		last = capacity;

		for (i = seededHash & (capacity - 1); i < last &&
		    buckets[i] != NULL && buckets[i] != &deleted; i++);
︙
454
455
456
457
458
459
460
461

462
463
464
465
466
467
468

464
465
466
467
468
469
470

471
472
473
474
475
476
477
478








-
+








	uint32_t i, hash, last;

	if (key == NULL)
		@throw [OFInvalidArgumentException
		    exceptionWithClass: [self class]
			      selector: _cmd];

	hash = keyFunctions.hash(key) ^ seed;
	hash = OF_ROL(keyFunctions.hash(key) ^ seed, rotate);
	last = capacity;

	for (i = hash & (capacity - 1); i < last && buckets[i] != NULL; i++) {
		if (buckets[i] == &deleted)
			continue;

		if (keyFunctions.equal(buckets[i]->key, key)) {
︙

Modified src/macros.h from [ba733f14be] to [6b2bc955be].

︙
321
322
323
324
325
326
327



328
329
330
331
332
333
334

321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337








+
+
+








#if defined(__MACH__) && defined(__arm__)
# define OF_IOS
#endif

#define OF_ROL(value, bits)						\
	(((value) << ((bits) % (sizeof(value) * 8))) |			\
	(value) >> (sizeof(value) * 8 - ((bits) % (sizeof(value) * 8))))
#define OF_ROR(value, bits)						\
	(((value) >> ((bits) % (sizeof(value) * 8))) |			\
	(value) << (sizeof(value) * 8 - ((bits) % (sizeof(value) * 8))))

#define OF_HASH_INIT(hash) hash = of_hash_seed
#define OF_HASH_ADD(hash, byte)			\
	{					\
		hash += (uint8_t)(byte);	\
		hash += (hash << 10);		\
		hash ^= (hash >> 6);		\
︙

Fossil 2.23 [47362306a7] 2023-11-01 18:56:47
This page was generated in about 0.019s