13
\$\begingroup\$

I am trying to build a fast cryptography algorithm. The algorithm works fine, but I am worried if there are any potential flaws that might make the algorithm vulnerable to any kind of attack. Here is my code.

Encryptor.cpp

#include <iostream>

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

using namespace std;

class Encryptor
{
private:
    unsigned char *key; //256 byte
    unsigned char key16[16]; //16 byte

public:
    Encryptor(unsigned char *k)
    {
        key = k;

        for (int i = 0; i < 256; i += 16)
        {
            for (int j = 0; j < 16; j++)
            {
                if (i < 16)
                {
                    key16[j] = key[j];
                }
                else
                {
                    key16[j] = key16[j] ^ key[i + j];
                }
            }
        }
        srand(time(0));
    }
    string encrypt(string txt)
    {
        int totalRounds = (txt.size() / 256);
        if (txt.size() % 256)
            totalRounds++;
        string cipher(totalRounds * 16 + txt.size(), 0);

        for (int i = 0; i < totalRounds; i++)
        {
            unsigned char randKey[16];
            int txtIndex = i * 256;
            int cipherIndex = i * (16 + 256);
            int txtSize = (i == (totalRounds - 1)) ? txt.size() % 256 : 256;

            for (int j = 0; j < 16; j++)
            {
                randKey[j] = random(1, 254);
                cipher[cipherIndex] = key16[j] ^ randKey[j];
                cipherIndex++;
            }

            for (int j = 0; j < txtSize; j++)
            {
                cipher[cipherIndex] = key[j] ^ randKey[j % 16] ^ txt[txtIndex];
                cipherIndex++;
                txtIndex++;
            }
        }
        return cipher;
    }
    string decrypt(string cipher)
    {
        int totalRounds = (cipher.size() / (256 + 16));
        if (cipher.size() % (256 + 16))
            totalRounds++;

        string txt(cipher.size() - totalRounds * 16, 0);

        for (int i = 0; i < totalRounds; i++)
        {
            unsigned char randKey[16];
            int txtIndex = i * 256;
            int cipherIndex = i * (16 + 256);
            int txtSize = (i == (totalRounds - 1)) ? (cipher.size() % (256 + 16)) - 16 : 256;

            for (int j = 0; j < 16; j++)
            {
                randKey[j] = cipher[cipherIndex] ^ key16[j];
                cipherIndex++;
            }

            for (int j = 0; j < txtSize; j++)
            {
                txt[txtIndex] = cipher[cipherIndex] ^ key[j] ^ randKey[j % 16];
                cipherIndex++;
                txtIndex++;
            }
        }
        return txt;
    }
    int random(int lower, int upper)
    {
        return (rand() % (upper - lower + 1)) + lower;
    }
};

main.cpp

#include <iostream>
#include "Encryptor.cpp"

using namespace std;

int main()
{
    unsigned char key[256] = {239, 222, 80, 163, 48, 26, 182, 101, 123, 51, 145, 28, 106, 157, 105, 1, 51, 129, 222, 124, 80, 254, 118, 220, 208, 75, 225, 127, 180, 192, 125, 149, 22, 140, 218, 162, 89, 45, 237, 250, 71, 85, 245, 75, 59, 122, 146, 95, 68, 130, 33, 62, 124, 11, 203, 252, 72, 141, 140, 12, 241, 218, 89, 147, 58, 124, 209, 177, 71, 254, 201, 3, 166, 10, 179, 89, 194, 72, 150, 32, 97, 197, 119, 50, 185, 11, 202, 164, 175, 115, 239, 113, 146, 7, 84, 62, 49, 124, 25, 108, 111, 107, 250, 168, 75, 137, 87, 219, 115, 242, 237, 23, 79, 53, 95, 45, 180, 59, 243, 138, 37, 219, 174, 13, 188, 19, 62, 104, 176, 154, 183, 242, 177, 19, 215, 42, 197, 88, 149, 246, 40, 54, 184, 31, 187, 9, 115, 152, 128, 165, 116, 105, 179, 242, 145, 195, 250, 153, 139, 247, 96, 51, 225, 237, 86, 97, 97, 196, 146, 67, 73, 88, 30, 135, 192, 29, 64, 189, 123, 95, 152, 22, 31, 5, 71, 38, 136, 6, 68, 247, 93, 206, 200, 229, 243, 140, 11, 137, 60, 197, 22, 92, 118, 44, 3, 47, 121, 249, 88, 27, 101, 242, 222, 36, 112, 45, 188, 46, 170, 201, 244, 90, 115, 224, 88, 157, 109, 136, 228, 134, 186, 124, 154, 3, 78, 49, 225, 57, 249, 172, 103, 44, 74, 84, 158, 48, 139, 185, 207, 9, 58, 143, 211, 177, 62, 32};
    Encryptor e(key);

    for (int i = 0; i < 100; i++)
    {
        string c = e.encrypt("my secret");
        cout << "cipher: " << c << endl;
        cout << "After decryption: " << e.decrypt(c) << endl;
    }

    return 0;
}

