Finding Collisions in the Full SHA-1

Finding Collisions in the Full SHA-1
Xiaoyun Wang, Yiqun Lisa Yin, and Hongbo Yu

Discovered on: http://www.schneier.com/blog/

IBM's Billy Goat worm detection system

Lessons Learned from Billy Goat, an Accurate Worm-Detection System

This paper describes some of the lessons, insights and constructions stemming from the creation, deployment, and operation of the Billy Goat worm detection system. The most important feature of Billy Goat is its reliability in terms of accuracy, resilience and rapidity in detection and identification of worms without false positives. It is widely deployed throughout IBM and several other corporate networks. We discuss the features and requirements of worm detection systems in general, and how they are addressed by Billy Goat. We also describe some experiences and findings from our deployments of the system.

By: James Riordan; Diego Zamboni; Yann Duponchel

Published in: RZ3609 in 2005

Data clustering: a review

i'm just making up for a lack of posts here ... another good paper to read if you do any large scale data analysis and pattern recognition. i like this paper because it's a meaty, lengthy review and anyone can learn a boatload of useful material from it. highly recommended reading.

This paper presents an overview of pattern clustering methods from a statistical pattern recognition perspective, with a goal of providing useful advice and references to fundamental concepts accessible to the broad community of clustering practitioners. We present a taxonomy of clustering techniques, and identify cross-cutting themes and recent advances. We also describe some important applications of clustering algorithms such as image segmentation, object recognition, and information...

Source: Data clustering: a review, ACM Computing Surveys, Vol. 31, No. 3. (1999), pp. 264-323. Available for free.

CLUSTAL W: improving the sensitivity of progressive multiple sequence alignment ...

similar to the BLAST paper i posted some time ago, CLUSTAL W is a valuable tool and a great way to think about string matching.

The sensitivity of the commonly used progressive multiple sequence alignment method has been greatly improved for the alignment of divergent protein sequences. Firstly, individual weights are assigned to each sequence in a partial alignment in order to down-weight near-duplicate sequences and up-weight the most divergent ones. Secondly, amino acid substitution matrices are varied at different alignment stages according to the divergence of the sequences to be aligned. Thirdly, residue-specific gap penalties and locally reduced gap penalties in hydrophilic regions encourage new gaps in potential loop regions rather than regular secondary structure. Fourthly, positions in early alignments where gaps have been opened receive locally reduced gap penalties to encourage the opening up of new gaps at these positions. These modifications are incorporated into a new program, CLUSTAL W which is freely available.

Source: CLUSTAL W: improving the sensitivity of progressive multiple sequence alignment through sequence weighting, position-specific gap penalties and weight matrix choice. originallt published in Nucleic Acids Res, Vol. 22, No. 22. (11 November 1994), pp. 4673-4680. you can get it for free using the link above.

while this works well for things with obvious, formal structures and functions, it is difficult to achieve for arbitrary text and letters. still, i think that once you get beyond the definite match/no match mentality, regular expressions suddenly lose their appeal.

Windows Kernel Internals Process Architecture

"Windows Kernel Internals Process Architecture" PDF of PPT slides by David B. Probert, Ph.D; Windows Kernel Development, Microsoft Corporation.

http://www.i.u-tokyo.ac.jp/ss/lecture/new-documents/Lectures/13-Processes/Processes.pdf

This is specific to process & thread initialization and termination and goes into, while not ultra-specific, more of the gory details than most Windows internals books on this subject. In all honesty, I don't have the apropos character set installed, so I am not sure what version of Windows it is really meant to describe. I do, however, believe that while some ultra-specific data might change, much of the discussed is true today (with the exception of XP not calling static TLS initializers upon process startup -- IIRC, XP does not do that; it will call the initializers at thread creation/termination time and process termination time). It's pretty useful for RevEng'ing ntdll.dll.

The below link provides more PDF/PPT slides from this author on Windows internals and might be useful, but I have not really looked through them.

http://www.i.u-tokyo.ac.jp/ss/lecture/

Analyzing Memory Accesses in x86 Executables

i just had a look at a related paper to this one, but the abstract below is from a more general paper on the subject. if malware analysis interests you, this is probably worth a look.

This paper concerns static-analysis algorithms for analyzing x86 executables. The aim of the work is to recover intermediate representations that are similar to those that can be created for a program written in a high-level language. Our goal is to perform this task for programs such as plugins, mobile code, worms, and virus-infected code. For such programs, symbol-table and debugging information is either entirely absent, or cannot be relied upon if present; hence, the technique described in the paper makes no use of symboltable/debugging information. Instead, an analysis is carried out to recover information about the contents of memory locations and how they are manipulated by the executable.

Source: Analyzing Memory Accesses in x86 Executables, Gogul Balakrishnan and Thomas Reps.

w00w00 campathon

hello,we is planning a campathon (weekend camping trip) for the middle of august 2005in the stanislas national forest in california.http://www.fs.fed.us/r5/stanislaus/ pure eliteness.anyhow, anyone interested in such an event please let me know when you might possibly be available to do such a thing during the mid-august time frame.if you are not familiar with camping, pls refer to http://en.wikipedia.org/wiki/Camping

aempirei@the-mathclub.net

Minesweeper NP-complete (and more)

Yes, someone sat down and spent the time to figure out that some properties of playing minesweeper well are NP-complete:
http://web.mat.bham.ac.uk/R.W.Kaye/minesw/minesw.pdf

The reduction is pretty amusing, he shows that configurations of minesweeper act like logic gates and wires and gives a construction for building arbitrary logic systems out of minesweeper configurations, reducing the satisfiability of boolean expressions to solving problems in minesweeper.

There's also some more information in:
http://web.mat.bham.ac.uk/R.W.Kaye/minesw/ordmsw.htm
http://web.mat.bham.ac.uk/R.W.Kaye/minesw/ASE2003.pdf
http://web.mat.bham.ac.uk/R.W.Kaye/minesw/minesw.htm

The author goes further and describes how an infinite variation of minesweeper is Turing-complete in a paper linked from the last page. Kind of makes you evaluate what you're doing with your free time.

Another Google Paper

Here they're doing analysis on large sets of data distributed across many machines:
http://labs.google.com/papers/sawzall.html

The abstract describes it much better than I could, so I wont bother trying.

Two Papers

Here are two I ran across today. The first is a paper to be presented at usenix about protecting against exploits. I'm not sure how I feel about it. It seems rather hack-ish to me, but I havent been able to poke any major holes in the concept:
http://www.cs.arizona.edu/people/debray/papers/injection-attacks.ps

Two thoughts I had reguarding this paper are 1) it may be exponential to determine wether an instruction traps, but forcing it to trap is easy. It may be possible to use this fact to discover hidden system call traps. 2) They suggest modifying binaries to obfuscate them, however if they want to do this without losing the benefits of shared libraries, all binaries sharing the same library will have to share the same modifications. This means one binary may leak information about another. An attacker can use an information leak in one program to construct an exploit for a second program.

The second paper is about virtual machines and a technical called pre-virtualization. The idea is to use binary transformation of select parts of a system to get the effects of paravirtualization (ie. xen) without requiring modifications to the operating system source:
http://l4ka.org/projects/virtualization/afterburn/whitepaper.pdf