Phelix

Phelix is a high-speed stream cipher using a one-time message authenticity code . The code was presented at the eSTREAM contest in 2004. The authors are Bruce Schneier , Doug Whitting , Stefan Lux and Frederick Muller . The algorithm contains addition operations modulo 2 ³² , addition modulo 2 and cyclic shift; Phelix uses a 256-bit key and a 128-bit timestamp . Some cryptographers have expressed concerns about the possibility of obtaining a secret key if the cipher is used incorrectly.

The forerunner to Phelix was the Helix cipher, built on the simplest operations, but it turned out to be hacked. The advanced Helix was named Phelix, but it was rejected at the eCrypt contest. The reason for the refusal was controversial - the attacks were based on the selection of a timestamp, which was the weak point of other ciphers, but the developers said that their cipher is resistant to this kind of attack. It turned out that the cipher is hacked by differential linear cryptanalysis, although it does not threaten the strength of the cipher in other conditions. As a result, Phelix was not admitted to the third round of the competition, for some presumption and carelessness of the authors. In addition to all this, a number of theoretical works appeared, in which it was argued that mixing add-xor-shift operations does not provide the necessary non-linearity, but in practice there were no hacks. Now the Phelix design is proposed by the authors for use in Skein and Threefish .

Phelix Review

The complexity of the algorithm is 128 bits, which means that to crack the cipher, it is necessary to calculate at least $2^{128}$ ${\ displaystyle 2 ^ {128}}$ $2^{128}$ block functions forming a key output sequence. Phelix uses a key of arbitrary length (from 128 to 256 bits), complemented by up to 256 bits, and a 128-bit timestamp. The key is considered secret, the default timestamp is considered to be known to everyone. The cipher is optimized for 32-bit platforms, since all operations occur on 32-bit words. We can say that Phelix is a “multi-round simple cipher”, since rather simple modulo additions are used in the process of creating the ciphertext $2^{32}$ ${\ displaystyle 2 ^ {32}}$ $2^{32}$ , exclusive "OR" and permutation of bits.

The initial state is 9 words $Z_{i}$ ${\ displaystyle Z_ {i}}$ $Z_{i}$ , 32 bits each. Words are divided into two groups: 5 “active”, which participate in the operations of the function block, and old (“old”), which participate only in the formation of the key output stream, and are stored in the block function buffer. The encryption round is shown in Figure 1. In total, the block includes 20 rounds (Figure 2).

Due to the great similarity of the block with five spirals, the cipher got its name (penta-helix English. Five spirals). The following events occur in each block: one word of the output stream (gamma) is generated, two words KeyMaterial are added $X_{i}$ ${\ displaystyle X_ {i}}$ and one plaintext word $P_{i}$ ${\ displaystyle P_ {i}}$ . The output state of the current block is used as input for the subsequent one.

Accordingly, the calculations shown in Figure 2 are sufficient to process 4 bytes of the message. As in other stream ciphers, the ciphertext in Phelix is the result of summing modulo 2 of plaintext and keystream. At the start of encryption, the initial state is determined by the key and timestamp. KeyWords $X_{ij}$ ${\ displaystyle X_ {ij}}$ depend on the value and length of the key, timestamp and block number Attacks based on guessing the internal state are complicated by the addition of keymaterial at the keystream extraction stage. At the end of the message, additional processing is performed, during which a 128-bit tag is generated that is responsible for authenticating the message.

Definition

The encryption function takes an input U key of variable length (up to 256 bits), a 128-bit time stamp and plaintext. The decryption function is a key, a timestamp and a tag, respectively, and gives either plaintext or an error if authentication fails. Let be $L(x)$ ${\ displaystyle L (x)}$ - byte sequence length $x$ ${\ displaystyle x}$ . Then $L(U)$ ${\ displaystyle L (U)}$ <32. The working key K, consisting of eight 32-bit words, is generated by the keymixing function. The timestamp is 16 bytes in size. If its length is less, then the label must be supplemented with zeros to the desired length. Ciphertext and plaintext are the same length with restriction $2^{64}$ ${\ displaystyle 2 ^ {64}}$ .The last plaintext word is padded by default with zeros up to 32 bits if the word length is not a multiple of 32 bits. The encryption function can accept an empty message, then only the message authenticity code (MAC) will be its output.

Block Function

