PRISM and an Agenda for European Network

Security Research
Another Turn of the Wheel: Mainframe, Desktop, Cloud, Peer
Christian Grotho
Technische Universitat M unchen
02.07.2013
Never doubt your ability to change the world. Glenn Greenwald
Everybody Has Secrets

Business & Trade Secrets

Political opinions

Illegal activities
Keeping Secrets

Encryption: baseline

Hide meta-data: state of the art

Practice today?
Send everything to US in plaintext
Keeping Secrets

Encryption: baseline

Hide meta-data: state of the art

Practice today?
Send everything to US in plaintext

Guardian: The PRISM program allows the intelligence

services direct access to the companies servers.

Cooperating providers: Microsoft, Yahoo, Google, Facebook,

PalTalk, YouTube, Skype, AOL, Apple

PRISM enables real-time surveillance and access to stored

content

Data collected: E-mails, instant messages, videos, photos,

stored data (likely les), voice chats, le transfers, video
conferences, log-in times, and social network proles

Tiny part of NSA: $20 M budget

US discussion focuses on spying on US citizens and legality

under US law
Frank Church (D-Idaho): The NSAs capability at any time could
be turned around on the American people, and no American
would have any privacy left, such is the capability to monitor
everything: telephone conversations, telegrams, it doesnt matter.

Guardian: The PRISM program allows the intelligence

services direct access to the companies servers.

Cooperating providers: Microsoft, Yahoo, Google, Facebook,

PalTalk, YouTube, Skype, AOL, Apple

PRISM enables real-time surveillance and access to stored

content

Data collected: E-mails, instant messages, videos, photos,

stored data (likely les), voice chats, le transfers, video
conferences, log-in times, and social network proles

Tiny part of NSA: $20 M budget

US discussion focuses on spying on US citizens and legality

under US law
Frank Church (D-Idaho): The NSAs capability at any time could
be turned around on the American people, and no American
would have any privacy left, such is the capability to monitor
everything: telephone conversations, telegrams, it doesnt matter.

Guardian: The PRISM program allows the intelligence

services direct access to the companies servers.

Cooperating providers: Microsoft, Yahoo, Google, Facebook,

PalTalk, YouTube, Skype, AOL, Apple

PRISM enables real-time surveillance and access to stored

content

Data collected: E-mails, instant messages, videos, photos,

stored data (likely les), voice chats, le transfers, video
conferences, log-in times, and social network proles

Tiny part of NSA: $20 M budget

US discussion focuses on spying on US citizens and legality

under US law
Frank Church (D-Idaho): The NSAs capability at any time could
be turned around on the American people, and no American
would have any privacy left, such is the capability to monitor
everything: telephone conversations, telegrams, it doesnt matter.

NSAs tool to track global surveillance data

2,392,343,446 records from the US

97,111,199,358 records worldwide

This is for March 2013 alone

Germany most surveilled country in Europe

leverages FOSS technology

NSAs tool to track global surveillance data

2,392,343,446 records from the US

97,111,199,358 records worldwide

This is for March 2013 alone

Germany most surveilled country in Europe

leverages FOSS technology

NSAs tool to track global surveillance data

2,392,343,446 records from the US

97,111,199,358 records worldwide

This is for March 2013 alone

Germany most surveilled country in Europe

leverages FOSS technology

Other Programs

The SIGAD Used Most in NSA Reporting

there are more SIGINT tools

Presentations list FARVIEW and BLARNEY

Monitor ber cables and infrastructure

(IXPs?)

NSA collecting phone records of millions of

Verizon customers daily Guardian
We do not know all about PRISM. Repr. Sanches (D-Calif.), after
learning more during a brieng, said there is ... signicantly more
than what is out in the media today (...) I believe its the tip of
the iceberg.
Other Programs

The SIGAD Used Most in NSA Reporting

there are more SIGINT tools

Presentations list FARVIEW and BLARNEY

Monitor ber cables and infrastructure

(IXPs?)

NSA collecting phone records of millions of

Verizon customers daily Guardian
We do not know all about PRISM. Repr. Sanches (D-Calif.), after
learning more during a brieng, said there is ... signicantly more
than what is out in the media today (...) I believe its the tip of
the iceberg.
The Utah Data Center at Bludale
NSAs lastest expansion (2013):