Algorithm:

  • user provides 256 byte key where the value of any byte can't be 0 or 255
  • 16 byte internal key is generated from the user provided key

encryption:

  • plain text is processed in 256-byte blocks (same as the key length) except the last one which depends on the length of the plain text.
  • 16-byte random key is generated for every block where the value of each byte is between 1,254.
  • for each plain text block additional 16 byte is added in the beginning of cipher text block that increases the cipher text block size to 256+16 byte
  • the first 16 bytes of each cipher text block contains the XOR result of the block random key and the internal key
  • the 17th byte of the cipher text = key[first byte] xor random key[first byte] xor plain text block[first byte]
  • the 18th byte of the cipher text = key[second byte] xor random key[second byte] xor plain text block[second byte]
    ....
  • when the random key reaches its last byte, as it is shorter than the block size, it repeats from the beginning.

The decryption process is reverse of the encryption process.

\$\endgroup\$
  • 5
    \$\begingroup\$ Recommended reading: security.stackexchange.com/q/18197/218173 - TLDR: It's better to grab a well-tested open-source library and use that. Algorithms like AES-256 are not "slow". These public libraries are made from the combined efforts of legions of people, including many who are much more qualified than you or I. \$\endgroup\$ – Gloweye Oct 30 '19 at 15:08
  • 11
    \$\begingroup\$ It's not surprising that you can't find how to crack it. To quote Bruce Schneier, in 1998, Anyone, from the most clueless amateur to the best cryptographer, can create an algorithm that he himself can't break. It's not even hard. What is hard is creating an algorithm that no one else can break, even after years of analysis. IOW, being unable to crack it yourself says very little about its strength. \$\endgroup\$ – Toby Speight Oct 31 '19 at 10:50
  • 2
    \$\begingroup\$ I think that's more than you can reasonably expect a volunteer reviewer to be able to do for you, for free. \$\endgroup\$ – Toby Speight Oct 31 '19 at 12:01
  • 3
    \$\begingroup\$ In 99.9[...]9% of the cases where someone thinks "I know, I'll write my own encryption algorithm, It's [faster|safer|...] than existing ones", they're at the unconsciously incompetent stage of learning. You don't know what you need to know in order to know whether you're doing a good job. Regarding cryptography, I know I myself am consciously incompetent; I do know what I don't know, and therefore I won't attempt to roll my own. You should do more reading on the subject and abandon this current attempt. \$\endgroup\$ – CodeCaster Oct 31 '19 at 13:19
  • 3
    \$\begingroup\$ Someone might break your algorithm if they think it's fun and they have spare time. But I wouldn't rely on it. I agree that it's probably easy to break if you put in some work to actually figure out how to break it. I have broken a similar algorithm before using automated frequency analysis. I did that because I thought it was fun to show that person how broken their algorithm was, and I had spare time. I think this one will be harder than the one I previously broke, but not unbreakable at all. \$\endgroup\$ – user253751 Oct 31 '19 at 17:32
23
\$\begingroup\$

Here are a number of things you could do to improve the code.

Separate interface from implementation

The interface goes into a header file and the implementation (that is, everything that actually emits bytes including all functions and data) should be in a separate .cpp file. The reason is that you might have multiple source files including the .h file but only one instance of the corresponding .cpp file. In other words, split your existing Encryptor.cpp file into a .h file and a .cpp file.

Use C++-style includes

Instead of including stdio.h you should instead use #include <cstdio>. The difference is in namespaces as you can read about in this question.

Don't abuse using namespace std

Putting using namespace std at the top of every program is a bad habit that you'd do well to avoid. Know when to use it and when not to (as when writing include headers).

Make sure you have all required #includes

The code uses std::string but doesn't #include <string>. Also, carefully consider which #includes are part of the interface (and belong in the .h file) and which are part of the implementation per the earlier advice.

Don't use unnecessary #includes

The code has #include <stdio.h> but nothing from that include file is actually in the code. For that reason, that #include should be eliminated.

Don't use std::endl if you don't really need it

The difference betweeen std::endl and '\n' is that '\n' just emits a newline character, while std::endl actually flushes the stream. This can be time-consuming in a program with a lot of I/O and is rarely actually needed. It's best to only use std::endl when you have some good reason to flush the stream and it's not very often needed for simple programs such as this one. Avoiding the habit of using std::endl when '\n' will do will pay dividends in the future as you write more complex programs with more I/O and where performance needs to be maximized.

