Unbreakable Encryption with Elixir

Continuing with selected sections of Classic Computer Science Problems in Python (CCSPiP) by David Kopec, we now spend some time in the land of cryptography via the one time pad technique. This post corresponds to Chapter 1 Section 3. The source code presented here is available on GitHub.

One time pads cannot be cracked, but they have the disadvantage of requiring a one time pre-shared key per use. How to securely distribute all those keys makes its use cumbersome. The Wikipedia page is more informative, but the gist of problems goes like this:

• The secret key must be truly random, never repeating, or reused
• The secret key must be at least as long as the original text
• The secret key must be distributed securely in advance
• No authentication is available about the message

All these problems add up to a substantial challenge, but it can still have some interesting uses. So let's share some key secrets about the code.

Got that information on lock

To start off, the random byte generator used here is not truly random... it is simply used out of convenience. Therefore the encrypted message generated below is already at risk. We use a random byte generator rather than other random generators, which will cause the implementation to look different than what you would see on the Wikipedia page. We do this to remain consistent with the CCSPiP approach.

Let's say we have the following critical message we want to encrypt - smack the subscribe button!. To do so, we'd generate a secret key the same length as the original message and then convert both strings into their own bitwise friendly values. We then take the two values and XOR ^^^ (exclusive or) them together. This all works rather seamlessly due to our ability to convert strings to integers based on their byte value. Elixir strings lead covert double lives as UTF-8 encoded binaries.

As seen in the code:

import Bitwise, only: :macros

@spec random_key(non_neg_integer) :: non_neg_integer
defp random_key(length) do
  :crypto.strong_rand_bytes(length)
  |> :crypto.bytes_to_integer()
end

@spec encrypt(String.t()) :: {non_neg_integer, non_neg_integer}
def encrypt(original) do
  dummy_key = random_key(byte_size(original))
  original_key = :crypto.bytes_to_integer(original)
  encrypted_key = original_key ^^^ dummy_key
  {dummy_key, encrypted_key}
end

One potential tuple produced by encrypt("smack the subscribe button!") would be the following, with the first element the secret key or "dummy key" and the second value the actual encrypted message.

{
  98130323561516153040661178747373510909208433307399916182106784190,
  64958506369177747325205147482039019300614211204598760378667413407
}

Of course this tuple could be represented in other ways, such as a binary, but it can't be shown as a valid string since we used random bytes as opposed to random characters.

Time for the reveal

The decryption is dead simple. Given the secret key and the encrypted message, simply XOR ^^^ them and convert the value into a string.

@doc """
The ordering of the keys does not impact the result.
"""
@spec decrypt({non_neg_integer, non_neg_integer}) :: String.t()
def decrypt(keyPair)

def decrypt({key1, key2}) do
  decrypted = key1 ^^^ key2
  :binary.encode_unsigned(decrypted)
end

def decrypt(key1, key2) do
  decrypt({key1, key2})
end

This is made particularly easy with Erlang's :binary.encode_unsigned/1 function. It takes the integer produced by the XOR and produces a binary. As strings are binaries, this makes the conversion painless.

Running the following produces the original message, as desired:

decode({
  98130323561516153040661178747373510909208433307399916182106784190,
  64958506369177747325205147482039019300614211204598760378667413407
})
=> "smack the subscribe button!"

Understandably, you might wonder why this works. I find it easiest to show with some REPL action:

iex(1)> use Bitwise
Bitwise
iex(2)> 71 ^^^ 92
27
iex(3)> 92 ^^^ 71
27
iex(4)> 27 ^^^ 92
71
iex(5)> 27 ^^^ 71
92

Some observations:

• Given two integers, (2)  shows XORing them together produces a unique integer.
• The order does not matter as seen in (3)
• If you XOR the resulting value with either of the original integers, like in (4) and (5), then you produce the other original value.

This is how we are able to produce the original message when decrypting. During encryption, the secret key and original message are XOR'd to produce the encrypted message. When decrypting, we XOR the secret key and encrypted message to produce the original message. That's all there is to it!

Conclusion

This particular exercise went quite smoothly compared to the troubled encountered with compression... likely because I fell into all the possible traps regarding strings and bitwise operations in the last post. It is disappointing that CCSPiP does not cover more cryptography as it is such a fascinating topic, but there is some exciting content to be found in every chapter.

If you find this type of material interesting, you might want to check out cryptopals' crypto challenges. As of this writing they are a work in progress, but the material is promising and provides self-guided tour of crypto via experiential learning. I know I plan to dabble with them to learn more.

Photo by Markus Spiske on Unsplash