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
|