The Design and Implementation of
Network Puzzles

Wu-chang Feng, Ed Kaiser, Wu-chi Feng

Antoine Luu

Supported by:

Motivation

Undesirable communication is uncontrollable

Spam

Viruses

Worms

Port scans

Denial of service

Phishing

Puzzles

An interesting approach for mitigating undesirable activity...

Force client to spend its own resources before providing service

Currently for e-mail, authentication protocols, transport layers

Example: Yahoo! account captcha

Why network puzzles?

What do these attacks have in common?

IP flood

Smurf

Fraggle

SYN flood

Slammer

DNS poison

Code Red

Melissa

Morris worm

Why network puzzles?

What do these attacks have in common?

IP flood => IP

Smurf => ICMP IP

Fraggle => UDP IP

SYN flood => TCP IP

Slammer => MS-SQL UDP IP

DNS poison => domain UDP IP

Code Red => HTTP TCP IP

Melissa => SMTP TCP IP

Morris worm => finger TCP IP

Why network puzzles?

What do these attacks have in common?

IP flood => IP

Smurf => ICMP IP

Fraggle => UDP IP

SYN flood => TCP IP

Slammer => MS-SQL UDP IP

DNS poison => domain UDP IP

Code Red => HTTP TCP IP

Melissa => SMTP TCP IP

Morris worm => finger TCP IP

To protect against arbitrary attacks,

mechanism must be placed in a common layer

Goals

Build an effective IP puzzle mechanism

Build effective controllers for mechanism

Goals

Build an effective IP puzzle mechanism

Tamper-resistance

Prevent innocent client from answering bogus puzzles

From spoofed traffic

From spoofed puzzles

Prevent malicious clients from avoiding work

Answer forging

Answer replay between flows and across time

Performance

Puzzle issuing

Fast puzzle generation

Low packet overhead

Puzzle verification

Fast answer verification

Constant state at issuer

Low memory overhead

Build effective controllers for mechanism

Rest of talk

Protocol framework

Puzzle algorithms

Prototype implementation

Evaluation

Basic protocol

Based on

TCP SYN cookies [Bernstein1997]

Puzzle-protected authentication systems [Aura2001, Leiwo2000]

Features

Fixed-state (i.e. a single server nonce)

Resistant to puzzle spoofing

What about....

Brute-force attacks on Ns

Randomly generated circular nonce array continuously updated

Efficient verification

Add logical timestamp to index into circular nonce array (O(1) lookup)

Replay across flows

Add flow information to hash signature

Infinite replay over time

Add puzzle expiration time to hash signature

Streaming applications

Issue puzzles ahead of time to client

Add puzzle maturity time to hash signature

Final protocol design

Have a framework, need a mechanism

Can one develop a puzzle algorithm that can support….

Puzzle generation at line speed

Puzzle verification at line speed

Fine-grained control of puzzle difficulty

Puzzle algorithms

Time-lock puzzles

Hash reversal

Multiple hash reversal

Our approach

Hint-based hash reversals

Time-lock Puzzles

Based on notion of repeated squaring [Rivest,Shamir,Wagner]

Fine-grained control over difficulty

Multiples of squaring time (~1µs)

Slow to generate (~2ms)

2t(mod ((p-1)(q-1)))

ae(mod pq)

Hash reversal puzzles

Based on reversing a cryptographic hash

Brute-force search of input space to find match

Coarse-grained control over difficulty

Difficulty growth as powers of 2

Fast to generate (~1µs)

Hardware support for hashing common

IXP 2850

Multiple hash reversal puzzles

Reverse multiple hashes

Finer control of difficulty

Support O(210+211) difficulty?

One 11-bit hash = too easy

One 12-bit hash = too hard

One 10-bit hash and one 11-bit hash = just right

Fast to generate, but…

Linear increase in generation overhead over single hash

Linear increase in space/bandwidth for puzzle

Multiple hash reversal puzzles

Difficulty levels supported versus number of puzzles

Our approach

Hint-based hash reversal

Reverse a single hash given a hint where the answer lies

Issuer generates h(x)=y

Issuer passes back

Puzzle (y)

Randomly generated hint (x-u(0,2D))

Client performs brute-force search starting from hint

Characteristics

Fast to generate (~1µs)

Fine-grain difficulty adjustment

Difficulty adjusted via range adjustment

Multiples of hash time (~1µs)

o

Generation comparison

Measured across 10,000 puzzles

Granularity comparison

Actual difficulty levels on 1.8GHz Pentium 4

Granularity comparison

Derived analytically…

Puzzle-protected IP protocol

Implemented within IP

2 new IP options

1 new ICMP message

Allows for transparent deployment

Can run between proxies and firewalls

No modification to end-hosts required

Proxies

Can attach nonces on behalf of clients

