Proactive obfuscation is a new method for creating server replicas that are likely to have fewer shared vulnerabilities. It employs semantics-preserving code transformations to generate diverse executables from a single codebase and periodically restarts servers with these fresh images. Periodic restarts help bound the number of compromised replicas that a service ever concurrently runs, and therefore proactive obfuscation makes an adversary’s job more difﬁcult. Proactive obfuscation was used in implementing two prototypes: a distributed ﬁrewall based on state-machine replication and a distributed storage service based on quorum systems. Costs intrinsic to supporting proactive obfuscation were quantiﬁed by measuring the performance of these prototypes. Authentication is a large cost in proactive obfuscation. And some protocols used in the prototypes require transferable signed messages (for example, using digital signatures), which can be slow to compute. To reduce authentication costs, we introduce multi-veriﬁer signatures, a new family of signature schemes that generalizes traditional digital signatures to a secret-key setting. Some of our multi-veriﬁer signature schemes are faster to compute than digital signatures. Moreover, just like digital signatures, these signatures are both transferable and secure under arbitrary (unbounded) adaptive chosen-message attacks. Practical constructions of digital signature schemes rely on either strong number-theoretic assumptions or are proven secure only in the random oracle model. In contrast, we exhibit practical constructions of multi-veriﬁer signature schemes that are provably secure in the plain model assuming the existence of pseudorandom functions and without assuming access to random oracles.
dissertation or thesis