Showing posts with label Cryptography. Show all posts
Showing posts with label Cryptography. Show all posts

Wednesday, September 21, 2016

RC4 stream cipher variants and visualization of table permutation state



Here, I present some work I have been doing on two RC4 stream cipher variants. The first variant, as seen below, I wrote to help me visualize and understand what the RC4 tables was doing, and help me understand its properties.

Identity Permutation

The class that contains it is called SimpleTable and is exactly that; The simplest R4C implementation possible. It is notable in the fact that it does not use key scheduling at all, and its starting state is that of the Identity Permutation. The identity permutation is where the value at index zero equals zero, the value at index one is one, and so on. An easy way to remember what the Identity Permutation is, just recall the notion of a Multiplicative Identity (which is 1), where by multiplying a number N by the Multiplicative Identity gives you back the value of N, also known as the identity. Similarly, the Identity Permutation of an array A just gives you A. This is the trivial permutation. That is, there is no permuting of the array at all!

Anyways, this is done to see the perfectly ordered state, and how each round effects that state. In this way, we can visually check for the avalanche effect. In order to visualize the table, i just assign each value 0 to 255 a different shade of grey (I also have a rainbow-colored option that might be easier to tell apart similar values). At each step I create a Bitmap by looping through the table. Below, you can find an animated GIF of the first 100 steps of this cipher being applied to the identity permutation:


Notice how it takes a while to get going, and the first several values don't move much at all. After 256 steps, or one round, the cursor arrives back at index zero. Because the location of the first several values have not moved much or at all, we can clearly see that a mere 256 steps is insufficient at permuting the state enough to avoid leaking the first part of your key. Therefore it it is vital to permute the table for several rounds (256 steps per round) before you start using the stream.

Wired Equivalent Protocol

As some of you may know, WEP used RC4 with a weak key schedule. The key is spread out over 256 bytes using the following approach:


j = (j + table[i] + key[i mod keylength]) % 256;
SwapValues(table[i], table[j]);


and then it began streaming bytes from the table. Typically a nonce is concatenated to the key. Every time the table is set up and/or the nonce changes, some information about the key is leaked. Obviously a more secure procedure would use a hash of the key and the nonce, instead of the plain-text key, and to toss away the first 1024 bytes or so.

Cycle Length

Because each step in an RC4 cipher is a permutation, there is a limit to the number of unique bytes that can be produced before it begins repeating. This is called the permutation cycle. The length of the permutation cycle depends on the exact starting state, but we can get an upper bound.

Since there are 256 elements in the array, and two indices into the array (i and j), there is a maximum of
256! * 256^2 = 5.62 * 10^512 = 2^1700
possible states. That's 4.6 * 10^488 yottabytes!

This is the maximum possible states, however, and other starting states could have less. If the RC4 algorithm performed as a random permutation (which it does not, it performs worse), the cycle length would be half of the theoretical maximum above. Luckily the number above is so vast, that even some faction of it is still so many bytes that all of humanity has never and likely will never have that much total storage.

One thing to watch out for, however is something called Finney States. If an RC4 is started in one of these Finney States, the length of the cycle is much, much reduced. The chance of randomly generating one of these starting states, however, is VERY, very low.

Strengthening RC4

As stated, and visualized, above, it is vital to permute the table for several rounds (at 256 steps per round) after the key schedule, discarding the bytes, before you start using the stream. Also, it would be foolish to use the actual bytes of the key for permuting the starting state. It would be instead better to use a hash of the key + nonce or a key derivation function from the key instead the actual value of the key itself.

Another idea is, after shuffling the table enough rounds to hide the key, scramble the table an additional number of rounds, that value being some function of the key. This increases the possible starting states by whatever your range is.

In the classic RC4, each step would return one byte. The number of steps taken before returning each byte is configurable in my implementation.

Memory hardening

Check out the experimental branch for a memory hardened version. It stores the key class in memory, with the key XORed with a one-time pad, and then is protected in memory from access with the System.Security.Cryptography.ProtectedMemory class.

Other uses

The pseudo-random byte stream from the RC4 table is deterministic. Therefore if two remote computers with a shared secret, both computers can independently set up an RC4 table with exactly the same starting state and will get the same sequence of bytes which would be difficult to guess, given just the stream of bytes. If the plain text is XORed by the pseudorandom byte stream, then it can be decrypted by XORing it by the same byte steam.

The project includes 2 variants: 1) A simple table with a method to visualize the permutation state of the table and the avalanche effect as a bitmap 2) A more serious attempt at a secure implementation.


NOTE: THIS HAS NOT BEEN CRYPTO-ANALYZED AND PROBABLY NOT ACTUALLY SECURE, SO DO NOT TRUST IT!

Screenshots




Source code

