New Derivation Rule for Linear Approximations and Its Application to ChaCha
摘要
ChaCha is an ARX-based stream cipher and has been widely used in practice. In this paper, we propose a new derivation rule for linear approximations of ARX-based ciphers and then apply it to ChaCha. Compared with the previous derivation rules for linear approximations, it can reduce the number of active bits when deriving linear approximations. By combining this new derivation rule with the previous derivation rules in a mixed pattern, we improve the 3.5- and 4-round linear approximations for ChaCha. The original 3.5-round linear approximation presented at EUROCRYPT 2021 has a correlation of \(2^{-47}\) , which was improved to be \(-2^{-41}\) recently. This paper further improves it with a better correlation of \(-2^{-40}\) . Besides, we enhance the 4-round linear approximation for ChaCha with correlation \({2^{ - 48}}\) , improving the previous result (i.e., \(-2^{-50}\) ) by a factor of \(-{2^2}\) . The new derivation rule for linear approximations is general and can be applied to other ARX-based ciphers.