Introducing the RubySec Field Guide

Vulnerabilities have been discovered in Ruby applications with the potential to affect vast swathes of the Internet and attract attackers to lucrative targets online.

These vulnerabilities take advantage of features and common idioms such as serialization and deserialization of data in the YAML format. Nearly all large, tested and trusted open-source Ruby projects contain some of these vulnerabilities.

Few developers are aware of the risks.

In our RubySec Field Guide, you’ll cover recent Ruby vulnerabilities classes and their root causes. You’ll see demonstrations and develop real-world exploits. You’ll study the patterns behind the vulnerabilities and develop software engineering strategies to avoid these vulnerabilities in your projects.

You Will Learn

  • The mechanics and root causes of past Rails vulnerabilities
  • Methods for mitigating the impact of deserialization flaws
  • Rootkit techniques for Rack-based applications via YAML deserialization
  • Mitigations techniques for YAML deserialization flaws
  • Defensive Ruby programming techniques
  • Advanced testing techniques and fuzzing with Mutant

We’ve structured this field guide so you can learn as quickly as you want, but if you have questions along the way, contact us. If there’s enough demand, we may even schedule an online lecture.

Now, to work.

-The Trail of Bits Team

Closing the Windows Gap

The security research community is full of grey beards that earned their stripes writing exploits against mail servers, domain controllers, and TCP/IP stacks. These researchers started writing exploits on platforms like Solaris, IRIX, and BSDi before moving on to Windows exploitation. Now they run companies, write policy, rant on twitter, and testify in front of congress. I’m not one of those people; my education in security started after Windows Vista and then expanded through Capture the Flag competitions when real-world research got harder. Security researchers entering the industry post-20101 learn almost exclusively via Capture the Flags competitions.

Occasionally, I’ll try to talk a grey beard into playing capture the flag. It’s like trying to explain Pokemon to adults. Normally such endeavors are an exercise in futility; however, on a rare occasion they’ll also get excited and agree to try it out! They then get frustrated and stuck on the same problems I do – it’s fantastic for my ego2.

“Ugh, it’s 90s shellcoding problems applied today.”
— muttered during DEFCON 22 CTF Quals

Following a particularly frustrating CTF we were discussing challenges and how there are very few Windows challenges despite Windows being such an important part of our industry. Only the Russian CTFs release Windows challenges; none of the large American CTFs do.

Much like Cold War-era politics, the Russian (CTFs) have edged out a Windows superiority, a Windows gap.

Projected magnitude of the Windows gap

Projected magnitude of the Windows gap

The Windows gap exists outside of CTF as well. Over the past few years the best Windows security research has come out of Russia3 and China. So, why are the Russians and Chinese so good at Windows? Well, because they actually use Windows…and for some reason western security researchers don’t.

Let’s close this Windows gap. Windows knowledge is important for our industry.

Helping the CTF community

If Capture the Flag competitions are how today’s greenhorns cut their teeth, we should have more Windows-based challenges and competitions. To facilitate this, Trail of Bits is releasing AppJailLauncher, a framework for making exploitable Windows challenges!

This man knows Windows and thinks you should too.

This man knows Windows and thinks you should too.

As a contest organizer, securing your infrastructure is the biggest priority and securing Windows services has always been a bit tricky until Windows 8 and the introduction of AppContainers. AppJailLauncher uses AppContainers to keep everything nice and secure from griefers. The repository includes everything you need to isolate a Windows TCP service from the rest of the operating system.

Additionally, we’re releasing the source code to greenhornd, a 2014 CSAW challenge I wrote to introduce people to Windows exploitation and the best debugger yet developed: WinDbg. The repository includes the binary as released, deployment directions, and a proof-of-vulnerability script.

We’re hoping to help drag the CTF community kicking and screaming into Windows expertise.

Windows Reactions

Releasing a Windows challenge last year at CSAW was very entertaining. There was plenty of complaining4:

<dwn> how is this windows challenge only 200 points omg
<dwn> making the vuln obvious doesn’t make windows exploitation any easier ;_;

<mserrano> RyanWithZombies: dude but its fuckin windows
<mserrano> even I don’t use windows anymore
<@RyanWithZombies> i warned you guys for months
<mserrano> also man windows too hard

<geohot> omg windows
<geohot> is so hard
<geohot> will do tomorrow
<geohot> i don’t have windows vm

<ebeip90> zomg a windows challenge
<ebeip90> <3
[ hours later ]
<ebeip90> remember that part a long time ago when I said “Oh yay, a Windows challenge”?

<ricky> Windows is hard
<miton> ^

Some praise:

<cai_> i liked your windows one btw :)

<MMavipc> RyanWithZombies pls more windows pwning/rce

<CTFBroforce> I was so confused I have never done a windows exploit
<CTFBroforce> this challenge is going to make me look into windows exploits
<CTFBroforce> I dont know how to write windows shell code

<spq> thx for the help and the force to exploit windows with shellcode for the first time :)

It even caused some arguments among competitors:

<clockish> dudes, shut up, windows is hard
<MMavipc> windows is easy
<MMavipc> linux is hard

We hope AppJailLauncher will be used to elicit more passionate responses over the next few years!

Footnotes
  1. Many of the most popular CTFs started in 2010 and 2011: Ghost in the Shellcode (2010), RuCTFe (2010), PlaidCTF (2011), Codegate (2011), PHDays (2011). Very few predate 2010.
  2. Much like watching geohot fail at format string exploitation during a LiveCTF broadcast: https://www.youtube.com/watch?v=td1KEUhlSuk
  3. Try searching for obscure Windows kernel symbols, you’ll end up on a Russian forum.
  4. The names have not been changed to shame the enablers.

