[Cryptography] Making sure memory erasure is not optimized away

[Henry Baker]

I agree with Ron; modern HW makes it essentially impossible to guarantee that objects can always be
properly erased.

Earlier this year, I had a long-running battle with Rust (which claims to be implement such a capability),
but the usual Rust language type system isn't quite strong enough to be able to deliver on this guarantee.

---
The reason why erasure is such a hard problem, is that it stems from fundamental principles of
thermodynamics, information theory and quantum mechanics; i.e., it isn't just an artifact of computer
science.

QM first: most physical equations are time-symmetric, with or without other things thrown in -- e.g.,'CPT'
states that you can reverse time in physics equations so long as you also reverse charge and parity.

Erasure is asymmetric in time.  Oops!!

This makes erasure exceedingly difficult on a theoretical basis -- indeed, physicists still aren't certain
whether it's possible to guarantee erasure by throwing your computer into a Black Hole.  You see, as
the computer approaches the event horizon, time slows down to zero, thus ending up 'displaying' all
of the computer's bits on the visible (from the outside) event horizon surface of the Black Hole.

All of this physics integrates with Landauer's principle that *computation is thermodynamically free* --
i.e., computation in and of itself does not require any energy dissipation; only the *erasure* of
information (i.e., the zeroing out of a memory location) causes dissipation.

Indeed, many biological systems take advantage of this 'feature' by performing 'mostly reversible'
chemical processes -- e.g., copying DNA is a '2 steps forward, 1 step back' reversible process, with
the final step of tying off the new DNA strand dissipating additional kT's to finish the copy process and
separate the 2 identical strands. If biology didn't do this reversibly, the dividing cells would dissipate
so much heat that they would cook themselves.

Database transactions (ACID) have an analogous process -- reversibly gather up all of the necessary
information to compute the new answer, and then irreversibly *commit* the transaction (which makes
the transaction 'persistent'). Of course with *nested* transactions, persistence is only relative to the
next higher level of transaction.

---
So what kind of a type system is required to guarantee erasure/destruction?

You need a so-called 'linear' type system, in which linear types can only be constructed and destructed
in very precise ways which guarantee linearity.

Thus, a 'secret' in a linear type system would be given a linear typing upon construction, which means
that the secret *cannot be copied*, nor destroyed, except via a very carefully controlled process which
guarantees its complete (and private/secret) destruction.

Notice that no existing computer HW provides such guarantees of linearity, as things like caches, virtual
memory, etc., copy stuff willy nilly. And computer language compilers do similar things.

The Rust people are quick to point out that Rust does NOT implement *linear* types; only 'affine' types,
which can be copied or 'moved', but with no guarantees about clearing contents after 'move'.

A 'move' is roughly analogous to the PDP8's 'DCA' (Deposit and Clear Accumulator) instruction, which
stores the contents of the Accumulator to memory, but simultaneously clears the Accumulator, so that
there is still only one copy of the data. Thus, to copy data on the PDP8 required the programmer to
reload the data back into the Accumulator so it could be deposited again elsewhere in core memory.

In short, the copying of the data occurs when reading from (persistent) memory, not when storing multiple
times from an Accumulator. (Curiously, this is exactly backwards from the way that PDP8 core memory
actually works, since core memory readouts are *destructive*, and the contents of the memory have to
be *written back* if one wants to keep the core memory constant/persistent.)

Linear HW semantics are a tough taskmaster: a linear object is a kind of 'hot potato' which cannot just
be thrown away if the CPU wants to do something else; linear objects must be explicitly dealt with, and
if this causes a deadlock, so be it, as a deadlock is less of a problem than allowing a secret to be
inadvertently copied and divulged.

Programming with linear types can be done using *continuation-passing style* (CPS). A linear object
can be passed as an argument to a routine, which must either *explicitly destroy* it, or pass it to
another routine (possibly another argument -- the 'continuation').  But argument passing of a
linear object uses 'move' semantics, so that routine which passed the linear object can no longer
access it.

Rust could incorporate real 'linear' types (but so far refuses to do so), so this means that there are
currently ZERO non-research computer languages which have true linear types (much less HW that
would faithfully implement such linear types).

To a first approximation, a linear type object is an object whose *reference count* is exactly one, so
whoever has the reference to the object is the only one who can see it, manipulate it; i.e., it 'owns' it.

Probably the best place to start implementing linearity would be in one of the 'TPM'-type components
in modern computer HW.  In particular, we would need a *linear API* to interact with the TPM before
we can even begin to think about implementing real linearity in HW.

I've not yet looked carefully at any existing TPM API's, nor have I yet looked carefully at even OpenSSL
API's, to see what a prospective linear API might look like.

If anyone out there is doing research in this area, I would love to correspond, as I believe that this
area is the next major step in reliable/trusted SW beyond the current Rust-type efforts.

Henry Baker, PhD (MIT Computer Science, 1978)

-----Original Message-----
From: Ron Garret <ron at flownet.com>
Sent: Aug 27, 2022 4:44 PM
To: Phillip Hallam-Baker <phill at hallambaker.com>
Cc: Cryptography Mailing List <cryptography at metzdowd.com>
Subject: Re: [Cryptography] Making sure memory erasure is not optimized away

On Aug 25, 2022, at 12:24 PM, Phillip Hallam-Baker <phill at hallambaker.com (mailto:phill at hallambaker.com)> wrote:
[Before we start, use language X instead is not an answer here.]
 
We all know array bounds checking etc. is a good thing to have to write any application code. But the cost of abstracting away memory management is that cryptographic code has the very particular property that we want to ensure data is cleared AFTER USE rather than BEFORE REUSE.
 
A lot of applications written in high level languages are vulnerable to attacks when someone uses portable assembly language, aka C to write a program that allocates large chunks of memory and then greps through it looking for 'good stuff'.
 
So the question is how to ensure this does not happen by implementing disposal mechanisms THAT DO NOT GET OPTIMIZED AWAY.
 
See here is the thing. I can check my code and check my code but I can only check the current version of the compiler/optimizer. And some of the things I know the C# optimizer is now doing are pretty hard core. Yes, when generating assemblies, it can optimize across assembly boundaries now.
 
I am pretty sure most other high level languages suffer from the same thing unless there is a mechanism to explicitly state 'do not optimize'. Same goes for things like the Montgomery ladder which isn't as reliably constant time as some people might imagine. 
 
Has anyone got pointers to ways to make sure this is done right?


This is a Really Hard Problem that goes beyond the language level.  Nowadays these kinds of optimizations happen *in hardware*.  Even in assembly language there is often no way to guarantee that if you write a word to memory that anything actually happens beyond the L0 cache.  It is simply not possible to draw a reliable security perimeter around a *process* on modern hardware.  This is one reason secure enclaves have become a thing.
 
rg

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://www.metzdowd.com/pipermail/cryptography/attachments/20220828/7d9644ad/attachment.htm>