[Cryptography] Impossible trapdoor systems (was Re: Opening Discussion: Speculation on "BULLRUN")

[Jerry Leichter]

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