# Knowledge base: Warsaw University of Technology

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
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?