bison Instantiating the Whitened Swap-Or-Not Construction | SpringerLink
Skip to main content
Springer Nature Link
Log in

bison Instantiating the Whitened Swap-Or-Not Construction

  • Conference paper
  • First Online:
Advances in Cryptology – EUROCRYPT 2019 (EUROCRYPT 2019)

Part of the book series: Lecture Notes in Computer Science ((LNSC,volume 11478))

Abstract

We give the first practical instance – bison – of the Whitened Swap-Or-Not construction. After clarifying inherent limitations of the construction, we point out that this way of building block ciphers allows easy and very strong arguments against differential attacks.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 11439
Price includes VAT (Japan)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 14299
Price includes VAT (Japan)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

Notes

  1. 1.

    Primary constructions give bent functions from scratch, while secondary constructions build new bent functions from previously defined ones.

  2. 2.

    E.g. if, with high probability, the \(p_i + c_i\) do not depend on one or more \(k_j\)’s, the described attack can be extended to one or more rounds with high probability.

  3. 3.

    If (some) round keys are linearly dependent, Lemma 3 can easily be extended to more rounds.

References

  1. Abdelraheem, M.A., Ågren, M., Beelen, P., Leander, G.: On the distribution of linear biases: three instructive examples. In: Safavi-Naini, R., Canetti, R. (eds.) CRYPTO 2012. LNCS, vol. 7417, pp. 50–67. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-32009-5_4

    Chapter  Google Scholar 

  2. Advanced Encryption Standard (AES), November 2001

    Google Scholar 

  3. Andreeva, E., Bogdanov, A., Dodis, Y., Mennink, B., Steinberger, J.P.: On the indifferentiability of key-alternating ciphers. In: Canetti, R., Garay, J.A. (eds.) CRYPTO 2013. LNCS, vol. 8042, pp. 531–550. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-40041-4_29

    Chapter  Google Scholar 

  4. Beierle, C., Canteaut, A., Leander, G., Rotella, Y.: Proving resistance against invariant attacks: how to choose the round constants. In: Katz, J., Shacham, H. (eds.) CRYPTO 2017. LNCS, vol. 10402, pp. 647–678. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-63715-0_22

    Chapter  Google Scholar 

  5. Biham, E., Shamir, A.: Differential cryptanalysis of DES-like cryptosystems. In: Menezes, A.J., Vanstone, S.A. (eds.) CRYPTO 1990. LNCS, vol. 537, pp. 2–21. Springer, Heidelberg (1991). https://doi.org/10.1007/3-540-38424-3_1

    Chapter  Google Scholar 

  6. Biryukov, A., Khovratovich, D.: Related-key cryptanalysis of the full AES-192 and AES-256. In: Matsui, M. (ed.) ASIACRYPT 2009. LNCS, vol. 5912, pp. 1–18. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-10366-7_1

    Chapter  Google Scholar 

  7. Biryukov, A., Khovratovich, D., Nikolić, I.: Distinguisher and related-key attack on the full AES-256. In: Halevi, S. (ed.) CRYPTO 2009. LNCS, vol. 5677, pp. 231–249. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-03356-8_14

    Chapter  Google Scholar 

  8. Biryukov, A., Perrin, L.: On reverse-engineering S-boxes with hidden design criteria or structure. In: Gennaro, R., Robshaw, M. (eds.) CRYPTO 2015. LNCS, vol. 9215, pp. 116–140. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-47989-6_6

    Chapter  Google Scholar 

  9. Blondeau, C., Nyberg, K.: Improved parameter estimates for correlation and capacity deviates in linear cryptanalysis. IACR Trans. Symm. Cryptol. 2016(2), 162–191 (2016). http://tosc.iacr.org/index.php/ToSC/article/view/570

  10. Bogdanov, A., Knudsen, L.R., Leander, G., Standaert, F.-X., Steinberger, J., Tischhauser, E.: Key-alternating ciphers in a provable setting: encryption using a small number of public permutations (extended abstract). In: Pointcheval, D., Johansson, T. (eds.) EUROCRYPT 2012. LNCS, vol. 7237, pp. 45–62. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-29011-4_5

    Chapter  MATH  Google Scholar 

  11. Boura, C., Canteaut, A., De Cannière, C.: Higher-order differential properties of Keccak and Luffa. In: Joux, A. (ed.) FSE 2011. LNCS, vol. 6733, pp. 252–269. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-21702-9_15

    Chapter  Google Scholar 

  12. Canteaut, A., Lallemand, V., Leander, G., Neumann, P., Wiemer, F.: BISON - instantiating the whitened swap-or-not construction. Cryptology ePrint Archive, Report 2018/1011 (2018)

    Google Scholar 

  13. Canteaut, A., Roué, J.: On the behaviors of affine equivalent Sboxes regarding differential and linear attacks. In: Oswald, E., Fischlin, M. (eds.) EUROCRYPT 2015. LNCS, vol. 9056, pp. 45–74. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-46800-5_3

    Chapter  Google Scholar 

  14. Carlet, C.: Boolean functions for cryptography and error correcting codes. In: Crama, Y., Hammer, P. (eds.) Boolean Methods and Models. Cambridge University Press (2007)

    Google Scholar 

  15. Chen, S., Steinberger, J.: Tight security bounds for key-alternating ciphers. In: Nguyen, P.Q., Oswald, E. (eds.) EUROCRYPT 2014. LNCS, vol. 8441, pp. 327–350. Springer, Heidelberg (2014). https://doi.org/10.1007/978-3-642-55220-5_19

    Chapter  Google Scholar 

  16. Daemen, J.: Cipher and hash function design, strategies based on linear and differential cryptanalysis. Ph.D. thesis. K.U.Leuven (1995). http://jda.noekeon.org/

  17. Daemen, J., Govaerts, R., Vandewalle, J.: Block ciphers based on modular arithmetic. In: Wolfowicz, W. (ed.) State and Progress in the Research of Cryptography, pp. 80–89. Fondazione Ugo Bordoni (1993)

    Google Scholar 

  18. Daemen, J., Govaerts, R., Vandewalle, J.: Correlation matrices. In: Preneel, B. (ed.) FSE 1994. LNCS, vol. 1008, pp. 275–285. Springer, Heidelberg (1995). https://doi.org/10.1007/3-540-60590-8_21

    Chapter  Google Scholar 

  19. Daemen, J., Rijmen, V.: The block cipher Rijndael. In: Quisquater, J.-J., Schneier, B. (eds.) CARDIS 1998. LNCS, vol. 1820, pp. 277–284. Springer, Heidelberg (2000). https://doi.org/10.1007/10721064_26

    Chapter  Google Scholar 

  20. Daemen, J., Rijmen, V.: The wide trail design strategy. In: Honary, B. (ed.) Cryptography and Coding 2001. LNCS, vol. 2260, pp. 222–238. Springer, Heidelberg (2001). https://doi.org/10.1007/3-540-45325-3_20

    Chapter  Google Scholar 

  21. Daemen, J., Rijmen, V.: The Design of Rijndael: AES - The Advanced Encryption Standard. Information Security and Cryptography. Springer, Heidelberg (2002). https://doi.org/10.1007/978-3-662-04722-4

    Book  MATH  Google Scholar 

  22. Daemen, J., Rijmen, V.: Understanding two-round differentials in AES. In: De Prisco, R., Yung, M. (eds.) SCN 2006. LNCS, vol. 4116, pp. 78–94. Springer, Heidelberg (2006). https://doi.org/10.1007/11832072_6

    Chapter  Google Scholar 

  23. Derbez, P., Fouque, P.-A., Jean, J.: Improved key recovery attacks on reduced-round AES in the single-key setting. In: Johansson, T., Nguyen, P.Q. (eds.) EUROCRYPT 2013. LNCS, vol. 7881, pp. 371–387. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-38348-9_23

    Chapter  MATH  Google Scholar 

  24. Dillon, J.F.: A survey of bent functions. NSA Tech. J. 191, 215 (1972)

    Google Scholar 

  25. Even, S., Mansour, Y.: A construction of a cipher from a single pseudorandom permutation. J. Cryptol. 10(3), 151–162 (1997)

    Article  MathSciNet  Google Scholar 

  26. Ferguson, N., et al.: Improved cryptanalysis of Rijndael. In: Goos, G., Hartmanis, J., van Leeuwen, J., Schneier, B. (eds.) FSE 2000. LNCS, vol. 1978, pp. 213–230. Springer, Heidelberg (2001). https://doi.org/10.1007/3-540-44706-7_15

    Chapter  Google Scholar 

  27. Gilbert, H., Minier, M.: A collision attack on 7 rounds of Rijndael. In: AES Candidate Conference, vol. 230, p. 241 (2000)

    Google Scholar 

  28. Grassi, L., Rechberger, C., Rønjom, S.: Subspace trail cryptanalysis and its applications to AES. IACR Trans. Symm. Cryptol. 2016(2), 192–225 (2016). http://tosc.iacr.org/index.php/ToSC/article/view/571

  29. Grassi, L., Rechberger, C., Rønjom, S.: A new structural-differential property of 5-round AES. In: Coron, J.-S., Nielsen, J.B. (eds.) EUROCRYPT 2017. LNCS, vol. 10211, pp. 289–317. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-56614-6_10

    Chapter  Google Scholar 

  30. Guo, C., Lin, D.: On the indifferentiability of key-alternating feistel ciphers with no key derivation. In: Dodis, Y., Nielsen, J.B. (eds.) TCC 2015. LNCS, vol. 9014, pp. 110–133. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-46494-6_6

    Chapter  Google Scholar 

  31. Hoang, V.T., Morris, B., Rogaway, P.: An enciphering scheme based on a card shuffle. In: Safavi-Naini, R., Canetti, R. (eds.) CRYPTO 2012. LNCS, vol. 7417, pp. 1–13. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-32009-5_1

    Chapter  Google Scholar 

  32. Hoang, V.T., Tessaro, S.: Key-alternating ciphers and key-length extension: exact bounds and multi-user security. In: Robshaw, M., Katz, J. (eds.) CRYPTO 2016. LNCS, vol. 9814, pp. 3–32. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-53018-4_1

    Chapter  Google Scholar 

  33. Hong, S., Lee, S., Lim, J., Sung, J., Cheon, D., Cho, I.: Provable security against differential and linear cryptanalysis for the SPN structure. In: Goos, G., Hartmanis, J., van Leeuwen, J., Schneier, B. (eds.) FSE 2000. LNCS, vol. 1978, pp. 273–283. Springer, Heidelberg (2001). https://doi.org/10.1007/3-540-44706-7_19

    Chapter  Google Scholar 

  34. Jakobsen, T., Knudsen, L.R.: The interpolation attack on block ciphers. In: Biham, E. (ed.) FSE 1997. LNCS, vol. 1267, pp. 28–40. Springer, Heidelberg (1997). https://doi.org/10.1007/BFb0052332

    Chapter  Google Scholar 

  35. Keliher, L., Sui, J.: Exact maximum expected differential and linear probability for two-round advanced encryption standard. IET Inf. Secur. 1(2), 53–57 (2007)

    Article  Google Scholar 

  36. Kranz, T., Leander, G., Wiemer, F.: Linear cryptanalysis: key schedules and tweakable block ciphers. IACR Trans. Symm. Cryptol. 2017(1), 474–505 (2017)

    Google Scholar 

  37. Lai, X., Massey, J.L., Murphy, S.: Markov ciphers and differential cryptanalysis. In: Davies, D.W. (ed.) EUROCRYPT 1991. LNCS, vol. 547, pp. 17–38. Springer, Heidelberg (1991). https://doi.org/10.1007/3-540-46416-6_2

    Chapter  Google Scholar 

  38. Lampe, R., Seurin, Y.: Security analysis of key-alternating feistel ciphers. In: Cid, C., Rechberger, C. (eds.) FSE 2014. LNCS, vol. 8540, pp. 243–264. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-46706-0_13

    Chapter  Google Scholar 

  39. Leander, G., Abdelraheem, M.A., AlKhzaimi, H., Zenner, E.: A cryptanalysis of PRINTcipher: the invariant subspace attack. In: Rogaway, P. (ed.) CRYPTO 2011. LNCS, vol. 6841, pp. 206–221. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-22792-9_12

    Chapter  Google Scholar 

  40. Matsui, M.: On correlation between the order of S-boxes and the strength of DES. In: De Santis, A. (ed.) EUROCRYPT 1994. LNCS, vol. 950, pp. 366–375. Springer, Heidelberg (1995). https://doi.org/10.1007/BFb0053451

    Chapter  Google Scholar 

  41. Meier, W., Staffelbach, O.: Nonlinearity criteria for cryptographic functions. In: Quisquater, J.-J., Vandewalle, J. (eds.) EUROCRYPT 1989. LNCS, vol. 434, pp. 549–562. Springer, Heidelberg (1990). https://doi.org/10.1007/3-540-46885-4_53

    Chapter  Google Scholar 

  42. Miracle, S., Yilek, S.: Cycle slicer: an algorithm for building permutations on special domains. Cryptology ePrint Archive, Report 2017/873 (2017). http://eprint.iacr.org/2017/873

  43. Nyberg, K.: Linear approximation of block ciphers (rump session). In: De Santis, A. (ed.) EUROCRYPT 1994. LNCS, vol. 950, pp. 439–444. Springer, Heidelberg (1995). https://doi.org/10.1007/BFb0053460

    Chapter  Google Scholar 

  44. Nyberg, K.: “Provable” security against differential and linear cryptanalysis (invited talk). In: Canteaut, A. (ed.) FSE 2012. LNCS, vol. 7549, pp. 1–8. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-34047-5_1

    Chapter  Google Scholar 

  45. Nyberg, K., Knudsen, L.R.: Provable security against a differential attack. J. Cryptol. 8(1), 27–37 (1995)

    Article  MathSciNet  Google Scholar 

  46. Park, S., Sung, S.H., Lee, S., Lim, J.: Improving the upper bound on the maximum differential and the maximum linear hull probability for SPN structures and AES. In: Johansson, T. (ed.) FSE 2003. LNCS, vol. 2887, pp. 247–260. Springer, Heidelberg (2003). https://doi.org/10.1007/978-3-540-39887-5_19

    Chapter  Google Scholar 

  47. Rothaus, O.S.: On ‘bent’ functions. J. Comb. Theory Ser. A 20(3), 300–305 (1976)

    Article  Google Scholar 

  48. Tessaro, S.: Optimally secure block ciphers from ideal primitives. In: Iwata, T., Cheon, J.H. (eds.) ASIACRYPT 2015. LNCS, vol. 9453, pp. 437–462. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-48800-3_18

    Chapter  Google Scholar 

  49. Tessaro, S.: Optimally secure block ciphers from ideal primitives. Cryptology ePrint Archive, Report 2015/868 (2015). http://eprint.iacr.org/2015/868

  50. Todo, Y., Leander, G., Sasaki, Y.: Nonlinear invariant attack. In: Cheon, J.H., Takagi, T. (eds.) ASIACRYPT 2016. LNCS, vol. 10032, pp. 3–33. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-53890-6_1

    Chapter  Google Scholar 

  51. Vaudenay, S.: Provable security for block ciphers by decorrelation. In: Morvan, M., Meinel, C., Krob, D. (eds.) STACS 1998. LNCS, vol. 1373, pp. 249–275. Springer, Heidelberg (1998). https://doi.org/10.1007/BFb0028566

    Chapter  Google Scholar 

  52. Vaudenay, S.: The end of encryption based on card shuffling. CRYPTO 2012 Rump Session (2012). crypto.2012.rump.cr.yp.to

