Stupid Compiler

Notes on things about stuff

Archive for the ‘Uncategorized’ Category

Understanding the PDF format: DRM and Wookies

with one comment

Recently, my friend Dave and I were talking about the Adobe PDF DRM mechanism for eBooks. He was one of many people I’ve talked to who have bought an Adobe eBook without realizing it included DRM sludge. You can’t move it around (easily) or copy excerpts or print any of it. The discussion got me thinking about how Adobe went about their DRM system. I work for a company that does the equivalent for satellite cable systems and these things interest me once in a while. I went to Google and researched Adobes system.

In the end I decided to just take a look at the eBooks I own to see how the DRM mechanism fits with the PDF format. I downloaded the latest free PDF specification and opened up the PDF in vim to follow along. It seems the eBook I was looking at was using a version of the EBX system. After digesting some of that specification, I found a nice (if somewhat old) presentation outlining some reversing done on the various eBook protections. The comments about the passwords protections seem bit out of date, so I’m not sure how accurate this still is. In the end, I got completely distracted by the huge number of features implemented by Adobe. A whole JS engine? embedded Postscript support too? I thought it must be hard to have any confidence in the security of such a sprawling system. Less than a week later, there was a security advisory (some vulns provided remote code execution).

Anyway, I realized (or strongly suspected) that I needed a tcpdump of the eBook buying experience to make any more progress and put the eBook DRM circumvention (for academics! honest) on hold. I decided to play with the PDF format instead. My first exercise was adding a wookie sound (which turned into R2D2 due to lack of good internet accessible wookie sounds) to my (OLD!)resume (obviously something all employers want when opening a PDF document). It will play when opened by Adobe Reader (does anyone know if it works on Preview for OS X?). Adding this was fairly easy; PDFs can be modified by simply appending the modifications to the end of the file. Let’s walk through the robotification of my PDF.

PDF documents are specified by a list of PDF objects, followed by a lookup table giving the byte offsets for each object. These objects are one of: number, array, dictionary, boolean, null, string, stream, name, or indirect reference. You can see the PDF spec for full details, but most are exactly what you imagine. An array is written as “[ obj1 obj2 obj3 … objn ]”. Names are written “/name” and act as identifiers. A dictionary is written “<>” and maps names to objects. A stream is written “dict stream EOL bytes EOL endstream” and is a chunk of data which is not limited (as strings are) to a smaller length. An indirect reference is like a pointer to an identifiable object (an indirect object, which is given a unique pair of id numbers). To modify an existing PDF, you can add another list of objects (which, if the same identifier is used, override previous definitions of objects) and corresponding lookup table.

The PDF format also includes a dictionary after the lookup table. This dictionary includes a reference to the root object of the object tree. The root object is a dictionary containing the key Type of value Catalog. The Catalog object must also contain a entry for the Pages object (usually an indirect reference), but it has many other optional keys. We want to add an event that takes place when the document opens; the Catalog provides a key (OpenAction) we can define for this event. That is the first step.

We will lookup the current Catalog object:

53 0 obj <> endobj

So, starting at the end of the “victim” PDF, we append the new Catalog entry:

53 0 obj <> endobj

I chose to add the event as an indirect reference to object 55 (of generation 0). The number was chosen by looking at the trailer dictionary at the end of the PDF. The Size entry contains the highest unused object number — which was 55 for my document.

Now we must define our action. For this example, I decided to play a sound, but looking at the PDF spec, section 12.6.4 lists a bunch of action types. An action is a dictionary with the Type set to Action. It must contain an S entry giving the action type. For us, that is Sound. A Sound Action also requires a Sound entry giving a Sound object. Let’s add the Sound Action first:

55 0 obj <> endobj

The last object we must add is the actual Sound object. The Sound object is a stream. The stream dictionary (in addition to the usual stream dictionary entries such as Filter and Length) has the Type set to Sound. It is also required to set the Rate (R) — given in samples per second. Optionally, if the sound is not a 8-bit mono sample, bits per sample (B) and channels (C) can be set. Also, the encoding (E) can be set — see the specification for details (you can also just embed a whole WAV or AIFF file). The R2D2 sample was given as:

56 0 obj <>

