Re: "Rule 30" CA encryption implementation
From: J. Campbell (mango_maniac_at_yahoo.com)
Date: 12 May 2003 14:24:29 -0700
"Douglas A. Gwyn" <DAGwyn@null.net> wrote in message news:<3EBFD25F.FA17129@null.net>...
> "J. Campbell" wrote:
> > kind of like diffusion...given a particular 1000-bit line of a rule-30
> > automata, it's pretty difficult to determine an 80-bit initial state
> > that leads to the particular final state.
> I think you mean, so far as Wolfram knows, nobody has published
> an efficient way to do this for that specific system. **I know
> people who could do it if they needed to**.
Doug, I find this highly doubtful. You say there is a method to go
backwards up rule30??!!! I'd love to see this demonstrated...down is
(a xor (b or c))...how, now, do you go backwards up this automata???
suppose one uses a 10 byte passphrase...that's 80 bits...I don't think
there's another way to get the ~700 bit passkey for a particular
passphrase, or to get the passphrase, given the passkey other than to
start analyzing passphrases...and at 80-bits...there are a lot of
possibilities...and considering that the implementation I use accepts
passwords of arbitrary length, I believe the basic problem is
intractable. If I'm wrong, I'd love to see an example. I'm willing
to send you a passkey and let your 'friends' tell me the passphrase.
I'd be willing to do you a favor and provide the whole last line, not
just the subset of the last line I use...I still think the problem is
> > > > The output file will appear random
> > > > of the regularity of the input data-stream,
> > > > or the particular password chosen.
> > > It can't possibly do that, for a variety of reasons.
> > this isn't quite true.
> Sure it is, assuming that the ciphertext is not larger than the
> plaintext; it's a simple application of the pigeonhole principle.
> Or consider: If any possible input to the decryptor using any
> key produces plaintext that could be reencrypted using the same
> key to reproduce the original input, then you could feed in a
> highly regular ciphertext to discover which plaintext would
> produce that ciphertext. It might not be a plaintext that you
> would be likely to ever use, but it serves as a counterexample.
This is the same example I mentioned...where i mentioned the
possibility that a jpeg of a frog might be encrypted as a text of a
book on frogs...it's not likely, and even if it did happen, it
wouldn't help someone decode an encrypted file!!!
> I thank you for making your implementation available for people
> to play with,
> but caution you about assuming its security.
I neither made assumptions nor did I advocate anyone implementing my
scheme...however, I do agree with Wolfram's basic premis that this
particular automata is intractable...and I'll be surprised, and will
dutifully renounce the security of my program in this forum, if your
'friends' are able to go backwards 500+ steps (the minimum used with
my scheme) up a rule 30 automata and state the initial (80-bit) state
for a given final state!!!