2
\$\begingroup\$

At the company i work we have a system where an user is presented with a question and some alternatives to choose from. The question and answers are generated at runtime. In order to simplify the process among the sent payload is an encrypted JSON string that contains some "sensitive" (but not that much) information and which of the alternatives is the correct one.

This might seem weird at first but keep in mind that this is not business critical and therefore if an user can cheat on some questions, that's ok.

So i designed the following "encryption protocol":

  1. Generate hundreds of random keys and store them
  2. When the question and answers are selected, choose one key at random, encrypt all the necessary information and put the key index at the beginning

So when the user submit his answer we take the key index, retrieve the key, decrypt the payload and check if the answer is the correct one.

My first option was to use some existing and tested encryption library (we use PHP internally) and my first implementation used Halite. Things worked great, but it was too slow for our use case (also i think it's really overkill to this simple use case). So i decided to find some simpler encryption algorithm and ended up discovering the XXTEA cipher it seemed simple and fast. Perfect for our use case.

So i started looking for some library for PHP that implemented it and while i did find some i wasn't very satisfied with them (either performance wise or code quality wise).

So i used this given all that i decided to use this opportunity to create my own XXTEA implementation (yeah, i'm aware of the "don't implement your own crypto" mantra, but it seemed easy enough) in C++ and create a PHP extension of it. And this sort of became a pet project for me, so i decided i was going to publish it and open-source it. And where we are.

What i'm looking for in CodeReview is:

  1. Can my code be made more reusable ? Is the API i designed good?
  2. Are there any (obvious?) performance optimizations that i missed?
  3. Is my implementation correct? it's working great so far, but you never know
  4. Is my code idiomatic, can i make it better? if so how?
  5. Comments on the whole process, some new ideas maybe.
  6. Bonus: Can i use SIMD instructions to improve performance? I know very little about it but always wanted an excuse to read up on it and use it

The whole code can be seem here: Github repo

The whole library is contained in a single header: xxtea.hpp and all necessary functions are inside the xxtea namespace.

The whole API is std::string base because that was the requirement, but i do plan on implementing a binary interface.

So after all that to the code:

The first function provided is the encrypt, which as the name states encrypts the passed string.

/**
 *  Encrypts text using Corrected Block TEA (aka xxtea) algorithm
 * @param plaintext String to be encrypted. Handles utf-8.
 * @param password Password to be used for encryption (only 128 bits are used).
 * @return Encrypted text as uint32_t vector
 */
inline bytes encrypt(const std::string &plaintext, const std::string &password) {
    auto text = internal::to_blocks<std::uint32_t>(plaintext);
    auto key = internal::to_blocks<std::uint32_t>(password);

    encode(text, key);

    return text;

}

The first thing it does is to convert both strings to a std::vector of 32 bits integers, as required by the XXTEA cipher. I tried to make this function as portable as possible, because i think it can be used for other projects:

template<class BlockType>
std::vector<BlockType> to_blocks(std::string string) {

    constexpr unsigned short block_size = std::numeric_limits<BlockType>::digits;

    static_assert(block_size >= CHAR_BIT, "Can't be smaller than CHAR_BIT");

    string.resize(round_up(string.size(), block_size), '\x03');

    auto number_of_bits = string.size() * CHAR_BIT;
    std::vector<BlockType> blocks{};
    auto n_blocks = std::max(number_of_bits / block_size, 1UL);
    blocks.resize(n_blocks, 0);

    constexpr auto fit_size = block_size / CHAR_BIT;

    for (std::size_t i = 0; i < string.size(); ++i) {
        auto bucket = (i * CHAR_BIT) / block_size;
        auto shift = CHAR_BIT * (i % fit_size);
        auto c = static_cast<unsigned int>(string[i]);
        blocks[bucket] += c << shift;

    }

    return blocks;
}

The main idea here is to splice the string characters into groups of 32bits. Also if the string passed isn't a multiple of the block_size the string is padded with the ETX character. The round_up function just returns the first argument rounded up to the next multiple of the second argument.

The to_blocks function has a sister function that takes a std::vector of std::uint32_t blocks and transforms them into a string:

template<class BlockType>
std::string to_string(const std::vector<BlockType> &blocks) {
    constexpr unsigned short block_size = std::numeric_limits<BlockType>::digits;
    constexpr auto fit_size = block_size / CHAR_BIT;
    std::string s;
    s.reserve(fit_size * blocks.size());

    for (const auto &i : blocks) {
        for (std::size_t j = 0; j < fit_size; ++j) {
            auto shift = CHAR_BIT * (j % fit_size);
            auto c = static_cast<char >(i >> shift);
            if (c != '\x03') {
                s.push_back(c);
            } else {
                break;
            }
        }
    }

    return s;
}

Pretty much the same idea, but reversed: figure out how many chars can fit into the block size and shift-left them to produce a string, stop when the padding character is found or the blocks end

After that comes the main encryption routine:

// acording to this stackexchange https://crypto.stackexchange.com/a/12997 comment
// xxtea security can be increase by increasing the number of mixes,
// so i've put this as a definibable constant
#ifndef XXTEA_NUMBER_OF_MIXES
#define XXTEA_NUMBER_OF_MIXES 6
#endif

#define XXTEA_MX (((z>>5U^y<<2U) + (y>>3U^z<<4U)) ^ ((sum^y) + (k[(p&3U)^e] ^ z)))

using bytes = std::vector<std::uint32_t>; // probably not the best name, but at the time i couldn't think of another


/**
 * encodes an array of unsigned 32-bit integers using 128-bit key.
 * @param v vector of uint32
 * @param k 128-bit key, if smaller the vector will be padded
 */
inline void encode(bytes &v, const bytes &k) {
    if (v.empty()) {
        return;
    }

    auto n = v.size();

    unsigned long z{v[n - 1]};
    unsigned long y{v[0]};
    unsigned long sum = 0;
    long rounds = XXTEA_NUMBER_OF_MIXES + 52 / n;
    std::size_t p;

    while (rounds-- > 0) {
        sum += internal::delta; // constant defined as constexpr unsigned long delta{0x9E3779B9};
        unsigned long e = (sum >> 2U) & 3U;
        for (p = 0; p < n - 1; ++p) {
            y = v[p + 1];
            v[p] += XXTEA_MX;
            z = v[p];

        }
        y = v[0];
        v[n - 1] += XXTEA_MX;
        z = v[n - 1];

    }

}


In my first try i tried to replace the XXTEA_MX macro with a constexpr function, but that didn't work because of the vector access(k[(p&3U)^e]) in it.

I also think that i can replace the while loop with some sort of for loop (to improve readability)

You will notice that this code is really based on the implementation on the Wikipedia page. There are a few things that i would like to change about it, for example all those definitions before the while, maybe i could put it more closely to the actual variable use? The worst offender there is the p variable.

The decryption routine:

/**
 * Decrypts text using Corrected Block TEA (xxtea) algorithm
 * @param encrypted_string @see encrypt
 * @param password password used to encrypt the string
 * @return utf8 encoded string
 */
inline std::string decrypt(bytes &encrypted_string, const std::string &password) {

    auto key = internal::to_blocks<std::uint32_t>(password);

    decode(encrypted_string, key);

    return internal::to_string<std::uint32_t>(encrypted_string);

}

Take the encrypted vector, transform the key into blocks, decrypt the blocks, transform said blocks into string again.

And the main decryption function:

/**
 * decodes an array of unsigned 32-bit integers using 128-bit key.
 * @param v array to be decoded
 * @param k 128-bit key
 */
inline void decode(bytes &v, const bytes &k) {
    if (v.empty()) {
        return;
    }

    auto n = v.size();

    unsigned long z{v[n - 1]};
    unsigned long y{v[0]};
    long rounds = XXTEA_NUMBER_OF_MIXES + 52 / n;
    unsigned long sum = rounds * internal::delta;
    std::size_t p;

    for (; sum != 0; sum -= internal::delta) {
        unsigned long e = (sum >> 2U) & 3U;
        for (p = n - 1; p > 0; --p) {
            z = v[p - 1];
            v[p] -= XXTEA_MX;
            y = v[p];

        }
        z = v[n - 1];
        v[0] -= XXTEA_MX;
        y = v[0];
    }

}```
Again, what bothers me the most is the long list of declarations.

I could put the `sum` variable into the for loop constructor but i think would become way to long.
Initially i used `auto` for all the `unsigned long`s but changed it out of fear that the compiler deduced some smaller int and my code would break in some weird edge case. 

Last part:
The PHP extension. Not much to discuss is just a simple wrapper that uses the [PHP-CPP][4] library to generate the PHP bindings. To compile it it's just a matter of using the standard CMake commands `cmake; make;` and then copy the generated .so to the appropriate location and enable it on php.ini

But there's something that I'm unsure about:

This is the PHP wrapper function:
```C++
Php::Value xxtea_encrypt(Php::Parameters &params) {

    std::string plaintext = params[0];
    std::string key = params[1];

    if (plaintext.empty()) {
        return std::string{""};
    }

    if (key.empty()) {
        throw Php::Exception("key parameter cannot be empty");
    }

    auto encrypted = xxtea::encrypt(plaintext, key);

    std::stringstream result;

    std::copy(encrypted.begin(), encrypted.end(), std::ostream_iterator<std::uint32_t>(result, " "));

    return result.str();

}

I wanted to return an encrypted string to PHP, not a vector so in the last two lines i concatenated the encrypted blocks separated by a space. Usually I've seem people encode it with base64 or something like that, but i think it's overkill for something simple. The main advantage of base64 is that it's 8-bit clean but so it's concatenating all numbers. Still i'm a little bit unsure about it

\$\endgroup\$
5
  • \$\begingroup\$ Funny how in the process of writing this question i ended up noticing a bug (that was fixed prior to post) and made some small improvements (also prior to posting) \$\endgroup\$
    – scripts
    Commented Oct 29, 2019 at 21:40
  • \$\begingroup\$ That is quite a bundle to read. Putting your hopes upfront (or even at the end) would make them easier to spot. Can you tell how performance has been identified as an issue? \$\endgroup\$
    – greybeard
    Commented Oct 29, 2019 at 23:22
  • \$\begingroup\$ It looks bad for SIMD, the main computation is not data-parallel. to_blocks could be done with SIMD, but that's because it's a roundabout way to do a memcpy. \$\endgroup\$
    – user555045
    Commented Oct 29, 2019 at 23:46
  • \$\begingroup\$ @harold what do mean it's a roundabout way to do a memcpy? I could just cast the entirety char vector of the string to a vector of uint32 but that's different of what I'm doing \$\endgroup\$
    – scripts
    Commented Oct 30, 2019 at 3:20
  • \$\begingroup\$ @greybeard I haven't profiled it enough, I was just asking in case I was missing something obvious. Trying to get a second pair of eyes into this \$\endgroup\$
    – scripts
    Commented Oct 30, 2019 at 3:21

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.