1
$\begingroup$

I wonder what kind of techniques can be used to validate implementation of cryptography algorithms?

The obvious one is to run specific algorithms against publically known test vectors (i.e. from NIST). Other idea would be to run it against some tool for fuzzing like AFL.

Would you have any other ideas, tools? How would you test against side channel?

$\endgroup$
  • $\begingroup$ This question comes pretty close to "explain cryptanalysis". $\endgroup$ – Maarten Bodewes Mar 18 '16 at 0:14
2
$\begingroup$

My own algorithm validation for block ciphers consists of the combination of the AESAVS KAT and MCT tests from the NIST CAVP, plus the NESSIE test vector sets, plus an additional MCT of 400 key changes and 10000 inner loops (like the TDES tests). The probability of a block cipher passing all these tests but failing in production is astronomically low.

Once I have generated an entire set of test results, the file is hashed and compared to a known good hash. Each test set is hashed individually. That way I do not need to compare each of the 1000s of results individually. For a complete validation, each result MUST be compared individually.

Stream ciphers are tested similarly, a variety of keys/nonces are used, outputs are generated, and sections of the output are compared against the known answer. Additionally, the entire output can be hashed and compared, although this is slower.

There are also implementation tests, where data is passed to the algorithm that should not be passed, such as invalid key and block sizes. These are necessary to test against fault and overflow attacks, but do not test the algorithm itself.

For hash functions there are similar NIST validation systems in place, one for the SHA1/2 families, which can be applied similarly to other MD type functions like Blake and MD5. This is in addition to the "health test" checks which process about a dozen values of known size and compare the outputs.

SHA3 has a similar validation system, which can be applied to Keccak and other sponge based hash functions.

ECCDH validation is routinely done by KAT and MCT testing, the NIST test only uses 24 KATs. X25519 sometimes (depends on implementation) uses a MCT with 10000 operations, and a short list of KATs.

Other algorithms use similar tests. HMAC testing for example assumes the hash function being used already passed its component test, so the HMAC test is really only testing the HMAC implementation and not the hash function.

Of course, none of these are testing for side channels. Some algorithms have been designed to be free of cache timing and power analysis side channels, but only if they are implemented precisely as designed. A 32-bit integer implementation of X25519 will not be free of side channels. Side channel testing is usually targeted at specific algorithms and implementations, and there is not a one-size-fits all method.

$\endgroup$
  • $\begingroup$ I vaguely remember that many years ago there was a news saying that the kernel of an OS was successfully verified by a program verification system but I unfortunately didn't take any note of the reference. $\endgroup$ – Mok-Kong Shen Mar 18 '16 at 15:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.