We have been looking at eprint paper "A chosen IV attack using phase shifting equivalent keys against Decim v2" by Hidehiko Nakagami, Ryoichi Teramura, Toshihiro Ohigashi, Hidenori Kuwakado and Masakatu Morii and we have some concerns about the validity of the results because of two main points:

- the first point is that the claim on p.7 that, if a phase shifting equivalent key $\hat{K}$ exists for $K$, then the resulting keystream $Z$ and $\hat{Z}$ will synchronize eventually and thus enable the attacker to check that $K$ and $\hat{K}$ are phase shifting equivalent by using only keystream $Z$, is wrong. Indeed, two 1-bit Phase Shifting Equivalent Keys $K$ and $\hat{K}$ yield sequences output from the filter generator that are shifted from one bit. Thus, the two sequences that are input to the ABSG mechanism are shifted from one bit. As shown in the article "The Bit-Search Generator", published at SASC2004, the BSG and the ABSG outputs can be seen as the result of an action of the input sequence on a set of three elements. Two input sequences will yield shifted outputs iff the input sequences are shifted by a sequence of full BSG words, i.e. words of the form $b \bar{b}^k b$. Therefore, two input sequences that are shifted by only one bit do not yield shifted outputs and the outputs of $Z$ and $\hat{Z}$ never synchronize.

As a consequence, $Z$ and $\hat{Z}$ keystreams arising from phase shifting equivalent keys cannot be detected. Thus, in the attack algorithm from Section 5.2, testing whether an element of $E$ is $\hat{K}$ by generating the corresponding keystream $\hat{Z}$ and comparing it to the original keystream to detect phase shifting equivalent keys is not possible.

- the second point is the time complexity computation in the final attack.

It is usual to consider the time complexity of a key recovery algorithm as the overall expected number of keys tested in the algorithm to recover the key with probability close to 1, which means considering the total serial computational time. Otherwise, it would be sufficient to run 2 processes in parallel performing exhaustive search in two disjoint halves of the key space in order to claim a time complexity of $2^{n-1}$ to recover the key with probability 1.
A variant for time complexity is the average time complexity, where you compute the average expected number of keys tested. In the case of average time complexity, as even a single machine doing brute force will perform $2^{n-1}$ tests on average, the relevance of an average complexity of more than $2^{n-1}$ is questionable.
In this paper, the time complexity appears to be a mix of the two definitions above. The authors should precise the meaning of the result and provide a more precise description of the attack algorithm in order to support the complexity analysis.

If we have understood well the algorithm, there seems to be other flaws in the computation. Indeed, in the description of the attack algorithm in Section 5.2, it is mentioned that a subset $E$ of $2^{78}$ keys is first parsed, and for each element $x$ in this subset, the algorithm tests whether $x$ is suitable as the key $K$, and whether $x$ is suitable as a shifted key $\hat{K}$, thus requiring two key tests each time (and generation of one $Z$ keystream and one $\hat{Z}$ keystream). This doubles the time complexity of the algorithm steps carried out in $E$, as for each element in $E$, two candidates keys are tested. This is not taken into account in the time complexity. For instance, for case 4, the time complexity is $\frac{21}{32} (2\times 2^{78} + (2^{80} - 2^{78})$, as first $E$ is parsed unsuccessfully for $K$ and $\hat{K}$, and then $\bar{E}$ is parsed for $K$. This yields an increase in the average time complexity of the exhaustive key search that needs to be taken into account.

To summarize, we believe that there may be flaws in the time complexity computation of the attack algorithm in Section 5.2, and, most importantly, that a misunderstanding of the ABSG in the reasoning may invalidate this algorithm.


We will appreciate feedback and comments on these remarks.



Best regards,

Come Berbain, Aline Gouget, Herve Sibert

Regarding the alleged attack in the paper "A Chosen IV Attack Using Phase Shifting Equivalent Keys against DECIM v2", we have just submitted a note called "Understanding Phase Shifting Equivalent Keys and Exhaustive Search" to the eprint archive.

The note shows that this type of attack, from a general perspective, always has a time complexity at least $2^n$ updates of the cipher state, with $n$ being the length of the key. The erroneous result in the paper above stems from the fact that the authors forgot to include the initialization time in their computation, so one should read that their attack has complexity $O(2^{79.56})$, not $2^{79.56}$.

In a nutshell, what we prove in our note is that, considering a single operation to be one update of the cipher state, the constant in the $O(2^{m})$ attack complexity is always at least $2^{n-m}$. This type of attack can be used to speed up exhaustive search by "parallelizing" partly the search for multiple keys at once. However, there is an overhead for each parallelized key, which is always at least the computational cost of one additional update of the internal state, hence the result that such "attacks" always require at least the computation of $2^n$ updates of the internal state.

Please note that our result also invalidates the claims made by the authors in the introduction about the fact that another eSTREAM algorithm, Grain, fails under a similar attack better of complexity $2^{78.4}$ or $2^{78.7}$. Here again, the authors did not include the computational cost per tested key.

As a result, these attacks against both Decim v2 and Grain have a complexity that remains well over $2^80$, as these complexities shall be multiplied by a bit more than the complexity of one initialization of the cipher. Even in the case of a cipher with 80-bits keys to which these attacks would apply ideally (e.g. where the initialization and keystream generation steps are the same), these attacks could not reach less than $2^{80}$.

At last, please note that the authors of the paper "A Chosen IV Attack Using Phase Shifting Equivalent Keys against DECIM v2" are currently reconsidering their attack and the evaluation of the time complexity of their attack after the authors of this note pointed out (in the post above) a misunderstanding of the Decim v2 scheme. We thus expect a revised version to take into account this note and the comments above.

The note is available here: [eprint.iacr.org].

The note [eprint.iacr.org] has been updated to reflect the changes in Report 2008/128.
Namely:
- after taking into account the behavior of the ABSG in the right manner, the authors claim 2^79.90 time complexity,
- the same problems remain in essence:
* the complexity of the algorithm is at least 2^79.90 multiplied by (768 rounds + some keystream generation + more keystream generation in the case of phase-shifted keys),
* despite the comments above, the revised version of Report 2008/128 does not detail the algorithm more than the previous version; this prevents computing the real complexity of the algorithm to verify the claim precisely,
- all the comments and conclusions from the previous version of the note on phase-shifting-based attacks remain valid; the update encompasses only the description of Report 2008/128, which has been modified to take the revision into account.



Edited 1 time(s). Last edit at 17-Apr-2008 08:01 by Tib.