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!

Advertisements

4 thoughts on “Cryptographically secure One-time Pads

    • Well, none of the terrible things I was imagining happened so Very Merry! Very surrounded by lunatics, but Merry nonetheless ;)

      I did manage to sleep all day since this post and I just woke up just a little while ago. :D

  1. Might be worth pointing out that OTPs are only have full theoretical security if the randomness comes from a true random number generator. If you’re using a PRNG like windows entropy poll or anything else then you might as well just use a block cipher, the security is the same (Because PRNGs themselves are similar to a block cipher). Most stream ciphers xor the output from a PRNG directly to the ciphertext and you distribute the keys to those PRNGs as the secret

    Which is identical to your case; which means your OTP is actually a printed out stream cipher, not a OTP

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s