Rad HAZU, Matematičke znanosti, Vol. 25 (2021), 51-77.

ON WEAK ROTORS, LATIN SQUARES, LINEAR ALGEBRAIC REPRESENTATIONS, INVARIANT DIFFERENTIALS AND CRYPTANALYSIS OF ENIGMA

Nicolas T. Courtois, Marek Grajek and Michal Rams

University College London, Gower Street, London, UK
e-mail: n.courtois@ucl.ac.uk

Independent expert on crypto history, Grodzisk Mazowiecki, Poland
e-mail: mjg@interia.eu

Institute of Mathematics, Polish Academy of Sciences, Warsaw, Poland
e-mail: rams@impan.pl

Abstract.   Since the 1920s until today it was assumed that rotors in Enigma cipher machines do not have a particular weakness or structure. A curious situation compared to hundreds of papers about S-boxes and weak setup in block ciphers. In this paper we reflect on what is normal and what is not normal for a cipher machine rotor, with a reference point being a truly random permutation. Our research shows that most original wartime Enigma rotors ever made are not at all random permutations and conceal strong differential properties invariant by rotor rotation. We also exhibit linear/algebraic properties pertaining to the ring of integers modulo 26. Some rotors are imitating a certain construction of a perfect quasigroup which however only works when N is odd. Most other rotors are simply trying to approximate the ideal situation. To the best of our knowledge these facts are new and were not studied before 2020.

2020 Mathematics Subject Classification.   94A60, 68P25, 20N05, 05B15, 13A50.

Key words and phrases.   Enigma, block ciphers, linear cryptanalysis, differential cryptanalysis, weak keys, Latin squares, algebraic representation, quasigroups, Turing-Welchman attack.

Full text (PDF) (free access)

DOI: https://doi.org/10.21857/y26kec4k89

