general.hpp File Reference

Plans for the Data Encryption Standard crypto-system in Maxima/Lisp. More...

Go to the source code of this file.

Detailed Description

Plans for the Data Encryption Standard crypto-system in Maxima/Lisp.

Improve key schedule tests
  • We should look for tests vectors for the DES key schedule.
  • These test vectors should then be added to the tests.
  • The test vectors should provide good test coverage.
  • Before we can properly test the function, we need a specification (see "Specification").
  • We need full specifications for the following functions:
    • des_round_keys.
    • des_encryption.
    • des_decryption.
    • des_template.
Add variants with reduced number of rounds
  • In the literature, such as [Logical cryptanalysis as a SAT problem; Massaci and Marraro], variants of DES with smaller numbers of rounds are considered.
  • Do variants of the DES with smaller numbers of rounds flip the two 32-bit outputs?
    • It makes sense to do so. Then applying the cipher with the reversed round key list gives the decryption algorithm. This is the same as with 16-round DES.
  • To be able to properly test this, we need test vectors for smaller variants; see "Find more test vectors".
  • All functions which can have a variant with a reduced number of rounds should have one. For example, des_encryption_hex should have des_encryption_reduced_hex.
  • DONE We should have a clear simple function for the full DES. Therefore, it is best to have a different function for the smaller variants. For instance "des_encryption_reduced".
  • DONE With the current system, this is as simple as:
    des_encryption_reduced(plaintext, key, r) :=
     des_template(plaintext, take_elements(r,des_round_keys(key)))$
  • DONE We should offer generalised versions of the current functions.
  • DONE These generalised functions should take the number r of rounds.
  • DONE The functions should then compute the DES encryption with r rounds on the other inputs.
Find more test vectors
  • We need test vectors for variants of DES with smaller numbers of rounds.
  • Full 16 round DES swaps the two 32-bit outputs. Do DES variants with less rounds do this?
  • Authorative test vectors should answer this question.
  • [NIST Special Publication 800-17; NIST] provides test vectors for the full DES, and a small set of vectors for DES "round outputs".
  • In this case "round outputs" means the output of each round in the *16-round* DES computation. That is, these are not (directly) test vectors for generalised m-round DES.
  • These test vectors should be moved into the library.
  • Test vectors are also needed for the generalised m-round DES.
  • The tests should then be extended.
Notion of DES round
  • We consider the DES round function where:
    • It takes two 32-bit inputs (previous and current) and a 48-bit round key.
    • The first 32-bit input, "previous", is the output of the round two rounds ago.
    • The second 32-bit input, "current", is the output of the previous round.
    • For the first round, previous is the first 32-bits and current is the second 32-bits of the 64-bit DES input.
  • The round function does the following:
    • Applies an "expansion map" to current. This rearranges and repeats some bits to make 48-bits.
    • Adds the result of the expansion to the 48-bit key.
    • Applies DES Sbox i, for i in {1,...,6}, to the i-th 6-bit block in the result. This yields 32-bits, as the Sboxes are 6-to-4 bit functions.
    • Applies a "permutation box", i.e., a rewiring of bits, to the 32-bit result of the Sbox operations.
    • Adds previous to the result of the "permutation box".
  • Can the DES encryption scheme be fit into the notion of an iterated block cipher (see ComputerAlgebra/Cryptology/Lisp/CryptoSystems/IteratedBlockCipher.mac)?
  • Can the DES key addition be moved to the beginning of the round? This would then fit with our description of AES.
  • We should provide functions and tests for the Triple-DES encryption scheme.
  • Triple-DES is also called "3DES".
  • Triple-DES is defined in http://csrc.nist.gov/publications/nistpubs/800-67/SP800-67.pdf .
  • Triple-DES was apparently first defined in ANS X9.52-1998. Is this available somewhere?
  • Triple-DES is defined as:
    triple_des_hex(P,K1,K2,K3) := des_encryption_hex(des_decryption_hex(des_encryption_hex(P,K1),K2),K3);
    where K1, K2 and K3 are 64-bit keys with 56-bit of actual key data and 8 parity bits.
  • K1, K2 and K3 can be used in 3 ways, as defined by the Triple-DES standard:
    1. All keys are independent (164 independent key-bits).
    2. K1 and K2 are independent but K1=K3 (112 independent key-bits).
    3. K1 = K2 = K3 (56 independent key-bits; this is exactly DES).
  • Do we consider 3 different keys, or take a single key which we then split into the 3 keys?
    • Taking a single key fits more with our notion of a cipher, as something that takes a plaintext and key and outputs a ciphertextt.
    • Taking 3 keys fits more naturally with the definition of Triple-DES and ensures we always know which key is which.
  • Test vectors are available at http://csrc.nist.gov/groups/STM/cavp/index.html in http://csrc.nist.gov/publications/nistpubs/800-20/800-20.pdf .
  • Triple-DES is used in the various payment card systems world-wide. See http://www.eftpos.co.nz/cms_display.php?sn=55&st=1&pg=4261 .
  • 112-bit Triple-DES should be compared to 128-bit AES.

Definition in file general.hpp.