Allen Roginsky, CMVP NIST
There are power-up tests and conditional tests. Power-up includes integrity test, approved algorithm test, critical functions tests. Conditional are things like generating key pairs, a bypass test.
Implementations have become more robust, and integrity tests no longer take just a second or so - may be minutes.
Imagine a smartcard used to enter a building. If it is too slow, it may take 5-10 seconds... then the next person... the next. Quite a traffic jam
We don't want to drop the tests altogether, so what do we do? What are other industries doing?
Supposed the software/firmware image is represented as a bit-string. The module beraks the string into n substrings; n is no greater than 1024. the length, k bits, of each of the first (n-1) substrings is the same; the length of the last substring is no greater than k. Then, maybe you can just look at some of the strings.
A bloom filter optimization can significantly improve the efficiency of this method.
You could use a deterministic approach. You would have to keep track of the location where you ended, and hope that location doesn't get corrupted.
CMUF is working on an update to Implementation Guidance on doing integrity check from random sampling.
Vendors do not want to perform each algorithm's known answer test, not just delay until first use of algorithm. Why are we doing this test in the first place? Something to think about.
Another option offered by a questioner: maybe replace with on demand testing? Is a good option.
Flakes Welcome - "Hi, I'd like a cake, please, and could you put a 'happy birthday' plaque on it?" "No, no, I mean one of those plastic things on a spike - you know, a 'h...