Binaries, Bitstrings & DUKPT in Elixir

October 6, 2023

In my journey of learning Elixir, I've decided that there has not been enough pain. To explain, moving from an OO language to an FP one has had its challenges. I have spent quite a bit of time working on a problem from Exercism, and feeling quite satisfied with my solution, only to find that someone else in the community had solved that same problem in a much, much simpler manner. That kind of pain I think is normal when learning a new language. Those are mere inconveniences.

I decided that for a more advanced exercise before diving into the world of full-blown web development was to work on a DUKPT algorithm.

“DUKPUT? Never heard of it.”

DUKPT (Derived Unique Key Per Transaction) is a key derivation algorithm that credit/debit card readers use to ensure that each transaction uses a new encryption key. In the past few years DUKPT has adopted AES and simplified its algorithm. I would have none of that. For this exercise I went with old-school 3DES derivation.

The TLDR of DUKPT

Using a Base Derivation Key (BDK) and Key Serial Number (KSN, a 80 bit register split into 3 parts, the BDKID, the DerivationID, and the Transaction Counter), the BDK does some mangling to the BDKID and DerivationID portions of the KSN to derive a unique device key called an Initial Key (IK), which is then securely injected into the pin-pad device. Each time the device needs to encrypt a pin/account number package (pinblock) the device will increment the transaction counter and use the IK to mangle and encrypt the DerivationID and Transaction Counter portions of the KSN to generate the unique key. The back end can verify the legitimacy of the pinblock by using the BDK and the entire KSN to derive the current key and decrypt the pinblock. Got it? Good. The DUKPT standard is defined in ANSI x29.4, I can't tell you what is in it exactly, I can only summarize.

The tricky parts

Each binary 1 in the Transaction Counter is another round of mangling/encryption.
The Transaction Counter is 21 bits long... That's right. Not an easy to use 24, but 21.
The mangling is a lot of XOR and AND operations, meaning that there is a lot of conversion from bytes to integers and back to deal with.

Things that I thought would be easy, but were not

As it turns out binaries and bitstrings in Elixir are not enumerable like lists. Convenience functions like Enum.map and Enum.reduce are worthless here.
Encryption in Elixir, as far as I can tell, is not something that happens often. Doing plain-ole 3DES encryption means dropping into Erlang.
Erlang only uses single DES for ECB modes.

OK, What's tricky about binaries in Elixir?

Working with binaries and bitstrings means that while they are effectively the same thing, you cannot mix the two in most cases. Binary measurements are for binary strings and bit measurements are for bitstrings, except for when the measurement of bitstrings land on 8-bit boundaries.

When dealing with either bitstring or binary string, size specifications are made at the head of the string, not at the tail. If you need to pull from the tail, you will need to calculate how much head to discard and then float the tail.

When dealing with either, the default measurement is in bits. For instance take the following data:

iex> data = Base.decode16!("DEADBEEFFEEDBEEF")
<<222, 173, 190, 239, 254, 237, 190, 239>>

To pull a 4-bit nibble, you cannot do the following:

iex> <<head::4, tail::binary>> = data

But you can do this:

iex> <<head:4, tail::bits>> = data

or this:

iex> <<head::size(4), tail::bits>> = data

To pull a single byte one would do this:

iex> <<head::8, tail::binary>> = data

or this:

iex> <<head::binary-size(1), tail::binary>> = data

or this:

<<head::binary-size(1), tail::bits>> = data

Also note that specifying size and reading size do not invoke the same functions.

iex> bit_size(data)
64
iex> <<head::size(5), tail::bits>> = data
<<222, 173, 190, 239, 254, 237, 190, 239>>

iex> byte_size(data)
8
iex> <<head::binary-size(1), tail::binary>> = data
<<222, 173, 190, 239, 254, 237, 190, 239>>

And finally, when using a variable for a size measurement, the variable must be passed to a sizing function; it cannot be used directly

This will not work:

iex> my_len = 8
8
iex> <<head::my_len, tail::binary>> = data
warning: bitstring specifier "my_len" does not exist and is being expanded to "my_len()", please use parentheses to remove the ambiguity
  iex:15

