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.
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 values as we normally think about combiners today. Instead, the 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 intent here is *not* to add keyspace, since reasonable ciphers already 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 advantages: 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 >values as we normally think about combiners today. Instead, the >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 crypto code http://radiusnet.net/crypto/archive/scott/ 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 >>values as we normally think about combiners today. Instead, the >>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 crypto code http://radiusnet.net/crypto/archive/scott/ >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 crypto code http://radiusnet.net/crypto/archive/scott/ 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. Instead of cascading within a block (much like 3DES) 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 task. 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 crypto code http://radiusnet.net/crypto/archive/scott/ 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