Mixing
How fast does a pseudrandom number generator have to be in order to be competitive?
Clash Royale CLAN TAG#URR8PPP
up vote
4
down vote
favorite
Let $x_n_n$ be the pseudorandom sequence produced by a cryptographically secure pseudorandom number generator $G$. What is the cost of computing a term in the sequence for a competitive pseudorandom number generator (PRNG)?
Let me clarify: among the cryptographically secure PRNG, I would like to know which one has the lowest computational cost.
pseudo-random-generator
edited 21 mins ago
Ella Rose
13.6k43472
asked 6 hours ago
Reyx_0
1293
add a comment |Â
up vote
4
down vote
favorite
Let $x_n_n$ be the pseudorandom sequence produced by a cryptographically secure pseudorandom number generator $G$. What is the cost of computing a term in the sequence for a competitive pseudorandom number generator (PRNG)?
Let me clarify: among the cryptographically secure PRNG, I would like to know which one has the lowest computational cost.
pseudo-random-generator
edited 21 mins ago
Ella Rose
13.6k43472
asked 6 hours ago
Reyx_0
1293
add a comment |Â
up vote
4
down vote
favorite
up vote
4
down vote
favorite
Let $x_n_n$ be the pseudorandom sequence produced by a cryptographically secure pseudorandom number generator $G$. What is the cost of computing a term in the sequence for a competitive pseudorandom number generator (PRNG)?
Let me clarify: among the cryptographically secure PRNG, I would like to know which one has the lowest computational cost.
pseudo-random-generator
edited 21 mins ago
Ella Rose
13.6k43472
asked 6 hours ago
Reyx_0
1293
Let $x_n_n$ be the pseudorandom sequence produced by a cryptographically secure pseudorandom number generator $G$. What is the cost of computing a term in the sequence for a competitive pseudorandom number generator (PRNG)?
Let me clarify: among the cryptographically secure PRNG, I would like to know which one has the lowest computational cost.
pseudo-random-generator
pseudo-random-generator
edited 21 mins ago
Ella Rose
13.6k43472
asked 6 hours ago
Reyx_0
1293
edited 21 mins ago
Ella Rose
13.6k43472
asked 6 hours ago
Reyx_0
1293
edited 21 mins ago
Ella Rose
13.6k43472
edited 21 mins ago
Ella Rose
13.6k43472
edited 21 mins ago
Ella Rose
13.6k43472
13.6k43472
asked 6 hours ago
Reyx_0
1293
asked 6 hours ago
Reyx_0
1293
asked 6 hours ago
Reyx_0
1293
1293
add a comment |Â
add a comment |Â
2 Answers
2
active
oldest
votes
up vote
8
down vote
On modern CPUs, a fast Cryptographically Secure Pseudo-Random Number Generator runs sizably faster than one cycle per byte. We are talking >40Gbit/s. See numbers there. Top contenders are AES-CTR assisted by special instruction, and ARX ciphers like ChaCha.
When using dedicated hardware, the true limit is moving around the generated random bits. We can arbitrarily parallelize CSPRNGs, and we have many efficient designs. For example, Trivium is reported at >120Gbit/s/mm2 using 250nm metal CMOS technology, and state of the art today is about 10nm technology, which is faster and some hundreds time denser.
Update per comment: All modern CSPRNGs require $O(n)$ bit operations to produce $n$ bits, and we want little-o notation for an interesting figure. ChaCha with $r$ rounds (see source) produces $16$ words each 32-bit with computational cost dominated by $16(r+1)$ 32-bit additions and $16r$ 32-bit XORs. Using NAND gates, a ripple-carry adder is 9 gates, XOR is 4 gates, thus the cost is $13r+9$ NAND bit operations per bit produced. For Chacha8 (which is hoped to have 128-bit security), the cost is like $o(113n)$ NAND bit operations to produce $n$ bits (with no consideration for circuit depth).
answered 5 hours ago
fgrieu
73.4k6149310
Thanks for this. In terms of big O notation, how many bit operations does chacha requires for example to produce an n-bit pseudoradom number?
– Reyx_0
5 hours ago
add a comment |Â
up vote
-1
down vote
It sort of depends on what you are using it for.
You would think that openssl's PRNG, rand, would be
cryptographically secure, and I'm sure it's plenty fast.
But I couldn't help but notice a regular preponderance
of repeated hex digits in every call to openssl rand, using
a value of 16 (for AES 128 purposes). Given that the average
intel chip comes with AES round calculations in silicon, for
extra speed, it does seem like the search space for brute
forcing AES (without the benefit of the RSA-encrypted key)
has been made smaller by this repetition.
If you know that 3 of your 32 4-bit possibilities will
be repeated FOUR times (or more!) you do save some time
doing a brute force. If I knew in advance that 31 of
the 32 nybbles would be repeated, I would only have to
check 4096 different keys. (as an extreme example)
I once counted 9 repeated digits on one generation.
I know the goal is for a random distribution, but
when you only have 128 bits, that's not always good enough.
So I imagine even at mind-blowing speeds, there's room for
side-channel surprises. Good luck!
Here's some results I just generated on the fly:
user0@ii:~$ openssl rand 16 -hex
0fe29badfe8e2300cbe4d1f0eecfdac1
000011223489aabbcccdddEEEEEEffff (6,4x2)
user0@ii:~$ openssl rand 16 -hex
a6f3b7054138c58991b560b6377a567f
001133345555666677778899aabbbcff (4x3)
user0@ii:~$ openssl rand 16 -hex
c2d854a9fdac7e73a9872c12ade2c048
012222344577788899aaaaccccdddeef (4x3)
user0@ii:~$ openssl rand 16 -hex
7e1a3400da787aff51dbddd2fd10067a
00001112345677778aaaabDDDDDDefff (6,4x3)
user0@ii:~$ openssl rand 16 -hex
4785496843d62083ed285572cd1ad6b2
012222334445556667788889abcdddde (4x3)
answered 4 hours ago
James Huddle
71
New contributor
James Huddle is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
2
I believe that a truly random output would show the same artifacts that you complain about OpenSSL; for example, a truly random 16 byte output would have 9 or repeated hex digits once every circa 370000 outputs. So, yes, if you go through enough of them, you would expect to see such extreme cases (and 'enough' needn't be that many...)
– poncho
3 hours ago
1
You're falling into a trap. I recall a complaint that consecutive second factor codes repeated a few digits and so it was not truly random. Something like "182345" and "405346" - there's a repeat of "34". Just because something stands out to you does not mean it is not random. Humans are great at seeing patterns including the ones that don't exist.
– iheanyi
2 hours ago
If you're suggesting that OpenSSL's PRNG is inadequate because it shows patterns, then this answer needs to be improved by including an analysis showing that the patterns are statistically significant.
– Tanner Swett
1 hour ago
I agree that seeing "34" like that in two outputs would be "reading a lot into it." But if you see "34" in 6 out of 6 outputs, I'd say you've reduced your brute force effort by a factor of 100. Of course, you're betting that the 7th will have a "34" and it's always possible that it was just pure randomness (I understand the counterintuitive qualities of pure random values). I'm just saying that if I were designing a PRNG system, I would work hard to avoid such coincidences. And yes, I know how naive that sounds. Sorry about the lack of math proof.
– James Huddle
9 mins ago
add a comment |Â
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
8
down vote
On modern CPUs, a fast Cryptographically Secure Pseudo-Random Number Generator runs sizably faster than one cycle per byte. We are talking >40Gbit/s. See numbers there. Top contenders are AES-CTR assisted by special instruction, and ARX ciphers like ChaCha.
When using dedicated hardware, the true limit is moving around the generated random bits. We can arbitrarily parallelize CSPRNGs, and we have many efficient designs. For example, Trivium is reported at >120Gbit/s/mm2 using 250nm metal CMOS technology, and state of the art today is about 10nm technology, which is faster and some hundreds time denser.
Update per comment: All modern CSPRNGs require $O(n)$ bit operations to produce $n$ bits, and we want little-o notation for an interesting figure. ChaCha with $r$ rounds (see source) produces $16$ words each 32-bit with computational cost dominated by $16(r+1)$ 32-bit additions and $16r$ 32-bit XORs. Using NAND gates, a ripple-carry adder is 9 gates, XOR is 4 gates, thus the cost is $13r+9$ NAND bit operations per bit produced. For Chacha8 (which is hoped to have 128-bit security), the cost is like $o(113n)$ NAND bit operations to produce $n$ bits (with no consideration for circuit depth).
answered 5 hours ago
fgrieu
73.4k6149310
Thanks for this. In terms of big O notation, how many bit operations does chacha requires for example to produce an n-bit pseudoradom number?
– Reyx_0
5 hours ago
add a comment |Â
up vote
8
down vote
On modern CPUs, a fast Cryptographically Secure Pseudo-Random Number Generator runs sizably faster than one cycle per byte. We are talking >40Gbit/s. See numbers there. Top contenders are AES-CTR assisted by special instruction, and ARX ciphers like ChaCha.
When using dedicated hardware, the true limit is moving around the generated random bits. We can arbitrarily parallelize CSPRNGs, and we have many efficient designs. For example, Trivium is reported at >120Gbit/s/mm2 using 250nm metal CMOS technology, and state of the art today is about 10nm technology, which is faster and some hundreds time denser.
Update per comment: All modern CSPRNGs require $O(n)$ bit operations to produce $n$ bits, and we want little-o notation for an interesting figure. ChaCha with $r$ rounds (see source) produces $16$ words each 32-bit with computational cost dominated by $16(r+1)$ 32-bit additions and $16r$ 32-bit XORs. Using NAND gates, a ripple-carry adder is 9 gates, XOR is 4 gates, thus the cost is $13r+9$ NAND bit operations per bit produced. For Chacha8 (which is hoped to have 128-bit security), the cost is like $o(113n)$ NAND bit operations to produce $n$ bits (with no consideration for circuit depth).
answered 5 hours ago
fgrieu
73.4k6149310
Thanks for this. In terms of big O notation, how many bit operations does chacha requires for example to produce an n-bit pseudoradom number?
– Reyx_0
5 hours ago
add a comment |Â
up vote
8
down vote
up vote
8
down vote
On modern CPUs, a fast Cryptographically Secure Pseudo-Random Number Generator runs sizably faster than one cycle per byte. We are talking >40Gbit/s. See numbers there. Top contenders are AES-CTR assisted by special instruction, and ARX ciphers like ChaCha.
When using dedicated hardware, the true limit is moving around the generated random bits. We can arbitrarily parallelize CSPRNGs, and we have many efficient designs. For example, Trivium is reported at >120Gbit/s/mm2 using 250nm metal CMOS technology, and state of the art today is about 10nm technology, which is faster and some hundreds time denser.
Update per comment: All modern CSPRNGs require $O(n)$ bit operations to produce $n$ bits, and we want little-o notation for an interesting figure. ChaCha with $r$ rounds (see source) produces $16$ words each 32-bit with computational cost dominated by $16(r+1)$ 32-bit additions and $16r$ 32-bit XORs. Using NAND gates, a ripple-carry adder is 9 gates, XOR is 4 gates, thus the cost is $13r+9$ NAND bit operations per bit produced. For Chacha8 (which is hoped to have 128-bit security), the cost is like $o(113n)$ NAND bit operations to produce $n$ bits (with no consideration for circuit depth).
answered 5 hours ago
fgrieu
73.4k6149310
On modern CPUs, a fast Cryptographically Secure Pseudo-Random Number Generator runs sizably faster than one cycle per byte. We are talking >40Gbit/s. See numbers there. Top contenders are AES-CTR assisted by special instruction, and ARX ciphers like ChaCha.
When using dedicated hardware, the true limit is moving around the generated random bits. We can arbitrarily parallelize CSPRNGs, and we have many efficient designs. For example, Trivium is reported at >120Gbit/s/mm2 using 250nm metal CMOS technology, and state of the art today is about 10nm technology, which is faster and some hundreds time denser.
Update per comment: All modern CSPRNGs require $O(n)$ bit operations to produce $n$ bits, and we want little-o notation for an interesting figure. ChaCha with $r$ rounds (see source) produces $16$ words each 32-bit with computational cost dominated by $16(r+1)$ 32-bit additions and $16r$ 32-bit XORs. Using NAND gates, a ripple-carry adder is 9 gates, XOR is 4 gates, thus the cost is $13r+9$ NAND bit operations per bit produced. For Chacha8 (which is hoped to have 128-bit security), the cost is like $o(113n)$ NAND bit operations to produce $n$ bits (with no consideration for circuit depth).
answered 5 hours ago
fgrieu
73.4k6149310
edited 2 hours ago
answered 5 hours ago
fgrieu
73.4k6149310
answered 5 hours ago
fgrieu
73.4k6149310
answered 5 hours ago
fgrieu
73.4k6149310
73.4k6149310
Thanks for this. In terms of big O notation, how many bit operations does chacha requires for example to produce an n-bit pseudoradom number?
– Reyx_0
5 hours ago
add a comment |Â
Thanks for this. In terms of big O notation, how many bit operations does chacha requires for example to produce an n-bit pseudoradom number?
– Reyx_0
5 hours ago
Thanks for this. In terms of big O notation, how many bit operations does chacha requires for example to produce an n-bit pseudoradom number?
– Reyx_0
5 hours ago
Thanks for this. In terms of big O notation, how many bit operations does chacha requires for example to produce an n-bit pseudoradom number?
– Reyx_0
5 hours ago
add a comment |Â
up vote
-1
down vote
It sort of depends on what you are using it for.
You would think that openssl's PRNG, rand, would be
cryptographically secure, and I'm sure it's plenty fast.
But I couldn't help but notice a regular preponderance
of repeated hex digits in every call to openssl rand, using
a value of 16 (for AES 128 purposes). Given that the average
intel chip comes with AES round calculations in silicon, for
extra speed, it does seem like the search space for brute
forcing AES (without the benefit of the RSA-encrypted key)
has been made smaller by this repetition.
If you know that 3 of your 32 4-bit possibilities will
be repeated FOUR times (or more!) you do save some time
doing a brute force. If I knew in advance that 31 of
the 32 nybbles would be repeated, I would only have to
check 4096 different keys. (as an extreme example)
I once counted 9 repeated digits on one generation.
I know the goal is for a random distribution, but
when you only have 128 bits, that's not always good enough.
So I imagine even at mind-blowing speeds, there's room for
side-channel surprises. Good luck!
Here's some results I just generated on the fly:
user0@ii:~$ openssl rand 16 -hex
0fe29badfe8e2300cbe4d1f0eecfdac1
000011223489aabbcccdddEEEEEEffff (6,4x2)
user0@ii:~$ openssl rand 16 -hex
a6f3b7054138c58991b560b6377a567f
001133345555666677778899aabbbcff (4x3)
user0@ii:~$ openssl rand 16 -hex
c2d854a9fdac7e73a9872c12ade2c048
012222344577788899aaaaccccdddeef (4x3)
user0@ii:~$ openssl rand 16 -hex
7e1a3400da787aff51dbddd2fd10067a
00001112345677778aaaabDDDDDDefff (6,4x3)
user0@ii:~$ openssl rand 16 -hex
4785496843d62083ed285572cd1ad6b2
012222334445556667788889abcdddde (4x3)
answered 4 hours ago
James Huddle
71
New contributor
James Huddle is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
2
I believe that a truly random output would show the same artifacts that you complain about OpenSSL; for example, a truly random 16 byte output would have 9 or repeated hex digits once every circa 370000 outputs. So, yes, if you go through enough of them, you would expect to see such extreme cases (and 'enough' needn't be that many...)
– poncho
3 hours ago
1
You're falling into a trap. I recall a complaint that consecutive second factor codes repeated a few digits and so it was not truly random. Something like "182345" and "405346" - there's a repeat of "34". Just because something stands out to you does not mean it is not random. Humans are great at seeing patterns including the ones that don't exist.
– iheanyi
2 hours ago
If you're suggesting that OpenSSL's PRNG is inadequate because it shows patterns, then this answer needs to be improved by including an analysis showing that the patterns are statistically significant.
– Tanner Swett
1 hour ago
I agree that seeing "34" like that in two outputs would be "reading a lot into it." But if you see "34" in 6 out of 6 outputs, I'd say you've reduced your brute force effort by a factor of 100. Of course, you're betting that the 7th will have a "34" and it's always possible that it was just pure randomness (I understand the counterintuitive qualities of pure random values). I'm just saying that if I were designing a PRNG system, I would work hard to avoid such coincidences. And yes, I know how naive that sounds. Sorry about the lack of math proof.
– James Huddle
9 mins ago
add a comment |Â
up vote
-1
down vote
It sort of depends on what you are using it for.
You would think that openssl's PRNG, rand, would be
cryptographically secure, and I'm sure it's plenty fast.
But I couldn't help but notice a regular preponderance
of repeated hex digits in every call to openssl rand, using
a value of 16 (for AES 128 purposes). Given that the average
intel chip comes with AES round calculations in silicon, for
extra speed, it does seem like the search space for brute
forcing AES (without the benefit of the RSA-encrypted key)
has been made smaller by this repetition.
If you know that 3 of your 32 4-bit possibilities will
be repeated FOUR times (or more!) you do save some time
doing a brute force. If I knew in advance that 31 of
the 32 nybbles would be repeated, I would only have to
check 4096 different keys. (as an extreme example)
I once counted 9 repeated digits on one generation.
I know the goal is for a random distribution, but
when you only have 128 bits, that's not always good enough.
So I imagine even at mind-blowing speeds, there's room for
side-channel surprises. Good luck!
Here's some results I just generated on the fly:
user0@ii:~$ openssl rand 16 -hex
0fe29badfe8e2300cbe4d1f0eecfdac1
000011223489aabbcccdddEEEEEEffff (6,4x2)
user0@ii:~$ openssl rand 16 -hex
a6f3b7054138c58991b560b6377a567f
001133345555666677778899aabbbcff (4x3)
user0@ii:~$ openssl rand 16 -hex
c2d854a9fdac7e73a9872c12ade2c048
012222344577788899aaaaccccdddeef (4x3)
user0@ii:~$ openssl rand 16 -hex
7e1a3400da787aff51dbddd2fd10067a
00001112345677778aaaabDDDDDDefff (6,4x3)
user0@ii:~$ openssl rand 16 -hex
4785496843d62083ed285572cd1ad6b2
012222334445556667788889abcdddde (4x3)
answered 4 hours ago
James Huddle
71
New contributor
James Huddle is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
2
I believe that a truly random output would show the same artifacts that you complain about OpenSSL; for example, a truly random 16 byte output would have 9 or repeated hex digits once every circa 370000 outputs. So, yes, if you go through enough of them, you would expect to see such extreme cases (and 'enough' needn't be that many...)
– poncho
3 hours ago
1
You're falling into a trap. I recall a complaint that consecutive second factor codes repeated a few digits and so it was not truly random. Something like "182345" and "405346" - there's a repeat of "34". Just because something stands out to you does not mean it is not random. Humans are great at seeing patterns including the ones that don't exist.
– iheanyi
2 hours ago
If you're suggesting that OpenSSL's PRNG is inadequate because it shows patterns, then this answer needs to be improved by including an analysis showing that the patterns are statistically significant.
– Tanner Swett
1 hour ago
I agree that seeing "34" like that in two outputs would be "reading a lot into it." But if you see "34" in 6 out of 6 outputs, I'd say you've reduced your brute force effort by a factor of 100. Of course, you're betting that the 7th will have a "34" and it's always possible that it was just pure randomness (I understand the counterintuitive qualities of pure random values). I'm just saying that if I were designing a PRNG system, I would work hard to avoid such coincidences. And yes, I know how naive that sounds. Sorry about the lack of math proof.
– James Huddle
9 mins ago
add a comment |Â
up vote
-1
down vote
up vote
-1
down vote
It sort of depends on what you are using it for.
You would think that openssl's PRNG, rand, would be
cryptographically secure, and I'm sure it's plenty fast.
But I couldn't help but notice a regular preponderance
of repeated hex digits in every call to openssl rand, using
a value of 16 (for AES 128 purposes). Given that the average
intel chip comes with AES round calculations in silicon, for
extra speed, it does seem like the search space for brute
forcing AES (without the benefit of the RSA-encrypted key)
has been made smaller by this repetition.
If you know that 3 of your 32 4-bit possibilities will
be repeated FOUR times (or more!) you do save some time
doing a brute force. If I knew in advance that 31 of
the 32 nybbles would be repeated, I would only have to
check 4096 different keys. (as an extreme example)
I once counted 9 repeated digits on one generation.
I know the goal is for a random distribution, but
when you only have 128 bits, that's not always good enough.
So I imagine even at mind-blowing speeds, there's room for
side-channel surprises. Good luck!
Here's some results I just generated on the fly:
user0@ii:~$ openssl rand 16 -hex
0fe29badfe8e2300cbe4d1f0eecfdac1
000011223489aabbcccdddEEEEEEffff (6,4x2)
user0@ii:~$ openssl rand 16 -hex
a6f3b7054138c58991b560b6377a567f
001133345555666677778899aabbbcff (4x3)
user0@ii:~$ openssl rand 16 -hex
c2d854a9fdac7e73a9872c12ade2c048
012222344577788899aaaaccccdddeef (4x3)
user0@ii:~$ openssl rand 16 -hex
7e1a3400da787aff51dbddd2fd10067a
00001112345677778aaaabDDDDDDefff (6,4x3)
user0@ii:~$ openssl rand 16 -hex
4785496843d62083ed285572cd1ad6b2
012222334445556667788889abcdddde (4x3)
answered 4 hours ago
James Huddle
71
New contributor
James Huddle is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
It sort of depends on what you are using it for.
You would think that openssl's PRNG, rand, would be
cryptographically secure, and I'm sure it's plenty fast.
But I couldn't help but notice a regular preponderance
of repeated hex digits in every call to openssl rand, using
a value of 16 (for AES 128 purposes). Given that the average
intel chip comes with AES round calculations in silicon, for
extra speed, it does seem like the search space for brute
forcing AES (without the benefit of the RSA-encrypted key)
has been made smaller by this repetition.
If you know that 3 of your 32 4-bit possibilities will
be repeated FOUR times (or more!) you do save some time
doing a brute force. If I knew in advance that 31 of
the 32 nybbles would be repeated, I would only have to
check 4096 different keys. (as an extreme example)
I once counted 9 repeated digits on one generation.
I know the goal is for a random distribution, but
when you only have 128 bits, that's not always good enough.
So I imagine even at mind-blowing speeds, there's room for
side-channel surprises. Good luck!
Here's some results I just generated on the fly:
user0@ii:~$ openssl rand 16 -hex
0fe29badfe8e2300cbe4d1f0eecfdac1
000011223489aabbcccdddEEEEEEffff (6,4x2)
user0@ii:~$ openssl rand 16 -hex
a6f3b7054138c58991b560b6377a567f
001133345555666677778899aabbbcff (4x3)
user0@ii:~$ openssl rand 16 -hex
c2d854a9fdac7e73a9872c12ade2c048
012222344577788899aaaaccccdddeef (4x3)
user0@ii:~$ openssl rand 16 -hex
7e1a3400da787aff51dbddd2fd10067a
00001112345677778aaaabDDDDDDefff (6,4x3)
user0@ii:~$ openssl rand 16 -hex
4785496843d62083ed285572cd1ad6b2
012222334445556667788889abcdddde (4x3)
answered 4 hours ago
James Huddle
71
New contributor
James Huddle is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
answered 4 hours ago
James Huddle
71
New contributor
James Huddle is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
answered 4 hours ago
James Huddle
71
answered 4 hours ago
James Huddle
71
71
New contributor
James Huddle is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
New contributor
James Huddle is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
James Huddle is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
2
I believe that a truly random output would show the same artifacts that you complain about OpenSSL; for example, a truly random 16 byte output would have 9 or repeated hex digits once every circa 370000 outputs. So, yes, if you go through enough of them, you would expect to see such extreme cases (and 'enough' needn't be that many...)
– poncho
3 hours ago
1
You're falling into a trap. I recall a complaint that consecutive second factor codes repeated a few digits and so it was not truly random. Something like "182345" and "405346" - there's a repeat of "34". Just because something stands out to you does not mean it is not random. Humans are great at seeing patterns including the ones that don't exist.
– iheanyi
2 hours ago
If you're suggesting that OpenSSL's PRNG is inadequate because it shows patterns, then this answer needs to be improved by including an analysis showing that the patterns are statistically significant.
– Tanner Swett
1 hour ago
I agree that seeing "34" like that in two outputs would be "reading a lot into it." But if you see "34" in 6 out of 6 outputs, I'd say you've reduced your brute force effort by a factor of 100. Of course, you're betting that the 7th will have a "34" and it's always possible that it was just pure randomness (I understand the counterintuitive qualities of pure random values). I'm just saying that if I were designing a PRNG system, I would work hard to avoid such coincidences. And yes, I know how naive that sounds. Sorry about the lack of math proof.
– James Huddle
9 mins ago
add a comment |Â
2
I believe that a truly random output would show the same artifacts that you complain about OpenSSL; for example, a truly random 16 byte output would have 9 or repeated hex digits once every circa 370000 outputs. So, yes, if you go through enough of them, you would expect to see such extreme cases (and 'enough' needn't be that many...)
– poncho
3 hours ago
1
You're falling into a trap. I recall a complaint that consecutive second factor codes repeated a few digits and so it was not truly random. Something like "182345" and "405346" - there's a repeat of "34". Just because something stands out to you does not mean it is not random. Humans are great at seeing patterns including the ones that don't exist.
– iheanyi
2 hours ago
If you're suggesting that OpenSSL's PRNG is inadequate because it shows patterns, then this answer needs to be improved by including an analysis showing that the patterns are statistically significant.
– Tanner Swett
1 hour ago
I agree that seeing "34" like that in two outputs would be "reading a lot into it." But if you see "34" in 6 out of 6 outputs, I'd say you've reduced your brute force effort by a factor of 100. Of course, you're betting that the 7th will have a "34" and it's always possible that it was just pure randomness (I understand the counterintuitive qualities of pure random values). I'm just saying that if I were designing a PRNG system, I would work hard to avoid such coincidences. And yes, I know how naive that sounds. Sorry about the lack of math proof.
– James Huddle
9 mins ago
2
2
I believe that a truly random output would show the same artifacts that you complain about OpenSSL; for example, a truly random 16 byte output would have 9 or repeated hex digits once every circa 370000 outputs. So, yes, if you go through enough of them, you would expect to see such extreme cases (and 'enough' needn't be that many...)
– poncho
3 hours ago
I believe that a truly random output would show the same artifacts that you complain about OpenSSL; for example, a truly random 16 byte output would have 9 or repeated hex digits once every circa 370000 outputs. So, yes, if you go through enough of them, you would expect to see such extreme cases (and 'enough' needn't be that many...)
– poncho
3 hours ago
1
1
You're falling into a trap. I recall a complaint that consecutive second factor codes repeated a few digits and so it was not truly random. Something like "182345" and "405346" - there's a repeat of "34". Just because something stands out to you does not mean it is not random. Humans are great at seeing patterns including the ones that don't exist.
– iheanyi
2 hours ago
You're falling into a trap. I recall a complaint that consecutive second factor codes repeated a few digits and so it was not truly random. Something like "182345" and "405346" - there's a repeat of "34". Just because something stands out to you does not mean it is not random. Humans are great at seeing patterns including the ones that don't exist.
– iheanyi
2 hours ago
If you're suggesting that OpenSSL's PRNG is inadequate because it shows patterns, then this answer needs to be improved by including an analysis showing that the patterns are statistically significant.
– Tanner Swett
1 hour ago
If you're suggesting that OpenSSL's PRNG is inadequate because it shows patterns, then this answer needs to be improved by including an analysis showing that the patterns are statistically significant.
– Tanner Swett
1 hour ago
I agree that seeing "34" like that in two outputs would be "reading a lot into it." But if you see "34" in 6 out of 6 outputs, I'd say you've reduced your brute force effort by a factor of 100. Of course, you're betting that the 7th will have a "34" and it's always possible that it was just pure randomness (I understand the counterintuitive qualities of pure random values). I'm just saying that if I were designing a PRNG system, I would work hard to avoid such coincidences. And yes, I know how naive that sounds. Sorry about the lack of math proof.
– James Huddle
9 mins ago
I agree that seeing "34" like that in two outputs would be "reading a lot into it." But if you see "34" in 6 out of 6 outputs, I'd say you've reduced your brute force effort by a factor of 100. Of course, you're betting that the 7th will have a "34" and it's always possible that it was just pure randomness (I understand the counterintuitive qualities of pure random values). I'm just saying that if I were designing a PRNG system, I would work hard to avoid such coincidences. And yes, I know how naive that sounds. Sorry about the lack of math proof.
– James Huddle
9 mins ago
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcrypto.stackexchange.com%2fquestions%2f62736%2fhow-fast-does-a-pseudrandom-number-generator-have-to-be-in-order-to-be-competiti%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
