[Cryptography] [Crypto-practicum] Secure erasure in C.

[Ron Garret]

On Sep 7, 2016, at 1:04 PM, Ray Dillinger <bear at sonic.net> wrote:

> 
> 
> 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?

No, but it seems like overkill to me.  AFAICT the problem is more straightforward than that:

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

The problem seems to me to be that the buffer contents are not volatile.  You want:

static void *(*const volatile deleter)(volatile char*, int,size_t) =
  (void *(*const volatile)(volatile char *, int, size_t)) memset;

static void erase(volatile char *buf, size_t len) { deleter(buf, 0, len); }

But why not simply:

void erase(volatile char *buf, size_t len) {
  for (int i=0; i<len; i++) buf[i]=0;
}

Or, if you really want to be paranoid:

int  erase(volatile char *buf, size_t len) {
  for (int i=0; i<len; i++) buf[i]=0;
  for (int i=0; i<len; i++) if (buf[i]) return -1;
  return 0;
}

or if you want to be really REALLY paranoid:

volatile int _dummy = 0;

int  erase(volatile char *buf, size_t len) {
  for (int i=0; i<len; i++) buf[i]=0;
  for (int i=0; i<len; i++) if (buf[i]) return -1;
  _dummy++;  // Or _dummy = get_random_number() or gettimeofday()
  return 0;
}

rg