How to decrypt or even substitute DES-encrypted messages in \(2^{28}\) steps. (Q1853119)

In this paper we analyze the complexity of recovering cryptographic keys when messages are encrypted under various keys. We suggest key-collision attacks, which show that the theoretic strength of a block cipher (in ECB mode) cannot exceed the square root of the size of the key space. As a result, in some circumstances, some keys can be recovered while they are still in use, and these keys can then be used to substitute messages by messages more favorable to the attacker (e.g., transfer 1000000 to bank account 123-4567890). Taking DES as our example, we show that one key of DES can be recovered with complexity \(2^{28},\) and one 168-bit key of (three-key) triple-DES can be recovered with complexity \(2^{84}.\) We also discuss the theoretic strength of chaining modes of operation, and show that in some cases they may be vulnerable to such attacks.