Empire Hacking, a New Meetup in NYC

Today we are launching Empire Hacking, a bi-monthly meetup that focuses on pragmatic security research and new discoveries in attack and defense.

EmpireHacking_Poster_Final

It’s basically a security poetry jam

Empire Hacking is technical. We aim to bridge the gap between weekend projects and funded research. There won’t be any product pitches here. Come prepared with your best ideas.

Empire Hacking is exclusive. Talks are by invitation-only and are under Chatham House Rule. We will discuss ongoing research and internal projects you won’t hear about anywhere else.

Empire Hacking is engaging. Talk about subjects you find interesting, face to face, with a community of experts from across the industry.

Each meetup will consist of short talks from three expert speakers and run from 6-9pm at Trail of Bits HQ. Tentative schedule: Even months, on Patch Tuesday. Beverages and light food will be provided. Space is limited. Please apply on our Meetup page.

Our inaugural meetup will feature talks from Chris Rohlf, Dr. Byron Cook, and Nick DePetrillo on Tuesday, June 9th.

Offense at Scale

Chris will discuss the effects of scale on vulnerability research, fuzzing and real attack campaigns.

Chris Rohlf runs the penetration testing team at Yahoo in NYC. Before Yahoo he was the founder of Leaf Security Research, a highly-specialized security consultancy with expertise in vulnerability discovery, reversing and exploit development.

Automatically proving program termination (and more!)

Byron will discuss research advances that have led to practical tools for automatically proving program termination and related properties.

Dr. Byron Cook is professor of computer science at University College London.

Cellular Baseband Exploitation

Baseband exploitation has been a topic of interest for many, however, few have described the effort required to make such attacks practical. In this talk, we explore the challenges towards reliable, large-scale cellular baseband exploitation.

Nick DePetrillo is a principal security engineer at Trail of Bits with expertise in cellular hardware and infrastructure security.

Keep up with Empire Hacking by following us on Twitter. See you at a meetup!

 

The Foundation of 2015: 2014 in Review

We need to do more to protect ourselves. 2014 overflowed with front-page proof: Apple, Target, JPMorgan Chase. Et cetera. Et cetera.

The current, vulnerable status quo begs for radical change, an influx of talented people, and substantially better tools. As we look ahead to driving that change in 2015, we’re proud to highlight a selection of our 2014 accomplishments that will underpin that work.

1. Open-source framework to transform binaries to LLVM bitcode

Our framework for analyzing and transforming machine-code programs to LLVM bitcode became a new tool in the program analysis and reverse engineering communities. McSema connects the world of LLVM program analysis and manipulation tools to binary executables. Currently it supports the translation of semantics for x86 programs and supports subsets of integer arithmetic, floating point, and vector operations.

2. Shaped smarter public policy

The spate of national-scale computer security incidents spurred anxious conversation and action. To pre-empt poorly conceived laws from poorly informed lawmakers, we worked extensively with influential think tanks to help educate our policy makers on the finer points of computer security. The Center for a New American Security’s report “Surviving on a Diet of Poisoned Fruit” was just one result of this effort.

3. More opportunities for women

As part of our ongoing collaboration with NYU-Poly, Trail of Bits put its support behind the CSAW Program for High School Women and Career Discovery in Cyber Security Symposium. These events are intended to help guide talented and interested women into careers in computer security. We want to create an environment where women have the resources to contribute and excel in this industry.

4. Empirical data on secure development practices

In contrast with traditional security contests, Build-it, Break-it, Fix-it rewards secure software development under the same pressures that lead to bugs: tight deadlines, performance requirements, competition, and the allure of money. We were invited to share insights from the event at Microsoft’s Bluehat v14.

5. Three separate Cyber Fast Track projects

Under DARPA’s Program Manager Peiter ‘Mudge’ Zatko, we completed three distinct projects in the revolutionary Cyber Fast Track program: CodeReason, MAST, and PointsTo. Five of our employees went to the Pentagon to demonstrate our creations to select members of the Department of Defense. We’re happy to have participated and been recognized for our work. We’re now planning on giving back; CodeReason will be making an open-source release in 2015!

6. Taught machines to find Heartbleed

Heartbleed, the infamous OpenSSL vulnerability, went undetected for so long because it’s hard for static analyzers to detect. So, Andrew Ruef took on the challenge and wrote a checker for clang-analyzer that can find Heartbleed and other bugs like it automatically. We released the code for others to learn from.

7. A resource for students of computer security

One of the most fun and effective ways to learn computer security is by competing in Capture the Flag events. But many fledgling students don’t know where to get started. So we wrote the Capture the Flag Field Guide to help them get involved and encourage them to take the first steps down this career path.

8. The iCloud Hack spurs our two-factor authentication guide

Adding two-factor authentication is always a good idea. Just ask anyone whose account has been compromised. If you store any sensitive information with Google, Apple ID or Dropbox, you’ll want to know about our guide to adding an extra layer of protection to your accounts.

9. Accepted into DARPA’s Cyber Grand Challenge

The prize: $2 million. The challenge: Build a robot that can repair insecure software without human input. If successful, this program will have a profound impact on the way companies secure their data in the future. We were selected as one of seven funded teams to compete.

10. THREADS 2014: How to automate security

Our CEO Dan Guido chaired THREADS, a research and development conference that takes place at NYU-Poly’s Cyber Security Awareness Week (CSAW). This year’s theme focused on scaling security — ensuring that security is an integral and automated part of software development and deployment models. We believe that the success of automated security is essential to our ever more internetworked society and devices. See talks and slides from the event.

