Cryptographically secure One-time Pads

It’s the end of Christmas day… And I’ve got a splitting headache (because I don’t drink and had to watch everything). Luckily I’m not covered in someone else’s puke or urine, which is always nice.  No one drove into any trees (as far as I know), lost their pants or an eye.

Super…

Just finished checking my email and it seems a quite a few people were interested in my last post on the one-time pad and one frequent question was how to make it secure enough for truly private communication. First off, the JavaScript version is out if you want true security. Second, it’s best to implement something in a reusable class that can be used perhaps in a web application or client-side app. I chose an MVC web app in C# for this demonstration because my brain won’t let me stay up for much longer.

To make a large enough one-time pad that is both cryptographically secure and still computationally practical, we have to balance between how strong the algorithm is and how often it is iterated. In my original example, I opted to shuffle the character pool using the Fisher-Yates algorithm before a character is picked and each time, the pick was also random from the shuffled pool.

Considering JavaScript’s inherent weakness in that it must rely on the browser’s scripting engine for the psudorandom number, these were necessary improvements even with the added overhead. However, since modern browers do have optimized JS engines, this wasn’t a huge concren.

The problem is when we move toward much stronger cryptographic functions where computation starts to become non-trivial.

In the case of the RNGCryptoServiceProvider, the class provides a much stronger random number than the simple Random function. The output is spectrally white and is better suited for generating keys. The main point here is that it is cryptographically secure. I.E. It’s random enough to be used for proper encryption while still being a psudorandom number generator. The down side is that it is more computationally intensive than just plain Random.

The solution is to not shuffle the pool between character picks, but randomize between “segments”; the separated 6-8 character “words” in the pad. This strikes a good balance between randomness and speed.

Then, the issue comes down to how the pad is generated and presented to the user. Conventionally, this was in the form of plain text or as a downloadable file, however one of the requests I received was to make something that can do both. If the one-time pad can be saved as an image file, it can be sent via encrypted email to the recipient. The risk is that browsers store images and the like and the browser cache must be emptied after each generation. If a printer is used, it must also be cleared of its cache because some printers save a history of printed documents.

The following is a quick class that has both text and image generation. The GetImg function can be used to turn any sort of text into an image byte array, not just pad text.

/**
 * THIS SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
 */

using System;
using System.Security;
using System.Security.Cryptography;
using System.Drawing;
using System.Drawing.Drawing2D;
using System.Drawing.Imaging;
using System.IO;
using System.Text;

namespace OneTimePad
{
	public class PadModel
	{
		// Render settings
		FontFamily renderFont = FontFamily.GenericMonospace;
		FontStyle renderStyle = FontStyle.Bold;
		GraphicsUnit renderUnit = GraphicsUnit.Pixel;
		int renderSize = 10;

		// Creates formatted pages of keys
		public string RenderPad(int s, int l, string chars)
		{
			// Result
			StringBuilder sb = new StringBuilder();

			// First page
			int p = 1;

			for (int i = 0; i < l; i++)
			{
				// First page number
				if (p == 1 && i == 0)
					sb.Append("1.\n\n");

				// Generate segment
				sb.Append(GenerateRandomString(s, chars));

				// Page, number and segment separartion
				if (i % 63 == 62)
				{
					if (i + 1 < l)
					{
						p++;
						sb.Append("\n\n\n");
						sb.Append(p);
						sb.Append(".\n\n");
					}
				}
				else if (i % 7 == 6) // Line separation
				{
					sb.Append("\n");
				}
				else // Segment separation
				{
					sb.Append("   ");
				}
			}

			return sb.ToString();
		}

		// Generates a random string of given length
		public static string GenerateRandomString(int len, string range)
		{
			Byte[] _bytes = new Byte[len];
			char[] _chars = new char[len];

			// Shuffle the range first
			range = Shuffle(range);

			using (RNGCryptoServiceProvider rng = new RNGCryptoServiceProvider())
			{
				rng.GetBytes(_bytes);

				for (int i = 0; i < len; i++)
					_chars[i] = range[(int)_bytes[i] % range.Length];
			}

			return new string(_chars);
		}

		// Implements the Fisher-Yates algorithm to shuffle the range
		public static string Shuffle(string range)
		{
			char[] _chars = range.ToCharArray();
			int len = _chars.Length;
			Byte[] _bytes = new Byte[len];

			using (RNGCryptoServiceProvider rng = new RNGCryptoServiceProvider())
			{
				for (int i = len - 1; i > 1; i--)
				{
					// New set of random bytes
					rng.GetBytes(_bytes);

					int r = (int)_bytes[i] % len;
					char c = _chars[i];
					_chars[i] = _chars[r]; // Swap
					_chars[r] = c;
				}
			}

			return new string(_chars);
		}

