Skip to main content

Advertisement

Springer Nature Link
Log in

Troika: a ternary cryptographic hash function

  • Published:
Designs, Codes and Cryptography Aims and scope Submit manuscript

Abstract

Linear codes over finite fields are one of the most well-studied areas in coding theory. While codes over finite fields of characteristic two are of particular practical interest due to their good implementation properties, ternary codes have been extensively studied as well. By contrast, there has been essentially no research into ternary cryptographic algorithms. The only exception to date is a cryptocurrency and distributed ledger technology called IOTA which is ternary and has been designed primarily for use in the Internet of Things. Its security depends on using a secure cryptographic hash function over \(\mathbb {F}_{3}\). With all existing hash designs being binary, a ternary prototype called Curl-P had been developed, however was found to admit practical collision attacks. A ternary adaption of SHA-3 called Kerl is currently used instead, but comparatively inefficient. In this paper, we propose a new ternary hash function called Troika which is tailored for use in IOTA’s ternary distributed ledger and can be used as a drop-in replacement for Kerl. The design of Troika leverages elements from the well-established Keccak and Rijndael design philosophies, while being designed for efficiency in terms of basic \(\mathbb {F}_{3}\) operations. In particular, it features a novel 3-trit S-box which is differentially 3-uniform while being implementable in only 7 additions and multiplications over \(\mathbb {F}_{3}\). Troika is designed to offer a security level comparable to SHA-3. It is expected that Troika, as part of IOTA’s distributed ledger, will find widespread commercial real-world use in the near- to mid-term future. We believe that not the least due to its unorthodox ternary design, it will provide both a practically relevant and interesting target for further cryptanalysis.

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

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2

Similar content being viewed by others

