Re: A (Low-Level) Opaque Object Proposal for R5RS

[Michael R. Blair <ziggy@martigny.ai.mit.edu>]

>--------------------------------------------------------------------------
> lack of experience with authorization constructs in the Lisp family of
> languages would have hampered efforts to support it.
>--------------------------------------------------------------------------

I'm not aware of any authorization constructs in the Lisp family of
languages.  Then again, I don't follow much of the literature from the
security/database community very closely... just enough to stay abreast of
current trends.

>--------------------------------------------------------------------------
>  ...  Its _sole_ purpose is to provide an opaque type/object
>  facility completely orthogonal from any other language mechanism.
>
> This is an excellent reduction.  I think you have reached the heart of
> the matter.
>--------------------------------------------------------------------------

I am ecstatic to hear that.  Thank you for validating my efforts.

>--------------------------------------------------------------------------
>  I [propose] the following four procedures be standardized for Scheme and
>  their names be added to the list of reserved identifiers:
>  --------------------------------------------------------------------
>  [1].     (MAKE-OPAQUE-TYPE                              . <passkey>)
>  [2].     (     OPAQUE-UP   <opaque-type>       <object> . <passkey>)
>  [3].     (     OPAQUE-DOWN              <opaque-object> . <passkey>)
>  [4].     (     OPAQUE-TYPE                     <object>            )
>  --------------------------------------------------------------------
> 
> A few minutes with a Thesaurus finds some descriptive transitive verbs
> which might better serve users' memories than OPAQUE-UP and
> OPAQUE-DOWN:
>
>  OPAQUE-UP: obscure hide darken obfuscate perplex cloud baffle perplex
>  scramble jumble
>
>  OPAQUE-DOWN: illumine clarify realize fathom illuminate elucidate
>  explicate
>
> I find particularly appealing that a computer language might have the
> operators: OBFUSCATE and ELUCIDATE.
>--------------------------------------------------------------------------

The (admittedly bland) names UP and DOWN were chosen based on my (limited)
experience with Clu, one of the proposals for Ada that didn't make it into
the final Ada standard.

In Clu, the thing that converts an abstract type into its underlying
concrete representational (`rep') type is called DOWN, and that which
converts rep types into abstract types is called UP.  I believe these are
intended to suggest moving UP and DOWN across layers of abstraction
barriers and levels of abstractness.  I guess I should have explained that.

Alternative names might be:

 ABSTRACT->CONCRETE  &  CONCRETE->ABSTRACT

or

 ABS->REP  &  REP->ABS

etc., consistent with the other type conversion procedures in Scheme (like
vector->list and number->string).

The names are not important to me.

>--------------------------------------------------------------------------
>    -------------------------
>    I. Opaque Object Creation
>    -------------------------
> 
>    [1]. (MAKE-OPAQUE-TYPE . <passkey>)
> 
>     Returns a predicate (a procedure of one or more arguments) that returns
>     #T only on objects coerced to this opaque type by a call to OPAQUE-UP
>     with this predicate as the <opaque-type> argument and with matching
>     <passkey>, if any was supplied in the call to MAKE-OPAQUE-TYPE.
> 
>     The resulting ``opaque type'' predicate is not EQ? to any datum except
>     itself (i.e., it is a ``unique'' object).
> 
> At first I was leery of the uniqueness requirement because I thought
> it would require an implementation to make procedures non-EQV? which
> were allowed to be EQV? by R4RS:
>
> But on further thought, it is correct as it is -- by using the OPAQUE
> constructs, a user is explicitly asking for an abstraction barrier.
>--------------------------------------------------------------------------

Two points:

 1. The predicate generated by MAKE-UNIQUE-TYPE can be wrapped in some
    state-revealing shroud so that the issue of EQV procedures does not
    come into play.  Months ago I stirred up a discussion on the Scheme
    Digest (a.k.a. comp.lang.scheme) about MAKE-UNIQUE-OBJECT which
    presented this sort of issue as a puzzle.  I won't go into detail about
    that here, but a similar implementation hack could resolve this issue
    here too.

 2. This uniqueness criteria is _precisely_ what allows a user to define
    a new, unique `user-defined' type that does not satisfy any of the
    existing type predicates from Section 3.4 of R4RS.  This is the low-
    level mechanism that, for example, could allow MAKE-RECORD-TYPE to make
    a new, distinct record type per invocation.  Similarly for modules,
    restarts, and any other new entity someone might want to be distinct
    from the existing Scheme data types.

>--------------------------------------------------------------------------
> Latitude
> --------
> 
>    Under such a diversity, sharing source code would still be possible.
>    Sharing executables and/or marshalling opaque data and exchanging it
>    between incompatible systems is already quite _im_possible,
> 
> Databases are routinely used to exchange data, parts of which have
> access restricted to certain authorizations.
>--------------------------------------------------------------------------

But when two systems share a common database in order to exchange data,
they are using the database as a go-between to make the incompatible
systems find a compatible intermediate representation.

I was not trying to get into the issues of persistent data or data exchange
in bringing up implementation latitude.  What I had in mind was trying to
reassure those who might lose sleep over the thought that their binaries
might not be portable between systems that choose incompatible underlying
representation/enforcement policies for opaque types. I was just trying to
point out that this has not made a bad situation any worse than it already
is.

Any common data format proposal would be well beyond the scope of this
proposal.  That is yet another separate issue that should also be addressed
on it own ground.

>--------------------------------------------------------------------------
>    so nothing is
>    lost by giving implementors this latitude.  And people worried about
>    shipping proprietary code to binary compatible sites with unknown opaque
>    type enforcement could either encrypt the passkeys embedded in their code
>    on a per-site basis (requiring site registration) or they could adopt
>    some
>    site certification protocol, or they could require a legally binding
>    contract to be signed.  Whatever.
> 
> In your Matthias example, I am not certain at what level(s) you have a
> security guarantee.  Is it that once the system is debugged Matthias
> will know that if his encryption (OPAQUE-UP) and decryption
> (OPAQUE-DOWN) are secure, then his whole (compiled) program is?
> 
> Or is it that, even when interpreted, his program is secure from
> attack in Scheme (but not necessarily from core dumps).
>--------------------------------------------------------------------------

I was too vague in what I meant by encryption in this case.  I was not
referring to OPAQUE-UP and OPAQUE-DOWN as somehow `encrypting' the datum.
I was alluding to PGP or DES encryption of the _passkeys_, assuming they
are strings.

For example, some programmers are paranoid control freaks (none of us,
surely, but they do exist).  Such people are not content to know that they
themselves are not violating any opaque type abstraction barriers: they
feel driven to impose this discipline on everyone else who might use their
code (often under the guise of a company `coding standard').  Dijkstra's
name came up on this list recently.  He is this sort of person. And now
that I think about it, I should not have used the fictional name
`Matthias'' in this context, since I'm not sure any particular person who
might be named Matthias feels as strongly about this as Dijkstra.

At any rate, those obsessed with absolute opacity could always trade
performance to appease their neurosis as follows:

  In compiled code using localized opaque types, the passkey stuff can
    all be compiled out.  (This is like flattening data structures using
    partial evaluation and arity raising, assuming you wrap all your opaque
    type UP/DOWN/MAKE code inside a single code block or you use the sort
    of clever compiler tricks Kent alludes to for dropping slots in his
    record proposal.)  In this case, no passkeys would appear as constants
    in the compiled code blocks, so no threat of revealing an opaque type's
    passkey through examination of the binaries exists.  UNIX's `strings'
    and debuggers like gdb cannot reveal what is not there. No performance
    hit comes into play here.

  For opaque data that is passed around as first class data, the opaque
    type, and hence its passkey, must conceptually escape into the run-
    time heap.  This might allow someone using `gdb' or similar debugger to
    poke around in memory to discover the passkey of some opaque type to
    then go break a bunch of abstraction barriers.  Again, this sort of
    thing keeps some people awake at night.  Not me.  In this situation,
    however, OPAQUE-UP could generate a cryptographic checksum for each
    opaque datum and use that to secure the passkey. So, for example, when
    I try to OPAQUE-DOWN some opaque datum, the checksum of the datum could
    be passed to the low-level passkey matcher along with the passkey of
    the opaque type.  The low-level matcher would then do whatever crypto
    magic is required to determine if they match.  This way, finding the
    passkey constant embedded inside one opaque datum would not compromise
    other opaque data of the same opaque type.  Further, the passkey
    embedded in the opaque types (predicates) can themselves be encrypted
    using a checksum mechanism based on the predicate code block.  Finally,
    each binary executable I ship to a site could encrypt all the embedded
    passkeys in all data by using a per-site master key and each site using
    the code could use a per-site private/public key pair to seal data
    shipped among remote databases and object repositories, etc.  This
    allows control over attempted key sharing between consumers of my code
    as well as data privacy between sites sharing a common database, etc.

Again, I don't have any interest in engaging in this sort of rampant
Dr. Strangelovean paranoid programming.  But some people do.  I was just
trying to hint that a completely separate opaque object mechanism, removed
from all other mechanisms like records, modules, and so on, would give
neurotic programmers just the rope they want to go and hang themselves
exploring the cloak and dagger world of safe/secure/private data.

And again, I'm not proposing we discuss any of this in whatever text might
actually appear in the R5RS, assuming this opaque type proposal is adopted
for standardization.  I'm just pointing out that this is another good
reason to separate out the opacity stuff from any proposal being
considered.

Specifically, Bill and Kent's on-going exchange on how to secure the
abstraction barriers in the rapidly converging record proposal seems to me
to be a case in point where a fine proposal is being stalled due to
concerns over opacity.  It is fine with me if this gets settled without any
attention paid to this orthogonal opaque type proposal.  I'd rather have a
standardized record mechanism with a minor ``slot names as unique strings''
blemish as an opacity concession than not have a record mechanism at all
because some folks veto it due to lack of opacity.  I feel this way even
though I would prefer symbols as slot names since a separate opacity
mechanism could seal all this up inside a MAKE-OPAQUE-RECORD wrapper,
within which one could play whatever unique string games one wanted atop an
underlying non-opaque standardized record mechanism.

I don't want to be accused of delaying the record proposal.  I'm just
trying to avoid this sort of several-week delay for the next new thing
proposal that comes along since I suspect that every new widget that comes
along will be subjected to the same opacity scrutiny as the record proposal
is currently enjoying.

I just want to try to settle the whole issue once and for all on its own
grounds so it won't continue to hijack future progress in Scheme.

>--------------------------------------------------------------------------
> I am interested in storing and retrieving opaque data in files in such
> a way as to preserve its opacity or at least its key associations.
> This would seem to require that keys be externally representable and
> that distinct keys be non-equal?.  With those conditions, should it
> work?
>--------------------------------------------------------------------------

I think it is up to you to find a passkey mechanism that fulfills your
personal needs and desires.  This is precisely why I left the details of
implementing passkeys up to the implementor.

In MIT Scheme, for example, (and in Scheme 48, from what I've heard), just
being able to fasdump and fasload (read: pickle and unpickle) passkeys and
opaque types and data should suffice.

I don't want to venture down the slippery slope of prescribing a style of
passkey manipulation.  People should be allowed to experiment with the
whole spectrum of security and efficiency, limited only by their own
imagination and not by any narrow standard interface.

Who knows, we may even get the Java drones to look our way for inspiration,
rather than the other way 'round.

>--------------------------------------------------------------------------
> OPAQUE data seems to be related to weak pointers.  If the key for some
> OPAQUE data has been lost, then, subject to the reconstructability of
> keys, all OPAQUE data with that key can be collected, because it
> cannot be ELUCIDATEd again.  If it were collected, then EQ?-ness
> (different data being not EQ?) of OPAQUE data would then not be
> guaranteed.  That is not necessarily bad -- it might make OPAQUE data
> more secure if unauthorized pointers to it were subject to change.
>--------------------------------------------------------------------------

Bill has already responded to this.  I liked his response and have nothing
to add. (He has much more expertise in that area than I do.)