### Re: Proving the randomness of a random number generator?

On Fri, 2005-12-02 at 11:54 +0100, Lee Parkes wrote: So, the question is, how can the randomness of a PRNG be proved within reasonable limits of time, processing availability and skill? Cryptographic randomness? None. Any one who considers arithmetical methods of producing random digits is, of course, in a state of sin. John von Neumann, 1951, quoted by Knuth Depending on the language you are using, it is as simple as calling the appropriate random number generator. Of have someone read Knuth's Art of Computer Programming for background on it. -- Pat Farrell http://www.pfarrell.com - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]

### Re: Proving the randomness of a random number generator?

On Fri, Dec 02, 2005 at 11:54:03AM +0100, Lee Parkes wrote: Hi, Apologies if this has been asked before. The company I work for has been asked to prove the randomness of a random number generator. I assume they mean an PRNG, but knowing my employer it could be anything.. I've turned the work down on the basis of having another gig that week. However, it raised the issue of just how this could be achieved. As far as I'm aware there are no strong mathematicians in the team, so it will get thrown out to the first available person (cool idea, eh?). There will most likely be very little time allocated to do it. So, the question is, how can the randomness of a PRNG be proved within reasonable limits of time, processing availability and skill? It can't be done. What can be done instead is that multiple parties participate in a random number generation protocol. The protocol ensures that all can be confident that the number is at least as random as each one of them wants it to be. If at least one party is using a decent PRNG, or a physical source of real entropy then all the parties get random numbers, and no-one feels cheated if they like the randomness of their own contribution to the protocol. -- /\ 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: Proving the randomness of a random number generator?

On Fri, 2 Dec 2005, Lee Parkes wrote: Hi, Apologies if this has been asked before. So, the question is, how can the randomness of a PRNG be proved within reasonable limits of time, processing availability and skill? Randomness is a quality that, intrinsically, cannot be proven. Period. You can take an urn with a hundred numbered balls and pull them out one at a time -- a truly random process -- and the sequence from one to a hundred by ones is just as likely as every other sequence. If it happens to come up, even that doesn't prove that it wasn't a random process. On a practical note, I would test the PRNG's output against pattern detectors. Spectral Analysis software is quite good at detecting patterns in PRNG output. Then there are the pattern detectors built into various file compression tools. If gzip or winzip or arc or arj or (etc) can find a pattern, it will succeed in producing a shorter file than the original. Before you do any of that, however, check the literature to see if it's already been done. If you're using a commercial or cryptological PRNG that's been studied, read the papers of the people who studied it, and the papers of people who studied competing products. See if they found anything usable or any useful property that you can use to support a claim of randomness. (note: it won't actually *be* randomness, for the simple reason that that can't be proven. But some systems have proofs that someone who has access to the entire output of the PRNG so far has no strategy better than random guessing for determining the next and subsequent outputs, and that may be random enough for your bosses.) Bear - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]

### Re: Session Key Negotiation

Will Morton wrote: I am designing a transport-layer encryption protocol, and obviously wish to use as much existing knowledge as possible, in particular TLS, which AFAICT seems to be the state of the art. In TLS/SSL, the client and the server negotiate a 'master secret' value which is passed through a PRNG and used to create session keys. My question is: why does this secret need to be negotiated? Why can one side or another (preference for client) not just pick a secret key and use that? I guess that one reason would be to give both sides some degree of confidence over the security in the key. Is this true, and if so is it the only reason? One reason is that one side or the other might have a screwed implementation. For example, an RNG that spits out zeroes. Another reason is that one side or other might have reasons for screwing the key deliberately; a server might for example fix its key so that it can be listened to outside. If a simple XOR is negotiated, then the server could always choose its part to XOR to a certain value. This is plausible if a server operator has done a deal to reveal to an eavesdropper, but doesn't want to reveal its private key. (I suspect the newer ciphersuites in TLS may have been motivated by this.) Hence, slop in lots of random from both sides, and hash the result, so you have at least the key space of the one side that is behaving well. iang - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]

### Re: Session Key Negotiation