Use a better random number generator

You are currently using

(rand() % (upper - lower + 1)) + lower;

There are a number of problems with this approach. This will generate lower numbers more often than higher ones -- it's not a uniform distribution. Another problem is that the low order bits of the random number generator are not particularly random, so neither is the result. On my machine, there's a slight but measurable bias toward 0 with that. See this answer for details.

Study cryptography

If you're interested in this sort of thing, it would be good for you to study cryptography. One book you might like is Modern Cryptanalysis by Christopher Swenson. It's quite understandable and may help you answer your own questions. Here's a brief analysis of your scheme:

First, some nomenclature. I'm going to be referring to blocks (16-byte chunks) hereafter. Let \$m\$ be a single block message we're encrypting, and the 256-byte key is \$k[0] \cdots k[15]\$. Let's also say the random key is \$r\$ and your key16 is \$b\$. Using standard notation, \$\oplus\$ is the block-sized exclusive or operator. Your scheme does this:

$$ b = k[0] \oplus k[1] \oplus \cdots \oplus k[14] \oplus k[15] $$

The generated message has two parts which I'll call \$p\$ and \$q\$:

$$ p = b \oplus r $$ $$ q = k[0] \oplus r \oplus m $$

If we combine those into a new quantity \$m'\$, we get this:

$$ m' = p \oplus q = b \oplus r \oplus k[0] \oplus r \oplus m $$ $$ m' = p \oplus q = b \oplus k[0] \oplus m $$

So we can easily already see that the random key has no useful effect. Further, we can say that \$b' = b \oplus k[0]\$, so from the definition of \$b\$ we get:

$$ b' = k[1] \oplus k[2] \oplus \cdots \oplus k[14] \oplus k[15] $$

And so \$m' = b' \oplus m\$ and we can now see that the first block of the key also doesn't need to be derived. All that we need to get is \$b'\$ and we can decode any message encrypted with that key. If we know or can guess that the encrypted text is ASCII, for example, it's not at all hard to guess at the top few bits of each of the bytes of \$b'\$ and in essence, your scheme is no better (and no different) than choosing a randomly generated single key and exclusive-or-ing it with the message. That's a very, very weak scheme that even amateur cryptographers like me would have little difficulty breaking.

| improve this answer | |
\$\endgroup\$
13
\$\begingroup\$

Please do not roll your own encryption outside of an academic context.

If you would like a fast algorithm that can be easily implemented in C/C++ take a look at ChaCha or Salsa. Runs great on most general purpose CPUs and has been verified by the cryptographic community at large. I've seen it outpace AES accelerators in constrained devices.

| improve this answer | |
\$\endgroup\$
11
\$\begingroup\$

Regarding the cryptographic algorithm only:

Important observations

