# Statistical tests for pseudorandom permutations

I'm implementing a format-preserving encryption scheme similar to those described in the literature. I want to sanity test my PRP using some statistical tests like TestU01. However, I'm not sure how applicable these kinds of tests are to PRPs since they are designed to test PRNGs. Are there statistical tests that are PRP-specific? If not, would the results of a PRNG test against a collection of PRP ciphertexts be a meaningful test of its statistical pseudorandomness?

• Some hints… – e-sushi Sep 3 '14 at 21:49
• I did something similar recently, a cipher with a 5-bit domain. I used a monte carlo like test, encrypting the prior ciphertext a billion times to see if it gets stuck in a cycle – Richie Frame Sep 4 '14 at 5:48

Typically, the output of format-preserving encryption is easily distinguishable from a random bitstream, precisely because the ciphertexts conform to some non-random format. Thus, you cannot use standard statistical tests on them, at least not directly.

If the format of your FPE scheme is flexible enough, you may be able to test some aspects of it by configuring your scheme to use, say, "a block of $n$ bits" as the format. More generally, any format that has exactly $2^n$ possible ciphertexts can be bijectively mapped to $n$-bit blocks and tested that way. However, this will not let you test how your PRP behaves on domains whose size is not a power of two, which is probably what you're most interested in.

(Generally, statistical tests intended for random bitstreams can also be applied to the output of $n$-bit PRPs, e.g. with a simple counter as the input, provided that the number of $n$-bit blocks in the output to be tested is significantly below $2^{n/2}$. Above that "birthday limit", the probability of observing a repeated $n$-bit block in a truly random bitstream becomes significant, allowing a PRP to be distinguished from a random bitstream.)

In principle, you could also write your own statistical tests that can handle arbitrary ciphertext formats, e.g. by looking at existing test suites and adapting them. (Alas, while the math is not necessarily all that difficult, many standard test suites tend to be written and documented in a rather abstruse style.)

However, neither of these approaches solves that fundamental issue that, in general, statistical testing is a very poor way to test the security of a cryptographic primitive. Sure, if your "PRP" output fails a statistical test (for some reason other than its format or the birthday bound), it's a clear sign that it's not secure, but alas, the converse does not hold — it is quite possible for a totally insecure primitive to pass all standard statistical tests not specifically designed to detect the hidden weakness in that particular primitive.

Thus, to convincingly demonstrate the security of your PRP, you need to either:

1. construct it so that its security can be provably reduced to that of some other cryptographic construction which is already widely believed to be secure, or

2. publish it and invite other cryptographers to try to break it.

The difficult part with the second option is getting enough attention — good cryptanalysts are few and far between, and often busy, whereas new ciphers are dime a dozen. Thus, unless you're already a big name in the field, it can be difficult to get anyone to even look at your system. There are various ways to try to get around that, such as getting someone already well known in the field to publish an analysis of your scheme, submitting it to an international crypto standards competition, or offering a large cash prize for breaking it, but none of them are easy. Thus, where possible, a provable reduction to an existing scheme is generally preferred.

• Yeah, I don't plan on relying solely on statistical tests to argue the security of my scheme. I think of passing statistical tests as a necessary but not sufficient condition for security. – pg1989 Sep 3 '14 at 22:31
• Also, my internal PRP in the FPE scheme is merely an unbalanced Feistel network similar to the Thorp shuffle. – pg1989 Sep 3 '14 at 22:34