References:

  1. A. Albertini, J.-P. Aumasson, M. Eichlseder, F. Mendel and M. Schläffer, Malicious hashing: Eve's variant of SHA-1, in: Selected Areas in Cryptography - SAC 2014, Lecture Notes in Comput. Sci. 8781, Springer, Cham, 2014. pp. 1-19.
    MathSciNet     CrossRef

  2. D. Alvarez, Wilhelm Fenner and the development of the German Cipher Bureau, 1922-1939, Cryptologia 31 (2007), 152-163.
    CrossRef

  3. G. V. Bard, S. V. Ault and N. T. Courtois, Statistics of random permutations and the cryptanalysis of periodic block ciphers, Cryptologia 36 (2012), 240-262.
    CrossRef

  4. M. Batey, Dilly Knox - A reminiscence of this pioneer Enigma cryptanalyst, Cryptologia 32 (2008), 104-130.
    CrossRef

  5. F. L. Bauer, Decrypted Secrets: Methods and Maxims of Cryptology, Springer, Berlin, 2006.
    MathSciNet

  6. L. P. Brown, Analysis of the DES and the Design of the LOKI Encryption Scheme, PhD Thesis, Dept. Computer Science, UC UNSW, ADFA, Canberra, 1991.

  7. M. Calderini, A note on some algebraic trapdoors for block ciphers, Adv. Math. Commun. 12 (2018), 515-524.
    MathSciNet     CrossRef

  8. N. T. Courtois, Si seulement Enigma tournait moins vite, ou cryptanalyse d'Enigma avec un rotor faible, Bulletin de l'Association des Réservistes du Chiffre et de la Séécurité de l'Information, 46 (2020), 79-90.

  9. N. T. Courtois, Student exercises about breaking Enigma, updated March 2020, taught at University College London in 2020 as a part of COMP0058 Allied Cryptography and Cryptanalysis course,
    http://www.nicolascourtois.com/teach/Exos_Engima_0058.pdf.

  10. N. Courtois, Algebraic Complexity Reduction and Cryptanalysis of GOST, Monograph study on GOST cipher, 224 pages, available at https://ia.cr/2011/626.

  11. N. Courtois and J. Pieprzyk, Cryptanalysis of block ciphers with overdefined systems of equations, in: in: Advances in Cryptology -- ASIACRYPT 2002, Lecture Notes in Comput. Sci. 2501, Springer, Berlin, 2002. pp. 267-287.
    MathSciNet     CrossRef

  12. N. T. Courtois and A. Patrick, Lack of unique factorization as a tool in block cipher cryptanalysis, Preprint, https://arxiv.org/abs/1905.04684, submitted 12 May 2019.

  13. N. T. Courtois, On the existence of non-linear invariants and algebraic polynomial constructive approach to backdoors in block ciphers, https://ia.cr/2018/807, last revised 27 Mar 2019.

  14. N. T. Courtois, A nonlinear invariant attack on T-310 with the original Boolean function, Cryptologia 45 (2021), 178-192.
    CrossRef

  15. N. Courtois, The inverse S-box, non-linear polynomial relations and cryptanalysis of block ciphers, in: Advanced Encryption Standard - AES, Lecture Notes in Comput. Sci. 3373, Springer, Berlin, 2005, pp. 170-188.
    CrossRef

  16. N. Courtois, Feistel schemes and bi-linear cryptanalysis, in: Advances in Cryptology - CRYPTO 2004, Lecture Notes in Comput. Sci. 3152, Springer, Berlin, 2004. pp. 23-40.
    MathSciNet     CrossRef

  17. N. T. Courtois, K. Schmeh, J. Drobick, J. Patarin, M.-B. Oprisanu, M. Scarlata and O. Bhallamudi, Cryptographic Security Analysis of T-310, Monography study on the T-310 block cipher, 132 pages, received 20 May 2017, last revised 29 June 2018,
    https://ia.cr/2017/440.pdf.

  18. N. Courtois, 100 years of Cryptanalysis: Compositions of Permutations, slides about cryptanalysis of Engima and block cipher cryptanalysis, used teaching GA18 Cryptanalysis course at University College London 2014-2016,
    http://www.nicolascourtois.com/papers/code_breakers_enigma_block_teach.pdf.

  19. N. Courtois, M.-B. Oprisanu and K. Schmeh, Linear cryptanalysis and block cipher design in East Germany in the 1970s, Cryptologia 43 (2019), 2-22.
    CrossRef

  20. N. Courtois and J. Pieprzyk, Cryptanalysis of block ciphers with overdefined systems of equations, in: Advances in Cryptology - ASIACRYPT 2002, Lecture Notes in Comput. Sci. 2501, Springer, Berlin, 2002. pp. 267-287.
    MathSciNet     CrossRef

  21. N. T. Courtois, Invariant hopping attacks on block ciphers, presented at WCC’2019, Abbaye de Saint-Jacut de la Mer, France, 31 March - 5 April 2019.
    Extended version available at https://arxiv.org/pdf/2002.03212.pdf, 8 February 2020.

  22. N. Courtois, G. Castagnos and L. Goubin, What do DES S-boxes say to each other?, Available on https://ia.cr/2003/184/.

  23. N. Courtois, The best differential characteristics and subtleties of the Biham-Shamir attacks on DES, Available on https://ia.cr/2005/202.
    MathSciNet     CrossRef

  24. N. T. Courtois, T. Mourouzis, M. Misztal, J.-J. Quisquater and G. Song, Can GOST be made secure against differential cryptanalysis?, Cryptologia 39 (2015), 145-156.
    CrossRef

  25. N. T. Courtois and J.-J. Quisquater, Can a differential attack work for an arbitrarily large number of rounds?, in: Information Security and Cryptology - ICISC 2020, Lecture Notes in Comput. Sci. 12593, Springer, Cham, 2021, pp. 157-181.
    CrossRef

  26. C. Eyraud, Précis de Cryptographie Moderne, Editions Raoul Tari, Paris, 1st edition 1953, 2nd edition 1959.

  27. P. Flajolet and R. Sedgewick, Analytic Combinatorics, Cambridge University Press, Cambridge, 2009.
    MathSciNet     CrossRef

  28. J. R. S. Fuensanta, F. J. López-Brea Espiau, and F. Weierud, Spanish Enigma: A history of the Enigma in Spain, Cryptologia 34 (2010), 301-328.
    CrossRef

  29. J. J. Gillogly, Ciphertext-only cryptanalysis of Enigma, Cryptologia 19 (1995), 405-413.
    CrossRef

  30. I. J. Good and C. A. Deavours, Afterword to: Marian Rejewski, "How Polish mathematicians deciphered the Enigma", Annals of the History of Computing 3 (3) (1981), 229-232.

  31. C. Jennings, The Third Reich is Listening: Inside German codebreaking 1939-45, Osprey Publishing, Oxford, 2018.

  32. D. Kahn, How I discovered World War II's greatest spy, Cryptologia 34 (2009), 12-21.
    CrossRef

  33. P. Morawiecki, Malicious Keccak, https://ia.cr/2015/1085.

  34. T. Peyrin and H. Wang, The MALICIOUS framework: Embedding backdoors into tweakable block ciphers, in: Advances in Cryptology - CRYPTO 2020, Lecture Notes in Comput. Sci. 12172, Springer, Cham, pp. 249-278.
    CrossRef

  35. K. Pommerening, Permutations and Rejewski’s Theorem,
    https://www.staff.unimainz.de/pommeren/MathMisc/Permut.pdf.

  36. S. Ree, Choi Seokjeong and traditional Asian mathematics, Confucian scholar's discovery predates the work of Euler, In page 3 of Math & Presso, Daily News of the Congress, No 3, Friday 15 August 2014, printed and edited by Korea JoongAng Daily newspaper, publication commissioned by the International Congress of Mathematicians, ICM 2014, Seoul, Korea. Available on http://www.icm2014.org/download/MP0815.pdf.

  37. M. Rejewski, H. Zygalski and other undisclosed authors, Kurzgefasste Darstellung der Auflösungsmethoden, Bertrand archives, Service Historique de la Défense, Vincennes, France, DE 2016 ZB 25/6, Dossiers Nos. 281 and 282, ca. 1940.

  38. M. Rejewski, Memories of My Work at the Cipher Bureau of the General Staff Second Department 1930-45, second edition, Adam Mickiewicz University Press, Poznan, 2011.

  39. Random Permutation Statistics, Wikipedia article, consulted 14 March 2020, available at http://en.wikipedia.org/wiki/Random_permutation_statistics.

  40. A. Turing, Mathematical Theory of ENIGMA Machine, UK national archives, c. 1940.

  41. D. Turing with help of D. Kenyon, The Bombe Breakthrough, blue guide book, sold by Bletchley Park trust, 96 pages, 2018.

  42. H. Ulbricht, Die Chiffriermaschine ENIGMA, Trügerische Sicherheit, Ein Beitrag zur Geschichte der Nachrichtendienste, PhD thesis, Technische Universität Braunschweig, 14 April 2005.

Rad HAZU Home Page