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, > Your tests would not detect that kind of vulnerability. Let´s try it. http://sig.cacert.at/random/ I have setup a small randomness collection website, and I am asking everyone to submit as many random numbers as possible from as many different sources as possible. Please upload any kind of randomness (none, PRNG, special patterns, your personally preferred HRNG, ...) to the website. I will try to do a larger statistical analysis of all random samples, and also try to find ways to identify PRNGs ... I have a couple of goals with the project: * perhaps being able with a high number of samples to differentiate statistically between PRNG and HRNGs * a HRNG commercial market overview, which random speed you can get for which price. * at the end, I am planning, to run the analysis tools as a web service, so that everyone can have his own random numbers tested anytime, by simply uploading them, and having them analyzed and compared to the others automatically. Best regards, Philipp Gühring - 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 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
... >From: Philipp G�hring <[EMAIL PROTECTED]> >Sent: Jan 3, 2006 12:13 PM >To: "Steven M. Bellovin" <[EMAIL PROTECTED]>, cryptography@metzdowd.com >Subject: 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: It's helpful if you try to determine what you're testing here. What is the ideal situation which you hope to approximate by your RNG? For example, RSA moduli will always be odd, since they're the product of two odd primes. So you're going to get some statistical flaws when you look at the low bit. Similarly, the high few bits will be somewhat skewed by our choices of p and q (you usually set the high bits so that you get the desired size of modulus). And you may be choosing p and q according to some other criteria--I don't know what OpenSSL does exactly. Further, you're looking at the result of using the PRNG outputs in a really complicated way. There might be all kinds of nonrandom behavior in the outputs that would not be apparent at all in the result of generating RSA keys. Think about what's happening--you're generating a random starting point of 512 bits with a certain form (high bit set), and then sieving it, and then running a primality test for a bunch of rounds. Then you're doing the same thing a second time. Then you're multiplying the numbers together. 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. It's really hard to get a satisfactory model for most of the OS/software sources, unfortunately. If you can't get a simple model for it, you can at least attempt to determine some kind of bound on its entropy. See Peter Gutmann's wonderful paper from USENIX a few years ago on his Cryptlib's PRNG for some flavor of what this kind of analysis looks like. The critical thing to understand here is where your statistical tools are and are not useful. There's no harm in running some big statistical tests on the outputs from a cryptographic mechanism, and you may in principle even find something this way, but you probably won't. To the extent that you have a probability model for the source of seed material or entropy you're using, you can use statistical tests to check the plausibility of your model. (That is, if your model says that successive samples of some variable are independent, it's really a good idea to run some statistical tests to check that--Chi Square tests of independence, autocorrelation, whatever makes sense with the kind of data you have.) ... >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. Well, the analysis of your entropy source is ultimately a data analysis problem. You go back and forth between your best understanding of the underlying process that generates entropy, your data, and what kind of models you can work with, refining your understanding of your entropy source until your money or time run out. If some attacker has a much better model than yours, he may be able to predict your seeds and thus break your PRNG. (This is a good reason to seed the PRNG with more estimated entropy than the minimum you can get away with--there are other reasons to do this, too.) ... >> 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? Suppose I'm using AES128 with a key of 0 in counter mode, starting with a counter of 0. This will pass all the statistical tests you run ag
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
On 12/23/05, Philipp Gühring <[EMAIL PROTECTED]> wrote: > It´s easy to say that it´s their responsibility. > But how should they do it? Very carefully. Picking random numbers is far too important to be left to chance. -- http://www.lightconsulting.com/~travis/ "Vast emptiness, nothing sacred." -- Bodhidharma -><- GPG fingerprint: 50A1 15C5 A9DE 23B9 ED98 C93E 38E9 204A 94C2 641B - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: RNG quality verification
-- From: Philipp Gühring <[EMAIL PROTECTED]> > 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. Randomness is necessarily theory laden. To determine what is good, and what is bad, you have to look inside the software. Software should get its randomness from dev/random, or from similarly open sources of randomness, so that the source of randomness can be inspected. The general rule is that true randomness comes from quantities that are known to be unknown - for example the variation in disk read timing, which is affected by turbulence, or the microphone input, which is inherently noisy. You have to ask where these random numbers ultimately come from. --digsig James A. Donald 6YeGpsZR+nOTh/cGwvITnSR3TdzclVpR0+pr3YYQdkG 5i5rAiu+t+UqxlCHKBfiAn24UbuH1D2GsYrL3hv7 4q7w1mi+V9whucgThiyHnkPt0EkjS1oIAp9hQ1UKc - 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 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]
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 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
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 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 David, > 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. At first I had the same answer. But then I started to think it through. And it makes far more sense to me now. > You should ask them what problem they're trying to solve. They are just trying to fulfill the legal requirements. > Don't let them try to tell you how to solve it; you just need to know > the goal, not the mechanism. They just told me their requirements, and how it is normally solved. I am known for inventing my own mechanisms to solve requirements. Actually, I already developed one mechanism, that solves that problem as a side-effect. http://wiki.cacert.org/wiki/QualifiedCertificateRequest But it´s dedicated for hardware implementations, and I need mechanism for software implementations (mostly for the browsers) now. > 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. Yes. That´s what I am planning to do. But what do I do, if the users ask "And how do I do that?" It´s easy to say that it´s their responsibility. But how should they do it? At the moment, I wouldn´t even know how to do it myself, if someone asked me to care for it. Ok, let´s forget the CA and the users. How do I do it myself? How do I make sure myself, that the browser is generating good random numbers, and actually using them properly for the certificate requests? I will be personally liable for it, it that random thing breaks. Well, I could get a lot of paper, a good hex editor, and start calculating my own RSA keys with pencil and paper, read through the ASN.1 specifications, and manufacture my certificate request myself. (Has anyone actually does that yet, and can give some time-estimations?) > If the user fails to do so, they're the one who bears the costs of their > failure, so why should you care? Perhaps because I am working for a CA that actually does care. Do you know any browser vendor that guarantees the correct generation of secure random numbers and their correct usage, that offer to take liability, if it goes wrong? > 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, I am already in that business. And yes, it´s great fun, and I like it. > 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.) Well, I have to start somewhere. And the best way to start that I could find is by fulfilling the requirements that are already given. So yes, I start here now. And I´ll try not to stop, before I haven´t found good answers to all the open questions. > Most CA's have gravitated towards the opinion that that's not > something they can control, nor do they want to, nor should they -- I don´t want to control it, I want to audit it. I want the users to have it under their control. At the moment, nobody gave them much control over the random number quality of the keys they are using. > and > that sounds reasonable to me. Yes, it´s reasonable, if you aren´t paranoid enough. I thought exactly the same way, before I started to think more about this specific topic more detailled. Now I think it´s a bit negligent to ignore the topic completely. But perhaps there are bigger problems, yes. (Sometimes little problems are easier to solve than bigger problems ...) > 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. Yes. Do you have a TODO list for me? Thanks for your input, Philipp Gühring - 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]
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]
Re: RNG quality verification
On 12/22/05, Philipp Gühring <[EMAIL PROTECTED]> wrote: > 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. The only thing is, you cannot test in randomness, and it is an abuse of statistics to make predictions about individual events -- they describe populations. The best thing you could do is combine them with a truly random source that you control. 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 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. 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. 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'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. -- http://www.lightconsulting.com/~travis/ "You are free... to do as we tell you!" -><- GPG fingerprint: 50A1 15C5 A9DE 23B9 ED98 C93E 38E9 204A 94C2 641B - 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
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]
