computer science

Integral cryptanalysis

Integral cryptanalysis is a computer science topic covered in the lgStudy science library. This page brings together a partial reference excerpt, illustrations, worked examples, real-world applications and a short study plan, so you can understand Integral cryptanalysis rather than just read about it. In short: In cryptography, integral cryptanalysis is a cryptanalytic attack that is particularly applicable to block ciphers based on substitution–permutation networks. It was originally designed by Lars Knudsen as a dedicated attack against Square, so it is commonly known as the Square attack.

Key takeaways

Integral cryptanalysis belongs to computer science; place it in that map before memorising details.
Learn the definition first, then one example that makes the definition concrete.
Connect Integral cryptanalysis to a quantity you can measure, compute or draw — that is where exam questions come from.
Reproduce the core statement of Integral cryptanalysis from memory before moving on to harder problems.

Reference excerpt

In cryptography, integral cryptanalysis is a cryptanalytic attack that is particularly applicable to block ciphers based on substitution–permutation networks. It was originally designed by Lars Knudsen as a dedicated attack against Square, so it is commonly known as the Square attack. It was also extended to a few other ciphers related to Square: CRYPTON, Rijndael, and SHARK. Stefan Lucks generalized the attack to what he called a saturation attack and used it to attack Twofish, which is not at all similar to Square, having a radically different Feistel network structure. Forms of integral cryptanalysis have since been applied to a variety of ciphers, including Hierocrypt, IDEA, Camellia, Skipjack, MISTY1, MISTY2, SAFER++, KHAZAD, and FOX (now called IDEA NXT). Unlike differential cryptanalysis, which uses pairs of chosen plaintexts with a fixed XOR difference, integral cryptanalysis uses sets or even multisets of chosen plaintexts of which part is held constant, and another part varies through all possibilities. For example, an attack might use 256 chosen plaintexts that have all but 8 of their bits the same, but all differ in those 8 bits. Such a set necessarily has an XOR sum of 0, and the XOR sums of the corresponding sets of ciphertexts provide information about the cipher's operation. This contrast between the differences of pairs of texts and the sums of larger sets of texts inspired the name "integral cryptanalysis", borrowing the terminology of calculus.

