nettime's_dusty_archivist on Mon, 20 Mar 2000 07:38:59 +0100 (CET)

[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]

<nettime> The Breaking of Cyber Patrol® 4 [part 1 of 2]

[orig from <>]

[part 1 of 2]

The Breaking of Cyber Patrol® 4

   Written by Eddy L O Jansson and Matthew Skala
   "Cyber Patrol has sophisticated anti-hacker security." -- Cyber Patrol
   Several attacks are presented on the "sophisticated anti-hacker
   security" features of Cyber Patrol® 4, a "censorware" product intended
   to prevent users from accessing Internet content considered harmful.
   Motivations, tools, and methods are discussed for reverse engineering
   in general and reverse engineering of censorware in particular. The
   encryption of the configuration and data files is reversed, as are the
   password hash functions. File formats are documented, with commentary.
   Excerpts from the list of blocked sites are presented and commented
   upon. A package of source code and binaries implementing the attacks
   is included.
  Table of contents
    1. Introduction
    2. Metodus operandi
    3. Overview
    4. Analysis of cp4crypt()
    5. Cryptanalysis of cp4hash()
    6. Files, formats and the URL database
    1. Structure tables
    1. Rogue deinstallation
     Source and binaries
    1. CPHack documentation
    1. Thanks
  1 Introduction
   The market is full of "parental control" applications, and as has been
   shown in earlier essays [DFR98, DFR99], they are mostly of low
   technical quality. When we now look at Cyber Patrol (v4.03.005), we
   find that this trend continues. Some things are a little better than
   what we're used to from products like CyberSitter and NetNanny, but
   mostly, things are the same.
   We will begin by presenting our goals for the evening, with a small
   digression on the "how" and "why" in a section we call Metodus
   operandi, followed by a quick overview of our target for the day. We
   start getting technical as we do a quick presentation of a cipher
   found in the target. After that little snack we move on to the main
   course, something a little bit more complicated, the cryptanalysis of
   a hash function. At this point we have completed the first goal, and
   so we move on to take a closer look at how CP manages its URL
   database. Putting the technicalities behind us we make some
   observations about the product as a whole. As we take our last bite
   out of the target, we treat ourselves to a dessert; some source &
   binaries to drive our point home. All good things must end, so also
   this pleasant evening. We draw our conclusions, say our goodbyes and
   part with only a handful of references to follow up on.
   Let the festivities begin!
  2 Metodus operandi
   People often ask "How can I learn to do these things?". The answer is
   the same as for all other things you want to learn: you must study,
   and you must practice. This, of course, was not the answer the
   questioner was hoping for. There is a certain amount of "magic" in
   learning this crude form of reverse engineering. There are no books to
   learn from, and most of the material on the web is quite bad. There
   are some excellent essays from some excellent practitioners out there,
   but while the knowledge possessed by the authors is often great, their
   presentation is often sub-par, which can make the material
   inaccessible to the beginner.
   There's really no substitute for practice, but what you must have is a
   firm ground to stand on. This means good knowledge of binary
   arithmetic and of the platform you are to work with, both the
   processor and the operating system. While these things can actually be
   learned by means of books and classes, most people are probably
   self-taught in these matters.
   It's been said that to be good at creating ciphers, you must be good
   at breaking them. Similarly, we'd like to say that to be good at
   reverse engineering, you must be a good programmer. So, if you haven't
   already, learn a language or two.
   Now, let's say you have all the background knowledge you need. Then
   you need some tools. You will need a good debugger. There are a couple
   out there, but for the Win32 platform most people are using the one
   included in their development environment, such as the one in
   Microsoft's Visual Studio, or one of NuMega's offerings, of which the
   crown jewel is the systems debugger SoftIce. SoftIce has been the tool
   of choice of crackers and device-driver developers for over half a
   decade now, and it is a very competent product. In addition to a
   couple of programming languages and a good debugger, you will want a
   good hex-editor. Here the choices are plenty, at least on the "WinDos"
   platform. One good hex-editor which is often mentioned is HIEW. It's a
   favourite primarily because it supports some disassembly functions and
   because many of us feel comfortable in the Norton Commander-esque
   interface. Speaking of disassembly, you will probably want a good
   disassembler, and here there is really only one product worth
   mentioning by name, and that is IDA. There're quite a few other
   disassemblers out there, but IDA - which disassembles ELF executables
   too by the way - is the most advanced and most competent of them.
   In addition to the big three, there are some other utilities that you
   might want to add to your toolbox. We're thinking mainly of such tools
   as regmon and filemon by SysInternals.
   Add in a little paper, a good pencil and possibly a calculator, and
   you are all set.
   Now, this is not meant as an essay for teaching real beginners about
   reverse engineering, cryptanalysis or any such matters, but feedback
   from the essay on NetNanny indicates that the pieces on how the
   reversal was done were really appreciated by you readers, and so we
   will try to incorporate some of that into this essay too. Hopefully,
   those of you not interested in these matters will find it easy
   skipping the sections in question.
   Let's start from the beginning. Before we even install a product we
   must have some set of goals we want to achieve. For Cyber Patrol the
   goal was to break the authentication scheme and to extract the URL
   database, documenting the structures in the progress, thus
   facilitating interoperability. These constitute practical goals. You
   will also find less pragmatic goals for the launching of an attack,
   such as the inquisitive desire to learn the internals of someone
   else's product, the thrill of doing something you are not supposed to
   be able to do, and the recognition you might gain for being the first
   one to explore unchartered territory. We can call these goals of
   personal gratification. More interesting for the majority of people
   are probably the political goals, to expose any hidden agenda that
   might be lurking behind the product and to fuel the discussion around
   it, in this case the discussion around censorware. For us, the primary
   motivation has been the possible political implications.
   With the goals firmly set in mind, we begin our work to achieve them.
  3 Overview
   Installation is straightforward. You will note, however, that you are
   not asked to supply an installation path. This is a typical example of
   producers taking the easy way out. Rather than going through with the
   little extra bit of effort, they chose to take the easy route - by
   forcing all their customers to install the software into C:\PATROL no
   matter what.
   Now, before we speak some more on how we can achieve our goals, let's
   go on a short tour of the program. For reference, here's a screenshot
   of the main interface. As can be seen, a large part of the main
   interface is devoted to time management. For each day in the week you
   can - with a 30 minute granularity - control the hours in which a user
   is allowed to use the Internet. You can set the maximum amount of time
   "online" allowed per day and calendar week.
   To the upper right, you'll find a panel for controlling the filters in
   Cyber Patrol. It's fairly straightforward, but let's run through the
   alternatives anyway.
   IRC Chat
          Filters on keywords that are not allowed to be part of the
          channel name.
          Lets you specify things that are never to be allowed to be
          transmitted over the Internet, such as your address, phone
          number and the like. The clipboard will be monitored too. The
          "Carlin-7" mentioned are shit, piss, fuck, cunt, cocksucker,
          mother-fucker, and tits. See also [ACLU96]
   WWW, FTP & Other
          This is where you add any additional URLs you want to filter,
          or allow, as the case may be.
          This screen is virtually identical to the "WWW, FTP & Other"
          one, but here you can define any newsgroups you want to filter.
          You can also choose to apply the IRC keyword filters to
          newsgroup names.
   Games & Applications
          Here you can specify up to sixteen 16-bit windows applications
          that should not be allowed to be run. Not very useful if you're
          running a 32-bit operating system though.
   Also in the main interface, under "categories" the following
   categories are available for filtering:
    1. Violence / Profanity
    2. Partial Nudity
    3. Full Nudity
    4. Sexual Acts / Text
    5. Gross Depictions / Text
    6. Intolerance
    7. Satanic or Cult
    8. Drugs / Drug Culture
    9. Militant / Extremist
   10. Sex Education
   11. Questionable / Illegal & Gambling
   12. Alcohol & Tobacco
   13. Reserved 4
   14. Reserved 3
   15. Reserved 2
   16. Reserved 1
   It is, as we will show in the section on file formats and the URL
   database, not a coincidence that there are sixteen categories in this
   list. The last four entries, named "reserved", are greyed out and
   cannot be toggled on or off by the administrator. In addition,
   "Reserved 4" and "Reserved 3" are selected, and thus cannot be
   unselected. We'll comment more on this later, but rest assured that an
   opportunity for foul play lurks right there.
   Now, let's review our goals. First, we want to break the
   authentication, so let's talk about that. There are three levels of
   access in Cyber Patrol. You could be the administrator, which gives
   you full access to both the Internet, naturally, and to administering
   CP. Below the administrator is a "deputy". A deputy is someone who's
   given full access to the Internet, bypassing CP, but is not allowed to
   do administration. Everyone else is simply a "user" and must abide by
   whatever filtering and rules CP enforces.
   After installing CP it will install its hooks and remain loaded in the
   background. To disable it you must authenticate against it. If you
   want more than one person to have administrative privileges, then you
   must give them the administrator password; similarly for deputies. As
   the administrator you can add users, which is simply a matter of
   assigning a password to go with the username and then setting up the
   restrictions you want to apply to him or her. A user can then
   authenticate against CP by right-clicking on the CP icon in the
   taskbar and select his or her name from a list of all users
   configured. After you've chosen your username you'll be prompted for
   the password. It's generally acknowledged that giving out account
   names like this is bad security since it makes it easier to attack
   them, for example by guessing likely passwords.
   Now, to break the authentication we must simply follow the flow from
   where we enter our password, to where the valid passwords are
   retrieved and compared against ours. Or, so goes the theory...
  4 Analysis of cp4crypt()
   Real life isn't nearly as neat and perfect as our theory would have
   it. In order to break the authentication scheme, i.e. extract the
   passwords, we must first locate them. The obvious way, and so our
   theory says, is to trace the path from entry down to comparison. In
   the case where retrieval was done earlier and thus is not in the path,
   we can actually backtrack once we've found out what our password is
   compared to. We would do that by setting a breakpoint on the memory
   occupied by the data our password was compared against, then - by
   restarting the application - gaining access to the point where that
   data is loaded. This, however, was not the path we took in this
   reversal. We were a little bit less methodical, but maybe a little bit
   more intuitive.
   We quite simply disassembled the target and browsed it for suspicious
   code. Using the debugger to locate something like this can be very
   effective in terms of time spent, but in the grander scheme of things
   you will want to spend some time browsing the disassembly just to get
   a feel for the program. The debugger is great for following a specific
   path and to learn exactly what gets loaded into every register, but
   it's not a very effective way of learning to know the program more
   generally, because it's hard to track different code paths with it.
   So there we were, browsing our disassembly of CP.EXE for suspicious
   code. So what constitutes suspicious code, anyway? This of course
   depends on the context and the type of application, but as a general
   rule you will want to slow down when you encounter xors used in any
   other way than with the same register as both source and destination,
   as in xor eax, eax, or against an immediate value not a power of two.
   We're looking for clusters of bit-manipulation instructions; shifts,
   ands, ors, xors, rotations and compact loops. These are all signs that
   you might be dealing with some sort of encryption routine.
   So, lazily browsing the code was how we ended up in a routine we call
   cp4crypt(), which we will now examine in detail. In reality we're
   speaking of two different routines, one doing the encryption and one
   doing decryption. We'll use the term cp4crypt to mean these two
   collectively, or the cipher algorithm they express.
   The first thing one wonders when one finds a suspicious routine is
   "For what is this routine used?". An important question, and to answer
   it we use our next most powerful tool, the debugger (the most powerful
   tool of course being your brain, and don't ever let anyone tell you
   otherwise). By inserting the special opcode 0xCC, or INT3 as it is
   also known, into the suspicious code, we can make the debugger active
   when the routine is run. Typically you will want to enter this into
   the entry-code of the routine.
   To give you an idea of how "suspicious" code can look, here is the
   piece of code we found:
