Is this test result sufficient to steer clear from this RNG for cryptographic applications?
$begingroup$
I'm not really interested in this PRNG. I'm more interested in understanding what it takes to fail the security threshold for cryptographic applications. I'm taking the C PRNG as an example.
#include <stdio.h>
#include <stdlib.h>
int main(void)
{
unsigned int random;
srand(1);
for (;;) {
random = rand();
fwrite(&random, sizeof random, 1, stdout);
}
}
Here's the summary of a small crush by TestU01:
========= Summary results of SmallCrush =========
Version: TestU01 1.2.3
Generator: crand
Number of statistics: 15
Total CPU time: 00:00:21.67
The following tests gave p-values outside [0.001, 0.9990]:
(eps means a value < 1.0e-300):
(eps1 means a value < 1.0e-15):
Test p-value
----------------------------------------------
1 BirthdaySpacings 1.1e-14
2 Collision eps
3 Gap 4.2e-9
6 MaxOft eps
6 MaxOft AD 1 - eps1
7 WeightDistrib eps
10 RandomWalk1 H eps
10 RandomWalk1 M eps
10 RandomWalk1 J eps
10 RandomWalk1 R eps
10 RandomWalk1 C eps
----------------------------------------------
All other tests were passed
Is this enough to make me steer clear from C's rand()? What if it had failed only a single test?
pseudo-random-generator
asked Nov 14 '18 at 13:30
user45491user45491
867
$endgroup$
add a comment |
$begingroup$
I'm not really interested in this PRNG. I'm more interested in understanding what it takes to fail the security threshold for cryptographic applications. I'm taking the C PRNG as an example.
#include <stdio.h>
#include <stdlib.h>
int main(void)
{
unsigned int random;
srand(1);
for (;;) {
random = rand();
fwrite(&random, sizeof random, 1, stdout);
}
}
Here's the summary of a small crush by TestU01:
========= Summary results of SmallCrush =========
Version: TestU01 1.2.3
Generator: crand
Number of statistics: 15
Total CPU time: 00:00:21.67
The following tests gave p-values outside [0.001, 0.9990]:
(eps means a value < 1.0e-300):
(eps1 means a value < 1.0e-15):
Test p-value
----------------------------------------------
1 BirthdaySpacings 1.1e-14
2 Collision eps
3 Gap 4.2e-9
6 MaxOft eps
6 MaxOft AD 1 - eps1
7 WeightDistrib eps
10 RandomWalk1 H eps
10 RandomWalk1 M eps
10 RandomWalk1 J eps
10 RandomWalk1 R eps
10 RandomWalk1 C eps
----------------------------------------------
All other tests were passed
Is this enough to make me steer clear from C's rand()? What if it had failed only a single test?
pseudo-random-generator
asked Nov 14 '18 at 13:30
user45491user45491
867
$endgroup$
2
$begingroup$
@fgrieu said it first. A statistical test can only fail a CSPRNG, it can never tell us that a CSPRNG is safe. Passing such tests is really easy. CSPRNGs need be more random by many orders of magnitude. They also must not reveal information about their seed, past outputs, future outputs, or internal state even if a hacker can see lots of the RNG's output.
$endgroup$
– Future Security
Nov 14 '18 at 18:06
$begingroup$
@poncho's answer is correct, but even if you do this test correctly, the rand implementation will still fail miserably: it's similar to the LCG entries at pcg-random.org/statistical-tests.html#id2
$endgroup$
– user60561
Nov 14 '18 at 21:18
$begingroup$
As an aside from your test results: C'srand()isn't necessarily always the same algorithm, so even if it is found to be cryptographically safe on your current system it might not be on another system your code is later compile on. Never assume something has properties that it doesn't make any claim to have: the standards forrand()make no claim or requirement for the algorithm used to meet any cryptographically relevant standard.
$endgroup$
– David Spillett
Nov 15 '18 at 10:46
add a comment |
$begingroup$
I'm not really interested in this PRNG. I'm more interested in understanding what it takes to fail the security threshold for cryptographic applications. I'm taking the C PRNG as an example.
#include <stdio.h>
#include <stdlib.h>
int main(void)
{
unsigned int random;
srand(1);
for (;;) {
random = rand();
fwrite(&random, sizeof random, 1, stdout);
}
}
Here's the summary of a small crush by TestU01:
========= Summary results of SmallCrush =========
Version: TestU01 1.2.3
Generator: crand
Number of statistics: 15
Total CPU time: 00:00:21.67
The following tests gave p-values outside [0.001, 0.9990]:
(eps means a value < 1.0e-300):
(eps1 means a value < 1.0e-15):
Test p-value
----------------------------------------------
1 BirthdaySpacings 1.1e-14
2 Collision eps
3 Gap 4.2e-9
6 MaxOft eps
6 MaxOft AD 1 - eps1
7 WeightDistrib eps
10 RandomWalk1 H eps
10 RandomWalk1 M eps
10 RandomWalk1 J eps
10 RandomWalk1 R eps
10 RandomWalk1 C eps
----------------------------------------------
All other tests were passed
Is this enough to make me steer clear from C's rand()? What if it had failed only a single test?
pseudo-random-generator
asked Nov 14 '18 at 13:30
user45491user45491
867
$endgroup$
I'm not really interested in this PRNG. I'm more interested in understanding what it takes to fail the security threshold for cryptographic applications. I'm taking the C PRNG as an example.
#include <stdio.h>
#include <stdlib.h>
int main(void)
{
unsigned int random;
srand(1);
for (;;) {
random = rand();
fwrite(&random, sizeof random, 1, stdout);
}
}
Here's the summary of a small crush by TestU01:
========= Summary results of SmallCrush =========
Version: TestU01 1.2.3
Generator: crand
Number of statistics: 15
Total CPU time: 00:00:21.67
The following tests gave p-values outside [0.001, 0.9990]:
(eps means a value < 1.0e-300):
(eps1 means a value < 1.0e-15):
Test p-value
----------------------------------------------
1 BirthdaySpacings 1.1e-14
2 Collision eps
3 Gap 4.2e-9
6 MaxOft eps
6 MaxOft AD 1 - eps1
7 WeightDistrib eps
10 RandomWalk1 H eps
10 RandomWalk1 M eps
10 RandomWalk1 J eps
10 RandomWalk1 R eps
10 RandomWalk1 C eps
----------------------------------------------
All other tests were passed
Is this enough to make me steer clear from C's rand()? What if it had failed only a single test?
pseudo-random-generator
pseudo-random-generator
asked Nov 14 '18 at 13:30
user45491user45491
867
asked Nov 14 '18 at 13:30
user45491user45491
867
asked Nov 14 '18 at 13:30
user45491user45491
867
asked Nov 14 '18 at 13:30
user45491user45491
867
asked Nov 14 '18 at 13:30
user45491user45491
867
867
2
$begingroup$
@fgrieu said it first. A statistical test can only fail a CSPRNG, it can never tell us that a CSPRNG is safe. Passing such tests is really easy. CSPRNGs need be more random by many orders of magnitude. They also must not reveal information about their seed, past outputs, future outputs, or internal state even if a hacker can see lots of the RNG's output.
$endgroup$
– Future Security
Nov 14 '18 at 18:06
$begingroup$
@poncho's answer is correct, but even if you do this test correctly, the rand implementation will still fail miserably: it's similar to the LCG entries at pcg-random.org/statistical-tests.html#id2
$endgroup$
– user60561
Nov 14 '18 at 21:18
$begingroup$
As an aside from your test results: C'srand()isn't necessarily always the same algorithm, so even if it is found to be cryptographically safe on your current system it might not be on another system your code is later compile on. Never assume something has properties that it doesn't make any claim to have: the standards forrand()make no claim or requirement for the algorithm used to meet any cryptographically relevant standard.
$endgroup$
– David Spillett
Nov 15 '18 at 10:46
add a comment |
2
$begingroup$
@fgrieu said it first. A statistical test can only fail a CSPRNG, it can never tell us that a CSPRNG is safe. Passing such tests is really easy. CSPRNGs need be more random by many orders of magnitude. They also must not reveal information about their seed, past outputs, future outputs, or internal state even if a hacker can see lots of the RNG's output.
$endgroup$
– Future Security
Nov 14 '18 at 18:06
$begingroup$
@poncho's answer is correct, but even if you do this test correctly, the rand implementation will still fail miserably: it's similar to the LCG entries at pcg-random.org/statistical-tests.html#id2
$endgroup$
– user60561
Nov 14 '18 at 21:18
$begingroup$
As an aside from your test results: C'srand()isn't necessarily always the same algorithm, so even if it is found to be cryptographically safe on your current system it might not be on another system your code is later compile on. Never assume something has properties that it doesn't make any claim to have: the standards forrand()make no claim or requirement for the algorithm used to meet any cryptographically relevant standard.
$endgroup$
– David Spillett
Nov 15 '18 at 10:46
2
2
$begingroup$
@fgrieu said it first. A statistical test can only fail a CSPRNG, it can never tell us that a CSPRNG is safe. Passing such tests is really easy. CSPRNGs need be more random by many orders of magnitude. They also must not reveal information about their seed, past outputs, future outputs, or internal state even if a hacker can see lots of the RNG's output.
$endgroup$
– Future Security
Nov 14 '18 at 18:06
$begingroup$
@fgrieu said it first. A statistical test can only fail a CSPRNG, it can never tell us that a CSPRNG is safe. Passing such tests is really easy. CSPRNGs need be more random by many orders of magnitude. They also must not reveal information about their seed, past outputs, future outputs, or internal state even if a hacker can see lots of the RNG's output.
$endgroup$
– Future Security
Nov 14 '18 at 18:06
$begingroup$
@poncho's answer is correct, but even if you do this test correctly, the rand implementation will still fail miserably: it's similar to the LCG entries at pcg-random.org/statistical-tests.html#id2
$endgroup$
– user60561
Nov 14 '18 at 21:18
$begingroup$
@poncho's answer is correct, but even if you do this test correctly, the rand implementation will still fail miserably: it's similar to the LCG entries at pcg-random.org/statistical-tests.html#id2
$endgroup$
– user60561
Nov 14 '18 at 21:18
$begingroup$
As an aside from your test results: C's
rand() isn't necessarily always the same algorithm, so even if it is found to be cryptographically safe on your current system it might not be on another system your code is later compile on. Never assume something has properties that it doesn't make any claim to have: the standards for rand() make no claim or requirement for the algorithm used to meet any cryptographically relevant standard.$endgroup$
– David Spillett
Nov 15 '18 at 10:46
$begingroup$
As an aside from your test results: C's
rand() isn't necessarily always the same algorithm, so even if it is found to be cryptographically safe on your current system it might not be on another system your code is later compile on. Never assume something has properties that it doesn't make any claim to have: the standards for rand() make no claim or requirement for the algorithm used to meet any cryptographically relevant standard.$endgroup$
– David Spillett
Nov 15 '18 at 10:46
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
Actually, this case is a misapplied test. rand() is defined to generate numbers between 0 and RAND_MAX, which is a compiler-defined constant which is positive as an int. That means that the range of possible results $[0..RAND_MAX]$ is strictly smaller than the range of results you are writing $[0..UINT_MAX]$. For example, if you are on a machine with 32 bit int's, then the msbit for every value you write will always be 0, that is, every 32nd bit will always be zero.
Of course the statistical tests will throw up their hands at that; obviously, real random outputs won't do that. However, that's not the fault of rand(), instead, it is the fault of how you're using it.
Now, to address your question:
I'm more interested in understanding what it takes to fail the security threshold for cryptographic applications
Statistical tests don't tell you much; hard failures are an indication that something may be up (or you're misapplying the test, as is the case here); however:
Any such PRNG would need a good entropy source; rand() only allows srand(), which allows a single (unsigned int) as input; that's not sufficient
Any such PRNG should be designed and analyzed as giving an indistinguishable output; rand() implementations rarely are...
answered Nov 14 '18 at 14:02
ponchoponcho
92.5k2145240
$endgroup$
$begingroup$
Nice answer. 32767 fits into a 16-bit unsigned integer. In my system, that's anunsigned short int. I changed the generator accordingly and it did passSmallCrush, but it failed PractRand's `[Low1/8]DC6-9x1Bytes-1 ' with just 2^24 bytes.
$endgroup$
– user45491
Nov 15 '18 at 10:15
$begingroup$
@user45491: Same thing.USHORT_MAXis at least 65535, not 32767. So the MSB is still non-random in your setup.
$endgroup$
– MSalters
Nov 15 '18 at 13:04
$begingroup$
@MSalters, yes, I made that mistake: $32677$ is actually $2^{15} - 1$ not $2^{16} - 1$. So now I need to think: I need to hand PractRand only 15 of the 16 bits of ashort int. Not sure how to do that at the moment. (Thanks!)
$endgroup$
– user45491
Nov 15 '18 at 15:42
add a comment |
$begingroup$
No test is needed to stay clear from srand for cryptographic purposes, including when a pseudo-random generator is thought. The definition of srand is enough to disqualify it.
That definition states:
void srand(unsigned int seed);
The
srandfunction uses the argument as a seed for a new sequence of pseudo-random numbers to be returned by subsequent calls to rand. Ifsrandis then called with the same seed value, the sequence of pseudo-random numbers shall be repeated.
Problem is: the key is an int, and that's not wide enough. int is typically 32-bit, sometime 16-bit, rarely more than 64-bit, and 80-bit is a bare minimum for a modern key (we want more like 128-bit, or 192-bit when considering multi-target attacks, or 256-bit for extra peace of mind when considering the possibility of quantum computers).
Poncho beats me at first stating that the test is misapplied, since the output is not supposed to consist of uniformly random bits, which likely SmallCrush expects. Problem is,
The
randfunction computes a sequence of pseudo-random integers in the range 0 toRAND_MAX.
The value of the
RAND_MAXmacro shall be at least 32767.
and RAND_MAX is often INT_MAX. It's then likely that for sizeof(int) bytes written, one byte has its high-order bit stuck to 0, which should be caught by many statistical tests.
CSPRNGs can not be validated by statistical tests. Failure of such test only indicates (with high certainty) that the PRNG or/and test procedure is flawed (here, both are). Success does not prove anything, and indicates very little. Image: it's like validating a road bridge by having an ant cross it, when the actual things to test are high load, wind-induced oscillations and long-term corrosion of metal parts.
Also, many cryptographic applications need a True RNG (with output unpredictable from the code). That's not even touched by either srand or the test.
answered Nov 14 '18 at 14:02
fgrieufgrieu
80.4k7171338
$endgroup$
$begingroup$
Just a note that the difference between 192-bit and 256-bit is quite huge. So huge, in fact, that 256-bit is physically impossible to crack based on laws of thermodynamics.
$endgroup$
– Nelson
Nov 15 '18 at 5:48
$begingroup$
@Nelson: I do not know if the reasoning you link to applies when considering the possibility of quantum computers. Because many others do not know, and using 256-bit keys cost so little extra, it's not foolish to use that level.
$endgroup$
– fgrieu
Nov 15 '18 at 7:21
1
$begingroup$
@Nelson: The reservation was specifically about quantum computing. The linked argument hinges on the minimum energy needed for state changes, but the essential feature of quantum computing is that a system can be in a superposition of states, all at the same time.
$endgroup$
– MSalters
Nov 15 '18 at 13:09
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "281"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
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
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcrypto.stackexchange.com%2fquestions%2f64000%2fis-this-test-result-sufficient-to-steer-clear-from-this-rng-for-cryptographic-ap%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Actually, this case is a misapplied test. rand() is defined to generate numbers between 0 and RAND_MAX, which is a compiler-defined constant which is positive as an int. That means that the range of possible results $[0..RAND_MAX]$ is strictly smaller than the range of results you are writing $[0..UINT_MAX]$. For example, if you are on a machine with 32 bit int's, then the msbit for every value you write will always be 0, that is, every 32nd bit will always be zero.
Of course the statistical tests will throw up their hands at that; obviously, real random outputs won't do that. However, that's not the fault of rand(), instead, it is the fault of how you're using it.
Now, to address your question:
I'm more interested in understanding what it takes to fail the security threshold for cryptographic applications
Statistical tests don't tell you much; hard failures are an indication that something may be up (or you're misapplying the test, as is the case here); however:
Any such PRNG would need a good entropy source; rand() only allows srand(), which allows a single (unsigned int) as input; that's not sufficient
Any such PRNG should be designed and analyzed as giving an indistinguishable output; rand() implementations rarely are...
answered Nov 14 '18 at 14:02
ponchoponcho
92.5k2145240
$endgroup$
$begingroup$
Nice answer. 32767 fits into a 16-bit unsigned integer. In my system, that's anunsigned short int. I changed the generator accordingly and it did passSmallCrush, but it failed PractRand's `[Low1/8]DC6-9x1Bytes-1 ' with just 2^24 bytes.
$endgroup$
– user45491
Nov 15 '18 at 10:15
$begingroup$
@user45491: Same thing.USHORT_MAXis at least 65535, not 32767. So the MSB is still non-random in your setup.
$endgroup$
– MSalters
Nov 15 '18 at 13:04
$begingroup$
@MSalters, yes, I made that mistake: $32677$ is actually $2^{15} - 1$ not $2^{16} - 1$. So now I need to think: I need to hand PractRand only 15 of the 16 bits of ashort int. Not sure how to do that at the moment. (Thanks!)
$endgroup$
– user45491
Nov 15 '18 at 15:42
add a comment |
$begingroup$
Actually, this case is a misapplied test. rand() is defined to generate numbers between 0 and RAND_MAX, which is a compiler-defined constant which is positive as an int. That means that the range of possible results $[0..RAND_MAX]$ is strictly smaller than the range of results you are writing $[0..UINT_MAX]$. For example, if you are on a machine with 32 bit int's, then the msbit for every value you write will always be 0, that is, every 32nd bit will always be zero.
Of course the statistical tests will throw up their hands at that; obviously, real random outputs won't do that. However, that's not the fault of rand(), instead, it is the fault of how you're using it.
Now, to address your question:
I'm more interested in understanding what it takes to fail the security threshold for cryptographic applications
Statistical tests don't tell you much; hard failures are an indication that something may be up (or you're misapplying the test, as is the case here); however:
Any such PRNG would need a good entropy source; rand() only allows srand(), which allows a single (unsigned int) as input; that's not sufficient
Any such PRNG should be designed and analyzed as giving an indistinguishable output; rand() implementations rarely are...
answered Nov 14 '18 at 14:02
ponchoponcho
92.5k2145240
$endgroup$
$begingroup$
Nice answer. 32767 fits into a 16-bit unsigned integer. In my system, that's anunsigned short int. I changed the generator accordingly and it did passSmallCrush, but it failed PractRand's `[Low1/8]DC6-9x1Bytes-1 ' with just 2^24 bytes.
$endgroup$
– user45491
Nov 15 '18 at 10:15
$begingroup$
@user45491: Same thing.USHORT_MAXis at least 65535, not 32767. So the MSB is still non-random in your setup.
$endgroup$
– MSalters
Nov 15 '18 at 13:04
$begingroup$
@MSalters, yes, I made that mistake: $32677$ is actually $2^{15} - 1$ not $2^{16} - 1$. So now I need to think: I need to hand PractRand only 15 of the 16 bits of ashort int. Not sure how to do that at the moment. (Thanks!)
$endgroup$
– user45491
Nov 15 '18 at 15:42
add a comment |
$begingroup$
Actually, this case is a misapplied test. rand() is defined to generate numbers between 0 and RAND_MAX, which is a compiler-defined constant which is positive as an int. That means that the range of possible results $[0..RAND_MAX]$ is strictly smaller than the range of results you are writing $[0..UINT_MAX]$. For example, if you are on a machine with 32 bit int's, then the msbit for every value you write will always be 0, that is, every 32nd bit will always be zero.
Of course the statistical tests will throw up their hands at that; obviously, real random outputs won't do that. However, that's not the fault of rand(), instead, it is the fault of how you're using it.
Now, to address your question:
I'm more interested in understanding what it takes to fail the security threshold for cryptographic applications
Statistical tests don't tell you much; hard failures are an indication that something may be up (or you're misapplying the test, as is the case here); however:
Any such PRNG would need a good entropy source; rand() only allows srand(), which allows a single (unsigned int) as input; that's not sufficient
Any such PRNG should be designed and analyzed as giving an indistinguishable output; rand() implementations rarely are...
answered Nov 14 '18 at 14:02
ponchoponcho
92.5k2145240
$endgroup$
Actually, this case is a misapplied test. rand() is defined to generate numbers between 0 and RAND_MAX, which is a compiler-defined constant which is positive as an int. That means that the range of possible results $[0..RAND_MAX]$ is strictly smaller than the range of results you are writing $[0..UINT_MAX]$. For example, if you are on a machine with 32 bit int's, then the msbit for every value you write will always be 0, that is, every 32nd bit will always be zero.
Of course the statistical tests will throw up their hands at that; obviously, real random outputs won't do that. However, that's not the fault of rand(), instead, it is the fault of how you're using it.
Now, to address your question:
I'm more interested in understanding what it takes to fail the security threshold for cryptographic applications
Statistical tests don't tell you much; hard failures are an indication that something may be up (or you're misapplying the test, as is the case here); however:
Any such PRNG would need a good entropy source; rand() only allows srand(), which allows a single (unsigned int) as input; that's not sufficient
Any such PRNG should be designed and analyzed as giving an indistinguishable output; rand() implementations rarely are...
answered Nov 14 '18 at 14:02
ponchoponcho
92.5k2145240
answered Nov 14 '18 at 14:02
ponchoponcho
92.5k2145240
answered Nov 14 '18 at 14:02
ponchoponcho
92.5k2145240
answered Nov 14 '18 at 14:02
ponchoponcho
92.5k2145240
92.5k2145240
$begingroup$
Nice answer. 32767 fits into a 16-bit unsigned integer. In my system, that's anunsigned short int. I changed the generator accordingly and it did passSmallCrush, but it failed PractRand's `[Low1/8]DC6-9x1Bytes-1 ' with just 2^24 bytes.
$endgroup$
– user45491
Nov 15 '18 at 10:15
$begingroup$
@user45491: Same thing.USHORT_MAXis at least 65535, not 32767. So the MSB is still non-random in your setup.
$endgroup$
– MSalters
Nov 15 '18 at 13:04
$begingroup$
@MSalters, yes, I made that mistake: $32677$ is actually $2^{15} - 1$ not $2^{16} - 1$. So now I need to think: I need to hand PractRand only 15 of the 16 bits of ashort int. Not sure how to do that at the moment. (Thanks!)
$endgroup$
– user45491
Nov 15 '18 at 15:42
add a comment |
$begingroup$
Nice answer. 32767 fits into a 16-bit unsigned integer. In my system, that's anunsigned short int. I changed the generator accordingly and it did passSmallCrush, but it failed PractRand's `[Low1/8]DC6-9x1Bytes-1 ' with just 2^24 bytes.
$endgroup$
– user45491
Nov 15 '18 at 10:15
$begingroup$
@user45491: Same thing.USHORT_MAXis at least 65535, not 32767. So the MSB is still non-random in your setup.
$endgroup$
– MSalters
Nov 15 '18 at 13:04
$begingroup$
@MSalters, yes, I made that mistake: $32677$ is actually $2^{15} - 1$ not $2^{16} - 1$. So now I need to think: I need to hand PractRand only 15 of the 16 bits of ashort int. Not sure how to do that at the moment. (Thanks!)
$endgroup$
– user45491
Nov 15 '18 at 15:42
$begingroup$
Nice answer. 32767 fits into a 16-bit unsigned integer. In my system, that's an
unsigned short int. I changed the generator accordingly and it did pass SmallCrush, but it failed PractRand's `[Low1/8]DC6-9x1Bytes-1 ' with just 2^24 bytes.$endgroup$
– user45491
Nov 15 '18 at 10:15
$begingroup$
Nice answer. 32767 fits into a 16-bit unsigned integer. In my system, that's an
unsigned short int. I changed the generator accordingly and it did pass SmallCrush, but it failed PractRand's `[Low1/8]DC6-9x1Bytes-1 ' with just 2^24 bytes.$endgroup$
– user45491
Nov 15 '18 at 10:15
$begingroup$
@user45491: Same thing.
USHORT_MAX is at least 65535, not 32767. So the MSB is still non-random in your setup.$endgroup$
– MSalters
Nov 15 '18 at 13:04
$begingroup$
@user45491: Same thing.
USHORT_MAX is at least 65535, not 32767. So the MSB is still non-random in your setup.$endgroup$
– MSalters
Nov 15 '18 at 13:04
$begingroup$
@MSalters, yes, I made that mistake: $32677$ is actually $2^{15} - 1$ not $2^{16} - 1$. So now I need to think: I need to hand PractRand only 15 of the 16 bits of a
short int. Not sure how to do that at the moment. (Thanks!)$endgroup$
– user45491
Nov 15 '18 at 15:42
$begingroup$
@MSalters, yes, I made that mistake: $32677$ is actually $2^{15} - 1$ not $2^{16} - 1$. So now I need to think: I need to hand PractRand only 15 of the 16 bits of a
short int. Not sure how to do that at the moment. (Thanks!)$endgroup$
– user45491
Nov 15 '18 at 15:42
add a comment |
$begingroup$
No test is needed to stay clear from srand for cryptographic purposes, including when a pseudo-random generator is thought. The definition of srand is enough to disqualify it.
That definition states:
void srand(unsigned int seed);
The
srandfunction uses the argument as a seed for a new sequence of pseudo-random numbers to be returned by subsequent calls to rand. Ifsrandis then called with the same seed value, the sequence of pseudo-random numbers shall be repeated.
Problem is: the key is an int, and that's not wide enough. int is typically 32-bit, sometime 16-bit, rarely more than 64-bit, and 80-bit is a bare minimum for a modern key (we want more like 128-bit, or 192-bit when considering multi-target attacks, or 256-bit for extra peace of mind when considering the possibility of quantum computers).
Poncho beats me at first stating that the test is misapplied, since the output is not supposed to consist of uniformly random bits, which likely SmallCrush expects. Problem is,
The
randfunction computes a sequence of pseudo-random integers in the range 0 toRAND_MAX.
The value of the
RAND_MAXmacro shall be at least 32767.
and RAND_MAX is often INT_MAX. It's then likely that for sizeof(int) bytes written, one byte has its high-order bit stuck to 0, which should be caught by many statistical tests.
CSPRNGs can not be validated by statistical tests. Failure of such test only indicates (with high certainty) that the PRNG or/and test procedure is flawed (here, both are). Success does not prove anything, and indicates very little. Image: it's like validating a road bridge by having an ant cross it, when the actual things to test are high load, wind-induced oscillations and long-term corrosion of metal parts.
Also, many cryptographic applications need a True RNG (with output unpredictable from the code). That's not even touched by either srand or the test.
answered Nov 14 '18 at 14:02
fgrieufgrieu
80.4k7171338
$endgroup$
$begingroup$
Just a note that the difference between 192-bit and 256-bit is quite huge. So huge, in fact, that 256-bit is physically impossible to crack based on laws of thermodynamics.
$endgroup$
– Nelson
Nov 15 '18 at 5:48
$begingroup$
@Nelson: I do not know if the reasoning you link to applies when considering the possibility of quantum computers. Because many others do not know, and using 256-bit keys cost so little extra, it's not foolish to use that level.
$endgroup$
– fgrieu
Nov 15 '18 at 7:21
1
$begingroup$
@Nelson: The reservation was specifically about quantum computing. The linked argument hinges on the minimum energy needed for state changes, but the essential feature of quantum computing is that a system can be in a superposition of states, all at the same time.
$endgroup$
– MSalters
Nov 15 '18 at 13:09
add a comment |
$begingroup$
No test is needed to stay clear from srand for cryptographic purposes, including when a pseudo-random generator is thought. The definition of srand is enough to disqualify it.
That definition states:
void srand(unsigned int seed);
The
srandfunction uses the argument as a seed for a new sequence of pseudo-random numbers to be returned by subsequent calls to rand. Ifsrandis then called with the same seed value, the sequence of pseudo-random numbers shall be repeated.
Problem is: the key is an int, and that's not wide enough. int is typically 32-bit, sometime 16-bit, rarely more than 64-bit, and 80-bit is a bare minimum for a modern key (we want more like 128-bit, or 192-bit when considering multi-target attacks, or 256-bit for extra peace of mind when considering the possibility of quantum computers).
Poncho beats me at first stating that the test is misapplied, since the output is not supposed to consist of uniformly random bits, which likely SmallCrush expects. Problem is,
The
randfunction computes a sequence of pseudo-random integers in the range 0 toRAND_MAX.
The value of the
RAND_MAXmacro shall be at least 32767.
and RAND_MAX is often INT_MAX. It's then likely that for sizeof(int) bytes written, one byte has its high-order bit stuck to 0, which should be caught by many statistical tests.
CSPRNGs can not be validated by statistical tests. Failure of such test only indicates (with high certainty) that the PRNG or/and test procedure is flawed (here, both are). Success does not prove anything, and indicates very little. Image: it's like validating a road bridge by having an ant cross it, when the actual things to test are high load, wind-induced oscillations and long-term corrosion of metal parts.
Also, many cryptographic applications need a True RNG (with output unpredictable from the code). That's not even touched by either srand or the test.
answered Nov 14 '18 at 14:02
fgrieufgrieu
80.4k7171338
$endgroup$
$begingroup$
Just a note that the difference between 192-bit and 256-bit is quite huge. So huge, in fact, that 256-bit is physically impossible to crack based on laws of thermodynamics.
$endgroup$
– Nelson
Nov 15 '18 at 5:48
$begingroup$
@Nelson: I do not know if the reasoning you link to applies when considering the possibility of quantum computers. Because many others do not know, and using 256-bit keys cost so little extra, it's not foolish to use that level.
$endgroup$
– fgrieu
Nov 15 '18 at 7:21
1
$begingroup$
@Nelson: The reservation was specifically about quantum computing. The linked argument hinges on the minimum energy needed for state changes, but the essential feature of quantum computing is that a system can be in a superposition of states, all at the same time.
$endgroup$
– MSalters
Nov 15 '18 at 13:09
add a comment |
$begingroup$
No test is needed to stay clear from srand for cryptographic purposes, including when a pseudo-random generator is thought. The definition of srand is enough to disqualify it.
That definition states:
void srand(unsigned int seed);
The
srandfunction uses the argument as a seed for a new sequence of pseudo-random numbers to be returned by subsequent calls to rand. Ifsrandis then called with the same seed value, the sequence of pseudo-random numbers shall be repeated.
Problem is: the key is an int, and that's not wide enough. int is typically 32-bit, sometime 16-bit, rarely more than 64-bit, and 80-bit is a bare minimum for a modern key (we want more like 128-bit, or 192-bit when considering multi-target attacks, or 256-bit for extra peace of mind when considering the possibility of quantum computers).
Poncho beats me at first stating that the test is misapplied, since the output is not supposed to consist of uniformly random bits, which likely SmallCrush expects. Problem is,
The
randfunction computes a sequence of pseudo-random integers in the range 0 toRAND_MAX.
The value of the
RAND_MAXmacro shall be at least 32767.
and RAND_MAX is often INT_MAX. It's then likely that for sizeof(int) bytes written, one byte has its high-order bit stuck to 0, which should be caught by many statistical tests.
CSPRNGs can not be validated by statistical tests. Failure of such test only indicates (with high certainty) that the PRNG or/and test procedure is flawed (here, both are). Success does not prove anything, and indicates very little. Image: it's like validating a road bridge by having an ant cross it, when the actual things to test are high load, wind-induced oscillations and long-term corrosion of metal parts.
Also, many cryptographic applications need a True RNG (with output unpredictable from the code). That's not even touched by either srand or the test.
answered Nov 14 '18 at 14:02
fgrieufgrieu
80.4k7171338
$endgroup$
No test is needed to stay clear from srand for cryptographic purposes, including when a pseudo-random generator is thought. The definition of srand is enough to disqualify it.
That definition states:
void srand(unsigned int seed);
The
srandfunction uses the argument as a seed for a new sequence of pseudo-random numbers to be returned by subsequent calls to rand. Ifsrandis then called with the same seed value, the sequence of pseudo-random numbers shall be repeated.
Problem is: the key is an int, and that's not wide enough. int is typically 32-bit, sometime 16-bit, rarely more than 64-bit, and 80-bit is a bare minimum for a modern key (we want more like 128-bit, or 192-bit when considering multi-target attacks, or 256-bit for extra peace of mind when considering the possibility of quantum computers).
Poncho beats me at first stating that the test is misapplied, since the output is not supposed to consist of uniformly random bits, which likely SmallCrush expects. Problem is,
The
randfunction computes a sequence of pseudo-random integers in the range 0 toRAND_MAX.
The value of the
RAND_MAXmacro shall be at least 32767.
and RAND_MAX is often INT_MAX. It's then likely that for sizeof(int) bytes written, one byte has its high-order bit stuck to 0, which should be caught by many statistical tests.
CSPRNGs can not be validated by statistical tests. Failure of such test only indicates (with high certainty) that the PRNG or/and test procedure is flawed (here, both are). Success does not prove anything, and indicates very little. Image: it's like validating a road bridge by having an ant cross it, when the actual things to test are high load, wind-induced oscillations and long-term corrosion of metal parts.
Also, many cryptographic applications need a True RNG (with output unpredictable from the code). That's not even touched by either srand or the test.
answered Nov 14 '18 at 14:02
fgrieufgrieu
80.4k7171338
edited Nov 14 '18 at 23:04
answered Nov 14 '18 at 14:02
fgrieufgrieu
80.4k7171338
answered Nov 14 '18 at 14:02
fgrieufgrieu
80.4k7171338
answered Nov 14 '18 at 14:02
fgrieufgrieu
80.4k7171338
80.4k7171338
$begingroup$
Just a note that the difference between 192-bit and 256-bit is quite huge. So huge, in fact, that 256-bit is physically impossible to crack based on laws of thermodynamics.
$endgroup$
– Nelson
Nov 15 '18 at 5:48
$begingroup$
@Nelson: I do not know if the reasoning you link to applies when considering the possibility of quantum computers. Because many others do not know, and using 256-bit keys cost so little extra, it's not foolish to use that level.
$endgroup$
– fgrieu
Nov 15 '18 at 7:21
1
$begingroup$
@Nelson: The reservation was specifically about quantum computing. The linked argument hinges on the minimum energy needed for state changes, but the essential feature of quantum computing is that a system can be in a superposition of states, all at the same time.
$endgroup$
– MSalters
Nov 15 '18 at 13:09
add a comment |
$begingroup$
Just a note that the difference between 192-bit and 256-bit is quite huge. So huge, in fact, that 256-bit is physically impossible to crack based on laws of thermodynamics.
$endgroup$
– Nelson
Nov 15 '18 at 5:48
$begingroup$
@Nelson: I do not know if the reasoning you link to applies when considering the possibility of quantum computers. Because many others do not know, and using 256-bit keys cost so little extra, it's not foolish to use that level.
$endgroup$
– fgrieu
Nov 15 '18 at 7:21
1
$begingroup$
@Nelson: The reservation was specifically about quantum computing. The linked argument hinges on the minimum energy needed for state changes, but the essential feature of quantum computing is that a system can be in a superposition of states, all at the same time.
$endgroup$
– MSalters
Nov 15 '18 at 13:09
$begingroup$
Just a note that the difference between 192-bit and 256-bit is quite huge. So huge, in fact, that 256-bit is physically impossible to crack based on laws of thermodynamics.
$endgroup$
– Nelson
Nov 15 '18 at 5:48
$begingroup$
Just a note that the difference between 192-bit and 256-bit is quite huge. So huge, in fact, that 256-bit is physically impossible to crack based on laws of thermodynamics.
$endgroup$
– Nelson
Nov 15 '18 at 5:48
$begingroup$
@Nelson: I do not know if the reasoning you link to applies when considering the possibility of quantum computers. Because many others do not know, and using 256-bit keys cost so little extra, it's not foolish to use that level.
$endgroup$
– fgrieu
Nov 15 '18 at 7:21
$begingroup$
@Nelson: I do not know if the reasoning you link to applies when considering the possibility of quantum computers. Because many others do not know, and using 256-bit keys cost so little extra, it's not foolish to use that level.
$endgroup$
– fgrieu
Nov 15 '18 at 7:21
1
1
$begingroup$
@Nelson: The reservation was specifically about quantum computing. The linked argument hinges on the minimum energy needed for state changes, but the essential feature of quantum computing is that a system can be in a superposition of states, all at the same time.
$endgroup$
– MSalters
Nov 15 '18 at 13:09
$begingroup$
@Nelson: The reservation was specifically about quantum computing. The linked argument hinges on the minimum energy needed for state changes, but the essential feature of quantum computing is that a system can be in a superposition of states, all at the same time.
$endgroup$
– MSalters
Nov 15 '18 at 13:09
add a comment |
Thanks for contributing an answer to Cryptography Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
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
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcrypto.stackexchange.com%2fquestions%2f64000%2fis-this-test-result-sufficient-to-steer-clear-from-this-rng-for-cryptographic-ap%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
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
Required, but never shown
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
Required, but never shown
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
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
2
$begingroup$
@fgrieu said it first. A statistical test can only fail a CSPRNG, it can never tell us that a CSPRNG is safe. Passing such tests is really easy. CSPRNGs need be more random by many orders of magnitude. They also must not reveal information about their seed, past outputs, future outputs, or internal state even if a hacker can see lots of the RNG's output.
$endgroup$
– Future Security
Nov 14 '18 at 18:06
$begingroup$
@poncho's answer is correct, but even if you do this test correctly, the rand implementation will still fail miserably: it's similar to the LCG entries at pcg-random.org/statistical-tests.html#id2
$endgroup$
– user60561
Nov 14 '18 at 21:18
$begingroup$
As an aside from your test results: C's
rand()isn't necessarily always the same algorithm, so even if it is found to be cryptographically safe on your current system it might not be on another system your code is later compile on. Never assume something has properties that it doesn't make any claim to have: the standards forrand()make no claim or requirement for the algorithm used to meet any cryptographically relevant standard.$endgroup$
– David Spillett
Nov 15 '18 at 10:46