phelix.tex

phelix加密算法源代码,是一个开源的加密算法

bits, something the carry bits already do. This reduced the set of candidate
rotation counts to 86.

Using the full block function, we ran statistical tests on many candidate
rotation count sets to see how these values would affect the ability of the
block function to diffuse changes and mix together separate information
within the 160-bit internal state.  Among our tests, we considered:
\begin{enumerate}
\item The number of rounds required before all output bits passed binomial
tests, given a fixed input difference in the state.

\item The number of rounds required before the output states' Hamming weight
distribution passed a $\chi^2$ test, given low- and high-Hamming weight input
states.

\item The number of rounds required before the output states' differences in
Hamming weight distribution passed a $\chi^2$ test, given low- and
high-Hamming weight differences in the input state \cite{KRRR:RC2-98}.

\item Low- and high-Hamming weight higher-order differences, and the number
of rounds required before the resulting output differences' Hamming weights
passed a $\chi^2$ test.

\end{enumerate}

The surprising result was that most rotation counts did pretty well. Our
carefully selected rotation count sets were slightly better than random
ones, but only by a small margin. Degenerate rotation counts (all rotation
counts equal, or most rotation counts zero) led to much worse test results.

At the end of our analysis, we selected more or less at random from the
remaining candidates. Based on our limited analysis, the specific choice of
rotation counts does not have a strong impact on the security of Phelix, with
only the caveat that we had to avoid some obvious degenerate cases.

\section{Cryptanalysis}

Phelix is intended to provide everything needed for an encrypted and
authenticated communications session.  A successful attack on Phelix will
have occurred when an attacker can either predict a keystream bit he hasn't
seen with a probability slightly higher than 50\%, or when he can create a
forged or altered message that is accepted by the recipient with a
probability substantially higher than $2^{-128}$. To be meaningful, given the
128-bit security bound of Phelix, any such attack must require fewer than
$2^{128}$ block function evaluations for all participants combined. Also,
any such attack must obey the security requirements placed on Phelix
operations; e.g., no reuse of nonces, MACs checked before decrypted messages
released, etc.

In this section, we consider a number of possible ways to attack Phelix.
Although our time and resources have been limited, we have not yet
discovered any workable method of attacking Phelix.


\subsection{Static analysis}
A static analysis takes the keystream and tries to reconstruct the
state and key. Several properties make this type of attack difficult.
Even if the whole state is known, any four consecutive keystream
words are fully random. This is because each $X_{i,0}$ key value
affects $S_{i}$ in a bijective manner, so for any given state and any
sequence of $X_{i,1}$ words, there is a bijective mapping from
$K_{i\bmod 8}, \ldots, K_{(i+3)\bmod 8}$ to $S_{i}, \ldots, S_{i+3}$.
A similar argument applies when the block function is computed
backwards. Any attempt to recover the key, even if the state is known
at a single point, must therefore span at least 4 blocks. Of course,
there is no reasonable way of finding the state. At any point in a
block, there are at least 256 bits of unknown state, even after the
keystream word is output. As the design strength is 128 bits, an
attacker cannot afford to guess the entire state. A partially guessed
state does not help much, as key material is added at twice the rate
that keystream is produced.

\subsection{Period length}
The Phelix internal state is updated continuously by the plaintext it is
encrypting.  So long as the plaintext is not repeating, the keystream should
have an arbitrarily long period, up to the maximum packet size of $2^{64}$ bytes.

With a fixed or repeating plaintext, the Phelix state does not cycle, either.
In section~\ref{sec:Rat-keyschedule} we showed that any 17 consecutive key
words used as inputs to the block function are unique. The nonrepeating key
word values prevent the state from ever falling into a cycle.


\subsection{State collisions} 
In \cite{Muller:Helix04}, an internal collision after $2^{114}$ words of
chosen plaintext was found in the cipher Helix \cite{FWSKLK:Helix03}, the
predecessor to Phelix.  To avoid this class of attack, Phelix added the 4
``old'' state words, increasing the internal state significantly to 288
bits.  Thus, the unknown state remains at 256 bits even after outputting
the keystream word within a block, so no collisions are reasonably expected
within the security bounds.