Here is the GitHub page to the project (master branch).
Or just directly download the Zip file (experimental branch).




Tuesday, July 5, 2016

True hardware random number generator with the Raspberry PI



So, I have been getting into cryptology lately, (For my most recent projects that I may or may not have blogged about at this point, see Bloom Filter and RC4Ever on GitHub).

The other day, I had a need for a TRUE random number generator, so I was searching the web for a hardware random number generator, when I found some very pleasant information: I already own one!

As it turns out, the Raspberry Pi (A/A+/B/B+/and 2) includes a hardware based random number generator, and according to many sources, its a very good source of truly random bytes. Yay!


To get this working on your own Pi, its a breeze:
1) Install the RasPi's random number generator tools: sudo apt-get install rng-tools.
2) Add to the boot process file (/etc/modules.conf) the command to run the hwrng module: bcm2708-rng.
3) Reboot the Pi.

Now, /dev/hwrng is available for reading. Its treated like a device, and you can use the dd command to copy bytes from the device stream to a file (like examples you might have seen doing the same from /dev/random).

NOTE: /dev/hwrng is accessible by the user root only.

But we can change that! The following command gives the user level read access: sudo chmod a+r /dev/hwrng

NOTE: This setting gets reset upon every reboot.

Again, we can change that: Add the following line to /etc/rc.local file, just above the exit 0 line:
chmod a+r /dev/hwrng

And its just that easy!

Now, say if you want to generate 1 megabyte worth of random bytes to a file in /tmp, simply enter the following command into a terminal:
dd if=/dev/hwrng of=hwrng-test-data.bin bs=1024 count=1024

The bs argument specifies the size to buffer before writing to disk. You probably want to leave that at or around 1024. Its the count argument that specifies the size, or amount, of data you want to copy from /dev/hwrng, in Kilobytes. So 1024 == 1 MB, where as 1 == 1KB.

Now, its time for Step 4) Create a C# helper library to simplify the retrieval of random bytes from /dev/hwrng.


So there is two ways to approach this. One is to make a C++ library that makes native calls and then write a .NET interop library to wrap that Or, if you are like me, a little lazy, and find that ever since transitioning to C# you find it difficult to write anything in C or C++ that compiles, you may opt to just issue the above commands to the shell and just read in the resulting file from the tmp directory.

As hackey as this second option might seem, it works remarkably well and I have written a GitHub project doing just that. It consists of a library to return random bytes, and a console executable exercising said library to get random bytes. Links below!


- The PiRngWrapper GitHub Project
- The PiRngWrapperLibrary.cs wrapper code file







Wednesday, June 29, 2016

Bloom Filter - A novel, space efficient data structure like a hash-table for billions of values.




Introduction


A bloom filter is a truly novel data structure. Similar to a hash table, it can tell you if you've hashed a particular value previously. You can add many, many more values to a bloom filter than you can to a hash table, does not degrade performance as the number of values in the set grows large, and requires only a fraction of the space of a hash table to store it!

This is not just an academic exercise, or something that only works in theory or in special cases. Indeed, companies like google use bloom filters to quickly determine if it has never seen that value before, thus avoiding a more costly lookup against a database every time the bloomfilter returns false.



Probabilistic


First off, its important to understand that a bloom filter is NOT a hash table, it operates in an entirely different way. A bloom-filter is what is known as a probabilistic data structure. What this means is, that it can tell you to within a certain probability, if an element exists in a set. In other words, false positive matches ARE possible, but false negative matches ARE NOT possible. For example, if you check a bloom filter for the existence of a value, and it returns false, you can know with 100% certainty that the bloom filter does not contain that value value before. However, if you test a value against the filter and it returns true, there is a small probability that it has in fact not seen that value before, but is returning a false positive. How big of a probability? Here's the beauty: It can be as small as you want it to be. It depends on a few factors, including the size of the filter, how full it is, and how many bits you use to store each value in the filter.

In a HashTable class, each item is stored as a key value pair, so the size of your object plus a 32 bit integer. Contrast that to a bloom filter, which stores only about 3-7 bits per value hashed. Also, my implementation applies compression when saving the filter to disk, providing even more space savings. A bloom filter with 160,000 values hashed and a 1% collision probability results in a filter that is 235KB uncompressed, and a whopping 54KB when compressed! Remember the filter is an array of bits. The entropy of the array is going to be at its greatest, and thus the compression ratio lowest, when exactly 1/2 of the bits are flipped, or the filter is half-way 'full'. This has the unusual property of getting smaller as you add more hashes to the filter. Actually, this is misleading--the actual filter itself never changes size, its only the compressed version that varies in size.

To handle the compression I just used the System.IO.Compression.DeflateStream class. An important note about working with this class: build an array of bytes and send your entire file in one go. In this way it will compress the whole file as one chunk. If you sent data to this stream piecemeal, it will compress each piece separately and you will get a poor compression ratio.

