Crash in RandomNumberGenerator::GenerateWord32 due to stack recursion

[noloader]

Testing of RandomNumberGenerator::GenerateWord32 revealed a potential bug in GenerateBlock. GenerateBlock calls GenerateIntoBufferedTransformation. GenerateIntoBufferedTransformation, in turn, calls, GenerateBlock. Ad infinitum.

In the past, a patch to call OS_GenerateRandom was declined; see Patch for RandomNumberGenerator::GenerateIntoBufferedTransformation bug. It turns out that was not a bad decision. But the issue endured and we got a private bug report against 5.6.3rc4 due to it.

I dug up an old email thread with Wei on the same subject (from 2012 or so), and here's what he had to say about it:

Yeah, you're not supposed to use it directly. It's just meant to define the interface that other RNGs are supposed to implement, and includes some helper functions. I should probably make it so that it can't be instantiated.

So I'd like to make it so it can't be instantiated. The best way I know is to remove the implementations for GenerateIntoBufferedTransformation and GenerateBlock, and make them pure virtuals.

[DevJPM]

Am 06.10.2015 um 21:49 schrieb Jeffrey Walton:

Testing of |RandomNumberGenerator::GenerateWord32| revealed a
potential bug in |GenerateBlock|. |GenerateBlock| calls
|GenerateIntoBufferedTransformation|.
|GenerateIntoBufferedTransformation|, in turn, calls, |GenerateBlock|.
Ad infinitum.

In the past, a patch to call |OS_GenerateRandom| was declined; see
Patch for RandomNumberGenerator::GenerateIntoBufferedTransformation
bug
https://groups.google.com/d/msg/cryptopp-users/GUtJOdx9ltU/WPI8Q70MJ7oJ.
It runs out that was not a bad decision, but the issue still remains.
In fact, we got a private bug report against 5.6.3rc4 due to it.

I dug up an old email thread with Wei, and here's what he had to say
about it:

Yeah, you're not supposed to use it directly. It's just meant to
define the interface that other RNGs are supposed to implement,
and includes some helper functions. I should probably make it so
that it can't be instantiated.

So I'd like to make it so it can't be instantiated. The best way I
know is to remove the implementations for
|GenerateIntoBufferedTransformation| and |GenerateBlock|, and make
them pure virtuals.

I'd recommend leaving the implementation in the codebase, but commented
out, so anyone interested in only implementing either one can simply
copy and paste the other one to their own instantiation (or get it from
our implementations...)

I'm not sure though if this already counts as "breaking compatibility"
as it will break all external RNGs relying on our interface...

BTW: If we "fix" this we may have to do the exact same (put the caller
in place) for our implementations of RNGs (e.g. our test-CTR RNG,
RandomPool, X9.17CRNG, LGC RNG, ...)

BR

JPM

—
Reply to this email directly or view it on GitHub
#38.

[noloader]

How does the following look to you? Any objections?

// Stack recursion below... GenerateIntoBufferedTransformation calls GenerateBlock, and
// GenerateBlock calls GenerateIntoBufferedTransformation. Ad infinitum.
// 
// According to Wei, RandomNumberGenerator is an interface, and it should not be
// instantiable. Its now spilt milk, and we are going to assert it in Debug builds and
// throw in Release builds to alert the programmer. They have a reference implementation
// in case its needed. If a programmer unintentionally lands here, then they should ensure
// use of a RandomNumberGenerator pointer or reference so polymorphism can provide the
// proper runtime dispatching.

void RandomNumberGenerator::GenerateBlock(byte *output, size_t size)
{
    CRYPTOPP_UNUSED(output), CRYPTOPP_UNUSED(size);

    assert(0);
    throw NotImplemented("RandomNumberGenerator: GenerateBlock not implemented");

#if 0
    ArraySink s(output, size);
    GenerateIntoBufferedTransformation(s, DEFAULT_CHANNEL, size);
#endif
}

We could not make the base class a pure virtual, or make many/most functions pure virtual. Too many things broke in derived classes. We might be able to make GenerateBlock pure virtual.

We could not apply this to GenerateIntoBufferedTransformation. Many derived classes use the base class's GenerateIntoBufferedTransformation. In fact, it caused an exception in the self tests.

Derived classes must override GenerateBlock. This is consistent with the library's examples, and the self tests executed without exception.

[DevJPM]

Am 08.10.2015 um 01:28 schrieb Jeffrey Walton:

How does the following look to you? Ant objections?

I guess I have no "ant" objections :P
|// Stack recursion below... GenerateIntoBufferedTransformation calls
GenerateBlock, and GenerateBlock calls //
GenerateIntoBufferedTransformation. Ad infitntiuim. // // According to
Wei, RandomNumberGenerator is an interface, and it should not be
instantiable. Its now spilt milk, // and we are going to assert it in
Debug builds and throw in Release builds to alert the programmer. They
// have a reference implementation in case its needed. If a programmer
unintentially lands here, then they // should ensure they are using a
RandomNumberGenerator pointer or reference so polymorphism ensures //
proper runtime dispatching. void
RandomNumberGenerator::GenerateBlock(byte *output, size_t size) {
CRYPTOPP_UNUSED(output), CRYPTOPP_UNUSED(size); assert(0); throw
NotImplemented("RandomNumberGenerator: GenerateBlock not
implemented"); #if 0 ArraySink s(output, size);
GenerateIntoBufferedTransformation(s, DEFAULT_CHANNEL, size); #endif } |

We could not make the base class a pure virtual. Lots of things broke.

We could not apply this to |GenerateIntoBufferedTransformation|. Many
derived classes use the base class's
|GenerateIntoBufferedTransformation|. In fact, it caused an exception
in the self tests. Derived classes must override |GenerateBlock|.

As long as they realize that they may as well override
GenerateIntoBufferedTransformation() and adapt GenerateBlock() (which
they may looking at that comment above the function) I'm fine.

So no objections :)

BR

JPM

—
Reply to this email directly or view it on GitHub
#38 (comment).

[noloader]

As long as they realize that they may as well override GenerateIntoBufferedTransformation() and adapt GenerateBlock() (which they may looking at that comment above the function) I'm fine.

Yeah, this is one of those areas where I think we want to document and lead by example.

We discuss creating a generator on the wiki at RandomNumberGenerator | Creating A Generator. We also provide a sample generator on the wiki at Mersenne Twister.

---

So no objections :)

OK, good. I'm going to close it.

[noloader]

The AutoSeeded generators override GenerateIntoBufferedTransformation, and not GenerateBlock. We are in a situation where about half the generators override one function, and about half override the other. We cannot move to throw in any of the functions.

I don't want to modify about half the generators just to enforce design criteria. I think its a bit much, even if it may be a good idea. If the group wants it, then we can do it.

We added self tests to validat1.cpp to catch any other breaking changes in the future. The self test is named TestAutoSeeded.

[noloader]

So this is interesting... Based on Uri's suggestion, we added a self test for AutoSeededRandomPool called TestAutoSeeded(). Here's what it found under Undefined Behavior sanitizer:

20064:randpool.cpp:49:36: runtime error: signed integer overflow: 1876017710 + 1446085457
    cannot be represented in type 'long int'

The offending statement was:

*(time_t *)(m_seed.data()+8) += t;

For completeness, here's what it was changed to:

// *(time_t *)(m_seed.data()+8) += t;
assert(m_seed.size() >= 16);
word64 tt1, tt2 = (word64)t;
memcpy(&tt1, m_seed.data()+8, 8);
memcpy(m_seed.data()+8, &(tt2 += tt1), 8);