Re: "Rule 30" CA encryption implementation

From: J. Campbell (mango_maniac_at_yahoo.com)
Date: 05/12/03


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
basically unsolvable.

 
> > > > The output file will appear random
> regardless
> > > > 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,

You're welcome.

> 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!!!

Cheers



Relevant Pages

  • Recommend AES Program, Please
    ... The program should allow me to enter the key, not a passphrase. ... The ciphertext must have the same number of bytes as the plaintext ... I have tried 5 programs and they all failed to meet these goals. ...
    (sci.crypt)
  • Re: Initial CTR and Key from HMAC?
    ... Given that I must use a password-based encryption model, ... IV = HMAC_sha256(Passphrase, Plaintext) ... identical ciphertext in the event that the same passphrase ...
    (sci.crypt)
  • Vigenere++ Proposal of a (new?) cipher
    ... additional ciphertext shuffling phase. ... which is a fast hash function with a low collision rate and the Mersenne ... plaintext, "C" to indicate the i-th letter of the ciphertext and ... For each character of index "i" of the plaintext: ...
    (sci.crypt)
  • Re: How to cryptanalysis of Japanese PURPLE cipher machine.
    ... I have a question about PURPLE. ... > PURPLE ciphertext in September 1940 and intervals revealed the ... already completely broken the "sixes" -- early-on frequency counts ... great deal of matched plaintext and ciphertext. ...
    (sci.crypt)
  • Chosen plain text attack on Chaocipher
    ... Submit the plaintext for encipherment ... Assume left wheel is OUHJTGLXAIEMKWVZQRPBSNYFCD and right wheel is ... Note the ciphertext we got: ... It is a repetition of the same 14 letters. ...
    (sci.crypt)