How it works


So how does this all work? The filter part of a bloom filter is just a large array of bits. You also require several different hash functions that each return a unique result for the same input value. When you add a value to the filter, the value is sent to about 3-7 different hash functions. Each hash function will return a value that is between 0 and the number of bits in the filter. Each value is used as an index to access and element on the array of bits that is your filter. When hashing a value, you just set the bit at each index location in the array to 1. Then testing for the presence of a value in the filter, you pass the value to the hash functions the same way as above, then visit each index, checking to see if any of them are 0. If even one bit at one of those index positions are zero, it means the filter has never seen that value before, because it would have set all those bits to 1. If all the bits at the index locations are 1, then it is likely that the filter has seen that value before. However,there is a chance that it is a false positive, because it could be that that value's different hashes all mapped to bits from other values. As the filter becomes more full, more bits are set to 1, and so the odds of a false positive go up. To build your filter by supplying the estimated number of values you think you are likely to store in the filter, and don't go above a certain ratio of 1 bits to 0 bits. If you were to let your filter hash so many values that every bit got set to 1, then the probability of receiving a false positive for a random value becomes 100%.



Solving the many hash problem

As I mentioned before, this requires several different hash functions that each return a unique result for the same input value. Although I said 3-7 hash functions, you might require 14 or more, when working with filters that can handle large number of hashes or a low false positive likelihood or both.

Instead of writing a bunch of separate hash algorithms, I implemented a stream cipher where in I just scramble the cipher table by a number of rounds that is unique to that input. Then, I can return as many indices as the filter is configured for. This sets up the table once per value. It needs to reset the table or else the indices that we mark will depend on every value that came before it, and in that particular order. Currently the bottle-neck is how many times it has the scramble the table for each value. If you need to hash really long values, you'll want to lower the number of rounds it scrambles the table.



Variations


In this implementation, the bloom-filter size is set once you create it, meaning that it cannot grow bigger if it gets too full, nor can you resize this bloom filter to become smaller if you sized it too big. Because multiple values could rely on the same bit, this implementation does not support removal of items, because to do so would cause several values to begin reporting false negatives.

In order to make a bloom filter that supports deletion, use a number like a byte instead of bits in your filter, and each time you visit an index in the filter while adding values, increment the number you find there. Then, to delete a value, visit each index as you did before, but decrement the number there. This way, if two values map to the same index, that information is tracked by incrementing the value. This is what is known as a Counting Bloom Filter.

There are other variants of bloom filters out there, including bloom filters that can grow in size if it gets too full, but such a thing is beyond the scope of my needs. In essence, when the filter gets too full, you create another separate filter, and add new values by first checking the first filter to see if it exists, and if not, adding the value to the second filter. Checking for the presence of a value requires checking both (and other) filters. For information on scalable bloom filters, please see this whitepaper.

The code


My C# Bloom Filter project on GitHub
Or download zip here.








Sunday, August 2, 2015

Certificate Enumerator



     Recently, my windows quit updating. Just prior to that, I had been messing around with my certificate store, so I suspected that to be the cause. Running Microsoft's troubleshooter reset the download, which I had a lot of hope of fixing the issue, but the download still continued to to fail. I decided to check the Windows Event Logs, and that's where I found an error message about a certificate in the chain failing. I knew it! However, I did not know whether a trusted certificate accidentally got put in the untrusted store, or whether an untrusted certificate was accidentally put in the trusted store. I needed a way to search all of my certificates' thumbprints or serial numbers against a know repository of trusted or untrusted certificates.
    Microsoft's certificate snap-in for MMC does not allow you to view certificates in an efficient way. Opening them one at a time, manually, and then scrolling all the way down to where the thumbprint is displayed to compare it to a webpage is painful. Also, I was not satisfied with the way that Microsoft allows you to search the certificate store. The search is not very effective and you cant even search for thumbprints! Also I do not believe the search feature allows you anyway to copy any of that information to clipboard.
Most of what I needed to accomplish could simply be done if I could just export all of my computers certificates thumbprint or serial numbers to a text file, csv file, or other simple and searchable format. Then I thought to myself, I know how to do that! It was the great the lack of features of the MMC certificate snap-in, and the inability to search for certificate thumbprints that inspired me to write my own certificate utility, known simply as Certificate Enumerator.




     CertificateEnumerator can list every certificate in your various certificate stores for your local machine and currently logged in user. It can then display that information to you either in a DataGridView or TextBox (as columnarized text), and provides the ability to persist that information to file as text, comma separated values (CSV), excel format or HTML table.


     The Certificate Enumerator also has the ability to 'validate' each certificate against its CRL (certificate revocation list), if it supplied one.


     The GUI could really use some love. In case you missed it, the project is on my GitHub, so feel free to download the source and play with it. If you come up with useful, submit a pull request.


