Cryptography Contest: Cracking an Algorithm bit by bit.

[InfoSec News <isn () c4i org>]

+------------------------------------------------------------------+
|  Linux Security: Tips, Tricks, and Hackery                       |
|  Published by Onsight, Inc.                                      |
|                                                                  |
|  29-January-2003                                                 |
|  http://www.hackinglinuxexposed.com/articles/20030129.html       |
+------------------------------------------------------------------+

This issue sponsored by EFF: Defending Freedom in the Digital World

The Electronic Frontier Foundation (EFF) is a membeship organization
that needs your help. EFF works to protect civil liberties taht
relate to new technologies. Our lawyers engage in cases that champion
online freedoms, our site archive is a comprehensive digital rights
resource, and we've developed a powerful media presence.

Check out http://www.eff.org/ to learn more.

--------------------------------------------------------------------

Cryptography Contest: Cracking an Algorithm bit by bit.
By Brian Hatch

Summary: This week, we begin to reverse engineer the 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 week. But I'll
dispense with putting quotes around encrypted henceforth.

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

                            -------------                            
Brian 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. Brian can be
reached at brian () hackinglinuxexposed com.

--------------------------------------------------------------------
This newsletter is distributed by Onsight, Inc.

The list is managed with MailMan (http://www.list.org). You can
subscribe, unsubscribe, or change your password by visiting
http://lists.onsight.com/ or by sending email to
linux_security-request () lists onsight com.

Archives of this and previous newsletters are available at
http://www.hackinglinuxexposed.com/articles/

--------------------------------------------------------------------

Copyright 2003, Brian Hatch.



-
ISN is currently hosted by Attrition.org

To unsubscribe email majordomo () attrition org with 'unsubscribe isn'
in the BODY of the mail.