More Web Proxy on the site http://driver.im/

article

Quantifying information leakage in process calculi

Author:

Michele BorealeAuthors Info & Claims

Information and Computation, Volume 207, Issue 6

Pages 699 - 725

https://doi.org/10.1016/j.ic.2008.12.007

Published: 01 June 2009 Publication History

Abstract

Building on simple information-theoretic concepts, we study two quantitative models of information leakage in the pi-calculus. The first model presupposes an attacker with an essentially unlimited computational power. The resulting notion of absolute leakage, measured in bits, is in agreement with secrecy as defined by Abadi and Gordon: a process has an absolute leakage of zero precisely when it satisfies secrecy. The second model assumes a restricted observation scenario, inspired by the testing equivalence framework, where the attacker can only conduct repeated success-or-failure experiments on processes. Moreover, each experiment has a cost in terms of communication effort. The resulting notion of leakage rate, measured in bits per action, is in agreement with the first model: the maximum amount of information that can be extracted by repeated experiments coincides with the absolute leakage A of the process. Moreover, the overall extraction cost is at least A/R, where R is the rate of the process. The compositionality properties of the two models are also investigated.

References

[1]

Abadi, M. and Gordon, A., A calculus for cryptographic protocols: the Spi-calculus. Information and Computation. v148 i1. 1-70.

[2]

Aldini, A., Bravetti, M. and Gorrieri, R., A process-algebraic approach for the analysis of probabilistic non-interference. Journal of Computer Security. v12 i2. 191-245.

[3]

E. Bach, et al., What's a key-guessing attack? What's entropy? in: Cryptography Frequently Asked Questions, Section 4.9. Avaliable from: <http://www.faqs.org/faqs/cryptography-faq/part04/>.

[4]

M. Boreale, Quantifying information leakage in process calculi, in: ICALP 2006, LNCS, vol. 4052, Springer, 2006.

[5]

Boreale, M. and De Nicola, R., Testing equivalence for mobile processes. Information and Computation. v120 i2. 279-303.

[6]

Boreale, M. and De Nicola, R., A symbolic semantics for the pi-calculus. Information and Computation. v126 i1. 34-52.

[7]

C. Braun, K. Chatzikokolakis, C. Palamidessi, Compositional methods for information-hiding, in: Proceedings of FOSSACS'08, LNCS, vol. 4962, Springer, 2008.

[8]

K. Chatzikokolakis, C. Palamidessi, P. Panangaden, Anonymity protocols as noisy channels, in: Proceedings of the 2nd Symposium on Trustworthy Global Computing (TGC 06), Springer, LNCS, 2006, Full version in Information and Computation, 206 (2008), 378--401.

Digital Library

[9]

K. Chatzikokolakis, C. Palamidessi, P. Panangaden, Probability of error in information-hiding protocols, in: Proceedings of the 20th IEEE CSF, IEEE Computer Society, 2007.

[10]

Clark, D., Hunt, S. and Malacaria, P., Quantitative analysis of the leakage of confidential data. Electronic Notes in Theoretical Computer Science. v59 i3.

[11]

Clark, D., Hunt, S. and Malacaria, P., Quantitative information flow, relations and polymorphic types. Journal of Logic and Computation. v15 i2. 181-199.

[12]

Clark, D., Hunt, S. and Malacaria, P., A static analysis for quantifying information flow in a simple imperative language. Journal of Computer Security. v15 i3. 321-371.

[13]

Cover, T.M. and Thomas, J.A., Elements of Information Theory. 1991. Wiley, New York.

[14]

De Nicola, R. and Hennessy, M.C.B., Testing equivalences for processes. Theoretical Computer Science. v34. 83-133.

[15]

A. Di Pierro, C. Hankin, H. Wiklicky, Approximate non-interference, in: Computer Security Foundations Workshop, 2002, Full version in Journal of Computer Security 12 (1) (2004) 37--82.

[16]

