advertisement

ieee sp 2004

40 %
60 %
advertisement
Information about ieee sp 2004
Education

Published on June 18, 2007

Author: Breezy

Source: authorstream.com

advertisement

On-The-Fly Verification of Rateless Erasure Codes:  On-The-Fly Verification of Rateless Erasure Codes Max Krohn (MIT CSAIL) Michael Freedman and David Mazières (NYU) On-The-Fly Verification of Rateless Erasure Codes:  On-The-Fly Verification of Rateless Erasure Codes Max Krohn (MIT CSAIL) Michael Freedman and David Mazières (NYU) Multicast Authentication: Dead/Exhausted The Setting:  The Setting A large file F Linux ISO (650MB) H(F) is available signed by Publisher (RedHat) A handful of untrusted sources/mirrors S1,…S8 A Handful of Senders:  A Handful of Senders The Setting:  The Setting A large file F Linux ISO (650MB) H(F) is available signed by Publisher (RedHat) A handful of untrusted sources S1,…S8 Their aggregate BW is limited A slew of receivers R1,...,R1,000,000 Version 81.3 just released! Want it Now! Three Desirable Properties:  Three Desirable Properties Sources Can Multicast Clients Get Fast Downloads Clients Can Verify Blocks On-the-Fly Receivers Get Fast, Verifiable Downloads:  Receivers Get Fast, Verifiable Downloads The trusted publisher (RedHat) Splits up F into n blocks Hashes all blocks Signs all hashes (or hash tree) Receivers: Download and verify hashes Download needed file blocks in parallel Everyone for Themselves:  R1 S1 S3 S4 S2 R3 R2 R4 R5 R6 R7 R8 R9 R10 R11 R12 R13 Everyone for Themselves Everyone For Themselves:  Everyone For Themselves Sources Can Multicast Clients Get Fast Downloads Clients Can Verify Blocks On-the-Fly Verifiable Multicast (BitTorrent):  R1 S1 S3 S4 S2 R3 R2 R4 R5 R6 R7 R8 R9 R10 R11 R12 R13 Verifiable Multicast (BitTorrent) Verifiable Multicast (BitTorrent):  Verifiable Multicast (BitTorrent) Sources Can Multicast Clients Get Fast Downloads Clients Can Verify Blocks On-the-Fly Multicast With Erasure Codes:  Multicast With Erasure Codes Sources erasure encode the file F n blocks blocks F Multicast With Erasure Codes:  Multicast With Erasure Codes Sources erasure encode the file F Receivers collect blocks and decode n blocks blocks 1.03n blocks n blocks F F … … … … … Multicast With Erasure Codes:  R1 S1 S3 S4 S2 R3 R2 R4 R5 R6 R7 R8 R9 R10 R11 R12 R13 Multicast With Erasure Codes Multicast With Erasure Codes:  Multicast With Erasure Codes Bullet [SOSP 2003] SplitStream [SOSP 2003] Big Downloads [IPTPS 2003] Informed Content Delivery [SIGCOMM 2002] Receivers Cannot Verify Content:  R1 S1 S3 S4 S2 Receivers Cannot Verify Content ? ? ? ? ? ? ? ? ? ? ? ? ? ? Receivers Cannot Verify Content:  Receivers Cannot Verify Content R1 S1 S3 S4 S2 ? ? ? ? ? ? ? ? ? ? Multicast With Erasure Codes:  Multicast With Erasure Codes Sources Can Multicast Clients Get Fast Downloads Clients Can Verify Blocks On-the-Fly Multicast With Erasure Codes:  Multicast With Erasure Codes Sources Can Multicast Clients Get Fast Downloads Clients Can Verify Blocks On-the-Fly What is the Attack Goal?:  What is the Attack Goal? To corrupt the file. To waste bandwidth. R S1 S3 S2 How To Attack?:  How To Attack? Send correct blocks but with skewed distributions. 'Distribution Attack' Send incorrect blocks 'Pollution Attack' Karlof et al. [NDSS ’04] R S1 S3 S2 Properties of a Solution to Pollution:  Properties of a Solution to Pollution OK: Receivers can tell good from bad. Much better: Receivers can finger bad blocks as they arrive. R S1 S3 S2 CONTRIBUTION Outline:  Outline Introduction Review of LT Codes Strawman #1 Strawman #2 Efficiently Catching Bad Blocks as They Arrive LT-Codes [Luby, FOCS 2002]:  LT-Codes [Luby, FOCS 2002] b1 b2 b3 b4 b5 F= n=5 input blocks LT-Codes – How To Encode:  LT-Codes – How To Encode b1 b2 b3 b4 b5 c1 Pick degree d1 from a pre-specified distribution. (d1=2) Select d1 input blocks uniformly at random. (Pick b1 and b4 ) Compute their sum. Output E(F)= F= LT-Codes – How To Encode (cont’d):  LT-Codes – How To Encode (cont’d) b1 b2 b3 b4 b5 c1 c2 c3 c4 c5 c6 c7 E(F)= F= How To Decode:  How To Decode b1 b2 b3 b4 b5 c1 c2 c3 c4 c5 c6 c7 E(F)= F= How To Decode:  How To Decode b1 b2 b3 b4 b5 c1 c2 c3 c4 c5 c6 c7 E(F)= F= How To Decode:  How To Decode b1 b2 b3 b4 b5 c1 c2 c3 c4 c5 c6 c7 E(F)= F= How To Decode:  b1 b2 b3 b4 b5 c1 c2 c3 c4 c5 c6 c7 E(F)= F= How To Decode How To Decode:  How To Decode b1 b2 b3 b4 b5 c1 c2 c3 c4 c5 c6 c7 E(F)= F= b5 b5 b5 How To Decode:  How To Decode b1 b2 b3 b4 b5 c1 c2 c3 c5 c6 c7 E(F)= F= b5 b5 How To Decode:  How To Decode b1 b2 b3 b4 b5 c1 c2 c3 c5 c6 c7 E(F)= F= b5 b5 How To Decode:  How To Decode b1 b2 b3 b4 b5 c1 c2 c3 c5 c6 c7 E(F)= F= b5 b5 How To Decode:  How To Decode b1 b2 b3 b4 b5 c1 c2 c3 c5 c6 c7 E(F)= F= b5 b5 b2 b2 How To Decode:  How To Decode b1 b2 b3 b4 b5 c1 c2 c3 c5 c6 c7 E(F)= F= b5 b5 b2 b2 Outline:  Outline Introduction Review of LT Codes Strawman #1 Simple Solution To Tell Good Blocks From Bad Strawman #2 Efficiently Catching Bad Blocks as They Arrive “Smart Decoder” for LT-Codes:  'Smart Decoder' for LT-Codes b1 b2 b3 b4 b5 c1 c2 c3 c4 c5 c6 c7 E(F)= F= “Smart Decoder” for LT-Codes:  'Smart Decoder' for LT-Codes b1 b2 b3 b4 b5 c1 c2 c3 c4 c5 c6 c7 E(F)= F= “Smart Decoder” for LT-Codes:  'Smart Decoder' for LT-Codes b1 b2 b3 b4 b5 c1 c2 c3 c4 c5 c6 c7 E(F)= F= “Smart Decoder” for LT-Codes:  'Smart Decoder' for LT-Codes b1 b2 b3 b4 b5 c1 c2 c3 c4 c5 c6 c7 E(F)= F= “Smart Decoder” for LT-Codes:  'Smart Decoder' for LT-Codes b1 b2 b3 b4 b5 c1 c2 c3 c4 c5 c6 c7 E(F)= F= “Smart Decoder” for LT-Codes:  'Smart Decoder' for LT-Codes b1 b2 b3 b4 b5 c1 c2 c3 c4 c5 c6 c7 E(F)= F= b5 b5 b5 “Smart Decoder” for LT-Codes:  'Smart Decoder' for LT-Codes b1 b2 b3 b4 b5 c1 c2 c3 c4 c5 c6 c7 E(F)= F= b5 b5 b5 “Smart Decoder” for LT-Codes:  'Smart Decoder' for LT-Codes b1 b2 b3 b4 b5 c1 c2 c3 c4 c5 c6 c7 E(F)= F= b5 b5 b5 X “Smart Decoder” for LT-Codes:  'Smart Decoder' for LT-Codes b1 b2 b3 b4 b5 c1 c2 c3 c4 c5 c6 c7 E(F)= F= b5 b5 b5 X “Smart Decoder” for LT-Codes:  'Smart Decoder' for LT-Codes b1 b2 b3 b4 b5 c1 c2 c3 c4 c5 c6 c7 E(F)= F= b5 b5 b5 “Smart Decoder:” Problem:  'Smart Decoder:' Problem Data collected from 50 random Online encodings of a 10,000 block file. Outline:  Outline Introduction Review of LT Codes Strawman #1 Strawman #2 Hashing/Signing Encoded Blocks Efficiently Catching the Bad as They Arrive Hashing/Signing Encoded Blocks:  Hashing/Signing Encoded Blocks Trusted Publisher (RedHat) Picks e, computes e·n encoded blocks Hashes all encoded blocks Signs the hashes. n blocks e·n blocks F Hashing/Signing Encoded Blocks:  Hashing/Signing Encoded Blocks Expansion factor e should be big to avoid duplicate blocks. e should be small to make crypto overhead acceptable. Our analysis shows there’s no 'sweet spot'. Hashing/Signing Encoded Blocks:  Hashing/Signing Encoded Blocks Expansion factor e should be big to avoid duplicate blocks. e should be small to make crypto overhead acceptable. Our analysis shows there’s no 'sweet spot'. e.g., best case bandwidth requirements: +5% e.g., generating hashes is very expensive as e gets large. Outline:  Outline Introduction Review of LT Codes Strawman #1 Strawman #2 Efficiently Catching the Bad as They Arrive Best of Both Worlds :  Best of Both Worlds Goal: Crypto overhead of one hash for every block in the input file (Strawman #1) Verify blocks as they arrive (Strawman #2) Idea: Distribute hashes of file blocks, and use them to verify encoded blocks. Need a better hash function. Insight: Homomorphic Hashing:  Insight: Homomorphic Hashing Assume function h exists such that: is homomorphic: is a CRHF: Homomorphic Hashing: Intuition:  Homomorphic Hashing: Intuition R receives the block c b2 b5 c Homomorphic Hashing: Intuition:  Homomorphic Hashing: Intuition c b2 b5 c R receives the block Homomorphic Hashing: Intuition:  Homomorphic Hashing: Intuition c b2 b5 c R receives the block Homomorphic Hashing: Intuition:  Homomorphic Hashing: Intuition R receives the block Homomorphic Hashing: Intuition:  Homomorphic Hashing: Intuition Property 1 R receives the block Homomorphic Hashing: Intuition:  Homomorphic Hashing: Intuition Property 1 Property 2 R receives the block Homomorphic Hashing: Protocol:  Homomorphic Hashing: Protocol R receives the block Compute h(c) If Accept block; mark as valid else Suspect sender of being bad guy, and switch. Homomorphic Hashing: Protocol:  Homomorphic Hashing: Protocol R receives the block Compute h(c) If Accept block; mark as valid else Suspect sender of being bad guy, and switch. Can such an h possibly exist? Homomorphic Hashing: Related Work:  Homomorphic Hashing: Related Work DLog-Based CRHF Pederson Commitment [CRYPTO ’91] Chaum et al. [CRYPTO ’91] One-Way Accumulators Benaloh and de Mare [EUROCRYPT ’93] Barić and Pfitzmann [EUROCRYPT ’93] Incremental Hashing Bellare et al. [CRYPTO ’94] Homomorphic Signatures Micali and Rivest [RSA ’02] Johnson et al. [RSA ’02] Mechanics of Homomorphic Hashing:  Mechanics of Homomorphic Hashing Discrete Log Hash Pick 1024-bit prime p and 256-bit prime q, q divides (p-1) Pick from 512 generators of order q: Write F as elements in F= 256-bit 'fragment' 16K 'block' How to Encode (example):  How to Encode (example) How To DLog Hash:  How To DLog Hash Hashes are elements in (128 bytes big) Hash reduces 16K block by a factor of 128 How To DLog Hash:  How To DLog Hash Hashes are elements in (128 bytes big) Hash reduces 16K block by a factor of 128 +1% overhead DLog-Hash: Key Property:  DLog-Hash: Key Property Note that: DLog-Hash: Key Property:  DLog-Hash: Key Property Note that: Goal achieved! “This Seems Really Expensive”:  'This Seems Really Expensive' Key Optimizations:  Key Optimizations Hash Generation Each publisher picks her own parameters, compute with 1 exponentiation (not 512) Hash Verification Receiver verifies hashes probabilistically and in batches. Bellare et al. [EUROCRYPT ’98] Much Better:  Much Better Homomorphic Hashing: Key Points:  Homomorphic Hashing: Key Points Key Algebraic Feature Homomorphism: Receivers can compose hashes the way encoders sum file blocks. Can check encoded blocks as they arrive. Fast Can be optimized to achieve good generation and verification throughputs Provably Secure As hard as discrete log (SHA1/MD5 not needed) Conclusion:  Conclusion Sources Can Multicast Clients Get Fast Downloads Clients Can Verify Blocks On-the-Fly Thank you.:  Thank you. Now accepting questions.

