Original title: Kryptoanalýza šifer používaných v GSM telefonech
Translated title: Cryptanalysis of ciphers used in GSM phones
Authors: Barboriková, Jana ; Tůma, Jiří (advisor) ; Kechlibar, Marian (referee)
Document type: Master’s theses
Year: 2012
Language: eng
Abstract: [eng] [cze]
The aim of this thesis is to introduce the family of A5 algorithm which is used in data encryption and decryption in GSM phones. It is focused on real time cryptanalysis of the stream cipher A5/1. It describes in detail the known plaintext attack published by A. Biryukov, A. Shamir and D. Wagner. Both the attack and the cipher are implemented. The implementation proves that the preprocessing stage of the attack is very time consuming, but the actual attack can be carried out in real time on a single PC. Then the problem of finding a good statistical model for the process of generating tree of predecessors of internal states of A5/1 is studied. We present reasons why the singletype Galton-Watson process is not suitable for the problem and introduce a multitype Galton-Watson process and a macro process. The models are applied to the process of generating predecessors and their predictions are compared with experimental data. Cílem této práce je představit rodinu algoritmů A5, které se používají při šifrování a dešifrování dat v GSM telefonech. Práce se blíže zabývá kryptoanalýzou proudové šifry A5/1 v reálném čase. Podrobně popisuje útok se znalostí otevřeného textu publikovaný A. Biryukovem, A. Shamirem a D. Wagnerem. Je provedena vlastní implementace tohoto útoku a zmíněné šifry, která dokládá jak náročnost přípravné fáze útoku, tak i jeho efektivitu a proveditelnost na PC. Dále studuje problém hledání vhodného statistického modelu, který by modeloval proces generování předchůdců interních stavů A5/1. Předkládá argumenty pro nevhodnost jednoduchého Galton-Watson procesu pro tento problém a seznamuje s vícetypovým Galton-Watson procesem a makro procesem. Aplikuje tyto modely na daný proces a porovnává jejich předpovědi s experimentálně získanými daty.
Keywords: 1; A5; macro process; multitype Galton-Watson process; real time cryptanalysis; singletype Galton-Watson process; 1; A5; Galton-Watson proces; kryptoanalýza v reálném čase; makro proces; vícetypový Galton-Watson proces

Institution: Charles University Faculties (theses) (web)
Document availability information: Available in the Charles University Digital Repository.
Original record: http://hdl.handle.net/20.500.11956/40442

Permalink: http://www.nusl.cz/ntk/nusl-486221


The record appears in these collections:
Universities and colleges > Public universities > Charles University > Charles University Faculties (theses)
Academic theses (ETDs) > Master’s theses