Wednesday, April 9, 2014

An Implementation of a One-Way Hashing Algorithm using Substitution and Permutation




        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;   
 }
}

Wednesday, August 7, 2013

Pseudo 'random' even distribution table




In my last post, I discussed what a co-prime is and showed you to find them.

So, what's so special about relatively prime numbers? Well, then can be used to create an one-for-one distribution table that is seemingly random, but is deterministically calculated (created).

To understand what I mean, picture the face of a clock...


It has the hours 1 through 12, and if you and an hour to 12, you get 1. This can also be thought of as a single digit in a base 12 number system. Now we need a co-prime to 12. 7 is relatively prime to 12, so lets choose 7.

Starting at hour 1, if we add 7 hours, it will be 8. If we add 7 more hours, we will get 3. 7 more, 10. If we keep adding 7 hours to our clock, the hour hand will land on each of the different numbers exactly once before repeating itself, 12 steps later. Intrigued yet?

If, say, we find a co-prime to the largest number that can be represented by a byte (8-bits, 256 [also expressed as 2^8=256 or 8=Log2(256)]), we can create an array of bytes with a length of 256, containing each of the 256 different possible bytes, distributed in a seemingly random order. The discrete order, or sequence, in which each each number is visited it completely dependent on the value of the co-prime that was selected.

This table is now essentially a one-to-one, bijective mapping of one byte to another. To express this mapping to another party, say to map a stream of bytes back to their original values (decrypt), the entire table need not be exchanged, only the co-prime.

This provides a foundation for an encryption scheme who's technical requirements are similar to handling a cipher-block-chain (CBC) and its changing IV (initialization vector).

Now, it it easy to jump to the conclusion that such an encryption scheme is less secure than a CBC, but this is not necessarily the case. While this approach may be conceptually more simple, the difficulty of discovering the sequence can be made arbitrarily hard.

First of all, the number of relatively prime numbers to 256 is probably infinite. A co-prime to 256 does not have to be less than 256. Indeed, it may be several thousand time greater than 256. Additionally, any prime greater than 256 is, by definition, co-prime to 256, and likely will have a seemingly more 'random' distribution/appearance.

There is, however, a limit here. It does not have to do with the number of co-primes, but is instead limited by the number of possible sequences that can be represented by our array of 256 bytes; eventually, two different co-primes are going to map to the same unique sequence. The order matters, and we don't allow repetition to exist in our sequence. This is called a permutation without repetition, and can be expressed as 256! or 256 factorial and is instructing one to calculate the product of 256 * 255 * 254 * 253 * [...] * 6 * 5 * 4 * 3 * 2 * 1, which equals exactly this number:

857817775342842654119082271681232625157781520279485619859655650377269452553147589377440291360451408450375885342336584306157196834693696475322289288497426025679637332563368786442675207626794560187968867971521143307702077526646451464709187326100832876325702818980773671781454170250523018608495319068138257481070252817559459476987034665712738139286205234756808218860701203611083152093501947437109101726968262861606263662435022840944191408424615936000000000000000000000000000000000000000000000000000000000000000

Yeah, that's right, that number has exactly 63 zeros on the end and is 507 digits long. (As an aside, the reason there is so many zeros on the end of this number is, well for one it is highly composite, but more specifically, its prime factorization includes 2^255 and 5^63 and so 63 fives multiply with 63 of those twos to make 63 tens, and hence that many zeros.)

Above I said arbitrarily hard. So far we have only considered one table, but try and fathom the complexity of many tables. I present three different ways to use multiple tables; Nested, sequentially, and mangled.
Furthermore, the distribution tables can be discarded and replaced.

I will explain what those mean and finish this post tomorrow.


Thursday, August 1, 2013

Greatest common divisor & Co-primeness



Below are three different methods for finding the greatest common divisor of a number. I provide a method using modulus, one using Euclid's method, and one that uses the Stein method.

Believe it or not, the modulus method has the best performance. I would have guessed the Stein method. Credit goes to blackwasp for the stein method.


public static uint FindGCDModulus(uint value1, uint value2)
{
        while(value1 != 0 && value2 != 0)
        {
                if (value1 > value2)
                {
                        value1 %= value2;
                }
                else
                {
                        value2 %= value1;
                }
        }
        return Math.Max(value1, value2);
}

public static uint FindGCDEuclid(uint value1, uint value2)
{
        while(value1 != 0 && value2 != 0)
        {
                if (value1 > value2)
                {
                        value1 -= value2;
                }
                else
                {
                        value2 -= value1;
                }
        }
        return Math.Max(value1, value2);
}

