Re: Proving the randomness of a random number generator?

2005-12-03 Thread Pat Farrell
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?

2005-12-03 Thread Victor Duchovni
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?

2005-12-03 Thread bear


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

2005-12-03 Thread Ian G

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

2005-12-03 Thread Ben Laurie
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?

2005-12-03 Thread leichter_jerrold
| 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

2005-12-03 Thread Steven M. Bellovin
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?

2005-12-03 Thread afonso . ez

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

2005-12-03 Thread dan

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

2005-12-03 Thread Sidney Markowitz
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?

2005-12-03 Thread Victor Duchovni
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

2005-12-03 Thread Greg Black
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

2005-12-03 Thread John Gilmore
 ...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

2005-12-03 Thread Paul Hoffman

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]