Knowledge base: Warsaw University of Technology

Settings and your account

Back

Complexity of cryptographic keys

Aleksander Michał Kubań

Abstract

Cryptography is a study which has many similarities to nonlinear physics, and dynamical systems. The similarities occur mostly in these ciphers which bases their encryption process on some kind of pseudo-random generator – nonlinear deterministic systems, which have many applications in statistical physics, e.g. in Monte Carlo approach. For that reason the pseudo-random generator is the subject of my analysis . In this document I am showing how nonlinear systems terminology can help in description of properties of certain stream ciphers, namely ARC4. Moreover I am revealing few statistical weaknesses which can be used to construct a successful attack. In my analysis I focused on a ARC4(known as RC4) stream cipher. This cipher was created by Ron Rivest in 1987. It was the most commercially used cryptographic algorithm. It was implemented in the various Internet protocols, such as: SSL, WEP, WPA, Sequre SQL. In the first part of this paper I introduce the reader to the world of cryptograph. I define couple of terms that are needed to fully understand this thesis. Beside the terms itself I equip the reader with certain knowledge from cryptoanalysis field, such as different forms of cryptographic attacks. In the second part I describe the ARC4 stream cipher, it’s implementation and functions that it consists of. Also I look at this cipher from a perspective of a physicist, by using knowledge from fields of statistical and nonlinear physics. In the third part of this paper I shall describe the methods of attacks I used during my examination of ARC4. In the last part I present my findings from a three different perspectives -cryptography, physics, and end user. During my examination of ARC4 I constructed a brute force attack compared with statistical analysis. One of the methods used by me was a partial conclusion. For an attack type I chose an attack with known key. I compared an ARC4 stream cipher to microcanonical ensemble. My examination yielded the following results: In the phase space of baseline condition there are sates which have higher probability of being reached which confirms the H.Finney’s experiment[2]. Also I discovered that sum of random sequence, which exists inside the ARC4 function, which have uniform distribution have got Gaussian distribution which is more precise for longer sequence. From cryptographic perspective, it shows us that pseudo-random generator does not yield random values, hence it is reasonable to look at it as a nonlinear system, which exhibits such properties of nonlinear dynamical systems as gradual loss of information of initial conditions and presence of two coexisting attractors. Results presented by me concern only one of the statistical weaknesses of ARC4 stream cipher. There are many more weaknesses in this cipher, however because of the computational resources needed by methods used by me in the examination of this cipher, I was not able to exam this cipher in its fullest form – I only examined ARC4’s reduced form. However the results are repeatable for the different sizes of this cipher. Because of that there is a huge probability that full cipher has got the same weaknesses as described in this paper. The method of reduction of ARC4 is interesting as such.
Diploma type
Engineer's / Bachelor of Science
Diploma type
Engineer's thesis
Author
Aleksander Michał Kubań (FP) Aleksander Michał Kubań,, Faculty of Physics (FP)
Title in Polish
Miary złożoności kluczy kryptograficznych
Supervisor
Teodor Buchner (FP/PCSD) Teodor Buchner,, Physics of Complex Systems Divison (FP/PCSD)Faculty of Physics (FP)
Certifying unit
Faculty of Physics (FP)
Affiliation unit
Physics of Complex Systems Divison (FP/PCSD)
Study subject / specialization
, Fizyka Techniczna
Language
(pl) Polish
Status
Finished
Defense Date
04-04-2019
Issue date (year)
2019
Reviewers
Teodor Buchner (FP/PCSD) Teodor Buchner,, Physics of Complex Systems Divison (FP/PCSD)Faculty of Physics (FP) Grzegorz Siudem (FP/PCSD) Grzegorz Siudem,, Physics of Complex Systems Divison (FP/PCSD)Faculty of Physics (FP)
Keywords in Polish
Kryptografia, ARC4, RC4, szyfry strumieniowe, kryptoanaliza, fizyka statystyczna, fizyka układów dynamicznych, teoria chaosu
Keywords in English
Cryptography, ARC4, RC4, stream ciphers, cryptoanalysis, statistical physics, nonlinear physics, chaos theory
Abstract in Polish
Kryptografia to dziedzina mająca wiele pokrewieństw do dynamiki nieliniowej i fizyki układów złożonych. Dotyczy to między innymi szyfrów, których centralną częścią jest generator liczb pseudolosowych: nieliniowy układ deterministyczny. W niniejszej pracy pokazuję w jaki sposób terminologia dynamiki nieliniowej może pomóc w opisie własności wybranego szyfru i ujawniam słabość jego konstrukcji, która może być podstawą do wykonaniu ataku kryptograficznego. W swoich badaniach skupiłem się na szyfrze kryptograficznym ARC4 stworzonym przez Rona Rivesta w 1987 roku. W pierwszej części pracy przedstawiam czytelnikowi podstawy kryptografii, oraz uzbrajam czytelnika w wiedzę z zakresu podstaw kryptoanalizy. W części drugiej mówię o szyfrze ARC4, jego implementacji i funkcjach które go tworzą, następnie pokazuje w jaki sposób można rozpatrzyć ten szyfr z punktu widzenia fizyka, wykorzystując przy tym takie dziedziny fizyki jak fizyka układów nieliniowych oraz fizyka statystyczna. W części trzeciej opisuję metody analizy tego szyfru oraz sposoby ataków na nim wykonanych. W ostatniej części natomiast, przedstawiam wnioski wyciągnięte z wyżej wspomnianej analizy oraz ich interpretację dla przeciętnego użytkownika algorytmu ARC4. W tej pracy wykonałem atak siłowy oraz analizę częstotliwości szyfru strumieniowego ARC4. Wykorzystałem metodę częściowego wnioskowania, a za typ ataku wybrałem atak z wybranym kluczem. Otrzymane wyniki analizuję z punktu widzenia fizyka statystycznego. Porównałem szyfr ARC4 do rozkładu mikrokanonicznego. Zbadałem iż nie jest on mocnym szyfrem, gdyż w jego przestrzeni warunków początkowych istnieją stany o większym prawdopodobieństwie osiągnięcia niż inne, co potwierdza spostrzeżenie dokonane przez H. Finneya [2]. Oprócz tego pokazałem iż suma ciągu losowego, który istnieje wewnątrz jednej z funkcji szyfru ARC4, o rozkładzie równomiernym aproksymuje rozkład Gaussa tym dokładniej im dłuższy jest ciąg. Z punktu widzenia kryptograficznego, pokazuje to iż generator pseudolosowy w funkcji KSA(Key Scheduling Algorithm) szyfru strumieniowego ARC4 nie tylko w teorii ale również w praktyce nie zwraca losowych wartości(szumu), co potwierdza wartość podejścia polegającego na tym, żeby analizować układy kryptograficzne jako układy nieliniowe. Z formalnego punktu widzenia jest to układ nieliniowy, wykazujący takie własności jak utrata informacji o warunku początkowym czy koegzystujące atraktory. Wyniki przeze mnie przedstawione dotyczą tylko jednej z podatności szyfru ARC4 i nie wyczerpują tematu, chociażby dlatego, że ze względu na wymagania obliczeniowe stosowanych przeze mnie metod, używałem ich nie dla pełnego szyfru ale dla jego ograniczonej wersji. Niemniej owe wyniki są powtarzalne dla wersji szyfru opisanych różnymi wartościami parametru. Wprowadzenie ograniczonej wersji szyfru RC4 zachowującej jednak własności dynamiczne jest nowym podejściem w analizie kryptograficznej.
File
  • File: 1
    Aleksander_Kuban_Miary_Zlozonosci_Kluczy_Kryptograficznych.pdf
Request a WCAG compliant version
Local fields
Identyfikator pracy APD: 32144

Uniform Resource Identifier
https://repo.pw.edu.pl/info/bachelor/WUT837c7d3b6e0e430ab68443521a6ac00b/
URN
urn:pw-repo:WUT837c7d3b6e0e430ab68443521a6ac00b

Confirmation
Are you sure?
Report incorrect data on this page