Abstract The Generalized Feistel Structure ( $$\texttt{GFS}$$ GFS ) is one of the most widely used frameworks in symmetric cipher design. In FES 2010, Suzaki and Minematsu strengthened the cryptanalysis security of $$\texttt{GFS}$$ GFS by searching for shuffles with the best diffusion property. In ASIACRYPT 2018, Shi et al. suggested a set of shuffles, which makes $$\texttt{GFS}$$ GFS a better resistance against Demirci–Selcuk meet-in-the-middle cryptanalysis. Since these shuffles are different from the currently known good ones and also different from the shuffles used in $$\texttt{TWINE}$$ TWINE and $$\texttt{LBlock}$$ LBlock , our research focuses on a more comprehensive evaluation of $$\texttt{GFS}$$ GFS with different shuffles, including diffusion property of shuffle, differential, linear, impossible differential, zero-correlation linear, integral and Demirci–Selcuk meet-in-the-middle cryptanalysis, to find the best one. Such evaluations entail significant time consumption. Thus, we utilize Mixed Integral Linear Programming models and introduce an evaluate-and-filter strategy to achieve it efficiently. Our results verify that the shuffles discovered by Suzaki and Minematsu and those used in $$\texttt{TWINE}$$ TWINE and $$\texttt{LBlock}$$ LBlock are the best so far. We also find that the cryptanalysis resistances of $$\texttt{GFS}$$ GFS are not necessarily consistent. It is this finding that makes the necessity of our more comprehensive evaluation self-evident.

Abstract Small-state stream ciphers (SSCs), which violate the principle that the state size should exceed the key size by a factor of two, still demonstrate robust security properties while maintaining a lightweight design. These ciphers can be classified into several constructions and their basic security requirement is to resist generic attacks, i.e., the time–memory–data tradeoff (TMDTO) attack. In this paper, we investigate the security of small-state constructions in the multi-user setting. Based on it, the TMDTO distinguishing attack and the TMDTO key recovery attack are developed for such a setting. It is shown that SSCs which continuously use the key can not resist the TMDTO distinguishing attack. Moreover, SSCs based on the continuous-IV-key-use construction cannot withstand the TMDTO key recovery attack when the key length is shorter than the IV length, no matter whether the keystream length is limited or not. Finally, we apply these two generic attacks to TinyJAMBU and DRACO in the multi-user setting. The TMDTO distinguishing attack on TinyJAMBU with a 128-bit key can be mounted with time, memory, and data complexities of $$2^{64}$$ 2 64 , $$2^{48}$$ 2 48 , and $$2^{32}$$ 2 32 , respectively. This attack is comparable with a recent work on ToSC 2022, where partial key bits of TinyJAMBU are recovered with more than $$2^{50}$$ 2 50 users (or keys). As DRACO’s IV length is smaller than its key length, it is vulnerable to the TMDTO key recovery attack. The resulting attack has a time and memory complexity of both $$2^{112}$$ 2 112 , which means DRACO does not provide 128-bit security in the multi-user setting.