Encryption is not secure

[rspencer01]

See here: https://www.reddit.com/r/crypto/comments/7rpvur/cape_can_you_break_it/dsyx1w8/

I suggest a banner at the top of the readme explaining that this algorithm is for research and educational purposes only and that it shouldn't be used in production.

[gioblu]

Ciao @rspencer01 thank you so much for dedicating some time to hack this :) I agree with you that a 150 characters plaintext encrypted with a 10 characters key is not secure, and that is stated clearly in the README.

I see you assumptions implies:

• Use an extremely weak configuration (150 characters plaintext encrypted with a tiny 10 characters key).
• have a partial knowledge of what the content of the string is (excluding to check most of the possible byte values), that is not always the case.
• Know that the user is using Cape
• Know that the user is using the encrypt function

How much harder would be without starting from those assumptions to get back the plaintext?

Thank you so much for your support.

[luke-park]

I've also looked at the code here and it has a few rather concerning flaws... The whole salt and IV thing doesn't really make any sense (neither are what they say on the box, you could have called them foo and bar). Additionally, encrypting only zero bytes leads almost directly to the keystream, which means any sort of chosen plaintext attack ("in the wild") would break the implementation pretty quickly.

The largest issue is the issue outlined by rspencer01. I say issue lightly here, it is a full break of the algorithm, really. I feel that it is misleading to potential viewers of this repository to not alert them to the fact that the code within doesn't actually provide any security. I second the idea of a banner.

[gioblu]

Ciao @rspencer01 @luke-park I am sincerely thankful to you for taking time to study the algorithm and even write some code to demonstrate its vulnerability.

I had a real life issue in the last 2 hours, so I was not able to commit changes, I will for sure add the suggested statement in the README and relate it to this issue.

This repository and its codebase are obviously in experimental state and its procedure for sure not in its definitive state, it is just an experiment.

@rspencer01 I am also eager to finally run your gist and test on longer keys. Thank you again for sharing your experience. I am sure who is following Cape's development will be as happy as me to play with your example.

@luke-park I am sorry, the 00000 string encryption flaw was already described in the reddit, but I have practically tested this afternoon using different keys and both hash and encrypt function but I am not able to get the key as you describe. Quoting myself on reddit:

-/-#%!/-') this is a cipher text generated using the hash function that does not use any IV, its plaintext is 0000000000 and the key is extremely simple. Any idea of the key value?

@luke-park what you mean with

The whole salt and IV thing doesn't really make any sense

[silkeh]

@gioblu The problem with encrypting a zero byte string is that this results in a direct correlation between known variables. The key can be calculated as follows:

srk = salt ^ reduced_key
// For encrypt/decrypt; 0 <= i < message length
key[(srk ^ i) % _key_length] = destination[i] ^ source[i] ^ iv ^ i;
// For hash; 0 <= i < message length
key[(srk ^ i) % _key_length] = destination[i] ^ source[i] ^ srk ^ i;

This means that there is a fairly straightforward way to calculate the key if the source (or any properties of the source) are known. The only unknowns are the length of the key (which is probably below 256 characters) and the reduced key (8 bits), assuming the salt (and/or IV) are known (though these two only are 8 bits in size).

Brute forcing the unknowns allows a very quick calculation of all valid keys for a message. Additional messages (even when fairly short) would narrow the list of valid keys down quite quickly.

-/-#%!/-') this is a cipher text generated using the hash function that does not use any IV, its plaintext is 0000000000 and the key is extremely simple. Any idea of the key value?

Sure, the following prints that ciphertext:

#include <iostream>
#include <string>
#include "Cape.h"

int main() {
  char key[] = "e`mnijkd????kd??"; // Undetermined characters were replaced by ?
  char src[]  = {0,0,0,0,0,0,0,0,0,0};
  char dst[255];

  Cape cape(key, std::strlen(key));
  cape.hash(src, dst, 10);

  std::cout << std::string(dst, 10) << std::endl;
}

[gioblu]

Ciao @silkeh, thank you so much for your support. I have tried out the proposed calculation starting from hash using key 1234567890, plantext 0000000000 and salt 0 :

calculated_key[(i ^ cape.salt ^ reduced_key) % 10] =
  (destination[i] ^ source[i] ^ cape.salt ^ reduced_key ^  i);

Results show effectively the key for plaintext 0000000000 and 1234567890, but thiskeynot and many others does not output the key, it seems an attack related not only to a finite set of plaintext (0000000000, 1111111111, 2222222222) but also a finite set of keys (0000000000, 1234567890, 2345678901) and salt values:

Key: 0000000000 Cipher: @ABCDEFGHI Computed key: 0000000000 Salt: 0
Key: 1234567890 Cipher: ½¼¿¾¹¸»ºµ´ Computed key: 1234567890 Salt: 0
Key: 2345678901 Cipher: vvzz~~zzvv Computed key: 2345678901 Salt: 0

Then starting from the assumption that the plaintext is known to the attacker, I have used brute force to obtain the salt and I have noticed that more than one value of salt (also not the one is in use) outputs the correct key used for that ciphertext and also that the salt only scrambles the key in any case giving good hints about it.

So absolutely, too few unkowns, weak algorithm and me not taking into consideration the known plaintext attack. 🥇 Thank you and my compliments again @silkeh and @rspencer01 .

I will work on something less vulnerable :)

[silkeh]

Good luck!

By the way, watch out for the use of the % operator on negative values. The following (from encrypt/decrypt) can read _key with a negative index because srk is a (signed) char:

destination[i] = source[i] ^ iv ^ i ^ _key[(srk ^ i) % _key_length];

Additionally, I think the quality of the C++ code could be improved:

• Make use of std types (like std::string, std::vector and std::array), this simplifies the function arguments, loops and allows easier bounds checks.
• Declare function arguments as const when they are not modified.
• Document the code for use with Doxygen
• Lint and format code (by using tools like clang-tidy and clang-format)

Following the features of a C++ standard (eg: C++11 or C++14) and matching guidelines (eg: http://cginternals.github.io/guidelines/) can help you with this.

[gioblu]

@silkeh I have fixed the sign issue, thank you. I will clean out the warnings, not sure if to be able to comply 100% to the codestyle standard. I will download the suggested tools and will make better use of std types. Thank you again for sharing your experience.

[Pharap]

Sorry to drag this up again, but I missed it at the time because I forgot to watch the repo.

@silkeh The reason C++ stdlib types aren't used is because this library is used on Arduino and Arduino programs don't have a version of the stdlib, and frankly some Arduino MCUs don't have enough RAM to support the dynamic allocation used by std::vector or std::string.

The const thing is a fair point, but really that ought to be raised as a separate issue.

@rspencer01 I'm glad you managed to make a proof of this. I had suspected it was possible but didn't raise the issue because I couldn't write a program capable of proving it. I was missing the bit about making assumptions about what the encrypted data looks like, so I was trying a lot of unnecessary permutations.

[gioblu]

Ciao @Pharap I agree, I wasn't able to break it too, @rspencer01 gave a great contribution 👍 , extremely instructive. I agree with you @Pharap about std::vector or std::string, it is not the only repository where I was forced to choose so.