Add a comment

Related presentations

Related pages

IEEE - The world's largest technical professional ...

IEEE.org serves technical professionals and students who are looking to both foster working relationships and gain access to the latest technical research ...
Read more

IEEE Symposium on Security and Privacy and Euro S&P

IEEE Symposium on Security and Privacy. ... The debut of the IEEE European Privacy and Security Symposium ... SP Conference Information.
Read more

dblp: IEEE Symposium on Security and Privacy 2004

conf/sp/2004; ask others. Google; Google Scholar; MS Academic Search; ... (S&P 2004), 9-12 May 2004, Berkeley, CA, USA. IEEE Computer Society 2004, ISBN 0 ...
Read more

IEEE Xplore Digital Library

IEEE Xplore Digital Library; IEEE-SA; IEEE Spectrum; More Sites; cartProfile.cartItemQty ; Create Account; Personal Sign In; Personal Sign In. Username ...
Read more

2004 IEEE Symposium on Security and Privacy Home Page

2004 IEEE Symposium on Security and Privacy. May 9-12, 2004 The Claremont Resort Oakland, California, USA. ... IEEE Technical Committee on Security and Privacy
Read more

dblp: IEEE Symposium on Security and Privacy

Bibliographic content of IEEE Symposium on Security and ... 2016 IEEE Security and Privacy Workshops, SP ... Symposium on Security and Privacy (S&P 2004 ...
Read more

IEEE Spectrum: Technology, Engineering, and Science News

IEEE Standards | IEEE Spectrum | More Sites; Follow on: Advertisement. Engineering Topics ; Special Reports ; Blogs ; Multimedia ; The Magazine ...
Read more

[ IEEE SP Magazine, May 2004 - hep.upatras.gr

It is a multidisciplinary field, borrowing and enhancing ideas from diverse areas such as statistics, image ...
Read more

Privacy-Preserving Data Mining: Why, How, and When

IEEE Computer Society Digital Library ... Data mining is under attack from privacy advocates because of a misunderstanding about what it actually is and a ...
Read more

IEEE Xplore - Advanced Search

Advanced Search Options . Advanced Keyword ... IEEE is the world's largest technical professional organization dedicated to advancing technology for the ...
Read more