But, this will:

iex> <<head::size(my_len), tail::binary>> = data
<<222, 173, 190, 239, 254, 237, 190, 239>>

First Things First, Make My Tools

DUKPT uses simple ECB mode of 3DES encryption so it's nothing fancy. However from the Erlang Crypto Docs, as far as I can tell, 3DES ECB isn't implemented and I'll have to resort to 3-rounds of single DES encryption to do the job.

A 3DES key can either be 16 or 24 bytes long and works like this. In the case of a 24byte key in the form of A|B|C encrypt data with bytes A, decrypt with bytes B, encrypt with bytes C. In the case of 16byte keys, encrypt data with bytes A, decrypt with bytes B, encrypt again with bytes A. Seeing that chaining data is a part of the process, Elixir's pipe operator along with pattern matching and multiple function clauses worked wonders for this:

defmodule CryptoTools do

  def des_encrypt(data, <<k1::binary-size(8), k2::binary-size(8), k3::binary-size(8)>>) do
    data
    |> des_encrypt(k1)
    |> des_decrypt(k2)
    |> des_encrypt(k3)
  end

  def des_encrypt(data, <<k1::binary-size(8), k2::binary-size(8)>>) do
    data
    |> des_encrypt(k1)
    |> des_decrypt(k2)
    |> des_encrypt(k1)
  end

  def des_encrypt(data, <<k1::binary-size(8)>>) do
    :crypto.crypto_one_time(:des_ecb, k1, data, encrypt: true)
  end


  def des_decrypt(data, <<k1::binary-size(8), k2::binary-size(8), k3::binary-size(8)>>) do
    data
    |> des_decrypt(k3)
    |> des_encrypt(k2)
    |> des_decrypt(k1)
  end

  def des_decrypt(data, <<k1::binary-size(8), k2::binary-size(8)>>) do
    data
    |> des_decrypt(k1)
    |> des_encrypt(k2)
    |> des_decrypt(k1)
  end

  def des_decrypt(data, key) do
    :crypto.crypto_one_time(:des_ecb, key, data, encrypt: false)
  end
end

From there I needed to work on a way to do my bitwise operations on bytes. Here function capturing worked like a charm.

defmodule CryptoTools do

  ...

  defp byte_wise_operation(arg1, arg2, operator, acc \\ <<>>)

  defp byte_wise_operation(<<>>, <<>>, _operator, acc), do: acc

  defp byte_wise_operation(<<arg1::8, r1::binary>>, <<arg2::8, r2::binary>>, operator, acc) do
    byte_wise_operation(r1, r2, operator, acc <> <<operator.(arg1, arg2)>>)
  end


  def and_bytes(a, b),  do: byte_wise_operation(a, b, &Bitwise.band/2)


  def or_bytes(a, b),   do: byte_wise_operation(a, b, &Bitwise.bor/2)


  def xor_bytes(a, b),  do: byte_wise_operation(a, b, &Bitwise.bxor/2)
end

The Different Approach With Functional Programming

Creating the IK is a trivial issue. The bigger challenge is the Current key in regards to the algorithm which deals with the once per binary 1 in the counter operations. In an imperative language this is solved with a shift-register, while-loop and an IF statement: Start the loop and AND the shift-register with the counter to see if we are on a one. If we are then do the necessary operations and then shift right the shift-register by one and repeat the loop, then break out of the loop when the shift-register is zero.

While I could “fake” that loop with a recursive function and still use a shift-register and ANDing on an IF, that would totally break the spirit of using Elixir's pattern matching on bitstrings. Also, there is a fair number of variables that needs to be carried over each recursion. Do I make a recursive function with a ton of arguments? Do keep the number of arguments low and use a struct and increase complexity? Do I keep the number of arguments low and derive what I need via private, convenience functions at runtime?

The third option is what I went with, because in the imperative code some of those variables had dual purposes, while in the functional code they were reduced to single purpose. I guess I could have used a struct/map to pass data between each function call, I just didn't this time.

IK code

