Some notes on XOR (one way hash) Encryption

A while back, I was looking for information on cryptographic techniques that would help me break a simple XOR encryption. In that course, I found this code snippet that purported to demonstrate how to do it. It’s written in Pascal, or so I presume. It looks like Pascal, which I haven’t worked with in prolly 20 years. But it’s plain enough to read and see what it is doing.

procedure TForm1.Button1Click(Sender: TObject);
var i,j:longword;
    thistime,lasttime:longword;
    buffer:array[0..7]of byte;
b:array[0..1]of longword absolute buffer[0];
    plaintext:array[0..7]of byte;
    p:array[0..1]of longword absolute plaintext[0];
    key:array[0..7]of byte;
    k:array[0..1]of longword absolute key[0];
begin
   lasttime:=gettickcount;
   randomize;
   if length(edit1.text)<8 then exit;
   for i:=0 to 7 do
   begin
      plaintext[i]:=byte(edit1.text[i+1]);
      buffer[i]:=plaintext[i] xor random(256);//encrypt
   end;
   i:=0;
   repeat
      for j:=0 to 1000000 do //loop is unrolled by compiler
      begin
         randseed:=i;
         key[0]:=random(256);
         key[1]:=random(256);
         key[2]:=random(256);
         key[3]:=random(256);
         key[4]:=random(256);
         key[5]:=random(256);
         key[6]:=random(256);
         key[7]:=random(256);
         if b[0] xor k[0]=p[0] then
         if b[1] xor k[1]=p[1] then
         begin
            thistime:=gettickcount;
            caption:='The key is: '+inttostr(i)+' _
                      ('+inttostr((thistime- lasttime) _
                       div 1000)+'sec)';
            Exit;
         end;
         inc(i,1);
      end;
      caption:=inttostr(i);
      application.processmessages;
   until i>longword(MaxInt);
end;

The basic “english translation” here is this:

Take each character of the cypher (encrypted) text, and XOR it with a random byte value. Do this over and over until you get the first character of the plaintext. So if your plaintext is “KIRBY”, then XOR the first character of the cypher text with random bytes until it yeilds “K”. Make note of that random byte value, and move on to the next position. Keep doing this until you have converted the entire cypher text into plain text (ie, keep doing it until you get “KIRBY” out of it). At that point, the combination of all the random byte chars that you noted IS they key that was used to encrypt it.

While that certainly is true, it doesn’t help you crack an XOR in which the plain text is not known. And that is, after all the goal. But without knowing what the plain text is, you don’t know when to “stop and make note of that random byte”.

The problem they are pointing out here – and possibly correctly – is that if you can make an educated guess as to what the plain text might be in one instance, you might get the key which would then let you decrypt anything else that was encoded with that same key.

But to do that, you have to break one key somehow.

A problem with XOR is that, once you have the key, any other message coded with that same key is immediately trivial. The weakness of XOR is not the strength of the algorithm but the managerial problem of exchanging keys. You can either use the same key over and over, and your crypto will very soon become trivial, or you can change the key very frequently, but then you have to communicate that key – and LOTS of them – for the system to be useful. In this process, your keys are MUCH more likely to be compromised. Let’s face it, it’s much easier to conceal and transport a single small BB, than it is to conceal and transport a metric ton of them – on a regular basis. The weakness of XOR is the business of Key-Exchange.

An interesting thing about the STRENGTH of XOR is this – and I mention it just “for fun” because it is kinda fun:

Performing a brute force attack on the following Cypher-Text: 0C4A7B2F3E4D50BC6A3C519F will, at some point along the way yeild ALL of the following Plain-Texts:

GO TO THE STORE
DO NOT GO TO THE STORE
ROB THE STORE
BLOW UP THE STORE
YOU ARE THE STORE

In fact, you can yield all the above no matter what the cypher-text actually is. Any cipher text will produce any plaintext, depending on the key you use. “THE KING’S NOT IN THE BLDG” will yield all the above messages just as easily – only at different points along the way. And, “THE KING’S NOT IN THE BLDG” is also one of the texts that can be extracted from “0C4A7B2F3E4D50BC6A3C519F”. It all depends on the key.

Essentially, XOR is shorthand for X-tORture. You can EXTORT or TORTURE any message out of any cypher text. The problem is, without confidence that you have the ACTUAL key, you never know which plain-text message you are deriving is actually the right one.

Advertisements

About combatdba

I'm a production DBA at a terabyte-class SQL Server Shop
This entry was posted in General. Bookmark the permalink.

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