Can answer puzzles and attach answers on behalf of clients

Firewalls

Can issue and verify puzzles on behalf of servers

Puzzle client IP options

Client cookie

Puzzle answer

Puzzle server ICMP message

ICMP type 38

“Mandatory source quench”

In action

“Route this packet”

“Solve this first”

“Route this packet

Here is the answer”

“Packet with correct

answer, route it!”

Puzzle-protected IP implementation

Linux via iptables/netfilter

No kernel modifications

Minimal modifications to iptables to add puzzle module hooks

Compatibility with pre-existing iptables rulesets

Client, server, proxy, firewall implementations via simple rule configuration

Example #1: Simple client and server

Server issues puzzles on all incoming TCP SYN segments without a valid puzzle answer

Server

Client

tcpdump trace

ak47% insmod ./puzzlenet_mgr.o

ak47% insmod ./ipt_puzClient.o

ak47% iptables –t mangle –A INPUT –p icmp –icmp-type 38 –j puzClient

ak47% iptables –t mangle –A POSTROUTING –j puzClient

ak47%

ak47% telnet mp5

Trying 10.0.0.7…

Connected to 10.0.0.7.

Escape character is ‘^]’.

mp5% insmod ./puzzlenet_mgr.o

mp5% insmod ./ipt_puzServer.o

mp5% iptables –t mangle –A INPUT –p tcp –-syn –j puzServer

17:09:28.983779 10.0.0.6.12799 > 10.0.0.7.23: S

17:09:28.983822 10.0.0.7 > 10.0.0.6: icmp: type-#38

17:09:31.980573 10.0.0.6.12799 > 10.0.0.7.23: S

17:09:31.980637 10.0.0.7.23 > 10.0.0.6.12799: S ack

ak47 (10.0.0.6)

mp5 (10.0.0.7)

Example #2: Proxy and firewall

Firewall issues puzzles on all packets without valid answer

Proxy attaches nonces and answers puzzles on behalf of all clients

Firewall

Proxy

proxy% insmod ./puzzlenet_mgr.o

proxy% insmod ./ipt_puzClient.o

proxy% iptables –t mangle –A INPUT –p icmp –icmp-type 38 –j puzClient

proxy% iptables –t mangle –A FORWARD –p icmp –icmp-type 38 –j puzClient

proxy% iptables –t mangle –A POSTROUTING –j puzClient

firewall% insmod ./puzzlenet_mgr.o

firewall% insmod ./ipt_puzServer.o

firewall% iptables –t mangle –A INPUT –j puzServer

firewall% iptables –t mangle –A FORWARD –j puzServer

Example #2: Proxy and firewall

Client (ak47)

Connection to closed port on server (mp5)

Connection to non-existent machine

tcpdump trace

10.0.1.2

17:12:53.632512 10.0.0.6.14698 > 10.0.2.6.2601: S
17:12:53.632566 10.0.1.2 > 10.0.0.6: icmp: type-#38
17:12:56.630212 10.0.0.6.14698 > 10.0.2.6.2601: S
17:12:56.630287 10.0.2.6.2601 > 10.0.0.6.14698: R

17:13:05.456542 10.0.0.6.14699 > 10.0.2.123: S

17:13:05.455725 10.0.1.2 > 10.0.0.6: icmp: type-#38

17:13:08.454862 10.0.0.6.14699 > 10.0.2.123: S

17:13:14.453935 10.0.0.6.14699 > 10.0.2.123: S

proxy

firewall

ak47 (10.0.0.6)

mp5 (10.0.2.6)

ak47% telnet mp5 2601

Trying 10.0.2.6…

telnet: Unable to connect to remote host: Connection refused

ak47% telnet 10.0.2.123

Trying 10.0.2.123…

IP puzzle scenario revisited

Thwarting port and machine scanning

Status

iptables/netfilter implementation (< 500 LoC)

Tamper-resistance

Tamper-proof operation (must be along path to deny service)

Performance

Constant-state puzzle issuer

180,000 puzzles/sec on commodity hardware

~1Gbs for per-packet puzzles with MTU packets

Puzzle generation ~1µs

Puzzle verification ~1µs

Small packet overhead

Puzzle question ~40 bytes

Puzzle answer ~20 bytes

Low latency

Can play puzzle-protected Counter-strike transparently

Prototype IXP 2400/2850 implementation underway

Future work

Publicly auditable puzzles

Multiple issuers along path

Extra round-trips and puzzle messages

IP header limitations (40 byte limit => 1 answer)

Lightweight cryptographic primitives

Require nanosecond operation in high-speed routers

Do not require the strength of current cryptographic primitives

Puzzle control

Control algorithms similar to AQM

“Reputation-based networking”

Questions?

http://syn.cs.pdx.edu/projects/puzzles

What about reflector attacks?

