Can you break my home rolled encryption?

I give you two plaintexts of the same length of my choice, you select one of them and encrypt it with a key of your choice and give me the resulting ciphertext. If I can determine with probability p>50% which of the two plaintexts you have encrypted, the cipher is considered broken at level p.

I chose the following two plaintexts relative to the C source liked to elsewhere in this thread, with

    #define DATA_SIZE (1024 * 1024 * 128)

    for(i = 0; i < DATA_SIZE; i++)
        decrypted[i] = i;

    for(i = 0; i < DATA_SIZE; i++)
        decrypted[i] = 0;

I don't need the full ciphertext, the output of the following code fragment is sufficient:

    for(i = 0; i < DATA_SIZE; i++) {
      count[encrypted[i] & 0xFF] += 1;
      count[(encrypted[i] >> 8) & 0xFF] += 1;
      count[(encrypted[i] >> 16) & 0xFF] += 1;
      count[(encrypted[i] >> 24) & 0xFF] += 1;
    }

    for(i = 0; i < 256; i+=1) {
      printf(" %8d", count[i]);
      if (count[i] > 2400000) {
	printf("*");
      } else {
  	printf(" ");
      }
      if (i%16 == 15) {
        printf("\n");
      }   
    }

    decrypted[i] = encrypted[i] ^ key[pos_a] ^ key[pos_b];
    key[pos_c] = (key[pos_c] << 31) | (key[pos_c] >> 1);
    key[pos_a] ^= key[pos_c] ^ i ^ decrypted[i];

    key[pos_a] ^= key[pos_c] ^ i ^ encrypted[i] ^ key[pos_a] ^ key[pos_b];

    key[pos_a] = key[pos_c] ^ i ^ encrypted[i] ^ key[pos_b];

As always, it's terrible easy to create an encryption algorithm that's complicated enough that you yourself can't break it. That doesn't make it safe. (It might still be a fun exercise for you.)

Have you tried breaking any ciphers, yet? Even obviously weak ones require some thought to break.

* If you delivered a complete implementation in a popular language like C, Python, or Ruby, rather than publishing pseudocode that may or may not be interpreted correctly by error-prone humans

* If there was a clear goal. "Find a weakness" is vague; "Recover the missing plaintext from this 1MB message" is specific.

        #include <stdio.h>

        int main() {
                char key[] = {0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0x08};
                int key_size = sizeof(key) / sizeof(key[0]);

                int pos_a = key[0];
                int pos_b = key[1];
                int pos_c = key[2];

                char encrypted[100], decrypted[100];

                for(int i = 0; i< 100; i++) encrypted[i] = 0;

                for(int i = 0; i < 100; i++)
                {
                        int old_a = pos_a;
                        pos_a = key[pos_b] % key_size;
                        pos_b = (pos_a + 1 + key[pos_c] % (key_size - 1)) % key_size;
                        pos_c = (pos_a + 1 + key[old_a] % (key_size - 1)) % key_size;
                        decrypted[i] = encrypted[i] ^ key[pos_a] ^ key[pos_b];
                        key[pos_c] = (key[pos_c] << 31) | (key[pos_c] >> 1);
                        key[pos_a] ^= key[pos_c] ^ i ^ decrypted[i];
                }

                for(int i = 0; i < 100; i++) printf("%02x ", decrypted[i]);

        }

I see one very big problem with the algorithm. If I know the first bytes encrypted (a known plaintext attack), I will recover the xor of two parts of the raw key. On the next word encrypted, it will be a shifted version of the raw key material. This will eventually mix, but the mixing is slow enough that the key can be recovered. Even ciphertext only attacks will be possible if you know or guess underlying statistical properties of the plaintext, like that this is english text, HTTP headers or whatever. In general, too much of the key material leak into the keystream, making the cipher breakable. In practice, the length of an HTTP header will likely leak enough of material to break it.

A better streamcipher would have a key schedule before the encryption, making a table of bits that are mangled based on the key bits so that there is less correlation between the keystream and the key instead of using the key directly. Any such correlation will make the cipher breakable.

Furthermore, there must be more mixing of bits than the given algorithm has. RC4 appear to have no more mixing, but that uses a much bigger table of 256 bytes, and not only the size of the key like this one, that makes it very likely that a byte has been mixed quite a lot the next time it is used.

With that said, I'm not convinced that your pseudocode actually works. Specifically, the following doesn't make sense to me:

pos_a = key[0];

pos_b = key[1];

pos_c = key[2];

...

pos_a = key[pos_b] % key_size;

It would be really cool if you posted functioning encrypt() and decrypt() methods to github. Something that people can actually compile/run/analyze. In fact, if you do that get in touch with me and I'll try to crack it.

I played around with your C implementation a little[1]. I put it into 8-bit mode, and generated 16 random keys and output their keystreams[2]. Here's the first 32 bytes of those keystreams, in hex:

0002010203fd050607b0090a0b250d0e0f8b111213a4151617f5191a1be6003e 3b4a00790369050607004b170b820d0e0fb7111213d0005f1796191a1b321d1e 00130102036b05060734090a0b260d0e0fca111264141516178700671b534ae8 df7c806903d10506077fcc670b583600dec617580a2b8b161712191a1b1c00a7 00260102032f1d0082a0090a0bd30d0e0f4ca8c616aa151617a400a34f1c9e1e af7cb175036705060786090a0bc90d0e0f2a111213831516173700501bfa1d1e 000236ca58110506079c00090b860d0e0f8f111251009e1617b4191a1b311d1e 00250102039700ec0729090a0b2a0d0e0f961112133a151617e3a200956764b8 002a0102031e050607ed003c0b260d0e0fcf111213c000151a18191a1bb21d1e 413c0102031505060745090a0b060d0e0fc6111213b815161784191a1b341d1e 00890102039500b807a200570ba70d0e0fa31112134c1516172d191a1ba03900 00cd01020332050607e100b10bdd0d0e0f0d111213261516170e191a1b041d1e 0076010203c30506074e03c7880069000eb8078d54134604a61a142d1a0600c3 00f101020344050607a8090a0b0e0d0e0f11111213e6151617f3191a1b291d1e 00f1007a0369aab10068090a0b53b1ac0fd1111213531516171800ee1bde1d1e 0036010203570506076c00d60b050d0e0f2f27583f03591617bc09471b141d1e

