[Cryptography] Secure erasure in C.

Ray Dillinger bear at sonic.net
Wed Sep 7 16:04:17 EDT 2016



When possible, I do operations that can be done in finite
bounded memory using a static volatile buffer to hold
sensitive data.  Design the program right so you absolutely
know how much memory the operations need, and the static
volatile buffer solves many problems.

Writes and reads aren't optimized away regardless of whether
you're going to read that space again before exiting.
Transient copies and virtual-memory caches don't get made
because if the compiler can't assume the copies remain in
sync to the buffer, then making copies is useless.  Finally
out-of-memory errors don't happen at runtime (and can't be
forced by an attacker to happen at runtime) if you've
preallocated the secure buffer that you keep using.

That is definitely the preferred solution. As far as I know,
the desired behavior is absolutely required by all versions of
the C standard and the availability of static volatile buffers
is the main reason why I write security code in C despite all
of C's sharp pointy bits, vicious free-swinging hooks and
bloody blades.

But every so often I need to securely delete a buffer that I
get from somewhere else, or flatten a stack image before exiting
a routine, and that turns out to be harder.

Non-volatile variables and buffers have MANY problems that
mean they should usually be avoided for secure data. The
compiler making copies in order to parallelize operations or
relocating data for whatever other reasons, or the OS deciding
that it needs to make a disk cache for virtual memory on a
machine whose cache partition is unencrypted, etc.  Those
problems can only be managed with careful configuration of
the machine, runtime environment, and OS.

But aside from that,  it's actually hard to get a non-
volatile buffer deleted.  The short version of the story is
that most languages don't have volatile buffers, and the
one that does has a standard that says unless something
in the "officially observable" output is required by the
standard, the compiler doesn't have to do it.  We want to
delete non-volatile buffers when we're done with them, but
when we're done with them we don't read them anymore, and
the compiler often concludes that therefore the writes
don't have to happen.  We often rely on observed behavior
instead of the language standard, but in many cases observed
behavior is just the optimizer not being able to figure out
that the language standard will allow it to get away with
skipping something.

In response to a compiler that made a completely unexpected
pessimization of my code, I've recently been forced to revisit
secure erasure of non-volatile buffers.

For years I'd been defining 'erase' using

//////
static void *(*const volatile deleter)(void*,int,size_t)=memset;
static void erase(void *buf,size_t len){deleter(buf, 0, len);}
//////


which, IIRC, I originally copied from the PGP source code
back when Hal Finney was working on it.

It's a reasonably clever bit and has been standard in crypto
code for a long time. Declaring the pointer to the routine
as volatile  means the program is absolutely obligated to
access that pointer when the routine is called.  It also
means that the compiler can't make static assumptions about
what the routine does because the pointer might change
outside of program control.  And we've been assuming that
because the compiler isn't allowed to guess what the routine
does, it has to call it in order to make sure that if it
does anything "observable" that thing actually happens.

And this has been true through all of computing history,
Up to now.

Unfortunately while the standard absolutely obligates the
program to access the function pointer and doesn't allow it
to assume that the pointer value (and therefore the routine
it points at) is unchanged, it does not obligate it to
actually execute the routine.

And someone recently discovered some obscure combination of
mind-boggling optimization levels, compilation environment,
and system settings under which an Intel compiler actually
doesn't.  Usually this kind of thing is discovered w/r/t
gcc: Intel is something of a surprise.

When static analysis reveals that calling the function which
'deleter' is initialized with, does not in fact change the
contents of volatile memory, nor non-volatile memory that
the program will later access, nor cause other un-skippable
side effects, the program can cache a copy of the function
pointer.  Then when the call to 'deleter' is made, it must
read the volatile pointer - which completes its obligation
to the standard. But then, instead of just executing the
procedure, it is allowed to compare the pointer's value to
the cached value, and if they are identical may conclude
that it need not actually execute the routine.

So.  I'm redefining 'erase.'  I think that these steps
will ensure that secure deletion happens and would like
feedback if anyone can think of any way for a compiler
compliant to the language standard to pessimize this
method.
   1) Make calls to the RNG to get a key and IV, allocating
      the space for key and IV out of a static volatile
      buffer where the normal secure-deletion procedure
      will work on them.
   2) Encrypt the buffer in place using that key and IV.
   3) Calculate a CRC of the encrypted buffer.
   4) Write the CRC to a volatile variable.
   5) Clear the key and IV from the volatile buffer.

Rationale/Assumptions:
   1) Calls to the RNG cause side effects that can't be
      elided (changes to RNG state), and produce results
      which a static compiler cannot predict.
   2) Encryption in-place in CBC mode using a random key
      and IV should leave no recoverable information about
      the original contents of the buffer once the key and
      IV are secure-deleted. (Note; in-place encryption
      requires avoiding creation of ciphertext longer
      than the original buffer.  The IV should not be
      written to the buffer, and I can encrypt the last
      block starting at a different offset so it overlaps
      the previous block placing its end is at the end
      of the buffer).
   3) The compiler can't elide the encryption because
      the encrypted value will be used to calculate a
      CRC.
   4) The compiler has to calculate the CRC because it
      can't otherwise figure out what it has to write
      to a volatile variable and isn't allowed to guess.
   5) The volatile variable containing the CRC is not a
      risk because of random key and IV; it contains no
      recoverable information about the original contents
      of the buffer (and anyway it's in the volatile
      buffer so it can be secure-deleted normally).
   6) Although some "observable" effects are data-
      dependent, there are no possible buffer contents
      that could affect its operation for purposes of
      an attack.  It is not vulnerable to timing attacks
      because the time taken for encryption and CRC
      does not depend on the buffer data.
   7) Copies of the buffer will not be made because I'll
      be calling a competently implemented encryption
      library. I know this is the big assumption but
      encryption implementation flaws are a much more
      serious threat which must be fixed for other
      reasons and fixing them for other reasons will
      fix them for secure deletion as well. Therefore
      they are out-of-scope as a problem specific to
      secure deletion.

Can anybody think of any way that a standard-compliant
compiler is allowed to mess this up?

				Bear


-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 819 bytes
Desc: OpenPGP digital signature
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20160907/226be127/attachment.sig>


More information about the cryptography mailing list