public static uint FindGCDStein(uint value1, uint value2)
{
        if (value1 == 0) return value2;
        if (value2 == 0) return value1;
        if (value1 == value2) return value1;

        bool value1IsEven = (value1 & 1u) == 0;
        bool value2IsEven = (value2 & 1u) == 0;
                       
        if (value1IsEven && value2IsEven)
        {
                return FindGCDStein(value1 >> 1, value2 >> 1) << 1;
        }
        else if (value1IsEven && !value2IsEven)
        {
                return FindGCDStein(value1 >> 1, value2);
        }
        else if (value2IsEven)
        {
                return FindGCDStein(value1, value2 >> 1);
        }
        else if (value1 > value2)
        {
                return FindGCDStein((value1 - value2) >> 1, value2);
        }
        else
        {
                return FindGCDStein(value1, (value2 - value1) >> 1);
        }
}

Here are the results of my benchmark tests:

Stein: 36.4657 milliseconds.
Euclid: 31.2369 milliseconds.
Modulus: 7.5199 milliseconds.



Yeah, I couldn't believe it either, the modulus approach is the fastest!

Here is the benchmark code that I created:

public class CodeStopwatch
{
        //int m_pointer;
        Stopwatch m_elapsed;
        
        public CodeStopwatch()
        {
                Reset();
        }

        public double Stop()
        {
                m_elapsed.Stop();
                return m_elapsed.Elapsed.TotalMilliseconds;
        }
        
        public void Reset()
        {
                GC.Collect(GC.MaxGeneration);
                m_elapsed = new Stopwatch();
                m_elapsed.Start();
        }
}

public class CoprimeBenchmark
{
        public delegate bool IsCoprimeDelegate(uint value1, uint value2);
        public List<uint> FindCoprimesDelegate(uint quantity,IsCoprimeDelegate isCoprime)
        {
                List<uint> results = new List<uint>();
                if(quantity<2) {
                        return results;
                }
                
                for (uint count = 2; count < quantity; count++)
                {
                        if(isCoprime(count,quantity))
                        {
                                results.Add(count);
                        }
                }
                return results;
        }
        
        public static bool IsCoprimeModulus(uint value1, uint value2)
        {
                return FindGCDModulus(value1, value2) == 1;
        }
        
        public static bool IsCoprimeEuclid(uint value1, uint value2)
        {
                return FindGCDEuclid(value1, value2) == 1;
        }
        
        public static bool IsCoprimeStein(uint value1, uint value2)
        {
                return FindGCDStein(value1, value2) == 1;
        }

        // [ Please refer to methods above. Ommited for brevity. ]
        public static uint FindGCDModulus(uint value1, uint value2) { ... }
        public static uint FindGCDEuclid(uint value1, uint value2) { ... }
        public static uint FindGCDStein(uint value1, uint value2) { ... }
}

Usage of above classes:

// Button OnClick event
void ButtonBenchmarkClick(object sender, EventArgs e)
{
        uint number = 50000;
        List<uint> resultsStein = new List<uint>();
        List<uint> resultsEuclid = new List<uint>();
        List<uint> resultsModulus = new List<uint>();
        
        CoprimeBenchmark cop = new CoprimeBenchmark();
        
        CodeStopwatch time = new CodeStopwatch();
        resultsStein = cop.FindCoprimesDelegate(number,CoprimeBenchmark.IsCoprimeStein);
        string stein = time.Stop().ToString();
        
        time = new CodeStopwatch();
        resultsEuclid = cop.FindCoprimesDelegate(number,CoprimeBenchmark.IsCoprimeEuclid);
        string euclid = time.Stop().ToString();
        
        time = new CodeStopwatch();
        resultsModulus = cop.FindCoprimesDelegate(number,CoprimeBenchmark.IsCoprimeModulus);
        string modulus = time.Stop().ToString();
        
        textBoxOutput.Text = "Stein:\t" + stein + " milliseconds." + Environment.NewLine;
        textBoxOutput.Text += "Euclid:\t" + euclid + " milliseconds." + Environment.NewLine;
        textBoxOutput.Text += "Modulus:\t" + modulus + " milliseconds." + Environment.NewLine;
        
        textBoxOutput.Text += Environment.NewLine + Environment.NewLine;
        foreach(uint a in resultsStein)
        {
                textBoxOutput.Text += a.ToString() + Environment.NewLine;
        }
        
        textBoxOutput.Text += Environment.NewLine + Environment.NewLine;
        foreach(uint b in resultsEuclid)
        {
                textBoxOutput.Text += b.ToString() + Environment.NewLine;
        }
        
        textBoxOutput.Text += Environment.NewLine + Environment.NewLine;
        foreach(uint c in resultsModulus)
        {
                textBoxOutput.Text += c.ToString() + Environment.NewLine;
        }
}


--


