This program is a one-way hashing algorithm that can be used for hashing passwords or verifying a file's integrity. Like other ciphers, it has rounds. While this particular implementation was designed to overwrite some of the information required to reverse the rounds operations to be asymmetric, the same core 'substitution' algorithm could be used to make a symmetric stream cipher by taking a different approach.
Each round proceeds as follows: First a scrambling or mangling (sounds violent) of a substitution table is performed before substituting the plain-text (or last round's output) with values from the table chosen by the index corresponding to the plain-text character's equivalent byte value. The substituted-text is then converted into a List of bits (bool) and the list then split in half into two lists of bits. One of the lists of bits is optionally flipped (reversed) based on the value of the first bit of that list. The value of the middle bit of the other list is used to determine which list is to lead during the (next step) bit shuffling. Starting with the selected list, the bits of the two lists are interleaved (shuffled) making one list again. The bits are converted back into bytes via an extension method and used as the input for the next round.
The substitution/cipher block step uses a variation of the RC4 cipher with the key-scheduling algorithm dropped in favor of a pseudo-random-appearing, but evenly distributed table with each number from 0 to 256 appearing exactly once. This table is deterministically populated by an initial value, IV, which is some number that is both greater than 256 and co-prime to it. Starting with zero, set each byte in the table to the value plus IV, modulus 256, in order. Then, to 'prime' the table/block, iterate over the table several thousand times with the RC4 algorithm, discarding the byte stream (in the case of RC4). In the case of my particular RC4 variant implementation, the result byte is put into the table at an index that congruent to 256 modulus the current iteration count multiplied by some co-prime of 256, in this case, 331.
While many people believe that RC4 is well on its way to being broken, it is my hope that by using a smarter key-scheduling function with a different (larger) block size and maybe some bit country line-dancing (shuffling) will make a variant of RC4 that we all can have confidence in again. Hmm, there is already an RC5 and RC6. Maybe a good name would be RC4.1 or RC4.Awesome. RC4 and seven thirteenths? R2C2 perhaps? No, I got it: The stream cipher formally known as RC4. RC4Realz or RCL33t? Anyways, this article is not about symmetric algorithms, but rather asymmetric ones, so read on...
Cryptography is one of my interests. I love the math behind it and I think the mechanics behind RSA are just so elegant. I often daydream that one day I will be able to come out with something incredibly clever and useful. For the past several months, I have been working on implementing several different concepts of cryptography in C#. I have wrote several classes that do one specific type of job, such as transposition, permutation or substitution. I have been toying with combinations these different methods into 'rounds', with each round getting its input from the output of the previous round. In this post, I am proposing a one-way hashing algorithm that uses a combination of bit-shuffling (permutation) and a substitution table with logic that mangle the table based on the current state of the table. It is possible to make an asymmetric algorithm from this idea, but that is not the aim of this particular tool.
This algorithm still has some areas that need improving. First of all, its rather slow, so hashing large files is not practical. The number of rounds has a large baring on its hash time. A smaller number of rounds is recommended for anything beyond a paragraph. The current default is 18. This is rather arbitrary, as I have not done any testing to find the optimal number of rounds. Anyone who uses less than 4 rounds will start to see some repeating characters, not to mention make their implementation more susceptible to cryptanalysis. Sometimes a lengthy hashing time can be desirable, such as a proof of work concept, or to make it more difficult to brute force. For a password-length input at 1024 rounds, it takes almost a full second.
Another area for improvement is the permutation step; is basically just shuffles the bits by dividing the bit array in half and interleaving the bits (think a deck of cards). While there is some variation in the order, based off the input, a much better bit shuffling would probably be an expansion or compression style of permutation. See
this link to Wikipedia for an visual depiction.
Well that about sums it up, so now on to the code! Take note at how I used extension methods to take care of converting a BitArray and a Byte array into a string, and back again. This makes the code very readable and not take up nearly as many lines by reusing code. The code is pretty heavily commented, so I will just let it explaining itself:
public class AJRHash
{
byte[] table;
// Unsure the optimum setting for rounds.
// No less that 4. 1024 takes around 1 second for password-length hashes.
// Use lower setting for large hashes
static int rounds = 18;
static int minimumLength = 10;
static int tableSize = 256; // Because we are using bytes
// By choosing a co-prime to 256, we ensure we get an evenly distributed table
static int[] coprimesOf256 = { 4489, 2209, 1369 }; // Changing the co-primes will change the hash
public AJRHash()
{
table = new byte[tableSize];
InitializeTable();
}
public string Hash(string Input)
{
// Pad the input to minimum length
if(Input.Length<minimumLength)
{
List<byte> padding = new List<byte>();
// Copy the input first
if(Input.Length>0)
padding.AddRange(Input.GetBytes());
// Make up the diffrence with nulls
int diffrence = minimumLength - Input.Length;
while(diffrence>0)
{
padding.Add(0);
diffrence--;
}
Input = padding.ToArray().GetString();
}
byte[] permutation = Input.GetBytes();
byte[] substitution = new byte[Input.Length+1];
int counter = rounds;
while(counter>0)
{
substitution = Substitution(permutation);
permutation = Permutation_Interleave(substitution);
counter--;
}
return Convert.ToBase64String(permutation);
}
void InitializeTable()
{
int prime = coprimesOf256[0];
byte index = 0;
for (int i = 0; i < tableSize; i++)
{
table[index] = (byte)i;
unchecked // The large prime will just roll over. Essentially just modular arithmetic
{ // By choosing a co-prime to 256, we ensure we get an evenly distributed table
index += (byte)prime;
}
}
// Finish initializing the table by shuffling it
ScrambleTable(prime);
}
void ScrambleTable(int iterations)
{
byte i = 0;
byte j = 0;
byte k = 0;
byte l = 0;
byte iteration = 0;
int counter = iterations;
// Just roll over on overflow
unchecked
{
// Some initial values
j=table[table.Length/2];
i=table[j];
// Use the current state of the table to determine how it is changed
while(counter>0)
{
i++;
l=(byte)(table[i]+1);
j=(byte)(j+l+1);
table[i] = (byte)(j + 3);
table[j] = (byte)(l - 1);
k = (byte)( (table[i] + table[j]));
l = (byte)(k % 255);
table[k] = (byte)(table[k]+1);
k = table[l];
l = table[iteration];
table[(byte)(iteration*331)] = (byte)(k ^ l);
counter--;
iteration++;
}
}
}
byte[] Substitution(byte[] input)
{
// Shuffle the table by an ammount unique to the input
ScrambleTable(input.Length*input[0]);
// Apply input against the substitution table
List<byte> result = new List<byte>();
foreach(byte b in input)
{
result.Add( table[(int)b] );
}
return result.ToArray();
}
// TODO: Add more robust bit shuffling/permutation such as compression or expansion
byte[] Permutation_Interleave(byte[] input)
{
// Convert input into an array of bits
BitArray temp = new BitArray(input);
List<bool> bits = temp.GetList();
// Ensure we have an even number of bits
if(bits.Count%2 != 0)
bits.Add(false);
// Split the input up into two arrays of bits
List<bool[]> split = bits.Split();
// Make sure we have at least two arrays to interleave
if(split.Count<2)
throw new Exception("Input is too short.");
bool[] one = split[0];
bool[] two = split[1];
// Ensure both arrays are the same length
if(one.Length != two.Length)
throw new Exception("Lengths must match.");
// If the first bit of two is 1, reverse it.
// This makes the deterministic shuffling more difficult to reverse
if(two[0])
Array.Reverse(two);
// If the 'middle' bit of one is 1, take from two first.
// This makes the deterministic shuffling more difficult to reverse
bool SecondFirst = false;
if(one[one.Length/2])
SecondFirst = true;
// Interleave the two arrays
int counter = 0;
List<bool> result = new List<bool>();
while(counter<one.Length)
{
// Two possible ways to order (decided above)
if(SecondFirst)
{
result.Add(two[counter]);
result.Add(one[counter]);
}
else
{
result.Add(one[counter]);
result.Add(two[counter]);
}
counter++;
}
return new BitArray(result.ToArray()).GetBytes();
}
}
I also wrote a few extension methods to help with all the tedious converting of data types. Extension methods can help keep you code tidy, readable. Don't forget to add these extension methods, or the above code wont compile:
public static class ExtentionMethods
{
public static byte[] GetBytes(this string Input)
{
if(Input == null) return new byte[0];
return Encoding.UTF8.GetBytes(Input);
}
public static string GetString(this byte[] Input)
{
if(Input == null) return string.Empty;
return Encoding.UTF8.GetString(Input);
}
public static string GetString(this BitArray Input)
{
if(Input == null) return string.Empty;
return Encoding.UTF8.GetString(Input.GetBytes());
}
public static byte[] GetBytes(this BitArray Input)
{
if(Input == null) return new byte[0];
int lengthInBytes = (Input.Length%8==0) ? Input.Length/8 : (Input.Length/8)+1;
byte[] result = new byte[lengthInBytes];
Input.CopyTo(result,0);
return result;
}
public static bool[] GetArray(this BitArray Input)
{
if(Input == null) return new bool[0];
return Input.GetList().ToArray();
}
public static List<bool> GetList(this BitArray Input)
{
if(Input == null) return new List<bool>();
List<bool> result = new List<bool>();
foreach(bool b in Input)
{
result.Add(b);
}
return result;
}
public static List<bool[]> Split(this List<bool> Input)
{
if(Input == null) return new List<bool[]>();
int midpoint = (Input.Count/2);
List<bool> result1 = new List<bool>();
List<bool> result2 = new List<bool>();
int counter = 0;
foreach(bool b in Input)
{
if(counter<midpoint)
{
result1.Add(b);
}
else
{
result2.Add(b);
}
counter++;
}
List<bool[]> result = new List<bool[]>();
result.Add(result1.ToArray());
result.Add(result2.ToArray());
return result;
}
}