Strongly-Secure Communications: Everlasting Secrecy and Undetectability Internet of Things Festival February 22, 2014 Boulat Bash University of Massachusetts, Amherst University of Massachusetts Amherst · School of Computer Science Introduction and Motivation Goal: to secure communications from very powerful adversaries Everlasting secrecy We want to keep something secret forever. Challenge of cryptography: messages can be stored and decrypted later • E.g. if you used DES in the 80s and early 90s, you were in trouble in late 90s • Moore’s Law (and reversible computing?) can do this to AES-256… EFF DES Cracker (source: EFF) School of Computer Science 2 Motivation (cont.) Undetectable communication We want to conceal the presence of a message: “metadata”, not message content Stronger than any form of encryption: You can’t decode what you can’t see. • also, encrypted data looks suspicious… NSA Utah Data Center (source: businessinsider.com) School of Computer Science Source: PraxisFilms 3 What this talk is about Consider additive noise: independent random events adding to the signal Underlying theme: this noise is good for security Everlasting secrecy • Elementary one-time pad • Wiretap channel: how it works and challenges Undetectability (or low probability of detection=LPD) • Background: steganography and spread spectrum • LPD communication on AWGN channel and square root law • Experiments on optical LPD channels and other extensions School of Computer Science 4 Everlasting Secrecy using One-Time Pad Encryption by modular addition of a random key Perfectly secret: no info revealed about message • Cryptanalysis impossible: trying all possible keys yields all possible messages of the same length Used in practice for transmission of highly sensitive messages Source: D. Rijmenants School of Computer Science Washington-Moscow hotline (source: NSA) Source: M. Ranum 5 Everlasting Secrecy using One-Time Pad Drawbacks: • Requires long secret keys (same length as the message) • Numbers for the keys must be random and independent • Determinism exploited by US Army Signal Corps in breaking some German WWII one-time pads • Re-use of keys compromises security • VENONA project Source: US DoE School of Computer Science 6 Wiretap Channel Adversary’s view: one-time pad = random noise Communications systems are naturally noisy AWGN SNR=0dB We use this noise for both everlasting secrecy and undetectability! School of Computer Science 7 Wiretap Channel Adversary’s view: one-time pad = random noise Communications systems are naturally noisy AWGN SNR=-20dB We use this noise for both everlasting secrecy and undetectability! School of Computer Science 8 Wiretap Channel Adversary’s view: one-time pad = random noise Communications systems are naturally noisy Note: Communication is possible even on this “bad” channel, but at a lower rate (need more time to “average out” the noise) AWGN SNR=-20dB We use this noise for both everlasting secrecy and undetectability! School of Computer Science 9 Wiretap Channel Consider Alice using a broadcast (e.g. wireless) channel to communicate with Bob “good” channel Bob Alice Eve’s wiretap channel “bad” channel Eve School of Computer Science 10 Wiretap Channel Suppose Alice transmits a 2-bit message, and Bob can distinguish between all four possibilities Messages that Alice can send “good” channel Bob Alice “bad” channel 00 10 01 11 Eve Bob can distinguish between them since his channel is good Wyner ‘75, Cheong and Hellman ‘78 School of Computer Science 11 Wiretap Channel However, Eve can’t distinguish the least significant bit (LSB), it’s “smudged” by noise Messages that Alice can send “good” channel Bob Alice “bad” channel 00 10 01 11 Eve Wyner ‘75, Cheong and Hellman ‘78 School of Computer Science Eve can’t distinguish zero from one in the LSB since her channel isn’t as good as Bob’s 12 Wiretap Channel Alice can transmit one perfectly secret bit to Bob in the LSB, choosing the most significant bit (MSB) at random Suppose Alice wants to send “1” “good” channel Bob Alice “bad” channel 00 10 01 11 Eve She setting LSB=“1” Wyner ‘75, Cheong and Hellman ‘78 School of Computer Science 13 Wiretap Channel Alice can transmit one perfectly secret bit to Bob in the LSB, choosing the most significant bit (MSB) at random Suppose Alice wants to send “1” “good” channel Bob Alice “bad” channel 00 10 01 11 Eve Chooses MSB=“0” randomly Wyner ‘75, Cheong and Hellman ‘78 School of Computer Science 14 Wiretap Channel Alice can transmit one perfectly secret bit to Bob in the LSB, choosing MSB at random Messages that Alice can send “good” channel Bob Alice “bad” channel 00 10 01 11 Eve Wyner ‘75, Cheong and Hellman ‘78 School of Computer Science Eve reads the MSB, but not the LSB, which encodes the secret message 15 Wiretap Channel Alice can transmit one perfectly secret bit to Bob in the LSB, choosing MSB at random Bob discards the MSB “good” channel Bob Alice “bad” channel 00 10 01 11 Eve Great! Alice sent “1” secretly! • Unlimited computational power doesn’t help Eve! • Unlike one-time pad, no need for secret key exchange between Alice and Bob! School of Computer Science 16 Wiretap Channel But BIG problem: what if Eve’s channel is better? Bob “bad” channel Alice “good” channel Eve Then this doesn’t work! School of Computer Science 17 Wiretap Channel Information is leaked if Alice and Bob incorrectly estimate Eve’s channel (or their own channel) Bob “bad” channel Alice “good” channel Eve In wireless comms, Eve’s channel depends on her location relative to Alice, and this is called the “Near Eve” problem. Signal fluctuations also occur due to unpredictable environment. Lots of academic research to mitigate the “Near Eve” problem, little practical success. School of Computer Science 18 Undetectable communication Problem: conceal presence of the message: “metadata” as opposed to protecting message content (encryption) Why? Lots of applications… • Communication looks suspicious • “Camouflage” military operations • etc… LPD=“low probability of detection” Source: PraxisFilms • Limit adversary’s detection capability to a tolerable level Cost: shared secret which could be larger than the message • Good price to pay for not having the message detected? • May be avoidable in certain scenarios (research ongoing) School of Computer Science 19 Steganography: a type of LPD communication Hiding messages by modifying characters in a covertext (images, code, etc.) Source: User Cyp, Wikipedia Extract two LSBs from this bitmap and normalize… School of Computer Science 20 Steganography: a type of LPD communication Hiding messages by modifying characters in a covertext (images, code, etc.) Source: User Cyp, Wikipedia Extract two LSBs from this bitmap and normalize… School of Computer Science 21 Steganography: a type of LPD communication Hiding messages by modifying characters in a covertext (images, code, etc.) However, this is easily detected by a competent adversary! (using statistical analysis) Source: User Cyp, Wikipedia If adversary is ignorant of covertext statistics, you can safely embed B ∝ C bit message, where C is covertext size (Cachin ‘04) • Otherwise B ∝ C log C with no channel noise (Fridrich ’09) School of Computer Science 22 Spread Spectrum power Original narrow-band information signal Spread Spectrum signal frequency “Hide signal in the noise” at a spectrum loss of 1/W (the bandwidth expansion or processing gain). Well known, and used by the military (Simon et al. ’94). But what is the fundamental tradeoff? School of Computer Science 23 Scenario Alice uses radio to covertly communicate with Bob • They share a secret (codebook) Willie attempts to detect if Alice is talking to Bob • Willie is passive, doesn’t actively jam Alice’s channel Willie’s problem: detect Alice Alice’s problem: limit Willie’s detection schemes Bob’s problem: decode Alice’s message School of Computer Science 24 Scenario Alice uses radio to covertly communicate with Bob • They share a secret (codebook) Willie attempts to detect if Alice is talking to Bob • Willie is passive, doesn’t actively jam Alice’s channel Willie’s problem: detect Alice Alice’s problem: limit Willie’s detection schemes Bob’s problem: decode Alice’s message School of Computer Science 25 Scenario Alice uses radio to covertly communicate with Bob • They share a secret (codebook) Willie attempts to detect if Alice is talking to Bob • Willie is passive, doesn’t actively jam Alice’s channel Thanks! or + ? Willie’s problem: detect Alice Alice’s problem: limit Willie’s detection schemes Bob’s problem: decode Alice’s message School of Computer Science 26 Undetectability: Main Result The Square Root Law: Suppose Alice tries to communicate with Bob in the presence of Warden Willie using N symbols (time periods) Thanks! or + ? Alice can reliably transmit B ∝ N bits to Bob with probability of detection by Willie of < ε for any ε > 0 Conversely, if Alice attempts to transmit more than that, one of the following occurs: 1. Bob experiences decoding errors 2. Alice’s transmission is detected School of Computer Science (Bash et al. ‘13) 27 Other advances in LPD Communications Optical LPD communications • Square root law similar to AWGN channel • Experimentally verified at Raytheon BBN Technologies PBSC Collimator Alice (laser) Mirror Variable attenuator Linear polarizer Willie HWP Bob Fiber-Beam Splitter Fiber-Beam Splitter Bob (SPD) Alice Willie (SPD) School of Computer Science 28 Optical LPD communications Credit for the setup: Andrei Gheorghe (Amherst College), Jon Habif (BBN) and Monika Patel (BBN) School of Computer Science 29 Optical LPD Communications experiment results Willie’s detector Bits received Prob(Error) Bob’s receiver Lines=analytic approximation Points=experiment Amount of time used (µs) Careless Alice (ignores square root law) School of Computer Science Careful Alice Amount of time used (µs) (obeys square P (Miss) + P( False Alarm) P (Error) = root law) 2 30 Other advances in LPD communication No shared codebook (Che et al. ’13) • Possible to achieve LPD communication without Alice and Bob sharing a codebook when all the channels are binary and symmetric (Bob’s channel has to be better) If Willie doesn’t know the time of the message • E.g. Alice-to-Bob secret: “I’ll transmit at 4:01am tomorrow” Slot 0 Slot 1 Slot 2 Slot 3 Slot T N N N N N • Willie has to watch a much longer time interval, more noise. • Can transmit B ∝ N log T bits by randomly choosing one of T slots, each having N symbol periods (Bash et al. ’14) School of Computer Science 31 Conclusion, takeaways, and future work Strong security is difficult, but not impossible • Noise is a resource that makes it happen • Everlasting secrecy • Cryptography works very well for “ephemeral” secrets; everlasting secrecy is costly (and understandably so) • Highly theoretical question: is there a middle ground between cryptographic security and perfect secrecy? • Undetectability • Privacy is very costly (and there is a reason why companies/governments are collecting data on everyone) • But, if one takes care, privacy IS achievable • Is it possible to build “shadow networks”? School of Computer Science 32
© Copyright 2024 ExpyDoc
