more on Solution for Gov't Security-Privacy Clash?

[Dave Farber <dave () farber net>]

Delivered-To: dfarber+ () ux13 sp cs cmu edu
Date: Thu, 11 Mar 2004 15:14:09 -0800
From: Seth David Schoen <schoen () eff org>
Subject: Re: [IP] Solution for Gov't Security-Privacy Clash?
Sender: Seth David Schoen <schoen () zork net>
To: Dave Farber <dave () farber net>
X-Modulation: 8/VSB Is Not A Crime

Dave Farber writes:

> Delivered-To: dfarber+ () ux13 sp cs cmu edu
> Date: Thu, 11 Mar 2004 16:54:44 -0500
> From: Pike236 () cs com
> Subject: Solution for Gov't Security-Privacy Clash?
> To: dave () farber net
> (Have I not heard this one before?? djf)

There's a lot of material about hashing techniques to protect privacy
in Peter Wayner's _Translucent Databases_, but a general problem with
these techniques is the possibility of a brute-force attack.  For
example, if you hash an address to try to avoid giving it away,
someone can buy a Census database like TIGER and get a list of all the
street names in the country.  Presumably a brute force search over
those addresses will be feasible.

On a single fast modern computer, if you knew the name or some other
personally-identifiable characteristic of every person in the world,
you could trivially try _each possibility_ to see if the hash matched
up or not.

A modern PC (not even a cluster and not even custom hardware) will do
some millions of one-way hashes per second.  That means waiting around
an hour while your desktop figures out which person is the subject of
an "encrypted" record, simply by trying each possibility, if you have
a suitable database of candidate identities.

If I remember correctly, Wayner extensively cautioned implementers
about these problems.  If the space of possible values is small by
computer standards (around 32 bits, like an IP address, or a human
being's identity), brute force is perfectly plausible.  In fact,
suggestions about hashing IP addresses in log files for privacy
suffer from an equivalent problem.

The Markle report this article mentions is available at

http://www.markletaskforce.org/Report2_Full_Report.pdf

but the report's two references to hashing don't provide enough
technical detail to say whether brute force is a problem for these
applications.  Without more detail, it's hard to be very
enthusiastic about this approach.

--
Seth Schoen
Staff Technologist                                schoen () eff org
Electronic Frontier Foundation                    http://www.eff.org/
454 Shotwell Street, San Francisco, CA  94110     1 415 436 9333 x107 

-------------------------------------
You are subscribed as interesting-people () lists elistx com
To manage your subscription, go to
 http://v2.listbox.com/member/?listname=ip

Archives at: http://www.interesting-people.org/archives/interesting-people/