Gregory Hildstrom Projects Publications Resume Links Contact About Google+ Facebook Youtube Donate




Randomized Random-Cipher Encryption Version 1

Overview

RRCE encrypts 1 byte at a time by xor with 1 byte key segment from the secret key file. The initial random key segment offset is determined from input data, a nonce, and key file data. The order of key segments used during xor encryption is determined by the initial offset, key file data, and encrypted input data. The key file should be filled with high-quality random data, like recorded radio static or something far more sophisticated.

The offset type can be 16, 32, or 64 bit and is specified in rrce.h.

rrce.zip is the source code version 200711062130.
rrce.exe.zip is the Windows (XP 32-bit) exe version 200711062130.

Encrypted 3-Byte File Byte/Algorithm 32bit Example

  1. output[0-3] = initial random key offset; nextoffset = key[initial offset]
  2. output[4] = input[0] ^ key[offset]; nextoffset = key[offset+1] ^ output[4]
  3. output[5] = input[1] ^ key[offset]; nextoffset = key[offset+1] ^ output[5]
  4. output[6] = input[2] ^ key[offset]

The output filesize = inputfilesize+offset type size. So this 3-byte file would be 5 bytes if the offset type is 16bit and 7 bytes if the offset type is 32bit. The key offsets can be up to 64bits, which allows for a huge key file, but it revolves for smaller key files. This makes it very difficult to determine the actual key size from the ciphertext. The code can use the % (modulus) operator to compute remainders in revolving indexes, which is slow and commented out, but it allows for any key size. The code currently uses bitwise operators to compute remainders in revolving indexes, which is very fast, but assumes that key size is a power of 2. The entire key is also not guaranteed to be used on any one file because the key segments are chosen by combining key data and ciphertext data, which should be very random in nature.

The initial offset, which is a pointer to a pointer, is just the least significant bits of the current system time in this simple file encryption program. In the case that the first byte of the input file is guessed, xoring the 1 byte known plaintext with 1 byte ciphertext will yield 1 byte of the key, but that byte's location is unknown because the initial offset is a pointer to a pointer. The actual key data used to encrypt the first byte is key[key[initial offset]]. Any change in initial offset, byte number, or input data could result in a different key segment order being used for encryption.

Known Plaintext Attack

A known plaintext attack already constitutes a security breach, but it may reduce the number of test keys over a brute force attack. The known plaintext corresponds to some known ciphertext.

In the case of a known plaintext attack, segments (bytes) of the key, and not the actual key, can be easily determined by xoring the ciphertext and known plaintext. However, the order and extent of key segments is unknown, so the original key cannot be easily reconstructed.

In the case that a set of key segments is determined from a known plaintext attack and another encrypted file exists with the same initial key offset, additional data are kept safe by the computation of offsets from unknown key data xored with ciphertext data. This ensures that neither the same key segments nor the same order are used on different files starting with the same offset.

Known plaintext attack helps IFF (if and only if) the entire key was actually used during encryption, key size is known, and all segments were compromised; otherwise permutations increase. Here are two brief examples:



Now imagine a 1MB or 1GB key that could easily fit onto many different types of flash memory cards.

Unknowns

There may very well be a shortcut method to breaking this encryption, but I have not found it yet. It is quite possible that some math savant or someone with a different perspective will end up finding a hole in this, so rigorous research and testing are needed.

Related Algorithms

I discovered some interesting information after writing the initial versions of RRCE and this web page. Apparently the algorithm I came up with is a type of stream cipher (or 8-bit block cipher depending on your perspective). It uses some techniques similar to other stream cipher algorithms like RC4, which is used in SSL, WEP, and WPA. The similarities lie in the use of input data and key data to mangle the key during use. This attempts to approximate the behavior of one-time pad encryption schemes and maximize resistance to stream cipher attacks. RC4 uses input and key data in an 8-bit lookup table, which is very fast, but not random enough for many applications. RRCE computes key offsets using 16, 32, or 64 bits of key data with 8 bits of encrypted input data, which should use more total data in the encryption of each byte than RC4. RRCE is also fast (90MB/s on a 3.0GHz Xeon) and supports much larger key sizes than RC4. The example RRCE program loads the entire key into memory, so key size is limited by available memory. RRCE should be more random than RC4, but an in-depth analysis by experts is necessary. RRCE's initial random key offset is analogous to the initialization vector (IV) on Wikipedia's Comparison of Stream Ciphers table, but unlike RC4's IV, the use of input data and key data to determine key offsets after the first encrypted byte should thwart the key reuse attack that crippled WEP.

Key Segment Distribution

I generated three histograms to show how often each byte of the key was directly used to encrypt the input data. They key was 32 bytes generated from /dev/random. The first input file was a 500MB file full of /dev/urandom data, the second was the 10KB rrce.h file, and the third was a tiny 34B ASCII english message. Even though the small message did not directly use the entire key, the entire key was used for computing key offsets and the resulting key order; the offset type was 32 bit, which uses 4 consecutive bytes after the current key byte to compute the next offset. If the algorithm just used key byte 8 xor with the input byte, the next offset is computed using key bytes 9-12 and the current encrypted byte.
key byte500MB10KB34B
0156190173301
1156268862961
2156201033921
3156228483262
4156262283350
5156227843162
6156273813300
7156246843361
8156231063191
9156219563763
10156194682931
11156280473080
12156274283301
13156294883241
14156256303352
15156212483114
16156251673542
17156219832910
18156286873341
19156194983480
20156268192892
21156248103261
22156228003561
23156272133431
24156344263640
25156270913682
26156264643370
27156295132851
28156291013510
29156193373260
30156266042802
31156241853170