Now, I will take the fastest algorithm and show you the code for finding co-primness and a list of co-primes for a given number.

Finding co-primness is simple; Two numbers are relatively prime to each other if their greatest common divisor is equal to one.

My function FindCoprimes returns a List<uint> of co-primes given a number and a range

public static class Coprimes
{
        public static List<uint> FindCoprimes(uint number,uint min,uint max)
        {
                if(max<2 || min<2 || max<=min || number<1) {    return null;    }
                
                List<uint> results = new List<uint>();
                for(uint counter = min; counter<max; counter++) {
                        if(IsCoprime(number,counter)) {
                                results.Add(counter);
                        }
                }
                return results;
        }
       
        public static bool IsCoprime(uint value1, uint value2)
        {
                return FindGCDModulus(value1, value2) == 1;
        }
}

Pretty easy!

What is so special about co-primes? Well, one thing I use co-primes for is for making an evenly distributed table. For an explanation and the code, see my post on Evenly Distributed Tables.



Saturday, July 27, 2013

Information entropy and data compression



In my last post, I talked about Shannon data entropy and showed a class to calculate that. Lets take it one step further and actually compress some data based off the data entropy we calculated.

To do this, first we calculate how many bits are needed to compress each byte of our data. Theoretically, this is the data entropy, rounded up to the next whole number (Math.Ceiling). But this is not always the case, and the number of unique symbols in our data may be a number that is too large to be represented in that many number of bits. We calculate the number of bits needed to represent the number of unique symbols by getting its Base2 logarithm. This returns a decimal (double), so we use Math.Ceiling to round to up to the nearest whole number as well. We set entropy_Ceiling to which ever number is larger. If the entropy_Ceiling is 8, then we should immediately return, as we cannot compress the data any further.

We start by making a compression and decompression dictionary. We make these by taking the sorted distribution dictionary (DataEntropyUTF8.GetSortedDistribution) and start assigning X-bit-length value to each entry in the sorted distribution dictionary, with X being entropy_Ceiling. The compression dictionary has a byte as the key and an array of bool (bool[]) as the value, while the decompression dictionary has an array of bool as the key, and a byte as a value. You'll notice in the decompression dictionary we store the array of bool as a string, as using an actual array as a key will not work, as the dictionary's EqualityComparer will not assign the same hash code for two arrays of the same values.

Then, compression is as easy as reading each byte, and getting the value from the compression dictionary for that byte and adding it to a list of bool (List), then converting that array of bool to an array of bytes.

Decompression consists of converting the compressed array of bytes into an array of bool, then reading in X bools at a time and getting the byte value from the decompression library, again with X being entropy_Ceiling.




But first, to make this process easier, and to make our code more manageable and readable, I define several extension methods to help us out, since .NET provides almost no support for working with data on the bit level, besides the BitArray class. Here are the extension methods that to make working with bits easier:

public static class BitExtentionMethods
{
    //
    // List<bool> extention methods
    //
    public static List<bool> ToBitList(this byte source)
    {
        List<bool> temp = ( new BitArray(source.ToArray()) ).ToList();
        temp.Reverse();
        return temp;
    }
    
    public static List<bool> ToBitList(this byte source,int startIndex)
    {
        if(startIndex<0 || startIndex>7) {
            return new List<bool>();
        }
        return source.ToBitList().GetRange(startIndex,(8-startIndex));
    }
    
    //
    // bool[] extention methods
    //
    public static string GetString(this bool[] source)
    {
        string result = string.Empty;
        foreach(bool b in source)
        {
            if(b) {
                result += "1";
            } else {
                result += "0";
            }
        }
        return result;
    }
    
    public static bool[] ToBitArray(this byte source,int MaxLength)
    {
        List<bool> temp = source.ToBitList(8-MaxLength);
        return temp.ToArray();
    }
    
    public static bool[] ToBitArray(this byte source)
    {
        return source.ToBitList().ToArray();
    }

    //
    // BYTE extention methods
    //
    public static byte[] ToArray(this byte source)
    {
        List<byte> result = new List<byte>();
        result.Add(source);
        return result.ToArray();
    }
    
    //
    // BITARRAY extention methods
    //
    public static List<bool> ToList(this BitArray source)
    {
        List<bool> result = new List<bool>();
        foreach(bool bit in source)
        {
            result.Add(bit);
        }
        return result;
    }
    
    public static bool[] ToArray(this BitArray source)
    {
        return ToList(source).ToArray();
    }
}
Remember, these need to be the base class in a namespace, not in a nested class.


Now, we are free to write our compression/decompression class:

