[Cryptography] Other obvious issues being ignored?

Henry Baker hbaker1 at pipeline.com
Thu Oct 22 12:19:52 EDT 2015


At 05:13 PM 10/21/2015, Ray Dillinger wrote:
>it is impossible to write secure code in Lisp (because garbage collection

I have a 1992 "Linear Lisp" that does precisely what you want:
complete programmer control of data *copies*.

The "linear" here means all reference counts are exactly *one*, so
when an object is deleted, it can (and *will*) be immediately
recycled/zeroed.

(Note that a "linear" implementation should most likely run with
*interrupts mostly disabled*, because the implementation would
like to carefully control the conditions under which someone else
(e.g., an interrupt routine) can examine its memory.  Those who
have programmed *microcode* will recognize this style of machine
language programming in which interrupts are allowed only at
certain pre-determined instruction boundaries.)

Duplicating an object (DUP) in a "linear" language means *deep
copying* the object, so that it remains unshared.

While a completely "linear" programming language would appear to
be very inefficient -- e.g., a Lisp interpreter using only "linear"
objects would have to deep-copy the interpreted Lisp source code
for each iteration/recursion -- it can be implemented much more
efficiently using *reference counts* "behind-the-scenes".

Basically, all CONSing is done using *hash cons* (which is O(1)). 
If the object already exists in the hash cons table, the reference
count is incremented and the existing object is returned.  DUP
simply increments the reference count instead of deep copying.

The key idea is that any modifications to the list structure
unshares (decrementing the reference count in the process)
prior to performing the operation.

So long as the "behind-the-scenes" implementation fastidiously
recycles list structure whose reference counts reach zero ("deep"
recycle), then there will be no dead data lying around to leak. 
In particular, a "linear" Lisp interpreter would DUP (++refcnt)
the interpreted code prior to each iteration and "recycle"
(refcnt--) the code being interpreted.  The refcnt DUP ensures
that the interpreter can run fast; the refcnt manipulations
are all O(1), and can be substantially optimized -- e.g., by
utilizing *swaps*, *rotates*, etc., which preserve reference
counts and thereby avoid these additional memory references.

(We note that swaps/exchanges in some architectures -- e.g.,
x86 -- might be *slow* precisely because they are fastidious
wrt not leaving copies around.  For certain calculations,
security is more important than speed, so this fastidiousness
may be acceptable.)

In my spare time, I've been working on a compiler from Linear
Lisp direct to assembly/machine language.  I hope to be able
to publish it at some point.

Here's the "Lively Linear Lisp" paper:

http://home.pipeline.com/~hbaker1/LinearLisp.ps.gz

http://home.pipeline.com/~hbaker1/LinearLisp.html

Here's a paper talking about "linear" (unshared) types:

http://home.pipeline.com/~hbaker1/Use1Var.html

Here's my paper repository; note any papers with "linear" in
their title:

http://home.pipeline.com/~hbaker1/



More information about the cryptography mailing list