Projects Publications Resume Contact About Youtube

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.

16bit: 65KB (524288bit) max key size
32bit: 4GB max key size
64bit: #TB max key size

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

output[0-3] = initial random key offset; nextoffset = key[initial offset]
output[4] = input[0] ^ key[offset]; nextoffset = key[offset+1] ^ output[4]
output[5] = input[1] ^ key[offset]; nextoffset = key[offset+1] ^ output[5]
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:

Assume a very small key size of 64 Bytes (512bits) for this example.
Key segment size is 1byte (8bits), but segment can start at any byte in key.
Number of key segments possible: 64.
All possible keys from different segment ordering: 64! ~= 1.27x10^89

Now imagine a key that is 100B (800bits).
Key segment size is still 1byte (8bits), but segment can start at any byte in key.
Now try to determine the correct key based on the order of the 100 segments
All possible keys from different segment ordering: 100! ~= 9.33x10^157

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 byte	500MB	10KB	34B
0	15619017	330	1
1	15626886	296	1
2	15620103	392	1
3	15622848	326	2
4	15626228	335	0
5	15622784	316	2
6	15627381	330	0
7	15624684	336	1
8	15623106	319	1
9	15621956	376	3
10	15619468	293	1
11	15628047	308	0
12	15627428	330	1
13	15629488	324	1
14	15625630	335	2
15	15621248	311	4
16	15625167	354	2
17	15621983	291	0
18	15628687	334	1
19	15619498	348	0
20	15626819	289	2
21	15624810	326	1
22	15622800	356	1
23	15627213	343	1
24	15634426	364	0
25	15627091	368	2
26	15626464	337	0
27	15629513	285	1
28	15629101	351	0
29	15619337	326	0
30	15626604	280	2
31	15624185	317	0