1-1.5 million square feet

$2 billion building, $2 billion hardware

65 MW power consumption
SuperMuc: < 3 MW, 155,656 cores, 3 Peta FLOPS
Likely able to store and process all communication
Cyberwar
Presidential Policy Directive 20, issued October 2012 and released
by Edward Snowden, outlines U.S. cyberwar policy:
Oensive Cyber Eect Operations (OCEO) can oer unique and
unconventional capabilities to advance U.S. national objectives around
the world with little or no warning to the adversary or target and with
potential eects ranging from subtle to severely damaging. (...)
The United States Government shall identify potential targets of national
importance where OCEO can oer a favorable balance of eectiveness
and risk as compared with other instruments of national power, establish
and maintain OCEO capabilities integrated as appropriate with other
U.S. oensive capabilities, and execute those capabilities in a manner
consistent with the provisions of this directive.
Technical Cooperation
Bloomberg reports:

US companies provide internal information to US secret

services

Companies from software, banking, communications hardware

providers, network security rms

Including technical specications and unpatched software

vulnerabilities

In return, these US companies are given access to

intelligence information

Partners include: Microsoft, Intel, McAfee

History: ECHELON

SIGINT collection network

of AU, CA, NZ, UK and US

Baltimore Sun reported in

1995 that Airbus lost a $6
billion contract in 1994 after
NSA reported that Airbus
ocials had been bribing
ocials to secure the
contract.

Used to facilitate Kenetech

Windpowers espionage
against Enercon in
1994-1996.
Former US listening station at Teufelsberg, Berlin.
Does it matter?
MPI estimated losses due to industrial espionage damage
in 1988 at DM 8 billion.
So how does the EU react to learning about PRISM?
Direct access of US law enforcement to the data of EU citizens
on servers of US companies should be excluded unless in clearly
dened, exceptional and judicially reviewable situations.
Viviane Reding, EC vice-president in response to PRISM
Does it matter?
MPI estimated losses due to industrial espionage damage
in 1988 at DM 8 billion.
So how does the EU react to learning about PRISM?
Direct access of US law enforcement to the data of EU citizens
on servers of US companies should be excluded unless in clearly
dened, exceptional and judicially reviewable situations.
Viviane Reding, EC vice-president in response to PRISM
History: Irak War
Katharine Gun leaked memo from NSA agent Frank Koza in 2003
about an American eort to monitor the communications of six
delegations to the United Nations who were undecided on
authorizing the Iraq War and who were being ercely courted by
both sides:
As youve likely heard by now, the Agency is mounting a surge
particularly directed at the UN Security Council (UNSC) members
(minus US and GBR of course) for insights as to how to membership is
reacting to the on-going debate RE: Iraq, plans to vote on any related
resolutions, what related policies/negotiating positions they may be
considering, alliances/dependencies, etc the whole gamut of
information that could give US policymakers an edge in obtaining
results favorable to US goals or to head o surprises. In RT, that
means a QRC surge eort to revive/create eorts against UNSC
members Angola, Cameroon, Chile, Bulgaria and Guinea, as well as extra
focus on Pakistan UN matters.
Not Just Monitoring

US controls key Internet infrastructure:

Number resources (IANA)

Domain Name System (Root zone)

DNSSEC root certicate

X.509 CAs and browser vendors

Encryption does not help if PKI is compromised!

Political Solutions?
Ron Wyden (US Senate
intelligence committe) asked
James Clapper, director of
national intelligence in March
2013:
Does the NSA collect any
type of data at all on millions
or hundreds of millions of
Americans?
Clapper replied:
No, sir..
The Enemy Within
In February, the UK based research publication Statewatch
reported that the EU had secretely agreed to set up an
international telephone tapping network via a secret network of
committees established under the third pillar of the Mastricht
Treacty covering co-operation on law and order. (...) EU countries
(...) should agree on international interception standards (...)
to co-operate closely with the FBI (...). Network and service
providers in the EU will be obliged to install tappable systems and
to place under surveillance any person or group when served an
interception order. These plans have never been referred to any
European government for scrutiny (...) despite the clear civil
liberties issues raised by such an unaccountable system. (...)
The German government estimates that the mobile phone part of
the package alone will cost 4 billion D-marks.
Scientic and Technological Options Assessment (STOA), An Appraisal of Technologies of Political Control,
European Parliament, PE 166499, 6 January 1998.
Technical Solutions
Can we develop technologies to solve problems created by
technology?