Phelix consists of a sequence of blocks, each of which is assigned its own unique number, according to the sequence. At the input of each block there are five “active” words. Five words are also output. $Z_{0}^{i}$ ${\ displaystyle Z_ {0} ^ {i}}$ , $Z_{1}^{i}$ ${\ displaystyle Z_ {1} ^ {i}}$ , $Z_{2}^{i}$ ${\ displaystyle Z_ {2} ^ {i}}$ , $Z_{3}^{i}$ ${\ displaystyle Z_ {3} ^ {i}}$ , $Z_{4}^{i}$ ${\ displaystyle Z_ {4} ^ {i}}$ which will represent the input of the next block $Z_{0}^{i+1}$ ${\ displaystyle Z_ {0} ^ {i + 1}}$ , $Z_{1}^{i+1}$ ${\ displaystyle Z_ {1} ^ {i + 1}}$ , $Z_{2}^{i+1}$ ${\ displaystyle Z_ {2} ^ {i + 1}}$ , $Z_{3}^{i+1}$ ${\ displaystyle Z_ {3} ^ {i + 1}}$ , $Z_{4}^{i+1}$ ${\ displaystyle Z_ {4} ^ {i + 1}}$ . AT $i$ ${\ displaystyle i}$ th block also uses two keywords as input $X_{i,0}$ ${\ displaystyle X_ {i, 0}}$ and $X_{i,1}$ ${\ displaystyle X_ {i, 1}}$ one plaintext word $P_{i}$ ${\ displaystyle P_ {i}}$ and the word of the previous internal state $Z_{4}^{i-4}$ ${\ displaystyle Z_ {4} ^ {i-4}}$ .

Figure 2 gives a complete illustration of the block function. All values are 32-bit words; By tradition, exclusive OR has the designation $\oplus$ ${\ displaystyle \ oplus}$ , permutation - <<<, modulo addition - $+$ ${\ displaystyle +}$ . The block function can be represented as a sequence of two "semi-block" H, defined as follows.

Thus, the following equations are true for words participating in block operations. $(Y_{0}^{i},Y_{1}^{i},Y_{2}^{i},Y_{3}^{i},Y_{4}^{i}):=H(Z_{0}^{i},Z_{1}^{i},Z_{2}^{i},Z_{3}^{i},Z_{4}^{i},0,X_{i,0});(Z_{0}^{i+1},Z_{1}^{i+1},Z_{2}^{i+1},Z_{3}^{i+1},Z_{4}^{i+1}):=H(Y_{0}^{i},Y_{1}^{i},Y_{2}^{i},Y_{3}^{i},Y_{4}^{i},P_{i},X_{i,1})$ ${\ displaystyle (Y_ {0} ^ {i}, Y_ {1} ^ {i}, Y_ {2} ^ {i}, Y_ {3} ^ {i}, Y_ {4} ^ {i}): = H (Z_ {0} ^ {i}, Z_ {1} ^ {i}, Z_ {2} ^ {i}, Z_ {3} ^ {i}, Z_ {4} ^ {i}, 0, X_ {i, 0}); (Z_ {0} ^ {i + 1}, Z_ {1} ^ {i + 1}, Z_ {2} ^ {i + 1}, Z_ {3} ^ {i + 1}, Z_ {4} ^ {i + 1}): = H (Y_ {0} ^ {i}, Y_ {1} ^ {i}, Y_ {2} ^ {i}, Y_ {3} ^ {i}, Y_ {4} ^ {i}, P_ {i}, X_ {i, 1})}$ Each block produces one key stream word $S_{i}=Y_{4}^{i}+Z_{4}^{i-4}$ ${\ displaystyle S_ {i} = Y_ {4} ^ {i} + Z_ {4} ^ {i-4}}$ . Ciphertext, as usual, is defined as follows: $C_{i}=P_{i}+S_{i}$ ${\ displaystyle C_ {i} = P_ {i} + S_ {i}}$ .

Keywords for each block

Extended keywords are determined by the working key K, timestamp N, input key length U and block number. First, the timestamp expands to eight words by the rule: $N_{k}:=(kmod4)-N_{k-4}(mod2^{32})$ ${\ displaystyle N_ {k}: = (kmod4) -N_ {k-4} (mod2 ^ {32})}$ . Next, the keywords for block i are calculated as follows:

where all operations are performed modulo $2^{32}$ ${\ displaystyle 2 ^ {32}}$

Initialization

Encryption starts with setting the internal state:

Then 8 blocks are executed, as a result of which the words of the key output stream (gamma) are formed, which are ultimately discarded and do not participate in encryption, and only after that the work cycle begins.

Encryption

After initialization, the plaintext encryption process begins. Let K be the number of byte words of plaintext, then the number of blocks will also be K. Each block produces one word of the output key stream, which is used to encrypt one plaintext word.

Depending on the $L(P)mod4$ ${\ displaystyle L (P) mod4}$ , in the last word of the output key stream, 1 to 4 bytes are used.

Authentication Code

After the last byte of the plaintext has been encrypted, it is time for MAC generation. XOR operation for $Z_{0}^{k}$ ${\ displaystyle Z_ {0} ^ {k}}$ and 0x912d94f1. Next, the updated internal state is processed sequentially by eight blocks. The role of plaintext here are $L(P)mod4$ ${\ displaystyle L (P) mod4}$ , the generated output key stream is not used in any way. After postprocessing the internal state, four consecutive blocks are taken to generate the MAC tag, using the same words as plaintext $L(P)mod4$ ${\ displaystyle L (P) mod4}$ .

Fixed-length key generation function (keymixing)