Focardi, R. and Gorrieri, R., A classification of security properties. Journal of Computer Security. v3 i1. 5-34.

[17]

Goguen, J.A. and Meseguer, J., Security policies and security models. IEEE Symposium on Security and Privacy.

[18]

J.W. Gray III, Towards a mathematical foundation for information flow security, in: Proceedings of 1991 IEEE Symposium on Research in Computer Security and Privacy, 1991.

[19]

Hennessy, M.C.B. and Lin, H., Symbolic bisimulations. Theoretical Computer Science. v138 i2. 353-389.

[20]

P. Kocher, Timing attacks on implementations of Diffie-Hellman, RSA, DSS, and other systems, in: CRYPTO 1996, 1996, pp. 104--113.

[21]

P. Kocher, J. Jaffe, B. Jun, Differential power analysis, in: CRYPTO 1999, 1999, pp. 388--397.

Digital Library

[22]

Köpf, B. and Basin, D.A., An information-theoretic model for adaptive side-channel attacks. ACM Conference on Computer and Communications Security. 286-296.

[23]

Lowe, G., Defining information flow quantity. Journal of Computer Security. v12 i3--4. 619-653.

[24]

P. Malacaria, Assessing security threats of looping constructs, in: POPL 2007.

[25]

J.L. Massey. Guessing and entropy, in: Proceedings of IEEE International Symposium on Information Theory, 1994, p. 204.

[26]

J. Millen, Covert channel capacity, in: Proceedings of 1987 IEEE Symposium on Research in Computer Security and Privacy, 1987.

[27]

J.O. Pliam, On the incomparability of entropy and marginal guesswork in Brute-force attacks, in: Proceedings of Progress in Cryptology -- INDOCRYPT 2000, First International Conference in Cryptology in India, Calcutta, India, December 2000, LNCS, vol. 1977, Springer-Verlag.

[28]

Reiter, M. and Rubin, A., Crowds: anonymity for web transactions. ACM Transactions on Information and System Security. v1 i1.

[29]

Sangiorgi, D. and Walker, D., The Pi-Calculus: A Theory of Mobile Processes. 2001. Cambridge University Press.

[30]

Shannon, C.E., Communication theory of secrecy systems. Bell System Technical Journal. v27. 379-423.

[31]

F.-X. Standaert, E. Peeters, C. Archambeau, J.-J. Quisquater, Towards security limits in side-channel attacks, in: Proceedings of CHES 2006, Lecture Notes in Computer Science, vol. 4249, Yokohama, Japan, October 2006, Springer-Verlag, pp. 30--45.

[32]

F.-X. Standaert, T.G. Malkin, M. Yung, A Unified Framework for the Analysis of Side-Channel Key Recovery Attacks, Cryptology ePrint Archive, Report 2006/139, February 2008.

[33]

F. Topsøe, Basic concepts, identities and inequalities -- the Toolkit of information theory, Entropy 3 (2001) 162--190. Available from: <http://www.math.ku.dk/~topsoe/toolkitfinal.pdf/>.

[34]

D. Volpano, G. Smith, Verifying secrets and relative secrecy, in: POPL 2000, 2000, pp. 268--276.

[35]

J.T. Wittbold, D. Johnson, Information flow in nondeterministic systems, in: Proceedings of 1990 IEEE Symposium on Research in Computer Security and Privacy, 1990.

Cited By

Romanelli MChatzikokolakis KPalamidessi CPiantanida PLigatti JOu XKatz JVigna G(2020)Estimating g-Leakage via Machine LearningProceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security10.1145/3372297.3423363(697-716)Online publication date: 30-Oct-2020
https://dl.acm.org/doi/10.1145/3372297.3423363
Watt CRenner JPopescu NCauligi SStefan D(2019)CT-wasm: type-driven secure cryptography for the web ecosystemProceedings of the ACM on Programming Languages10.1145/32903903:POPL(1-29)Online publication date: 2-Jan-2019
https://dl.acm.org/doi/10.1145/3290390
Boreale MCorradi F(2018)Searching secrets rationallyInternational Journal of Approximate Reasoning10.1016/j.ijar.2015.11.01069:C(133-146)Online publication date: 29-Dec-2018
https://dl.acm.org/doi/10.1016/j.ijar.2015.11.010
Show More Cited By