This is equivalent to an XOR cipher with a repeating 256-byte key. The key16 stuff adds no security. The randKey stuff adds no security. The following is working decryption code for one round (I'll use your terminology), if you know the key:

unsigned char key16[16] = {0};
for(int k = 0; k < 256; k++) key16[k % 16] ^= key[k];
for(int k = 0; k < 256; k++) key[k] ^= key16[k % 16];

// everything above this line adds no security,
// because we could just take the modified key HERE
// and pretend that's the real key.
// Then we wouldn't need key16.

string decrypted = encrypted.substr(16);
for(int i = 0; i < decrypted.length(); i++) {
    // This line adds no security, because the attacker
    // knows what encrypted[i % 16] is.
    decrypted[i] ^= encrypted[i % 16];

    // This is the only part where we need to know the key.
    // It's a standard XOR cipher.
    decrypted[i] ^= key[i % 256];
}
std::cout << decrypted << std::endl;

This does the same as your decryption code (try it and see), but I've rearranged it for easier analysis.

In the rest of this answer, I will ignore key16 and randKey because they are easily reversed (see code above) and concentrate on the XOR cipher.

So with that in mind, what are the problems?

It is vulnerable to statistical analysis, to get key16

The bytes in randKey are never 0 or 255. This means that after you XOR them with key16, they'll never be equal to key16 or key16^255. If the attacker sees a lot of rounds, this means the attacker can guess the bytes in key16, by narrowing each byte down to 2 possibilities.

If you did discover key16, then you can combine it with 240 key bytes to work out the other 16. So it's not much of a breakthrough.

It might be vulnerable to statistical analysis, to get the message

Because the key bytes are never 0 or 255, once you have recovered key16 (see above), you can XOR that with the ciphertext (along with the randKey^key16) and then you'll never get bytes equal to the original message, or the message XOR 255. If you had enough copies of the same message encrypted with different keys, you could figure out which bytes you aren't getting, which is the message.

To use this attack, you'd need to have a very long message (so that it contains enough rounds to figure out key16 for each key) and you'd need to see it encrypted with a lot of different keys (so that you can figure out the message).

It is vulnerable to known plaintext attacks.

If you know the plaintext (decrypted text), or part of it, you can XOR the plaintext with the ciphertext (encrypted text), and you get the key.

It is vulnerable to chosen ciphertext attacks

If I can give you some ciphertext (encrypted text) and get you to decrypt it, and show me the plaintext (decrypted text), then I can work out the key by XORing them.

In particular, if I just give you a bunch of 0 bytes, and ask you to decrypt them, the plaintext will be the key XOR key16. That's really lame.

It is vulnerable to frequency analysis

The most common letter in English is 'e' (ASCII 0x65) or possibly a space (ASCII 0x20). If you see that 0x8F as the most common first byte of a round, you can guess that the first byte of the key XOR key16 is 0xEA (which would make them 'e') or 0xAF (which would make them spaces). Same for the second byte, and the third byte, and all the other bytes. For this to work, the message has to be quite long.

It is vulnerable to XORing two messages

Once you undo the random keys, you can XOR the ciphertext for two messages (or blocks) and it will be the same as XORing the plaintext for those two messages (or blocks). This can give you lots of information about the plaintext, but it's very specific to the situation. I'm not sure if this attack has a standard name.

| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ This looks like a great first post, good job! \$\endgroup\$ – IEatBagels Oct 31 '19 at 20:47
7
\$\begingroup\$

File naming

It's a long-standing convention in C++, as in C, that files meant to be included as part of another translation unit (headers) are given names with a .h suffix. It's a good idea to follow such conventions, as it makes the code easier for everyone to understand.

Includes

Don't use the C compatibility headers in new code; use the C++ versions, which declare their identifiers in the std namespace, whence they can be used unambiguously:

#include <cstdio>
#include <cstdlib>
#include <ctime>

using directive

Don't bring the whole of std into the global namespace - especially not in a header file, which will inflict the harm onto the entire translation unit. Just use the minimum set of identifiers you need into the smallest reasonable scope, and fully qualify names where reasonable.

Use initializers

Instead of writing key = k; in the body of the constructor, it's much better practice to use an initializer for this. That makes it easier for the compiler to determine whether the class is properly initialized:

Encryptor(unsigned char *k)
    : key{k}

Mark conversion constructor as explicit

We don't want Encryptor to be considered as an implicit promotion from unsigned char*, so it should be marked explicit.

Avoid mutable non-owning pointers

We never modify the values in k[], so don't store a mutable pointer:

class Encryptor
{
    unsigned char const *key;

public:
    explicit Encryptor(unsigned char const *k)
        : key{k}
    {

Validate arguments

There's a documented constraint that k[n] is not 0 or 255, but this is never checked. The constructor should validate that constraint and throw std::invalid_argument if it's violated. However, there's no justification for that constraint - I see no reason not to accept all values from 0 to UCHAR_MAX.

Use the full keyspace

The key16 array contains only values from 1 to 254. We actually need it to be uniformly distributed across the full range 0 to UCHAR_MAX.

Initialise the random seed only once

std::srand() doesn't give very good randomness if reseeded every time we create a new Encryptor - it's best called exactly once per process (generally in main(), where we can't accidentally link in another call).

Don't pass std::string by value

We can pass inputs by reference to const:

    std::string encrypt(const std::string& txt);
    std::string decrypt(const std::string& cipher);

Don't pass mutable this unnecessarily

encrypt() and decrypt() require only read access; random() doesn't use any members at all:

    std::string encrypt(const std::string& txt) const;
    std::string decrypt(const std::string& cipher) const;
private:
    static int random(int lower, int upper);

Don't mix signed and unsigned arithmetic

Strings are measured and indexed using std::size_t, which is unsigned, so don't access them using int, which is signed and may be too small.

Scrub key data after use

Don't leave secrets in memory unnecessarily, as they could be exposed to an attacker (e.g. in core dumps).

~Encryptor()
{
    std::fill(std::begin(key16), std::end(key16), 0u);
}

Improve the encryption

The encryption algorithm is extremely weak, as some elementary cryptanalysis would reveal. Avoid any encryption that isn't based on proven mathematical difficulty.

The only positive thing I could find is that the code doesn't seem to have any obvious data dependencies in its timing or power consumption.

Ciphertexts are more than 6% larger than plaintexts, making this algorithm inefficient for storage or transmission of secret data.

| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy