[dave at farber.net: [IP] Anti-terrorism software that balances privacy and security?]

Wed Jan 25 15:52:49 PST 2006

This was discussed at Crypto last year - it was a pretty cool result.
Basically it uses "computing on encrypted instances" technology. A
filter site runs (potentially) open-source software which is looking
for certain key words and saving messages that match; but the site
can't tell which exact words are being searched for, and it can't tell
when they get matched.

However it's not quite as amazing as it sounds. There is a long list
of all possible words, that are stored in the clear. Then there is an
encrypted bit mask that tells which of these words the security agency
is searching for. The open software compares each message against each
word and creates a bit mask of which ones match. Then it does some
fancy crypto to compare this bit mask with the encrypted one, and
compute an encrypted 1 or 0 as to whether the message matched one of
the words of interest. It then multiplies this encrypted 1 or 0 by the
message, getting either an encryption of the message or zero, and adds
this into an encrypted buffer. More tricks are used to keep messages
from overwriting each other in the buffer, given that the filter
software doesn't know when it is writing meaningful data or just an
encrypted zero.

All in all it was a clever idea but suffered from two problems. The
first is that it would be computationally expensive; each operation
requires a lot of exponentiations. And the second is that the word
list is public, so even though you don't know exactly which words from
the list are of interest, you (and the bad guys) would be able to see
all the words they might be searching for, which could be a security
leak.

Hal

On 1/25/06, Eugen Leitl <eugen at leitl.org> wrote:
> ----- Forwarded message from David Farber <dave at farber.net> -----
>
> From: David Farber <dave at farber.net>
> Date: Wed, 25 Jan 2006 07:56:16 -0500
> To: ip at v2.listbox.com
> Subject: [IP] Anti-terrorism software that balances privacy and security?
> X-Mailer: Apple Mail (2.746.2)
> Reply-To: dave at farber.net
>
>
>
> Begin forwarded message:
>
> From: Ry Rivard <ryrivard at gmail.com>
> Date: January 25, 2006 5:08:15 AM EST
> To: dave at farber.net
> Subject: Anti-terrorism software that balances privacy and security?
>
> Dave,
>
> This seems interesting, but I'm skeptical about phrases like
> "mathematically proven to be impossible to reverse-engineer." If
> someone can explain this, that would be helpful. It seems either
> remarkable, somewhat exactly what already exists minus the
> impenetrability claim, or terribly over-hyped, or dangerous.
> _________________
> Anti-terrorism software claims to balance privacy and security
>
> By BJS
> Created 01/24/2006 - 13:42
> The government's ability to balance the privacy concerns of lawful
> U.S. citizens with effective monitoring of potential terrorists has
> proven an increasingly difficult task, particularly in recent months.
> But a landmark software development by researchers at UCLA's Henry
> Samueli School of Engineering and Applied Science may ease some of
> these privacy concerns by making the tracking of terrorist
> communications over the Internet more efficient, and more targeted,
> than ever before.
>
> UCLA Engineering professor Rafail Ostrovsky and graduate researcher
> William Skeith have developed a new method to mine potential
> terrorist-related communications that essentially narrows down the
> data to only those documents that fit pre-set, secret criteria chosen
> by intelligence agencies. The new approach filters down the
> information from billions of communications to just those deemed
> essential ??? discarding communications from law-abiding citizens before
> they ever reach the intelligence community. That means lawful U.S.
> citizens who don't fit the parameters are automatically ruled out.
>
> The truly revolutionary facet of the technology is that it is a new
> and powerful example of a piece of code that has been mathematically
> proven to be impossible to reverse-engineer. In other words, it can't
> be analyzed to figure out its components, construction and inner
> workings, or reveal what information it's collecting and what
> information it's discarding ??? it won't give up its secrets. It can't
> be manipulated or turned against the user.
>
> Because the code cannot be analyzed, terrorists using the Internet to
> communicate will never know if the filter has pinpointed their data or
> not. For those seeking to thwart terrorism, this development means
> less data to store and wade through in a secure setting, and,
> ultimately, the ability to react more quickly, without fear of
> exposing top-secret search criteria and tipping off the terrorists.
>
> ..."Gathering data can be costly and time-consuming for intelligence
> agencies. All of the potential data must first be pulled offline into
> a trusted and classified environment, and then painstakingly sifted
> through," Ostrovsky said. "With this new technology, based on highly
> esoteric mathematics, the software can be distributed to many machines
> on the Internet, not necessarily trusted or highly secure. The
> software works by analyzing all of the data and then having the
> appearance of putting all the data into a 'secure box.' A secret
> filter inside the box dismisses some data as useless and collects only
> relevant data according to the confidential criteria that can be
> programmed into the software. And because it's all done inside
> encrypted code, it's not apparent which, if any, of the data has been
> selected and kept, except by the person who has deployed the filter
> and has the decryption key."
>
> The filter criteria can be reset as often as intelligence analysts
> deem necessary to keep up with the changing terminology of terrorists.
>
> "While a savvy person may be able to tell that the program is running
> in the background, they will not be able to tell what data is being
> selected," Ostrovsky explained. "For example, even if Al Qaeda had an
> extremely knowledgeable programmer and, say, they steal a laptop with
> this program, they would not be able to figure out which documents
> were selected and kept inside the 'secure box' and which were not. By
> distributing this software all over the Internet to providers and
> network administrators, you can easily monitor a huge data flow in a
> distributed, cost-efficient manner, and choose only those documents
> that look promising based on your secret criteria. The filter cannot
> be broken in the same sense that one cannot crack time???tested
> public???key encryption functions such as those already used for
> Internet commerce and banking applications. In that aspect, it's
> essentially a bullet-proof technology."
>
> ...Ostrovsky, who also directs the Center of Information and
> Computation Security at the school, said, "There have to be checks and
> balances. Like any tool, technology can be used for good or bad. I
> view this research as a new and viable way to combat terrorism that
> can also strike a balance with the need for strong privacy protections
> for ordinary citizens. It's an efficient data???gathering technology
> against the bad guys. In that sense, it could be an exciting new tool
> in the U.S. Department of Defense's arsenal against terror."
>
> The technology also has other potential privacy-enhancing
> applications. In addition to its use online, it also could be used by
> physicians wishing to search patient records for certain medical
> conditions while maintaining the patient's privacy from other workers
> in the office, among other functions. The researchers already have
> filed a patent on the work.
>
> For more information contact Melissa Abraham
> mabraham at support.ucla.edu
> Phone: 310-206-0540
>
> Source URL:
> http://www.scienceblog.com/cms/anti-
> terrorism_software_claims_to_balance_privacy_and_security_9862
>
> --
> Ry Rivard
> http://braxtonian.com
>
> -------------------------------------
> You are subscribed as eugen at leitl.org
> To manage your subscription, go to
>  http://v2.listbox.com/member/?listname=ip
>
> Archives at: http://www.interesting-people.org/archives/interesting-people/
>
> ----- End forwarded message -----
> --
> Eugen* Leitl <a href="http://leitl.org">leitl</a> http://leitl.org
> ______________________________________________________________
> ICBM: 48.07100, 11.36820            http://www.ativel.com
> 8B29F6BE: 099D 78BA 2FD3 B014 B08A  7779 75B0 2443 8B29 F6BE
>
> [demime 1.01d removed an attachment of type application/pgp-signature which had a name of signature.asc]