Recommendations

Quantifying information leakage in process calculi
ICALP'06: Proceedings of the 33rd international conference on Automata, Languages and Programming - Volume Part II

We study two quantitative models of information leakage in the pi-calculus. The first model presupposes an attacker with an essentially unlimited computational power. The resulting notion of absolute leakage, measured in bits, is in agreement with ...
On the expressiveness and decidability of higher-order process calculi

In higher-order process calculi, the values exchanged in communications may contain processes. A core calculus of higher-order concurrency is studied; it has only the operators necessary to express higher-order communications: input prefix, process ...
On the Expressiveness and Decidability of Higher-Order Process Calculi
LICS '08: Proceedings of the 2008 23rd Annual IEEE Symposium on Logic in Computer Science

In higher-order process calculi the values exchanged in communications may contain processes. A core calculus of higher-order concurrency is studied; it has only the operators necessary to express higher-order communications: input prefix, process ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Information and Computation

Information and Computation Volume 207, Issue 6

June, 2009

117 pages

ISSN:0890-5401

Issue’s Table of Contents

Copyright © Elsevier Inc. © 2009.

Publisher

Academic Press, Inc.

United States

Publication History

Published: 01 June 2009

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

7
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 27 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Romanelli MChatzikokolakis KPalamidessi CPiantanida PLigatti JOu XKatz JVigna G(2020)Estimating g-Leakage via Machine LearningProceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security10.1145/3372297.3423363(697-716)Online publication date: 30-Oct-2020
https://dl.acm.org/doi/10.1145/3372297.3423363
Watt CRenner JPopescu NCauligi SStefan D(2019)CT-wasm: type-driven secure cryptography for the web ecosystemProceedings of the ACM on Programming Languages10.1145/32903903:POPL(1-29)Online publication date: 2-Jan-2019
https://dl.acm.org/doi/10.1145/3290390
Boreale MCorradi F(2018)Searching secrets rationallyInternational Journal of Approximate Reasoning10.1016/j.ijar.2015.11.01069:C(133-146)Online publication date: 29-Dec-2018
https://dl.acm.org/doi/10.1016/j.ijar.2015.11.010
Biondi FLegay AQuilbeuf J(2015)Comparative Analysis of Leakage Tools on Scalable Case StudiesProceedings of the 22nd International Symposium on Model Checking Software - Volume 923210.1007/978-3-319-23404-5_17(263-281)Online publication date: 24-Aug-2015
https://dl.acm.org/doi/10.1007/978-3-319-23404-5_17
Boreale MPampaloni FPaolini M(2011)Quantitative information flow, with a viewProceedings of the 16th European conference on Research in computer security10.5555/2041225.2041267(588-606)Online publication date: 12-Sep-2011
https://dl.acm.org/doi/10.5555/2041225.2041267
Boreale MPampaloni FPaolini M(2011)Asymptotic information leakage under one-try attacksProceedings of the 14th international conference on Foundations of software science and computational structures: part of the joint European conferences on theory and practice of software10.5555/1987171.1987205(396-410)Online publication date: 26-Mar-2011
https://dl.acm.org/doi/10.5555/1987171.1987205
Wibmer MBiswas DKerschbaum F(2010)Leakage quantification of cryptographic operationsProceedings of the 2010 international conference on On the move to meaningful internet systems - Volume Part I10.5555/1947725.1947788(685-700)Online publication date: 25-Oct-2010
https://dl.acm.org/doi/10.5555/1947725.1947788

View Options

View options

Figures

Tables

Media

View Issue’s Table of Contents