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



On Aug 20, 6:34 pm, "Tran Ngoc Duong" <tranngocdu...@xxxxxxxxx> wrote:
"Maaartin" <grajc...@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
function.
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.

Agreed, I'm not sure what I could use it for. It's not secure and it
needs a secure PRNG, that's a clear loss. It's just faster, that's
all.

If I have
a truly secure PRNG, I would surely find a better way to use it. No MDSs
or other such jokes.

But maybe they do? Aren't there attacks which can be stopped by
decimating the sequence?

If one actually uses the sequence I'm sure there are easy attacks (not
much more complicated than attacking a XOR stream cipher that uses the
same key stream twice). I see no such attacks with the decimated
sequence.

With the decimated sequence there can't be any attacks, since each
it's member depends bijectively on a member of the secure sequence
which doesn't get used anywhere else. There are attacks distinguishing
it from random, which IMHO need the whole sequence.

But this isn't what I meant. I was speaking about partly-secure PRNGs
like RC4. There are attacks against RC4, which can be prevented be
dropping the beginning of the sequence.


On Aug 20, 6:44 pm, Mok-Kong Shen <mok-kong.s...@xxxxxxxxxxx> wrote:
It is well known that a system of linear equations doesn't have a
determined solution, if the determinant is zero. I am making use
essentially of an akin argument. If one thus can't even find a "path"
to the generation process of a PRNG, how could one start to break it
at all?

There's no established cryptosystem build on a zero-determinant matrix
and I'd say, there can't be any. Given enough input/output pairs you
always get enough equations. When the determinant is zero, it means
there are equivalent keys, and this is a weakness. The attacker can't
determine the key uniquely, but they don't need to; each one of them
suffices.


On Aug 20, 7:20 pm, Mok-Kong Shen <mok-kong.s...@xxxxxxxxxxx> wrote:
BTW, a historical remark: Actually the idea of exploiting
"indeterminancy" was present in a thread months ago, where I argued
with Maaatin whether a simple scheme of mine could be cracked. Maaartin
wrote a program which he reported to be capable of very speedily
breaking that in some 10 of test cases. There should however be in fact
nonetheless some errors in his work. For there was a negotiation of a
challenge prize between him and me and my challlenge offer was later
not taken up by him.

There were no errors in my program, it just took too long in some
cases. Most instances were solved much faster than you'd imagine. To
my surprise, the hard instances were the ones NOT having the maximum
period.

I never cared about the challlenge, but I'll publish the program some
day.
.



Relevant Pages

  • Re: C code of PEARL1, a block encryption algorithm emphasising simplicity
    ... the secure PRNG sort of begs the question. ... shoving the existence of something. ... multiple solutions, so you can't find out which one was actually used. ...
    (sci.crypt)
  • Re: C code of PEARL1, a block encryption algorithm emphasising simplicity
    ... Generate y using a trivial PRNG. ... I think it could be considered semi-secure. ... practically usable since it is constructed from a secure PRNG. ...
    (sci.crypt)
  • Re: new /dev/random
    ... >might be a very, very secure PRNG, but that's still what you've got, ... >turn it into a PRNG. ... And while you are at it, be honest and open about whether your ... difference between a RNG and a PRNG. ...
    (sci.crypt)
  • Re: Problem with Random function
    ... Resetting the random number generator is something you ... A PRNG generates a sequence of numbers which appear random. ... periodicity is how long that sequence is before it repeats. ...
    (comp.soft-sys.matlab)
  • Re: KISS4691, a potentially top-ranked RNG.
    ... I think in the parallel case, one would want to be able to generate a seed to produce values that are guaranteed not to overlap with any other node. ... new_seedwould depend on my_node in such a way that the generated sequence would not overlap with that produced by any other possible value of my_node. ... what if we wanted several independent streams of random numbers? ... if the designer of the PRNG was careful or just lucky. ...
    (sci.math)