defmodule Dukpt.TDes.InitialKey do
  @behaviour Dukpt.TDes.Deriver
  import CryptoTools
  # @variant "C0C0C0C000000000C0C0C0C000000000"
  @variant <<192, 192, 192, 192, 0, 0, 0, 0, 192, 192, 192, 192, 0, 0, 0, 0>>
  @modder <<255, 255, 255, 255, 255, 255, 255, 224, 0, 0>>


  @impl Dukpt.TDes.Deriver
  def derive_key(key_material, ksn) do
    mod_ksn = and_bytes(ksn, @modder)
    modified_bdk = xor_bytes(key_material, @variant)
    {:ok, create_initial_half_key(mod_ksn, key_material) <> create_initial_half_key(mod_ksn, modified_bdk)}
  end


  defp create_initial_half_key(ksn, key) do
    <<device_id::binary-size(8), _::binary>> = ksn
    des_encrypt(device_id, key)
  end
end

Current Key Code

defmodule Dukpt.TDes.CurrentKey do
  @behaviour Dukpt.TDes.Deriver
  import CryptoTools
  # @variant "C0C0C0C000000000C0C0C0C000000000"
  @variant <<192, 192, 192, 192, 0, 0, 0, 0, 192, 192, 192, 192, 0, 0, 0, 0>>
  @dev_id_mask <<255, 255, 255, 255, 255, 224, 0, 0>>


  @impl Dukpt.TDes.Deriver
  def derive_key(initial_key, ksn) do
    discard_bytes = byte_size(ksn) - 8
    <<_::binary-size(discard_bytes), ksnr::binary >> = ksn

    dev_id = and_bytes(ksnr, @dev_id_mask)

    discard_bit_size = bit_size(ksnr) - 21
    <<_::size(discard_bit_size), counter::bits>> = ksnr

    derivation_process(counter, initial_key, dev_id)
  end


  defp update_dev_id(dev_id, rest) do
    tail_padding = bit_size(rest)
    head_padding = bit_size(dev_id) - 1 - tail_padding
    or_bytes(<<0::size(head_padding), 1::size(1), 0::size(tail_padding)>>, dev_id)
  end


  defp derivation_process(counter, current_key, dev_id, ones \\ 0)

  defp derivation_process(_, _, _, ones) when ones >= 10, do: {:error, "Too many binary ones in the counter"}

  defp derivation_process(<<>> = _counter, current_key, _dev_id, _ones) do
    {:ok, current_key}
  end

  defp derivation_process(<<0::1, rest::bits>> = _counter, current_key, dev_id, ones) do
    derivation_process(rest, current_key, dev_id, ones)
  end

  defp derivation_process(<<1::1, rest::bits>> = _counter, current_key, dev_id, ones) do
    <<right_first::binary-size(8), right_second::binary-size(8)>> = current_key
    <<left_first::binary-size(8), left_second::binary-size(8)>> = xor_bytes(current_key, @variant)

    dev_id = update_dev_id(dev_id, rest)

    right_half =
      xor_bytes(right_second, dev_id)
      |> des_encrypt(right_first)
      |> xor_bytes(right_second)

    left_half =
      xor_bytes(left_second, dev_id)
      |> des_encrypt(left_first)
      |> xor_bytes(left_second)

    derivation_process(rest, left_half <> right_half, dev_id, ones + 1)
  end
end

In the end the update_dev_id function was the only necessary convenience function needed. In the imperative world the device_id needs to be OR'd with the shift-register on every operation. Since I'm not ANDing with a shift-register for recursion control, I just recreate it when I need it.

Conclusion

When I implemented this code in Python some four years ago, there were also convenience functions that needed to be created for byte-wise operations. This was not as nearly straight forward as they were in Elixir, due to the fact that converting between Bytes and Ints in Python is a bit more esoteric than in Elixir.

While I could have used a shift register for recursion control, I didn't need to. I could instead use the much more ergonomic mechanism of pattern matching. In other languages I would have to remember that “ANDing with 1 keeps the bit while ANDing with 0 turns off the bit.” Previously I had to focus more on the “how” and not the “what,” which is quite liberating.