# What's the reason for Monte Carlo tests for block ciphers?

NIST specifies that implementations were required to create Monte Carlo test vectors for ECB and CBC mode for the AES competition.

What's the reason for these tests? The only thing I can think of is that it is some randomized testing of the block cipher in specific modes. However, in that case the difference between ECB and CBC would not matter.

It seems to me that this is a weird way to test for implementation errors. You'd expect things like bounds checking and such, but just performing the encryption over and over again may not actually hit the right results. And weird keys / input values are also covered by the other tests.

Finally, having the algorithm generate it's own input seems dangerous. If the block cipher doesn't behave as specified, then the input may be erroneous. So why use the block cipher as DRBG and not another well specified / tested algorithm?

• Seems to me that iterating the cipher is a good way to verify that an implementation usually works as expected. If any of the iterations hits an error, it's quite unlikely that any errors in later iterations would exactly cancel it, so a correct output from the last iteration is a pretty good indicator that all the iterations were correct. True, such testing is unlikely to hit any really rare special cases, but it allows you to exercise a lot of "typical" cases with a relatively small number of test inputs and outputs. – Ilmari Karonen Apr 10 at 16:48
• The link to the NIST specification is to a Greek ftp site. Maybe provide a link to NIST's web site? – Squeamish Ossifrage Apr 11 at 3:40

As usual, government departments simply repeat their existing rules. So they incorporated the Monte Carlo tests from earlier test documents, this time from 1980. If you follow the dusty trail from Maarten's link, you eventually arrive at NBS Special Publication 500-20, Validating the Correctness of Hardware Implementations of the NBS Data Encryption Standard. These are the two relevant extracts.

This publication describes the design and operation of the NBS testbed that is used for the validation of hardware implementations of the Federal Information Processing Data Encryption Standard (DES).

and

Since the test set is known to all, an additional series of tests is performed using pseudo-random data to verify that the device has not been designed just to pass the test set. In addition a successful series of Monte Carlo tests give some assurance that an anomalous combination of inputs does not exist that would cause the device to hang or otherwise malfunction for reasons not directly due to the implementation of the algorithm. While the purpose of the DES test set is to insure that the commercial device performs the DES algorithm accurately, the Monte Carlo test is needed to provide assurance that the commercial device was not built expressly to satisfy the announced tests.

So it is there to test future hardware implementations of AES.

Conceivably if there were only fixed known-answer test vectors, a fraudulent hardware designer could make a circuit that just matches those but falls apart the moment you try to use it in the real world. It would pass certification but it would be completely useless. For example, it might compute a Lagrange interpolant of the fixed known-answer test vectors in $$\operatorname{GF}(2^{128})$$. So while fixed known-answer test vectors are helpful debugging tools, they are not good certification criteria.

• These are fixed known answer values, as they start with the same "seed" (key, plaintext and - for CBC - IV). OK, there are 16 million correct answers that are required, but it would still be easy to work your way around that when making deliberate changes in the code. With so many the change would be very deliberate though, and probably easy to spot in a code review. – Maarten - reinstate Monica Apr 11 at 8:47
• OK, that's silly. I didn't read the document because ftp sites aren't convenient to browse through Tor, and there was no other bibliographic information, and I was too lazy to look up the keywords, so I guessed you were referring to NIST's certification criteria for algorithm validation, which does use unpredictable inputs. I guess it's effectively just a large sequence of known-answer tests, then, that can be compressed into a single output. – Squeamish Ossifrage Apr 11 at 21:41