Termination-Insensitive Noninterference Leaks More Than Just a Bit. Askarov, A., Hunt, S., Sabelfeld, A., & Sands, D. In The 13th European Symposium on Research in Computer Security (ESORICS 08, Malaga, Spain, October 6-8, 2008. Proceedings, of LNCS, pages 333--348, 2008. Springer Verlag. Paper abstract bibtex Current tools for analysing information flow in programs build upon ideas going back to Denning's work from the 70's. These systems enforce an imperfect notion of information flow which has become known as termination-insensitive noninterference. Under this version of noninterference, information leaks are permitted if they are transmitted purely by the program's termination behaviour (i.e., whether it terminates or not). This imperfection is the price to pay for having a security condition which is relatively liberal (e.g. allowing while-loops whose termination may depend on the value of a secret) and easy to check. But what is the price exactly? We argue that, in the presence of output, the price is higher than the ``one bit'' often claimed informally in the literature, and effectively such programs can leak all of their secrets. In this paper we develop a definition of termination-insensitive noninterference suitable for reasoning about programs with outputs. We show that the definition generalises ``batch-job'' style definitions from the literature and that it is indeed satisfied by a Denning-style program analysis with output. Although more than a bit of information can be leaked by programs satisfying this condition, we show that the best an attacker can do is a brute-force attack, which means that the attacker cannot reliably (in a technical sense) learn the secret in polynomial time in the size of the secret. If we further assume that secrets are uniformly distributed, we show that the advantage the attacker gains when guessing the secret after observing a polynomial amount of output is negligible in the size of the secret.
@inproceedings{Askarov+:ESORICS08,
title={{Termination-Insensitive Noninterference Leaks More Than Just a Bit}},
author={Askarov, A. and Hunt, S. and Sabelfeld, A. and Sands, D.},
booktitle={The 13th European Symposium on Research in Computer Security (ESORICS 08, Malaga, Spain, October 6-8, 2008. Proceedings},
number = {5283},
series = {LNCS},
url_Paper = {http://www.cse.chalmers.se/~andrei/esorics08.pdf},
publisher = {Springer Verlag},
abstract={ Current tools for analysing information flow in programs
build upon ideas going back to Denning's work from
the 70's. These systems enforce an imperfect notion
of information flow which has become known as
termination-insensitive noninterference. Under this
version of noninterference, information leaks are
permitted if they are transmitted purely by the
program's termination behaviour (i.e., whether it
terminates or not). This imperfection is the price
to pay for having a security condition which is
relatively liberal (e.g. allowing while-loops whose
termination may depend on the value of a secret) and
easy to check. But what is the price exactly? We
argue that, in the presence of output, the price is
higher than the ``one bit'' often claimed informally
in the literature, and effectively such programs can
leak all of their secrets. In this paper we develop
a definition of termination-insensitive
noninterference suitable for reasoning about
programs with outputs. We show that the definition
generalises ``batch-job'' style definitions from the
literature and that it is indeed satisfied by a
Denning-style program analysis with output. Although
more than a bit of information can be leaked by
programs satisfying this condition, we show that the
best an attacker can do is a brute-force attack,
which means that the attacker cannot reliably (in a
technical sense) learn the secret in polynomial time
in the size of the secret. If we further assume that
secrets are uniformly distributed, we show that the
advantage the attacker gains when guessing the
secret after observing a polynomial amount of output
is negligible in the size of the secret. },
pages={333--348},
year={2008}
}
Downloads: 0
{"_id":"AKB9quYZCNfy4FnYh","bibbaseid":"askarov-hunt-sabelfeld-sands-terminationinsensitivenoninterferenceleaksmorethanjustabit-2008","downloads":0,"creationDate":"2017-02-03T08:24:26.806Z","title":"Termination-Insensitive Noninterference Leaks More Than Just a Bit","author_short":["Askarov, A.","Hunt, S.","Sabelfeld, A.","Sands, D."],"year":2008,"bibtype":"inproceedings","biburl":"http://www.cse.chalmers.se/~dave/davewww2016.bib","bibdata":{"bibtype":"inproceedings","type":"inproceedings","title":"Termination-Insensitive Noninterference Leaks More Than Just a Bit","author":[{"propositions":[],"lastnames":["Askarov"],"firstnames":["A."],"suffixes":[]},{"propositions":[],"lastnames":["Hunt"],"firstnames":["S."],"suffixes":[]},{"propositions":[],"lastnames":["Sabelfeld"],"firstnames":["A."],"suffixes":[]},{"propositions":[],"lastnames":["Sands"],"firstnames":["D."],"suffixes":[]}],"booktitle":"The 13th European Symposium on Research in Computer Security (ESORICS 08, Malaga, Spain, October 6-8, 2008. Proceedings","number":"5283","series":"LNCS","url_paper":"http://www.cse.chalmers.se/~andrei/esorics08.pdf","publisher":"Springer Verlag","abstract":"Current tools for analysing information flow in programs build upon ideas going back to Denning's work from the 70's. These systems enforce an imperfect notion of information flow which has become known as termination-insensitive noninterference. Under this version of noninterference, information leaks are permitted if they are transmitted purely by the program's termination behaviour (i.e., whether it terminates or not). This imperfection is the price to pay for having a security condition which is relatively liberal (e.g. allowing while-loops whose termination may depend on the value of a secret) and easy to check. But what is the price exactly? We argue that, in the presence of output, the price is higher than the ``one bit'' often claimed informally in the literature, and effectively such programs can leak all of their secrets. In this paper we develop a definition of termination-insensitive noninterference suitable for reasoning about programs with outputs. We show that the definition generalises ``batch-job'' style definitions from the literature and that it is indeed satisfied by a Denning-style program analysis with output. Although more than a bit of information can be leaked by programs satisfying this condition, we show that the best an attacker can do is a brute-force attack, which means that the attacker cannot reliably (in a technical sense) learn the secret in polynomial time in the size of the secret. If we further assume that secrets are uniformly distributed, we show that the advantage the attacker gains when guessing the secret after observing a polynomial amount of output is negligible in the size of the secret. ","pages":"333--348","year":"2008","bibtex":"@inproceedings{Askarov+:ESORICS08,\n title={{Termination-Insensitive Noninterference Leaks More Than Just a Bit}},\n author={Askarov, A. and Hunt, S. and Sabelfeld, A. and Sands, D.},\n booktitle={The 13th European Symposium on Research in Computer Security (ESORICS 08, Malaga, Spain, October 6-8, 2008. Proceedings},\n number = {5283},\n series = \t {LNCS},\n url_Paper = {http://www.cse.chalmers.se/~andrei/esorics08.pdf},\n publisher = {Springer Verlag},\n abstract={ Current tools for analysing information flow in programs\n build upon ideas going back to Denning's work from\n the 70's. These systems enforce an imperfect notion\n of information flow which has become known as\n termination-insensitive noninterference. Under this\n version of noninterference, information leaks are\n permitted if they are transmitted purely by the\n program's termination behaviour (i.e., whether it\n terminates or not). This imperfection is the price\n to pay for having a security condition which is\n relatively liberal (e.g. allowing while-loops whose\n termination may depend on the value of a secret) and\n easy to check. But what is the price exactly? We\n argue that, in the presence of output, the price is\n higher than the ``one bit'' often claimed informally\n in the literature, and effectively such programs can\n leak all of their secrets. In this paper we develop\n a definition of termination-insensitive\n noninterference suitable for reasoning about\n programs with outputs. We show that the definition\n generalises ``batch-job'' style definitions from the\n literature and that it is indeed satisfied by a\n Denning-style program analysis with output. Although\n more than a bit of information can be leaked by\n programs satisfying this condition, we show that the\n best an attacker can do is a brute-force attack,\n which means that the attacker cannot reliably (in a\n technical sense) learn the secret in polynomial time\n in the size of the secret. If we further assume that\n secrets are uniformly distributed, we show that the\n advantage the attacker gains when guessing the\n secret after observing a polynomial amount of output\n is negligible in the size of the secret. },\n pages={333--348},\n year={2008}\n}\n\n\n","author_short":["Askarov, A.","Hunt, S.","Sabelfeld, A.","Sands, D."],"key":"Askarov+:ESORICS08","id":"Askarov+:ESORICS08","bibbaseid":"askarov-hunt-sabelfeld-sands-terminationinsensitivenoninterferenceleaksmorethanjustabit-2008","role":"author","urls":{" paper":"http://www.cse.chalmers.se/~andrei/esorics08.pdf"},"downloads":0},"search_terms":["termination","insensitive","noninterference","leaks","more","bit","askarov","hunt","sabelfeld","sands"],"keywords":[],"authorIDs":[],"dataSources":["SBHWXKotbthoEYKJv"]}