kcrypt3

kcrypt3 - an experimental cryptosystem based on the NP-hard polynomial reconstruction problem. Released to the public domain by Kamila Szewczyk - see COPYING.

Project homepage: https://github.com/iczelia/kcrypt3

Building

# If using a git clone (not needed for source packages), first...
$ ./bootstrap

# All...
$ ./configure
$ make
$ sudo make install

Disclaimer

You know what they say about rolling your own crypto. I find the idea of novel cryptographic systems interesting and I enjoy tinkering with it, but there is no guarantee that this program is even remotely secure. In fact it is likely that it is not, due to the fact that it has not been independently reviewed for problems as mundane as unintended code bugs, let alone issues with the code idea or specification.

Even if this program and the underlying idea was secure, it is extremely slow. Encoding and decoding are performed, on my machine, at the rate of about 500KiB/s.

Algorithm description

Block cipher

KCrypt3 principially operates in GF(256) generated by the polynomial 0x1D. The block cipher is a function that combines the IV, key and the plaintext to produce the ciphertext. The plaintext and ciphertext are 64 bytes in length. The key is a tuple of two GF(256) element vectors: the combining state (32 bytes) and the permuting state (64 bytes). In total, the key is 96 bytes long. The encryption algorithm first diffuses the IV into the key using regular addition (non-linear operation in GF(256)). Then, three keys are generated using a key scheduler (described later). They are used as successive inputs in a three-layer Feistel network with 32-byte left and right blocks. As a result of this operation, the plain text block is encrypted and the key for the next block is generated.

Feistel network topology

Only three layers are used. The kernel is a highly non-linear function that performs the following operation:

• The vectors x and y, 64 elements each, are arranged as follows:

x         0         1         2  ...          31        32        33
y  blk[0]+0  blk[1]+1  blk[2]+2  ...  blk[31]+31  key[0]+0  key[1]+1 ...

• The vector x is permuted using the Fisher-Yates algorithm with the permuting state dictating the ordering.
• The encoded block is given by the values of the polynomial for the arguments α^255, α^254, and so on.

Key scheduler

The key scheduler operates very similarly to the block cipher. The following operation is performed:

• The vectors x and y, 32 elements each, are arranged as follows:

x         0         1         2  ...          31
y  key[0]+0  key[1]+1  key[2]+2  ...  key[31]+31

• The vector x is permuted using the Fisher-Yates algorithm with the permuting state dictating the ordering.
• The permuted key is given by the values of the polynomial for the arguments α^64+i, the next key is given by α^128+i, while the new permuting state is given by α^192+i.

Block cipher modes of operation

CTR and OFB modes are supported. A 32-bit IV is always randomly generated.

Use as a random number generator

Cryptographically secure random number generators are trivially constructed from symmetric block ciphers by first sampling a cryprographically secure randomness source for the (short) key and inserting zero bytes into the block cipher.

The use of block ciphers in the CTR mode (like AES-CTR) generally does not yield sufficient diffusion of the zero bytes when small sample sizes are used. This is why the DieHarder random number generator testing suite prefers to use AES-OFB. The same principle applies to KCrypt3 and the use of KCrypt3-OFB is recommended.

Use as a hash function

Follows from a standard Merkle-Damgard construction. It has however certain requirements from the block cipher that may not be satisfied by KCrypt3. Such construction has not yet been implemented in the mainline.

Security

The author believes that KCrypt3 is secure for data at rest. The author further believes that the main sources of potential insecurity in the cipher would stem from the application of differential cryptoanalysis and attempts of simultaineously recovering both parts of the encryption key.

Derivation

The algorithm was derived by the author while studying RS-codes. It is clear that correcting RS-codes up to the Singleton bound is an easy problem. However, in the original paper due to Reed and Solomon it is claimed that the RS-codes can be corrected up to the n-k bound (via naive enumeration). Such naive enumeration is prohibitively costly, however it is theoretically feasible and probabilistic algorithms like list decoding can already be used to correct RS-codes to capacities beyond the Singleton bound.

Seeing this, the author realised that a cryptographic system can be built on top of the RS-codes. The input message would be encoded with the non-systematic RS-code (to prevent plaintext leakage) and then corrupted with a key-derived error vector. Without the key, the message would be practically unrecoverable as doing so would be equivalent to solving the practically difficult and NP-hard problem of polynomial reconstruction.

The McEliece cryptosystem, which the author was not aware of at the time of initial work on KCrypt3, works on a similar premise. It is an assymetric system that uses Goppa codes and further relies on the indistinguishability of the Goppa code generator matrix from a general linear code generator matrix. While believed secure, recent work has shown that this problem may be tractable. Similarly, McEliece-derived systems have been proven vulnerable to attacks that exploit the generator matrix structures of other linear codes, like BCH-codes and RS-codes. The author however believes that this is not an issue for KCrypt3, as the assumption on indistinguishability is not made by this cipher.

Performance

The block cipher is quadratic at its core and its theoretical performance can not be improved, unless a sub-quadratic algorithm for polynomial interpolation is used.