Blobfish

An encryption/decryption protocol inspired from Enigma. It is a symmetric-key algorithm that reuses and generalizes some concepts of the Enigma machines, such as plugboards and rotors. This implementation is written in C++.

Goals

Blobfish's goal is to encrypt and decrypt any kind of file. It doesn't require any specific format or file system, and both encryption and decryption should work exactly the same independently of the environment or file system. The contents of the file are seen as a stream of bytes, or numbers between 0 and 255. This is similar to the Enigma machine where each input and ouput was a value from a given alphabet. The process shouldn't require to load the whole file in memory, as this would limit the file size.

Mathematical interlude

Useful notions here include basic algebra, groups and combinatorics.

Let E be a set of distinct elements, and f : E → E a function with E as both its domain and image. We can use f to encrypt and decrypt values from the set E only if f is a bijection that covers the whole set. Such a function is called a permutation of the set E. That permutation can be represented in different ways but the most intuitive may be using a table containing in one line the domain values and in the next line the corresponding image values:

A	B	C	D
D	B	A	C

Here f transforms A into D, B into itself, C into A and D into C. If we assume the elements from the first line are always ordered, we can ommit storing it into memory in order to be more space-efficient.

Some operations are allowed on permutations. A common one is composition, that combines multiple permutations into a single one, called the composite permutation. Composition is represented with the (round) ∘ operator as follows : assuming that f : E → E and g : E → E are permutations, h = f ∘ g is also a permutation from E to E.

Permutations are bijections, therefore they have inverses. The inverse of f is also a permutation f^-1 : E → E such that for all x in E, f^-1 ∘ f (x) = x. Intuitively, f^-1 can be represented by inverting the top and bottom lines from the previous table:

D	B	A	C
A	B	C	D

The algorithm

There are two algorithms: one for encryption and one for decryption. However, they are symmetrical in every way, and use the exact same concepts and mechanisms, defined hereafter.

Password

The encryption and decryption algorithms use the same password p₀, made out of n = 256 different integers between 0 and n-1. Therefore each value is represented only once, giving us n! = 8.58 e⁵⁰⁶ possible passwords. The proper algorithm is applied to the whole file t times sequentially, each time using a modified version of the password.

Each modified password p_i+1 is generated by adding to each of its values the (i mod n)^th value from p_i, and then computing their modulus n. When encrypting, the sequence of passwords used at each step will be p_{0 .. t-1}. When decrypting, that sequence will be p_{t-1 .. 0}.

Plugboard

The plugboard is a part of the algorithm that uses a permutation to modify given values. This permutation is defined for the set of integers [0, n-1], and is represented by an array of n integers, where the value contained at index i of the array is the image of the value i. This representation allows for efficient computing and storage of the permutation function.

P_i maps each value x to the x^th value of p_i. It is used for encryption, and its representation is exactly the same as the password's. For decryption, the inverse permutation is computed, therefore its representation is adapted for efficiency purposes.

The plugboard can be seen as a monoalphabetic cypher since all identical values will be transformed into the same value.

Rotors

A rotor is a part of the algorithm that uses a permutation C_{i, x} to modify given values. This permutation is defined for the set of integers [0, n-1] and is also represented by the password. However, it works differently:

C_{i, j} maps each value x to the value (x + v) mod n, where v is the (j mod n)^th value of p_i, xored with the ((j // n) mod n)^th value of p_i. For decryption, v is subtracted to x instead, but still uses modulus. The value j is initialized as the distance between the values n-1 and 0 in the password.

The rotor can be seen as a polyalphabetic cypher (or more exactly, a set of n monoalphabetic cyphers used in varying order) since the permutations change for each value.

Pseudocode

Encryption will work as follows

p_i = password

i = 0
while i < t:
  P_i.set(p_i) #set plugboard i with p_i as the permutation
  R_i.set(p_i) #set rotor i with p_i as the permutation
  
  for byte b in file:
    b = P_i(b) #go through plugboard i
    b = R_i(b) #go through rotor i
    b = P_i(b)
   
   i++
   p_i = addithvalue(p_i, i mod n) #modify password

Decryption works backwards, so it has to generate the last password before beginning.

p_i = password
for i in range(t):
  p_i = addithvalue(p_i, i) #modify password

i = t-1
while i >= 0:
  P_i.setReverse(passwords[i]) #set plugboard i with p_i as the reverse permutation
  R_i.setReverse(passwords[i]) #set rotor i with p_i as the reverse permutation
  
  for byte b in file:
    b = P_i(b) #go through plugboard i
    b = R_i(b) #go through rotor i
    b = P_i(b)
   
   i--
   p_i = subithvalue(p_i, i) #modify password

Future development

Here are some thoughts about the future of this project.

Parallel execution (multithreading)

This would allow to multiply performance by the number of threads, which is not superfluous in today's architectures. Parallel execution may even enable us to use graphics cards to encrypt or decrypt files.

In order to achieve this, we could divide files in blocks of n² bytes, each being treated by one thread at a time. The size of n² would allow us to avoid initialization of the rotors : (j+n²) % n = j and ((j+n²) // n) mod n = j. Maximum number of threads could be given as a parameter or determined by a systems library. Furthermore, once the first thread is done computing one block, it can immediately start computing the next available block -even before the next threads are done- or start a new pass for the first block (if the previous pass for the same block is finished). Recycling the threads would allow to gain time since thread creation may not be optimized on the system.

Password generation

By allowing a user to generate the password from a sentence or series of words we could make it manageable to remember the password, and avoir users writing them down or choosing easy to remember -and guess- passwords. Here's an idea for a password generator :

• Compute the n-sized md5 digest of the text
• Replace each repeated value by the next bigger unused value