[cap-talk] Implementing a crypto brand: What are the security requirements?

[David Wagner]

Tyler Close writes:
>http://waterken.sourceforge.net/javadoc/org/ref_send/brand/package-summary.html
>
>I've composed an initial list of security properties. I'd like us to
>criticize: the completeness of the list, the terminology used in the
>list and the definitions used in the list.

Terminology: I think I've mentioned that I don't find the names in the
API intuitive.  I would have found BrandFactory (not KeySpace) and
makeBrand() or make() (not bear()) more intuitive names.  But I
assume naming is out of scope.

>For a brand A, the following security properties must hold:

I assume these only apply to a brand A returned by a call to
x.bear(), where x is some brand factory under consideration.

Note that all security claims should be limited to only apply to
adversaries whose computation resources are bounded.  More precisely,
the probability that an adversary using no more than resources R
can observe a violation of the following requirements should be at
most p.  The documentation for a crypto brand should document R and p.
For instance, one choice might be R = 2^80 Java instructions, p = 1/2^32.

>Separation
>        - Possession of Sealer A does not yield possession of Unsealer
>A, nor possession of any Box A, except as the return of a seal()
>operation.

except as the return of a seal() operation *invoked on Sealer A*.

I think we want something stronger.  We want to rule out the possibility
that, e.g., possession of Sealer A plus possession of Sealer B yields
possession of Unsealer A.  This is a little tricky to formalize.  Perhaps
what we mean is that in this code:
    ...
    Object otherstuff = ...;
    Brand br = keyspace.bear(label);
    f(br.label, br.sealer, otherstuff);
no matter how we fill in the "..."'s or the body of the function f(),
f() cannot get possession of br.unsealer.  Does that do the trick?

Something similar goes for all the other "does not yield" statements
in your email.

Does this seem useful?

>Protection
>    The contents of a Box A are only accessible given possession of
>both Box A and Unsealer A.

Yes.  In particular,
    ...
    Object otherstuff = ...;
    Object contents = ...;
    Brand br = keyspace.bear(label);
    Box box = br.sealer(contents);
    f(br.label, br.sealer, box, otherstuff);
no matter how you fill in the "..."'s, if f() can get the reference
'contents', then there exists some ff() that takes the same arguments
except for 'box' and that can also get the reference 'contents'.
A similar statement also goes if we replace the last line above by
    f(br.label, br.sealer, br.unsealer, otherstuff);
if f() can get 'contents', then there exists some ff() that takes all
the same arguments except not 'br.unsealer' and that can get 'contents'.

>Confidentiality
>    Without possession of Unsealer A, possession of a Box A does not
>yield any information about its contents.

Is to possible eliminate all side channels?  I'm not sure whether it
is achievable, in general.  In particular, caching effects and garbage
collection may make it possible to get some partial information about
the contents of Box A, at least in contrived situations.

Example:
    private Brand brand = ...;
    private boolean b = ... some secret ...;
    public Box getOne(Object x, Object y) {
        return brand.sealer.seal(b ? x : y);
    }
You might think that no attacker who uses only the public interface
getOne() can learn anything about the value of the boolean b.  But
now consider this:
    void attack() {
        Box box;
        {
            Object o1 = new int[1] { 0 };
            Object o2 = new int[1000000000] { 0 };
            box = getOne(o1, o2);
        }

        // wait for gc

        // test whether o2 has been garbage collected or not,
        // e.g., by checking for cache effects or disk thrashing
    }
I think that this illustrates that confidentiality is very hard to
guarantee.

>Spoofability
>    Without possession of Unsealer A , it is not possible to determine
>if a Box is an authentic Box A.

Why is this a security requirement?  I would say that "it may not
be possible" -- but it might be possible, and if it were possible,
that wouldn't violate any security requirement.

>Authenticity
>    It is only possible to produce a Box A given possession of Sealer
>A.

Too strong.  For instance:
    Box boxbox = sealerA.seal(sealerA.seal(whatever));
given possession of 'boxbox' and Unsealer A, I can get access
to a Box A, even without possession of Sealer A.

>Unsealer A can determine the authenticity of a Box A and provide
>access to the content of Box A.

Too weak.  If Unsealer A is applied to a box that was returned by Sealer
A, it should succeed and return the content of the box.  If Unsealer A is
applied to anything else, it must throw a ClassCastException.  It's not
just that Unsealer A can determine the authenticity of the box it is
passed, but also that it is guaranteed to act upon that authenticity
and only succeed if given an authentic box.



If you want to make analogies to the definition of security for
public-key signature schemes, we might have three requirements:

Memorylessness:
  Sealer A retains no memory of any arguments passed to it.  Its
computation depends only upon its argument and creation state, but
not on any previous arguments, and it does not mutate its own state
or the state of anything other than the box it returns, and the box
it allocates is newly allocated and not aliased to anything else.
Sealer B retains no memory of any arguments passed to it.  Its
computation depends only upon its argument and creation state, but
not on any previous arguments, and it does not mutate its own state
or the state of anything else.

Completeness:
  Define the adversary as a function satisfying this signature:
    T adversary(Brand<T> br);
Then
    Brand<T> br = keyspace.bear(...);
    T o = br.adversary(br);
    return o == null || o == br.unsealer.unseal(br.sealer.seal(o));
is guaranteed to return true, no matter how you implement adversary().
(Do we need to replace "==" with "equals()"?  I don't think that will
do the trick.)

Strong unforgeability:
  Define the adversary as a function satisfying this signature:
    Box<T> adversary(Brand brand);
Then the code
    final Brand<T> br = keyspace.bear(...);
    final Set<Box<T>> set = new HashSet<T>();
    Sealer<T> s = new Sealer() {
        public String getLabel() { return br.sealer.getLabel(); }
        public Box<T> seal(T value) {
            Box<T> rv = br.sealer.seal(value);
            set.add(rv);
            return rv;
        }
    }
    Box<T> advbox = adversary(new Brand(br.label, s, br.unsealer));
    if (advbox == null)
        return true;
    boolean valid = false;
    try {
        br.unsealer(advbox);
        valid = true;
    } catch (ClassCatchException e) {
        valid = false;
    }
    return !valid || set.contains(advbox);
is guaranteed to return true, no matter how you implement adversary().
(The above assumes that all Boxes returned by the Sealer under
consideration have a trustworthy equals() and hashCode().)