5
$\begingroup$

Real-world encryption systems are often not broken algorithmically but because the implementation has a bug. Sometimes the bug only happens in circumstances that could not have been foreseen, such as weak random numbers, or an error in a library causing e.g. predictable IVs.

So I wonder, are there workable methods of estimating randomness or entropy that could be helpful to detect (a subset of) actual failures in cryptographic systems?

As a simple example, such an estimator could be fed with consecutive CTR IVs and alert higher protocol layers when there is an apparent failure, because all IVs are identical for example. Or an estimator could be fed with encrypted DES output to detect a bug in the implemention.

Improve this question
$\endgroup$
10
  • $\begingroup$ Do you mean this would be installed in production installations, and executed periodically somehow? Or are you suggesting a test harness that an implementer could wire in to "certify" the implementation? $\endgroup$
    – John Deters
    Jul 18, 2013 at 18:49
  • $\begingroup$ I mean in production installations, and preferably executed continually (so cost is important). Take as example CBC mode AES used for repeated messages - monitoring the IV value for randomness continously would allow the sender to stop sending when a catastrophic IV failure is detected. $\endgroup$
    – Marc Lehmann
    Jul 18, 2013 at 19:19
  • $\begingroup$ Regarding failure modes: An example of a failure mode could be a compiler bug that causes the IV value not to be calculated at all, but isntead being left at it's previous value, or using some semi-random data garbage left on the stack etc. The original program might be secure and correct while being tested, and might malfucntion somewhere else. The idea is having an extra failsafe mechanism, not something that is guaranteed to work. $\endgroup$
    – Marc Lehmann
    Jul 18, 2013 at 19:21
  • 1
    $\begingroup$ @JohnDeters I think he means e.g. check that something has gone wrong with the entropy supply algorithmically, in the same way that TRNG's need to do some tests on their output periodically to verify they haven't failed. It's an interesting question but it seems unlikely such an estimator exists, unless you are willing to run statistical tests on terabytes of data to detect a potential flaw. The problem is there just isn't enough data to assert that "this IV is not random, abort the mission", you need a lot more samples to conclude anything about what you are seeing. $\endgroup$
    – Thomas
    Jul 18, 2013 at 21:02
  • 2
    $\begingroup$ I can see this working somewhat as a one-off implementation test bench, but it just doesn't seem doable to do those verifications constantly with any degree of accuracy. The old quote rings true: "that's the problem with randomness - you can never be sure". $\endgroup$
    – Thomas
    Jul 18, 2013 at 21:06

1 Answer 1

Reset to default
1
$\begingroup$

Such practices are commonly applied to results of some random number generators, but less often to other applications.

There is one very common such fail-safe test

NIST's FIPS 140-2 requires very simple contiguous test for random number generation: store previous generated block and compare. Only if the block is different it is assumed that the RNG did not fail.

From FIPS 140-2 4.9.2:

Continuous random number generator test. If a cryptographic module employs Approved or non- Approved RNGs in an Approved mode of operation, the module shall perform the following continuous random number generator test on each RNG that tests for failure to a constant value.

More entropy tests

The standard (FIPS 140-2) used to require more tests (mono bit test, poker test, runs test, long runs test). These tests give fairly good estimate of if input appears random. These were decommissioned, because they work better with NDRBG than RNGs required by the standard (see FIPS 140-2 Annex C if you need details), and because for some cases it is excessive requirement to produce 20000 bits for analysis (it may be that you just needed one 128-bit key). AIS31 standard used to evaluate true random number generators uses some very similar tests.

Used in practice

These tests are useful against some hardware random bit generators and for this reason, Linux rngd program is running the tests (previously part of FIPS 140-2) to ensure quality of entropy gotten (for example from /dev/hwrng) and to ignore inputs which appear non-random.

You may use Linux rngtest program to apply these tests to data of your choice, for instance, examine output of (possibly) buggy encryption software.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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