Hack back?

Monitor them?

Move data to European cloud?

Decentralize data and trust!

Technical Solutions
Can we develop technologies to solve problems created by
technology?

Hack back?

Monitor them?

Move data to European cloud?

Decentralize data and trust!

Technical Solutions
Can we develop technologies to solve problems created by
technology?

Hack back?

Monitor them?

Move data to European cloud?

Decentralize data and trust!

Technical Solutions
Can we develop technologies to solve problems created by
technology?

Hack back?

Monitor them?

Move data to European cloud?

Decentralize data and trust!

Technical Solutions
Can we develop technologies to solve problems created by
technology?

Hack back?

Monitor them?

Move data to European cloud?

Decentralize data and trust!

Decentralize Everything

Encrypt everything end-to-end

Decentralized PKI

Decentralized data storage

No servers

No authorities
No jucy targets for APTs
Decentralize Everything

Encrypt everything end-to-end

Decentralized PKI

Decentralized data storage

No servers

No authorities
No jucy targets for APTs
Decentralized vs. Centralized
Decentralized: Centralized:
Slower
No economics of scale
More complex to use
More complex to develop
Hard to secure
Hard to evolve
Decentralized vs. Centralized
Decentralized: Centralized:
Slower Compromised
No economics of scale
More complex to use
More complex to develop
Hard to secure
Hard to evolve
My Research and Development Agenda
Make decentralized systems:

Faster, more scalable

Easier to develop, deploy and use

Easier to evolve and extend

Secure (privacy-preserving, censorship-resistant, available, ...)

Our Vision
Internet
Google/Facebook
DNS/X.509
TCP/UDP
IP/BGP
Ethernet
Phys. Layer
GNUnet
RegEx/PSYC
GADS
Mesh (ECDHE+AES)
R
5
N DHT
CORE (ECDHE+AES)
HTTPS/TCP/WLAN/...
Our Vision
Internet
Google/Facebook
DNS/X.509
TCP/UDP
IP/BGP
Ethernet
Phys. Layer
GNUnet
RegEx/PSYC
GADS
Mesh (ECDHE+AES)
R
5
N DHT
CORE (ECDHE+AES)
HTTPS/TCP/WLAN/...
Our Vision
Internet
Google/Facebook
DNS/X.509
TCP/UDP
IP/BGP
Ethernet
Phys. Layer
GNUnet
RegEx/PSYC
GADS
Mesh (ECDHE+AES)
R
5
N DHT
CORE (ECDHE+AES)
HTTPS/TCP/WLAN/...
Our Vision
Internet
Google/Facebook
DNS/X.509
TCP/UDP
IP/BGP
Ethernet
Phys. Layer
GNUnet
RegEx/PSYC
GADS
Mesh (ECDHE+AES)
R
5
N DHT
CORE (ECDHE+AES)
HTTPS/TCP/WLAN/...
Our Vision
Internet
Google/Facebook
DNS/X.509
TCP/UDP
IP/BGP
Ethernet
Phys. Layer
GNUnet
RegEx/PSYC
GADS
Mesh (ECDHE+AES)
R
5
N DHT
CORE (ECDHE+AES)
HTTPS/TCP/WLAN/...
Our Vision
Internet
Google/Facebook
DNS/X.509
TCP/UDP
IP/BGP
Ethernet
Phys. Layer
GNUnet
RegEx/PSYC
GADS
Mesh (ECDHE+AES)
R
5
N DHT
CORE (ECDHE+AES)
HTTPS/TCP/WLAN/...
Our Vision
Internet
Google/Facebook
DNS/X.509
TCP/UDP
IP/BGP
Ethernet
Phys. Layer
GNUnet
RegEx/PSYC
GADS
Mesh (ECDHE+AES)
R
5
N DHT
CORE (ECDHE+AES)
HTTPS/TCP/WLAN/...
Our Vision
Internet
Google/Facebook
DNS/X.509
TCP/UDP
IP/BGP
Ethernet
Phys. Layer
GNUnet
RegEx/PSYC
GADS
Mesh (ECDHE+AES)
R
5
N DHT
CORE (ECDHE+AES)
HTTPS/TCP/WLAN/...
Decentralized Naming Systems
1
Secure
Global Memorable Hierarchical Registration
C
r
y
p
t
o
g
r
a
p
h
i
c