\subsection{Weak keys}
Phelix makes constant use of the words of the working key.  An all-zero
working key intuitively seems like a bad thing (it effectively omits a few
operations from the block function), but we have not discovered any possible
attack based on it. The all-zero working key is only generated by a single
key of 32 bytes in length. Shorter key length cannot generate the all-zero
working key. The all-zero working key does not seem to have any practical
security relevance, and there is no reason to treat this key differently
from any other key.

\subsection{Adaptive chosen plaintext attacks}
Because the plaintext affects the state, Phelix allows an attack model that
traditional stream ciphers prevent: An attacker can request the encryption
of a plaintext block under an already established (key,nonce) pair, and can
use the resulting ciphertext to determine what plaintext to request next.

We have found no way to use such an attack against Phelix.  As with the
discussion of static analysis above, the large unknown and untouchable
state, and the continual mixing of key material into that state, appear to
defeat attempts to use control over one input of the block function to
control other parts of its state.  Additionally, the usage restrictions on
Phelix do not allow reuse of nonces, which ensures that the state is always a
``moving target.''

However, it should be noted that in \cite{Muller:Helix04}, a key recovery
attack of complexity $2^{88}$ was found against Helix \cite{FWSKLK:Helix03},
assuming nonce reuse.  While this attack clearly violates critical and
commonly accepted usage restrictions of stream ciphers, the concern that the
Helix key itself could be recovered led to the Phelix enhancements. The
active state values of Phelix are identical to those of Helix, but the inclusion
of the ``old'' state variables in the Phelix output keystream function makes
it much more difficult to guess or learn the internal active state than in
Helix.  Further, the point within the Phelix block at which the keystream is
extracted, namely $Y^{(i)}_4$, forces much greater diffusion and nonlinear
mixing of the previous plaintext word, thwarting the differential plaintext
attack described in \cite{Muller:Helix04}.

\subsection{Chosen input differential attacks}
One powerful mode of attack is for the attacker to make small changes in the
input values and look at how the changes propagate through the cipher.

In Phelix, this can be done only with the key or the nonce. In each case, the
block function is applied multiple times to the input. In Phelix, all the
places where such attacks are possible have eight consecutive blocks
without any output. A change to the nonce, such as is considered in
\cite{JGV:stream93}, will be thoroughly mixed into the state by the time the
first keystream word is generated. Similarly, a change to the last
plaintext byte is thoroughly mixed into the state before the first MAC tag
word is generated. A differential attack would have to use a differential
through 8 blocks, or 160 rounds of Phelix. A search found no useful
differentials for 8 blocks of Phelix, nor useful higher-order differentials.


\subsection{Algebraic attacks over GF($2$)}\label{sec:XSL-Attack}