Looking ahead.

This year, we’re excited to develop and share more code, including: improvements to McSema (i.e. support for LLVM 3.5, lots more SSE and FPU instruction support, and a new control flow recovery module based on JakStab), a private videochat service, and an open-source release of CodeReason. We’re also excited about Ghost in the Shellcode (GitS) — a capture the flag competition at ShmooCon in Washington DC in January that three of our employees are involved in running. And don’t forget about DARPA’s Cyber Grand Challenge qualifying event in June.

For now, we hope you’ll connect with us on Twitter or subscribe to our newsletter.

Close Encounters with Symbolic Execution (Part 2)

This is part two of a two-part blog post that shows how to use KLEE with mcsema to symbolically execute Linux binaries (see the first post!). This part will cover how to build KLEE, mcsema, and provide a detailed example of using them to symbolically execute an existing binary. The binary we’ll be symbolically executing is an oracle for a maze with hidden walls, as promised in Part 1.

As a visual example, we’ll show how to get from an empty maze to a solved maze:

Maze (Before) Maze (After)

Building KLEE with LLVM 3.2 on Ubuntu 14.04

One of the hardest parts about using KLEE is building it. The official build instructions cover KLEE on LLVM 2.9 and LLVM 3.4 on amd64. To analyze mcsema generated bitcode, we will need to build KLEE for LLVM 3.2 on i386. This is an unsupported configuration for KLEE, but it still works very well.

We will be using the i386 version of Ubuntu 14.04. The 32-bit version of Ubuntu is required to build a 32-bit KLEE. Do not try adding -m32 to CFLAGS on a 64-bit version. It will take away hours of your time that you will never get back. Get the 32-bit Ubuntu. The exact instructions are described in great detail below. Be warned: building everything will take some time.

# These are instructions for how to build KLEE and mcsema. 
# These are a part of a blog post explaining how to use KLEE
# to symbolically execute closed source binaries.
 
# install the prerequisites
sudo apt-get install vim build-essential g++ curl python-minimal \
  git bison flex bc libcap-dev cmake libboost-dev \
  libboost-program-options-dev libboost-system-dev ncurses-dev nasm
 
# we assume everything KLEE related will live in ~/klee.
cd ~
mkdir klee
cd klee
 
# Get the LLVM and Clang source, extract both
wget http://llvm.org/releases/3.2/llvm-3.2.src.tar.gz
wget http://llvm.org/releases/3.2/clang-3.2.src.tar.gz
tar xzf llvm-3.2.src.tar.gz
tar xzf clang-3.2.src.tar.gz
 
# Move clang into the LLVM source tree:
mv clang-3.2.src llvm-3.2.src/tools/clang
 
# normally you would use cmake here, but today you HAVE to use autotools.
cd llvm-3.2.src
 
# For this example, we are only going to enable only the x86 target.
# Building will take a while. Go make some coffee, take a nap, etc.
./configure --enable-optimized --enable-assertions --enable-targets=x86
make
 
# add the resulting binaries to your $PATH (needed for later building steps)
export PATH=`pwd`/Release+Asserts/bin:$PATH
 
# Make sure you are using the correct clang when you execute clang — you may 
# have accidentally installed another clang that has priority in $PATH. Lets 
# verify the version, for sanity. Your output should match whats below.
# 
#$ clang --version
#clang version 3.2 (tags/RELEASE_32/final)
#Target: i386-pc-linux-gnu
#Thread model: posix
 
# Once clang is built, its time to built STP and uClibc for KLEE.
cd ~/klee
git clone https://github.com/stp/stp.git
 
# Use CMake to build STP. Compared to LLVM and clang,
# the build time of STP will feel like an instant.
cd stp
mkdir build && cd build
cmake -G 'Unix Makefiles' -DCMAKE_BUILD_TYPE=Release ..
make
 
# After STP builds, lets set ulimit for STP and KLEE:
ulimit -s unlimited
 
# Build uclibc for KLEE
cd ../..
git clone --depth 1 --branch klee_0_9_29 https://github.com/klee/klee-uclibc.git
cd klee-uclibc
./configure -l --enable-release
make
cd ..
 
# It’s time for KLEE itself. KLEE is updated fairly often and we are 
# building on an unsupported configuration. These instructions may not 
# work for future versions of KLEE. These examples were tested with 
# commit 10b800db2c0639399ca2bdc041959519c54f89e5.
git clone https://github.com/klee/klee.git
 
# Proper configuration of KLEE with LLVM 3.2 requires this long voodoo command
cd klee
./configure --with-stp=`pwd`/../stp/build \
  --with-uclibc=`pwd`/../klee-uclibc \
  --with-llvm=`pwd`/../llvm-3.2.src \
  --with-llvmcc=`pwd`/../llvm-3.2.src/Release+Asserts/bin/clang \
  --with-llvmcxx=`pwd`/../llvm-3.2.src/Release+Asserts/bin/clang++ \
  --enable-posix-runtime
make
 
# KLEE comes with a set of tests to ensure the build works. 
# Before running the tests, libstp must be in the library path.
# Change $LD_LIBRARY_PATH to ensure linking against libstp works. 
# A lot of text will scroll by with a test summary at the end.
# Note that your results may be slightly different since the KLEE 
# project may have added or modified tests. The vast majority of 
# tests should pass. A few tests fail, but we’re building KLEE on 
# an unsupported configuration so some failure is expected.
export LD_LIBRARY_PATH=`pwd`/../stp/build/lib
make check
 
#These are the expected results:
#Expected Passes : 141
#Expected Failures : 1
#Unsupported Tests : 1
#Unexpected Failures: 11
 