public class BitCompression
{
    // Data to encode
    byte[] data;
    // Compressed data
    byte[] encodeData;
    // # of bits needed to represent data
    int encodeLength_Bits;
    // Original size before padding. Decompressed data will be truncated to this length.
    int decodeLength_Bits;
    // Bits needed to represent each byte (entropy rounded up to nearist whole number)
    int entropy_Ceiling;
    // Data entropy class
    DataEntropyUTF8 fileEntropy;
    // Stores the compressed symbol table
    Dictionary<byte,bool[]> compressionLibrary;
    Dictionary<string,byte> decompressionLibrary;
    
    void GenerateLibrary()
    {
        byte[] distTable = new byte[fileEntropy.Distribution.Keys.Count];
        fileEntropy.Distribution.Keys.CopyTo(distTable,0);
        
        byte bitSymbol = 0x0;
        bool[] bitBuffer = new bool[entropy_Ceiling];
        foreach(byte symbol in distTable)
        {
            bitBuffer = bitSymbol.ToBitArray(entropy_Ceiling);
            compressionLibrary.Add(symbol,bitBuffer);
            decompressionLibrary.Add(bitBuffer.GetString(),symbol);
            bitSymbol++;
        }
    }
    
    public byte[] Compress()
    {
        // Error checking
        if(entropy_Ceiling>7 || entropy_Ceiling<1) {
            return data;
        }

        // Compress data using compressionLibrar
        List<bool> compressedBits = new List<bool>();
        foreach(byte bite in data) {    // Take each byte, find the matching bit array in the dictionary
            compressedBits.AddRange(compressionLibrary[bite]);
        }
        decodeLength_Bits = compressedBits.Count;
        
        // Pad to fill last byte
        while(compressedBits.Count % 8 != 0) {
            compressedBits.Add(false);  // Pad to the nearest byte
        }
        encodeLength_Bits = compressedBits.Count;
        
        // Convert from array of bits to array of bytes
        List<byte> result = new List<byte>();
        int count = 0;
        int shift = 0;
        int offset= 0;
        int stop  = 0;
        byte current = 0;
        do
        {
            stop = encodeLength_Bits - count;
            stop = 8 - stop;
            if(stop<0) {
                stop = 0;
            }
            if(stop<8)
            {
                shift = 7;
                offset = count;
                current = 0;
                
                while(shift>=stop)
                {
                    current |= (byte)(Convert.ToByte(compressedBits[offset]) << shift);
                    shift--;
                    offset++;
                }
                
                result.Add(current);
                count += 8;
            }
        } while(count < encodeLength_Bits);
        
        encodeData = result.ToArray();
        return encodeData;
    }
    
    public byte[] Decompress(byte[] compressedData)
    {
        // Error check
        if(compressedData.Length<1) {
            return null;
        }
        
        // Convert to bit array for decompressing
        List<bool> bitArray = new List<bool>();
        foreach(byte bite in compressedData) {
            bitArray.AddRange(bite.ToBitList());
        }
        
        // Truncate to original size, removes padding for byte array
        int diff = bitArray.Count-decodeLength_Bits;
        if(diff>0) {
            bitArray.RemoveRange(decodeLength_Bits-1,diff);
        }

        // Decompress
        List<byte> result = new List<byte>();
        int count = 0;
        do
        {
            bool[] word = bitArray.GetRange(count,entropy_Ceiling).ToArray();
            result.Add(decompressionLibrary[word.GetString()]);
            
            count+=entropy_Ceiling;
        } while(count < bitArray.Count);
        
        return result.ToArray();
    }
    
    public BitCompression(string filename)
    {
        compressionLibrary  = new Dictionary<byte, bool[]>();
        decompressionLibrary = new Dictionary<string, byte>();
        
        if(!File.Exists(filename))  {
            return;
        }
        
        data = File.ReadAllBytes(filename);
        fileEntropy = new DataEntropyUTF8();
        fileEntropy.ExamineChunk(data);
        
        int unique  = (int)Math.Ceiling(Math.Log((double)fileEntropy.UniqueSymbols,2f));
        int entropy = (int)Math.Ceiling(fileEntropy.Entropy);
        
        entropy_Ceiling = Math.Max(unique,entropy);
        encodeLength_Bits   = data.Length * entropy_Ceiling;
        
        GenerateLibrary();
    }
}


Please feel free to comment with ideas, suggestions or corrections.

Monday, July 22, 2013

Information Shannon Entropy



Shannon/data entropy is a measurement of uncertainty. Entropy can be used as a measure of randomness. Data entropy is typically expressed as the number of bits needed to encode or represent data. In the example below, we are working with bytes, so the max entropy for a stream of bytes is 8.

A file with high entropy means that each symbol is more-or-less equally as likely to appear next. If a file or file stream has high entropy, it is either probably compressed, encrypted or random. This can be used to detect packed executables, cipher streams on a network, or a breakdown of encrypted communication on a network that is expected to be always encrypted.

A text file will have low entropy. If a file has low data entropy, it mean that the file will compress well.

