Teaching linear cryptanalysis by breaking the Data Encryption Standard (DES)

Abstract

Kryptologie ist eines der wichtigsten Themen heutiger Informationstechnologien, da sichere Kommunikation und Authentifizierung über unsichere Netze ermöglicht werden. Dennoch spielt sie eine geringere Rolle in IT-Studienrichtungen an der Technischen Universität Wien. Ziel dieser Diplomarbeit ist es, einen Aspekt der modernen Verschlüsselung durch die Bereitstellung einer kompletten Unterrichtssequenz aufbauend auf Problembasiertem Lernen einzubringen.<br />Etwa 15 Stunden an der Universität und bis zu 20 Stunden individuelle Arbeit sind für diese Sequenz eingeplant. Es ist möglich die bereitgestellten Materialien nach klassischem Lehrstil fachbezogen einzusetzen und damit den Aufwand für Vortragende und Studierende zu reduzieren, allerdings geht dies auf Kosten der Nachhaltigkeit.<br />Als "Problem" wurde eine Challenge erstellt, in der die Studierenden aus 80 KB pseudozufälligem Klartext und dem zugehörigen verschlüsselten Text den verwendeten Schlüssel extrahieren müssen. Die Lösung soll in selbstverantwortlichen Gruppen zu jeweils fünf Studierenden erarbeitet werden. Zur Verschlüsselung wird eine Vier-Runden-Variante von DES verwendet, sodass Lineare Kryptanalyse, wie von Mitsuru Matsui in den Jahren 1993 entwickelt, angewendet und erweitert werden muss. Die Studierenden müssen sich alle notwendigen Kenntnisse selbst aneignen, während der Lektor eine "Coaching-Rolle" einnimmt. Außerdem werden die Studierenden während ihrer Untersuchungen viele Themen entdecken und verstehen, die für aktuelle Algorithmen relevant sind.<br />Die Diplomarbeit soll die Vortragenden zeiteffizient unterstützen und ist daher themabasiert aufgebaut. Zunächst wird der pädagogische Rahmen erläutert, indem Problembasiertes Lernen, Authentisches Lernen und Curriculares Lernen diskutiert, sowie Lernziele und Methoden sie zu erreichen, festgelegt werden. Danach werden grundlegende kryptografische Methoden (Permutation, Substitution, öffentliche Schlüssel, ...) und ihre kryptanalytischen Gegenstücke (Häufigkeitsanalyse, (wo)man-in-the-middle-Attacke, Kasiski Test, ...) kurz behandelt. Darauf folgt detaillierte Theorie von DES und Linearer Kryptanalyse mit vielen Beispielen, die in der Lehrveranstaltung direkt eingesetzt werden können. Der Angriff selbst ist auf "sieben Verständnisschritten" aufgebaut, die jeden Aspekt getrennt erklären, um die Komplexität zu verhindern, mit der die meisten anderen Dokumenten das Thema erklären.<br />Schließlich wird die Challenge beschrieben und eine passende Lösung vorgestellt.<br />Zusammen mit der Diplomarbeit werden alle für die Challenge notwendigen Dateien, Präsentationen sowie auch ein Handout für die Studierenden bereitgestellt. Außerdem sind die erforderlichen Source-Codes und eine Schritt-für-Schritt-Anleitung zur Erstellung eigener Angaben zu finden.<br />

Cryptology is one of the main topics in today's Information Technologies, enabling secure communication and authentication over unsecure networks. Nevertheless it plays a lower role in IT studies at the Technical University of Vienna. The master thesis is intended to bring in an aspect of modern encryption by providing a complete learning sequence implementing Problem-Based Learning. This sequence is planned to take about 15 hours present at university and up to 20 hours of individual work. Using the provided material in a subject-based way to reduce the time-effort for both lector and student is possible but goes at cost of sustainability.<br />As "problem" a challenge is created in which the students have to derive the key out 80 KB of plain text and the corresponding cipher text. This shall be solved self-reliantly in groups of five. For encryption a four round variation of DES is used so the students need to implement Linear Cryptanalysis as it was developed by Matsui in 1993 and extend it. The students are required to gain all necessary knowledge on their own while the lector remains in a coaching role. Moreover the students will discover and comprehend many topics relevant for actual ciphers while doing their investigations.<br />The thesis itself is intended to support the lector time-efficiently and will therefore show a subject-based structure. At first the educational framework is explained by discussing Problem-Based Learning, Authentic Learning and Curricular Learning as well as defining educational objectives and methods to reach them. Afterwards basic cryptographic methods (permutation, substitution, public keys, ...) and their cryptanalytical counterparts (frequency analysis, (wo)man-in-the-middle attacks, Kasiski Test, ...) are handled briefly. Next the theory of DES and Linear Cryptanalysis is covered in detail supported by many examples that can be used directly when teaching. The attack itself is built upon "seven steps of understanding" which explain each aspect separately to avoid the complexity most other documents show. Finally the challenge described above and a matching sample solution it are introduced.<br />Together with the master thesis all necessary files, presentations and a student hand out is provided. Furthermore the required source codes and step-by-step-instructions to create own examples can be found.<br />