Stupid Compiler

DFLY: syscall frequency

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.

#include
#include

#include
#include
#include
#include

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");
process_ktrace_log(logf);
fclose(logf);

return 0;
}

static void process_ktrace_log(FILE *logf) {
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");

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 +
tv_curr.tv_usec,
ktrsc->ktr_code);
syscalls[ktrsc->ktr_code]++;
}
break;
case KTR_CSW:
{
struct ktr_csw *ktrcsw = (struct ktr_csw *)m;
}
break;
default:
break;
}
}

fclose(logsc);
fclose(logcsw);

{
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]);
}

fclose(schistlog);
}
}


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):

#!/usr/pkg/bin/python2.4

import sys
import re

sc = open("/usr/include/sys/syscall.h")
scdict = {}
mo = re.match("^#define\s+SYS_(\S+)\s+(\d+)\s*$", line) if mo is not None: scdict[mo.group(2)] = mo.group(1) sc.close() dpair_re = re.compile("^\s*(\d+) (\d+)$")
mo = dpair_re.match(line)
if mo is not None:
print '%15s %3s %s' % (mo.group(2), mo.group(1), scdict[mo.group(1)])


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

And the top 15 are: (full results)

        1047837 197 mmap
828677   5 open
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?

"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 sha_exp_rev.py that compute valid error
vectors.

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-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
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.

 is computed as:

1. Divide the 512-bit message block, M, into 16 32-bit words .
2. Expand the 16 words into 80 words using the expansion function defined by the recurrence relation:

3. Initialize the state variables, , using 
4. For each word in W, , compute the new state as:

The function  is defined below.
5. The output is given as:

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