		// Generates a jpeg of given text
		public byte[] GetImg(string txt)
		{
			// Blank image
			Bitmap bmp = new Bitmap(1, 1);
			Graphics gfx = Graphics.FromImage(bmp);

			// Font settings
			Font fnt = new Font(renderFont, renderSize, renderStyle, renderUnit);

			// Image dimensions
			int w = (int)gfx.MeasureString(txt, fnt).Width;
			int h = (int)gfx.MeasureString(txt, fnt).Height;

			// New image to text size
			bmp = new Bitmap(bmp, new Size(w, h));

			gfx = Graphics.FromImage(bmp);

			// Defaults
			gfx.Clear(Color.White);
			gfx.SmoothingMode = SmoothingMode.Default;

			gfx.TextRenderingHint =
				System.Drawing.Text.TextRenderingHint.AntiAlias;

			gfx.DrawString(txt, fnt, new SolidBrush(Color.Black), 0, 0);

			// Cleanup
			gfx.Flush();

			MemoryStream ms = new MemoryStream();
			bmp.Save(ms, ImageFormat.Png);
			return ms.ToArray();
		}
	}
}

 

To use this in an MVC application, for example, I would use the following ActionResult.

public ActionResult Index(FormCollection collection)
{
	// Generate
	string chars = "2346789ABCDEFGHKLMNPQRTWXYZ";

	// Default values
	int ds = 8, dl = 882;

	// Store (s = segment size, l = number of segments)
	int s = 0, l = 0;

	// Assign values
	if (Int32.TryParse(collection["s"], out s) || Int32.TryParse(collection["l"], out l))
	{
		// Set defaults to practical limits
		s = (s > 0 && s <= 20) ? s : ds;
		l = (l > 0 && l <= 1000) ? l : dl;
	}
	else
	{
		// Set defaults
		s = ds;
		l = dl;
	}

	PadModel model = new PadModel();
	string txt = model.RenderPad(s, l, chars);
	string img = Convert.ToBase64String(model.GetImg(txt));

	ViewData["s"] = s; // Segment size to be shown
	ViewData["l"] = l; // Total segment count
	ViewData["pad"] = txt; // Plain text version of the pad

	// Instead of sending binary data, I opted to use a base64 encoded image instead
	// since most modern browsers support it anyway
	ViewData["img"] = string.Format("data:image/png;base64,{0}", img);

	return View();
}

 

And in the View page, we can display both the plain text version and the image version of the pad using the following two lines

<img src="<%= ViewData["img"] %>" alt="PadImage" />
<pre><%= ViewData["Pad"] %></pre>

 

As an added benefit of sending a base64 encoded image instead of a binary file is that the base64 text itself can be sent via encrypted email that can be reconstituted by the recipient. This added layer of security is also handy if the user intends to hide the pad in its entirety in another data file.

The image version should produce something like this…

An image based one time pad that can be printed

 

I generated that pad just a little while ago and printed it out on my laser printer. Of course the quality is rubbish because my printer is low-res and only meant for office documents, but with a proper high resolution inkjet, we can get much finer details.

 

One-time pad close-up

 

Because the sheets are numbered, the previous message can contain details on which sheet to use for the next communication. Ideally, these pages should be cut into individual sheets and destroyed after each use.

Hope this was helpful.

Now I’m off to hit the hay!

Do they know that we know that they know?

The answer is always “yes!”

Everyone already knows what they say about assumptions, but there are cases where knowing a possibility makes that particular possibility inevitable as time goes by. In other words… If it can happen, it eventually will.

Allow me to explain…

I’m creating a product that uses, what I believe, the cleanest, most concise and error free method I can formulate. This doesn’t mean I am the only one to figure out this method, nor the only method out there, as mine may not be any or all of those things in reality.

If this is the case, then there is a probability that elsewhere some people have come up with the exact same method to deliver their product. Which means they may or may not put the product to market before you. If it does come to market and you happen to see what it’s all about, you may be concerned.

At that point, the question doesn’t really matter, because it isn’t as if you would simply abandon the project because a competitor has something else. That’s what they do. That’s why they are called competitors. Only once you put your own product out there, then the question really comes up.

“Do they know that you know that they know?”

By considering the answer to that question as “yes”, you are no longer concerned with the secrets of manufacture, but quality and speed. Foregoing the old NASA joke of “Faster, Better, Cheaper… Pick two” all three are possible if the project is approached properly. That should be the only concern. The competitor will always always know that you know that they know. That is to say, don’t worry about it.

What matters is that your product does what it does as well as you can make do. It is only inevitable that you or your competitor figures out what each other is doing. What matters is that you stay ahead of the game with something new and put it out faster than they do. That way, they don’t have time to figure out what you did and how or when they do, it’s too late.

That’s how you change the question into “do they know that we know”. The answer, again, is always “yes!” Now you’re not working to figure out if the competitor knows, of your efforts to figure out their efforts, but whether they know of your efforts. An easily managable situation.

Once again, the solution isn’t “let’s keep everything secret”. The solution is to work fast and as well as possible to make the better product and bring it to market.

If at any point you are confused by this explanation, then feel free to read it as many times as necessary. ;)