This post and code was inspired by Mike Schiffman's excelent explaination of data entropy on his Cisco Security Blog.

Here is what I wrote:

using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;

namespace DataEntropy
{
    public class DataEntropyUTF8
    {
        // Stores the number of times each symbol appears
        SortedList<byte,int>        distributionDict;
        // Stores the entropy for each character
        SortedList<byte,double> probabilityDict;
        // Stores the last calculated entropy
        double overalEntropy;
        // Used for preventing unnecessary processing
        bool isDirty;
        // Bytes of data processed
        int dataSize;
        
        public int DataSampleSize
        {
            get { return dataSize; }
            private set { dataSize = value; }
        }
        
        public int UniqueSymbols
        {
            get { return distributionDict.Count; }
        }
        
        public double Entropy
        {
            get { return GetEntropy(); }
        }
        
        public Dictionary<byte,int> Distribution
        {
            get { return GetSortedDistribution(); }
        }
        
        public Dictionary<byte,double> Probability
        {
            get { return GetSortedProbability(); }
        }
        
        public byte GetGreatestDistribution()
        {
            return distributionDict.Keys[0];
        }
        
        public byte GetGreatestProbability()
        {
            return probabilityDict.Keys[0];
        }
        
        public double GetSymbolDistribution(byte symbol)
        {
            return distributionDict[symbol];
        }
        
        public double GetSymbolEntropy(byte symbol)
        {
            return probabilityDict[symbol];
        }
        
        Dictionary<byte,int> GetSortedDistribution()
        {
            List<Tuple<int,byte>> entryList = new List<Tuple<int, byte>>();
            foreach(KeyValuePair<byte,int> entry in distributionDict)
            {
                entryList.Add(new Tuple<int,byte>(entry.Value,entry.Key));
            }
            entryList.Sort();
            entryList.Reverse();
            
            Dictionary<byte,int> result = new Dictionary<byte, int>();
            foreach(Tuple<int,byte> entry in entryList)
            {
                result.Add(entry.Item2,entry.Item1);
            }
            return result;
        }
        
        Dictionary<byte,double> GetSortedProbability()
        {
            List<Tuple<double,byte>> entryList = new List<Tuple<double,byte>>();
            foreach(KeyValuePair<byte,double> entry in probabilityDict)
            {
                entryList.Add(new Tuple<double,byte>(entry.Value,entry.Key));
            }
            entryList.Sort();
            entryList.Reverse();
            
            Dictionary<byte,double> result = new Dictionary<byte,double>();
            foreach(Tuple<double,byte> entry in entryList)
            {
                result.Add(entry.Item2,entry.Item1);
            }
            return result;
        }
        
        double GetEntropy()
        {
            // If nothing has changed, dont recalculate
            if(!isDirty) {
                return overalEntropy;
            }
            // Reset values
            overalEntropy = 0;
            probabilityDict = new SortedList<byte,double>();
            
            foreach(KeyValuePair<byte,int> entry in distributionDict)
            {
                // Probability = Freq of symbol / # symbols examined thus far
                probabilityDict.Add(
                    entry.Key,
                    (double)distributionDict[entry.Key] / (double)dataSize
                );
            }
            
            foreach(KeyValuePair<byte,double> entry in probabilityDict)
            {
                // Entropy = probability * Log2(1/probability)
                overalEntropy += entry.Value * Math.Log((1/entry.Value),2);
            }
            
            isDirty = false;
            return overalEntropy;
        }
        
        public void ExamineChunk(byte[] chunk)
        {
            if(chunk.Length<1 || chunk==null) {
                return;
            }
            
            isDirty = true;
            dataSize += chunk.Length;
            
            foreach(byte bite in chunk)
            {
                if(!distributionDict.ContainsKey(bite))
                {
                    distributionDict.Add(bite,1);
                    continue;
                }
                distributionDict[bite]++;
            }
        }
        
        public void ExamineChunk(string chunk)
        {
            ExamineChunk(StringToByteArray(chunk));
        }
        
        byte[] StringToByteArray(string inputString)
        {
            char[] c = inputString.ToCharArray();
            IEnumerable<byte> b = c.Cast<byte>();
            return b.ToArray();
        }
        
        void Clear()
        {
            isDirty = true;
            overalEntropy = 0;
            dataSize = 0;
            distributionDict = new SortedList<byte, int>();
            probabilityDict = new SortedList<byte, double>();
        }
        
        public DataEntropyUTF8(string fileName)
        {
            this.Clear();
            if(File.Exists(fileName))
            {
                ExamineChunk(  File.ReadAllBytes(fileName) );
                GetEntropy();
                GetSortedDistribution();
            }
        }
        
        public DataEntropyUTF8()
        {
            this.Clear();
        }
    }
}