Will Morton wrote: Eric Rescorla wrote: May I ask why you don't just use TLS? I would if I could, believe me. :o) The negotiated key will be used for both reliable (TCP-like) and non-reliable (UDP-like) connections, all tunnelled over a single UDP port for NAT-busting purposes. For the TCP-like component, I want to follow TLS as much as possible for obvious reasons. Err ... DTLS, then? -- http://www.apache-ssl.org/ben.html http://www.thebunker.net/ ** ApacheCon - Dec 10-14th - San Diego - http://apachecon.com/ ** 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: Proving the randomness of a random number generator?

| Hi, | Apologies if this has been asked before. | | The company I work for has been asked to prove the randomness of a random | number generator. I assume they mean an PRNG, but knowing my employer it | could be anything.. I've turned the work down on the basis of having another | gig that week. However, it raised the issue of just how this could be | achieved. As far as I'm aware there are no strong mathematicians in the | team, so it will get thrown out to the first available person (cool idea, | eh?). There will most likely be very little time allocated to do it. | | So, the question is, how can the randomness of a PRNG be proved within | reasonable limits of time, processing availability and skill? It can't be *proved*, for any significant sense of that word, regardless of the availability of resources. At best, you can - if you are lucky - prove *non-randomness*. In practice, one makes attempts to prove non-randomness and, if enough of those fail - enough being determined by available resources - one just asserts randomness. There are basically two kinds of tests one can do: - Various kinds of statistical tests. These look at things like average numbers of 0's and 1's (assume a series of random bits), correlations between successive bits, and so on. There are a number of test suites out there, the best known of which is probably the Diehard suite. (I don't have a link, but you should have no trouble finding it.) Testing like this looks for statistical randomness: That is, the random number generator produces outputs that have the same statistical properties as random numbers. They say *nothing* about predictability by someone who knows how the numbers have been generated. For example, any good PRNG will pass most or all of these tests, but if you know the starting key, you can predict the outputs exactly. So if your interest is *cryptographic security*, statistical randomness tells you little (though *lack* of it is obviously a red flag). - Attack attempts. This is mainly relevant for cryptographic random number generation, and is like cryptanalysis: Look at the generator and try to break it, i.e., predict its output. The techniques and expertise needed are as varied as the techniques used to construct the generators. If the generator uses measurements of system events, you need to know, at a deep level, what causes those system events, how an attacker might observe them, and how an attacker might influence them. If the generator is based on some electronic circuit, e.g., a noise diode, you need to understand the physics and electronics. In almost all cases, you need to understand how one attacks electronics, at various levels of abstraction. A thorough analysis like this is likely to be very expensive, and is prone to miss things - it's just the nature of the beast. -- Jerry - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]

### NSA declassifies some Vietnam-era SIGINT

http://www.nsa.gov/vietnam/ These are the documents related to the claim that NSA suppressed many of the intercepts relating to the so-called Gulf of Tonkin incident. --Steven M. Bellovin, http://www.cs.columbia.edu/~smb - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]

### Re: Proving the randomness of a random number generator?

Well, you just can't prove a PRNG is secure. It would be like proving that the AES is secure, or that factoring integers is hard. It just can't be done (aside theoretical discutions about P=NP). What you can do, at most, is show that it has the same strength than a known difficult problem. A PRNG using AES as central core, and correctly designed, can be shown to be as strong as AES itself. Or you can use a hard problem like discrete logarithm to construct one that carries on the same difficulty for predictability. I think, under the reasonable assumption that they know what they are asking, your best approach world be to show that breaking it is as hard as some other problem, and that depends exactly on how the PRNG was designed. If it's just a bunch of XOR and S-Boxes or if it is something like a Linear Feedback Shift Register PRNG, I think you can't do it. Afonso Araujo Neto On 2 Dec 2005 at 11:54, Lee Parkes wrote: Hi, Apologies if this has been asked before. The company I work for has been asked to prove the randomness of a random number generator. I assume they mean an PRNG, but knowing my employer it could be anything.. I've turned the work down on the basis of having another gig that week. However, it raised the issue of just how this could be achieved. As far as I'm aware there are no strong mathematicians in the team, so it will get thrown out to the first available person (cool idea, eh?). There will most likely be very little time allocated to do it. So, the question is, how can the randomness of a PRNG be proved within reasonable limits of time, processing availability and skill? Thanks, Lee -- -- [EMAIL PROTECTED] DOC #25 GLASS #136 www.mud-dog.org I Need A Reason To Stand Up And Fight Need To Believe What I See - The Silver Drop - Mnemic - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED] - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]

