[Passwordsafe-devel] secure allocator

[Edward E. <ed...@ya...>]

As promised, I have performed a more thorough review of the "secure" 
CDHAllocator in the BSL library at http://www.bitvise.com/bsl.html.
I'm somewhat embarassed by my earlier assessment that it looked 
"pretty good", even if it was only based on a five-minute perusal.
After only a couple hours studying the code, I've found a half-dozen 
serious flaws and can't recommend its use to anyone.

Here is a summary of the problems I encountered:

 1) CDHAllocator subclasses std::allocator.  I see two potential
    problems with this.  One, std::allocator provides no virtual 
    destructor.  I can't think of a situation where this would cause 
    problems; I haven't seen a situation where allocators are used 
    through pointers or passed by value such that slicing can occur.
    Allocators are not supposed to have non-static member variables 
    anyway (so that two allocators of the same type are always 
    equal), so destruction may be irrelevant.  However no good can
    come of it.

 2) (subclassing, continued) CDHAllocator inherits the operator== 
    from std::allocator.  Comparing a CDHAllocator and a
    std::allocator will therefore be possible (which it shouldn't), 
    since a CDHAllocator is in fact a "const std::allocator&".
    Moreover, this comparison will return true, indicating one type
    of allocator can be used to destroy the other's memory.  I don't 
    know when this would happen but if it did the results would be
    disastrous.  Just the possibility makes me very uncomfortable.

 3) Thread synchronization is provided by a global lock variable 
    (g_lockDH).  Initialization of this lock therefore occurs at an 
    unspecifed time during the program's static initialization.  If a 
    method called elsewhere during static initialization attempts to 
    use CDHAllocator, the lock may be uninitialized and the results 
    undefined (but almost certainly bad).  This may occur for instance
    in the constructor of a vector<char, CDHAllocator<char> > declared 
    at global scope in another translation unit.  The same applies to
    the global variables g_dwPageSize and g_DHBlock.

 4) The global lock provides Lock() and Unlock() methods to acquire
    and release the lock.  If an exception is thrown between these
    two calls, the lock will never be released.  DieHardAlloc, 
    DieHardFree, and DieHardVerifyClean are all subject to this 
    problem. What's worse, CDHBlock explicitly throws exceptions in
    the Allocate and Free methods which DieHardAlloc and DieHardFree 
    call.  For a reliable allocator, especially a secure one where 
    an adversary may be actively trying to cause exceptions, 
    disregarding exception safety and deadlocks is not an option.  

 5) It uses a map and a multimap to keep track of free blocks, a 
    structure far too inefficient for fundamental operations like 
    memory allocation.  Every memory allocation requires at least a
    binary search and two erases, usually accompanied by two inserts
    into the maps as well.  Maps guarantee logarithmic element access
    times but have large constant factors and do not perform well on
    small data sets.  

 6) On memory allocation failure, CDHAllocator throws its own 
    CDHAllocationFailed exception instead of the accepted 
    std::bad_alloc.  This applies to the CAllocator class as well.

 7) On deallocation, it only overwrites each byte a single time with
    0x00.  A safer approach would be to overwrite memory several times
    with different values, including 0x00 and 0xff.

 8) Uses std::fill_n to zero out the memory on deallocation.  Because
    DieHardFree passes unsigned char *'s as iterators, std::fill_n
    loops over the memory one byte at a time.  This is horribly 
    inefficient.  memset (for zeroing out) and memcpy (for overwriting
    with a string of random bytes) are much better.

There may well be other problems with CDHAllocator; I stopped short
of examining CDHBlock's Allocate and Free methods in detail.  I 
decided at this point nothing was salvageable and I needed to write
my own secure allocator from scratch.  I should have it done within
a few days, at which time I'll pass it along.

Edward Elliott

__________________________________________________
Do You Yahoo!?
Yahoo! Sports - live college hoops coverage
http://sports.yahoo.com/