Multiciphering and Random Cipher Selection in Shannon

A Ciphers By Ritter Page

I have long proposed using a multiciphering "stack" of ciphers, instead of just one which could be weak beyond our knowledge. I have long proposed using multiple ciphers instead of just one, to end any "break" which might exist. Conventional cryptography has considered these ideas strange and unnecessary. Yet these ideas originate in Shannon, the first source of mathematical cryptography itself:

Shannon, C. 1949. Communication Theory of Secrecy Systems. Bell System Technical Journal. 28: 656-715.

Contents

• 2001-06-19 Terry Ritter: "With all the reading of Shannon . . . , I have been waiting for the discussion of Multiciphering and Random Cipher Selection." " 'The first combining operation is called the product operation and corresponds to enciphering the message with the first secrecy system R and enciphering the resulting cryptogram with the second system S, the keys for R and S being chosen independently.'" "The second combining operation is 'weighted addition.'"
• 2001-06-19 SCOTT19U.ZIP_GUY: "One should also note that the encryption systems Shannon is refering to are fully bijective."
• 2001-06-20 Terry Ritter: "As far as I can see, these issues are separate: the concept of combining ciphers in these two ways does not require ciphers with the perfect secrecy property." "If we are going to demand that every cipher we use have perfect secrecy, we will not have many ciphers to select from."
• 2001-06-20 Mok-Kong Shen: "We are likely to have wait till eternity in order to get a 'real' cipher that is perfectly secure."
• 2001-06-20 SCOTT19U.ZIP_GUY: "I was not talking about "perfect security". You missed my point."
• 2001-06-20 Mok-Kong Shen: "Your argument of the danger of not applying a compression scheme like that you have been propagating could under circumstance scare people away from applying compression in the first place . . . ."
• 2001-06-19 Mok-Kong Shen: "I agree fully with what you (very lucidly) wrote in support of the employment of multiple encryption algorithms."
• 2001-06-20 Bo Dömstedt: "In 1995 I found a way to implement ciphers, so that the function that encrypt data is varying during encryption."
• 2001-06-22 Mark Wooding: "This is snake-oil, dressed up in academic clothing."
• 2001-06-22 John Savard: "I suppose those little implementation details that convert the system from an elaborate one-way hash into a usable cipher were fuzzed over . . . ."
• 2001-06-22 David Wagner: "Agreed. It is easy to see that uncomputability doesn't have much to do with computationally-secure encryption."
• 2001-06-22 SCOTT19U.ZIP_GUY: "Well the only reason that in the modern ciphers you work with that a correct key from a lucky guess can be verifed as true is due to the poor design of modern ciphers."
• 2001-06-27 Bo Dömstedt: "The proof is by Jesper Jansson, Dep. Computer Science, Lund University." "Thank you for your note, this comment will be considered when we update the report."
```
Subject: Multiciphering and Random Cipher Selection in Shannon
Date: Tue, 19 Jun 2001 03:48:23 GMT
From: ritter@io.com (Terry Ritter)
Message-ID: <3b2ec9d9.2169032@news.io.com>
References: <90BDB945AH110W296LC45WIN3030R@207.36.190.226>
<3b255450.442318@news.powersurfr.com>
Newsgroups: sci.crypt
Lines: 128

With all the reading of Shannon . . .

Shannon, C.  1949.  Communication Theory of Secrecy Systems.  Bell
System Technical Journal.  28: 656-715.

. . . , I have been waiting for the discussion of Multiciphering and
Random Cipher Selection.

MULTICIPHERING

In section 1, "Introduction and Summary," on p. 658, Shannon talks
about "combining operations," but these are not the combining of two
Shannon combiners combine whole "secrecy systems" or ciphers (these
are secret key ciphers):

"The first combining operation is called the product operation and
corresponds to enciphering the message with the first secrecy system R
and enciphering the resulting cryptogram with the second system S, the
keys for R and S being chosen independently."

This is multiciphering, chain ciphering or cascade ciphering; it is
the ciphering "stacks" I have many times proposed to address the risk
of unknown weakness in a cipher, a weakness inherent in conventional
ciphering wisdom.  There are various security advantages:

1.  A cipher stack prevents a single broken cipher from exposing our
information.  Since any particular cipher may be broken when we use it
(the opponents do not tell us), this is a significant improvement.

2.  A 3-cipher stack hides the "known-plaintext" and
"defined-plaintext" information for the individual ciphers.  Such
information simply is not exposed to the opponents, which thus
prevents known-plaintext and defined-plaintext attacks on the
individual ciphers.  The construction itself thus eliminates whole
classes of attack on the component ciphers.

3.  A 3-cipher stack gives us exponentially many (n**3, or perhaps
just n**2 for weenies) different ciphering stack possibilities.  The
have enough.  Instead, the point is the easy construction of
exponentially many conceptually different overall ciphering functions
which the opponents must engage.

4.  Weenies could specify that their particular favorite cipher would
always be part of the (changing) cipher stack, thus guaranteeing at
least as much strength as using that cipher alone.  This leaves little
room to argue that the cipher stack concept is not as secure as using
any particular single cipher.

The added execution cost is two extra layers of ciphering.

RANDOM CIPHER SELECTION

"The second combining operation is 'weighted addition.'

"T = pR + qS, p+q = 1

"It corresponds to making a preliminary choice as to whether system R
or S is to be used with probabilities p and q respectively.  When this
is done R or S is used as originally defined."

That description can be confusing.  Fortunately, the topic is
addressed just a little differently in section 6, "The Algebra of
Secrecy Systems," p. 670 (but note the change of symbols):

"If we have two secrecy systems T and R we can often combine them in
various ways to form a new secrecy system S.  If T and R have the same
domain (message space) we may form a kind of "weighted sum,"

"S = pT + qR

"where p + q = 1.  This operation consists of first making a
preliminary choice with probabilities p and q determining which of T
and R is used.  This choice is part of the key of S.  After this is
determined T or R is used as originally defined.  The total key of S
must specify which of T and R is used and which key of T (or R) is
used."

Then, on p. 672, we have:

"It should be emphasized that these combining operations of addition
and multiplication apply to secrecy systems as a whole.  The product
of two systems T and R should not be confused with the product of the
transformations T[i]R[j], which also appears often in this work."

Shannon's multiplication combining is thus nothing less than a keyed
selection between two ciphers, which is then generalized for "n"
ciphers (p. 671).  I have many times proposed selecting among multiple
ciphers to address the problem of using a broken cipher forever, as
one now does in conventional cryptography if the break is not exposed.
I have proposed using a simple handshake (not a complex cryptographic
protocol) under cipher for cipher agreement, instead of
message-by-message (or faster!) keyed selection, but the basic idea of
selecting a cipher at random is the same.  Again, there are various

1.  Having frequent cipher changes guarantees that we *can* change
ciphers, immediately and easily, if any cipher we use is found weak.

2.  A cipher change terminates any existing break.  Since we will not
know when a break exists (and that our information is being exposed),
this provides an alternative to just using the same cipher forever and
hoping for the best.

3.  Cipher changes prevent information from being concentrated under a
single overall cipher, which would otherwise be a primary attack
target.  This prevents the opposing attack budget from concentrating
on a single target.

4.  Cipher changes support the continued creation and use of new
ciphers, which the opponents must then identify, obtain, analyze and
break.  Cryptanalysis for practical weakness will cost opponents more
than new ciphers will cost us, and each different opponent must pay.
Cryptanalysis takes longer than use, so the opponents probably will
never even know the complete set of ciphers actually in use.

This has little execution cost.

---
Terry Ritter   ritter@io.com   http://www.io.com/~ritter/
Crypto Glossary   http://www.io.com/~ritter/GLOSSARY.HTM

Subject: Re: Multiciphering and Random Cipher Selection in Shannon
Date: 19 Jun 2001 10:39:15 GMT
From: david_a_scott@emailv.com (SCOTT19U.ZIP_GUY)
Message-ID: <90C522CF7H110W296LC45WIN3030R@207.36.190.226>
References: <3b2ec9d9.2169032@news.io.com>
Newsgroups: sci.crypt
Lines: 64

ritter@io.com (Terry Ritter) wrote in <3b2ec9d9.2169032@news.io.com>:

>
>With all the reading of Shannon . . .
>
>Shannon, C.  1949.  Communication Theory of Secrecy Systems.  Bell
>System Technical Journal.  28: 656-715.
>
>. . . , I have been waiting for the discussion of Multiciphering and
>Random Cipher Selection.
>
>
>MULTICIPHERING
>
>In section 1, "Introduction and Summary," on p. 658, Shannon talks
>about "combining operations," but these are not the combining of two
>Shannon combiners combine whole "secrecy systems" or ciphers (these
>are secret key ciphers):
>
>"The first combining operation is called the product operation and
>corresponds to enciphering the message with the first secrecy system R
>and enciphering the resulting cryptogram with the second system S, the
>keys for R and S being chosen independently."
>
>

One should also note that the encryption systems Shannon is
refering to are fully bijective. Meaning not only does an
input message map to same cipher text under a set of keys.

But when decipering a cipher text with the wrong keys it
would also map back to the input message space. This unfortunatly
will not happen with most modern implimentation of chainned ciphers.
Unless one plays a careful matching game that seems not to be
played much to day.

But I agress one should set up several ciphers so they can
be select and used in chaining. One such cipher is already set up
to be used in this kind of chain that is BICOM. Shannon would have
liked it.

We as the open community should set up several cipher programs
that can be indiviual chainned such that they use as input the
set of all binary files and as output the set of all binary files
then this Shannon kind of chaining for increased security could
easily be achieved.

David A. Scott
--
SCOTT19U.ZIP NOW AVAILABLE WORLD WIDE "OLD VERSIOM"
http://www.jim.com/jamesd/Kong/scott19u.zip
My website http://members.nbci.com/ecil/index.htm
MY Compression Page http://members.nbci.com/ecil/compress.htm
**TO EMAIL ME drop the roman "five" **
Disclaimer:I am in no way responsible for any of the statements
made in the above text. For all I know I might be drugged.
As a famous person once said "any cryptograhic
system is only as strong as its weakest link"

Subject: Re: Multiciphering and Random Cipher Selection in Shannon
Date: Wed, 20 Jun 2001 05:25:45 GMT
From: ritter@io.com (Terry Ritter)
Message-ID: <3b3033be.8111425@news.io.com>
References: <90C522CF7H110W296LC45WIN3030R@207.36.190.226>
Newsgroups: sci.crypt
Lines: 81

On 19 Jun 2001 10:39:15 GMT, in
<90C522CF7H110W296LC45WIN3030R@207.36.190.226>, in sci.crypt
david_a_scott@emailv.com (SCOTT19U.ZIP_GUY) wrote:

[...]
>>
>>MULTICIPHERING
>>
>>In section 1, "Introduction and Summary," on p. 658, Shannon talks
>>about "combining operations," but these are not the combining of two
>>Shannon combiners combine whole "secrecy systems" or ciphers (these
>>are secret key ciphers):
>>
>>"The first combining operation is called the product operation and
>>corresponds to enciphering the message with the first secrecy system R
>>and enciphering the resulting cryptogram with the second system S, the
>>keys for R and S being chosen independently."
>>
>>
>
>   One should also note that the encryption systems Shannon is
>refering to are fully bijective. Meaning not only does an
>input message map to same cipher text under a set of keys.
>
>  But when decipering a cipher text with the wrong keys it
>would also map back to the input message space.

As far as I can see, these issues are separate: the concept of
combining ciphers in these two ways does not require ciphers with the
perfect secrecy property.

If we are going to demand that every cipher we use have perfect
secrecy, we will not have many ciphers to select from.

>This unfortunatly
>will not happen with most modern implimentation of chainned ciphers.
>Unless one plays a careful matching game that seems not to be
>played much to day.

Oddly, within the past few months I myself have described Dynamic
Transposition ciphers which do have perfect secrecy on a
block-by-block basis.

>   But I agress one should set up several ciphers so they can
>be select and used in chaining. One such cipher is already set up
>to be used in this kind of chain that is BICOM. Shannon would have
>liked it.
>
>   We as the open community should set up several cipher programs
>that can be indiviual chainned such that they use as input the
>set of all binary files and as output the set of all binary files
>then this Shannon kind of chaining for increased security could
>easily be achieved.
>
>
>
>
>David A. Scott
>--
>SCOTT19U.ZIP NOW AVAILABLE WORLD WIDE "OLD VERSIOM"
>http://www.jim.com/jamesd/Kong/scott19u.zip
>My website http://members.nbci.com/ecil/index.htm
>MY Compression Page http://members.nbci.com/ecil/compress.htm
>**TO EMAIL ME drop the roman "five" **
>Disclaimer:I am in no way responsible for any of the statements
> made in the above text. For all I know I might be drugged.
>As a famous person once said "any cryptograhic
>system is only as strong as its weakest link"

Note that this logic does not apply to a "chain" of ciphers, where the
chain is as strong as the *strongest* link or cipher.

---
Terry Ritter   ritter@io.com   http://www.io.com/~ritter/
Crypto Glossary   http://www.io.com/~ritter/GLOSSARY.HTM

Subject: Re: Multiciphering and Random Cipher Selection in Shannon
Date: Wed, 20 Jun 2001 10:01:47 +0200
From: Mok-Kong Shen <mok-kong.shen@t-online.de>
Message-ID: <3B30586B.1EB1BC5@t-online.de>
References: <3b3033be.8111425@news.io.com>
Newsgroups: sci.crypt
Lines: 20

Terry Ritter wrote:
>

> If we are going to demand that every cipher we use have perfect
> secrecy, we will not have many ciphers to select from.

Very true. We are likely to have wait till eternity in
order to get a 'real' cipher that is perfectly secure.

> Oddly, within the past few months I myself have described Dynamic
> Transposition ciphers which do have perfect secrecy on a
> block-by-block basis.

I would in your place qualify that with 'under certain
ideal assumptions', if I remember discussions way back
correclty.

M. K. Shen

Subject: Re: Multiciphering and Random Cipher Selection in Shannon
Date: 20 Jun 2001 12:41:09 GMT
From: david_a_scott@emailv.com (SCOTT19U.ZIP_GUY)
Message-ID: <90C645DEEH110W296LC45WIN3030R@207.36.190.226>
References: <3b3033be.8111425@news.io.com>
Newsgroups: sci.crypt
Lines: 55

ritter@io.com (Terry Ritter) wrote in <3b3033be.8111425@news.io.com>:

>>
>>   One should also note that the encryption systems Shannon is
>>refering to are fully bijective. Meaning not only does an
>>input message map to same cipher text under a set of keys.
>>
>>  But when decipering a cipher text with the wrong keys it
>>would also map back to the input message space.
>
>As far as I can see, these issues are separate: the concept of
>combining ciphers in these two ways does not require ciphers with the
>perfect secrecy property.

I was not talking about "perfect security". You missed my point.
Example since one has the source code. Suppouse you encrypt
a message with 3 ciphers your favorite scheme. know suppose
at end you get a message C out of the 3 cipher system.

You then start to test keys ( not I know the time factor
large just looking at information leakage) You first test
a key for the third cipher to partially decrypt it.
Know suppose the decrypted message is such that the second
cipher could not have produced it. You have proven that
your guess for last key is wrong. Independent of the possible
key values for first 2 ciphers.

To show how this applies in real world pretend using
AES where input message padded to full blocks in CBC mode
for first two ciphers. So output at stage two is only full blocks
then for stage 3 you use Matts BICOM. The above three will
encrypt anything. But when you start looking from back end
almost every key you decyrpt with at the BICOM stage leads
back to a file size that could not have been encrypted with
the last stage of AES since it only writes full blocks out.
While decryption with random key in BICOM almost any size file
can come out and most will not be a nice length for RIJNDAEL.
Therefor you can eliminate key as bad right away. THe problem
with is that this is easy to fix with impedance matching
sections but few understand or see how easy this is.

David A. Scott
--
SCOTT19U.ZIP NOW AVAILABLE WORLD WIDE "OLD VERSIOM"
http://www.jim.com/jamesd/Kong/scott19u.zip
My website http://members.nbci.com/ecil/index.htm
MY Compression Page http://members.nbci.com/ecil/compress.htm
**TO EMAIL ME drop the roman "five" **
Disclaimer:I am in no way responsible for any of the statements
made in the above text. For all I know I might be drugged.
As a famous person once said "any cryptograhic
system is only as strong as its weakest link"

Subject: Re: Multiciphering and Random Cipher Selection in Shannon
Date: Wed, 20 Jun 2001 17:32:31 +0200
From: Mok-Kong Shen <mok-kong.shen@t-online.de>
Message-ID: <3B30C20F.520BBABB@t-online.de>
References: <90C645DEEH110W296LC45WIN3030R@207.36.190.226>
Newsgroups: sci.crypt
Lines: 27

"SCOTT19U.ZIP_GUY" wrote:
>

[snip]
>  Therefor you can eliminate key as bad right away. THe problem
> with is that this is easy to fix with impedance matching
> sections but few understand or see how easy this is.

Just a very tiny remark. Your argument of the danger of
not applying a compression scheme like that you have been
propagating could under circumstance scare people away
from applying compression in the first place, which
certainly is void of that type of security threats.

I would personally only consider compression that contains
a 'key' and thus regard that, in the context of multiple
encryption, as a 'particular' kind of cipher that doesn't
preserve the length. (Employing homophones, which always
expands, i.e. doing the opposite of compression, could
thus be considered together with compression from sort
of 'unified' standpoint, I believe.)

M. K. Shen
-------------------------
http://home.t-online.de/home/mok-kong.shen

Subject: Re: Multiciphering and Random Cipher Selection in Shannon
Date: Tue, 19 Jun 2001 12:43:24 +0200
From: Mok-Kong Shen <mok-kong.shen@t-online.de>
Message-ID: <3B2F2CCC.2882D2C2@t-online.de>
References: <3b2ec9d9.2169032@news.io.com>
Newsgroups: sci.crypt
Lines: 34

Terry Ritter wrote:
>
> With all the reading of Shannon . . .
[snip]

Though my knowledge is very humble, I agree fully with
what you (very lucidly) wrote in support of the employment
of multiple encryption algorithms. High variability is an
effective weapon against the opponent. Combinatorial
explosion thwarts his efforts, unless perhaps new
advancements in sciences, maybe quantum computers,
alleviates that problem for him. (This argument evidently
wouldn't hold in the case of an opponent of unbounded
resources. Fortunately, we don't have such a one in our
poor real world.)

A point that I think could be considered is with repect
to the common situation where one uses block ciphers.
with several different block ciphers (the number could
also be variable), one could first let one block cipher
process the whole message with appropriate chanining.
Then one could do a pass of very simple and hence
relatively cheap operations, e.g. permuting the words
(of 32/64 bits) or doing a chaining with an IV, etc. etc.
After that one applies a second block cipher, and so on.
That is, one could do sort of employing the block
ciphers in parallel instead of in series.

M. K. Shen
-------------------------
http://home.t-online.de/home/mok-kong.shen

Subject: Re: Multiciphering and Random Cipher Selection in Shannon
Date: Wed, 20 Jun 2001 10:31:30 GMT
From: bo.doemstedt@mbox200.swipnet.se (Bo Dömstedt)
Message-ID: <3b3070f7.72238690@nntpserver.swip.net>
References: <3b2ec9d9.2169032@news.io.com>
Newsgroups: sci.crypt
Lines: 23

ritter@io.com (Terry Ritter) wrote:
> Shannon's multiplication combining is thus nothing less than a keyed
> selection between two ciphers, which is then generalized for "n"
> ciphers (p. 671).  I have many times proposed selecting among multiple
> ciphers to address the problem of using a broken cipher forever, as
> one now does in conventional cryptography if the break is not exposed.
> ---
> Terry Ritter   ritter@io.com   http://www.io.com/~ritter/
> Crypto Glossary   http://www.io.com/~ritter/GLOSSARY.HTM

In 1995 I found a way to implement ciphers, so that the function that
encrypt data is varying during encryption. As special cipher
implementations don't attract much interest, I have been working
with a theory explaining how the cipher works.

We have now, included in our server update at Protego Information,
a page on this encryption technology:
http://www.protego.se/encrypt.htm

Bo Dömstedt
Chief Cryptographer
Protego Information AB

Subject: Re: Multiciphering and Random Cipher Selection in Shannon
Date: 22 Jun 2001 18:00:56 GMT
From: mdw@nsict.org (Mark Wooding)
Message-ID: <slrn9j71uo.clo.mdw@daryl.nsict.org>
References: <3b3070f7.72238690@nntpserver.swip.net>
Newsgroups: sci.crypt
Lines: 58

Bo Dömstedt <bo.doemstedt@mbox200.swipnet.se> wrote:

> In 1995 I found a way to implement ciphers, so that the function that
> encrypt data is varying during encryption. As special cipher
> implementations don't attract much interest, I have been working
> with a theory explaining how the cipher works.

I shouldn't bother.  We've seen it all before.

> We have now, included in our server update at Protego Information,
> a page on this encryption technology:
> http://www.protego.se/encrypt.htm

Arrgh!  Will someone kill this meme, please?

This is snake-oil, dressed up in academic clothing.  It's thoroughly
disingenuous.  I'm amazed, and disappointed, actually, given that Bo
D\"omstedt is a /contributor/ to the Snake Oil FAQ!

Your proof of Theorem 1 in `The Theory of Dynamic Encryption, a New
Approach to Cryptography' is, of course, entirely wrong.