No worse than TCP SYN reflector attacks

Can push issuer arbitrarily close to source

Do not need to issue a puzzle on every packet

What about slow path processing of IP options?

Does not require hop-by-hop processing

Routers not participating can forward immediately

What about launching DoS attacks on issuer?

Fast puzzle generation reduces impact of traffic spoofing attack

Fast verification reduces impact of answer spoofing attack

Constant-state issuer prevents flooding attacks

Questions?

http://syn.cs.pdx.edu/projects/puzzles

Wu-chang Feng, Ed Kaiser, Wu-chi Feng, Antoine Luu, “The Design and

Implementation of Network Puzzles”, IEEE INFOCOM 2005, March 2005.

Ed Kaiser, Wu-chang Feng, Wu-chi Feng, Antoine Luu, “Reducing Malicious

Traffic with IP Puzzles”, ACM SIGCOMM 2004/USENIX Security Symposium

(poster session), August 2004.

Wu-chang Feng, “The Case for TCP/IP Puzzles”, ACM SIGCOMM Future

Directions in Network Architecture, August 2003.

Future work

Have a decent hammer

Need to make it better

Other proof-of-work mechanisms

T-function puzzles

Publicly auditable puzzles

Implementation on other platforms (Intel IXP2850)

Need to learn how to use it

Build systems that can learn about...

Desirable and undesirable communication activity

Good and bad hosts

Selectively and automatically deploy puzzles to protect the Internet

Internet-scale Immune System

“Risk adaptable network access control”

Motivation

A quick look back on 15 years of not so “Good Times”

1988

1993

1998

2003

Morris worm

Christmas

Michaelangelo

Melissa

LoveLetter

Nimda

Sircam

Code Red

Klez

SoBig

Fizzer

Slammer

Blaster

Smurf

Fraggle

SYN flood

Nachi

Deloder

SMTP, TCP, ICMP, UDP, FastTrack, SMB, finger, SSL, SQL, etc.

Outline

IP puzzles

Motivation

Challenges

Design, implementation, and evaluation of a prototype

On-going work

Understanding the basic protocol

Client nonce

Client attaches nonce that server must echo in puzzle message

Prevents bad guy from spoofing a puzzle to the client

Server nonce and puzzle generation

Server generates puzzle/answer on the fly

Uses secret nonce to “sign” a hash of the answer

Sends puzzle along with above hash

Throws away the puzzle and answer

Client response

Attaches answer along with signed hash

Server verifies valid answer via correctly signed hash

IP puzzle scenario #2

Coordinated DDoS: simultaneous attacks against multiple sites from the same set of zombie machines

Mafiaboy (2000)

Have zombies initiate low bandwidth attacks on a diverse set of victims to evade localized detection techniques (such as mod_dosevasive)

IP puzzle scenario #2

Mitigation using IP puzzles

Why are IP puzzles a bad idea?
(What are the opportunities for research?)

Tamper-resistance

Performance

Control

Fairness

Tamper-resistance

A tool to both prevent and initiate DoS attacks

Disable a client by...

Spoofing bogus puzzle questions to it

Spoofing its traffic to unfairly trigger puzzles against it

Disable a router or server by...

Forcing it to issue loads of puzzles

Forcing it to verify loads of bogus puzzle answers

Replaying puzzle answers at high-speed

Performance

Must support low-latency, high-throughput operation

Must not add latency for applications such as on-line games

Must support high-speed transfers

Must not add large amounts of packet overhead

Determines the granularity at which puzzles are applied

Per byte? Per packet? Per flow? Per aggregate?

Driven by performance and level of protection required

Mechanism must allow for flexible use

Control

Control algorithms required to maintain high utilization and low loss

Mandatory, multi-resolution ECN signals that can be given at any time granularity

Can apply ideas from TCP/AQM control

Adapt puzzle difficulty within network based on load and user behavior

Adapt end-host response to maximize throughput while minimizing system resource consumption

Natural game theoretic operation (if done correctly)

Fairness

202.183.197.116 - - [02/Jun/2003:02:08:29 -0700] "GET /default.ida?XXXXXXXXXXXXX

XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX%u9090%u6858%ucbd3%u7801%u909

0%u6858%ucbd3%u7801%u9090%u6858%ucbd3%u7801%u9090%u9090%u8190%u00c3%u0003%u8b00%

u531b%u53ff%u0078%u0000%u00=a HTTP/1.0" 404 306 "-" "-"

Minimize work for “good citizens”, maximize work for bad ones

Problem: mechanism is in a layer with minimal information

Can support bandwidth-based puzzle delivery

Can support some differentiation to deter Smurf/Fraggle

Would like to knock this guy out….

Need a “puzzle manager”

Drive puzzle difficulty based on application input and learning algs.

2005-03-17T05:21:24