References Joan Daemen, Lars Knudsen, Vincent Rijmen (January 1997). The Block Cipher Square (PDF). 4th International Workshop on Fast Software Encryption (FSE '97), Volume 1267 of Lecture Notes in Computer Science. Haifa: Springer-Verlag. pp. 149–165. Retrieved 2007-02-15.{{cite conference}}: CS1 maint: multiple names: authors list (link) Carl D'Halluin, Gert Bijnens, Vincent Rijmen, Bart Preneel (March 1999). Attack on Six Rounds of Crypton (PDF/PostScript). 6th International Workshop on Fast Software Encryption (FSE '99). Rome: Springer-Verlag. pp. 46–59. Retrieved 2007-03-03.{{cite conference}}: CS1 maint: miscellaneous url (link) CS1 maint: multiple names: authors list (link) N. Ferguson, J. Kelsey, S. Lucks, B. Schneier, M. Stay, D. Wagner, D. Whiting (April 2000). Improved Cryptanalysis of Rijndael (PDF/PostScript). 7th International Workshop on Fast Software Encryption (FSE 2000). New York City: Springer-Verlag. pp. 213–230. Retrieved 2007-03-06.{{cite conference}}: CS1 maint: multiple names: authors list (link) Stefan Lucks (September 14, 2000). The Saturation Attack - a Bait for Twofish (PDF/PostScript). 8th International Workshop on Fast Software Encryption (FSE '01). Yokohama: Springer-Verlag. pp. 1–15. Retrieved 2006-11-30. Paulo S. L. M. Barreto, Vincent Rijmen, Jorge Nakahara, Jr., Bart Preneel, Joos Vandewalle, Hae Yong Kim (April 2001). Improved SQUARE Attacks against Reduced-Round HIEROCRYPT (PDF). 8th International Workshop on Fast Software Encryption (FSE '01). Yokohama: Springer-Verlag. pp. 165–173. Retrieved 2007-03-03.{{cite conference}}: CS1 maint: multiple names: authors list (link) Jorge Nakahara, Jr.; Paulo S.L.M. Barreto; Bart Preneel; Joos Vandewalle; Hae Y. Kim (2001). "SQUARE Attacks on Reduced-Round PES and IDEA Block Ciphers" (PDF/PostScript). Retrieved 2007-03-03. {{cite journal}}: Cite journal requires |journal= (help)CS1 maint: miscellaneous url (link) Yongjin Yeom; Sangwoo Park; Iljun Kim (February 2002). On the Security of CAMELLIA against the Square Attack (PDF). 9th International Workshop on Fast Software Encryption (FSE '02). Leuven: Springer-Verlag. pp. 89–99. Retrieved 2007-03-03. Kyungdeok Hwang; Wonil Lee; Sungjae Lee; Sangjin Lee; Jongin Lim (February 2002). Saturation Attacks on Reduced Round Skipjack. 9th International Workshop on Fast Software Encryption (FSE '02). Leuven: Springer-Verlag. pp. 100–111. Archived from the original (PDF) on 2007-05-25. Retrieved 2007-03-03. Lars Knudsen; David Wagner (December 11, 2001). Integral cryptanalysis (PDF/PostScript). 9th International Workshop on Fast Software Encryption (FSE '02). Leuven: Springer-Verlag. pp. 112–127. Retrieved 2006-11-30. Gilles Piret, Jean-Jacques Quisquater (February 16, 2003). "Integral Cryptanalysis on reduced-round Safer++" (PDF/PostScript). Retrieved 2007-03-03. {{cite journal}}: Cite journal requires |journal= (help)CS1 maint: miscellaneous url (link) Frédéric Muller (December 2003). A New Attack against Khazad (PDF). Advances in Cryptology – ASIACRYPT 2003. Taipei: Springer-Verlag. pp. 347–358. Retrieved 2007-03-03.{{cite conference}}: CS1 maint: deprecated archival service (link) Wu Wenling; Zhang Wentao; Feng Dengguo (August 25, 2005). "Improved Integral Cryptanalysis of FOX Block Cipher" (PDF). Retrieved 2007-03-03. {{cite journal}}: Cite journal requires |journal= (help)

Worked examples

Example 1 — a first encounter with Integral cryptanalysis

Start with the simplest possible case. Write down what Integral cryptanalysis claims or describes in one sentence, then invent the smallest concrete situation in which that sentence is true. In computer science, the smallest case is usually a single object, a single equation or a single measurement. Check that every symbol or term in your sentence has a meaning in that case.

Example 2 — changing one variable

Take the situation from Example 1 and change exactly one quantity: double it, halve it, or set it to zero. Predict what should happen to Integral cryptanalysis before you calculate. Comparing your prediction with the result is the fastest way to find out whether you understand the idea or only the words.

Example 3 — an exam-style question

Typical questions about Integral cryptanalysis ask you to (a) state it precisely, (b) apply it to given data, and (c) explain a limitation. Practise writing all three answers in under five minutes; the third part is what separates a full-mark answer from an average one.

Applications of Integral cryptanalysis

In research: Integral cryptanalysis appears in computer science research whenever the underlying quantities have to be modelled precisely. Papers usually cite it as a starting assumption and then explore where it breaks down.
In technology and industry: Engineering practice reuses Integral cryptanalysis in design rules, simulations and safety margins. Knowing the idea lets you read a specification sheet and understand why the numbers look the way they do.
In the classroom: Integral cryptanalysis is common in secondary-school and first-year university syllabi. It links to neighbouring topics Cryptographic attacks, so understanding it makes those chapters shorter.
In everyday life: Look for Integral cryptanalysis outside the textbook — in sport, cooking, traffic, electronics or the sky above you. An example you found yourself is remembered far longer than one you were given.

Affiliate

Preply — study more efficiently by working with a personal tutor. 50% off.

How to study Integral cryptanalysis in 20 minutes

Read the reference excerpt below once, without taking notes.
Close the page and write down what Integral cryptanalysis means in your own words.
Compare your version with the excerpt and mark what you missed.
Work through the three examples above with pen and paper.
Explain Integral cryptanalysis out loud to somebody else — or to Teacher Smith in the lgStudy chat.

Frequently asked questions

What is Integral cryptanalysis in simple terms?

Why does Integral cryptanalysis matter?

Because it connects several computer science ideas at once: it gives you a definition you can apply, a quantity you can calculate, and a way to check whether a result is plausible.

How should I study Integral cryptanalysis?

Read the excerpt, restate it from memory, then work through the examples and applications listed on this page. The five-step study plan above takes about twenty minutes.

What does this page cover?

It gives you a compact reference excerpt plus original lgStudy explanations, examples, applications and study material on Integral cryptanalysis.