Download references

Acknowledgments

We would like to thank the anonymous reviewers and Christof Beierle for their helpful comments, and Lucas Hartmann for the artistic design of bison.

Author information

Authors and Affiliations

  1. Inria, Paris, France

    Anne Canteaut

  2. Horst Görtz Institute for IT-Security, Ruhr University Bochum, Bochum, Germany

    Virginie Lallemand, Gregor Leander, Patrick Neumann & Friedrich Wiemer

Authors
  1. Anne Canteaut
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Virginie Lallemand
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Gregor Leander
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Patrick Neumann
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Friedrich Wiemer
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Friedrich Wiemer .

Editor information

Editors and Affiliations

  1. Technion, Haifa, Israel

    Yuval Ishai

  2. COSIC Group, KU Leuven, Heverlee, Belgium

    Vincent Rijmen

Rights and permissions

Reprints and permissions

Copyright information

© 2019 International Association for Cryptologic Research

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Canteaut, A., Lallemand, V., Leander, G., Neumann, P., Wiemer, F. (2019). bison Instantiating the Whitened Swap-Or-Not Construction. In: Ishai, Y., Rijmen, V. (eds) Advances in Cryptology – EUROCRYPT 2019. EUROCRYPT 2019. Lecture Notes in Computer Science(), vol 11478. Springer, Cham. https://doi.org/10.1007/978-3-030-17659-4_20

Download citation

  • DOI: https://doi.org/10.1007/978-3-030-17659-4_20

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-030-17658-7

  • Online ISBN: 978-3-030-17659-4

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Societies and partnerships