Re: Randomness testing Was: On the randomness of DNS
On Aug 3, 2008, at 13:54, Alexander Klimov wrote: If your p-value is smaller than the significance level (say, 1%) you should repeat the test with different data and see if the test persistently fails or it was just a fluke. Or better still, make many tests and see if your p-values are uniformly distributed in (0,1). [Hint: decide on a p-value for that last equidistribution test *before* you compute that p-value.] Best, Stephan - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Randomness testing Was: On the randomness of DNS
On Mon, 4 Aug 2008, Stephan Neuhaus wrote: Or better still, make many tests and see if your p-values are uniformly distributed in (0,1). [Hint: decide on a p-value for that last equidistribution test *before* you compute that p-value.] Of course, there are many tests for goodness of fit (Kolmogorov- Smirnov, chi-square, etc.) and also you can calculate for a given number of tests how many tests should have p-value below the significance level. And after making hundred tests you ask yourself what you gonna do once your test gives good uniformity, say p-value is 0.23, but the proportion is 0.95, while the minimum pass rate for 1% is 0.96. Only a bad statistician cannot justify any predefined answer :-) -- Regards, ASK - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: On the randomness of DNS
Hi Ben, http://www.cacert.at/cgi-bin/rngresults Are you seriously saying that the entropy of FreeBSD /dev/random is 0? Thanks for the notice, that was a broken upload by a user. Best regards, Philipp Gühring - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Randomness testing Was: On the randomness of DNS
On Thu, 31 Jul 2008, Pierre-Evariste Dagand wrote: Just by curiosity, I ran the Diehard tests[...] Sum-up for /dev/random: Abnormally high value: 0.993189 [1] Abnormally low value: 0.010507 [1] Total: 2 Sum up for Sha1(n): Abnormally high values: 0.938376, 0.927501 [2] Abnormally low values: 0.087107, 0.091750, 0.060212, 0.050921 [4] Total: 6 So, I would say that Sha1(n) does not pass DieHard (while /dev/random does). But this would require further examination, in particular to understand why some tests failed. And, in fact, I have no clue why they failed... See http://en.wikipedia.org/wiki/P-value. Since p-value is supposed to be uniform on the interval [0,1] for a truly random source, it is no wonder that with so many p-values some of them are close to 0 and some are close to 1. If your p-value is smaller than the significance level (say, 1%) you should repeat the test with different data and see if the test persistently fails or it was just a fluke. -- Regards, ASK - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: On the randomness of DNS
SHA-1(1), SHA-1(2), SHA-1(3), ... SHA-1(N) will look random, but clearly is not. Just by curiosity, I ran the Diehard tests on /dev/random (FreeBSD 7.0) and a sha1 sequence of [ 1 ... N ]. Both random files are 63 Mb. I know that there has been some controversy about /dev/random of FreeBSD on this list in the past, I don't know if the issues has been solved, though. I do not have any other OS at hand right now. To interpret the results, quoting DieHard presentation: Most of the tests in DIEHARD return a p-value, which should be uniform on [0,1) if the input file contains truly independent random bits. Those p-values are obtained by p=1-F(X), where F is the assumed distribution of the sample random variable X---often normal. But that assumed F is often just an asymptotic approximation, for which the fit will be worst in the tails. Thus you should not be surprised with occasion- al p-values near 0 or 1, such as .0012 or .9983. When a bit stream really FAILS BIG, you will get p`s of 0 or 1 to six or more places. By all means, do not, as a Statistician might, think that a p .025 or p .975 means that the RNG has failed the test at the .05 level. Such p`s happen among the hundreds that DIEHARD produces, even with good RNGs. So keep in mind that p happens For /dev/random, I get: Birthday spacing: 0.323220 Overlapping 5-permutations:0.483655 0.215005 Binary rank: 0.405667 Count the 1's:0.379616 Parking lot:0.993189 Minimum distance:0.580824 3D-spheres: 0.616398 Squeeze: 0.195228 Overlapping sums:0.010507 Runs: 0.233353 0.274341 0.719427 0.749529 Craps:0.480129 0.650224 Sum-up for /dev/random: Abnormally high value: 0.993189 [1] Abnormally low value: 0.010507 [1] Total: 2 For sha1(n), I get: Birthday spacing: 0.810196 Overlapping 5-permutations: 0.717577 0.645166 Binary rank:0.891962 Count the 1's: 0.377828 Parking lot: 0.188993 Minimum distance: 0.138668 3D-spheres:0.087107 Squeeze:0.377509 Overlapping sums: 0.091750 Runs: 0.938376 0.060212 0.050921 0.210624 Craps: 0.927501 0.827696 Sum up for Sha1(n): Abnormally high values: 0.938376, 0.927501 [2] Abnormally low values: 0.087107, 0.091750, 0.060212, 0.050921 [4] Total: 6 So, I would say that Sha1(n) does not pass DieHard (while /dev/random does). But this would require further examination, in particular to understand why some tests failed. And, in fact, I have no clue why they failed... Regards, -- Pierre-Evariste DAGAND http://perso.eleves.bretagne.ens-cachan.fr/~dagand/ - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: On the randomness of DNS
Ben wrote: But just how GREAT is that, really? Well, we don' t know. Why? Because there isn't actually a way test for randomness. Your DNS resolver could be using some easily predicted random number generator like, say, a linear congruential one, as is common in the rand() library function, but DNS-OARC would still say it was GREAT. At 11:57 AM 7/30/2008, Pierre-Evariste Dagand wrote: Well, they are some tests to judge the quality of a random number generator. The best known being the Diehard tests: Random number quality is contextual. In this case, for 95-99% of the market, the real test is between Patched Badly Broken Not patched yet Didn't need patching, and if you'd prefer the term Best we can do until DNSSEC instead of GREAT I won't be the one to argue with you. There are some other possible conditions, like Rolled their own with open source, badly or Maliciously subtle malware DNS resolver. The latter is way too much work compared to cruder approaches (like targeting queries directly to your evil DNS server). The former is not too common, though it probably exists, but once most systems get patched, it may not be a big enough target to interest crackers. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: On the randomness of DNS
Dirk-Willem van Gulik wrote: I fail to see how you could evaluate this without seeing the code (and even then - I doubt that one can properly do this -- the ?old? NSA habit of tweaking your random generated rather than your protocol/algorithm when they wanted your produced upgraded to export quality - is terribly effective and very hard to spot). Or am I missing something ? I think that, in general, you are correct. However, in the case of NAT your adversary is not someone who is trying to guess your randomness, but someone who is trying to sell you their NAT gateway. In this case, code/silicon inspection probably suffices. Cheers, Ben. -- http://www.apache-ssl.org/ben.html http://www.links.org/ There is no limit to what a man can do or how far he can go if he doesn't mind who gets the credit. - Robert Woodruff - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: On the randomness of DNS
Hi, I would suggest to use http://www.cacert.at/random/ to test the randomness of the DNS source ports. Due to the large variety of random-number sources that have been tested there already, it's useful as a classification service of unknown randomly looking numbers. You just have to collect 12 MB of numbers from a DNS server and upload it there. (If you get 2 Bytes per request, that's 6 million requests you have to do) I don't see the point of evaluating the quality of a random number generator by statistical tests. We successfully used statistical tests to detect broken random number generators, we informed the vendors and they fixed them. http://www.cacert.at/cgi-bin/rngresults Best regards, Philipp Gühring - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
On the randomness of DNS
I thought this list might be interested in a mini-rant about DNS source port randomness on my blog: http://www.links.org/?p=352. Ever since the recent DNS alert people have been testing their DNS servers with various cute things that measure how many source ports you use, and how random they are. Not forgetting the command line versions, of course dig +short porttest.dns-oarc.net TXT dig +short txidtest.dns-oarc.net TXT which yield output along the lines of aaa.bbb.ccc.ddd is GREAT: 27 queries in 12.7 seconds from 27 ports with std dev 15253 But just how GREAT is that, really? Well, we don' t know. Why? Because there isn't actually a way test for randomness. Your DNS resolver could be using some easily predicted random number generator like, say, a linear congruential one, as is common in the rand() library function, but DNS-OARC would still say it was GREAT. Believe them when they say it isn't GREAT, though! Non-randomness we can test for. So, how do you tell? The only way to know for sure is to review the code (or the silicon, see below). If someone tells you don't worry, we did statistical checks and it's random then make sure you're holding on to your wallet - he'll be selling you a bridge next. But, you may say, we already know all the major caching resolvers have been patched and use decent randomness, so why is this an issue? It is an issue because of NAT. If your resolver lives behind NAT (which is probably way more common since this alert, as many people's reactions [mine included] was to stop using their ISP's nameservers and stand up their own to resolve directly for them) and the NAT is doing source port translation (quite likely), then you are relying on the NAT gateway to provide your randomness. But random ports are not the best strategy for NAT. They want to avoid re-using ports too soon, so they tend to use an LRU queue instead. Pretty clearly an LRU queue can be probed and manipulated into predictability. So, if your NAT vendor is telling you not to worry, because the statistics say they are random, then I would start worrying a lot: your NAT vendor doesn't understand the problem. It's also pretty unhelpful for the various testers out there not to mention this issue, I must say. Incidentally, I'm curious how much this has impacted the DNS infrastructure in terms of traffic - anyone out there got some statistics? Oh, and I should say that number of ports and standard deviation are not a GREAT way to test for randomness. For example, the sequence 1000, 2000, ..., 27000 has 27 ports and a standard deviation of over 7500, which looks pretty GREAT to me. But not very random. -- http://www.apache-ssl.org/ben.html http://www.links.org/ There is no limit to what a man can do or how far he can go if he doesn't mind who gets the credit. - Robert Woodruff - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: On the randomness of DNS
On Jul 30, 2008, at 1:56 PM, Ben Laurie wrote: Oh, and I should say that number of ports and standard deviation are not a GREAT way to test for randomness. For example, the sequence 1000, 2000, ..., 27000 has 27 ports and a standard deviation of over 7500, which looks pretty GREAT to me. But not very random. I boggled a bit at the abuse of simple descriptive statistics, too. For those interested in actual statistical tests of randomness, there's a good literature survey at http://www.ciphersbyritter.com/RES/RANDTEST.HTM . -- Ivan Krstić [EMAIL PROTECTED] | http://radian.org - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: On the randomness of DNS
But just how GREAT is that, really? Well, we don' t know. Why? Because there isn't actually a way test for randomness. Your DNS resolver could be using some easily predicted random number generator like, say, a linear congruential one, as is common in the rand() library function, but DNS-OARC would still say it was GREAT. Believe them when they say it isn't GREAT, though! Well, they are some tests to judge the quality of a random number generator. The best known being the Diehard tests: http://en.wikipedia.org/wiki/Diehard_tests http://stat.fsu.edu/pub/diehard/ For sure, these tests might be an overkill here. Also, there must be some tests in the Art of Computer Programming too but I don't have it at hand right now (shame on me). I don't see the point of evaluating the quality of a random number generator by statistical tests. But I might be wrong, though. Regards, -- Pierre-Evariste DAGAND - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: On the randomness of DNS
Pierre-Evariste Dagand wrote: But just how GREAT is that, really? Well, we don' t know. Why? Because there isn't actually a way test for randomness. Your DNS resolver could be using some easily predicted random number generator like, say, a linear congruential one, as is common in the rand() library function, but DNS-OARC would still say it was GREAT. Believe them when they say it isn't GREAT, though! Well, they are some tests to judge the quality of a random number generator. The best known being the Diehard tests: http://en.wikipedia.org/wiki/Diehard_tests http://stat.fsu.edu/pub/diehard/ For sure, these tests might be an overkill here. Also, there must be some tests in the Art of Computer Programming too but I don't have it at hand right now (shame on me). I doubt you can get a large enough sample in any reasonable time. I don't see the point of evaluating the quality of a random number generator by statistical tests. Which is entirely my point. But I might be wrong, though. Regards, -- http://www.apache-ssl.org/ben.html http://www.links.org/ There is no limit to what a man can do or how far he can go if he doesn't mind who gets the credit. - Robert Woodruff - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: On the randomness of DNS
I doubt you can get a large enough sample in any reasonable time. Indeed. I don't see the point of evaluating the quality of a random number generator by statistical tests. Which is entirely my point. I fear I was not clear: I don't see what is wrong in evaluating the quality of a random number generator with (an extensive set of) statistical tests. For sure, it would be better if we could check the source code and match the implemented RNG against an already known RNG. But, then, there is a the chicken or the egg problem: how would you ensure that a *new* RNG is a good source of randomness ? (it's not a rhetorical questions, I'm curious about other approaches). Regards, -- Pierre-Evariste DAGAND - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: On the randomness of DNS
Pierre-Evariste Dagand wrote: I doubt you can get a large enough sample in any reasonable time. Indeed. I don't see the point of evaluating the quality of a random number generator by statistical tests. Which is entirely my point. I fear I was not clear: I don't see what is wrong in evaluating the quality of a random number generator with (an extensive set of) statistical tests. SHA-1(1), SHA-1(2), SHA-1(3), ... SHA-1(N) will look random, but clearly is not. For sure, it would be better if we could check the source code and match the implemented RNG against an already known RNG. But, then, there is a the chicken or the egg problem: how would you ensure that a *new* RNG is a good source of randomness ? (it's not a rhetorical questions, I'm curious about other approaches). By reviewing the algorithm and thinking hard. -- http://www.apache-ssl.org/ben.html http://www.links.org/ There is no limit to what a man can do or how far he can go if he doesn't mind who gets the credit. - Robert Woodruff - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: On the randomness of DNS
Ben Laurie writes: Oh, and I should say that number of ports and standard deviation are not a GREAT way to test for randomness. For example, the sequence 1000, 2000, ..., 27000 has 27 ports and a standard deviation of over 7500, which looks pretty GREAT to me. But not very random. That's a good point, Ben. Dan Kaminsky's DNS tester at http://www.doxpara.com/ does include output like this: Your name server, at 1.2.3.4, appears to be safe, but make sure the ports listed below aren't following an obvious pattern (:1001, :1002, :1003, or :3, :30020, :30100...). Requests seen for dae687514c50.doxdns5.com: 1.2.3.4:34023 TXID=64660 1.2.3.4:50662 TXID=51678 1.2.3.4:55984 TXID=49711 1.2.3.4:17745 TXID=12263 1.2.3.4:26318 TXID=59610 This shows only the last 5 ports so it won't detect an LCG, but at least it can detect some of the more obvious patterns. Hal Finney - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: On the randomness of DNS
Date: Wed, 30 Jul 2008 21:22:59 +0200 From: Pierre-Evariste Dagand [EMAIL PROTECTED] To: Ben Laurie [EMAIL PROTECTED], cryptography@metzdowd.com Subject: Re: On the randomness of DNS [...] For sure, it would be better if we could check the source code and match the implemented RNG against an already known RNG. [...] So... Download BIND and check. URL is http://www.isc.org/index.pl and select bind 9.5.0-P1 and then select BIND-9.5.0-P1 - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: On the randomness of DNS
On 30 Jul 2008, at 19:57, Pierre-Evariste Dagand wrote: But just how GREAT is that, really? Well, we don' t know. Why? Because there isn't actually a way test for randomness. Your DNS resolver could be using some easily predicted random number generator like, say, a linear congruential one, as is common in the rand() library function, but DNS-OARC would still say it was GREAT. Believe them when they say it isn't GREAT, though! Well, they are some tests to judge the quality of a random number generator. The best known being the Diehard tests: http://en.wikipedia.org/wiki/Diehard_tests http://stat.fsu.edu/pub/diehard/ For sure, these tests might be an overkill here. Also, there must be some tests in the Art of Computer Programming too but I don't have it at hand right now (shame on me). I don't see the point of evaluating the quality of a random number generator by statistical tests. But I might be wrong, though. Sorry - but something like AES(static-key) encrypt of i++ or SHA1(i++) will pass each and everyone of those test very nicely - but with a bit of code or silicon peeking - one can probably 'break' this with relative ease. I fail to see how you could evaluate this without seeing the code (and even then - I doubt that one can properly do this -- the ?old? NSA habit of tweaking your random generated rather than your protocol/ algorithm when they wanted your produced upgraded to export quality - is terribly effective and very hard to spot). Or am I missing something ? Dw - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: On the randomness of DNS
On 30 Jul 2008, at 21:33, Ben Laurie wrote: For sure, it would be better if we could check the source code and match the implemented RNG against an already known RNG. But, then, there is a the chicken or the egg problem: how would you ensure that a *new* RNG is a good source of randomness ? (it's not a rhetorical questions, I'm curious about other approaches). By reviewing the algorithm and thinking hard. But even then - is that really 'possible' - or is this fundamentally a black art ? Dw - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