The fixed-length key generation function maps a key of arbitrary length to a 256-bit key. First, the function R is taken, defined as follows:

Then the key U is padded with zeros to a length of 256 bits, and values are assigned to 32-bit key words $K_{32},...,K_{39}$ ${\ displaystyle K_ {32}, ..., K_ {39}}$ . The working key is entered as follows for k = 7, ..., 0: $(K_{4i},...,K_{4i+3}):=R(K_{4i+4},...,K_{4i+7})\oplus (K_{4i+8},...,K_{4i+11})$ ${\ displaystyle (K_ {4i}, ..., K_ {4i + 3}): = R (K_ {4i + 4}, ..., K_ {4i + 7}) \ oplus (K_ {4i + 8 }, ..., K_ {4i + 11})}$

Decryption

Decryption is almost identical to encryption, with the only differences:

$S_{i}$ ${\ displaystyle S_ {i}}$ generated during the first application of the H-function is used to decrypt the ciphertext, producing the plaintext word used later in the second application of the function H.
After the tag has been received, it is compared with the expected one, and if they are not equal, then the message is destroyed.

Performance

Phelix is optimized for 32-bit platforms. The authors claim that it can achieve up to eight cycles per byte on modern 86-bit processors.

The following are the performance indicators of FPGA equipment:

Xilinx chip	Fragments	FPGA Mbps	GE score	Description of implementation
XC2S100-5	1198	960.0	20404	(A) Full round 160-bit model
XC2S100-5	1077	750.0	18080	(B) Half-round 160-bit model
XC2S30-5	264	3.2	12314	(C) 32-bit data channel

Helix

Phelix is a slightly modified form of the early cipher, Helix, published in 2003 by Nils Ferguson , Doug Whiting , Bruce Schneier , John Kelsey , Stefan Lax and Tadayoshi Kono ; Phelix adds 128 bits for internal state.

In 2004, Muller published two attacks on Helix. The first has a complexity of 2 ⁸⁸ and requires 2 ¹² adaptively selected plaintext words, but requires random numbers for reuse. Souradiuti Paul and Bart Prenel later showed that the number of adaptively matched plaintext words of Mueller’s attack can be reduced by 3 times in the worst case, using their optimal algorithms to solve differential equations of addition. In a subsequent development, Souradiuti Paul and Bart Prenel showed that the attack above can be implemented with selected plaintext (CP) rather than adaptively matched (ACP) with data complexity of 2 ^35.64 CP's. Muller's second attack on Helix is a distinctive attack that requires ^2,114 words of selected plaintext.

The development of Phelix is largely motivated by Mueller's differential attack.

Security

The authors report that Phelix should not be used until it has received additional cryptanalysis.

Hongjun Wu and Bart Prenel, the authors of the differential attack, express concern that each word of the plaintext affects the key stream, bypassing sufficient confusion and diffusion layers. They claim that this is an inherent flaw in the structure of Helix and Phelix. The authors conclude that Phelix is unsafe.

Hardware Implementation

Phelix can be implemented in many different ways. The figure below shows one of the possible implementations of the Special Purpose Integrated Circuit ( ASIC ).

n_expand: Converts a timestamp of arbitrary length to a lengthstamp of 192 bits.
key_mix: Converts a variable-length key to a 256-bit key.
sub_key_gen: Generates keywords $X_{i,0},X_{i,1}$ ${\ displaystyle X_ {i, 0}, X_ {i, 1}}$ for each block.
ini_dp: Initialization.
H_func: Implementation of the logic of the H-function.
FIFO: A memory that implements the principle of first in first out FIFO .

To increase the speed of the algorithm, you can change the H-function by adding new adders and excluding ORs that could work in parallel, but this increase in the number of elements in the circuit would also entail a noticeable increase in the circuit itself, since the adder is the largest circuit element.

Notes

Literature

D. Whiting, B. Schneier, S. Lucks, and F. Muller, Phelix: Fast Encryption and Authentication in a Single Cryptographic Primitive (includes source code)
T. Good, W. Chelton, M. Benaissa: Review of stream cipher candidates from a low resource hardware perspective (PDF)
Yaser Esmaeili Salehani, Hadi Ahmadi: A Chosen-key Distinguishing Attack on Phelix, submitted to eSTREAM [withdrawn 2006-10-14]
Niels Ferguson, Doug Whiting, Bruce Schneier, John Kelsey, Stefan Lucks and Tadayoshi Kohno, Helix: Fast Encryption and Authentication in a Single Cryptographic Primitive, Fast Software Encryption - FSE 2003, pp330-346 (PDF) .
Frédéric Muller, Differential Attacks against the Helix Stream Cipher, FSE 2004, pp94-108.
Souradyuti Paul and Bart Preneel , Solving Systems of Differential Equations of Addition, ACISP 2005. Full version ( PDF )
Souradyuti Paul and Bart Preneel , Near Optimal Algorithms for Solving Differential Equations of Addition With Batch Queries, Indocrypt 2005. Full version ( PDF )