I
d
e
n
t
i

e
r
s
P
e
t
n
a
m
e

S
y
s
t
e
m
s

m
n
e
m
o
n
i
c

U
R
L
s
c
e
r
t
i

c
a
t
e
s
S
D
S
I
Zookos Triangle
1
Joint work with Martin Schanzenbach and Matthias Wachs
The GNU Alternative Domain System (GADS)
Decentralized PKI that can also replace DNS/DNSSEC:

Signed Resource Records (RRs)

Secure delegation provides transitivity (SDSI)

Decentralized resolution (R
5
N DHT)

Every user manages his own zone

Zone Management: like in DNS
Name resolution in GADS

Bob wants to be called bob

Bob can reach his webserver via www.gads

Secure introduction
Bob Builder, Ph.D.
Address: Country, Street Name 23
Phone: 555-12345
Mobile: 666-54321
Mail: bob@H2R84L4JIL3G5C.zkey

Bob gives his public key to his friends via QR code

Bobs friends can resolve his records via *.petname.gads
Delegation

Alice learns Bobs public key

Alice creates delegation to zone bob

Alice can reach Bobs webserver via www.bob.gads

Name Resolution
DHT
GET www
'bob' 2
4 A: 5.6.7.8
5
Local Zone
.
.
.
3
bob PKEY K
Bob
pub
PKEY
.
.
.
www.bob.gnunet? 1
GADS as PKI (via DANE/TLSA)
GADS for GNUnet
Properties of GADS

Decentralized name system with secure memorable names

Decentralized name system with globally unique, secure

identiers

QR codes for introduction, delegation used to achieve

transitivity

Supports standard DNS record types

Can provide alternative PKI, validate TLS via TLSA records

Uses for GADS in GNUnet

Pseudonymous le-sharing

IP services in the P2P network (P2P-VPN) via VPN records

Identities in social networking applications

Our Vision
Internet
Google/Facebook
DNS/X.509
TCP/UDP
IP/BGP
Ethernet
Phys. Layer
GNUnet
RegEx/PSYC
GADS
Mesh (ECDHE+AES)
R
5
N DHT
CORE (ECDHE+AES)
HTTPS/TCP/WLAN/...
The Evolution Challenge
2

Features are frequently added to social applications

Some require changes (extensions) to data formats and

messages

Centralized, browser-based networks can easily update to new

version

Decentralized systems must transition gracefully

2
Joint work with Carlo v. Loesch and Gabor Toth
Related Work: GNU libtool
Here are a set of rules to help you update your library version
information:
1. Start with version information of 0:0:0 for each libtool library.
2. Update the version information only immediately before a
public release of your software. More frequent updates are
unnecessary, and only guarantee that the current interface
number gets larger faster.
3. If the library source code has changed at all since the last
update, then increment revision (c:r:a becomes c:r+1:a).
4. If any interfaces have been added, removed, or changed since
the last update, increment current, and set revision to 0.
5. If any interfaces have been added since the last public
release, then increment age.
6. If any interfaces have been removed or changed since the
last public release, then set age to 0.
taken from the GNU libtool manual.
Related Work: GNU libtool
There are three possible kinds of reactions from users of your
library to changes in a shared library:

Programs using the previous version may use the new version
as drop-in replacement, and programs using the new version
can also work with the previous one. In other words, no
recompiling nor relinking is needed. In this case, bump
revision only, dont touch current nor age.

Programs using the previous version may use the new version
as drop-in replacement, but programs using the new version
may use APIs not present in the previous one. In other
words, a program linking against the new version may fail with
unresolved symbols if linking against the old version at
runtime: set revision to 0, bump current and age.

Programs may need to be changed, recompiled, relinked

in order to use the new version. Bump current, set revision
and age to 0.
Related Work: XML

Extensible Markup Language

Syntax is extensible

Extensions have no semantics

PSYC
We are working on PSYC2, the successor to PSYC:

More compact, mostly human-readable, faster-to-parse