As you can see, there are some significant biases here. For example, as an attacker, once I have a ciphertext, I can guess that bytes 18 and 19 of the keystream were (hex) "1112", and have a very good chance of being right.

While the 32-bit version isn't as bad, I think there's still significant biases. I generated 24495 keys. Here's the distribution for keystream byte 1 (script at [3]):

   92    82    82   104    99    90    99   111    90   102    91    95    94    91    73   102
  109   106    97    99    88    99    90    96    88    97   101   100   108    76    87    87
   91    94   111    90    92   104    88    97    94   100    89   102    90    91    92    89
   98    96    89    94   111   111   105    90    87    89    93   104   100   110   109    93
   77   107   103    84    88    96    89    87    77    96    90    84    87   106   101    98
   99    99   114   102   104   106    95    91    95    92    94   104    95    88    93    91
   91    78   102    89   104    88    94   100   102   105    94   102   100   105    99    94
   87    89    86    93    95    77    82    83    99    94    88   106   106   101   101    91
   82    88    98   111   104    93   102    91    87    93   106    89   102    78    88   105
   91    93   105    84   101   100    94    93    94   107    88    86   114    84   112    98
   97    84   111    87    91    93    89    95    92    96    78    85    90   104    84    80
  103    95    98   114    90    89    91   110    89   100    87   107    95   109    83   103
  112   102    93    93    87    90   101    91   108   108    90   107   103    95   111   126
   88    97    74   111    97    99    95    95   102    97   122    94   106    94    97   103
   86    90   102    91    95   108    83    97    91   102    99    90   103   111    93    84
   87   107    91    96    77    98    96    85   108   110   116   100    95    89    72   100

I did not look at 64-bit.

All in all, I wouldn't use your cryptosystem :) but there's no shame in that! Crypto is hard! and youre only going to get better.

This produces a sequence which is always the same for each session, but because the keyspace is so large (2^128 with AES-128), this is acceptable because these PRNGs are actually cryptographically secure hash functions, which makes them very hard to reverse. Therefore, the only efficient way to crack your session is to either catch the key (your counter) or to brute force it by using every value of the counter and test whether this leads to a successful decryption. Not only are there 2^n possibilities, but every possibility is extremely expensive to test and then you have to accurately check whether the decrypted values are coherent (this is difficult with packets with a fixed header and nearly impossible with raw binary data).

The big disadvantage is having to store your small key until decryption.

This doesn't seem right. If "the key describes the algorithm" you need another algorithm to generate the algorithm from the key. This other algorithm is unique and will produce patterns like any other deterministic algorithm. Patterns in the generated algorithms will eventually be reflected in the data.

You can reduce all this algorithm generation back into essentially one algorithm anyway: generating "changes to the algorithm" merely obfuscates the presentation of the underlying single algorithm. In the end, there's still a fixed set of input information that goes into an encryption function and no matter how you try to obfuscate it Shannon won't budge.

http://en.wikipedia.org/wiki/Stream_cipher_attack -- in particular, the period of your key stream is very weak. Also, without an IV, you will be in trouble.

Essentially, you need to take a key, and an IV, and feed it into your magic box (algorithm) and all that should come out is an incredibly long random string that does not repeat for a very, very long time. The shorter the period the worse off you are. I can't be sure, but I think you have a predictable, short period.

Even more interesting, read up on RC4: http://en.wikipedia.org/wiki/RC4 -- there were small but detectable biases in the initial part of the key stream, which allowed an attacker to break the algorithm. The solution was to advance the key stream a bit to discard the initial, biased part.

And thus we get to the hardest part of cryptographic algorithm design and why these exercises are so hard. It is very easy for someone to build an algorithm they can't break themselves. Obviously, you did everything you knew how to do to prevent it from being broken. It might even take an experienced cryptographer a while to break it (the key stream bias in RC4 was not found for a long time). Check out some of the WEP attacks.

Another thought for you: http://www.rickwash.org/papers/stream.pdf -- just how easy it is to be wrong. Page 8: If the swap operation of RC4 is omitted, the keystream becomes cyclic with a period of 2 n+1 -- very small changes can introduce non-obvious periods, etc.

Final thought: check out how WEP got broken. Stream ciphers are hard. This is why it is often very good as an educational exercise to write your own ciphers (I have done it), but you sort of do it once and either decide to get good at it or realize it takes a LOT of knowledge and it is better to just know the attacks and not invest a lot of time in it.

Anyhow, hope you had fun with this. Read up on the various ways stream cipher design can be broken, and check out how AES can be used as a stream cipher. Not sure I had a point, precisely, just wanted to share some thoughts having seen a dozen or more of these crazy algorithms in use in live code meant to protect truly sensitive data. Some programmer always thinks he is clever and ends up creating some XOR cipher (I know that is not you as you have the right goals, in my mind, for doing this).

these include:

- plaintext injection

- ciphertext collisions

- distinguishing attack

- statistical plaintext matching

- partial known plaintext attack