These are tools that let one run a process and, in a sense, selectively debug by telling the tool to perform analysis when conditions are met in the kernel, such as when a certain argument is sent to sendto() one could replace it on the stack with their own value. You could write your own version of functions and hijack them with with LD_PRELOAD but being able to script instead of compile is significantly better for debugging.

There are several frameworks for such debugging available. �DTrace with RE:Trace (osx, sun), SystemTap on linux and vtrace for win32+linux, all scriptable.� My favorate as yet is Subterfugue though old its keep-it-simple-stupid methods have kept me coming back. Here is an example that changes the argument passed to a write() into rot13 ascii:

trans = string.maketrans(abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ,
                         nopqrstuvwxyzabcdefghijklmNOPQRSTUVWXYZABCDEFGHIJKLM)

class Rot13(Trick):
    def callbefore(self, pid, call, args):
        m = getMemory(pid)
        address = args[1]
        size = args[2]
        data = m.peek(address, size)
        m.poke(address, string.translate(data, trans), self)

    def callmask(self):
        return { write : 1 }

And the output:

bash-2.03$ sf --tri=Rot13 date
Jrq Sro  2 02:55:34 PFG 2000
bash-2.03$ sf --tri=Rot13 --tri=Rot13 date
Wed Feb  2 02:55:37 CST 200

So because Im too lazy to make a CVS commit, ill explain how you can revive it yourself. Hey! Really this is better. Its future proof: You wont have to worry about the software dieing if I go off to work at some draconian anti-opensource company just like all the other wonderful security engineers out there (Im looking at you Boomerang Decompiler). You wont have to worry because… within the next 5 minutes youll know how to maintain it yourself, kinda.

1. Downgrade python:
   download and install python 1.5.2. You could try your luck with later versions but the object c methods are different and subterfugue needs these for heavy use of ptrace() hooking. Lets race to see who recodes them first. Anyway, whatever version to try be sure you have the Makefile.pre.in from the python install sources.
2. Update system call map:
   grab the strace sources. The system call map that subterfugue is using is dated from 2001 or so and needs to be updated for newer kernels. compare the syscallmap.py in subterfugue to the syscallent.h of strace. From about array index 250+ is where the new entries start. To add them I just cut and paste to a new file, ran a replace routine for line in f.readlines(): print line.translate(string.maketrans(’{}/*’,()##’)). Also needed to be sure there there was no more than one flag in each array.
3. make install and then test with a trick from /usr/lib/subterfugue/tricks/: sf –tri=Count date

If time permits I would like to rewrite the ptrace c shell using python 2+ methods. Until then, this works.

Update: added seperate feeds for updated and new-only articles

One of the resources I use to monitor for current cryptography papers is the Cryptology ePrint Archive, a routinely updated repository of all cryptography papers. Recently the Archive setup their own RSS feeds. Their feed provides a link to the article summaries. For me this isn’t enough and for a while I’ve had my own bot building an RSS feed listing the latest additions to the archive including their full summary inside the feed itself, not just a link to it. It was too buggy to link publicly so last night I fixed what should be the last of the problems to providing a stable feed. I have a feed for just newly published articles and another for all articles new or updated.�

By Nathan Fain

Incomplete: must create detailed diagram for compression functions.

The following simplifies the specification of SHA-1 in an easy to digest form. First we will cover the general structure of the algorithm. Detail of the expansion and compression routines are covered separately.

First we start with a message. The message is padded and the length of the message is added to the end. It is then split into blocks of 512 bits (Figure 2).

(Figure 2)

The blocks are then processed one at a time. Each block must be expanded and compressed. The value after each compression is added to a 160bit buffer called the current hash state. After the last block is processed the current hash state is returned as the final hash. A overview of this procedure can be seen in Figure 3.

(Figure 3)

Let’s look more closely at the expansion and compression functions. For expansion each 512 bit message block is separated into chunks of 32 bits. As you can see in Figure 3 these 16 chunks are then used to create 64 more chunks for a total of 80. Details of how this is done are described later.

(Figure 4)

Now all 80 of these chunks are compressed into a 160 bit value which is added to the current hash state (Figure 5):

(Figure 5)

Figure 5 shows one block being processed. The expansion and compression functions are repeated for each block with the return constantly being added to the current hash state buffer. Once all blocks have been processed it is this value that is returned as the hash of the message.

3 tasks were generalized above: How the message is prepared before processing, how exactly the block is expanded to 80 chunks (Figure 4) and how those chunks are compressed (Figure 5). It is not essential to understand them in detail but should you desire, here are the details.

Message Preparation

The message is prepared in 4 steps:

1. Append a single binary 1 bit to the message
2. Split into blocks of 512 bits each (Figure 2 above)
3. The last block must be equal to 448 so that we can append the message length (next step). If it is under pad with binary 0 bits until equal to 448. If over, pad until it is 512 bits and create an additional block of 448 binary 0 bits.
4. Append the length of the original message to the last block. Represent this length as a 64 bit integer (making the last block equal to 512 bits).

I should also mention that before we process any blocks we must initiate the hash state buffer. The buffer is actually 5 separate 32 bit integers:

• h0 = 67452301
• h1 = EFCDAB89
• h2 = 98BADCFE
• h3 = 10325476
• h4 = C3D2E1F0

Block expansion
Each 512 bit block is split further into 32 bit chunks (”words“) as seen in Figure 4. These 16 chunks are then expanded to a total of 80. The processes of expansion is a simple XOR of 4 values. For instance, the next chunk, chunk 17, is created by XOR’ing together chunk 17-3, 17-8, 17-14 and 17-16. For chunk 18 run the same processes but subtracting from 18 instead of 17. This continues until all 80 have been created. This can clearly be seen in the animation to the right. (If the animation is not playing reload the page.)

Block compression

This work is licensed under a Creative Commons Public Domain License and may be used however you wish.� For sources to Dia based diagrams, contact me.

An Illustrated Guide to Cryptographic Hashes
by Steve Friedl
15 pages of text

Update 2006.02.11: clearer explanation of CTFP preimage resistance.

This is a very good introduction to what a hash algorithm is, what it is for and what collisions are all about. It does not cover specific details, only the general understanding. It’s a quick read so I’ll forgo summarizing the contents.

The article explains the common terms used in most papers that discuss collisions. These terms are used to classify the type of collision attacks possible and are necessary to understand when reading other papers:

• Collision resistance measures how difficult it is to create two inputs which produce any hash value which is the same for both inputs. In this scenario the attacker can control both inputs.
• Preimage resistance measures how difficult it is to create one input which matches the hash value of an unknown input. Here the attacker does not know the other input and is restricted by needing to create a specific hash value.
• Second preimage resistance measures how difficult it is to create one input which matches the hash value of a known input. Here the attacker can see both inputs but only controls one. Attacker is still restricted by having to create an input which matches the specific hash value of the other. However, knowing the input that produced the hash might be of assistance.

Both preimage and second preimage are similar in that the objective is to get one input to match a predefined hash which is not controlled by the attacker. Also, in the Herding Hash Functions by John Kelsey and Tadayoshi Kohno they that there is a 4rth resistance value:

• Chosen Target Forced Prefix preimage resistance measures how difficult it is to create a collision when the first input is known while the second input is not know yet. This is similar to preimage resistance except that here the attacker controls the first input and not the second. Well, almost. The attacker is permitted to append data to the second input. The attacker must determine the hash first using the first input and then “herd” the second input to the same hash. Herding is done by adding data to the second input to make it collide. Is a process that involves carefully predetermining the first input and using internal states from its hash generation in the appended data to the second.