\`x^2+y_1+z_12^34\`
Advanced Search
Article Contents
Article Contents

Revisiting design principles of Salsa and ChaCha

Abstract Full Text(HTML) Figure(3) / Table(7) Related Papers Cited by
  • Salsa and ChaCha are well known names in the family of stream ciphers. In this paper, we first revisit the existing attacks on these ciphers. We first perform an accurate computation of the attack complexities of the existing technique instead of the estimation used in previous works. This improves the complexity by some margin. The differential attacks using probabilistic neutral bits against ChaCha and Salsa involve two probability biases: forward probability bias ($ \epsilon_d $) and backward probability bias ($ \epsilon_a $). In the second part of the paper, we suggest a method to increase the backward probability bias, which helps reduce the attack complexity. Finally, we focus on the design principle of ChaCha. We suggest a slight modification in the design of this cipher as a countermeasure of the differential attacks against it. We show that the key recovery attacks proposed against ChaCha will not be effective on this modified version.

    Mathematics Subject Classification: Primary: 11Y05; Secondary: 94A60.

    Citation:

    \begin{equation} \\ \end{equation}
  • 加载中
  • Figure 1.  Two Normal distribution curves

    Figure 2.  Comparison between the probability achieved by random values and our values for ChaCha

    Figure 3.  Comparison between the probability achieved by random values and our values for Salsa

    Table 1.  New attack complexities for 8 rounds Salsa and 7 rounds ChaCha

    Cipher $ n $ $ |\epsilon| $ $ \alpha $ $ T $ $ N $ Existing complexity New complexity
    Salsa 43 0.000176 16.43 $ 2^{29.66} $ $ 2^{30.66} $ $ 2^{243.93} $ $ 2^{243.74} $
    ChaCha 53 0.000100 24.83 $ 2^{31.72} $ $ 2^{32.72} $ $ 2^{235.93} $ $ 2^{235.78} $
     | Show Table
    DownLoad: CSV

    Table 2.  Attack complexities using chaining distinguisher

    Cipher Existing complexity New complexity
    Salsa $ 2^{243.67} $ $ 2^{243.23} $
    ChaCha $ 2^{235.22} $ $ 2^{234.78} $
     | Show Table
    DownLoad: CSV

    Table 3.  Values for Probabilistic Neutral Bits of ChaCha

    3 6 7 15 16 17 18 31 35 38 67 68
    1 1 0 1 1 1 0 x 1 0 0 1
    71 72 73 91 92 93 94 95 96 97 98 99
    1 1 0 x x x x x 1 1 1 1
    100 103 104 105 106 107 127 136 137 138 139 156
    0 1 1 1 1 0 x 0 0 0 1 x
    159 191 223 224 225 226 227 228 248 249 250 251
    x x x 1 1 1 1 0 x x x x
    252 253 254 255
    x x x x
     | Show Table
    DownLoad: CSV

    Table 4.  Comparison of bias $ \epsilon $ and complexities between existing and our method for ChaCha when $ n = 52 $

    Percentage of keys bias (existing) bias (our) existing complexity our complexity
    10 0.000200 0.000648 $ 2^{234.97} $ $ 2^{231.56} $
    20 0.000178 0.000433 $ 2^{235.28} $ $ 2^{232.68} $
    30 0.000165 0.000314 $ 2^{235.50} $ $ 2^{ 233.57} $
    40 0.000152 0.000231 $ 2^{235.73} $ $ 2^{234.43} $
    50 0.000139 0.000182 $ 2^{235.96} $ $ 2^{235.09} $
     | Show Table
    DownLoad: CSV

    Table 5.  Values for the probabilistic neutral bits of Salsa

    25 26 27 28 29 30 31 39 70 71 72 107
    x x x x x x x x 1 1 0 1
    119 120 121 122 164 165 166 167 168 169 170 171
    1 1 1 0 0 1 1 1 1 0 0 0
    172 173 174 175 176 209 210 211 212 213 224 225
    0 0 0 0 1 1 1 1 1 0 0 1
    241 242 243 244 245 246 255
    1 1 1 1 1 0 x
     | Show Table
    DownLoad: CSV

    Table 6.  Comparison of bias and complexities between existing and our method for Salsa when $ n = 43 $

    Percentage of keys bias (existing) bias (our) existing complexity our complexity
    10 -0.000232 -0.000667 $ 2^{243.18} $ $ 2^{240.11} $
    20 -0.000207 -0.000397 $ 2^{243.48} $ $ 2^{241.53} $
    30 -0.000192 -0.000305 $ 2^{243.69} $ $ 2^{242.24} $
    40 -0.000181 -0.000226 $ 2^{ 243.86} $ $ 2^{243.06} $
    50 -0.000176 -0.000192 $ 2^{243.93} $ $ 2^{243.51} $
     | Show Table
    DownLoad: CSV

    Table 7.  Number of $ Random $ $ Value $ $ Positions $ for some size of PNB

    Percentage of PNB's Number of $ Random $ $ Value $ $ Positions $
    5% 70
    10% 127
    15% 180
    20% 219
     | Show Table
    DownLoad: CSV
  • [1] J. P. AumassonS. FischerS. KhazaeiW. Meier and C. Rechberger, New features of latin dances: Analysis of salsa, chacha, and rumba, FSE 2008, LNCS, 5086 (2008), 470-488.  doi: 10.1007/978-3-540-71039-4_30.
    [2] D. J. Bernstein, Salsa20 specification, eSTREAM Project algorithm description, http://www.ecrypt.eu.org/stream/salsa20pf.html, 2005.
    [3] D. J. Bernstein, ChaCha, a variant of Salsa20, In Workshop Record of SASC, volume 8, 2008.
    [4] A. R. Choudhuri and S. Maitra, Significantly Improved Multi-bit Differentials for Reduced Round Salsa and ChaCha, Accepted in FSE 2017, Available at http://eprint.iacr.org/2016/1034.
    [5] P. Crowley, Truncated differential cryptanalysis of five rounds of Salsa20, IACR 2005. Available at http://eprint.iacr.org/2005/375.
    [6] S. Dey and S. Sarkar, Improved analysis for reduced round Salsa and ChaCha, Discrete Applied Mathematics, 227 (2017), 58-69.  doi: 10.1016/j.dam.2017.04.034.
    [7] S. FischerW. MeierC. Berbain and J. F. Biasse, Non-randomness in eSTREAM Candidates Salsa20 and TSC-4, Progress in Cryptology–INDOCRYPT 2006, LNCS, 4329 (2006), 2-16.  doi: 10.1007/11941378_2.
    [8] S. Maitra, Chosen IV cryptanalysis on reduced round chacha and salsa, Discrete Applied Mathematics, 208 (2016), 88-97.  doi: 10.1016/j.dam.2016.02.020.
    [9] S. Maitra, G. Paul and W. Meier, Salsa20 Cryptanalysis: New Moves and Revisiting Old Styles, WCC 2015. Available at http://eprint.iacr.org/2015/217.
    [10] , Sage: Open Source Mathematics Software, http://www.sagemath.org.
    [11] Z. ShiB. ZhangD. Feng and W. Wu, Improved key recovery attacks on reduced-round salsa20 and ChaCha, ICISC 2012, LNCS, 7839 (2012), 337-351.  doi: 10.1007/978-3-642-37682-5_24.
    [12] Y. Tsunoo, T. Saito, H. Kubo, T. Suzaki and H. Nakashima, Differential Cryptanalysis of Salsa20/8, 2007.
  • 加载中

Figures(3)

Tables(7)

SHARE

Article Metrics

HTML views(651) PDF downloads(859) Cited by(0)

Access History

Other Articles By Authors

Catalog

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return