relative of XML/JSON/XMPP

PSYC messages consist of a state update and a method

invocation

PSYC includes interesting ideas for social networking:

Stateful multicast

History

Dierence-based updates

PSYC addresses extensibility problem using try-and-slice

pattern
PSYC State: Example
The PSYC state is a set of key-value pairs where the names of
keys use underscores to create an inheritance relationship:

name

name rst

name rst chinese

address

address street

address country
The data format for each state is xed for each top-level label.
PSYC Methods: Example
A PSYC method has a name which follows the same structure as
keys:

message

message private

message public

message public whisper

message announcement

message announcement anonymous

Methods have access to the current state and a per-message
byte-stream.
The Try-and-Slice Pattern
int msg (string method) {
while (1) {
switch (method) {
case "_notice_update_news": // handle news update
return 1;
case "_notice": // handle generic update
return 1;
case "_message": // handle generic message
return 1;
// ...
}
int glyph = strrpos (method, _);
if (glyph <= 1) break;
truncate (method, glyph);
}
}
Advantages of Try-and-Slice

Extensible, can support many applications

Can be applied to state and methods

Denes what backwards-compatible extensibility means:

Can incrementally expand implementations by deepening

coverage

Incompatible updates = introduce new top-level methods

PSYC2 for GNUnet
Properties of PSYC

Compact encoding (much smaller than XML/JSON/XMPP)

Supports stateful multicast

Supports message history (replay, see latest news, etc.)

Extensible synatx and semantics

Uses for PSYC2 in GNUnet

P2P social networking foundation (combine with GADS!)

Pushes social proles (state) to all recipients, no federation

Replay from local database used as primary access method

My data is stored on my machine

Use secure multicast to support very large groups

Our Vision
Internet
Google/Facebook
DNS/X.509
TCP/UDP
IP/BGP
Ethernet
Phys. Layer
GNUnet
RegEx/PSYC
GADS
Mesh (ECDHE+AES)
R
5
N DHT
CORE (ECDHE+AES)
HTTPS/TCP/WLAN/...
Distributed Search via Regular Expressions: Idea
3
1. Oerer creates regular expression describing service
2. Regular expression is converted to a DFA
3. DFA is stored in the DHT
4. Patron matches using a string
Offerer Patron
PUT GET
DFA
DHT
Search string
NFA
3
Joint work with Max Szengel, Ralph Holz, Bart Polot and Heiko
Niedermayer
Problem: Mapping of States to Keys
Regular expression (ab|cd)e

f and corresponding DFA

q0
a
c
(ab|cd)e* (ab|cd)e*f
a
c
d
b
f
e
DHT
h("(ab|cd)e*")
h("(ab|cd)e*f")
h("a")
h("c")
Problem: Merging of DFAs
Regular expressions (ab|cd)e

f and (ab|cd)e

fg

with
corresponding DFAs
q0
a
a
c
c
(ab|cd)e*
b
d
e
(ab|cd)e*f
f
q0
a
a
c
c
(ab|cd)e*
b
d
e
(ab|cd)e*fg*
f
g
Problem: Merging of DFAs
Merged NFA for regular expressions (ab|cd)e

fg

and (ab|cd)e

f
q0
a
a
c
c
(ab|cd)e*
b
d
e
(ab|cd)e*f
f
(ab|cd)e*fg*
f
g
Evaluation

Implementation in GNUnet

Proling of Internet-scale routing using regular expressions to

describe AS address ranges

CAIDA AS data set: Real AS data

