DES Encryption Algorithm all 64 bits for key instead of 56 bits

Question

Would a DES algorithm that uses all 64 bits for the key instead of just the 56 bits be more secure? I have been thinking about it but those 8 bits used for parity are very useful and but including them in the key could potentially make it more easily cracked.

From Wikipedia, it stated that the 56 bit key was cracked in 4 days due to hardware. Now if we include the 8 parity bits to make it a 64 bit key, would that make the key crackable after 1024 days? My math: 2^8 * 4 = 1024 days. Assume we use the same hardware.

If we included the 8 parity bits, would it have made the security of DES substantially stronger?

Answer 1

Yes, it would be more secure if they were used correctly. But as it would require a substantially different algorithm, you really would not be talking about DES anymore.

Brute forcing usually scales exponentially with the size of the key. However, if the algorithm is substantially altered then it is required to analyze the algorithm again.

Note that AES is both faster and stronger than DES. There is no need to (substantially) alter DES now there are many better algorithms available.

---

(Triple) DES is mainly used for backwards compatibility now. The keysize of DES is too small key size to be of practical use; triple DES has a blocksize that is too small to be used for uses in modern modes of encryption (CTR, GCM etc).

Answer 2

Including Parity bits absolutely does not increase the cryptographic strength of DES (or 2-key TDES, or 3-key TDES). The DES feistel network itself only accepts eight 7-bit blocks as input, no more and no less. You can add as many parity as you want, but that doesn't mean any more bits are being processed by the algorithm.

Parity bits are either used pre-cipher to determine the integrity (against corruption, not attack) of each 7-bit block and truncated before encryption/decryption operations are performed, or ignored altogether. The only reason they were used in the first place was to make an uncommon block size align with a byte-dominated world of computing.

As an example, the following DES keys are all identical cryptographically speaking (all encrypt a fixed plaintext to the same ciphertext on implementations that do not reject keys for malformed parity bits):

AA AA AA AA AA AA AA AA
AA AA AA AA AA AA AA AB
AB AB AB AB AB AB AB AB

Answer 3

DES cannot be substantially strengthened by using a longer key (i.e. > 56 bits) and/or a different key schedule.

The reason lies in the first differential attack paper;

• Biham, E., Shamir, A. Differential cryptanalysis of DES-like cryptosystems. J. Cryptology 4, 3–72 (1991)

In their paper, they also applied the differential attack with round independent subkeys i.e. $8\cdot48 = 384$ keys. In this setup the attack takes $2^{61}$ steps (normal DES has $2^{58}$ differential attack complexity).

This is the reason that we have 2DES,3DES, and DESX-like constructions to use larger keys with DES as a building block.

Keep in mind that DES's small block size is another problem caused by the birthday attack on any block cipher with 64-bit block size.