# KLEE also has a set of unit tests so run those too, just to be sure. 
# All of the unit tests should pass!
make unittests
 
# Now we are ready for the second part: 
# using mcsema with KLEE to symbolically execute existing binaries.
 
# First, we need to clone and build the latest version of mcsema, which
# includes support for linked ELF binaries and comes the necessary
# samples to get started.
cd ~/klee
git clone https://github.com/trailofbits/mcsema.git
cd mcsema
git checkout v0.1.0
mkdir build && cd build
cmake -G "Unix Makefiles" -DCMAKE_BUILD_TYPE=Release ..
make
 
# Finally, make sure our environment is correct for future steps
export PATH=$PATH:~/klee/llvm-3.2.src/Release+Asserts/bin/
export PATH=$PATH:~/klee/klee/Release+Asserts/bin/
export LD_LIBRARY_PATH=$LD_LIBRARY_PATH:~/klee/stp/build/lib/

Translating the Maze Binary

The latest version of mcsema includes the maze program from Felipe’s blog in the examples as demo_maze. In the instructions below, we’ll compile the maze oracle to a 32-bit ELF binary and then convert the binary to LLVM bitcode via mcsema.

# Note: tests/demo_maze.sh completes these steps automatically
cd ~/klee/mcsema/mc-sema/tests
# Load our environment variables
source env.sh
# Compile the demo to a 32-bit ELF executable
${CC} -ggdb -m32 -o demo_maze demo_maze.c
# Recover the CFG using mcsema's bin_descend
${BIN_DESCEND_PATH}/bin_descend -d -func-map=maze_map.txt -i=demo_maze -entry-symbol=main
# Convert the CFG into LLVM bitcode via mcsema's cfg_to_bc
${CFG_TO_BC_PATH}/cfg_to_bc -i demo_maze.cfg -driver=mcsema_main,main,raw,return,C -o demo_maze.bc
# Optimize the bitcode
${LLVM_PATH}/opt -O3 -o demo_maze_opt.bc demo_maze.bc

We will use the optimized bitcode (demo_maze_opt.bc) generated by this step as input to KLEE. Now that everything is set up, let’s get to the fun part — finding all maze solutions with KLEE.

# create a working directory next to the other KLEE examples.
cd ~/klee/klee/examples
mkdir maze
cd maze
# copy the bitcode generated by mcsema into the working directory
cp ~/klee/mcsema/mc-sema/tests/demo_maze_opt.bc ./
# copy the register context (needed to build a drive to run the bitcode)
cp ~/klee/mcsema/mc-sema/common/RegisterState.h ./

Now that we have the maze oracle binary in LLVM bitcode, we need to tell KLEE which inputs are symbolic and when a maze is solved. To do this we will create a small driver that will intercept the read() and exit() system calls, mark input to read() as symbolic, and assert on exit(1), a successful maze solution.

To make the driver, create a file named maze_driver.c with contents from the this gist and use clang to compile the maze driver into bitcode. Every function in the driver is commented to help explain how it works. 

clang -I../../include/ -emit-llvm -c -o maze_driver.bc maze_driver.c

We now have two bitcode files: the translation of the maze program and a driver to start the program and mark inputs as symbolic. The two need to be combined into one bitcode file for use with KLEE. The two files can be combined using llvm-link. There will be a compatibility warning, which is safe to ignore in this case.

llvm-link demo_maze_opt.bc maze_driver.bc > maze_klee.bc

Running KLEE

Once we have the combined bitcode, let’s do some symbolic execution. Lots of output will scroll by, but we can see KLEE solving the maze and trying every state of the program. If you recall from the driver, we can recognize successful states because they will trigger an assert in KLEE. There are four solutions to the original maze, so let’s see how many we have. There should be 4 results — a good sign (note: your test numbers may be different):

