Danfeng Zhang
Aslan Askarov
Andrew C. Myers
ABSTRACT
Timing channels remain a difficult and important problem for information security. Recent work introduced predictive mitigation, a new way to mitigating leakage through timing channels; this mechanism works by predicting timing from past behavior, and then enforcing the predictions. This paper generalizes predictive mitigation to a larger and important class of systems: systems that receive input requests from multiple clients and deliver responses. The new insight is that timing predictions may be a function of any public information, rather than being a function simply of output events. Based on this insight, a more general mechanism and theory of predictive mitigation becomes possible. The result is that bounds on timing leakage can be tightened, achieving asymptotically logarithmic leakage under reasonable assumptions. By applying it to web applications, the generalized predictive mitigation mechanism is shown to be effective in practice.
- B. W. Lampson, "A note on the confinement problem," Comm. of the ACM, vol. 16, no. 10, pp. 613--615, Oct. 1973. Google Scholar
Digital Library
- P. Kocher, "Timing attacks on implementations of Diffie-Hellman, RSA, DSS, and other systems," in Advances in Cryptology-CRYPTO'96, Aug. 1996. Google ScholarDigital Library
- D. Brumley and D. Boneh, "Remote timing attacks are practical," Computer Networks, Jan. 2005. Google ScholarDigital Library
- D. Osvik, A. Shamir, and E. Tromer, "Cache attacks and countermeasures: the case of AES," Topics in Cryptology--CT-RSA 2006, Jan. 2006. {Online}. Available: http://www.springerlink.com/index/F52X1H55G1632L17.pdf Google ScholarDigital Library
- A. Bortz and D. Boneh, "Exposing private information by timing web applications," in Proc. 16th Int'l World-Wide Web Conf., May 2007. Google ScholarDigital Library
- G. Shah, A. Molina, and M. Blaze, "Keyboards and covert channels," Proc. 15th USENIX Security Symp., Aug. 2006. Google ScholarDigital Library
- H. Meer and M. Slaviero, "It's all about the timing..." in Proc. Black Hat USA, 2007.Google Scholar
- Y. Liu, D. Ghosal, F. Armknecht, A. Sadeghi, and S. Schulz, "Hide and seek in time-robust covert timing channels," in ESORICS, 2009. Google ScholarDigital Library
- R. G. Gallagher, "Basic limits on protocol information in data communication networks," IEEE Transactions on Information Theory, vol. 22, no. 4, Jul. 1976.Google Scholar
- M. Padlipsky, D. Snow, and P. Karger, "Limitations of end-to-end encryption in secure computer networks," Mitre Corp., Tech. Rep. ESD TR-78--158, 1978.Google ScholarCross Ref
- I. S. Moskowitz and M. H. Kang, "Covert channels--here to stay?" in COMPASS '94, 1994.Google Scholar
- B. Köpf and M. Dürmuth, "A provably secure and efficient countermeasure against timing attacks," in 2009 IEEE Computer Security Foundations, Jul. 2009.Google Scholar
- B. Köpf and G. Smith, "Vulnerability bounds and leakage resilience of blinded cryptography under timing attacks," in 2010 IEEE Computer Security Foundations, Jul. 2010.Google Scholar
- A. Askarov, D. Zhang, and A. C. Myers, "Predictive black-box mitigation of timing channels," in ACM Conf. on Computer and Communications Security (CCS), 2010, pp. 297--307. Google ScholarDigital Library
- A. Sabelfeld and D. Sands, "Probabilistic noninterference for multi-threaded programs," in Proc. 13th IEEE Computer Security Foundations Workshop. IEEE Computer Society Press, Jul. 2000, pp. 200--214. Google ScholarDigital Library
- W.-M. Hu, "Reducing timing channels with fuzzy time," in IEEE Symposium on Security and Privacy, 1991, pp. 8 -- 20.Google Scholar
- J. Agat, "Transforming out timing leaks," in Proc. 27th ACM Symp. on Principles of Programming Languages (POPL), Boston, MA, Jan. 2000, pp. 40--53. Google ScholarDigital Library
- S. Zdancewic and A. C. Myers, "Observational determinism for concurrent program security," in Proc. 16th IEEE Computer Security Foundations Workshop, Pacific Grove, California, Jun. 2003, pp. 29--43.Google ScholarCross Ref
- A. Russo, J. Hughes, D. Naumann, and A. Sabelfeld, "Closing internal timing channels by transformation," in Proc. 11th Annual Asian Computing Science Conference (ASIAN), 2006. Google ScholarDigital Library
- J. Giles and B. Hajek, "An information-theoretic and game-theoretic study of timing channels." IEEE Transactions on Information Theory, vol. 48, no. 9, pp. 2455--2477, 2002. Google ScholarDigital Library
- D. E. Denning, Cryptography and Data Security. Reading, Massachusetts: Addison-Wesley, 1982.Google Scholar
- J. K. Millen, "Covert channel capacity," in Proc. IEEE Symposium on Security and Privacy, Oakland, CA, Apr. 1987.Google Scholar
- ----, "Finite-state noiseless covert channels," in Proc. 2nd IEEE Computer Security Foundations Workshop, Jun. 1989, pp. 11--14.Google ScholarCross Ref
- I. S. Moskowitz and A. R. Miller, "The channel capacity of a certain noisy timing channel," IEEE Trans. on Information Theory, vol. 38, no. 4, pp. 1339--1344. Google ScholarDigital Library
- G. Smith, "On the foundations of quantitative information flow," Proc. 12th Intl' Conf. on Foundations of Software Science and Computation Structures, pp. 388--402, 2010. Google ScholarDigital Library
- M. H. Kang and I. S. Moskowitz, "A pump for rapid, reliable, secure communication," in ACM Conf. on Computer and Communications Security (CCS), Nov. 1993, pp. 119--129. Google ScholarDigital Library
- M. H. Kang, I. S. Moskowitz, and D. C. Lee, "A network pump," IEEE Transactions on Software Engineering, vol. 22, pp. 329--338, 1996. Google ScholarDigital Library
- T. Cover and J. Thomas, Elements of information theory. Wiley, 2006. Google ScholarDigital Library
Index Terms
- Predictive mitigation of timing channels in interactive systems
Recommendations
Language-based control and mitigation of timing channels
PLDI '12: Proceedings of the 33rd ACM SIGPLAN Conference on Programming Language Design and ImplementationWe propose a new language-based approach to mitigating timing channels. In this language, well-typed programs provably leak only a bounded amount of information over time through external timing channels. By incorporating mechanisms for predictive ...
Predictive black-box mitigation of timing channels
CCS '10: Proceedings of the 17th ACM conference on Computer and communications securityWe investigate techniques for general black-box mitigation of timing channels. The source of events is wrapped by a timing mitigator that delays output events so that they contain only a bounded amount of information. We introduce a general class of ...
Language-based control and mitigation of timing channels
PLDI '12We propose a new language-based approach to mitigating timing channels. In this language, well-typed programs provably leak only a bounded amount of information over time through external timing channels. By incorporating mechanisms for predictive ...
Comments