### Re: [Clips] Banks Seek Better Online-Security Tools

You know, I'd wonder how many people on this list use or have used online banking. To start the ball rolling, I have not and won't. --dan Cryptography is nothing more than a mathematical framework for discussing the implications of various paranoid delusions. -- Don Alvarez - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]

### Re: Fermat's primality test vs. Miller-Rabin

Joseph Ashwood wrote: byte [] rawBytes = new byte[lenNum/8]; rand.nextBytes(rawBytes); curNum = new BigInteger(rawBytes); I haven't thought through why it would produce non-primes, but it doesn't seem to do what you want. That produces a 512 bit twos-complement number, which gives you a 511 bit positive integer, not 512 bit. It also is unnecessarily complicated compared to this form of the BigInteger constructor and the or method (see the javadoc): curNum = BigInteger.ONE.or(new BigInteger(512, rand)); -- Sidney Markowitz http://www.sidney.com - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]

### Re: Proving the randomness of a random number generator?

On Fri, Dec 02, 2005 at 10:13:21PM -0200, [EMAIL PROTECTED] wrote: Well, you just can't prove a PRNG is secure. It would be like proving that the AES is secure, or that factoring integers is hard. It just can't be done (aside theoretical discutions about P=NP). Actually, this is inaccurate, proving the strength of AES or factoring is difficult, and may never happen, we may even prove AES to be not secure (in a broad sense) some day. Proving an RNG secure is *impossible*. A replay of an AES tranmission remains confidential, a replay of an RNG generated sequence, is no longer random. Think of the scam in The Sting, a time-delayed random outcome is no longer random. It is not possible to prove to a passive observer that information he is receiving is not time-delayed and was not available to other observers in advance. -- Viktor. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]

### Re: [Clips] Banks Seek Better Online-Security Tools

On 2005-12-02, [EMAIL PROTECTED] wrote: You know, I'd wonder how many people on this list use or have used online banking. To start the ball rolling, I have not and won't. I've been using it for me and my wife with 3 banks since they first offered it; I use it every week to pay all our bills and would not be without it. The benefits I have gained from not having to waste time doing things the old way have proved to be substantial and I get to notice and resolve the occasional error (always in the form of fraudulent debits to credit cards) much faster than in the old days when I had to wait for the monthly statements. It's probably not related to my use of online banking, but it has also been noticeable that fraudulent debits to our credit cards have dropped from about 5 per card per year five years ago to one such debit to the 6 cards we use in the past two years. I detest banks and have had many battles with them over various issues over the years, but I remain confident that my careful practices, meticulous record keeping and careful management of passwords will continue to give me the edge in any dispute with them. And the cost to me of any such disputes seems unlikely to be anything like the benefits I have gained from online banking. Greg - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]

### Re: [Clips] Banks Seek Better Online-Security Tools

...how many people on this list use or have used online banking? To start the ball rolling, I have not and won't. Dan, that makes two of us. John - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]

### Re: [Clips] Banks Seek Better Online-Security Tools

At 11:05 PM -0500 12/2/05, [EMAIL PROTECTED] wrote: You know, I'd wonder how many people on this list use or have used online banking. To start the ball rolling, I have not and won't. I have, and it's nice for making Quicken data entry faster, but that's about all. The rest gives me the willies when I see the security clue of the folks running the site. FWIW, I have never had a problem changing my password to something very long and all-alphabetic, even if I don't include at least one capital letter and one digit or whatever the CYA rules for passwords are these days. --Paul Hoffman, Director --VPN Consortium - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]