[ISN] Cryptography Contest: Cracking an Algorithm bit by bit.

From: InfoSec News (isnat_private)
Date: Thu Jan 30 2003 - 00:49:46 PST

  • Next message: InfoSec News: "[ISN] REVIEW: "Information Security Best Practices", George L. Stefanek"

    |  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
      # String 2
      # String 3
      # String 4
      # String 5
    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) )
      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
      use strict;
      my $encrypted =
      # Add the backticks again
      $encrypted =~ s/(...)/\1``/g;
      print unpack( "u", $encrypted );
      prompt$ perl decrypt.pl
    (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!
    [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 brianat_private
    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
    Archives of this and previous newsletters are available at
    Copyright 2003, Brian Hatch.
    ISN is currently hosted by Attrition.org
    To unsubscribe email majordomoat_private with 'unsubscribe isn'
    in the BODY of the mail.

    This archive was generated by hypermail 2b30 : Thu Jan 30 2003 - 03:23:45 PST