4D6D:0025               loc_4D6D_25:
4D6D:0025 66 8B CA                      mov     ecx, edx
4D6D:0028               loc_4D6D_28:
4D6D:0028 D0 C8                         ror     al, 1
4D6D:002A 67 32 03                      xor     al, [ebx]
4D6D:002D 67 88 03                      mov     [ebx], al
4D6D:0030 66 43                         inc     ebx
4D6D:0032 67 E2 F3                      loopd   loc_4D6D_28
4D6D:0035 66 2B DA                      sub     ebx, edx
4D6D:0038 FE CC                         dec     ah
4D6D:003A 75 E9                         jnz     loc_4D6D_25

   The sequence of instructions that start with the ror (rotate right),
   followed by xor reg,mem (which is really a memory fetch) and then a
   memory store in mov [ebx],al triggers our interest. We also notice the
   two tight loops. This is a school book example of Intel x86
   encryption/decryption code, similar in complexity to the things you
   might find in old DOS viruses.
   For those of you unfamiliar with the architecture it should be noted
   that this particular Intel instruction set is read with the
   destination to the left and the source to the right, so the xor
   operation fetches the byte addressed by ("pointed to by") the register
   ebx and xors that byte with the value in the register al, and then
   stores the result back into al.
   The section of code above is a decryption routine. When the whole
   thing is translated into a higher level pseudo-code it reads something
   like this:
 key = ctsize & 0x000000FF
 do twice
   for each ctbyte in file
     rotate key right
     ptbyte = ctbyte ^ key
     key = ptbyte

   Algorithm in English:
     * First the key is initialized to be the low eight bits of the
       ciphertexts size.
     * Then we make two passes in which we:
     * Rotate (not shift) the key one bit to the right.
     * The key is exclusively-or'ed to the current ciphertext byte to
       give the corresponding plaintext byte
     * The key is set to be the now decrypted byte
   There are numerous issues with this algorithm which make it very weak.
   First of all we have the key size, which - weighing in at only eight
   bits - is, shall we say, very short of being impressive. Of course,
   since we have the code for deriving the key (that ctsize & 0x000000FF
   operation) a longer key wouldn't be much use anyway.
   Obviously this was never intended to be strong, but even so, someone,
   some where, spent time developing this scheme. There are certainly
   simpler ways of doing weak encryption than this, but this is actually
   a perfect example of the kind of homebrew encryption you are likely to
   find in commercial applications.
   To continue, the key update schedule is weak in that the key only
   depends on the previous byte. This means that plaintext repetitions
   longer than the number of rounds used will show through in the
   ciphertext. The number of rounds used by CP, as described above, is
   two. A competent cryptographer should be able to break this in mere
   hours (and by breaking, we mean recovering the plaintext and with it
   the algorithm), having access only to ciphertext. In real life we also
   have some assumed plaintext in that the file 'cyberp.ini' is encrypted
   using this scheme. Such a file probably starts with "[" or ";" and
   ends with 0x0d,0x0a, to mention but a few hooks. The use of two rounds
   strengthens the cipher somewhat from a ciphertext only attack, but...
   this is academia, not really relevant to our real life situation, in
   which we don't have to recover the algorithm by means of cryptanalysis
   of ciphertext. We can simply locate and translate the algorithm as it
   is implemented in the target. Much easier, much faster, though maybe a
   little bit less fun and rewarding.
   We introduced you to the decryption code because it's somewhat simpler
   to explain compared to the encryption code. The reason for this is
   that we must, in effect, encrypt the buffer backwards, and we must
   also treat it as a circular buffer, and even then we need to do a
   fixup at the end to key the encrypted data. Because of these
   complications we'll present some code that is a little closer to an
   actual implementation than pure pseudo-code:
 for i = BufferSize-1 downto 1 do
   key = Buf[i-1]
   rotate key right
   Buf[i] = Buf[i] ^ key

   Now, the buffer must be seen as circular due to the way the key (which
   is set to the previously decrypted byte when decrypting) carries over
   from one round to the next. It's possible to write this into the loop
   above, but in our case that would only make the explanation more
   difficult to follow. Anyway, after the loop we connect the two ends of
   the buffer:
 key = Buf[BufferSize-1]
 rotate key right
 Buf[0] = Buf[0] ^ key

   After that little tie-in we do another round of the backward
   encrypting loop above, after which we must do one final fixup for the
   first byte by keying the whole buffer with the lower eight bits of the
   buffer's size.
 key = BufferSize & 0x000000FF;
 rotate key right
 Buf[0] = Buf[0] ^ key

   There, now Buf[] will be encrypted. See the section on sources and
   binaries if you want to look at an actual implementation of these
   Now, for the question we posed, for what is this encryption used?
   cp4crypt() is used to encrypt some of Cyber Patrol's data files, such
   as the file cyberp.ini which contains configuration and user
   information, and also the administrator and deputy passwords. This
   cipher also protects the raw URL database, i.e. the files cyber.not
   and cyber.yes. It is also used on the file user.lst which contains
   some configuration information, most notably any additional URLs the
   local administrator(s) may have added.
   Let's talk about the passwords. The cyberp.ini contains a main
   section, "Cyber Patrol", under which the two passwords are stored in
   the keys "HQ PWD" and "DEPUTY PWD". The data of both these keys is
   encoded as a hexadecimal string representing eight bytes, or 64 bits
   if you prefer. It can look something like this:
  DEPUTY PWD=9A3740C7019A5AA1

   The deputy password is in fact the password encrypted using
   cp4crypt(), so it is a simple matter of decoding the hex-string into
   binary and then decrypting the string using the key 0x08, the maximum
   length of a password, and voilá; instant unrestricted access to the
   Internet. Are you impressed? We're impressed.
   This file also contains any additional users that have been
   configured. First the main section contain keys of the form
   "UserNameNN=name" where NN is a number. Associated with these keys are
   sections of the form "[UserNN]", which contains not only that users
   configuration but also his password (in the key "password"), again,
   encrypted using cp4crypt().
   But here things become interesting, because the administrator password
   is not encrypted in this way, the data for the administrator password
   is in fact a 64-bit hash value. Analysis of the hash function follows.
  5 Cryptanalysis of cp4hash()
   Throughout this section we'll use vaguely C-like notation, with some
   of the extensions common in cryptographic circles. In particular:
     * = is assignment
     * == is test for equality
     * ^ is bitwise XOR
     * | is bitwise OR
     * & is bitwise AND
     * ^=, |=, and &= are assignment variations of the above, just like
       in C
     * << and >> are unsigned shift left and right
     * <<< and >>> are bit rotate
     * ** means exponentiation (2**4 is two to the fourth power, which is
   All numbers are unsigned, and bits are numbered from 0 (least
   significant). When we get to the mathematical part, we'd ideally like
   to use some notation that doesn't map into ASCII. There we'll use
   reasonable approximations:
     * a[1], a[2], etc. for subscripts on variables... not the same as
       array indexing, but you can think of it as being like array
     * a = b (mod n) for "a is congruent to b modulo n"; it'd be nicer to
       use the proper math "congruent" symbol, which is like an equals
       sign with three bars.
   Cyber Patrol uses a technique called "hashing" for its HQ password.
   Instead of simply storing the password in its configuration files, it
   processes it through a "hash function" to produce a code called a
   "hash", and it stores the result. The hash function is supposed to
   have these properties:
     * The same password will always produce the same hash.
     * Two different passwords will not produce the same hash.
     * Given the hash, it's impossible to determine the password that
       produced it.
   These properties guarantee that the program can recognize the correct
   password when it's typed, but people like ourselves can't determine
   the password when we reverse engineer the program, even if we obtain
   the hash. In practice, even a very strong hash function cannot
   guarantee these properties perfectly - for instance, we could always
   try all possible passwords until we found the one that gives the
   correct hash. If the hash is shorter than the input password, then
   it's absolutely guaranteed that some two inputs will have the same
   hash. But strong hash functions do exist, which come close enough to
   the theoretical ideal for most purposes. Cyber Patrol's hash functions
   are not like that. The deputy password isn't even truly hashed; it is
   encrypted with the cp4crypt() routine already discussed.
   The hash function for the Cyber Patrol HQ password looks like this in
(1)   hash1 = 0
(2)   hash2 = 0
(3)   for every character in the input:
(4)      input character |= 0x20
(5)      hash1 = (hash1>>8) ^ table[(hash1 & 0xFF) ^ (input character)]
(6)      hash2 = (hash2<<<5) + (input character) - hash1
(7)   end for
(8)   result is hash2 concatenated with hash1 (64-bits)

   The first thing we notice here is that every input character gets bit
   5 set in line (4). That seems to be case conversion - it forces all
   alphabetic input characters to lowercase. It has some other effects as
   well (making certain punctuation characters equivalent to each other)
   but if the passwords are expected to always be alphanumeric, that
   shouldn't make much difference. One significant issue (which we'll
   revisit later) is that it gives attackers a bit of known plaintext: we
   know that bit 5 of every input character is 1. We can also guess that
   bit 7 of every input character is 0, since it's tricky to type
   characters with that bit set to 1 on an ordinary keyboard.
   Next let's look at line (5). This one may seem a little confusing: we
   shift 8 bits out of hash1, look them up in a table (using the input to
   screw with the index of the table), and XOR the result back into
   hash1. The table, if you look at it, seems at first glance to be
   random garbage. Here we just have to depend on our experience to
   enable us to recognize the code: it happens that this code is a
   standard idiom for hash calculation.
   To be precise, it's a 32-bit linear feedback shift register, also
   known as a CRC (cyclic redundancy check). This kind of algorithm is a
   traditional way of checking data integrity in things like file
   transfers and compressed archive files. Most serious programmers have
   written it, or something very much like it, before. The definitive
   explanation of CRCs is in [RNW93]. Most people who have to write CRC
   code consult that file for instructions; it's a reasonable bet that
   Microsystems based their code on it. Line (5) of our pseudocode is
   pretty much verbatim from one of the examples in that document.
   The code in Cyber Patrol isn't even just any CRC - examination of the
   table shows that except for a nonstandard initialization, it is the de
   facto standard CRC32 algorithm, used in ZModem, PKZip, Ethernet, and
   FDDI (among other places). CRC32 has proven to be a very successful
   error detection measure in these systems. Because it provides pretty
   good bit diffusion (i.e. changing one bit in the input changes lots of
   bits in the output) CRC32 is also a reasonable hash function just as a
   hash function. If you were building a hash table data structure, CRC32
   wouldn't be a bad way to generate your indices. It is not, however, a
   cryptographically strong hash function suitable for password hashing.
   CRC32 has fatal cryptographic holes - it not only provides no
   security, but also gives us a lot of hints for breaking the rest of
   the hash. We'll show how to exploit the holes below.
   Before we do, let's look at hash2, the other half of the 64-bit hash.
   This seems to be something homemade, created by throwing together
   several different techniques in an effort to provide cryptographic
   strength. That isn't a good way to build cryptographic systems, but in
   this particular case, it seems to have resulted in something that is
   at least better than the CRC half of the hash.
   There are three basic parts to the hash2 calculation: rotate the
   previous value, mix in the input character, and mix in the current
   value of hash1. The rotation gives us a little bit of what
   cryptographers call avalanche - bit changes get shifted around to
   eventually affect most of the word. Using addition and subtraction
   instead of XOR is important because the carry bits allow some
   information to flow from one bit position to the next.
   The designers are treating hash1 as a random number, and hoping to
   confuse things by mixing it in at every stage. It's not really very
   random at all, but combined with the carry bits and the rotation,
   there is a little bit of security here. In fact, in our attacks we
   haven't bothered to do much to hash2, cryptographically speaking; the
   results on hash1 are strong enough that we can get away with ignoring
   most of the holes that may exist in hash2.
   We might well speculate about the reasons for designing the hash
   function this way. It looks like Microsystems chose the CRC32
   algorithm because they knew it was a standard algorithm, and then they
   knew that 32 bits wasn't enough for a cryptographically strong
   algorithm, so they added some stuff. They knew that bit rotations are
   popular in cryptographic algorithms, and they knew that addition and
   XOR are popular, so they put in some of each.
   If they knew more than a little about how CRC32 worked, they'd have
   used a 64-bit CRC instead of extending the 32-bit version with
   homebrew stuff. If they understood the security implications of CRC32,
   they wouldn't have used it at all. So the general pattern here is that
   the pieces are there, but they aren't understood nor put together
   systematically. If you have a copy of the Jargon File[JRG00], the
   entry for "cargo cult programming" might be educational.
   Now, let's talk about cryptographic strength. Strength of
   cryptographic algorithms is measured by the order of magnitude of the
   fastest or most space-consuming attack. An algorithm is strong if the
   best attack takes too much time or space to be practical; it's also
   preferable that the best attack be a straightforward brute-force
   attack, because any other attack indicates a security hole which might
   easily become worse as the theory of cryptanalysis improves. An
   attack's difficulty is the amount of time or space it requires,
   whichever is worse, typically measured as a power of two (like
   This table is designed to give a very rough idea of the scale of the
   numbers involved. The exact time to attack a system will depend very
   much on the system, the optimizations, the hardware, etc. (what
   computer scientists call "constant factors"); as a result, the stuff
   in this table could well be off by a factor of a thousand or more in
   either direction. Where we're going, that isn't going to matter.
   Difficulty Resources required
   2**0 Pencil and paper
   2**8 Pencil and paper and a lot of patience
   2**16 Warez d00d with a Commodore 64
   2**32 Amateur with an average PC
   2**40 Smart amateur with a good PC
   2**56 Network of workstations, custom-built hardware
   2**64 Thousands of PCs working together for several years
   2**80 NSA, Microsoft, the Illuminati
   2**128 Cubic kilometers of sci-fi nanotech
   2**160 Dyson spheres
   Some real-life examples: the EFF's "Deep Crack" machine uses custom
   VLSI to solve a problem of difficulty 2**56 in a few days. The RC5 effort is attacking a problem of difficulty 2**64
   and expects to finish within a few years. The maximum keyspace of
   symmetric cryptography exportable without a license from the United
   States, before they made the rules more complicated recently, was
   2**40. Standard practice in most crypto circles is to use symmetric
   encryption keyspaces of 2**112 or 2**128. Those aren't directly
   comparable with the cryptographic hash sizes we're talking about, but
   the point here is the general size of the numbers involved.
   There are two ways in which you could break a cryptographic hash
   function: you could find an input that will produce a specified
   output, or you could find two inputs that produce the same output. For
   a hash with n bits of output, assuming it's cryptographically perfect,
   the difficulty of finding an input for a specified output is 2**n
   time, negligible space, and to find two different inputs with the same
   output, 2**(n/2) time and space. So, the two basic attacks we could
   apply to the HQ password (assuming it was perfect) are:
     1. Brute-force search: try inputs until one gives the right output,
     finds an input for a chosen output in 2**64 time and 2**0 space.
     2. Birthday Paradox attack: try inputs, remembering their hashes,
     until we find two with the same output. Finds such a pair in 2**32
     time and space.
   The prompting code in Cyber Patrol limits password inputs to 8
   characters, and we bash them to lower case and can assume the high
   bits are zero, so there are in fact only 48 bits of unknown input to
   the hash. That reduces the time for a brute-force search:
     3. Brute-force search with assumptions about input: finds password
     for a given hash, in 2**48 time, 2**0 space.
   That's starting to get into the range where it's feasible to attack.
   In fact, this attack lends itself to a time/space tradeoff because the
   hash is unsalted. Let's talk about Unix and salt for a minute. The
   Unix operating system uses a similar concept of password hashing. It
   doesn't store the user's password in the password file - only a hash
   (based on the DES algorithm) of the password. If it were a pure hash
   of the password, then a determined cracker could compile a codebook of
   all possible passwords and their hashes, and just look up each hash in
   the list. Also, the cracker could go down a list of users and
   recognize who had the same password (because they'd have the same
   hash) even without knowing what the password was.
   To prevent such attacks, Unix has a concept of "salt". Before hashing
   the password, the system chooses a random number called the salt. It
   then hashes the salt along with the password, and stores the salt and
   the resulting hash in the password file. Now a given password can hash
   to a lot of different values, depending on the salt. The attacker
   can't compile a codebook, or at least the codebook would have to be a
   lot bigger, because its size is multiplied by the number of possible
   salt values. The attacker can't identify pairs of users with the same
   password, because they'll probably have different salts and so
   different hashes.
   Cyber Patrol doesn't use any salt. As a result, it's vulnerable to a
   codebook attack, which as you can see is really just a time/space
   tradeoff of the brute force search above:
     4. Codebook attack: 2**48 time and space to compile the codebook
     once and for all, 2**0 time to look up each password.
   All those attacks apply to any hash function with this amount of input
   and output, no matter how cryptographically strong it may be; to avoid
   them, Microsystems would have to use a longer, stronger hash function.
   We like SHA1; it's got a 160-bit output and no known attacks better
   than brute force, so it takes 2**160 time to attack by brute force
   search, and 2**80 time and space for the much weaker birthday paradox
   attack. Of course, the prompting routines in Cyber Patrol would have
   to be modified to accept longer keys; with 48-bit passwords, about all
   they could do would be add salt, and pray.
   The first cryptographic hole that's apparent in the Cyber Patrol hash
   is that the per-character processing is bijective, for a given input
   character. What that means is that if we know the input character and
   the output, we can be absolutely sure of what the state was before
   that character. All we have to do is reverse the steps; we won't dwell
   on how to do that here because we have better things to do, but it's
   not hard to figure out.
   The bijective nature of the hash function makes it possible to do a
   meet-in-the-middle attack. To find an input for a given output, we
   hash about 2**32 guesses for the first half and store them. Then we
   hash backwards from the known output, about 2**32 guesses for the
   second half of the input. After doing that amount of work we expect to
   find about one pair of a first half that goes to an intermediate value
   with a second half that comes from the same intermediate value, and
   then we've broken the hash. This is about the same amount of work as
   the classic birthday paradox attack, but it allows us to find an input
   for a chosen output instead of just two inputs for the same output.
   It's enough to indicate that the Cyber Patrol hash is a lot weaker
   than a theoretical perfect cryptographic hash of the same size. But as
   we'll soon see, we have much stronger attacks on it.
     5. Meet-in-the-middle attack: input for a chosen output in 2**32
     time and space.
   Before we can talk about the difference between CRC32 and
   cryptographic hash functions, we have to learn some math. Let's talk
   about modulo arithmetic. Suppose you have an equation involving
   integers, addition, subtraction, and multiplication, like this:
   12 + (34 * 56) = 1916

   In modulo arithmetic, we have a number called the modulus, and we say
   that any two numbers are considered equal (or "congruent") if they
   have the same remainder when you divide them by the modulus, or in
   other words, if they differ by exactly a multiple of the modulus. It's
   an amazing fact that if you take any equation like the one above and
   replace all the numbers with their remainders when you divide by some
   modulus, you get a congruence that works. For instance, let's take all
   the numbers modulo 9; we can do that by adding up all the digits, and
   then if the result is two digits or more, adding up those, etc. This
   is the old accountant's trick of checking computations by "casting out
   12 + (34 * 56) = 1916        <-- equation
   3 + (7 * 2) = 17 = 8 (mod 9) <-- congruence

   Note that 17 (or 8, which is the same thing) is what you get if you
   take the digits in 1916 and add them up. All the numbers in the mod 9
   congruence come from adding up the digits in the equation above.
   In modulo n arithmetic, there are really only n numbers: 0 up to n-1.
   Anything else is congruent to one of those. To understand CRC32 we're
   going to use the second most boring kind of modulo arithmetic: modulo
   2. In our mod 2 universe there are only two numbers, 0 and 1. Are you
   starting to see how this could be relevant? Incidentally, the very
   most boring kind of modulo arithmetic is mod 1; everything equals
   zero. Anyway, let's look at the addition and multiplication tables for
   modulo 2:
   + 0 1   * 0 1
   0 0 1   0 0 0
   1 1 0   1 0 1
   Notice anything? The addition table is the same thing as what we like
   to call ^ (XOR) and the multiplication table is the same thing as what
   we like to call & (AND). This connection is important because it means
   we can take programs which do bit twiddling, and apply the mathematics
   of addition and multiplication to figure out what's going on.
   The CRC32 algorithm simulates a linear feedback shift register. We
   won't try to draw the diagram here, but the concept it simple: you
   shift bits out of the register one at a time, and you have a mask
   that's as long as the register, and you XOR the stream of bits you
   shift out with the stream of input bits, and every time the result is
   1, you XOR the mask into the register. Why this is useful is best
   explained in [RNW93]; we'll just take it for granted that in
   communications error checking, this is a sensible thing to do. The
   8-bit shift, and the magic table, are just a clever way of doing a
   whole byte at once. The result is the same as if you did the bits one
   at a time.
   What's important cryptographically is that after you've performed one
   cycle, every bit is either equal to the bit next to it (if its mask
   position was 0), or it's equal to the XOR of the bit next to it, the
   bit that just got shifted out, and the input bit (if its mask position
   was 1). Let's say we have a short register, four bits long, with the
   mask value 1011. Let a[0] to a[3] be the previous state, b[0] through
   b[3] be the next state, and x be the input bit. Then we have:
   b[3] = x + a[0]        (mod 2)
   b[2] = a[3]            (mod 2)
   b[1] = x + a[0] + a[2] (mod 2)
   b[0] = x + a[0] + a[1] (mod 2)

   Notice how we're using the + symbol to denote bit XOR; in modulo 2,
   it's the same thing. The most important thing to notice here is that
   every output bit is a XOR of some combination of the input bits. If
   you take two output bits and XOR them together, you find that the
   result is still simply a XOR of some of the input bits:
   b[1] = x + a[0] + a[2]     (mod 2)
   b[0] = x + a[0] + a[1]     (mod 2)
   b[1] + b[0] = x + x + a[0] + a[0] + a[1] + a[2]   (mod 2)
               = a[1] + a[2]  (mod 2)

   Note that we can get rid of all the terms that are repeated twice or
   an even number of times, because those are like multiplied by an even
   number, and all even numbers are equal to zero in modulo 2 arithmetic.
   OK, it takes some getting used to, but it really is easy once you see
   With the CRC32 algorithm, there are lots more variables than in that
   example, but this same general property holds: the CRC32 bits are each
   the modulo 2 sum of some combination of the input bits. Actually, in
   strictly correct CRC32 it's a little more complicated because the
   register doesn't start at 0, so you have to XOR in some extra bits
   that depend on the length of the input. But fortunately for our
   discussion, Cyber Patrol uses a nonstandard variant of CRC32 which
   initializes the register to 0.
   We can figure out a congruence for each output bit by feeding inputs
   into CRC32 which consist of only one bit set to 1 and all other bits
   set to 0. If an output bit is set for that input, then the input bit
   that was 1 is included in the congruence for that output bit. Once
   we've tested all the input bits this way, we have the entire
   To save space on the page, we will write out our congruences with all
   the variables included, multiplied by 0 or 1, like this:
   0*b[0]+0*b[1]+0*b[2]+1*b[3] = 1*x+1*a[0]+0*a[1]+0*a[2]+0*a[3] (mod 2)
   0*b[0]+0*b[1]+1*b[2]+0*b[3] = 0*x+0*a[0]+0*a[1]+0*a[2]+1*a[3] (mod 2)
   0*b[0]+1*b[1]+0*b[2]+0*b[3] = 1*x+1*a[0]+0*a[1]+1*a[2]+0*a[3] (mod 2)
   1*b[0]+0*b[1]+0*b[2]+0*b[3] = 1*x+1*a[0]+1*a[1]+0*a[2]+0*a[3] (mod 2)

   and then leave out everything except the coefficients (the 0 or 1 we
   multiply by):

   That block of bits has all the information from the complete set of
   congruences. It's what mathematicians call a "matrix", but there's no
   need to think too hard about what that means; just call it an
   abbreviated set of congruences. Each row is equivalent to a
   congruence, and we can add congruences to each other (the same way we
   did earlier) by XORing one row into another. If we shuffle the rows
   around and XOR them enough, we can solve for whatever variables we
   want - it's just like the simultaneous equations we learned in high
   school. For example, if we desperately want to know the value of a[1]
   in the example, we can say:
   b[3] = x + a[0]         (mod 2)
   b[0] = x + a[0] + a[1]  (mod 2)
   b[0] + b[3] = a[1]      (mod 2)

   or in our abbreviated notation:
 + 100011100
 = 100100100

   We wrote code to figure out the set of congruences for the CRC32
   algorithm as implemented in Cyber Patrol, using all 32 output bits and
   96 input bits (12 characters, which is overkill, but bits are cheap).
   Here's the resulting matrix. Input bits come first, first bits 0 to 7
   of the last byte, then bits 0 to 7 of the second-to-last byte, and so
   on; after that are the 32 outputs, again in order from 0 to 31. (This
   ordering of bits was easiest to program; it doesn't really matter.)

   Notice the diagonal stripe at the right-hand side of the matrix. That
   stripe reflects the fact that we have one congruence for each output
   bit, in order. Now, by flipping and XORing rows (the exact technique
   we used is called Gauss-Jordan elimination, which is just a
   formalization of the "system of equations" technique you do in high
   school) we shuffled that stripe over to the left, to get a set of
   congruences that tells us the last bits of the input based on the
   output and the other input bits:

   The diagonal isn't perfect here for a couple of reasons. One, we
   didn't solve for bits 5 and 7 of any input byte, because we don't have
   a choice for the values of those bits. We can't allow the congruences
   to force impossible values on them. Two, we found that some pairs of
   input bits are actually equivalent to each other. There's no way to
   solve for both of such a pair - you just have to choose a value for
   one or the other of them. But the point is that from this "solved" or
   "inverted" matrix, we have a set of congruences where we can choose
   all but 32 bits (including all the output bits of the CRC) and then
   just by evaluating the congruences, we get the values for the other
   input bits to make the whole thing work.
   This is why CRC32 is not a cryptographic algorithm: anyone who knows a
   little matrix algebra can generate inputs for a chosen output in
   minimal time. We extracted the columns from our solved matrix and put
   them into tables in cph1_rev.c. The reverse_crc() function takes
   parameters specifying the input length, some choices for the "free"
   input bits, and the desired output value. Then it fills in the
   "forced" bits for the chosen input length, and goes through its tables
   XORing together all the columns that correspond to 1 bits in the
   partial input. Then the result contains all the values for the rest of
   the input bits. It unpacks them and returns the completed input. The
   bit packing order is also in tables. Some checking of the result may
   be necessary because if you ask for a very short CRC input, there may
   well be no such input for the output you requested.
   Now we can attack the Cyber Patrol hash just as if it were a strong
   hash with only 32 bits of output:
     6. CRC-breaking Birthday Paradox attack: choose an output for the
     CRC32, generate inputs with that CRC32 value, save their hash
     values, until you have two the same. Finds such a pair in 2**16
     time and space.
     7. CRC-breaking brute force: choose an output for the CRC32,
     generate inputs with that CRC32 value until you find one with the
     hash you want. Finds an input for a chosen output in 2**32 time and
     2**0 space.
   But because we know that the input password is only 8 ASCII
   characters, bashed into lowercase by the OR with 0x20, we can improve
   the attack still further. With 8 input characters there are 48 bits
   unknown, and of those, we can derive 32 from the set of congruences.
   That leaves us only 16 bits unknown. We can simply test all possible
   values for those 16 bits, by brute force. This is the attack
   implemented by cph1_rev.c.
     8. CRC-breaking brute force, with assumptions about the input:
     finds input for a chosen output (assuming it really came from an
     8-character ASCII password) in 2**16 time, 2**0 space. Shorter
     passwords take much less time, so we can test all shorter passwords
     first, without increasing the cost noticeably.
   Our code for this attack isn't particularly optimized, and we haven't
   attacked the rotate-and-add part of the hash at all, but even so we
   can now reverse the function in a fraction of a second. At this point
   it's appropriate to categorize the Cyber Patrol HQ password hash
   function as blown wide open, thus fulfilling our first goal.
  6 File formats and the URL database
   The primary function of Cyber Patrol is to do filtering based on a
   database of URLs that are not allowed. CP can also be configured to
   work with the inverse policy, denying everything but a small set of
   allowed URLs, a very strict policy.
   The source of the URLs that are denied is a file called cyber.not.
   Conversely, the file cyber.yes is used for the "allowed" URLs.
   Currently the not file is about 600Kb, with the yes file only about
   50Kb. Roughly, this means there are less than one tenth as many
   allowed URLs as there are denied ones. These files are actually
   processed into another format and file called cyber.bin for use by the
   different Cyber Patrol modules. We will not discuss the format of this
   file since the raw files are much more suited to our needs.
   Before we broke the encryption on the cyber.not file, we did some
   short-range correlation measurements on it, to check for
   polyalphabetic encryption (like the classic "simple XOR" algorithm).
   The idea here was to measure, for various values of k, how often the
   byte at offset x was identical to the byte at offset x+k. We used a
   simple Perl script to compile these statistics.
   We found that very often, after some byte value would occur, the same
   byte was repeated again six bytes (or, somewhat less often, seven
   bytes) later. That would point towards some kind of modified
   polyalphabetic cipher with a key length that switched between six and
   seven bytes, or some very weak cipher that didn't conceal repeats in
   the plaintext, and record sizes of six and seven bytes in the
   plaintext. It turned out to be the latter, but we didn't find that out
   by cryptanalysis. Reverse engineering yielded the answers more easily,
   as described earlier.
   However, those six- and seven-byte repeats seemed interesting,
   especially once we had decrypted cyber.not, reversed its header
   format, and split it out into its component tables. The first table we
   figured out was the last one in the file, the table of blocked
   When reversing a file format it makes sense to start at the easy end,
   and with the cyber.not file that means the table used for newsgroup
   masks. What made this the obvious starting location is that it's very
   obvious - from a fast ocular inspection - what it is for. A section
   might look something like this (some unprintable characters replaced
   by question marks):
00065A90:  00 41 00 02-00 00 00 07-02 00 68 38-0B F7 07 11   A ?   ?? h8?½??
00065AA0:  00 FA BD 29-B8 00 5F 0A-28 07 1E 00-45 44 53 44   ¢)© _ (?? EDSD
00065AB0:  22 00 04 43-6F 70 79 72-69 67 68 74-2E 4D 69 63  " ?Copyright.Mic
00065AC0:  72 6F 73 79-73 74 65 6D-73 2E 53 6F-66 74 77 61  rosystems.Softwa
00065AD0:  72 65 0D 60-00 61 2E 62-73 75 2E 72-65 6C 2A 0B  re ` a.bsu.rel*?
00065AE0:  06 00 61 62-74 2E 6D 61-6D 2A 0B 0E-00 61 62 67  ? abt.mam*?? abg
00065AF0:  2E 74 65 73-2A 0E 0E 00-61 63 61 64-69 61 2E 62  .tes*?? acadia.b
00065B00:  75 6C 2A 07-00 08 61 6C-63 2A 0C 08-04 61 6C 74  ul*? ?alc*???alt
00065B10:  2E 32 33 69-73 2A 0A 09-04 61 6C 74-2E 32 36 2A  .23is*  ?alt.26*

   Some quick looking around would show that "ED" marks "End-of-Data" and
   consequently "SD" ought to mark "Start-of-Data". The first thing to do
   is try and see what constrains a record. Either there's a length
   count, a special marker, or the records are fixed length. They are not
   fixed length, that much is apparent, but they all end in an asterisk,
   so maybe that is a record terminator? Could be, but the first string,
   the "Copyright..." ends with 0x0d. To make sure, we must see if we can
   find a length marker, a common way to handle variable sized records,
   and also the preferred method in many ways. Now, because there are
   three "non-character" bytes between SD and the first string, we try
   this pattern on the other strings, and it checks out. Thus, we can
   guess that a record starts with three bytes, followed by a variable
   number of characters. A way to verify this result is to look at the
   end of the table, to see what kind of data ends the last record.
   Now, for the length, that would have to be one of the three bytes, so
   it shouldn't be too hard to locate, if indeed it exists. The first
   record starts '22 00 04' and then the string. The length of the string
   is more than zero or four, and definitely less than 1024 (0x400). By
   counting we see that the string is 31 characters, or 0x1F in hex. Very
   close to 0x22, and where could the difference come from? But of
   course, the three prefix bytes.
   This leaves one or two bytes per record unaccounted for. How many
   depend on how large the length specifier is. Looking around we find
   examples of records in which the second byte of the records is
   something besides zero, which would make the length way too long, and
   thus we can conclude that we are working with a length byte and not a
   word. Now them, what about the remaining two unaccounted bytes? As you
   may remember from the overview we mentioned that there are sixteen
   different categories available for filtering. The two remaining bytes
   are actually a blocking mask - a word whose bits maps to those sixteen
   categories. We call these records TNotNewsEntries.
   Having found the start and end, and thereby the size, of one table
   mean we have some usable information for reversing the next-easiest
   part of the file, the header. Our header looks like this in binary:
00000000:  FC 00 2A 00-43 48 00 00-00 00 03 01-03 00 49 00   * CH    ??? I
00000010:  F8 34 00 00-B6 25 06 00-41 00 2C 00-00 00 CC 34  4  ¬%? A ,   ¶4
00000020:  00 00 4E 00-AE 5A 06 00-B8 25 00 00-53 44 80 53    N ´Z? ©%  SD«S
00000030:  28 0F 02 80-53 28 10 80-53 28 11 D1-01 1C DE 01  (§?«S(?«S(???Ã?

   Seeing how "SD" marks the start of data, we can calculate the size of
   the header as 0x2C bytes, meaning the first table (of which there are
   at least two, one being the table for newsgroup masks) ought to start
   at 0x2C, the location of the "SD" marker. Experience tells us that
   headers often contains pointers (offsets), lengths, and counts (of
   records). Let's see if we can match any of those types into the
   We begin to look for pointers into the different tables. We know that
   the first one start at 0x2C (the "SD" marker, remember?) and it just
   so happens that we have two viable candidates, first one at offset
   0x02 and one at 0x1A. The first one is off by two, so it's a little
   less likely to be the one we want. Too little to go on, but we also
   know where the newsgroup table starts: 0x65AAE. Wouldn't you know,
   there it is at offset 0x24 of the header. Now, let's see if we can
   find any lengths in there. We begin by measuring the size of the
   newsgroup table. It runs from 0x65AAE to the end of the file at
   0x68065. Subtract and you get 0x25B8, and there it is in the header,
   following the offset. We can then verify our findings by checking them
   against the record of the table starting at 0x2C.
   Now we have a little more to work with, so we try and determine the
   size and the location of the first of the headers table-records. We
   know that one of the table entries end at 0x23 at the latest, because
   that is where we have our offset to the newsgroups table. We can also
   be sure that offsets 0x1E through 0x21 belong to the other table,
   because those bytes contain the length of the first table (whose
   contents are so far unknown). That leaves only two bytes between them.
   Implicit in this is a limit to the size of a record, because we know
   that the newsgroup entry ends at 0x2B at the latest, so it can run
   from 0x22 through 0x2B ( ten bytes) or 0x24 though 0x2B (eight bytes).
   And therein lies the answer to the question of the record's length,
   because we can see that the newsgroup record ends with the length
   field, and for that to hold the other record should too, which would
   orphan the two bytes between them. In this way we can come to know
   that a record is in fact ten bytes, consisting of two bytes (meaning
   unknown), a longword (table offset) and a longword (table length).
   Working backwards we can fill out the entries as this:

 0x004E, 0x0065AAE, 0x000025B8
 0x0041, 0x000002C, 0x000034CC
 0x0049, 0x00034F8, 0x000625B6


#  distributed via <nettime>: no commercial use without permission
#  <nettime> is a moderated mailing list for net criticism,
#  collaborative text filtering and cultural politics of the nets
#  more info: and "info nettime-l" in the msg body
#  archive: contact: