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

[David Hopwood]

Tyler Close wrote:
> Hi Kevin,
> 
[...]
>>>http://waterken.sourceforge.net/javadoc/org/ref_send/brand/package-
>>>summary.html
>>
>>Looking at this page, I note that it uses the term "Brand" in the
>>opposite sense that E does. The "brand" of E's built-in sealing
>>system is the facet of minimal authority; yours is the maximal.
>>
>>Most Authority <-----------> Least Authority
>>                   Sealer
>>                     /\
>>                    /  \
>> [Sealer,Unsealer] /    \  elib.sealing.Brand
>>    (your Brand)   \    /
>>                    \  /
>>                     \/
>>                   Unsealer
> 
> 
> In my opinion, the term "brand" in E is overloaded. I think it could
> be interpreted as describing the return of the getBrand() method, or
> the return of the makeBrand() method. For clarity, I chose to give it
> a single meaning, the return of the makeBrand() method and use the
> term "label" for the other meaning.

The return of makeBrand() is a "sealer/unsealer pair", not a brand.
This may mean that the 'makeBrand' function is misnamed, but the
terminology is otherwise consistent; I think that consistency is
important here and the terms should not be changed without good reason.

>>The elib.sealing.Brand (from a client's perspective) reliably
>>identifies the group without giving any other authority;
> 
> It depends on what you mean by "reliably". Any object possessing the E
> Brand can masquerade as a member of the group. I think this fact is
> easily missed since E's Brand supports identity comparison and so
> seems to provide authority.
> 
>>it is available everywhere your protocol offers its "label".
> 
> Correct. I renamed this attribute to label and changed its type to
> String to better communicate that this attribute does not offer any
> guarantees that can be relied upon.

Changing the type to String prevents the use of private (i.e. closely
held or anonymous) Brands. I don't see any good reason to do that.

> To find out if a Box is an
> authentic Box, you must unseal() it, not just check its label.

Yes, this is important. But I don't think that changing the type to String
helps much by itself to clarify it.

[...]
>>>Spoofability
>>>    Without possession of Unsealer A , it is not possible to determine
>>>if a Box is an authentic Box A.
>>
>>In E-on-Java, possession of the brand is sufficient:
>>
>>   ? def SealedBox := <type:org.erights.e.elib.sealing.SealedBox>
>>   # value: SealedBox
>>
>>   ? (sealer.seal("foo") :SealedBox).getBrand() == brand
>>   # value: true
>>
>>I do not know whether this or its lack is a desirable property, nor
>>whether it is possible to implement in a cryptographic system. This
>>property could be removed from E by hiding the SealedBox guard.
> 
> As I discussed above, the E-on-Java implementation does currently
> implement spoofability, since any object with the E Brand can
> masquerade as an authentic Box. Your comments above confirm that this
> fact is subtle and easily missed. In the above E code, "sealer" could
> refer to an object that creates a SealedBox of a different E Brand,
> but that claims to be of the "brand" Brand.

Yes. The corresponding cryptographic property is "recipient-hiding encryption",
where a ciphertext does not leak information about which public key was used to
encrypt it. This was discussed on sci.crypt in the following thread:
 <http://groups.google.co.uk/group/sci.crypt/browse_thread/thread/6d55f2194ec361ef/bba7b80796f095fd>

I later did some work on formalizing this property. Following the notation and
the approach to defining security properties from [DHIES], we have:

  Adv_Hide(A, ASYM) = 2.Pr[(sk_0, pk_0) <- ASYM.keygen;
                           (sk_1, pk_1) <- ASYM.keygen;
                           b <- {0, 1};
                           A.guess(pk_0, pk_1,
                                   ASYM.encrypt_(pk_b),
                                   ASYM.decrypt_(sk_b)) = b] - 1

That is, the security of a scheme ASYM is determined by an attacker A's
advantage in the following experiment:

 - generate two random key pairs: (sk_0, pk_0) and (sk_1, pk_1);
 - flip a fair coin, b = 0 or 1;
 - give the attacker both public keys, an encryption oracle for pk_b, and
   a decryption oracle for sk_b;
 - the attacker must guess b with probability significantly > 1/2.

Of course the scheme must also be secure in other senses usually required of
a public-key encryption scheme.

[There is a generalization of this that covers the case of "blinded" encryption,
where multiple equivalent-but-distinct public keys can be derived. See
<http://groups.google.co.uk/group/sci.crypt/msg/cadfb95e695c4b25>
for the gory details, although I'm not sure blinding is relevant here.]

It is fairly easy to come up with encryption schemes that provably have this
security property (the simplest way is to use [DHIES] in a cyclic group with
common parameters for all keys).

>>>Integrity
>>>    The content of a Box A cannot be mutated.
>>
>>This is not a property of the sealing system provided by E. The box
>>cannot be mutated, but its contents do not lose mutability.
> 
> E-on-Java does implement Integrity as I've defined it. Your second
> sentence above is the crucial one needed to understand the precise
> meaning. You can seal a reference to a mutable object in a Box, but
> you can't change which reference is in the Box once sealed.

An encryption scheme with the corresponding property is called "nonmalleable",
and I suggest using the same term here.

It is implied by "indistinguishability under adaptive chosen ciphertext attack" --
see Definition 4 in [DHIES] (note that this also implies privacy, i.e.
protection + confidentiality).


[DHIES] Michel Abdalla, Mihir Bellare, Phillip Rogaway,
        "DHIES: An encryption scheme based on the Diffie-Hellman Problem,"
        September 18, 2001.
        <http://www-cse.ucsd.edu/users/mihir/papers/dhaes.pdf>

-- 
David Hopwood <david.hopwood at industrial-designers.co.uk> (note new address)