References

  1. 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) Advances in Cryptology—CRYPTO 2017—37th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 20–24, 2017, Proceedings, Part II, vol. 10402. Lecture Notes in Computer Science, pp. 647–678. Springer, New York (2017).

    Chapter  Google Scholar 

  2. Bertoni G., Daemen J., Peeters M., Van Assche G.: On the indifferentiability of the Sponge construction. In: Smart, Nigel P. (ed.) EUROCRYPT. Lecture Notes in Computer Science, vol. 4965, pp. 181–197. Springer, New York (2008).

    Chapter  Google Scholar 

  3. Bertoni G., Daemen J., Peeters M., Van Assche G.: Keccak sponge function family main document. Submission to NIST SHA-3 competition (Round 3). http://keccak.noekeon.org/ (2011).

  4. Bertoni G., Daemen J., Peeters M., Van Assche G.: Duplexing the sponge: single-pass authenticated encryption and other applications. In: Miri A, Vaudenay S, (eds.) Selected areas in cryptography—18th International Workshop, SAC 2011, Toronto, ON, Canada, August 11–12, 2011, Revised Selected Papers. Lecture Notes in Computer Science, vol. 7118, pp. 320–337. Springer, New York (2011).

    Chapter  Google Scholar 

  5. Bertoni G., Daemen J., Peeters M., Van Assche G.: Cryptographic sponge functions, version 0.1. https://keccak.team/files/CSF-0.1.pdf (2011).

  6. Bertoni G., Daemen J., Peeters M., Van Assche G.: The Keccak reference, version 3.0. Submission to NIST (SHA-3 competition, final round) (2011).

  7. Biham E., Shamir A.: Differential cryptanalysis of DES-like cryptosystems. J. Cryptol. 4(1), 3–72 (1991).

    Article  MathSciNet  Google Scholar 

  8. Biryukov A., Wagner D.A.: Slide attacks. In: Knudsen, L.R., (eds.) Fast Software Encryption, 6th International Workshop, FSE ’99, Rome, Italy, March 24–26, 1999, Proceedings. Lecture Notes in Computer Science, vol. 1636, pp. 245–259. Springer, New York (1999).

  9. Bogdanov A., Knudsen L., Leander G., Paar C., Poschmann A., Robshaw M.J.B., Seurin Y., Vikkelsoe C.: PRESENT: an ultra-lightweight block cipher. In: Paillier P., Verbauwhede I., (eds.) CHES. Lecture Notes in Computer Science, vol. 4727, pp. 450–466. Springer, New York (2007).

  10. Chen G., Li R.: Ternary self-orthogonal codes of dual distance three and ternary quantum codes of distance three. Des. Codes Cryptogr. 69(1), 53–63 (2013).

    Article  MathSciNet  Google Scholar 

  11. Daemen J.: Cipher and hash function design strategies based on linear and differential cryptanalysis. PhD thesis, Katholieke Universiteit Leuven, Leuven, Belgium (1995)

  12. Daemen J., Rijmen V.: The Design of Rijndael: AES—The Advanced Encryption Standard. Springer, New York (2002).

    Book  Google Scholar 

  13. Daemen J., Knudsen L.R., Rijmen V.: Linear frameworks for block ciphers. Des. Codes Cryptogr. 22(1), 65–87 (2001).

    Article  MathSciNet  Google Scholar 

  14. Gauravaram P., Knudsen L.R., Matusiewicz K., Mendel F., Rechberger C., Schläffer M., Thomsen S.S.: Grøstl—a SHA-3 candidate. Submission to NIST (SHA-3 competition, final round) (2011).

  15. Granboulan L., Levieil É., Piret G.: Pseudorandom permutation families over abelian groups. In: Robshaw M.J.B. (ed.) Fast Software Encryption, 13th International Workshop, FSE 2006, Graz, Austria, March 15–17, 2006, Revised Selected Papers. Lecture Notes in Computer Science, vol. 4047, pp. 57–77. Springer, New York (2006).

    Chapter  Google Scholar 

  16. Greenough P.P., Hill R.: Optimal ternary quasi-cyclic codes. Des. Codes Cryptogr. 2(1), 81–91 (1992).

    Article  MathSciNet  Google Scholar 

  17. Heilman E., Narula N., Tanzer G., Lovejoy J., Colavita M., Virza M., Dryja T.: Cryptanalysis of Curl-P and Other Attacks on the IOTA Cryptocurrency. BlackHat, USA 2018 (2018).

  18. Helleseth T., Kholosha A.: New ternary binomial bent functions. In: IEEE International Symposium on Information Theory, ISIT 2016, Barcelona, Spain, July 10–15, 2016, pp. 101–104. IEEE (2016).

  19. Hill R., Newton D.E.: Optimal ternary linear codes. Des. Codes Cryptogr. 2(2), 137–157 (1992).

    Article  MathSciNet  Google Scholar 

  20. Hong D., Lee J.-K., Kim D.-C., Kwon D., Ryu K.H., Lee D.: LEA: a 128-bit block cipher for fast encryption on common processors. In: Kim Y., Lee H., Perrig A. (eds.) Information Security Applications—14th International Workshop, WISA 2013, Jeju Island, Korea, August 19–21, 2013, Revised Selected Papers. Lecture Notes in Computer Science, vol. 8267, pp. 3–27. Springer, New York (2013).

  21. Hong D., Sung J., Hong S., Lim J., Lee S., Koo B., Lee C., Chang D., Lee J., Jeong K., Kim H., Kim J., Chee S.: HIGHT: A new block cipher suitable for low-resource device. In: Goubin L., Matsui M. (eds.) Cryptographic Hardware and Embedded Systems—CHES 2006, 8th International Workshop, Yokohama, Japan, October 10–13, 2006, Proceedings. Lecture Notes in Computer Science, , vol. 4249, pp. 46–59. Springer, New York (2006).

    Google Scholar 

  22. Kölbl S.: CryptoSMT: an easy to use tool for cryptanalysis of symmetric primitives. https://github.com/kste/cryptosmt.

  23. Leander G., Abdelraheem M.A., AlKhzaimi H., Zenner E.: A cryptanalysis of printcipher: the invariant subspace attack. In: Rogaway P. (ed.) Advances in Cryptology—CRYPTO 2011—31st Annual Cryptology Conference, Santa Barbara, CA, USA, August 14–18, 2011. Proceedings. Lecture Notes in Computer Science, vol. 6841, pp. 206–221. Springer, New York (2011).

    Chapter  Google Scholar 

  24. Lidl R., Niederreiter H.: Introduction to Finite Fields and Their Applications. Cambridge University Press, revised edition (1994).

  25. MacWilliams F.J., Sloane N.J.A.: The Theory of Error-Correcting Codes, 2nd edn. North-holland Publishing Company, Amsterdam (1978).

    MATH  Google Scholar 

  26. Matsui M.: Linear cryptoanalysis method for DES cipher. In: Helleseth T. (ed.) EUROCRYPT. Lecture Notes in Computer Science, vol. 765, pp. 386–397. Springer, New York (1993).

  27. Matsui M.: The first experimental cryptanalysis of the Data Encryption Standard. In: Desmedt Y. (ed.) CRYPTO. Lecture Notes in Computer Science, vol. 839, pp. 1–11. Springer, New York (1994).

    Google Scholar 

  28. Mella S., Daemen J., Van Assche G.: New techniques for trail bounds and application to differential trails in keccak. IACR Trans. Symmetric Cryptol. 2017(1), 329–357 (2017).

    Google Scholar 

  29. Morrison K.E.: Random maps and permutations. Technical report, California Polytechnic State University, San Luis Obispo (1998).

  30. Ness G.J., Helleseth T.: A new family of ternary almost perfect nonlinear mappings. IEEE Trans. Inf. Theory 53(7), 2581–2586 (2007).

    Article  MathSciNet  Google Scholar 

  31. Rijmen V.: Cryptanalysis and design of iterated block ciphers. PhD thesis, Katholieke Universiteit Leuven, Leuven, Belgium (1997).

  32. Shibutani K., Isobe T., Hiwatari H., Mitsuda A., Akishita T., Shirai T.: Piccolo: an ultra-lightweight blockcipher. In: Preneel B., Takagi T. (eds.) CHES. Lecture Notes in Computer Science, vol. 6917, pp. 342–357. Springer, New York (2011).

    Chapter  Google Scholar 

  33. Shirai T., Shibutani K., Akishita T., Moriai S., Iwata T.: The 128-bit blockcipher CLEFIA (extended abstract). In: Biryukov A. (ed.) FSE. Lecture Notes in Computer Science, vol. 4593, pp. 181–195. Springer, New York (2007).

    Chapter  Google Scholar 

  34. Stoffelen K., Daemen J.: Column parity mixers. IACR Trans. Symmetric Cryptol. 2018(1), 126–159 (2018).

    Google Scholar 

  35. Todo Y., Leander G., Sasaki Y.: Nonlinear invariant attack—practical attack on full scream, iscream, and midori64. In: Cheon J.H., Takagi T. (eds.) Advances in Cryptology—ASIACRYPT 2016—22nd International Conference on the Theory and Application of Cryptology and Information Security, Hanoi, Vietnam, December 4–8, 2016, Proceedings, Part II. Lecture Notes in Computer Science, vol. 10032, pp. 3–33 (2016).

  36. Wei Y., Ye T., Wu W., Pasalic E.: Generalized nonlinear invariant attack and a new design criterion for round constants. IACR Transactions on Symmetric Cryptology, 2018(4), to appear (2019).

  37. Zhou Z.: Three-weight ternary linear codes from a family of cyclic difference sets. Des. Codes Cryptogr. 86(11), 2513–2523 (2018).

    Article  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Cybercrypt A/S, Copenhagen, Denmark

    Stefan Kölbl & Elmar Tischhauser

  2. IRISA, Rennes, France

    Patrick Derbez

  3. Technical University of Denmark, Lyngby, Denmark

    Andrey Bogdanov

Authors
  1. Stefan Kölbl
    View author publications

    You can also search for this author inPubMed Google Scholar

  2. Elmar Tischhauser
    View author publications

    You can also search for this author inPubMed Google Scholar

  3. Patrick Derbez
    View author publications

    You can also search for this author inPubMed Google Scholar

  4. Andrey Bogdanov
    View author publications

    You can also search for this author inPubMed Google Scholar

Corresponding author

Correspondence to Elmar Tischhauser.

Additional information

Communicated by L. Knudsen.

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Appendices

A Illustration of the state layout of Troika

Fig. 3
figure 3

Illustration of the nomenclature for different parts of the state of Troika

Full size image
Fig. 4
figure 4

Illustration of the rate (orange) and capacity (white) parts of the state of Troika

Full size image

B Test vectors

Table 8 Test vectors for Troika
Full size table

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Kölbl, S., Tischhauser, E., Derbez, P. et al. Troika: a ternary cryptographic hash function. Des. Codes Cryptogr. 88, 91–117 (2020). https://doi.org/10.1007/s10623-019-00673-2

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10623-019-00673-2

Keywords

Mathematics Subject Classification