Computer Security and Cryptography Reading Group
April 2004 List

URL: http://citeseer.nj.nec.com/heintze98slam.html

The SLam calculus is a typed λ-calculus that maintains security information as well as type information. The type system propagates security information for each object in four forms: the object's creators and readers, and the object's indirect creators and readers (i.e., those agents who, through flow-of-control or the actions of other agents, can influence or be influenced by the content of the object). We prove that the type system prevents security violations and give some examples of its power.

URL: http://www2.cs.uregina.ca/~pwlfong/Pub/sp-2004.pdf

Software execution environments like operating systems, mobile code platforms and scriptable applications must protect themselves against potential damages caused by malicious code. Monitoring the execution history of the latter provides an effective means for controlling the access pattern of system services. Several authors have recently proposed increasingly general automata models for characterizing various classes of security policies enforceable by execution monitoring. An open question raised by Bauer, Ligatti and Walker is whether one can further classify the space of security policies by constraining the capabilities of the execution monitor. This paper presents a novel information-based approach to address the research problem. Specifically, security policies are characterized by the information consumed by an enforcing execution monitor.

By restricting the execution monitor to track only a shallow history of previously granted access events, a precise characterization of a class of security policies enforceable by restricted access to information is identified. Although provably less expressive than the general class of policies enforceable by execution monitoring, this class does contain naturally occurring policies including Chinese Wall policy, low-water-mark policy, one-out-of-k authorization, assured pipelines, etc. Encouraged by this success, the technique is generalized to produce a lattice of policy classes. Within the lattice, policy classes are ordered by the information required for enforcing member policies. Such a finegrained policy classification lays the semantic foundation for future studies on special-purpose policy languages.

URL: http://ieeexplore.ieee.org/xpls/abs_all.jsp?isNumber=427&prod=CNF&arnumber=8092&arSt=2&ared=7&arAuthor=McLean%2C+J.&arNumber=8092&a_id0=8091&a_id1=8092&a_id2=8093&a_id3=8094&a_id4=8095&a_id5=8096&a_id6=8097&a_id7=8098&a_id8=8099&a_id9=8100&a_id10=8101&a_id11=8103&a_id12=8104&a_id13=8105&a_id14=8106&count=15

A general framework is developed in which various mandatory access control security models that allow changes in security levels can be formalized. These models form a Boolean Algebra. The framework is expanded to include models that allow n-person rules necessary for discretionary access controls in an industrial security setting. The resulting framework is a distributive lattice.

URL: http://www.cs.arizona.edu/solar/papers/pbw.pdf

Software watermarks - bitstrings encoding some sort of identifying information that are embedded into executable programs - are an important tool against software piracy. Most existing proposals for software watermarking have the shortcoming that they can be destroyed via fairly straight-forward semantics-preserving code transformations. This paper introduces path-based watermarking, a new approach to software watermarking based on the dynamic branching behavior of programs. We show how error-correcting and tamper-proofing techniques can be used to make path-based watermarks resilient against a wide variety of attacks. Experimental results, using both Java bytecode and IA-32 native code, indicate that even relatively large watermarks can be embedded into programs at modest cost.

URL: http://www.cs.wisc.edu/areas/sec/Yao1982.pdf

Two millionaires wish to know who is richer; however, they do not want to find out inadvertently any additional information about each other's wealth. How can they carry out such a conversation?

This is a special case of the following general problem. Suppose m people wish to compute the value of a function f(x₁, x₂, x₃,..., x_m), which is an integer-valued function of $m$ integer variables x_i of bounded range. Assume initially person P_i knows the value of x_i and no other x's. Is it possible for them to compute the value of f, by communicating among themselves, without unduly giving away any information about the values of their own variables? The millionaires' problem corresponds to the case when m = 2 and f(x₁, x₂) = 1 if x₁ < x₂, and 0 otherwise. In this paper, we will give precise formulation of this general problem and describe three ways of solving it by use of one-way functions (i.e., functions which are easy to evaluate but hard to invert). These results have applications to secret voting, private querying of database, oblivious negotiation, playing mental poker, etc. We will also discuss the complexity question ``How many bits need to be exchanged for the computation'', and describe methods to prevent participants from cheating. Finally, we study the question ``What cannot be accomplished with one-way functions''.