Re: C code of PEARL1, a block encryption algorithm emphasising simplicity

Tran Ngoc Duong <tranngocduong@xxxxxxxxx> wrote:

"Maaartin" <grajcar1@xxxxxxxxx> wrote in message

What about the following PRNG repeating these steps:
- Generate x using a secure PRNG.
- Generate y using a trivial PRNG.
- Output 2*x+y where the computation gets performed in GF.
- Output x+2*y where the computation gets performed in GF.

Instead of (x, y) -> (2*x+y, x+2*y) you can take any other MDS

Given all outputs you can invert the output transform and get to the
values generated by the trivial PRNG. Given only each second output
you can do nothing at all.

I think, it is a semi-secure PRNG according to you definition. I don't
think, semi-secure PRNGs occur in reality.

Yes. I think it could be considered semi-secure. I don't think it is
practically usable since it is constructed from a secure PRNG. If I have
a truly secure PRNG, I would surely find a better way to use it. No MDSs
or other such jokes.

NIST's Dual-EC DRBG was more or less like this. They generate a sequence
of points on an elliptic curve that really look random, then convert
the x-coordinates into bit strings. Unfortunately, that conversion
was defective. The end result is output that can be distinguished
from random bit strings, but decimating the output slightly results in
random-looking output.

In other words, a real, honestly designed PRNG that is semi-secure and
where decimation improves things.


Relevant Pages