I left out the 60k hexdump of raw samples. I had a really simple python script to convert from WAV to this, but I can’t find it now, sorry.

Now that all the new objects have been appended, we can write the crossref table and the trailer:

0 1
0000000000 65535 f
53 1
0000069494 00000 n
55 2
0000069564 00000 n
0000069624 00000 n

The xref table is a fixed format to allow quick and easy access for the PDF viewer. It contains a list of entries. Each entry begins with a line specifying the object to start at and the number of objects given. This is followed by a line for each object. The line contains two numbers: the byte offset of the start of that object and the generation of the object. Generations come into play when updates to a PDF delete an object. For us, all our objects are of generation 0. Also, object 0 is always of generation 65535 and is used when keeping the list of deleted object numbers available for reuse. The line must be of a strict format: the ten digit zero padded decimal number specifying the byte offset for the current object, a single space, the 5 digit zero padded decimal generation, a single space, a single character (‘n’ for regular object or ‘f’ for a freed object), and a 2 char end of line sequence (space + carriage return, space + line feed, or CR + LF).

After the xref table, the trailer dictionary is written. The trailer dictionary contains the Root reference, the new Size entry (our highest object was 56, so the Size is 57), and the byte offset to the last xref table (prior to this one — it will be given in the startxref near the end of the original file).

Finally, the startxref is given. startxref on a line by itself, then the byte offset of the new xref table in decimal on a line by itself.

Really finally, the ‘%%EOF’ comment ends the file.

Note: I did this with vim and while it wasn’t too bad, manually adding the byte offsets required by the PDF format was a bit error prone. I ended up writing a Python script to build PDFs to do some further experiments, but I didn’t add any parsing to do modification of existing PDFs. I know these things exist, but it was worth it to work it out myself.

After the first experiment, I wanted to bounce a ball around the PDF. Adobe provides Javascript! My bouncing ball worked great in older version of Adobe Reader, but a new security policy put the kibosh on my enthusiasm — I didn’t want to buy the full version of Adobe. I can’t find a way to enable modification of a document without having Adobe sign the PDF with their key. I may be reading the spec wrong, but it appears the default is to restrict modification by default and not allow any 3rd parties from generating annotatable documents. If anyone can show me how to do so, I’d love to know.

I was going to talk about breaking PathWords on Facebook to give a friend 6200 points. That will have to be next time. The length got away from me.

Other things: I’m reading “Ynot: Reasoning with the Awkward Squad” and I like the writing style. It is surprising to grok this stuff without too much trouble. I’d like to chalk that up to having more experience, but I think it’s just the clarity of the writing. I spent some time on the 0x41414141 reversing challenge. It was fun — I hope they add more. I encourage anyone looking for a job to take a crack at it.

TODO: Clean up the rest of this site (markup and finish the SHA notes). Write up the PathWords experience. Write up my experiences reversing the SNES version of “Zelda: A Link to the Past”.

Written by dionthegod

November 17, 2008 at 5:30 am

Posted in Uncategorized

Twelf Resources

leave a comment »

I’ve always been interested in computer assisted proof systems. Over the last year (or 2), I’ve been reading more and more on proving interesting properties of programs. I began with the very recent papers on security and safety properties of micro kernels (Gerwin Klein and Michael Norrish). From the NICTA work, I ended up working through much of the Isabelle proof system tutorials. The syntax of Isabelle felt very natural. Next, I read some of the French work (Xavier Leroy et al.) on formally verifying compilers. This led me to Coq and Benjamin Pierce’s exercises he has posted on his website. I’ve worked through a good 67% of those. Coq feels very pragmatic and the bundled environment is great to get started quick. Then, I took a few months break to look at a bunch of security stuff (static analysis work from Dawson Engler and the rest).

When I came back to it, I started reading the book Robert Harper is working on “Practical Foundations for Programming Languages”. This is dense (for me at least) and I’ve found myself having a hard time making too much progress. I think it would help to have an instructor, but in absence of that I have been taking large breaks in between chapters to decompress and let it marinate in my brain. My problem is remembering the vocabulary and notation each time, but after a day or two it comes back to me.

