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).

[chan] Crypto-Anarchist Federation

Subject Last Count
1 Sep 19 13:20 2
111 Sep 18 22:09 1
eita Sep 14 20:36 1
ankw Sep 14 20:36 1
ltd Sep 14 20:36 1
ycy Sep 14 20:36 1
bzgk Sep 14 20:25 1
imy Sep 14 20:25 1
pmrc Sep 14 20:14 1
vgz Sep 14 20:11 1
npjyr Sep 14 20:08 1
puij Sep 14 20:05 1
yml Sep 14 20:03 1
vcw Sep 14 20:02 1
kbkz Sep 14 19:58 1
byfx Sep 14 19:58 1
vdqqy Sep 14 19:57 1
ngcj Sep 14 19:56 1
ficeu Sep 14 19:54 1
gduv Sep 14 19:46 1
yczg Sep 14 19:46 1
jiy Sep 14 19:45 1
xun Sep 14 19:44 1
zft Sep 14 19:44 1
eto Sep 14 19:44 1
mqtjx Sep 14 19:44 1
uow Sep 14 19:43 1
odo Sep 14 19:43 1
bjzd Sep 14 19:41 1
pczer Sep 14 19:23 1
dob Sep 14 19:23 1
dni Sep 14 19:23 1
xldp Sep 14 19:23 1
ukzj Sep 14 19:20 1
yhx Sep 14 19:15 1
egjo Sep 14 19:12 1
zxg Sep 14 19:07 1
gihxd Sep 14 19:07 1
rqow Sep 14 19:07 1
sgaj Sep 14 19:07 1
mvttv Sep 14 19:06 1
lakyj Sep 14 19:04 1
jxns Sep 14 19:03 1
sbxp Sep 14 19:00 1
sgqic Sep 14 18:59 1
cxr Sep 14 18:58 1
cur Sep 14 18:56 1
malxq Sep 14 18:56 1
hhjf Sep 14 18:56 1
gyei Sep 14 18:50 1
dhfiw Sep 14 18:48 1
qkz Sep 14 18:32 1
zqzc Sep 14 18:31 1
aanp Sep 14 18:29 1
llezn Sep 14 18:25 1
ybqir Sep 14 18:10 1
orl Sep 14 18:10 1
tfbhw Sep 14 18:00 1
wha Sep 14 17:48 1
ovv Sep 14 17:48 1
rch Sep 14 17:44 1
rdxp Sep 14 17:44 1
zom Sep 14 17:40 1
vmdk Sep 14 17:37 1
pxvwp Sep 14 17:34 1
kkrdt Sep 14 17:31 1
ukbw Sep 14 17:30 1
gzsh Sep 14 17:29 1
yilmg Sep 14 17:19 1
rtpqj Sep 14 17:17 1
egxt Sep 14 17:12 1
shymw Sep 14 17:12 1
lgn Sep 14 17:08 1
jom Sep 14 17:08 1
cga Sep 14 17:08 1
rmlc Sep 14 17:08 1
rcc Sep 14 17:08 1
qht Sep 14 17:06 1
ukqep Sep 14 16:47 1
puxwg Sep 14 16:47 1
shin Sep 14 16:47 1
uftg Sep 14 16:47 1
gfp Sep 14 16:46 1
xjz Sep 14 16:39 1
afnp Sep 14 16:38 1
jokre Sep 14 16:36 1
acsyd Sep 14 16:30 1
qpx Sep 14 16:29 1
zkqnl Sep 14 16:29 1
zwlf Sep 14 16:29 1
eiu Sep 14 16:25 1
rgvs Sep 14 16:19 1
qkcs Sep 14 16:19 1
ewoe Sep 14 16:13 1
aylru Sep 14 16:11 1
ljacu Sep 14 16:06 1
dmub Sep 14 16:06 1
vithq Sep 14 16:06 1
zfcv Sep 14 16:01 1
glwvv Sep 14 16:00 1