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 Unified 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

@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;

}

/*!
 * @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








>








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

		minCapacity = capacity;

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

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

		if (of_hash_seed != 0)
			seed = of_random();


	} @catch (id e) {
		[self release];
		@throw e;
	}

	return self;
}








|

>
>








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) {
			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

	@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: buckets[i]->hash ^ seed];

	} @catch (id e) {
		[copy release];
		@throw e;
	}

	copy->minCapacity = MIN_CAPACITY;









>
|
>








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(
						       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

	uint32_t i, hash, last;

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

	hash = keyFunctions.hash(key) ^ seed;
	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))








|








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 = 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

	return NULL;
}

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


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

	fullness = newCount * 8 / capacity;









>








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


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

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


	}

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

			buckets[i]->hash ^= seedUpdate;



			last = newCapacity;

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

			/* In case the last bucket is already used */








>
>






|
>
>








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 = 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

		}
	}

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

}

- (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;

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

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








>















|








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 = 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


	/* 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;

		mutations++;
		last = capacity;

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









|








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 = 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

	uint32_t i, hash, last;

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

	hash = keyFunctions.hash(key) ^ seed;
	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)) {








|








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 = 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

#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_HASH_INIT(hash) hash = of_hash_seed
#define OF_HASH_ADD(hash, byte)			\
	{					\
		hash += (uint8_t)(byte);	\
		hash += (hash << 10);		\
		hash ^= (hash >> 6);		\








>
>
>








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