In any case, I came back to the work surrounding POPLMark and this led me to Twelf. I’ve been accumulating resources and wanted to put them all together for my own benefit. Maybe it will help someone else, but I think the Twelf wiki has a better selection — I’m just trying to keep track of what I have found and worked through.

Written by dionthegod

August 9, 2008 at 6:00 pm

Posted in Uncategorized

Installing SMLNJ on Cygwin

leave a comment »

Today, I spent a few hours trying to figure out why my SMLNJ install kept failing. For the benefit of others who may have run into this problem, I’m going to record my solution (which I haven’t seen anywhere).

Issue 1:
I had a native Win32 install of SMLNJ at some point and my first failure looks like:

$ ./config/
//fs01/Home/dblazakis/projects/smlnj/bin/.link-sml: line 45: c:smlnj/bin/.arch-n-opsys: No such file or directory

Notice the native windows path — once I saw that I remembered I had SMLNJ_HOME set. So, from bash, ‘unset SMLNJ_HOME’.

Issue 2:
With that out of the way, I figured I was golden… but I was wrong. The next error:

$ ./config/
./config/ CM metadata directory name is ".cm"
exception raised during init phase: SysErr: No such file or directory [noent]
//fs01/Home/dblazakis/projects/smlnj/bin/.run/run.x86-cygwin: Fatal error -- Uncaught exception SysErr with <unknown> raised at <stat.c>
./config/ !!! Boot code failed, no heap image (sml.x86-cygwin).

This one is more troublesome. First thought is that it is a path issue, so I add a few echos to the install script and everything looks correct to me. Next, I add a strace to the call in the install script which is failing (a call to generate the initial heap image containing the preloaded modules). This generates a ton of output even after masking to output only syscalls. Sifting through it, it appears the first open or stat call after reading the PIDMAP uses a single ‘/’ instead of the usual double ‘/’ to denote a network share.

340 27275136 [main] run.x86-cygwin 2956 normalize_posix_path: src /fs01/Home/dblazakis/projects/smlnj/sml.boot.x86-unix/smlnj/init

Poor cygwin — it tries so hard. This appears to be a bug in the SMLNJ SrcPath module (cm/paths/srcpath.sml), but this is the first time I’ve waded through the SMLNJ code.

Long story short, I decided to move my build to a local directory (instead of a network share) and it worked on the first try.

Written by dionthegod

August 8, 2008 at 10:28 pm

Posted in Uncategorized

DFLY: syscall frequency

with 2 comments

What does the syscall traffic look like for a “make buildkernel”?

% ktrace -di -f /home/dion/projects/syscall-hist/trace1.ktlog -t c make buildkernel
% ktrace -di -f /home/dion/projects/syscall-hist/trace2-cw.ktlog -t cw make buildkernel

Then, I used this “thing” to chew the log files and spit out a nicer form. This code is pretty loosely based on the source to kdump.



static void process_ktrace_log(FILE *logf);

uint64_t syscalls[512] = { 0 };

