Setting Parity on DES Keys

DES keys are 8 bytes, of which only 7 bits of each byte are used for the key. The least significant bit is used for parity and is thrown away for the actual encryption/decryption (resulting in a 56-bit key for single DES). Mostly, it seems, the parity is ignored by DES implementations, but occasionally a system using DES will check the parity and reject the key if the parity is not odd (or so Google tells me, I've never actually seen this happen). The parity bit was intended to prevent corruption or tampering with the key.

The DES parity calculation works as follows:

00001001 = 9

• for each byte, count the number of bits that are set. For the example byte above, 2 bits are set
  
• if the number of bits set is odd, do nothing
  
• if the number of bits is even, set or unset the least significant bit to make the count odd
  

In the example, the new value for the byte would be

00001000 = 8

Reading through Erlang's crypto support for DES and DES3, it's up to the caller to use a valid key. For example, the NIF making up crypto:des_cbc_crypt/3 is defined as:

DES_set_key((const_DES_cblock*)key.data, &schedule);
DES_ncbc_encrypt(text.data, enif_make_new_binary(env, text.size, &ret),
    text.size, &schedule, &ivec_clone, (argv[3] == atom_true));

DES_set_key() is an OpenSSL compatibility function that, in this case, is identical to DES_set_key_unchecked(). The corresponding checking function, DES_set_key_checked(), returns some information about the key: -1 (if the parity is even) and -2 (if the key is weak).

So I was curious how to go about setting the parity in a functional language. It turns out to be quite easy:

-module(des_key).
-export([set_parity/1, check_parity/1, odd_parity/1]).

set_parity(Key) ->
    << <<(check_parity(N))>> || <<N>> <= Key >>.

check_parity(N) ->
    case odd_parity(N) of
        true -> N;
        false -> N bxor 1
    end.

odd_parity(N) ->
    Set = length([ 1 || <<1:1>> <= <<N>> ]),
    Set rem 2 == 1.

set_parity/1 uses a binary comprehension to read 1 byte at a time from the 8 byte key.

check_parity/1 checks whether an integer has an odd or even parity and returns the integer XOR'ed with 1 if the parity is even.

odd_parity/1 counts the bit set by using a bit comprehension to return the list of bits that are set. The modulus of the length of this list returns oddness/evenness.

To test if this is correct, we can check if a few cases (all even bits or all odd bits in a key) work and then test that a key with corrected parity produces the same cipher text as the uncorrected key:

test() ->
    <<1,1,1,1,1,1,1,1>> = set_parity(<<0:(8*8)>>),
    <<1,1,1,1,1,1,1,1>> = set_parity(<<1,1,1,1,1,1,1,1>>),
    K1 = <<"Pa5Sw0rd">>,
    K2 = set_parity(K1),
    Enc = crypto:des_cbc_encrypt(K1, <<0:64>>, "12345678"),
    Enc = crypto:des_cbc_encrypt(K2, <<0:64>>, "12345678"),
    <<"12345678">> = crypto:des_cbc_decrypt(K2, <<0:64>>, Enc),
    ok.

,