Softwire Speed Coding Challenge – Question 3 Discussion


14 May 2012, by

previous article in series

In our last coding challenge post, we posted question 3 from our coding challenge. Did you try it yourself? Here’s the question again, as a reminder:

Truly Unbreakable Security

Linked (Secret.zip) is a file I have encrypted using the “truly unbreakable” security offered here. It has subsequently been zipped.

  • Short summary of the encryption: XOR each byte of the plaintext file with the next byte produced by a new instance of System.Random in C#
  • I have linked the source code of the encrypting app as Vernam.zip (NOTE: you do not need to read this)

I would like you to decrypt this file.

To aid you in this, here are the 7 most common “magic numbers” from Wikipedia. These are byte sequences which appear at the start of a file to mark the file format:

CAFEBABE    class
47494638    gif
FFD8FFE0    jpeg
89504E47    png
4D546864    midi
25504446    pdf
504B0304    zip

As if that weren’t enough, you also get these two enormous hints:

  • There are two constructors for System.Random – the default no-args constructor uses Environment.TickCount as a seed
  • I rebooted my system less than an hour before encrypting this file

Answer

Did you manage to crack the code? If you did, you will have got a picture looking something like this:

Secret Image - courtesy of Nick Black at www.thegibson.org

This one is a little more complicated so it is worth giving a summary of what is being done as well as having the code itself!

Essentially, this is what happens:

  • The data file is read out into a byte stream
  • For each possible seed (where a “seed” can be used to generate identical sequences of random numbers; see the remarks on this page for more details), the first block of data is compared to the “magic numbers”
  • When we have a match, we process the rest of the file and write it to disk

I’ve also added some comments to the code itself, in order to provide a bit more explanation where the code is a little trickier to follow!

Winning Solution – Submitted by Rupert Wood:

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

namespace SSC2_03
{
  class Program
  {
    static void Main(string[] args)
    {
      int length;
      byte[] secret;

      //----------------------------------------------------------
      // Read the data file.
      //----------------------------------------------------------
      using (FileStream stream = File.OpenRead(@"e:secret.dat"))
      {
        length = (int) stream.Length;
        secret = new byte[length];
        int bytesRead = stream.Read(secret, 0, length);
        stream.Close();
        if (bytesRead < length)
        {
          throw new Exception("Didn't read full file");
        }
      }

      byte b1 = secret[0];
      byte b2 = secret[1];
      byte b3 = secret[2];
      byte b4 = secret[3];

      int seed = 0;
      byte[] fourBytes = new byte[4];
      Random r;
      for(;;++seed)
      {
        if ((seed % 10000) == 0) Console.WriteLine(seed);

        r = new Random(seed);
        r.NextBytes(fourBytes);
        byte f = (byte)(b1 ^ fourBytes[0]);

        //-------------------------------------------------------
        // Check the first byte of the magic number against the
        // first generated byte of data with this seed. This is
        // a bit more efficient than checking against *all* of
        // the four bytes, especially if we are performing a
        // number of operations.
        //-------------------------------------------------------
        if ((f != 0xCA) && (f != 0x47) && (f != 0xff)
         && (f != 0x89) && (f != 0x4d) && (f != 0x25) && (f != 0x50))
        {
          continue;
        }

        //-------------------------------------------------------
        // We're happy with the first byte of data, check against
        // the rest of the key. Create an integer based on the
        // data and compare against the data we've received in
        // the format we received it in (i.e. as a hex string).
        //-------------------------------------------------------
        uint magic = ((uint)(f & 0xff) << 24)
                   | ((uint)((b2 ^ fourBytes[1]) & 0xff) << 16)
                   | ((uint)((b3 ^ fourBytes[2]) & 0xff) << 8 )
                   | ((uint)(b4 ^ fourBytes[3]) & 0xff);

        if ((magic == 0xCAFEBABE)
         || (magic == 0x47494638)
         || (magic == 0xFFD8FFE0)
         || (magic == 0x89504E47)
         || (magic == 0x4D546864)
         || (magic == 0x25504446)
         || (magic == 0x504B0304))
        {
          Console.WriteLine("seed = {0} magic = {1}", seed, magic.ToString("x"));
          break;
        }
      }

      //----------------------------------------------------------
      // We've got a match for the magic number, process the rest
      // of the file. As described in the question, the encryption
      // method involves XORing the data with the four bytes of
      // random data generated.
      //----------------------------------------------------------
      secret[0] ^= fourBytes[0];
      secret[1] ^= fourBytes[1];
      secret[2] ^= fourBytes[2];
      secret[3] ^= fourBytes[3];
      byte[] rest = new byte[length - 4];
      r.NextBytes(rest);
      for (int i = 4; i < length; ++i)
      {
        secret[i] ^= rest[i - 4];
      }

      //---------------------------------------------------------
      // We're done processing; create our unencyrypted file.
      //---------------------------------------------------------
      using (FileStream output = File.Create(@"e:secret.out"))
      {
        output.Write(secret,0,length);
        output.Close();
      }
    }
  }
}

Comments on the Winning Solution

As was the case in the last question, there wasn’t a huge amount of variety when it came to general program structure here as what you needed to do was well constrained. Rupert did manage to pick up on a couple of neat tricks that no doubt helped him win this round!

  • Rupert was the only one that checked for a match on the first byte alone (rather than all four bytes) when trying to figure out the magic number. (This is the initial “if” statement, where the first byte is checked against the first of the four “magic number” bytes.
  • He was also the only person who checked the first four bytes as a unit, comparing the magic numbers against the first bytes in integer format.

General Comments

One of the few areas of difference in the solutions was between the use of strings and byte[]‘s – many people converted from byte[] to string so that we could use easier string comparison code to look for matches rather than testing each element of an array. As ever, Linq has the answer – IEnumerable.SequenceEquals() handles all your array equality needs!

Other useful library methods for this question were:

  • File.ReadAllBytes and File.WriteAllBytes. Bear in mind that reading the entire file into memory may well not be a good idea in all cases, especially if you are dealing with large files!
  • IEnumerable.Zip, which takes two sequences (key and encoded bytes say) and allows you to operate on consecutive element pairs and generate a combined stream.

As a small aside, if you did use a FileStream, make sure you use it within a using() block so that it get disposed correctly! (Well done, Rupert!) Not disposing of your objects can lead to some resources becoming unavailable for use and can lead to difficult-to-debug issues where the file itself is inaccessible.

Join us next time for the final question, it might be worth brushing up on your Dijkstra 😉

next article in series

Tags: , , , , ,

Categories: Social, Softwire, Technical

«
»

One Response to “Softwire Speed Coding Challenge – Question 3 Discussion”

  1. Rupert Wood says:

    Thanks! In hindsight I’m not sure the initial byte check really helped, since I’m only saving a few XORs and shifts, and they are likely cheap with respect to the Random bytes generation anyway.

    Aside from File.ReadAllBytes and File.WriteAllBytes (which I hadn’t come across at the time) another nice-to-have I thought of after submitting was to switch on the magic value and generate the correct file extension once we’d identified the type.


Leave a Reply

* Mandatory fields


seven − 3 =

Submit Comment