Re: RNG quality verification
Similar site aiming to detect defects in various ciphers and hashes: http://defectoscopy.com/ ...where block ciphers can be compared against stream ciphers, asymmetric ciphers and hash functions in their quality determined by the security of each individual component as well as their combination. We aim to collect all the existing block ciphers, stream ciphers, asymmetric ciphers and hash functions under one roof, proving Shannon's 1949 definition of cipher security to be correct. We also want to show that cryptanalytic progress of the past few decades has enabled automated detection of flaws in cryptographic primitives, thus significantly reducing the amount of time required to determine security or insecurity of a given cryptographic primitive. Max - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: RNG quality verification
Hi, Ok, now I did the first test. I took OpenSSL, generated 1 RSA keys, and took them apart. First I analyzed the raw keys: -- ~~ ./ent RNGQA/openssl-keys-raw.random Entropy = 7.992782 bits per byte. Optimum compression would reduce the size of this 258 byte file by 0 percent. Chi square distribution for 258 samples is 38940.74, and randomly would exceed this value 0.01 percent of the times. Arithmetic mean value of data bytes is 127.2214 (127.5 = random). Monte Carlo value for Pi is 3.177609302 (error 1.15 percent). Serial correlation coefficient is -0.016663 (totally uncorrelated = 0.0). -- Then I stripped off the first 2 bytes and the last byte: -- ~~ ./ent RNGQA/openssl-keys-stripped.random Entropy = 7.32 bits per byte. Optimum compression would reduce the size of this 252 byte file by 0 percent. Chi square distribution for 252 samples is 236.33, and randomly would exceed this value 75.00 percent of the times. Arithmetic mean value of data bytes is 127.4632 (127.5 = random). Monte Carlo value for Pi is 3.14527 (error 0.12 percent). Serial correlation coefficient is 0.000327 (totally uncorrelated = 0.0). -- It isn´t perfect random quality, but I also don´t see any big problems with it. You can get the program and the extracted data here: http://www2.futureware.at/~philipp/RNGQA-light.tar.bz2 It's really unsolvable, in several different ways. Perhaps I should have stated the quality demands for possible solutions: Since I am working on a practical solution, and not a theoretical solution, the following demands apply: * A 99.999% solution is ok. First -- you just cannot tell if a single number is random. At best, you can look at a large selection of numbers and see if they fit certain randomness tests. Even that isn't easy, though there are several packages that will help. The best-known one is DIEHARD; ask your favorite search engine for diehard random. Sure. However -- and it's a big however -- numbers that are random enough for statistical purposes are not necessarily good enough for cryptographic purposes. As several people have pointed out already, there are processes involving cryptographic algorithms that produce very random sequences, but are in fact deterministic to someone who knows a secret. In other words, if you don't control the generator, it's not possible to distinguish these two cases. Has anyone tested yet, how much samples are needed to detect those PRNGs? In fact, any cipher or hash function whose output was easily distinguishable from a true- random source would be rejected by the cryptographic community. Yes, sure. Furthermore, even if the generator is good, if the machine using the certificates has been compromised it doesn't matter, because the malware can steal the secret key. What this boils down to is that you either trust the endpoint or you don't. Sure. To secure against compromised machines, you need Hardware Tokens with a qualified certificate request mechanism. But in the scenario, I am currently working on, the assumption is that we only have a software engine, and that the machine of the user is not compromised. But still the quality of the random number generator and the correct usage of the random numbers for the certificate request are not known yet. Finally, even if it were possible for you to verify that p and q were random, you *really* don't want to do that -- you *never* want to see users' secret keys, because that exposes the keys to danger and hence you to liability. I will not ask the users to send in their private keys for testing! As you write below, I would like to test the standard generation packages (Firefox, IE, Opera, OpenSSL), and I also want to offer a guideline (or even the testing software) for the advanced users that they can test their own generation package, if they really want to. Let me make an alternative suggestion. Pick two or three key generation packages -- as I recall, both Firefox and IE have such -- generate a lot of keys, and run them through DIEHARD. Then warn your users to use only approved mechanisms for generating their certificate requests -- you just can't do any better. That´s exactly what I wanted to do. (Sorry if I didn´t wrote that clear enough yet.) Best regards, Philipp Gühring - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: RNG quality verification
Philipp Gühring wrote: I took OpenSSL, generated 1 RSA keys, and took them apart. First I analyzed the raw keys: Try this: Generate 256000 bytes from MD5(i), i=1...16000 and run the same tests. That is clearly not acceptable as a PRNG because it is completely predictable if you know that the sequence is MD5(1) ... MD5(16000), but it should pass any tests other than one that checks specifically if it is correlated to MD5(1) ... MD5(16000). Perhaps you would say that example is unfair because MD5 makes a perfectly good PRNG as long as the software package seeds it properly. In that case, how are you going to ensure that the package you are testing is seeding the PRNG properly? In fact, the famous Netscape vulnerability was based on a PRNG that was simply MD5 of a counter, with the vulnerability being predictability of the seed. See http://www.cs.berkeley.edu/~daw/papers/ddj-netscape.html for a clear description of that. Your tests would not detect that kind of vulnerability. You asked, Has anyone tested yet, how much samples are needed to detect those PRNGs? The point is that your tests will not detect the difference between a PRNG using a properly seeded MD5(counter) and one with a predictable seed. More generally, a sequence can be predictable while still being statistically random. Carrying it even further, back in 1996 the only problem with using MD5 of a counter as a PRNG was making sure that the seed was unpredictable. That may not be true anymore because of recent results of MD5 collisions, or more accurately, it may not remain true if stronger attacks continue to be found. Statistical tests have not all of a sudden changed their results: MD5 will not appear any less random in those tests just because vulnerabilities are found. So how do you certify PRNGs used by your customers? You have them use well known software packages that have been analyzed and vetted by the cryptographic community, such as OpenSSL. It would be a shock if any of them did not pass the simple statistical tests that you can perform. Passing those tests does not ensure that there are none of the more subtle vulnerabilities that are only discovered by many smart people taking a very hard look over a significant time period. -- Sidney Markowitz http://www.sidney.com - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: RNG quality verification
-- John Kelsey wrote: To assess a cryptographic PRNG, you need to know two things: a. If it had a starting point or seed which was impossible to guess, would you be able to find any problems with its outputs? b. Does it get a starting point or seed which is impossible to guess? Assessing (a) is about cryptanalysis; statsitics can help there, but mostly, you're looking at the output from some cryptographic function like SHA1 or AES or 3DES. Assessing (b) is about data analysis--you're going to look at the sources for seed material, and try to determine what makes them ultimately unpredictable, and to model them somehow. You can't assess how much entropy some variable has without some kind of probability model for it. All observables are necessarily theory laden. Entropy and randomness are more theory laden than most, so theory laden as to be impossible to observe directly. One must study what goes in, not what goes out. For any test, ask yourself this: If the source of random numbers was the current time, hashed with SHA and a sixteen bit fixed code, would your test show any problem? --digsig James A. Donald 6YeGpsZR+nOTh/cGwvITnSR3TdzclVpR0+pr3YYQdkG KU60aORMS6eP2TWG+XjML/Cp7egySzT8UZW/n9Zo 40TzrkMfMK52cZ0Rdu5DMlo9ngx84PkNXCHQrnXQ+ - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: RNG quality verification
Philipp =?utf-8?q?G=C3=BChring?= [EMAIL PROTECTED] writes: What is wrong with the following black-box test? * Open browser * Go to a dummy CA's website * Let the browser generate a keypair through the keygen or cenroll.dll * Import the generated certificate * Backup the certificate together with the private key into a PKCS#12 container * Extract the private key from the backup * Extract p and q from the private key * Extract the random parts of p and q (strip off the first and the last bit) * Automate the previous steps with some GUI-Automation system * Concatenate all random bits from all the keypairs together * Do the usual statistical tests with the random bits How would this differentiate between keygen for which the PRNG is SHA1( get_thermal_noise() ) and one where it's SHA1( counter++ )? Or one where it's get_constant_value() and you take the counter++ -th primes as p and q? Or one where ...? In addition the PRNG input to the keygen process has no bearing on the form of the primes generated, look at the IPsec DH primes with their long strings of 1 bits for an example, they'd fail a statistical test because they've been specially constructed to have a certain form, but that makes them stronger, not weaker. Thus both David Wagner's and my comments that the people asking this question/setting this requirement don't understand the problem. So if you want a solution to something originating at the bureaucratic layer, you need to provide the solution at the bureaucratic layer. Peter. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: RNG quality verification
Hi Peter, Easily solveable bureaucratic problems are much simpler than unsolveable mathematical ones. Perhaps there is some mis-understanding, but I am getting worried that the common conception seems to be that it is an unsolveable problem. What is wrong with the following black-box test? * Open browser * Go to a dummy CA´s website * Let the browser generate a keypair through the keygen or cenroll.dll * Import the generated certificate * Backup the certificate together with the private key into a PKCS#12 container * Extract the private key from the backup * Extract p and q from the private key * Extract the random parts of p and q (strip off the first and the last bit) * Automate the previous steps with some GUI-Automation system * Concatenate all random bits from all the keypairs together * Do the usual statistical tests with the random bits Is this a valid solution, or is the question of the proper usage of random numbers in certificate keying material really mathematically unsolveable? (I am not a RSA specialist yet, I tried to stay away from the bit-wise details and the mathematics, so I might be wrong) But I would really worry, if it is mathematically impossible to attestate the correct usage (to a certain extent, I know about the statistical limitations) of random numbers with the software I am using to get certificates. Best regards, Philipp Gühring - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: RNG quality verification
In message [EMAIL PROTECTED], Philipp =?utf-8?q?G=C3=BChrin g?= writes: Hi Peter, Easily solveable bureaucratic problems are much simpler than unsolveable mathematical ones. Perhaps there is some mis-understanding, but I am getting worried that the common conception seems to be that it is an unsolveable problem. What is wrong with the following black-box test? * Open browser * Go to a dummy CA´s website * Let the browser generate a keypair through the keygen or cenroll.dll * Import the generated certificate * Backup the certificate together with the private key into a PKCS#12 container * Extract the private key from the backup * Extract p and q from the private key * Extract the random parts of p and q (strip off the first and the last bit) * Automate the previous steps with some GUI-Automation system * Concatenate all random bits from all the keypairs together * Do the usual statistical tests with the random bits Is this a valid solution, or is the question of the proper usage of random numbers in certificate keying material really mathematically unsolveable? (I am not a RSA specialist yet, I tried to stay away from the bit-wise details and the mathematics, so I might be wrong) But I would really worry, if it is mathematically impossible to attestate the correct usage (to a certain extent, I know about the statistical limitations) of random numbers with the software I am using to get certificates. It's really unsolvable, in several different ways. First -- you just cannot tell if a single number is random. At best, you can look at a large selection of numbers and see if they fit certain randomness tests. Even that isn't easy, though there are several packages that will help. The best-known one is DIEHARD; ask your favorite search engine for diehard random. However -- and it's a big however -- numbers that are random enough for statistical purposes are not necessarily good enough for cryptographic purposes. As several people have pointed out already, there are processes involving cryptographic algorithms that produce very random sequences, but are in fact deterministic to someone who knows a secret. In other words, if you don't control the generator, it's not possible to distinguish these two cases. In fact, any cipher or hash function whose output was easily distinguishable from a true- random source would be rejected by the cryptographic community. Furthermore, even if the generator is good, if the machine using the certificates has been compromised it doesn't matter, because the malware can steal the secret key. What this boils down to is that you either trust the endpoint or you don't. Finally, even if it were possible for you to verify that p and q were random, you *really* don't want to do that -- you *never* want to see users' secret keys, because that exposes the keys to danger and hence you to liability. Let me make an alternative suggestion. Pick two or three key generation packages -- as I recall, both Firefox and IE have such -- generate a lot of keys, and run them through DIEHARD. Then warn your users to use only approved mechanisms for generating their certificate requests -- you just can't do any better. --Steven M. Bellovin, http://www.cs.columbia.edu/~smb - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
RNG quality verification
Hi, I have been asked by to verify the quality of the random numbers which are used for certificate requests that are being sent to us, to make sure that they are good enough, and we don´t issue certificates for weak keys. The client applications that generate the keys and issue the certificate requests are the usual software landscape OpenSSL, IE, Firefox, SmartCards, ... and we would like to be able to accept all normally used software. We are being asked to either issue the keys for our users (I don´t want to), or alternatively demand the users to have good quality random numbers with a contract for the user. Now it might be easy that I demand the user to have good random numbers, but the first question will likely be and how do I do that? or which software/hardware does that? So I guess I have to ask the vendors, whether ther random numbers are good enough. But what if they just say yes or no? I think the better way would be if I had a possibility to verify the quality of the random numbers used in a certificate request myself, without the dependence on the vendor. From what I remember of the usual RSA key generation, random numbers gathered are being put into a field with the expected keysize. Then the first and last bit is set to 1, to make sure that the key has the necessary size, and to have it odd (not to be devidable by 2). Then it is verified for primeness, and if the check is ok, the number is used. So if I extract the key, remove the first and the last bit, then I should have the pure random numbers that are being used. If I do that with lots of keys, I should have a good amount of random material for the usual statistical tests. Am I right? Am I wrong? Has anyone done that before? Any other, better ideas? Should I do it that way? Best regards, Philipp Gühring - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: RNG quality verification
On Thu, 22 Dec 2005, Philipp [iso-8859-1] G?hring wrote: I have been asked by to verify the quality of the random numbers which are used for certificate requests that are being sent to us, to make sure that they are good enough, and we don?t issue certificates for weak keys. Consider an implementation which uses x = time and when SHA1(hardcoded-string||x), SHA1(hardcoded-string||x+1), etc. as a starting point to search for primes. Unless you know what is the hardcoded-string you cannot tell that the random starting point was not that random: it is very important to realize that randomness is the property of the source and not of a string. BTW, note that what you can see in the certificate request for an RSA key is n and not p and q themselves. -- Regards, ASK - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: RNG quality verification
On Thu, Dec 22, 2005 at 10:28:47AM +0100, Philipp G?hring wrote: I think the better way would be if I had a possibility to verify the quality of the random numbers used in a certificate request myself, without the dependence on the vendor. This is impossible. You don't see the raw random inputs: the CSR does not disclose the input primes, it only discloses their product. The real problem is deeper: there is no such thing as a single number that is or is not random, a random *process* produces the same discrete outputs as a similar non-random process. Furthermore, it is impossible to prove an untrusted sampled process to be securely random. To have *assurance* of randomness you need to participate in the process, and to have access to the raw random data. This of course you cannot do as a CA, because you don't have legitimate access to the private keys. If you must police the users, hand them their keys on smart cards (or other suitable hardware) that you initialize. -- /\ ASCII RIBBON NOTICE: If received in error, \ / CAMPAIGN Victor Duchovni please destroy and notify X AGAINST IT Security, sender. Sender does not waive / \ HTML MAILMorgan Stanley confidentiality or privilege, and use is prohibited. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: RNG quality verification
Hi Travis, The only thing is, you cannot test in randomness, That´s true, but I can test non-randomness. And if I don´t detect non-randomness, I can assume randomness to a certain extent. and it is an abuse of statistics to make predictions about individual events -- Wasn´t that one of the reasons, why statistic was invented? they describe populations. The best thing you could do is combine them with a truly random source that you control. I don´t control the software everyone is using on this world. Of course then your users may not trust you, so you have to do a cryptographically strong combination such that control of one of the inputs doesn't translate into control of the outputs. For example, you cannot simply XOR them or you could force the key to be anything of the same length by choosing an appropriate stream. Also, you could not do this with small input spaces or else exhaustive search is trivial (try every input until the output is what you want). The problem is that I have to live with COTS (Common-off-the-shelf) software out there, that is generating the certificate requests. The only thing I can do is create a blacklist or a whitelist of known bad or known good software, to tell the users: Use this software, or don´t use that software. The best you could do is examine (reverse engineer) the RNGs in the products, and whatever seeds them, and then create tests for their nonrandom properties, and then see if the tests work. This would, however, not tell you anything you didn't already know once you had examined the internals. Has anyone done this yet? You might be able to find structure in their outputs through blind application of general-purpose statistics, but it will likely take a great deal more output, even with supposedly sensitive statistics like double-sided Kolmogorov-Smirnof. Hmm, every key should deliver about 1000 bits of randomness, I guess. How many bits should I collect for the tests in your opinion? As a pathological example, my RNG may output the text of the King James Bible, encrypted with AES-CBC using a counter as the key, and uniquified across instances by using a processor serial number or licence number as an IV. Unless you knew this, you would be hard-pressed to tell they were not random and in fact totally predictable to anyone who knows the secret. If a general statistic could distinguish this from a random stream, I think it would imply a weakness in AES-CBC. The tests would likely fail until enough output was generated that it started to repeat itself. On the other hand, I could decrypt it with a counter and see what pops out, and all I'd have to do is distringuish the KJV from a random stream. I guess someone would have noticed already, if Microsoft, Mozilla or OpenSSL had done that. Wait. How many LOC(lines of code) does the King James Bible have? Mozilla had something like 13 Mio. LOC as far as I remember ... perhaps they really hid the KJ Bible in it! ;-) I'd look at seeding techniques first, as that's an easy win. Predictable seed - predictable output. If that bootstrap is wrong, you can treat everything else as an oracle and still get a good distinguisher. Contrary to the normal challenge of developing a new random number generator, I don´t have the possibility to change the existing software, I just have to evaluate them, and find out, whether it´s ok or not. I first thought about a black-box test, by simply tracing in the operating system where the software gets its numbers from. A open(/dev/random) systemcall at the time of key generation might be a good hint for good random numbers. But as Netscape proofed some years ago, you can ch=read(stream,ch,1) one perfectly random number, and overwrite it with the value 1 (which is not soo random anymore) in one single line of error, and invisibly to the operating system failing to use the random numbers given. So since the random numbers might be modified between gathering and using for the keypair, I thought that I need to evaluate the quality at the end of the keypair generation. Best regards, Philipp Gühring - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
RNG quality verification
Philipp G#ring [EMAIL PROTECTED] writes: I have been asked by to verify the quality of the random numbers which are used for certificate requests that are being sent to us, to make sure that they are good enough, and we don´t issue certificates for weak keys. Go tell whoever wrote your requirements that they (to be frank) don't know what they're talking about. What they're asking for doesn't make any sense. You should ask them what problem they're trying to solve. Don't let them try to tell you how to solve it; you just need to know the goal, not the mechanism. The standard solution is to just not worry about this at all, and say that it is the user's responsibility to choose good random numbers. If the user fails to do so, they're the one who bears the costs of their failure, so why should you care? If the goal is to hold the hands of your users, then you might want to think carefully about whether you want to be in that business, what are the most likely failure modes, and what is the best way to deal with it. (Trying to check whether their numbers are random probably isn't the best answer.) Most CA's have gravitated towards the opinion that that's not something they can control, nor do they want to, nor should they -- and that sounds reasonable to me. But if you want to be in the hand-holding business, you're going to have to do an awful lot more than just check the random numbers. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: RNG quality verification
Victor Duchovni [EMAIL PROTECTED] writes: On Thu, Dec 22, 2005 at 10:28:47AM +0100, Philipp G?hring wrote: I think the better way would be if I had a possibility to verify the quality of the random numbers used in a certificate request myself, without the dependence on the vendor. This is impossible. You don't see the raw random inputs: the CSR does not disclose the input primes, it only discloses their product. The real problem is deeper: there is no such thing as a single number that is or is not random, a random *process* produces the same discrete outputs as a similar non-random process. This question may be solveable, but to do it you need to step back and look at who's set this requirement and why. I've run into the random-number-obsession a couple of times, generally when government agencies or government departments following policy set by government agencies are involved (example: The CA generates the keys for the user and emails them their private key, because we can't trust the quality of the user's RNG). The reason I label it an obsession is because the entire remainder of the keygen process can be arbitrarily insecure as long as the RNG is some sort of officially approved one (in fact in at least two cases the officially approved RNGs were quite dubious). So if this is merely a checkbox requirement then it can be met by including an attribute in the request saying that the RNG was FIPS-certified, and recording during the issue process that the request stated that it used an approved RNG. Easily solveable bureaucratic problems are much simpler than unsolveable mathematical ones. Peter. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
