3.1. As stated in Sect. 3.5.2, one important property which makes DES secure is that the S-boxes are nonlinear. In this problem we verify this property by computing the output of S₁ for several pairs of inputs. Show that S₁ (x₁) S1 (x2) ‡ S₁ (x1 x2), where "" denotes bitwise XOR, for: 1. x₁ = 000000, x₂ = 000001 2. x₁ = 111111, x₂ = 100000 3. x₁ = = 101010, x2 = 010101
3.1. As stated in Sect. 3.5.2, one important property which makes DES secure is that the S-boxes are nonlinear. In this problem we verify this property by computing the output of S₁ for several pairs of inputs. Show that S₁ (x₁) S1 (x2) ‡ S₁ (x1 x2), where "" denotes bitwise XOR, for: 1. x₁ = 000000, x₂ = 000001 2. x₁ = 111111, x₂ = 100000 3. x₁ = = 101010, x2 = 010101
Database System Concepts
7th Edition
ISBN:9780078022159
Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Chapter1: Introduction
Section: Chapter Questions
Problem 1PE
Related questions
Question
![3.5.2 Analytical Attacks
As was shown in the first chapter, analytical attacks can be very powerful. Since
the introduction of DES in the mid-1970s, many excellent researchers in academia
(and without doubt many excellent researchers in intelligence agencies) tried to find
weaknesses in the structure of DES which allowed them to break the cipher. It is
a major triumph for the designers of DES that no weakness was found until 1990.
In this year, Eli Biham and Adi Shamir discovered what is called differential crypt-
analysis (DC). This is a powerful attack which is in principle applicable to any block
cipher. However, it turned out that the DES S-boxes are particularly resistant against
this attack. In fact, one member of the original IBM design team declared after the
discovery of DC that they had been aware of the attack at the time of design. Al-
legedly, the reason why the S-box design criteria were not made public was that the
design team did not want to make such a powerful attack public. If this claim is true
and all circumstances support it - it means that the IBM and NSA team was
15
years ahead of the research community. It should be noted, however, that in the
1970s and 1980s relatively few people did active research in cryptography.
In 1993 a related but distinct analytical attack was published by Mitsuru Matsui,
which was named linear cryptanalysis (LC). Similar to differential cryptanalysis,
the effectiveness of this attack also heavily depends on the structure of the S-boxes.
What is the practical relevance of these two analytical attacks against DES? It
turns out that an attacker needs 247 plaintext-ciphertext pairs for a successful DC
attack. This assumes particularly chosen plaintext blocks; for random plaintext 255
pairs are needed! In the case of LC, an attacker needs 243 plaintext-ciphertext pairs.
All these numbers seem highly impractical for several reasons. First, an attacker
needs to know an extremely large number of plaintexts, i.e., pieces of data which
are supposedly encrypted and thus hidden from the attacker. Second, collecting and
storing such an amount of data takes a long time and requires considerable memory
resources. Third, the attack only recovers one key. (This is actually one of many
arguments for introducing key freshness in cryptographic applications.) As a result
of all these arguments, it does not seem likely that DES can be broken with either
DC or LC in real-world systems. However, both DC and LC are very powerful
attacks which are applicable to many other block ciphers. Table 3.13 provides an
overview of proposed and realized attacks against DES over the last three decades.
Some entries refer to what is known as the DES Challenges. Starting in 1997, several
DES-breaking challenges were organized by the company RSA Security.
3.1. As stated in Sect. 3.5.2, one important property which makes DES secure is that
the S-boxes are nonlinear. In this problem we verify this property by computing the
output of S₁ for several pairs of inputs.
Show that S₁ (x₁) © S₁ (x2) ‡ S₁ (x1 © x2), where “” denotes bitwise XOR, for:
1. x₁ = 000000, x2 = 000001
2. x₁ = 111111, x₂ = 100000
3. x₁ = 101010, x₂
= = 010101](/v2/_next/image?url=https%3A%2F%2Fcontent.bartleby.com%2Fqna-images%2Fquestion%2F2dde791b-4e50-43ae-95b2-a5c8fabc78e8%2Fb00deec7-d3ec-45dd-8acd-018df7c17358%2F2pvtb98_processed.png&w=3840&q=75)
Transcribed Image Text:3.5.2 Analytical Attacks
As was shown in the first chapter, analytical attacks can be very powerful. Since
the introduction of DES in the mid-1970s, many excellent researchers in academia
(and without doubt many excellent researchers in intelligence agencies) tried to find
weaknesses in the structure of DES which allowed them to break the cipher. It is
a major triumph for the designers of DES that no weakness was found until 1990.
In this year, Eli Biham and Adi Shamir discovered what is called differential crypt-
analysis (DC). This is a powerful attack which is in principle applicable to any block
cipher. However, it turned out that the DES S-boxes are particularly resistant against
this attack. In fact, one member of the original IBM design team declared after the
discovery of DC that they had been aware of the attack at the time of design. Al-
legedly, the reason why the S-box design criteria were not made public was that the
design team did not want to make such a powerful attack public. If this claim is true
and all circumstances support it - it means that the IBM and NSA team was
15
years ahead of the research community. It should be noted, however, that in the
1970s and 1980s relatively few people did active research in cryptography.
In 1993 a related but distinct analytical attack was published by Mitsuru Matsui,
which was named linear cryptanalysis (LC). Similar to differential cryptanalysis,
the effectiveness of this attack also heavily depends on the structure of the S-boxes.
What is the practical relevance of these two analytical attacks against DES? It
turns out that an attacker needs 247 plaintext-ciphertext pairs for a successful DC
attack. This assumes particularly chosen plaintext blocks; for random plaintext 255
pairs are needed! In the case of LC, an attacker needs 243 plaintext-ciphertext pairs.
All these numbers seem highly impractical for several reasons. First, an attacker
needs to know an extremely large number of plaintexts, i.e., pieces of data which
are supposedly encrypted and thus hidden from the attacker. Second, collecting and
storing such an amount of data takes a long time and requires considerable memory
resources. Third, the attack only recovers one key. (This is actually one of many
arguments for introducing key freshness in cryptographic applications.) As a result
of all these arguments, it does not seem likely that DES can be broken with either
DC or LC in real-world systems. However, both DC and LC are very powerful
attacks which are applicable to many other block ciphers. Table 3.13 provides an
overview of proposed and realized attacks against DES over the last three decades.
Some entries refer to what is known as the DES Challenges. Starting in 1997, several
DES-breaking challenges were organized by the company RSA Security.
3.1. As stated in Sect. 3.5.2, one important property which makes DES secure is that
the S-boxes are nonlinear. In this problem we verify this property by computing the
output of S₁ for several pairs of inputs.
Show that S₁ (x₁) © S₁ (x2) ‡ S₁ (x1 © x2), where “” denotes bitwise XOR, for:
1. x₁ = 000000, x2 = 000001
2. x₁ = 111111, x₂ = 100000
3. x₁ = 101010, x₂
= = 010101
Expert Solution
![](/static/compass_v2/shared-icons/check-mark.png)
This question has been solved!
Explore an expertly crafted, step-by-step solution for a thorough understanding of key concepts.
This is a popular solution!
Trending now
This is a popular solution!
Step by step
Solved in 3 steps
![Blurred answer](/static/compass_v2/solution-images/blurred-answer.jpg)
Knowledge Booster
Learn more about
Need a deep-dive on the concept behind this application? Look no further. Learn more about this topic, computer-science and related others by exploring similar questions and additional content below.Recommended textbooks for you
![Database System Concepts](https://www.bartleby.com/isbn_cover_images/9780078022159/9780078022159_smallCoverImage.jpg)
Database System Concepts
Computer Science
ISBN:
9780078022159
Author:
Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:
McGraw-Hill Education
![Starting Out with Python (4th Edition)](https://www.bartleby.com/isbn_cover_images/9780134444321/9780134444321_smallCoverImage.gif)
Starting Out with Python (4th Edition)
Computer Science
ISBN:
9780134444321
Author:
Tony Gaddis
Publisher:
PEARSON
![Digital Fundamentals (11th Edition)](https://www.bartleby.com/isbn_cover_images/9780132737968/9780132737968_smallCoverImage.gif)
Digital Fundamentals (11th Edition)
Computer Science
ISBN:
9780132737968
Author:
Thomas L. Floyd
Publisher:
PEARSON
![Database System Concepts](https://www.bartleby.com/isbn_cover_images/9780078022159/9780078022159_smallCoverImage.jpg)
Database System Concepts
Computer Science
ISBN:
9780078022159
Author:
Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:
McGraw-Hill Education
![Starting Out with Python (4th Edition)](https://www.bartleby.com/isbn_cover_images/9780134444321/9780134444321_smallCoverImage.gif)
Starting Out with Python (4th Edition)
Computer Science
ISBN:
9780134444321
Author:
Tony Gaddis
Publisher:
PEARSON
![Digital Fundamentals (11th Edition)](https://www.bartleby.com/isbn_cover_images/9780132737968/9780132737968_smallCoverImage.gif)
Digital Fundamentals (11th Edition)
Computer Science
ISBN:
9780132737968
Author:
Thomas L. Floyd
Publisher:
PEARSON
![C How to Program (8th Edition)](https://www.bartleby.com/isbn_cover_images/9780133976892/9780133976892_smallCoverImage.gif)
C How to Program (8th Edition)
Computer Science
ISBN:
9780133976892
Author:
Paul J. Deitel, Harvey Deitel
Publisher:
PEARSON
![Database Systems: Design, Implementation, & Manag…](https://www.bartleby.com/isbn_cover_images/9781337627900/9781337627900_smallCoverImage.gif)
Database Systems: Design, Implementation, & Manag…
Computer Science
ISBN:
9781337627900
Author:
Carlos Coronel, Steven Morris
Publisher:
Cengage Learning
![Programmable Logic Controllers](https://www.bartleby.com/isbn_cover_images/9780073373843/9780073373843_smallCoverImage.gif)
Programmable Logic Controllers
Computer Science
ISBN:
9780073373843
Author:
Frank D. Petruzella
Publisher:
McGraw-Hill Education