The cipher I wrote at VIIT, and the bug I found three years later

In December 2022, for a course project at VIIT, I wrote a small stream cipher in C++. I called it the Bit Scrambling Cipher. It took a key, turned both the key and the message into bits, and rearranged the message using the key. It compiled, it printed scrambled text, and I moved on.

This year I opened it again for this blog, built it with a memory checker, and it failed on the first run.

How it works

The idea is simple enough to explain in one breath. Read the message and the key one bit at a time, side by side:

• where the key bit is 1, copy the message bit to the next free place from the front
• where the key bit is 0, flip the message bit and write it to the next free place from the back

When the key runs out, start it again. Decryption walks the same key and puts every bit back where it came from.

With the key 1234 and the message viit:

KEY  00110001 00110010 00110011 00110100
MSG  01110110 01101001 01101001 01110100
ENC  11010010 01111111 01100101 00100101

The one line

This is the encryption loop, as I wrote it:

r = cipher_in_bit_vector.begin();
s = cipher_in_bit_vector.begin(); s--;   // "the back"

while (p != msg_in_bit_vector.end()) {
    if (*q == 1) { *r = *p;  r++; }
    else         { *s = !(*p); s--; }
    ...
}

s is meant to be the pointer that fills the output from the back. But it starts at begin() and steps back once, so it points one place before the first bit, and every 0 bit in the key moves it further back. Every flipped bit is written outside the output, into memory the program does not own.

In C++ that is undefined behaviour. The program is allowed to do anything, including look like it works. Today, on my laptop, it does not even decrypt its own message:

PT : 01110110 01101001 01101001 01110100   (viit)
DEC: 11111110 11101101 11101101 11111111   (garbage)

Built with AddressSanitizer, it stops on the first write:

ERROR: AddressSanitizer: heap-buffer-overflow
  in StreamCipherAlgorithm::encrypt  stream_cipher_algorithm.h:70

The fix is one word

- s = cipher_in_bit_vector.begin(); s--;
+ s = cipher_in_bit_vector.end();   s--;

The same line sits in decrypt, reading from the back, and gets the same fix. The same test decrypts viit back to viit, and AddressSanitizer stays quiet.

Why it still is not secure

Fixed, it works. It still should not protect anything real.

• The key only decides positions and flips. For a given key and message length, the scramble is always the same. Anyone with one message and its scrambled version can read the pattern off and undo every other message of that length.
• Nothing changes between messages. Real stream ciphers mix in a fresh number for every message so the same text never scrambles the same way twice. This one has none.
• Each output bit depends on one input bit. Change one letter and one bit moves. Good ciphers spread every change across the whole output.

For real data, use a vetted library: AES-GCM or ChaCha20-Poly1305, through something like libsodium. Writing a cipher is a good way to learn. Using your own is not.

What I would tell myself in 2022

• “It printed something” is not a test. Encrypt, decrypt, compare. One assert would have caught this.
• Turn the checkers on. -fsanitize=address,undefined costs nothing and would have pointed at line 70 on day one.
• Undefined behaviour can look like working code, until the compiler, the machine or the day changes.

The fix is on GitHub now: commit bd65c47, the same word changed in two places.