Firstly, note that the set of inputs to a halting Turing machine is
countable, and hence may be enumerated (and computably so, since the
inputs are strings over a finite alphabet).  We introduce the bijection
B: N -> T^* from natural numbers to input tapes.

Now consider the following process:

Set i <- 0
Repeat:
Construct the input M <- B(i)
Compute C <- F_1(M) and C' <- F_2(M)
If C = C' then output `different: M, C, C'' and halt

If F_1 and F_2 are indeed different, the above process will halt in
finite time.  (If they're not, then it won't, but that wasn't the
problem set: I had to separate them, not decide whether they were
equal.)

It all gets rather bathetic[1] later.  The `paper' proposes that the
plaintext and key, together, be considered as the input to a UTM whose
input language is such that any binary string is valid.  The output of
the UTM is then used as a key stream, and combined with the plaintext
using some simple bijective combiner.

No mention is made of the possibility of the UTM halting before emitting
enough output, emitting trivial output, or never halting or emitting any
output at all.

I think the best bit of all, though, is that the legitimate recipient
appears to be in the same boat as the cryptanalyst.  Since the key and
plaintext are required to recreate the key stream, and the recipient has
the key but not the plaintext, he's in a bit of a pickle, really.

[1] Look it up.

-- [mdw]

Subject: Re: Multiciphering and Random Cipher Selection in Shannon
Date: Fri, 22 Jun 2001 18:41:57 GMT
From: jsavard@ecn.ab.SBLOK.ca.nowhere (John Savard)
Message-ID: <3b338fb4.11179320@news.powersurfr.com>
References: <slrn9j71uo.clo.mdw@daryl.nsict.org>
Newsgroups: sci.crypt
Lines: 51

On 22 Jun 2001 18:00:56 GMT, mdw@nsict.org (Mark Wooding) wrote, in
part:

>Arrgh!  Will someone kill this meme, please?

I don't think that's possible.

I agree that such notions can generate a lot of snake-oil, and in
another thread a mention of this system did strike me as having some
rather odd stuff in the discussion about Turing machines.

But it's possible to have a system of the form illustrated in the
diagram on the page

http://www.protego.se/encrypt.htm

which is amenable to decryption by the legitimate reciever.

From the message, generate a hash of the message.

Use the hash to select/construct an algorithm.

Using the secret key,

1) encipher the hash using a fixed algorithm,

2) apply the algorithm specified by the hash to the message.

Transmit both the enciphered hash and the encrypted message to the
legitimate recipient.

I suppose those little implementation details that convert the system
from an elaborate one-way hash into a usable cipher were fuzzed over
so as not to aid potential cryptanalysts.

As for the meme, look at my cipher Quadibloc III, on

http://home.ecn.ab.ca/~jsavard/crypto/co040706.htm

where I use one half of a 128-bit block to specify the algorithm to
apply to the other half of the block! But I don't try to generate any
_arbitrary_ algorithm; I merely apply rounds of five well-known block
ciphers to the other half of the block in any of the 120 possible
orders.

Causing every block to be enciphered in a way that is algorithmically
different from that applied to nearly every other block has to
complicate analysis.

John Savard
http://home.ecn.ab.ca/~jsavard/index.html

Originator: daw@mozart.cs.berkeley.edu (David Wagner)

Subject: Re: Multiciphering and Random Cipher Selection in Shannon
Date: Fri, 22 Jun 2001 18:47:03 +0000 (UTC)
From: daw@mozart.cs.berkeley.edu (David Wagner)
Message-ID: <9h03r7\$2qms\$1@agate.berkeley.edu>
References: <slrn9j71uo.clo.mdw@daryl.nsict.org>
Newsgroups: sci.crypt
Lines: 14

Agreed.  It is easy to see that uncomputability doesn't have much to do
with computationally-secure encryption.  After all, in most systems (I
exclude one-time pads here), if one can somehow guess the correct key,
this lucky guess can be verified to be correct.  This has to be true,
since the legitimate receiver has to be able to decrypt knowing only the
key and the ciphertext.  As a consequence, the cryptanalysis problem for
computationally-secure systems is always in NP (or something like it; I'm
being imprecise here, but this idea can be made precise).  In particular,
cryptanalysis is a computable/decidable problem.

The notion of a key-dependent algorithm has been explored many times
before, and has yet to produce good results.  It is, in my personal
opinion, not a very useful way of thinking about cryptographic design
problems.

Subject: Re: Multiciphering and Random Cipher Selection in Shannon
Date: 22 Jun 2001 20:17:59 GMT
From: david_a_scott@emailv.com (SCOTT19U.ZIP_GUY)
Message-ID: <90C89F380H110W296LC45WIN3030R@207.36.190.226>
References: <9h03r7\$2qms\$1@agate.berkeley.edu>
Newsgroups: sci.crypt
Lines: 35

daw@mozart.cs.berkeley.edu (David Wagner) wrote in
<9h03r7\$2qms\$1@agate.berkeley.edu>:

>Agreed.  It is easy to see that uncomputability doesn't have much to do
>with computationally-secure encryption.  After all, in most systems (I
>exclude one-time pads here), if one can somehow guess the correct key,
>this lucky guess can be verified to be correct.  This has to be true,
>since the legitimate receiver has to be able to decrypt knowing only the
>key and the ciphertext.  As a consequence, the cryptanalysis problem for
>computationally-secure systems is always in NP (or something like it; I'm
>being imprecise here, but this idea can be made precise).  In particular,
>cryptanalysis is a computable/decidable problem.
>

Well the only reason that in the modern ciphers you work with
that a correct key from a lucky guess can be verifed as true is
due to the poor design of modern ciphers. BICOM shows how any guess
leads to a result that might have been the file that was encrypted.
No need to purposely weaken systems to make verifcation a trival

David A. Scott
--
SCOTT19U.ZIP NOW AVAILABLE WORLD WIDE "OLD VERSIOM"
http://www.jim.com/jamesd/Kong/scott19u.zip
My website http://members.nbci.com/ecil/index.htm
MY Compression Page http://members.nbci.com/ecil/compress.htm
**TO EMAIL ME drop the roman "five" **
Disclaimer:I am in no way responsible for any of the statements
made in the above text. For all I know I might be drugged.
As a famous person once said "any cryptograhic
system is only as strong as its weakest link"

Subject: Re: Multiciphering and Random Cipher Selection in Shannon
Date: Wed, 27 Jun 2001 15:37:00 GMT
From: bo.doemstedt@mbox200.swipnet.se (Bo Dömstedt)
Message-ID: <3b39fcf2.88463821@nntpserver.swip.net>
References: <slrn9j71uo.clo.mdw@daryl.nsict.org>
Newsgroups: sci.crypt
Lines: 99

mdw@nsict.org (Mark Wooding) wrote:
> Your proof of Theorem 1 in `The Theory of Dynamic Encryption, a New
> Approach to Cryptography' is, of course, entirely wrong.
The proof is by Jesper Jansson, Dep. Computer Science,
Lund University.

> Firstly, note that the set of inputs to a halting Turing machine is
> countable, and hence may be enumerated (and computably so, since the
> inputs are strings over a finite alphabet).  We introduce the bijection
> B: N -> T^* from natural numbers to input tapes.
>
> Now consider the following process:
>
>   Set i <- 0
>   Repeat:
>     Construct the input M <- B(i)
>     Compute C <- F_1(M) and C' <- F_2(M)
>     If C = C' then output `different: M, C, C'' and halt
You really mean C != C'; C different from C' ??
>
> If F_1 and F_2 are indeed different, the above process will halt in
> finite time.  (If they're not, then it won't, but that wasn't the
> problem set: I had to separate them, not decide whether they were
> equal.)

Your algorithm run F_1 and F_2 consecutively on all inputs,
and test if F_1 is different from F_2. But we know that F1 _is_
different from F_2. The trouble is to decide if a given finite output
list [{M0,C0},{M1,C2},...,{Mn,Cn}] is the output from F_1 or F_2
(or some other function).

The real point is that there may be _any_ algorithm running --
how about a machine F_3(M) = {length(M); except when
M=M0 or M=M1 when F_3(M) =0}. If you actually detect M=M0, how
would you know if there might be an M1>M0?

Thank you for your note, this comment will be considered
when we update the report.

> It all gets rather bathetic[1] later.  The `paper' proposes that the
> plaintext and key, together, be considered as the input to a UTM whose
> input language is such that any binary string is valid.
Yes, valid.

> The output of the UTM is then used as a key stream, and combined with the
> plaintext using some simple bijective combiner.
Yes, a bijective cipher function, or (small) cipher algorithm.

> No mention is made of the possibility of the UTM halting before emitting
> enough output, emitting trivial output, or never halting or emitting any
> output at all.
Then the input is not "valid". As mentioned, this is fixed in the UTM.
The question of "trivial" output is more difficult, leading onto
description and interpretation problems of languages,
but kindly observe that "short" inputs cannot be used.

> I think the best bit of all, though, is that the legitimate recipient
> appears to be in the same boat as the cryptanalyst.  Since the key and
> plaintext are required to recreate the key stream, and the recipient has
> the key but not the plaintext, he's in a bit of a pickle, really.

John Savard also had questions on this:

1) The input message (and key/internal structures) may
not be too small. Then brute-force attacks may be possible.
2) Divide the input message in many small segments of 8-32 bits,
depending on implementation preferences.
3) Compute an internal key, using a HCIA system, until a "stop"
condition occurs.
4) Encrypt the block, using the bijective combiner.
5) Feedback both the plaintext and ciphertext to the HCIA software.
6) Restart at (3) until all blocks are encrypted.

When decrypting the HCIA system is run in the forward direction,
and the "bijective combiner" is run in decryption mode. The HCIA
system is given identical feedback in both cases.

To make every output bit a function of all input bits, restart the
system using a new (different) key, and run the process backwards
using previous "ciphertext" as plaintext input. This may be iterated,
if you want.

Note that decryption/encryption are always computable (efficient)
operations. Finding the key by brute force is theoretically
computable (finite), but not in practice, so the cryptanalyst has
to search for a solution elsewhere.

In practice will the memory of the HCIA machine be limited,
so the internal memory state space is limited. This leads to another
brute-force attack, that is much harder than attacking the key.

All other "intelligent" attacks must use the theoretical Turing
machine concept, and these attacks are uncomputable.

Bo Dömstedt
Chief Cryptographer
Protego Information AB
http://www.protego.se/encrypt.htm

```

Terry Ritter, his current address, and his top page.

Last updated: 2001-07-07