crypto question

[dmolnar]

On Thu, 21 Mar 2002, McMeikan, Andrew wrote:

> A question and a probe.
>
> Question.  Is it possible to have code that contains a private encryption
> key safely?  Every way I look at it the answer seems no, yet some degree of
> safety might be possible by splitting an encrypting routine across several
> nodes.  Can someone give me a pointer to any work in this area?

There are several different possible scenarios which fit this description.
My message will overlap a little with the other reply I've seen, for which
I apologize. Here they are in rough order of what I think you're asking.

1) You are trying to distribute an obfuscated binary which
encrypts/decrypts using a secret key, with the goal that the key resist
reverse engineering. The usual application for this is DRM, but you can
also use this to do "public-key encryption" from any symmetric algorithm
(obfuscate the encryption function!).

(disclaimer: I work for ShieldIP, which is a DRM company. All statements
and opinions here are my own.)

There's a recent result showing that there exist some functions which
*cannot* be obfuscated, for several technical formalizations of the notion
"obfuscated." That result is available as:

On the (Im)possibility of Obfuscating Programs
Boaz Barak Oded Goldreich, Russell Impagliazzo, Steven Rudich, Amit Sahai,
Salil Vadhan, Ke Yang
http://citeseer.nj.nec.com/barak01impossibility.html

It is important to note that this result doesn't necessarily apply to the
kinds of programs we want to obfuscate in practice. Rather it shows that
there is a large class of "unobfuscatable functions" and builds such
functions through clever means. At least that's my current take; I should
hedge here and say I haven't gone through it thoroughly -- I'd welcome
correction from anyone who's taken more time to map out the practical
implications (for instance, "is it possible that a block cipher could be
obfuscated?").

Naturally this result hasn't stopped people from trying practical
techniques for code obfuscation. Cloakware (www.cloakware.com) is just one
of the companies pursuing research into software obfuscation. Doing a
google search for "code obfuscation" provides many links. I don't know
enough to say which of them are any good.

People have also tried to obtain a similar level of protection by
embedding code in tamper-resistant hardware. IBM's ABYSS project was an
early example of this aimed specifically at copy protection. That begat
Citadel which begat 4758 and thus was the begatting begun. As another
message mentions, Atallah/Compaq/HP and Wave Systems today do similar
things. I note that the Intertrust web page mentions a Rights|Chip which
may or may not do similar things. Bennet Yee's thesis, among other places,
is a good place to learn about secure coprocessors.
ftp://www.cs.ucsd.edu/pub/bsy/pub/th.ps.gz

2) You have an application which uses private keys and you are worried
about writing them to disk. Your adversary is not the user, but someone
who may gain "lunch-time" access to the machine and not plant keyloggers,
bugs, etc, but only transfers files or swap to a diskette. This is kind of
a weak adversary, but it's also about what most co-workers or kid sisters
can mount, and hey we have to protect at least against them...

The best practice here, AFAIK, is to do what PGP does. Encrypt the private
key while it's on disk using some key not on the machine. Then use a
kernel driver to obtain memory which is guaranteed not to be paged to disk
and use that memory for all sensitive operations. Get yourself a copy of
the WinPGP source code and take a look.

3) You are worried about an adversary breaking in and stealing your own
signing or decryption key from your computer. You also just happen to have
a bunch of other computers lying around that are not running the same OS
or same version (so they are unlikely to be cracked at the same time as
your first machine).

Now you're in the territory of "threshold cryptography" and "proactive
security." The MIT Threshold Cryptography page explains it better than I
could:
http://theory.lcs.mit.edu/~cis/cis-threshold.html

Dan Boneh's group has put some of these ideas into code:
http://theory.stanford.edu/~dabo/ITTC/

With "proactive security," you "refresh" machines from time to time so as
to limit damage from machines which are compromised and then renewed.
Here's the abstract from the paper reporting on the IBM implementation.
http://www.cs.huji.ac.il/~feit/artzi/artzi18.html#abs1
that paper citation is

B. Barak, A. Herzberg, D. Naor, and E. Shai. The proactive security
toolkit and applications. In Proceedings of the 6th ACM Conference on
Computer and Communications Security (CCS'99), pages 18--27, Kent Ridge
Digital Labs, Singapore, November 1999. ACM SIGSAC, ACM

There used to be an IBM page specifically on the topic of "proactive
security" and they were even going to let people download the toolkit! I
don't think that actually happened. If it did, dude, I'd like to know.

-David Molnar


---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at wasabisystems.com