klee --emit-all-errors -libc=uclibc maze_klee.bc
# Lots of things will scroll by
ls klee-last/*assert*
# For me, the output is:
# klee-last/test000178.assert.err  klee-last/test000315.assert.err
# klee-last/test000270.assert.err  klee-last/test000376.assert.err

Now let’s use a quick bash script to look at the outputs and see if they match the original results. The solutions identified by KLEE from the mcsema bitcode are:

  • sddwddddsddw
  • ssssddddwwaawwddddsddw
  • sddwddddssssddwwww
  • ssssddddwwaawwddddssssddwwww

… and they match the results from Felipe’s original blog post!

Conclusion

Symbolic execution is a powerful tool that can execute programs on all inputs at once. Using mcsema and KLEE, we can symbolically execute existing closed source binary programs. In this example, we found all solutions to a maze with hidden walls — starting from an opaque binary. KLEE and mcsema could do this while knowing nothing about mazes and without being tuned for string inputs.

This example is simple, but it shows what is possible: using mcsema we can apply the power of KLEE to closed source binaries. We could generate high code coverage tests for closed source binaries, or find security vulnerabilities in arbitrary binary applications.

Note: We’re looking for talented systems engineers to work on mcsema and related projects (contract and full-time). If you’re interested in being paid to work on or with mcsema, send us an email!

Close Encounters with Symbolic Execution

At THREADS 2014, I demonstrated a new capability of mcsema that enables the use of KLEE, a symbolic execution framework, on software available only in binary form. In the talk, I described how to use mcsema and KLEE to learn an unknown protocol defined in a binary that has never been seen before. In the example, we learned the series of steps required to navigate through a maze. Our competition in the DARPA Cyber Grand Challenge requires this capability — our “reasoning system” will have no prior knowledge and no human guidance, yet must learn to speak with dozens, hundreds, or thousands of binaries, each with unique inputs.

Symbolic Execution

In the first part of this two part blog post, I’ll explain what symbolic execution is and how symbolic execution allows our “reasoning system” to learn inputs for arbitrary binaries. In the second part of the blog post, I will guide you through the maze solving example presented at THREADS. To describe the power of symbolic execution, we are going to look at three increasingly difficult iterations of a classic computer science problem: maze solving. Once I discuss the power of symbolic execution, I’ll talk about KLEE, an LLVM-based symbolic execution framework, and how mcsema enables KLEE to run on binary-only applications.

Maze Solving

One of the classic problems in first year computer science classes is maze solving. Plainly, the problem is this: you are given a map of a maze. Your task is to find a path from the start to the finish. The more formal definition is: a maze is defined by a matrix where each cell can be a step or a wall. One can move into a step cell, but not into a wall cell. The only valid move directions are up, down, left, or right. A sequence of moves from cell to cell is called a path. Some cell is marked as START and another cell is marked as END. Given this maze, find a path from START to END, or show that no such path exists.

An example maze. The step spaces are blank, the walls are +-|, the END marker is the # sign, and the current path is the X's.

An example maze. The step spaces are blank, the walls are +-|, the END marker is the # sign, and the current path is the X’s.

The typical solution to the maze problem is to enumerate all possible paths from START, and search for a path that terminates at END. The algorithm is neatly summarized in this stack overflow post. The algorithm works because it has a complete map of the maze. The map is used to create a finite set of valid paths. This set can be quickly searched to find a valid path.

Maze Solving sans Map

In an artificial intelligence class, one may encounter a more difficult problem: solving a maze without the map. In this problem, the solver has to discover the map prior to finding a path from the start to the end. More formally, the problem is: you are given an oracle that answers questions about maze paths. When given a path, the oracle will tell you if the path solves the maze, hits a wall, or moves to a step position. Given this oracle, find a path from the start to the end, or show there is no path.

The solution to this problem is backtracking. The solver will build the path one move at a time, asking the oracle about the path at every move. If an attempted move hits a wall, the solver will try another direction. If no direction works, the solver returns to the previous position and tries a new direction. Eventually, the solver will either find the end or visit every possible position. Backtracking works because with every answer from the oracle, the solver learns more of the map. Eventually, the solver will learn enough of the map to find the end.

Maze Solving with Fake Walls

Lets posit an even more difficult problem: a maze with fake walls. That is, there are some walls that are really steps. Since some walls are fake, the solver learns nothing from the oracle until it asks about a complete solution. If this isn’t very clear, imagine a map that is made from completely fake walls: for any path, except one that solves the maze, the oracle will always answer “wall.” More formally, the problem now is: given an oracle that will verify only a complete path from the start to the end, solve the maze.

This is vastly more difficult than before: the solver can’t learn the map. The only generic solution is to ask the oracle about every possible path. The solver will eventually guess a valid path, since it must be in the set of all paths (assuming the maze is finite). This “brute force” solver is even more powerful than the previous: it will solve all mazes, map or no map.

Despite its power, the brute force solver has a huge problem: it’s slow and impractical.

Cheat To Win

The last problem is equivalent to the following more general problem: given an oracle that verifies solutions, find a valid solution. Ideally, we want something that finds a valid solution faster than brute force guessing. Especially when it comes to generic problems, since we don’t even know what the inputs look like!

So lets make a “generic problem solver”. Brute force is slow and impractical because it tries every single concrete input, in sequence. What if a solver could try all inputs at once? Humans do this all the time without even thinking. For instance, when we solve equations, we don’t try every number until we find the solution. We use a variable that can stand in for any number, and algorithmically identify the answer.

So how will our solver try every input at once? It will cheat to win! Our solver has an ace up its sleeve: the oracle is a real program. The solver can look at the oracle, analyze it, and find a solution without guessing. Sadly, this is impossible to do for every oracle (because you run into the halting problem). But for many real oracles, this approach works.

For instance, consider the following oracle that declares a winner or a loser:

x = input();
if(x > 5 && x < 9 && x % 4 == 0) {
  winner();
else {
  loser();
}

The solver could determine that the winner input must be a number greater than 5, less than 9, and evenly divisible by 4. These constraints can be turned into a set of linear equations and solved, showing the only winner value is 8.

A hypothetical problem solver could work like this: it will treat input into the oracle as a symbol. That is, instead of picking a specific value as the input, the value will be treated as a variable. The solver will then apply constraints to the symbol that correspond to different branches in the oracle program. When the solver finds a “valid solution” state in the oracle, the constraints on the input are solved. If the constraints can be solved, the result will be a concrete input that reaches the valid solution state. The problem solver tries every possible input at once by converting the oracle into a system of linear equations.

This hypothetical problem solver is real: the part that discovers the constraints is called a symbolic execution framework, and the part that solves equations is called an SMT solver.

The Future Is Now

There are several software packages that combine symbolic execution with SMT solvers to analyze programs. We will be looking at KLEE because it works with LLVM bitcode. We can use KLEE as a generic problem solver to find all valid inputs given an oracle that verifies those inputs. KLEE can solve a maze with hidden walls: Felipe Manzano has an excellent blog post showing how to use KLEE to solve exactly such a maze.

So what does mcsema have to do with this? Well, KLEE works on programs written in LLVM bitcode. Before mcsema, KLEE could only analyze programs that come with source code. Using mcsema, KLEE can be a problem solver for arbitrary binary applications! For instance, given a compiled binary that checks solutions to mazes with hidden walls, KLEE could find all the valid paths through the maze. Or it could do something more useful, like automatically generate application tests with high code coverage, or maybe even find security bugs in binary programs.

But back to maze solving. In Part 2 of this blog post, we’ll take a binary that solves mazes, use mcsema to translate it to LLVM, and then use KLEE to find all valid paths through the maze. More specifically, we will take Felipe’s maze oracle and compile it to a Linux binary. Then, we will use mcsema and KLEE to find all possible maze solutions. Everything will be done without modifying the original binary. The only thing KLEE will know is how to provide input and how to check solutions. In essence, we are going to show how to use mcsema and KLEE to identify all valid inputs to a binary application.

Speaker Lineup for THREADS ’14: Scaling Security

For every security engineer you train, there are 20 or more developers writing code with potential vulnerabilities. There’s no human way to keep up. We need to be more effective with less resources. It’s time to make security a fully integrated part of modern software development and operations.

It’s time to automate.

This year’s THREADS will focus exclusively on automating security. In this single forum, a selection of the industry’s best experts will present previously unseen in-house innovations deployed at major technology firms, and share leading research advances available in the future.

Buy tickets for THREADS now to get the early-bird special (expires 10/13).

DARPA Returns – Exclusive

If you attended THREADS’13, you know that our showcase of DARPA’s Cyber Fast Track was not-to-be-missed. Good news, folks. DARPA’s coming back with a brief of another exciting project, the Integrated Cyber Analysis System (ICAS). ICAS enables streamlined detection of targeted attacks on large and diverse corporate networks. (Think Target, Home Depot, and JPMorgan Chase.)

We’ll hear from the three players DARPA invited to tackle the problem: Invincea Labs, Raytheon BBN, and Digital Operatives. Each group attempted to meet the project goals in a unique way, and will share their experiences and insights.

Learn about it at THREADS’14 first.

World-Class Speakers at THREADS’14

KEYNOTES

Robert Joyce, Chief, Tailored Access Operations (TAO), NSA

As the Chief of TAO, Rob leads an organization that provides unique, highly valued capabilities to the Intelligence Community and the Nation’s leadership.  His organization is the NSA mission element charged with providing tools and expertise in computer network exploitation to deliver foreign intelligence. Prior to becoming the Chief of TAO, Rob served as the Deputy Director of the Information Assurance Directorate (IAD) at NSA, where he led efforts to harden, protect and defend the Nation’s most critical National Security systems and improve cybersecurity for the nation.

Michael Tiffany, CEO, White Ops

Michael Tiffany is the co-founder and CEO of White Ops, a security company founded in 2013 to break the profit models of cybercriminals. By making botnet schemes like ad fraud unprofitable, White Ops disrupts the criminal incentive to break into millions of computers. Previously, Tiffany was the co-founder of Mission Assurance Corporation, a pioneer in space-based computing that is now a part of Recursion Ventures. He is a Technical Fellow of Critical Assets Labs, a DARPA-funded cyber-security research lab. He is a Subject Matter Advisor for the Signal Media Project, a nonprofit promoting the accurate portrayal of science, technology and history in popular media. He is also a Ninja.

LEADING RESEARCH

Smten and the Art of Satisfiability-based Search
Nirav Dave, SRI

Reverse All the Things with PANDA
Brendan Dolan-Gavitt, Columbia University

Code-Pointer Integrity
Laszlo Szekeres, Stony Brook University

Static Translation of X86 Instruction Semantics to LLVM with McSema
Artem Dinaburg & Andrew Ruef, Trail of Bits

Transparent ROP Detection using CPU Performance Counters
Xiaoning Li, Intel & Michael Crouse, Harvard University

Improving Scalable, Automated Baremetal Malware Analysis
Adam Allred & Paul Royal, Georgia Tech Information Security Center (GTISC)

Integrated Cyber Attribution System (ICAS) Program Brief
Richard Guidorizzi, DARPA

TAPIO: Targeted Attack Premonition using Integrated Operational Data Sources
Invincea Labs

Gestalt: Integrated Cyber Analysis System
Raytheon BBN

Federated Understanding of Security Information Over Networks (FUSION)
Digital Operatives

IN-HOUSE INNOVATIONS

Building Your Own DFIR Sidekick
Scott J Roberts, Github

Operating system analytics and host intrusion detection at scale
Mike Arpaia, Facebook

Reasoning about Optimal Solutions to Automation Problems
Jared Carlson & Andrew Reiter, Veracode

Augmenting Binary Analysis with Python and Pin
Omar Ahmed, Etsy & Tyler Bohan, NYU-Poly

Are attackers using automation more efficiently than defenders?
Marc-Etienne M.Léveillé, ESET

Making Sense of Content Security Policy (CSP) Reports @ Scale
Ivan Leichtling, Yelp

Automatic Application Security @twitter
Neil Matatall, Twitter

Cleaning Up the Internet with Scumblr and Sketchy
Andy Hoernecke, Netflix

CRITs: Collaborative Research Into Threats
Michael Goffin, Wesley Shields, MITRE

GitHub AppSec: Keeping up with 111 prolific engineers
Ben Toews, GitHub

Don’t miss out. Buy tickets for THREADS now to get the early-bird special (expires 10/13). You won’t find a more comprehensive treatment of scaling security anywhere else.

 

We’re Sponsoring the NYU-Poly Women’s Cybersecurity Symposium

NYU-Poly Women's Cybersecurity Symposium

Cyber security is an increasingly complex and vibrant field that requires brilliant and driven people to work on diverse teams. Unfortunately, women are severely underrepresented and we want to change that. Career Discovery in Cyber Security is an NYU-Poly event, created in a collaboration with influential men and women in the industry. This annual symposium helps guide talented and interested women into careers in cyber security. We know that there are challenges for female professionals in male-dominated fields, which is why we want to create an environment where women have the resources they need to excel.

The goal of this symposium is to showcase the variety of industries and career paths in which cyber security professionals can make their mark. Keynote talks, interactive learning sessions, and technical workshops will prepare participants to identify security challenges and acquire the skills to meet them. A mentoring roundtable, female executive panel Q&A session, and networking opportunities allow participants to interact with accomplished women in the field in meaningful ways. These activities will give an extensive, well-rounded look into possible career paths.

Trail of Bits is a strong advocate for women in the cyber security world at all stages of their careers. In the past, we were participants in the CSAW Summer Program for Women, which introduced high school women to the world of cyber security. We are proud of our involvement in this women’s symposium from its earliest planning stages, continue to offer financial support via named scholarships for attendees, and will take part in the post-event mentoring program.

This year’s symposium is Friday and Saturday, October 17-18 in Brooklyn, New York. For more details and registration, visit the website. Follow the symposium on Twitter or Facebook for news and updates.

Enabling Two-Factor Authentication (2FA) for Apple ID and DropBox

In light of the recent compromises, you’re probably wondering what could have been done to prevent such attacks. According to some unverified articles it would appear that flaws in Apple’s services allowed an attacker to brute force passwords without any rate limiting or account lockout. While its not publicly known if the attacks were accomplished via brute force password guessing, there has been a lot of talk about enabling Two-Factor Authentication (2FA) across services that offer it. The two most popular services being discussed are iCloud and DropBox. While setting up 2FA on these services is not as easy as it should be, this guide will step you through enabling 2FA on Google, Apple ID and DropBox accounts. It’s a free way of adding an extra layer of security on top of these services which handle potentially sensitive information.

What is Two-Factor Authentication?

Username and password authentication uses a single factor to verify identity: something the user knows. Two-Factor authentication adds an extra layer of security on top of a username and password. Normally, the second factor is something only the real user has. This is typically a temporary passcode generated by a piece of hardware such as an RSA token, a passcode sent as an SMS to the user’s cell phone, or a mobile application that accomplishes the same function.

With two-factor authentication, stealing a username and password won’t be enough to log in — the second factor is also required. This multi-factor authentication means an attacker will be required to compromise a user above and beyond password guessing or stealing a credentials database. An attacker would have to gain access to the source of the extra, unique and usually temporary information that makes up the 2FA.
[Read more…]

ReMASTering Applications by Obfuscating during Compilation

In this post, we discuss the creation of a novel software obfuscation toolkit, MAST, implemented in the LLVM compiler and suitable for denying program understanding to even the most well-resourced adversary. Our implementation is inspired by effective obfuscation techniques used by nation-state malware and techniques discussed in academic literature. MAST enables software developers to protect applications with technology developed for offense.

MAST is a product of Cyber Fast Track, and we would like to thank Mudge and DARPA for funding our work. This project would not have been possible without their support. MAST is now a commercial product offering of Trail of Bits and companies interested in licensing it for their own use should contact info@trailofbits.com.

Background

There are a lot of risks in releasing software these days. Once upon a time, reverse engineering software presented a challenge best solved by experienced and skilled reverse engineers at great expense. It was worthwhile for reasonably well-funded groups to reverse engineer and recreate proprietary technology or for clever but bored people to generate party tricks. Despite the latter type of people causing all kinds of mild internet havoc, reverse engineering wasn’t widely considered a serious threat until relatively recently.

Over time, however, the stakes have risen; criminal entities, corporations, even nation-states have become extremely interested in software vulnerabilities. These entities seek to either defend their own network, applications, users, or to attack someone else’s. Historically, software obfuscation was a concern of the “good guys”, who were interested in protecting their intellectual property. It wasn’t long before malicious entities began obfuscating their own tools to protect captured tools from analysis.

A recent example of successful obfuscation is that used by the authors of the Gauss malware; several days after discovering the malware, Kaspersky Lab, a respected malware analysis lab and antivirus company, posted a public plea for assistance in decrypting a portion of the code. That even a company of professionals had trouble enough to ask for outside help is telling: obfuscation can be very effective. Professional researchers have been unable to deobfuscate Gauss to this day.

Motivation

With all of this in mind, we were inspired by Gauss to create a software protection system that leapfrogs available analysis technology. Could we repurpose techniques from software exploitation and malware obfuscation into a state-of-the-art software protection system? Our team is quite familiar with publicly available tools for assisting in reverse engineering tasks and considered how to significantly reduce their efficacy, if not deny it altogether.

Software developers seek to protect varying classes of information within a program. Our system must account for each with equal levels of protection to satisfy these potential use cases:

  • Algorithms: adversary knowledge of proprietary technology
  • Data: knowledge of proprietary data (the company’s or the user’s)
  • Vulnerabilities: knowledge of vulnerabilities within the program

In order for the software protection system to be useful to developers, it must be:

  • Easy to use: the obfuscation should be transparent to our development process, not alter or interfere with it. No annotations should be necessary, though we may want them in certain cases.
  • Cross-platform: the obfuscation should apply uniformly to all applications and frameworks that we use, including mobile or embedded devices that may run on different processor architectures.
  • Protect against state-of-the-art analysis: our obfuscation should leapfrog available static analysis tools and techniques and require novel research advances to see through.

Finally, we assume an attacker will have access to the static program image; many software applications are going to be directly accessible to a dedicated attacker. For example, an attacker interested in a mobile application, anti-virus signatures, or software patches will have the static program image to study.

Our Approach

We decided to focus primarily on preventing static analysis; in this day and age there are a lot of tools that can be run statically over application binaries to gain information with less work and time required by attackers, and many attackers are proficient in generating their own situation-specific tools. Static tools can often very quickly be run over large amounts of code, without necessitating the attacker having an environment in which to execute the target binary.

We decided on a group of techniques that compose together, comprising opaque predicate insertion, code diffusion, and – because our original scope was iOS applications – mangling of Objective-C symbols. These make the protected application impossible to understand without environmental data, impossible to analyze with current static analysis tools due to alias analysis limitations, and deny the effectiveness of breakpoints, method name retrieval scripts, and other common reversing techniques. In combination, these techniques attack a reverse engineer’s workflow and tools from all sides.

Further, we did all of our obfuscation work inside of a compiler (LLVM) because we wanted our technology to be thoroughly baked into the entire program. LLVM can use knowledge of the program to generate realistic opaque predicates or hide diffused code inside of false paths not taken, forcing a reverse engineer to consult the program’s environment (which might not be available) to resolve which instruction sequences are the correct ones. Obfuscating at the compiler level is more reliable than operating on an existing binary: there is no confusion about code vs. data or missing critical application behavior. Additionally, compiler-level obfuscation is transparent to current and future development tools based on LLVM. For instance, MAST could obfuscate Swift on the day of release — directly from the Xcode IDE.

Symbol Mangling

The first and simplest technique was to hinder quick Objective-C method name retrieval scripts; this is certainly the least interesting of the transforms, but would remove a large amount of human-readable information from an iOS application. Without method or other symbol names present for the proprietary code, it’s more difficult to make sense of the program at a glance.

Opaque Predicate Insertion

The second technique we applied, opaque predicate insertion, is not a new technique. It’s been done before in numerous ways, and capable analysts have developed ways around many of the common implementations. We created a stronger version of predicate insertion by inserting predicates with opaque conditions and alternate branches that look realistic to a script or person skimming the code. Realistic predicates significantly slow down a human analyst, and will also slow down tools that operate on program control flow graphs (CFGs) by ballooning the graph to be much larger than the original. Increased CFG size impacts the size of the program and the execution speed but our testing indicates the impact is smaller or consistent with similar tools.

Code Diffusion

The third technique, code diffusion, is by far the most interesting. We took the ideas of Return-Oriented Programming (ROP) and applied them in a defensive manner.

In a straightforward situation, an attacker exploits a vulnerability in an application and supplies their own code for the target to execute (shellcode). However, since the introduction of non-executable data mitigations like DEP and NX, attackers have had to find ways to execute malicious code without the introduction of anything new. ROP is a technique that makes use of code that is already present in the application. Usually, an attacker would compile a set of short “gadgets” in the existing program text that each perform a simple task, and then link those together, jumping from one to the other, to build up the functionality they require for their exploit — effectively creating a new program by jumping around in the existing program.

We transform application code such that it jumps around in a ROP-like way, scrambling the program’s control flow graph into disparate units. However, unlike ROP, where attackers are limited by the gadgets they can find and their ability to predict their location at runtime, we precisely control the placement of gadgets during compilation. For example, we can store gadgets in the bogus programs inserted during the opaque predicate obfuscation. After applying this technique, reverse engineers will immediately notice that the handy graph is gone from tools like IDA. Further, this transformation will make it impossible to use state-of-the-art static analysis tools, like BAP, and impedes dynamic analysis techniques that rely on concrete execution with a debugger. Code diffusion destroys the semantic value of breakpoints, because a single code snippet may be re-used by many different functions and not used by other instances of the same function.

graph view is useful

Native code before obfuscation with MAST

graph view is useless

Native code after obfuscation with MAST

The figures above demonstrate a very simple function before and after the code diffusion transform, using screenshots from IDA. In the first figure, there is a complete control flow graph; in the second, however, the first basic block no longer jumps directly to either of the following blocks; instead, it must refer at runtime to a data section elsewhere in the application before it knows where to jump in either case. Running this code diffusion transform over an entire application reduces the entire program from a set of connected-graph functions to a much larger set of single-basic-block “functions.”

Code diffusion has a noticeable performance impact on whole-program obfuscation. In our testing, we compared the speed of bzip2 before and after our return-oriented transformation and slowdown was approximately 55% (on x86).

Environmental Keying

MAST does one more thing to make reverse engineering even more difficult — it ties the execution of the code to a specific device, such as a user’s mobile phone. While using device-specific characteristics to bind a binary to a device is not new (it is extensively used in DRM and some malware, such as Gauss), MAST is able to integrate device-checking into each obfuscation layer as it is woven through the application. The intertwining of environmental keying and obfuscation renders the program far more resistant to reverse-engineering than some of the more common approaches to device-binding.

Rather than acquiring any copy of the application, an attacker must also acquire and analyze the execution environment of the target computer as well. The whole environment is typically far more challenging to get ahold of, and has a much larger quantity of code to analyze. Even if the environment is captured and time is taken to reverse engineer application details, the results will not be useful against the same application as running on other hosts because every host runs its own keyed version of the binary.

Conclusions

In summary, MAST is a suite of compile-time transformations that provide easy-to-use, cross-platform, state-of-the-art software obfuscation. It can be used for a number of purposes, such as preventing attackers from reverse engineering security-related software patches; protecting your proprietary technology; protecting data within an application; and protecting your application from vulnerability hunters. While originally scoped for iOS applications, the technologies are applicable to any software that can be compiled with LLVM.

Follow

Get every new post delivered to your Inbox.

Join 4,182 other followers