How do I test the quality of an encryption algorithm?

Question

I want to test an encryption algorithm for strength. It doesn't have to be strong, it just has to resist accidental cracking and say, a determined hacker with 10-hours to waste. (I wrote the crypto algorithm. Yes, I know that this is generally a bad idea but I think that I have good reason.)

What kind of tests should I do? So far I've tried this:

• Generate random A.
• Flip one random bit of A to make B.
• Check that the number of 1s in encrypt(a) XOR encrypt(b) fits a poisson distribution (except that the XOR never outputs 0).

Any other suggested tests?

About the encryption

It's a standard Fiestel Cipher designed to run in 3ns and be entirely combinational, no registers. (This is orders of magnitude faster than DES/AES/etc.) I do as many rounds as I can in 3ns, which is only about 6.

First I permute the order of the input bits.

Then for each bit on the left half of the input I XOR with it the output of a function F. F has input 3-bits and output 1-bit. The 3 input bits to F are selected from the right-half of the input. The output of F is a permutation of {00001111} so F is balanced. The 3 input bits to F are selected from the bits on the right-half so that each bit on the right half is used the same number of times (or as close as possible to that). Each "F" is generated randomly and independently one time.

Next I swap left and right halves of the result and do it again. Again, new "F" for each bit with new input.

All that is one round. I do it 6 times, each round with random, independently-generated F functions. 6 rounds take about 3ns. I've tried changing the number of rounds and the number of inputs to F, too.

Answer 1

You try the Encryption Torture Test.

Answer 2

I suspect that the usual answer would be "If you need to ask this question the best you can hope for is kid-sister grade encryption."

---

But if you must, you might start by applying the usual randnomness tests to the output (How to test random numbers?) in bytes, words, long-words, etc.

If you can't pass that you know it is weak without any further work. Note that passing this does not guarantee that it is strong.

Answer 3

If you have to ask - that's a pretty good indication that you shouldn't write your own.

If you are just wanting to write one as a learning exercise, then the Encryption Torture Test that Kirtan suggested is probably good. However, if you are planning to really use this encryption for some purpose where security is truly needed, that tool is not going to be any substitute for the years of expert analysis published algorithms have gone through.

Even if your algorithm generates output that looks random, that does NOT mean that it is necessarily secure.

Answer 4

I can almost guarantee you don't have good reason. If you do, though, submit it for review by your peers and NIST when AES comes around for replacement. Sustained examination by people who actually know what they're doing is the only way to know.

Answer 5

Post it on the internet and see if anyone can break it (What NIST/NSA did with AES, SHA-3, etc..).

I would look at all the common attacks.

• linear cryptanalysis
• differential cryptanalysis
• related key attacks
• weak key attacks
• known plaintext
• known ciphertext attacks
• adaptive chosen ciphertext attacks

Determine how large the key space is that someone must bruteforce to find the plaintext, is it smaller than all possible keys? Do two keys result in the same ciphertext?

Can you choose a plaintext which will reveal the key in the ciphertext?

Answer 6

Statistical evaluation of an encryption algorithm is necessary but not sufficient to ensure it is secure. Many algorithms have known weaknesses or potential weaknesses that have nothing to do with entropy and statistical properties of the encryption. Look at RSA (depends on factoring being hard), MD5 (collision attacks), and other algorithms. These have had man-years of rigorous probing for weaknesses.

Answer 7

Download instructions off the web for making a low grade dirty nuclear device, zip that up with a street map of Washington, D.C., then encrypt it and send it to [email protected].

The strength of your encryption algorithm will be inversely proportional to the time it takes the men in black suits to show up at your door.

Keep in mind this is likely to be a one-off experiment, at least for those couple of years you spend in Gitmo :-)

Answer 8

Following the advice of not writing your own. This doesn't mean you have to pull in a huge complex ssl library. Look at something like TEA (and is derivatives) they can be coded in a single function in a dozen lines.