+------------------------------------------------------------------+ | 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 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 linux_security-requestat_private 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 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