Kopf B.,MPI SWS |
Basin D.,ETH Zurich
Journal of Computer Security | Year: 2011
We present a model of adaptive attacks which we combine with information-theoretic metrics to quantify the information revealed to an adaptive adversary. This enables us to express an adversary's remaining uncertainty about a secret as a function of the number of interactions with the system under attack. We present algorithms and approximation methods for computing this function. The main application area for our approach is the analysis of side-channels in cryptographic algorithms and we give examples of how it can be used to characterize the vulnerability of hardware implementations to timing and power attacks. We also show the generality of our approach by using it to quantify the information leaked by a security protocol. © 2011 IOS Press and the authors. All rights reserved.
Backes M.,Saarland University |
Fiore D.,MPI SWS |
Reischuk R.M.,Saarland University
Proceedings of the ACM Conference on Computer and Communications Security | Year: 2013
We address the problem in which a client stores a large amount of data with an untrusted server in such a way that, at any moment, the client can ask the server to compute a function on some portion of its outsourced data. In this scenario, the client must be able to efficiently verify the correctness of the result despite no longer knowing the inputs of the delegated computation, it must be able to keep adding elements to its remote storage, and it does not have to fix in advance (i.e., at data outsourcing time) the functions that it will delegate. Even more ambitiously, clients should be able to verify in time independent of the input-size - a very appealing property for computations over huge amounts of data. In this work we propose novel cryptographic techniques that solve the above problem for the class of computations of quadratic polynomials over a large number of variables. This class covers a wide range of significant arithmetic computations - notably, many important statistics. To confirm the efficiency of our solution, we show encouraging performance results, e.g., correctness proofs have size below 1 kB and are verifiable by clients in less than 10 milliseconds. © 2013 ACM.
Ganty P.,IMDEA Madrid Institute for Advanced Studies |
Majumdar R.,MPI SWS
ACM Transactions on Programming Languages and Systems | Year: 2012
Asynchronous programming is a ubiquitous systems programming idiom for managing concurrent interactions with the environment. In this style, instead of waiting for time-consuming operations to complete, the programmer makes a non-blocking call to the operation and posts a callback task to a task buffer that is executed later when the time-consuming operation completes. A cooperative scheduler mediates the interaction by picking and executing callback tasks from the task buffer to completion (and these callbacks can post further callbacks to be executed later). Writing correct asynchronous programs is hard because the use of callbacks, while efficient, obscures program control flow. We provide a formal model underlying asynchronous programs and study verification problems for this model. We show that the safety verification problem for finite-data asynchronous programs is EXPSPACE- complete. We show that liveness verification for finite-data asynchronous programs is decidable and polynomial-time equivalent to Petri net reachability. Decidability is not obvious, since even if the data is finite-state, asynchronous programs constitute infinite-state transition systems: both the program stack for an executing task and the task buffer of pending calls to tasks can be potentially unbounded. Our main technical constructions are polynomial-time, semantics-preserving reductions from asynchronous programs to Petri nets and back. The first reduction allows the use of algorithmic techniques on Petri nets for the verification of asynchronous programs, and the second allows lower bounds on Petri nets to apply also to asynchronous programs. We also study several extensions to the basic models of asynchronous programs that are inspired by additional capabilities provided by implementations of asynchronous libraries and classify the decidability and undecidability of verification questions on these extensions. © 2012 ACM.
Alvisi L.,University of Texas at Austin |
Clement A.,MPI SWS |
Epasto A.,University of Rome La Sapienza |
Lattanzi S.,Google |
Panconesi A.,University of Rome La Sapienza
Proceedings - IEEE Symposium on Security and Privacy | Year: 2013
Sybil attacks in which an adversary forges a potentially unbounded number of identities are a danger to distributed systems and online social networks. The goal of sybil defense is to accurately identify sybil identities. This paper surveys the evolution of sybil defense protocols that leverage the structural properties of the social graph underlying a distributed system to identify sybil identities. We make two main contributions. First, we clarify the deep connection between sybil defense and the theory of random walks. This leads us to identify a community detection algorithm that, for the first time, offers provable guarantees in the context of sybil defense. Second, we advocate a new goal for sybil defense that addresses the more limited, but practically useful, goal of securely white-listing a local region of the graph. © 2013 IEEE.
Nanevski A.,IMDEA Madrid Institute for Advanced Studies |
Banerjee A.,IMDEA Madrid Institute for Advanced Studies |
Garg D.,MPI SWS
ACM Transactions on Programming Languages and Systems | Year: 2013
We present Relational Hoare Type Theory (RHTT), a novel language and verification system capable of expressing and verifying rich information flow and access control policies via dependent types. We show that a number of security policies which have been formalized separately in the literature can all be expressed in RHTT using only standard type-theoretic constructions such as monads, higher-order functions, abstract types, abstract predicates, and modules. Example security policies include conditional declassification, information erasure, and state-dependent information flow and access control. RHTT can reason about such policies in the presence of dynamic memory allocation, deallocation, pointer aliasing and arithmetic.©2013 ACM 0164-0925/2013/07-ART7 $15.00.