Skip to contentSkip to conversation

Fortuna PRNG in /dev/random

PROPOSAL/PATCH Manfred Spraul 4 participants 5 messages Sep 27, 2004 – Sep 28, 2004

lore
Share & tools
lore
#0 lore raw
Quoted 3 lines · Theodore Ts'o

While you're at it, please re-read RFC 793 and RFC 1185. You still don't have TCP sequence generation done right.

Actually trying to replace the partial MD4 might be worth an attempt: I'm certain that the partial MD4 is not the best/fastest way to generate sequence numbers.

Quoted 5 lines

The only real way to settle this would be to ask Jamal and some of the other networking hackers to repeat their benchmarks and see if the AES encryption for every TCP SYN is a problem or not.

It would be unfair: The proposed implementation is not optimized - e.g. the sequence number generation runs under a global spinlock. On large SMP systems this will kill the performance, regardless of the internal implementation.

For the Linux-variant of RFC 1948, the sequence number generation can be described as:
A hash function that generates 24 bit output from 96 bit input. Some of the input bits can be chosen by the attacker, all of these bits are known to the attacker. The attacker can query the output of the hash for some inputs - realistically less than 2^16 to 2^20 inputs. A successful attack means guessing the output of the hash function for one of the inputs that the attacker can't query.

Current implementation:
Set the MD4 initialization vector to the 96 bit input plus 32 secret, random bits. Perform an MD4 hash over 256 secret, random bits.
Take the lowest 24 bits from one of the MD4 state words.
Every 5 minutes the secret bits are reset.

For IPV6, the requirements are similiar, except that the input is 288 bits long.

--
Manfred

#1 lore raw
Quoted 8 lines · Manfred Spraul
Quoted 3 lines · Theodore Ts'o

While you're at it, please re-read RFC 793 and RFC 1185. You still don't have TCP sequence generation done right.

Actually trying to replace the partial MD4 might be worth an attempt:
I'm certain that the partial MD4 is not the best/fastest way to generate sequence numbers.

It infact uses two full SHA1 hashs for tcp sequence numbers (endian and padding issues aside). my patch aims to do this in 1 AES256 Encrypt or 2 AES256 encrypts for ipv6.

Quoted 8 lines
Quoted 4 lines

The only real way to settle this would be to ask Jamal and some of the other networking hackers to repeat their benchmarks and see if the AES encryption for every TCP SYN is a problem or not.

It would be unfair: The proposed implementation is not optimized - e.g. the sequence number generation runs under a global spinlock. On large SMP systems this will kill the performance, regardless of the internal implementation.

This would be nice to have in both RNG implementations.

Quoted 21 lines

For the Linux-variant of RFC 1948, the sequence number generation can be described as:
A hash function that generates 24 bit output from 96 bit input. Some of the input bits can be chosen by the attacker, all of these bits are known to the attacker. The attacker can query the output of the hash for some inputs - realistically less than 2^16 to 2^20 inputs. A successful attack means guessing the output of the hash function for one of the inputs that the attacker can't query.

Current implementation:
Set the MD4 initialization vector to the 96 bit input plus 32 secret, random bits.
Perform an MD4 hash over 256 secret, random bits.
Take the lowest 24 bits from one of the MD4 state words. Every 5 minutes the secret bits are reset.

For IPV6, the requirements are similiar, except that the input is 288 bits long.

--
Manfred

#2 lore raw
Quoted 7 lines · Jean-Luc Cooke
Quoted 3 lines

Actually trying to replace the partial MD4 might be worth an attempt:
I'm certain that the partial MD4 is not the best/fastest way to generate sequence numbers.

It infact uses two full SHA1 hashs for tcp sequence numbers (endian and padding issues aside). my patch aims to do this in 1 AES256 Encrypt or 2 AES256 encrypts for ipv6.

No, that's not correct. We rekey once at most every five minutes, and that requires a SHA hash, but in the normal case, it's only a partial MD4.

An AES encrypt for every TCP connection *might* be faster, but I'd want to time it to make sure, and doing a bulk test ala "openssl speed" isn't necessarily going to be predictive, as I've discussed earlier.

- Ted

#3 lore raw
Quoted 11 lines · Theodore Ts'o
Quoted 7 lines · Jean-Luc Cooke
Quoted 3 lines

Actually trying to replace the partial MD4 might be worth an attempt:
I'm certain that the partial MD4 is not the best/fastest way to generate sequence numbers.

It infact uses two full SHA1 hashs for tcp sequence numbers (endian and padding issues aside). my patch aims to do this in 1 AES256 Encrypt or 2 AES256 encrypts for ipv6.

No, that's not correct. We rekey once at most every five minutes, and that requires a SHA hash, but in the normal case, it's only a partial MD4.

Pardon, the SYN cookies use two SHA1's, not the TCP sequence numbers. Easy to mistake to make with comments "Compute the secure sequence number." in the secure_tcp_syn_cookie() function. :)

Quoted 3 lines

An AES encrypt for every TCP connection *might* be faster, but I'd want to time it to make sure, and doing a bulk test ala "openssl speed" isn't necessarily going to be predictive, as I've discussed earlier.

Agreed.

Was meaning to ask:
add_timer_randomness()

There is a comment:
/* if over the trickle threshold, use only 1 in 4096 samples */ if ( random_state->entropy_count > trickle_thresh &&

	(__get_cpu_var(trickle_count)++ & 0xfff))
		return;

"if (x++ & 0xfff)" will return true 0xfff out of 0x1000 of the time. Is this the goal, because I don't think this will trickle control very well.

JLC

#4 lore raw
Quoted 26 lines · Jean-Luc Cooke
Quoted 11 lines · Theodore Ts'o
Quoted 7 lines · Jean-Luc Cooke
Quoted 3 lines

Actually trying to replace the partial MD4 might be worth an attempt:
I'm certain that the partial MD4 is not the best/fastest way to generate sequence numbers.

It infact uses two full SHA1 hashs for tcp sequence numbers (endian and padding issues aside). my patch aims to do this in 1 AES256 Encrypt or 2 AES256 encrypts for ipv6.

No, that's not correct. We rekey once at most every five minutes, and that requires a SHA hash, but in the normal case, it's only a partial MD4.

Pardon, the SYN cookies use two SHA1's, not the TCP sequence numbers. Easy to mistake to make with comments "Compute the secure sequence number." in the secure_tcp_syn_cookie() function. :)

Quoted 3 lines

An AES encrypt for every TCP connection *might* be faster, but I'd want to time it to make sure, and doing a bulk test ala "openssl speed" isn't necessarily going to be predictive, as I've discussed earlier.

Agreed.

Was meaning to ask:
add_timer_randomness()

Quoted 8 lines

There is a comment:
/* if over the trickle threshold, use only 1 in 4096 samples */ if ( random_state->entropy_count > trickle_thresh &&

	(__get_cpu_var(trickle_count)++ & 0xfff))
		return;

"if (x++ & 0xfff)" will return true 0xfff out of 0x1000 of the time. Is this the goal, because I don't think this will trickle control very well.

and it will 'return' 0xfff times of 0x1000 ...

(just one case (x == 0) will pass this check)

best,
Herbert

Quoted 6 lines

JLC
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/