On Mon, Mar 10, 2003 at 01:53:29PM -0500, Jack Lloyd wrote: > On 8 Mar 2003, Kryptik Logik wrote: > > > 1. In DES algorithm, given an encrypted text and the corresponding plain > > text for that is it possible to retrieve the key. Essentially, how secure > > is DES to known-plain text attack. > > 1 plaintext + 1 matching ciphertext + 2^55 work -> key If all you have to go on is a single plaintext-ciphertext pair, then in the worst case, this is correct. DES uses a 56-bit key, but there is a symmetry between keys which allows you to only test every second key. In the average case, you will need to perform about 2^54 trial decryptions before you will find the real key. > > I read some where that it is quite resistant requiring 2^55 plain texts > > to get the key but why is this so? What particular feature of the > > algorithm makes it this way? > > I think you're thinking of linear or differential cryptanalysis here. These > are attacks which make use of a lot of data to analyze patterns in the > text. They are not particularly practical, as 2^55 blocks = 256 petabytes. > I think it's highly unlikely that you'll be encrypting that much data with > DES anytime soon. Differential cryptanalysis is bad, but not that bad (If you're storing 2^55 blocks, then you may as well be doing exhaustive search). The best differential attack requires having 2^47 known plaintext/ciphertext pairs (2^47 * 2 * 64 bits = 2^51 bytes = 2 petabytes) and takes roughly 2^47 operations to compute. DES is quite resistant to differential attacks, thanks largely to the specific structure of its S-boxes. It is believed (proven?) that the NSA designed, or at least tweaked, the S-boxes long before the academic world discovered this attack. There is also a linear attack which requires (I believe) only 2^43 known pairs (256 terabytes of storage) and 2^43 operations to compute; but DES was never designed to be particularly resiliant against linear cryptanalysis. > In any case, I don't think secprog@ is the right place for questions like > this. Try cryptographyat_private, the general sanity level is much > higher there than in cypherpunks or sci.crypt. Agreed. Ian Clelland <ianat_private>
This archive was generated by hypermail 2b30 : Mon Mar 10 2003 - 15:03:35 PST