Evaluation
AS 12816
129.187.0.0/16
131.159.0.0/16
138.244.0.0/15
138.246.0.0/16
...
192.68.211.0/24
192.68.212.0/22
Distributed Hash Table
AS 10001
49.128.128.0/19
61.195.240.0/20
122.49.192.0/21
123.255.240.0/21
175.41.32.0/21
202.75.112.0/20
202.238.32.0/20
210.48.128.0/21
211.133.224.0/20
219.124.0.0/20
219.124.0.0/21
219.124.8.0/21
AS 56357
188.95.232.0/22
192.48.107.0/24
AS 8265
91.223.12.0/24
195.96.192.0/19
195.96.192.0/24
195.96.193.0/24
195.96.194.0/23
195.96.196.0/22
195.96.200.0/22
195.96.204.0/22
195.96.208.0/21
195.96.216.0/21
AS 50038
57.236.47.0/24
57.236.48.0/24
57.236.51.0/24
193.104.87.0/24
AS 825
91.221.132.0/24
91.221.133.0/24
192.16.240.0/20
AS 32310
204.94.175.0/24
AS 931
46.183.152.0/21
103.10.233.0/24
186.233.120.0/21
186.233.120.0/22
186.233.124.0/22
AS 12812
193.188.128.0/24
193.188.129.0/24
193.188.130.0/24
193.188.131.0/24
AS 7212
129.59.0.0/16
160.129.0.0/16
192.111.108.0/24
192.111.109.0/24
192.111.110.0/24
199.78.112.0/24
199.78.113.0/24
199.78.114.0/24
199.78.115.0/24
AS 10002
61.114.64.0/20
61.195.128.0/20
120.50.224.0/19
120.72.0.0/20
202.180.192.0/20
Evaluation: Results of Simulation
Degree of non-determinism at states in the merged NFA
1
10
100
1000
10000
100000
1e+06
1e+07
1 2 3
#

s
t
a
t
e
s
degree of non-determinism
max path length 1
max path length 2
max path length 4
max path length 6
max path length 8
max path length 16
Dataset: All 40, 696 ASes
Evaluation: Results of Emulation
Search duration averaged over ve runs with randomly connected
peers.
0
10
20
30
40
50
60
70
80
90
100
0 5 10 15 20 25 30
%

o
f

m
a
t
c
h
e
d

s
t
r
i
n
g
s
Search duration in seconds
1,000 peers
2,000 peers
4,000 peers
RegEx Search for GNUnet
Properties of RegEx Search

Capability discovery in DHT-based P2P networks using

regular expressions

Linear latency in the length of the search string

Suitable for applications that can tolerate moderate latency

Uses for GADS in GNUnet

Network search

Discovery of matching services, such as VPN exit nodes

Topic-based subscriptions in messaging (decentralized MQTT)

Conclusion

Everybody has something to hide

Decentralization creates challenges for research

We must decentralize or risk to loose control over our lives.
Conclusion

Everybody has something to hide

Decentralization creates challenges for research

We must decentralize or risk to loose control over our lives.
Do you have any questions?
References:

Glenn Greenwald and Ewen MacAskill. NSA Prism program taps in to user data of Apple, Google and
others. In The Guardian, June 7 2013.

George Zornick. Remember When NSA Surveillance Was Used to Help Launch the Iraq War?. In The
Nation, June 11, 2013.

Michael Riley. U.S. Agencies Said to Swap Data With Thousands of Firms. In Bloomberg, Jun 14, 2013.

Rudolf Wagner. US-Spionage: Lauschangri auf die Konkurrenz in Europa. In Der Spiegel, Jan 7, 2001.

Gerhard Schmid. Report on the existence of a global system for the interception of private and commercial
communications (ECHELON interception system) (2001/2098(INI)). In European Parliament Session
Document, July 11, 2001.

Martin Asser. Echelon: Big brother without a cause? In BBC News Online, July 6, 2000.

Nathan Evans and Christian Grotho. R5N. Randomized Recursive Routing for Restricted-Route Networks.
5th International Conference on Network and System Security, 2011.

M. Schanzenbach Design and Implementation of a Censorship Resistant and Fully Decentralized Name
System. Masters Thesis (TUM), 2012.

M. Szengel. Decentralized Evaluation of Regular Expressions for Capability Discovery in Peer-to-Peer

Networks. Masters Thesis (TUM), 2012.
Problem: Decentralizing the Start State
Regular expression: abc

defg

h and k = 4.
abc*
c
abc*defg*
def
g
abc*defg*h
h
q0
ab
abcc
c
def
abcd
ef
abde
f
GNUnet: Framework Architecture
fs
dht
core
datastore mesh
ats
block nse datacache
peerinfo
hello
transport
exit
tun
vpn
regex
pt
dns
dv
set
gns
namestore
nat fragmentation
topology hostlist
consensus
GNUnet: Envisioned Applications
secushare
psyc voting gns fs reuters
messaging multicast consensus
mesh
dotproduct core
regex dht
ats
set
vpn exit