Andrew LeFevre Andrew LeFevre - 11 months ago 141
C++ Question

Generic constant time compare function c++

I'm writing a ProtectedPtr class that protects objects in memory using Windows Crypto API, and I've run into a problem creating a generic constant time compare function. My current code:

template <class T>
bool operator==(volatile const ProtectedPtr& other)
{
std::size_t thisDataSize = sizeof(*protectedData) / sizeof(T);
std::size_t otherDataSize = sizeof(*other) / sizeof(T);

volatile auto thisData = (byte*)getEncyptedData();
volatile auto otherData = (byte*)other.getEncyptedData();

if (thisDataSize != otherDataSize)
return false;

volatile int result = 0;
for (int i = 0; i < thisDataSize; i++)
result |= thisData[i] ^ otherData[i];

return result == 0;
}


getEncryptedData function:

std::unique_ptr<T> protectedData;
const T& getEncyptedData() const
{
ProtectMemory(true);
return *protectedData;
}


The problem is casting to byte*. When using this class with strings, my compiler complains that strings can't be casted to byte pointers. I was thinking maybe trying to base my function off of Go's ConstantTimeByteEq function, but it still brings me back to my original problem of converting a template type to an int or something that I can preform binary manipulation on.

Go's ConstantTimeByteEq function:

func ConstantTimeByteEq(x, y uint8) int {
z := ^(x ^ y)
z &= z >> 4
z &= z >> 2
z &= z >> 1

return int(z)
}


How can I easily convert a template type into something that can have binary manipulation easily preformed on it?

UPDATE Working generic constant compare function based on suggestions from lockcmpxchg8b:

//only works on primative types, and types that don't have
//internal pointers pointing to dynamically allocated data
byte* serialize()
{
const size_t size = sizeof(*protectedData);
byte* out = new byte[size];

ProtectMemory(false);
memcpy(out, &(*protectedData), size);
ProtectMemory(true);

return out;
}

bool operator==(ProtectedPtr& other)
{
if (sizeof(*protectedData) != sizeof(*other))
return false;

volatile auto thisData = serialize();
volatile auto otherData = other.serialize();

volatile int result = 0;
for (int i = 0; i < sizeof(*protectedData); i++)
result |= thisData[i] ^ otherData[i];

//wipe the unencrypted copies of the data
SecureZeroMemory(thisData, sizeof(thisData));
SecureZeroMemory(otherData, sizeof(otherData));

return result == 0;
}

Answer Source

Generally, what you're trying to accomplish in your current code is called Format Preserving Encryption. I.e., to encrypt a std::string such that the resulting ciphertext is also a valid std::string. This is much harder than letting the encryption process convert from the original type to a flat array of bytes.

To do the conversion to a flat array, declare a second template argument for a "Serializer" object, that knows how to serialize objects of type T into an array of unsigned char. You could default it to a generic sizeof/memcpy serializer that would work for all primitve types.

Here's an example for std::string.

template <class T>
class Serializer
{
  public:
    virtual size_t serializedSize(const T& obj) const = 0;
    virtual size_t serialize(const T& obj, unsigned char *out, size_t max) const = 0;
    virtual void deserialize(const unsigned char *in, size_t len, T& out) const = 0;
};

class StringSerializer : public Serializer<std::string>
{
public:

  size_t serializedSize(const std::string& obj) const {
    return obj.length();
  };

  size_t serialize(const std::string& obj, unsigned char *out, size_t max) const {
    if(max >= obj.length()){
      memcpy(out, obj.c_str(), obj.length());
      return obj.length();
    }
    throw std::runtime_error("overflow");
  }

  void deserialize(const unsigned char *in, size_t len, std::string& out) const {
    out = std::string((const char *)in, (const char *)(in+len));
  }
};

Once you've reduced the objects down to a flat array of unsigned chars, then your given constant-time compare algorithm will work just fine.

Here's a really dumbed-down version of your example code using the serializer above.

template <class T, class S>
class Test
{
  std::unique_ptr<unsigned char[]> protectedData;
  size_t serSize;
public:
  Test(const T& obj) : protectedData() {
    S serializer;
    size_t size = serializer.serializedSize(obj);

    protectedData.reset(new unsigned char[size]);
    serSize = serializer.serialize(obj, protectedData.get(), size);

    // "Encrypt"
    for(size_t i=0; i< size; i++)
      protectedData.get()[i] ^= 0xa5;
  }

  size_t getEncryptedLen() const {
    return serSize;
  }
  const unsigned char *getEncryptedData() const {
    return protectedData.get();
  }

  const T getPlaintextData() const {
    S serializer;
    T target;

    //"Decrypt"
    for(size_t i=0; i< serSize; i++)
      protectedData.get()[i] ^= 0xa5;

    serializer.deserialize(protectedData.get(), serSize, target);
    return target;
  }
};

int main(int argc, char *argv[])
{
  std::string data = "test";
  Test<std::string, StringSerializer> tester(data);

  const unsigned char *ptr = tester.getEncryptedData();
  std::cout << "\"Encrypted\" bytes: ";
  for(size_t i=0; i<tester.getEncryptedLen(); i++)
    std::cout << std::setw(2) << std::hex << std::setfill('0') << (unsigned int)ptr[i] << " ";
  std::cout << std::endl;

  std::string recov = tester.getPlaintextData();

  std::cout << "Recovered: " << recov << std::endl;
}

Output:

$ ./a.out
"Encrypted" bytes: d1 c0 d6 d1
Recovered: test

Edit: answering request for a generic serializer for primtive/flat types. Consider this as pseudocode, because I'm typing it into a browser without testing. I'm not sure if that's the right template syntax.

template<class T>
class PrimitiveSerializer : public Serializer<T>
{
public:

  size_t serializedSize(const T& obj) const {
    return sizeof obj;
  };

  size_t serialize(const T& obj, unsigned char *out, size_t max) const {
    if(max >= sizeof obj){
      memcpy(out, &obj, sizeof obj);
      return sizeof obj;
    }
    throw std::runtime_error("overflow");
  }

  void deserialize(const unsigned char *in, size_t len, T& out) const {
    if(len < sizeof out) {
      throw std::runtime_error("underflow");
    }
    memcpy(&out, in, sizeof out);
  }
};
Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download