The algebraic analysis of Helix, the predecessor to Phelix, employed 
linearization techniques, inspired by extended linearisation 
\cite{CP:XSL02b}. Independently from Helix, such algebraic techniques have 
been used to successfully analyze stream ciphers 
\cite{Courtois:Toyo02,Armknecht:Bluetooth02}. The best attack against
Helix was based on optimistically (from the addversary's point of view) 
assuming a certain system of equations to have full rank. The adversary than
had to solve this system with its $\approx{2^{49.1}}$ binary unknowns. 
  Solving a system of linear equations in $N$ unknowns by Gaussian elimination 
takes time $O(N^3)$. However,  \cite{CP:XSL02b} suggested a
$O(N^{2.376})$-time algorithm, though with some apparently huge 
proportionality constant. 
  If we extremely optimistically set this constant to 1, the attacks
takes time $2^{116.7}$. At the time of designing Helix, we did not
consider this a practical threat, and, due to the optimistic and even
unrealistic nature of our assumptions, we conjectured the algebraic attack
actually to to take more than $2^{128}$ steps. We are not aware of any results
contradicting this conjecture. 

As it turns out, Phelix' resistance against this type of attack greatly
improves on Helix' resistance.  While Phelix uses the same block function as
Helix, the internal state size of Phelix has increased by 128 bits. The
analysis shows that (under the same full-rank assumption as before), the
system of linar equations now has $\approx 2^{64.07}$ unknowns. No algorithm
is known, which could possibly solve such a system of linear equations in 
$2^{128}$ steps or less.

\section{Conclusions and intellectual property statement}
Most applications that require symmetric cryptography actually
require both encryption and authentication.  We believe that the
most efficient way to achieve this combined goal is to design
cryptographic primitives specifically for the task.  Towards this
end, we present a new such cryptographic primitive, called Phelix.
We hope that Phelix and this paper will spur additional research in
authenticated encryption stream ciphers.
As with any experimental design, we note that
Phelix should not be used
until it has received additional cryptanalysis.

There are no hidden weaknesses inserted the the designers of Phelix, nor
are we aware of any material weaknesses of the algorithm.

Finally, we hereby explicitly release any intellectual property
rights to Phelix into the public domain.  Furthermore, we are
not aware of any patent or patent application anywhere in the world
that covers Phelix.

\section{Acknowledgements}
We would like to thank David Wagner, Rich Schroeppel, Niels Ferguson, John 
Kelsey, and Yoshi Kohno for their helpful comments and encouragements during 
the development of Helix and Phelix.

\bibliographystyle{alpha}
{\sloppy\hbadness 2000      % This helps reduce warnings
\bibliography{macfergus}
}

\appendix
\section{Test vectors}

The authors maintain a website at \url{http://www.schneier.com/phelix.html}
with Phelix news, example code, and test vectors. We give some simple test vectors
here. (The 8-word working key is given as a sequence of 32 bytes, least
significant byte first.)

\begin{verbatim}
 MAC tag:     128 bits
 Initial Key: <empty string>
 Working Key: A9 3B 6E 32  BC 23 4F 6C  32 6C 0F 82  74 FF A2 41
              E3 DA 57 7D  EF 7C 1B 64  AF 78 7C 38  DC EF E3 DE 
 Nonce:       00 00 00 00  00 00 00 00  00 00 00 00  00 00 00 00 
 AAD:         <empty string>
 Plaintext:   00 00 00 00  00 00 00 00  00 00 
 Ciphertext:  D5 2D 45 C6  05 FD 7A 67  74 8D 
 MAC:         EF 7B FE 7A  EB DC 1A 8B  43 36 2F 28  93 80 0D BC 

 MAC tag:     128 bits
 Initial Key: 00 00 00 00  01 00 00 00  02 00 00 00  03 00 00 00
              04 00 00 00  05 00 00 00  06 00 00 00  07 00 00 00 
 Working Key: 6E E9 A7 6C  BD 0B F6 20  A6 D9 B7 59  49 D3 39 95
              04 F8 4A D6  83 12 F9 06  ED D1 A6 98  9E C8 9D 45 
 Nonce:       00 00 00 01  01 00 00 01  02 00 00 01  03 00 00 01 
 AAD:         <empty string>
 Plaintext:   00 01 02 03  01 02 03 04  02 03 04 05  03 04 05 06
              04 05 06 07  05 06 07 08  06 07 08 09  07 08 09 0A 
 Ciphertext:  B5 FC 4B F5  BC 64 0A 56  00 3D 59 6D  33 4B A5 94
              A5 48 7B 4E  30 8E DB 05  A7 D6 2F 23  45 14 02 4A 
 MAC:         DB 0C 22 C4  66 BD CD E4  E3 29 03 F7  9A E5 42 D1 

 MAC tag:     64  bits
 Initial Key: 01 02 03 04  05 06 07 08  08 07 06 05  04 03 02 01 
 Working Key: 98 3F 23 CE  B9 F4 D9 68  B0 56 54 06  2D 15 34 C6
              4B 38 AD E7  C2 BA A4 DF  D8 D4 02 21  DB BC 96 E8 
 Nonce:       04 00 00 00  05 00 00 00  06 00 00 00  07 00 00 00 
 AAD:         <empty string>
 Plaintext:   <empty string>
 Ciphertext:  <empty string>
 MAC:         BE AF D3 BD  00 BE 44 17 

 MAC tag:     96  bits
 Initial Key: 09 07 05 03  01 
 Working Key: 36 0A 5B CD  91 EC 72 89  0A C3 BA 9D  1C 48 E2 E0
              03 1C 86 33  83 A4 9F D8  CB F8 CC CA  1F D6 AB 5D 
 Nonce:       08 07 06 05  04 03 02 01  00 01 02 03  04 05 06 07 
 AAD:         00 02 04 06  01 03 05 07  08 
 Plaintext:   00 01 02 03  01 02 03 04  02 03 04 05  FF 
 Ciphertext:  F1 0D 3E 06  7A 32 B1 BE  DA A5 89 8B  DE 
 MAC:         60 A2 31 C1  C9 F5 E4 EF  40 AA 0A 1C 
\end{verbatim}

\end{document}