Summary: This week, we begin to reverse engineer the home-grown encryption algorithm discussed last week.

Last week I offered you five examples of "encrypted"[1] text that were generated by a home-grown crypto system. Your job was to reverse engineer the algorithm.

Well, the week went by and folks did take a stab at it, but no one managed to break it yet. So I'm extending the contest another week. This article will provide the first part of the algorithm which should get you started. Once you get through this layer, you should be able to work through the solution in a few shifts.[2] If you break the code, write me email and the best writeup describing the algorithm will get a copy of Hacking Linux Exposed, Second Edition.

So, let's look at the first part of my reverse engineering.

We had only encrypted data to work with, and some idea of what acceptable contents would look like, in this case, normal English text. You might argue in an ideal world you would not have any idea what the plaintext would look like, but in the real world you can usually hazard a guess. For example if you find encrypted-looking text in a database, the field name will probably indicate what it is. If an email contains only an encrypted body, then it is likely composed of readable characters.

The five encrypted strings were as follows:

  # String 1
  !!@!1P!=P!?P!=P!?`!>`!<0!?0!;0!?0!=@!B`!,`!>@!A0!,P!>@!B@!A`

  # String 2
  !T`!M0!TP!V0!X0!Y0!C@!P0!Y0!W0!UP!Y@!H@

  # String 3
  !8@!>@!E`!EP!H`!GP!I0!GP!60!A@!I`!J@!L@!M@!7P!A0!N0!L@!L@!MP!J@!J@

  # String 4
  !^`!P0![0![0!IP!]0!H@!Z`!Y0!^0!I@!``![0!]0!]@!^@!`P!K0!`0!_0!_P!"`!P`

  # String 5
  !S@!O0!W`!SP!BP!V0!X@!X@!XP!D`!G@!D@!YP!V0![0!Z@!EP!X0![`!F@!W0!X0!\`!\@!K0

You should notice a few things instantly:

• Every third character is an exclamation point

• The number of characters in each line is evenly divisible by three, indicating that the original characters are probably being expanded into three characters through this algorithm.

• All the characters are in the printable ASCII set -- this algorithm is probably created to be usable in plain text fields such as email, or database character strings.

• There seem to be a high quantity of backtick (`) characters

It seemed that input characters were being transformed into 3 output characters, where the first was always "!". For some reason, my head was screaming "uuencode" - the standard way to transform 8 bit data streams into 7-bit printable characters, back before folks started using Base64 encoding. On a whim, I ran a command line perl script to print out the uuencoded values (using the 'pack' function in perl) for the first few letters of the alphabet:

  prompt$ perl <<EOM
    for my $let ( 65..75 ) {
        print "$let (",   chr($let),    ") => ",   pack( 'u', chr($let) )
    }
  EOM

  65 (A) => !00``
  66 (B) => !0@``
  67 (C) => !0P``
  68 (D) => !1```
  69 (E) => !10``
  70 (F) => !1@``
  71 (G) => !1P``
  72 (H) => !2```
  73 (I) => !20``
  74 (J) => !2@``
  75 (K) => !2P``

Look - the exclamation points that were so common in the encrypted text. However the results are 5 characters, not the three that we'd expect. But if you check out the uuencoding of any single byte, it is always "!..``" where only the "." characters change. So I suspected that the algorithm dropped the trailing backticks.

So, I started writing an actual decryption program. First, we stick the backticks back in and then uudecode:

  prompt$ cat decrypt.pl
  #!/usr/bin/perl
  use strict;

  my $encrypted =
     '!!@!1P!=P!?P!=P!?`!>`!<0!?0!;0!?0!=@!B`!,`!>@!A0!,P!>@!B@!A`';

  # Add the backticks again
  $encrypted =~ s/(...)/\1``/g;

  print unpack( "u", $encrypted );

  prompt$ perl decrypt.pl
  Gww|xq}m}v_0z_3z__b

(Note that, since some letters will be outside the printable range, I'll show them as underscores for the rest of this article.)

Ok, that obviously didn't do the trick, there was something else going on. Here's where you get to continue. I promise that the above crypto analysis is accurate, so here's your branching off point.

Happy decrypting!

NOTES:

[1] Yes, this encryption algorithm is extremely weak. But I'll dispense with putting quotes around encrypted henceforth.

[2] Whoa, a hint and a bad pun all in one.

Bri Hatch is Chief Hacker at Onsight, Inc and author of Hacking Linux Exposed and Building Linux VPNs. He developed his first (horribly insecure) cryptographic algorithm when he was six. It was no better than rot13, but took up a lot more space. Bri can be reached at bri@hackinglinuxexposed.com.

Copyright Bri Hatch, 2003

This is the January 29, 2003 issue of the Linux Security: Tips, Tricks, and Hackery newsletter. If you wish to subscribe, visit http://lists.onsight.com/ or send email to Linux_Security-request@lists.onsight.com.