Re: [Cryptography] Impossible trapdoor systems (was Re: Opening Discussion: Speculation on BULLRUN)
On 09/08/2013 11:49 AM, Perry E. Metzger wrote: That said, your hypothetical seems much like imagine that you can float by the power of your mind alone. The construction of such a cipher with a single master key that operates just like any other key seems nearly impossible, and that should be obvious. True. A universal key that uses the same decryption operation as a normal key is clearly stupid. I guess the thing I was thinking of is that the attacker knows a method that allows him to decrypt anything if he knows the IV, but cannot recover the key used to encrypt it. Which is of course a public-key system, where the decryption method is the private key and the IV is the public key. The thing I was thinking of as a key functions as a nonce or subkey which allows people unrelated to the private key holder to communicate semi-privately by shared secret, but the private key is a backdoor on their communication. Duh. Sorry, just wasn't thinking of the right parallel mapping of what I described. For the cipher itself to function as a key sort of escaped my attention. Sorry to waste time. Ray. ___ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
Re: [Cryptography] Impossible trapdoor systems (was Re: Opening Discussion: Speculation on BULLRUN)
On Sep 8, 2013, at 8:37 PM, James A. Donald wrote: Your magic key must then take any block of N bits and magically produce the corresponding plaintext when any given ciphertext might correspond to many, many different plaintexts depending on the key Suppose that the mappings from 2^N plaintexts to 2^N ciphertexts are not random, but rather orderly, so that given one element of the map, one can predict all the other elements of the map. Suppose, for example the effect of encryption was to map a 128 bit block to a group, map the key to the group, add the key to the block, and map back Before our current level of understanding of block ciphers, people actually raised - and investigated - the question of whether the DES operations formed a group. (You can do this computationally with reasonable resources. The answer is that it isn't.) I don't think anyone has repeated the particular experiment with the current crop of block ciphers; but then I expect the details of their construction, and the attacks they are already explicitly built to avoid, would rule out the possibility. But I don't know. Stepping back, what you are considering is the possibility that there's a structure in the block cipher such that if you have some internal information, and you have some collection of plaintext/ciphertext pairs with respect to a given key, you can predict other (perhaps all) such pairs. This is just another way of saying there's a ciphertext/known plaintext/chosen plaintext/ chosen ciphertext attack, depending on your assumptions about how that collection of pairs must be created. That it's conveniently expressible as some kind of mathematical structure on the mappings generated by the cipher for a given key is neither here nor there. Such a thing would contradict everything we think we know about block ciphers. Sure, it *could* happen - but I'd put it way, way down the list of possibles. -- Jerry ___ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
[Cryptography] Impossible trapdoor systems (was Re: Opening Discussion: Speculation on BULLRUN)
On Sat, 07 Sep 2013 20:14:10 -0700 Ray Dillinger b...@sonic.net wrote: On 09/06/2013 05:58 PM, Jon Callas wrote: We know as a mathematical theorem that a block cipher with a back door *is* a public-key system. It is a very, very, very valuable thing, and suggests other mathematical secrets about hitherto unknown ways to make fast, secure public key systems. I've seen this assertion several times in this thread, but I cannot help thinking that it depends on what *kind* of backdoor you're talking about, because there are some cases in which as a crypto amateur I simply cannot see how the construction of an asymmetric cipher could be accomplished. As an example of a backdoor that doesn't obviously permit an asymmetric-cipher construction, consider a broken cipher that has 128-bit symmetric keys; but one of these keys (which one depends on an IV in some non-obvious way that's known to the attacker) can be used to decrypt any message regardless of the key used to encrypt it. That key would then be known as the private key. The public key is the set of magic values used in the symmetric cipher (say in the one way functions of the Feistel network if it were a Feistel cipher) such that such a magic decryption key exists. However, it is not a valid encryption key; no matter what you encrypt with it you get the same ciphertext. So? If you have an algorithm that creates such ciphers in such a way that the magic key is hard to find, then you produce all that you want and you have a very powerful primitive for constructing public key systems. You don't have an obvious signature algorithm yet, but I'm sure we can think of one with a touch of cleverness. That said, your hypothetical seems much like imagine that you can float by the power of your mind alone. The construction of such a cipher with a single master key that operates just like any other key seems nearly impossible, and that should be obvious. A symmetric cipher encryption function is necessarily one-to-one and onto from the set of N bit blocks to itself. After all, if two blocks encrypt to the same block, you can't decrypt them, and one block can't encrypt to two blocks. If every key produces the same function from 2^N to 2^N, it will be rapidly obvious, so keys have to produce quite different mappings. Your magic key must then take any block of N bits and magically produce the corresponding plaintext when any given ciphertext might correspond to many, many different plaintexts depending on the key. That's clearly not something you can do. Perry -- Perry E. Metzgerpe...@piermont.com ___ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
Re: [Cryptography] Impossible trapdoor systems (was Re: Opening Discussion: Speculation on BULLRUN)
On 2013-09-09 4:49 AM, Perry E. Metzger wrote: Your magic key must then take any block of N bits and magically produce the corresponding plaintext when any given ciphertext might correspond to many, many different plaintexts depending on the key. That's clearly not something you can do. Suppose that the mappings from 2^N plaintexts to 2^N ciphertexts are not random, but rather orderly, so that given one element of the map, one can predict all the other elements of the map. Suppose, for example the effect of encryption was to map a 128 bit block to a group, map the key to the group, add the key to the block, and map back. To someone who knows the group and the mapping, merely a heavily obfuscated 128 bit Caesar cipher. No magic key. ___ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
