LIRA: Lightweight Incentivized Routing for Anonymity
This study delves into LIRA, a lightweight incentivized routing system designed for anonymity. The research, presented at the 20th Annual Network & Distributed System Security Symposium in 2013, focuses on enhancing routing techniques to bolster user privacy and security. Through encrypted Onion Routing and an exploration of Tor's performance and utilization, the project sheds light on improving network anonymity. It also delves into Tor's top exit relays and the distribution of bandwidth across relays. The findings provide valuable insights into strengthening online anonymity protocols.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
LIRA: Lightweight Incentivized Routing for Anonymity 20th Annual Network & Distributed System Security Symposium February 27, 2013 Rob Jansen Aaron Johnson Paul Syverson U.S. Naval Research Laboratory
Problem 2
encrypted Onion Routing unencrypted Destination User Onion Routers 3
encrypted Onion Routing unencrypted Destination User Onion Routers 4
encrypted Onion Routing unencrypted Destination User Onion Routers 5
encrypted Onion Routing unencrypted Destination User Onion Routers torproject.org 6
encrypted Onion Routing unencrypted Destination User Onion Routers torproject.org 7
Tor is Slow Web (320 KiB) Bulk (5 MiB) 8
Tor Utilization ~3000 relays 9
Tor Utilization ~500,000 users/day ~3000 relays 10
Tor Utilization Total relay bandwidth Advertised bandwidth Bandwidth history 3500 3000 2500 Bandwidth (MiB/s) 2000 1500 1000 500 0 Jan 2013 Feb 2013 Dec 2012 The Tor Project https://metrics.torproject.org/ 11
Tors Top 20 Exit Relays Exit Probability Advertised Bandwidth Nickname Country DE DE US NL DE DE NL SE RO DE DE SE DK US DE SE US US DE SE 7.25% 6.35% 5.92% 3.60% 3.35% 3.32% 3.26% 2.32% 2.23% 2.22% 2.05% 1.93% 1.82% 1.67% 1.53% 1.31% 1.26% 1.13% 0.84% 0.76% 0.87%chaoscomputerclub18 0.93%chaoscomputerclub20 1.48%herngaard 0.66%chomsky 1.17%dorrisdeebrown 1.18%bolobolo1 0.65%rainbowwarrior 0.36%sdnettor01 0.69%TheSignul 0.41%raskin 0.40%bouazizi 0.65%assk 0.39%kramse 0.35%BostonUCompSci 0.40%bach 0.73%DFRI0 0.31%Amunet2 0.27%Amunet8 0.27%chaoscomputerclub28 0.37%DFRI3 Total: 54.14% compass.torproject.org 12
Flows 3% Bytes 40% 2008* 58% 92% BitTorrent HTTP Other 11% 2010** 52% 36% 69% *McCoy et al. PETS 2008, **Chaabane et al. NSS 2010 13
Our Solution 14
Incentive Scheme LIRA Relays own traffic gets better performance 15
Incentive Schemes LIRA Gold star Tortoise BRAIDS Freedom PAR XPay Relays own traffic gets better performance Charge users, pay relays 16
Incentive Schemes External payment Non-relays pay Efficiency concerns Anonymity concerns Freedom PAR XPay Gold star Tortoise BRAIDS 17
prioritized Anonymous Incentives normal Problem: Priority identifies user as a relay
prioritized Anonymous Incentives normal Problem: Priority identifies user as a relay Solutions 1. Give some priority tickets to all users (BRAIDS).
prioritized Anonymous Incentives normal Problem: Priority identifies user as a relay Solutions 1. Give some priority tickets to all users (BRAIDS). 2. Cryptographic lottery gives priority; winning tickets can be (secretly) bought (LIRA).
LIRA Design Bank
LIRA Design Bank gives anonymous coins to relays based on amount of traffic forwarded
LIRA Design Bank sets up lottery with each relay
LIRA Design Buy winners with coins
LIRA Design Clients guess winners
LIRA Design Priority scheduling
Cryptographic Lotteries Lottery at relay r gr: {0,1}2L {0,1}2L x wins if gr(x) = y0|| y1 0 y0 y1< p 2L 27
Cryptographic Lotteries Lottery at relay r gr: {0,1}2L {0,1}2L x wins if gr(x) = y0|| y1 0 y0 y1< p 2L gr defined from PRF fr using a Luby-Rackoff- like construction y0 = fr(x1) x0 y1 = fr(y0) x1 gr(x) = y0|| y1 28
Cryptographic Lotteries Lottery at relay r gr: {0,1}2L {0,1}2L x wins if gr(x) = y0|| y1 0 y0 y1< p 2L gr defined from PRF fr using a Luby-Rackoff- like construction y0 = fr(x1) x0 y1 = fr(y0) x1 gr(x) = y0|| y1 fr(x) = H(x(H(H(x) xrd))) H is a hash function xr ispublic;bank gives xrd to r during setup, dis bank s private RSA key 29
Analysis 30
Efficiency LIRA 127.5+127.5f (256B/sig) BRAIDS 637.5 (488 B/sig) Blind signatures/s Bank Priority verification 6 hashes (18 us) PBS verify (1500 us) Relay Normal Client Tickets / connection 0 1 f is fraction of credit redeemed. Entire network is transferring 1700 MiB/s. Signature size: 1024 bits. Ticket size: 320 bits. Linux OpenSSL benchmarks on Intel Core2 Duo 2.67 GHz 31
Anonymity With m buyers and n guessers, the probability that a prioritized circuit source is a given buyer is 1 / (m + np3) compared to 1/(m+n) without priority. Linked priority degrades anonymity exponentially to 1/m. 32
Performance Bulk (5 MiB) Web (320 KiB)
Performance, More Capacity Bulk (5 MiB) Web (320 KiB)
Conclusion 1. Volunteer-run Tor network is overloaded. 2. LIRA provides incentives to contribute by rewards with better network performance. 3. LIRA is more efficient than previous schemes while maintaining anonymity. 4. Full-network experiments demonstrate better performance and scalability. 35
Buying winning tickets Client chooses y0, y1, 0 y0 XOR y1 < p2L Using using PRF protocol, client reverses Luby-Rackoff process to get gr-1(y0 || y1). Client c and bank B evaluate fr(x) 1. C sends aexrd to B, a random. 2. B returns abxrd, b random. 3. c sends b H(x)xrd to B. 4. B returns H(H(x)xrd) to c. 5. c outputs fr(x) = H(x H(H(x)xrd)). PRF Protocol 36
Winning circuits are prioritized 1. Client sends tickets to each relay in circuit. 2. Relays evaluate tickets. Winners must have unseen PRF inputs. Neighbors sent results. 3. If ticket wins and neighbors report wins, circuit is prioritized for next bytes. 37
Priority Scheduling Proportional Differentiated Services Split traffic into paid and unpaid classes Prioritize classes using quality differentiation parameters piand quality measure Q (EWMA) p1/p2 = Q1( t) / Q2( t) 38
Bank secrecy (honest-but-curious) Clients oblivious to xrd. B cannot produce r, input x, or output fr(x). Relay purchases are batched, preventing bank from knowing when prioritized circuits are constructed. c and B evaluate fr(x) 1. c obtains bxrd. 2. c sends b H(x)xrd to B. 3. B sends H(H(x)xrd) to c. 4. c outputs H(x(H(H(x)xrd))). PRF Protocol 39
Creating winning tickets fr is random in ROM when xrd unknown. y0XOR y1 is random. for y0or y1 unknown One-time-use inputs to fr prevent double spending. Tickets not fully purchased win with probability p. fr(x) = H(x(H(H(x) xrd))) y0 = fr(x1) y1 = fr(y0) gr(x) = y0|| y1 x0 x1 0 y0 y1< p 2L Cryptographic Lottery 40