int main(int argc, char *argv[]) {
    FILE *logf;

    logf = fopen(argv[1], "r");

    return 0;

static void process_ktrace_log(FILE *logf) {
    struct ktr_header ktrhdr;
    struct timeval tv_curr, tv_first, *tvp_first = NULL;
    int ktrlen;
    char *m = NULL;
    int m_size = 0;

    FILE *logsc = fopen("sc.log", "w");
    FILE *logcsw = fopen("csw.log", "w");

    while (fread(&ktrhdr, sizeof(struct ktr_header), 1, logf) == 1) {
        if ((ktrlen = ktrhdr.ktr_len)  m_size) {
            m = (void *)realloc(m, ktrlen+1);
            if (m == NULL)
                errx(1, "%s", strerror(ENOMEM));
            m_size = ktrlen;

        if (ktrlen && fread(m, ktrlen, 1, logf) == 0)
            errx(1, "data too short");

        if (!tvp_first) {
            tv_first = ktrhdr.ktr_time;
            tvp_first = &tv_first;

        timersub(&ktrhdr.ktr_time, tvp_first, &tv_curr);

        switch (ktrhdr.ktr_type) {
            case KTR_SYSCALL:
                    struct ktr_syscall *ktrsc = (struct ktr_syscall *)m;
                    fprintf(logsc, "%16lld %d\n",
                            (uint64_t) tv_curr.tv_sec * 1000000L +
            case KTR_CSW:
                    struct ktr_csw *ktrcsw = (struct ktr_csw *)m;


        FILE *schistlog = fopen("schist.log", "w");
        int i;

        for(i = 0; i < 512; i++) {
            if (syscalls[i]) fprintf(schistlog, "%d %lld\n", i, syscalls[i]);


Then I used this gnuplot input to generate a quick plot:

set terminal png
set output 'schist-1m.png'
set xrange [0:60000000]
plot "sc.log" using 1:2 with dots

Finally, I used this little python script (I’m guessing some awk/sed genius could do it on the command line, but I can’t):


import sys
import re

sc = open("/usr/include/sys/syscall.h")
scdict = {}
for line in sc.readlines():
    mo = re.match("^#define\s+SYS_(\S+)\s+(\d+)\s*$", line)
    if mo is not None:
        scdict[] =

dpair_re = re.compile("^\s*(\d+) (\d+)$")
for line in sys.stdin.readlines():
    mo = dpair_re.match(line)
    if mo is not None:
        print '%15s %3s %s' % (,, scdict[])

Then I sorted it on the command line:
% ./ schist-chew.log

And the top 15 are: (full results)

        1047837 197 mmap
         828677   5 open
         412613   3 read
         355321   6 close
         343725 476 fstat
         287935  73 munmap
         278365 475 stat
         114136   4 write
         108059 342 sigaction
          88929 199 lseek
          64747 477 lstat
          42090  92 fcntl
          40985 472 set_tls_area
          29434 253 issetugid
          27946  59 execve

[EDIT] Added the graph and final results.

Written by dionthegod

April 29, 2008 at 9:47 pm

Posted in Uncategorized

[SHA, Right] What's Joux Talkin' Bout?

leave a comment »

"Differential Collisions in SHA-0"

Chabaud & Joux begin by attacking a weakened SHA-0 variation.  The first version, which
they call SHI1, is equivalent to SHA-0 with the addition operations in A_{i+1} replaced
with XORs and the f_i functions replaced by XOR.  This effectively removes the
non-linearity introduced by the f_i function and the addition operations.

The analysis of SHI1 begins by examing the effect of perturbations of the vector
W_{i} (0 <= i < 80) directly (instead of trying to study the perturbations of the
message block, M or W_i (0 <= i = 75 "since a perturbation in
round i is never corrected before round i + 6, and since all perturbations must be
corrected by round 80."

The intuitive explanation of the process

Important observation:
* The expansion process does not interleave bits!  This turns it into a function
from 16 bits to 80 bits over each bit in the word.

1. Find valid perturbations -- these are deduced by ensuring they fit the expansion
recurrence relation.  It is important to see that since the compression functions
starts primed with some A - E, the recurrence must actually start at the 11th word
(5 steps [A-E] behind the 16th that the recurrence is defined at).

The search is brute force with a search space of 2^16.  It is simple.

We will call the chosen error vector e_{0}

TODO: Include the functions taken from that compute valid error

2. Now, derive the global differential mask (which is M in the paper -- M is also
the message block... bad naming).  The global differential mask is derived by fixing
the flips found in the previous step with the differential path described in the
prebvious section.  Since the SHI1 defines all combination function in the
compression function as XOR, we can XOR the differential paths for all the bits
flipped in e_{0} to compute up with the global mask.  We will call the global mask
G.  We only need the first 16 words of this mask since those will define the rest of
it (via the expansion function).

NOTE: Maybe worth pointing out that this will generate a valid W' because e_{0}
satisfies (9).

3. Given the global mask M and *any* input message M, SHI1(M) == SHI1(M \xor G).

Collision!  Hooray!  Wait.  That's just SHI1.  It's all linear.  We just solved an
algebra equation.  Oh.

Written by dionthegod

April 29, 2008 at 5:42 am

Posted in Uncategorized

[SHA, Right] The Algorithm

leave a comment »

SHA-0 (or something more clever here)

SHA-0 was specified in the first Secure Hash Standard (SHS) (current draft) issued in 1993. Two years later, NIST issued a small change to the SHA-0 expansion function; the new function is known as SHA-1. There was no justification for the updated function, but it is assumed the NSA found a collision attack.

Structure of the Hash Function

The SHA hash function works on blocks of 512 bits and outputs a hash value of 160 bits. The function proceeds as follows:

  1. Pad the message by adding a single 1 bit and then a string of 0 bits suffixed with the length (in bits) of the message without padding (represented as a 64-bit big endian integer). The number of zero bits is chosen as the minimum number to evenly pad the message to the next 512 bit boundary.
  2. The five state variables are initialized to fixed constants:
    A = 0x67452301
    B = 0xefcdab89
    C = 0x98badcfe
    D = 0x10325476
    E = 0xc3d2e1f0
  3. For each message block, call the compression function using the current state, A through E, and the current block. The compression function will return the new state. Pseudocode:
    state[i + 1] = compress(current_block, state[i])
  4. The output of the function is the concatentation of the state variables. Pseudocode:
    return A ++ B ++ C ++ D ++ E

The Compression Function

The compression function is where all the “good stuff” happens.

compress(M, h) is computed as:

  1. Divide the 512-bit message block, M, into 16 32-bit words W_0, W_1, \ldots, W_15.
  2. Expand the 16 words into 80 words using the expansion function defined by the recurrence relation:
    W_i = W_{i-3} \oplus W_{i-8} \oplus W_{i-14} \oplus W_{i-16}
  3. Initialize the state variables, A, B, C, D, E, using h
  4. For each word in W, W_i, compute the new state as:
    \begin{align*}A_{i+1} &= (W_i + A_i \lll 5 + f_i(B_i, C_i, D_i) + E_i + K_i) \mod 2^{32}\\B_{i+1} &= A_i\\C_{i+1} &= B_i \lll 30\\D_{i+1} &= C_i\\E_{i+1} &= D_i\end{align*}
    The function f_i(B,C,D) is defined below.
  5. The output is given as:
    (A_0 + A_80, B_0 + B_80, C_0 + C_80, D_0 + D_80, E_0 + E_80)
The function "f_i(X,Y,Z)" and "K_i" are defined as:
  If i is in the range:
    [ 0, 20)   "IF"   f_i = (X & Y) | (X & Z)             K_i = 0x5A827999
    [20, 39)   "XOR"  f_i = X ^ Y ^ Z                     K_i = 0x6ED9EBA1
    [40, 59)   "MAJ"  f_i = (X & Y) | (X & Z) | (Y & Z)   K_i = 0x8F1BBCDC
    [60, 79)   "XOR"  f_i = X ^ Y ^ Z                     K_i = 0xCA62C1D6

NOTE: Add a link to the python implementation.

Written by dionthegod

April 29, 2008 at 5:42 am

Posted in Uncategorized

[SHA, Right] Introduction: A French Guy, an Israeli Guy, and a Chinese Gal Walk into a Bar

leave a comment »

… and discuss how best to attack SHA.

I was talking with a math guy here about the requirement for SHA-384 in a product we are developing. I had heard that MD5 was “insecure” and not to be trusted for collision resistance, but I hadn’t heard anything about SHA-1. Despite hearing these claims around the internet, I’ve never investigated further. My co-worker mentioned that SHA-1 was also on the way out and NIST will probably issue something declaring the larger members of the SHA family (SHA-384 and SHA-512) to be the new standards (I’ve since learned that NIST has a call for proposals for new hash functions — in the same way they picked AES). Never having implemented a secure hash function, I was curious what was involved and where the “one-wayed-ness” came from. This investigation led me from doing a fast implementation of SHA-512 (and, almost by default, SHA-384) to the original paper on differential attacks on DES to a bunch of work by three groups hitting the SHA functions pretty hard. I feel like I should try and explain some of the attacks I’ve learned (along with source code) — they’re clever and not difficult to understand once digested.

Before I begin, here are some references for those following along at home. I’m sorry for the crappy links; I know Springer and ACM are useless for anyone outside of academia. I’ll have to upload local copies — these papers are surprisingly hard to find.

Written by dionthegod

March 12, 2008 at 9:17 pm

Posted in Uncategorized