John Kelsey Correspondence

Date: Thu, 15 Aug 2013 15:26:18 +0000
From: "Kelsey, John M."
To: tony

Tony,

A really good resource is the Handbook of Applied Cryptography. It's available at

http://cacr.uwaterloo.ca/hac/

They make the chapters available for free online. Chapter 5 talks about randomness in cryptography, and discusses some statistical tests. Chapters 6 and 7 talk about block and stream ciphers, the two ways that are widely used to encrypt a lot of data quickly. Reading these chapters will help you know at least the language that cryptographers use to describe things, and will give you some background on statistical tests of randomness and how they're used.

Another good resource to understand this stuff is Knuth's _The Art of Computer Programming_, volume 2 (Seminumerical algorithms). He has a big discussion of random number generation and how to test random number generators. You can probably find this in a good library.

The big thing to understand is that statistical testing of a crypto algorithm is that it can only detect really big flaws. Many algorithms that are completely broken look great when subjected to randomness tests. For example, the hash function MD5 can be used to produce a sequence of bits that looks very random, and passes any statistical test you can think of. And yet, MD5 is completely broken as a hash function--you can download programs off the internet to find collisions in MD5 in a few minutes on your laptop.

In general, inventing a new encryption algorithm is a very hard thing to do, and is not at all a way to make money. I have been involved in designing and publishing two new encryption algorithms (both published in the crypto literature and made freely available)--Twofish (an AES submission, many years before I worked at NIST) and Helix (which was submitted in a modified form to the eStream competition). Twofish still looks strong and is used in some products; Helix was broken a couple years after we published it. It was revised into Phelix(I wasn't involved with the revision, but my coauthors were), and then the revised version was broken again. All this is another way of saying: this is a hard thing to do. It's fun, but hard to get right.

There are a whole bunch of well-understood, apparently very strong cryptographic algorithms that are already available for free. AES (Rijndael), Serpent, Twofish, 3-key triple-DES, CAST5, Blowfish, XTEA, Rabbit, Salsa, Grain, Trivium, GOST, and so on. Designing a new encryption algorithm is fun and challenging and interesting, but you should start out knowing you aren't going to make much of a business out of inventing a new algorithm, because anyone can just use one of these existing algorithms for free. Even if your algorithm is twice as fast and just as secure, you probably won't make any money at it. There is even an example of this: some very clever researchers a few years ago figured out a way to use the same block cipher to do encryption and authentication (making it impossible for an attacker to alter the message without being caught) at the same time. They patented their methods--three different teams of researchers have patents on these schemes, and there's a lot of overlap in the patents. Using one of these schemes would give about a 2x speedup in encryption/authentication. And yet, these clever schemes are essentially never used, and they appear in almost no internet standards. The free algorithms are fast enough, and nobody has to worry about negotiating a patent license to use them.

I hope this is helpful,

--John
________________________________________
From: tony
Sent: Wednesday, August 14, 2013 3:41 PM
To: Kelsey, John M.
Subject: Fwd: RE: Randomness in relation to encrypting the net

John,
I know you are busy but is it possible for you to tell me
if you are going to test the randomness of the examples I gave you?
This is not time critical but it would help me to know if you
are because then I don't have to try to understand the randomness
tests you mentioned,

as I mentioned I am unsure if these are not beyond my ability to
complete, but I hope to try if I have to.

regards
Tony Royden

-------- Original Message --------
Subject: RE: Randomness in relation to encrypting the net
Date: Sat, 10 Aug 2013 10:07:52 +1200
From: tony
To: "Kelsey, John M."

John,
you understand what you are talking about but I cannot follow you at all.
I attached a copy of some encryptions which I want to use to encrypt
the internet, I also attached the code that was encrypted.

If I attach it again, and the HTML pages I made can you tell me if its a
good cipher according to the points you have outlined in your email.
(I think it is because of the randomness that has been included in the
program to make the cipher)

because that is what it is, its a combination of encryption techniques.
The HTML examples shows what is encrypted in the HTML pages and 2
encryptions
in the spreadsheet, the TRUE formula tells you that the line is not random
but part of the cipher/encryption etc.

If not then I'll try to run your programs on the site you mentioned.

But if I haven't explained this very well then I'd be happy to try to
explain
it in more detail. Basically I don't think I can run these tests as they
are too
complicated for me to really understand.

thanks & regards
Tony Royden

On Fri, 9 Aug 2013 20:34:12 +0000, "Kelsey, John M."

wrote:
> Tony:
>
> SP 800-22 is available from our website and has a bunch of tests of
> randomness, and there is some source code available. These tests are
all
> trying to find some way in which the bits they're fed fail to follow an
> ideal random distribution (every bit independent of every other bit and
> independent of its position in the sequence, every bit with exactly 0.5
> probability of taking on a 1). That's probably a place to start. There
> are also many other randomness tests, like Diehard or the tests
described
> in Knuth.
>
> The draft of SP 800-90B is also available on our website, and it
provides
> three different sets of tests--iid, non-iid, and sanity checks. The
tests
> are really intended to evaluate entropy sources, but they may be of some
> value to you. Really random-looking data arranged in a long sequence
> should pass the iid tests, and get an entropy estimate of close to one
bit
> of entropy per bit of data. This isn't available as code, just text, so
it
> will be a lot more work to use these than the sorts of tests that have
> source code available online.
>
> Randomness testing of outputs or intermediate values in a cipher is
> useful, but it can only detect a really small fraction of possible
> problems. If the keystream of a stream cipher or the ciphertexts of a
> block cipher (given predictable, patterned plaintexts like 0,1,2,3,...)
> fail statistical tests, this is evidence that the cipher is not very
> strong. But if they pass it, this is not really very good evidence that
> the ciphers are strong. Very weak ciphers have been known to pass
> statistical testing.
>
> If your cipher has rounds, it may be more informative to determine how
> many rounds it takes before the ciphertext passes the tests. For
example,
> if you have a block cipher with 16 rounds, and it passes statistical
tests
> only after 14 rounds, that would not be a good sign.
>
> I hope this is helpful,
>
> --John
>

HEADER INFORMATION

by harold.maxnet.net.nz (Postfix) with ESMTP id 673B7201
for xxxx@localdelivery.maxnet.co.nz ; Fri, 16 Aug 2013 03:26:28 +1200 (NZST)
Received: from ironport-smtp02.maxnet.net.nz (ironport-smtp02.maxnet.net.nz [123.100.71.102])
by hood.maxnet.net.nz (Postfix) with ESMTP id 5E4C31C07E
for xxxx@maxnet.co.nz ; Fri, 16 Aug 2013 03:26:28 +1200 (NZST)
Received: from wsget2.nist.gov ([129.6.13.151])
by ironport-mx02.maxnet.net.nz with ESMTP; 16 Aug 2013 03:26:27 +1200
Received: from WSGHUB1.xchange.nist.gov (129.6.42.34) by wsget2.nist.gov
(129.6.13.151) with Microsoft SMTP Server (TLS) id 14.3.123.3; Thu, 15 Aug
2013 11:26:15 -0400
Received: from wsget2.nist.gov (129.6.13.151) by wsghub1.xchange.nist.gov
(129.6.16.196) with Microsoft SMTP Server (TLS) id 14.3.123.3; Thu, 15 Aug
2013 11:26:23 -0400
Received: from WSGHUB2.xchange.nist.gov (129.6.42.35) by wsget2.nist.gov
(129.6.13.151) with Microsoft SMTP Server (TLS) id 14.3.123.3; Thu, 15 Aug
2013 11:26:15 -0400
Received: from na01-by2-obe.outbound.protection.outlook.com (207.46.163.241)
by mail-g.nist.gov (129.6.42.33) with Microsoft SMTP Server (TLS) id
14.3.123.3; Thu, 15 Aug 2013 11:26:22 -0400
Received: from BL2PR09MB017.namprd09.prod.outlook.com (10.255.229.142) by
BL2PR09MB018.namprd09.prod.outlook.com (10.255.229.143) with Microsoft SMTP
Server (TLS) id 15.0.745.25; Thu, 15 Aug 2013 15:26:19 +0000
Received: from BL2PR09MB017.namprd09.prod.outlook.com ([169.254.3.47]) by
BL2PR09MB017.namprd09.prod.outlook.com ([169.254.3.47]) with mapi id
15.00.0745.000; Thu, 15 Aug 2013 15:26:19 +0000
From: "Kelsey, John M." john.kelsey@nist.gov
To: xxxx xxxx@maxnet.co.nz
Subject: RE: RE: Randomness in relation to encrypting the net
Thread-Topic: RE: Randomness in relation to encrypting the net
Thread-Index: AQHOmSZoVx9G0x7yPU265YsvOIFfGJmWW1hL
Date: Thu, 15 Aug 2013 15:26:18 +0000
Message-ID: 3aa612ac98b142dd935dab2d3b251f22@BL2PR09MB017.namprd09.prod.outlook.com
References: ebb1eaae6387f13cb8611b0c83997492@maxnet.co.nz
In-Reply-To: ebb1eaae6387f13cb8611b0c83997492@maxnet.co.nz
Accept-Language: en-US
Content-Language: en-US
X-MS-Has-Attach:
X-MS-TNEF-Correlator:
x-originating-ip: [129.6.13.245]
x-forefront-prvs: 0939529DE2
x-forefront-antispam-report: SFV:NSPM;SFS:(13464003)(189002)(199002)(51704005)(24454002)(479174003)(377454003)(51856001)(77982001)(59766001)(74366001)(65816001)(66066001)(80022001)(19580405001)(19580385001)(83072001)(19580395003)(76576001)(33646001)(81816001)(81686001)(76796001)(76786001)(83322001)(46102001)(50986001)(47976001)(63696002)(47736001)(49866001)(79102001)(15202345003)(4396001)(81542001)(74316001)(69226001)(74876001)(16406001)(53806001)(54356001)(80976001)(56776001)(54316002)(76482001)(77096001)(56816003)(74706001)(47446002)(74502001)(74662001)(81342001)(31966008)(24736002);DIR:OUT;SFP:;SCL:1;SRVR:BL2PR09MB018;H:BL2PR09MB017.namprd09.prod.outlook.com;CLIP:129.6.13.245;RD:InfoNoRecords;MX:1;A:1;LANG:en;
Content-Type: text/plain; charset="us-ascii"
Content-Transfer-Encoding: quoted-printable
MIME-Version: 1.0
X-OriginatorOrg: nist.gov