Variable and machine generated secret ciphers

Jan 4 13:55 [raw]

There is no intrinsic difference between algorithm and data, the same information can be viewed as data in one context and as algorithm in another. Why then do so many people claim that encryption algorithms should be made public and only the key should be kept secret? (This is the famous and derisive mantra about "security through obscurity".) There are several answers: a) Some people, with little understanding about computer technology, try to keep secret what their programs do, even though the programs themselves are public. A program *is* a representation of the algorithm, even though it happens to be more difficult for humans to read than, say, an detailed description in English. Actually it is a very good idea to keep secret the algorithm (in all its representations), as long as you can afford to do so. That is why major governments do exactly that. b) One can memorize a key and keep it secret in one's head. Normally, encryption algorithms are too complicated to be memorized. Therefore it is easier to keep secret a key than an algorithm. c) Most people and organizations do not have sufficient expertise to create a new and good encryption algorithm and then try to keep it secret. A bad encryption algorithm, in this context, is an algorithm that can be broken by a sophisticated attacker even without knowledge about the algorithm itself. As you see, the reasons are of a practical nature, and are not derived from any fundamentals in cryptology. If we could find a practical way to keep secret both the key (that is the data the encryption method operates on) and also the method itself (or at least part of the method), then security would be greatly enhanced because the attacker would have less knowledge to work with. I believe there are several ways to overcome these practical difficulties: a) Machine generated secret ciphers. Today there are only a few encryption algorithms that are generally accepted as good. But suppose there existed a generator program which could construct a new encryption algorithm depending on some random input. Actually, the generator program would produce another program which would then be used as the encryption software. In some important cases, it is feasible to keep secret the resulting program: International organizations could distribute disks containing the program using trusted persons, the program could be loaded in centralized servers which actually operate from within a safe, or maybe the program (in encrypted form) would be run only from a floppy disk which would be handled with the same care as the key to a safe. We all know that absolute security is impossible. What I am suggesting here is that in many cases this system of security is better than one using a standardized and public algorithm which attracts a lot cryptanalytic work and may be broken in the near future or may have already been broken in secret. b) Intrinsically secret ciphers. Extend secrecy to parts of the encryption method. In his book, Schneier very briefly describes a variant of DES where the Sboxes (which most people would consider as part of the algorithm) are variable and depend on the key. Another very interesting possibility would have the key express the encryption method. In other words consider the key as the program, and the cipher simply as an interpreter, that follows the key's instructions to scramble the plaintext or unscramble the ciphertext. This would call for large keys, but not larger than keys used in public key encryption. c) "Variable" ciphers. The idea here is to implement a cipher that incorporates a huge number of different encryption functions. The objective is to overwhelm the analytic capability of an attacker. (At the end of this post you will find the outline of a proof about why a cipher of this type is intrinsically more secure.) Here is the definition of another cipher of this type (let us call it "heavy DES"): Start by randomly defining 16K DES keys; you need less the 1 MB space in your hard disk to save them. Suppose that this large key set is public (either by choice or because an attacker gained access to your computer and stole it). So now you have a large set of DES ciphers with *known* keys; the effort to break any one of them is 1. Now define a secret key of 140 bits. Use 14 bits at a time to index one of the 16K DES functions. Encrypt a 64 bit block by sequentially chaining the 10 indexed DES functions. DES is not a group, therefore each instance of the 140 bits long key results in a different mapping of the plaintext space into the ciphertext space. If we choose from 2^N DES functions and chain P of them together (in the example above N=14 and P=10) then there are 2^(N*P) different instances. Already with 140 bits of entropy, a brute force attack is out of the question no matter how many hardware coded DES machines you have. Suppose you have perfect cryptanalytic knowledge of DES - trapdoor and all - even then, can you see a way to attack this variable version? Finally, let me try to demonstrate why a "variable" cipher is more difficult to break: Take two ciphers A and B with keys of N bits. These ciphers must be independent in the sense that physically breaking one does not help in breaking the other. (By "physical break" I mean the work necessary to recover the key when the cipher is already cryptanalyzed; "logical break" would be the work necessary to successfully cryptanalize a cipher"). Let us suppose that these ciphers are not perfect; and therefore there exists a method (known or unknown) to physically break them that is more efficient then brute force, i.e. the trying of all possible keys. (Observe that no publicly known cipher with a key that is used repeatedly has been proved to be perfect in this sense.) For ciphers A and B there exists then a method to break them with as few as 2^(N*k) operations where k<1 (2^N corresponds to brute forcing them). If you increase the key length by 1 bit, then you would need 2^((N+1)*k)=2^N * 2^k operations to break A or B. But if you create a new cipher C with a key of N+1 bits where the last bit is used to choose either A or B as the working cipher with a key of N bits, then you must break A, and with 50% probability B also, with an effort comparable to 2^(N*k)+0.5*2^(N*k)=3/2 * 2^(N*k). Therefore you need more effort to break C with a key of N+1 bits, than either A or B with a key of N+1 bits, as long as k is less then ln(3/2)/ln(2) = 0.58. If instead of two ciphers, you started with 2^M different ciphers, then the results are more dramatic. The effort required for breaking the resulting cipher is now 2^(N*K-1)*(2^M+1) and it will be stronger as long as k < 1/M*(ln(2^M+1)/ln(2) -1) or for large M: k < 1 - 1/M. This works like a security amplifier: if you can construct 1024 independent ciphers then by this method you can produce a cipher that has a 10 bit longer key and is provably 512 times more secure than any one of them (in the sense that an attacker must invest 512 times more effort to break it).