June 28, 2011

Intermediate cryptography resources

Filed under: Crypto,Security — Nate Lawson @ 12:26 pm

People often ask me for a good introduction to intermediate cryptography. It’s often easy to find basic and dangerous introductions (“public key encryption is like a mailbox”), but the next level isn’t as available.

There’s no single source for this, but you can find good coverage of the main practical topics online. Here are some resources to get you started learning beyond cryptography basics.

Cryptography: an Introduction (Nigel Smart)

I can’t say enough good things about this book. It is a great way to learn about attacks on public key schemes (see part 4) and has good general coverage as well, including elliptic-curve.

Lecture Notes on Cryptography (Bellare and Goldwasser)

Good for understanding how to model block cipher constructions with PRFs and PRPs. When someone says “that construction is not IND-CPA-secure”, this will tell you what that means. Try chapters 5, 6, and 9. Also, see the class notes page for slides and individual chapters of this series.

Tom’s math and crypto libraries (Tom St. Denis)

It’s impossible to understand practical cryptography without looking at implementations. Tom’s libraries are relatively clear and readable and cover the gamut from low-level integer manipulation all the way up to protocols. There are no external dependencies and they are public domain. For extra credit, implement one of the ciphers yourself before looking at his code, then compare to see how you did.

He also includes a large PDF documenting the library, and it’s available as a book as well.

NIST FIPS, SP and RSA PKCS standards

The NIST standards are pretty clear. The RSA ones are a bit more difficult to read. In any case, it’s very helpful to read through these and ask “why?” for each requirement they make. There’s always a reason for every “shall” or “must”. But are there some “shoulds” that should be “shalls”?

Once you’ve moved beyond these resources, the best next level is to read survey papers (like Boneh’s coverage of RSA) in the specific area you’re interested in. If you have your own favorite resources for intermediate cryptography, let me know in the comments below.

June 9, 2011

Shatner on the future of microchips

Filed under: Security — Nate Lawson @ 5:39 am

AT&T recently published a lot of videos from their archives. I particularly like this video with William Shatner discussing the magic of the microchip. In hindsight, its view of the future is revealing.

First, it’s still a good introduction to how chips are produced. It shows an automated test machine, wire-bonding, and hand-soldering boards. It also shows microscopic views of a 5 micron circuit and a nice animation of clock pulses and gates. All of these processes are basically the same today, just more sophisticated.

On the flip side, its prediction about the computerization of telephones revolutionizing society has come and gone. Wired telephones connected to smart central computers have been surpassed by smart cellphones.

This video also reminded me how there once were more women in technology. Computer science was originally considered a branch of math, and women have often excelled at mathematics. When this video was made in 1980, women made up about 41% of computer science freshmen. That had dropped to about 12.5% by 2007. If you look at the graph from that article, it seems that women participated almost equally in the early 80’s computer craze but sat out the Dotcom boom.

I’m still not sure about all the causes of this, but it is a troubling trend. Any time half of your intelligence sits on the bench, you’re going to be at a disadvantage to other countries. Some studies have shown Chinese women have a more positive view of computers than other cultures. Additionally, all enrollment in computer science is lower as a percentage than at any time since the 1970’s.

What can be done to increase interest in computer science among all students and especially women?

June 6, 2011

Improving ASLR with internal randomization

Filed under: Hacking,Network,Security,Software protection — Nate Lawson @ 4:24 am

Most security engineers are familiar with address randomization (ASLR). In the classic implementation, the runtime linker or image loader chooses a random base offset for the program, its dynamic libraries, heap, stack, and mmap() regions.

At a higher level, these can all be seen as obfuscation. The software protection field has led with many of these improvements because cracking programs is a superset of exploiting them. That is, an attacker with full access to a program’s entire runtime state is much more advantaged than one with only remote access to the process, filtered through an arbitrary protocol. Thus, I predict that exploit countermeasures will continue to recapitulate the historical progress of software protection.

The particular set of obfuscations used in ASLR were chosen for their ease of retrofitting existing programs. The runtime linker/loader is a convenient location for randomizing various memory offsets and its API is respected by most programs, with the most notable exceptions being malware and some software protection schemes. Other obfuscation mechanisms, like heap metadata checksumming, are hidden in the internals of system libraries. Standard libraries are a good, but less reliable location than the runtime linker. For example, many programs have their own internal allocator, reducing the obfuscation gains of adding protection to the system allocator.

A good implementation of ASLR can require attackers to use a memory disclosure vulnerability to discover or heap fung shui to create a known memory layout for reliable exploitation. While randomizing chunks returned from the standard library allocator can make it harder for attackers to create a known state, memory disclosure vulnerabilities will always allow a determined attacker to subvert obfuscation. I expect we’ll see more creativity in exercising partial memory disclosure vulnerabilities as the more flexible bugs are fixed.

ASLR has already forced researchers to package multiple bugs into a single exploit, and we should soon see attackers follow suit. However, once the base offsets of various libraries are known, the rest of the exploit can be applied unmodified. For example, a ROP exploit may need addresses of gadgets changed, but the relative offsets within libraries and the code gadgets available are consistent across systems.

The next logical step in obfuscation would be to randomize the internals of libraries and code generation. In other words, you re-link the internal functions and data offsets within libraries or programs so that code and data are at different locations in DLLs from different systems. At the same time, code generation can also be randomized so that different instruction sequences are used for the same operations. Since all this requires deep introspection, it will require a larger change in how software is delivered.

Fortunately, that change is on the horizon for other reasons. LLVM and Google NaCl are working on link-time optimization and runtime code generation, respectively. What this could mean for NaCl is that a single native executable in LLVM bitcode format would be delivered to the browser. Then, it would be translated to the appropriate native instruction set and executed.

Of course, we already have a form of this today with the various JIT environments (Java JVM, Adobe ActionScript, JavaScript V8, etc.) But these environments typically cover only a small portion of the attack surface and don’t affect the browser platform itself. Still, randomized JIT is likely to become more common this year.

One way to implement randomized code delivery is to add this to the installer. Each program could be delivered as LLVM IR and then native code generation and link addresses could be randomized as it was installed. This would not slow down the installation process significantly but would make each installation unique. Or, if the translation process was fast enough, this could be done on each program launch.

Assuming this was successfully deployed, it would push exploit development to be an online process. That is, an exploit would include a built-in ROP gadget generator and SMT solver to generate a process/system-specific exploit. Depending on the limitations of available memory disclosure vulnerabilities and specific process state, it might not be possible to automatically exploit a particular instance. Targeted attacks would have to be much more targeted and each system compromised would require the individual attention of a highly-skilled attacker.

I’m not certain software vendors will accept the nondeterminism of this approach. Obviously, it makes debugging production systems more difficult and installation-specific. However, logging the random seed used to initiate the obfuscation process could be used to recreate a consistent memory layout for testing.

For now, other obfuscation measures such as randomizing the allocator may provide more return on investment. As ROP-specific countermeasures are deployed, it will become easier to exploit a program’s specific internal logic (flags, offsets, etc.) than to try to get full code execution. It seems that, for now, exploit countermeasures will stay focused on randomizing and adding checksums to data structures, especially those in standard libraries.

But is this level of obfuscation where exploit countermeasures are headed? How long until randomized linking and code generation are part of a mainline OS?

Blog at WordPress.com.