On LFSR based Stream Ciphers - analysis and design
(2003)- Abstract
- Stream ciphers are cryptographic primitives used to ensure privacy in digital communication. In this thesis we focus on stream ciphers built using Linear Feedback Shift Registers (LFSRs). Several different stream ciphers are analysed and new attacks are presented. In addition, two new stream ciphers are presented, both based on the same design.
The first attack is performed on SOBER-t16 and SOBER-t32. A new distinguishing attack is presented for simplified versions of the two ciphers, as well as for the complete version of SOBER-t16.
Next, the cipher A5/1, used in the GSM standard for mobile telephones, is analysed. The resulting attack is an initial state recovery attack which recovers the secret key... (More) - Stream ciphers are cryptographic primitives used to ensure privacy in digital communication. In this thesis we focus on stream ciphers built using Linear Feedback Shift Registers (LFSRs). Several different stream ciphers are analysed and new attacks are presented. In addition, two new stream ciphers are presented, both based on the same design.
The first attack is performed on SOBER-t16 and SOBER-t32. A new distinguishing attack is presented for simplified versions of the two ciphers, as well as for the complete version of SOBER-t16.
Next, the cipher A5/1, used in the GSM standard for mobile telephones, is analysed. The resulting attack is an initial state recovery attack which recovers the secret key using approximately 5 minutes of known keystream. The attack takes roughly 5 minutes to perform on today's standard PC.
Bluetooth is a well-known standard for wireless communication and the cipher responsible for the secrecy within that standard is called E0. An initial state recovery algorithm on E0 is presented, based on recently discovered correlations within the cipher. These new correlations are stronger than previously known. This attack, however, is only applicable to E0 in a theoretical perspective, since the required length of the observed keystream is longer than allowed in the Bluetooth standard.
Following this, two distinguishing attacks are presented targeting clock controlled generators; the shrinking generator and the self-shrinking generator. The attack on the shrinking generator is based on a new observation that the majority bits of a block surrounding the tap positions in the LFSR output also fulfils the linear recurrence equation. The attack on the self-shrinking generator identifies two new classes of weak feedback polynomials. For the first class, both a distinguishing attack and an initial state recovery attack are presented. This distinguishing attack is remarkable in the sense that the required length of the observed keystream only grows linearly in the length of the shift register. For the second class of weak feedback polynomials a distinguishing attack is given.
The final part of this thesis concerns the design of stream ciphers. Two new designs are presented, SNOW 1.0 and SNOW 2.0, the latter being an improvement on the former. These ciphers are designed to be very fast, especially in a software implementation. (Less) - Abstract (Swedish)
- Popular Abstract in Swedish
Den här avhandlingen handlar om kryptering, strömchiffer, metoder för att analysera (knäcka) och konstruera bättre chiffer.
Det finns flera olika metoder för att hemliggöra meddelanden. Det klassiska sättet är att två personer som vill kommunicera delar en hemlig nyckel som används för att både kryptera och dekryptera meddelanden. Denna metod kallas symmetrisk kryptering, eftersom båda parter delar en hemlig nyckel. Den andra metoden är så kallad öppen-nyckel kryptering, men det behandlas inte i denna avhandling.
Bland de symmetriska chiffren finns två huvudgrupper, blockchiffer och strömchiffer. Man kan enkelt säga att ett blockchiffer först delar in... (More) - Popular Abstract in Swedish
Den här avhandlingen handlar om kryptering, strömchiffer, metoder för att analysera (knäcka) och konstruera bättre chiffer.
Det finns flera olika metoder för att hemliggöra meddelanden. Det klassiska sättet är att två personer som vill kommunicera delar en hemlig nyckel som används för att både kryptera och dekryptera meddelanden. Denna metod kallas symmetrisk kryptering, eftersom båda parter delar en hemlig nyckel. Den andra metoden är så kallad öppen-nyckel kryptering, men det behandlas inte i denna avhandling.
Bland de symmetriska chiffren finns två huvudgrupper, blockchiffer och strömchiffer. Man kan enkelt säga att ett blockchiffer först delar in meddelandet i block av en viss storlek och krypterar sedan blocken individuellt. Ett strömchiffer krypterar varje tecken med en tidsvarierande funktion så att t.ex. ett "a" inte krypteras till samma chiffertext varje gång. Strömchiffer är oftast snabbare än blockchiffer och passar därför till att kryptera snabb datakommunikation såsom nätverkstrafik eller radiokommunikation.
Ett vanligt sätt att bygga strömchiffer är att först bygga en pseudo- slumptalsgenerator som från nyckeln genererar ettor och nollor som för en observatör ser i princip helt slumpmässiga ut. Denna ström av slumptal adderas (xor) sedan till meddelandet tecken för tecken. Mottagaren genererar sedan exakt samma slumptal med hjälp av den hemliga nyckeln och kan subtrahera bort den från chiffertexten och få tillbaka meddelandet.
Många av dessa strömchiffer är baserade på lineärt återkopplade skiftregister (Linear Feedback Shift Register, LFSR). I denna avhandling analyseras flera kända strömchiffer, bland annat det som krypterar talet i GSM mobiltelefoner. Det chiffret kallas A5/1. Utöver A5/1 analyseras också fyra andra intressanta konstruktioner.
I slutet av avhandlingen presenteras också en ny strömchifferkonstruktion, SNOW. SNOW finns i två versioner och den senare (SNOW 2.0) är på förslag som internationell standard av ISO. (Less)
Please use this url to cite or link to this publication:
https://lup.lub.lu.se/record/21364
- author
- Ekdahl, Patrik LU
- supervisor
- opponent
-
- Dr Babbage, Steve, Chief Cryptographer, Vodafone Group, UK
- organization
- publishing date
- 2003
- type
- Thesis
- publication status
- published
- subject
- keywords
- self-shrinking generator, shrinking generator, E0, A5, sober, stream cipher, LFSR, snow, Informatics, systems theory, Informatik, systemteori
- pages
- 164 pages
- publisher
- Department of Information Technology, Lund Univeristy
- defense location
- E-building, room E:1406, Lund Institute of Technology.
- defense date
- 2003-11-21 10:15:00
- ISBN
- 91-628-5868-8
- language
- English
- LU publication?
- yes
- id
- 08c1d26a-c791-41fa-8804-42dc9e5b1017 (old id 21364)
- date added to LUP
- 2016-04-04 11:22:26
- date last changed
- 2018-11-21 21:04:25
@phdthesis{08c1d26a-c791-41fa-8804-42dc9e5b1017,
abstract = {{Stream ciphers are cryptographic primitives used to ensure privacy in digital communication. In this thesis we focus on stream ciphers built using Linear Feedback Shift Registers (LFSRs). Several different stream ciphers are analysed and new attacks are presented. In addition, two new stream ciphers are presented, both based on the same design.<br/><br>
<br/><br>
The first attack is performed on SOBER-t16 and SOBER-t32. A new distinguishing attack is presented for simplified versions of the two ciphers, as well as for the complete version of SOBER-t16.<br/><br>
<br/><br>
Next, the cipher A5/1, used in the GSM standard for mobile telephones, is analysed. The resulting attack is an initial state recovery attack which recovers the secret key using approximately 5 minutes of known keystream. The attack takes roughly 5 minutes to perform on today's standard PC.<br/><br>
<br/><br>
Bluetooth is a well-known standard for wireless communication and the cipher responsible for the secrecy within that standard is called E0. An initial state recovery algorithm on E0 is presented, based on recently discovered correlations within the cipher. These new correlations are stronger than previously known. This attack, however, is only applicable to E0 in a theoretical perspective, since the required length of the observed keystream is longer than allowed in the Bluetooth standard.<br/><br>
<br/><br>
Following this, two distinguishing attacks are presented targeting clock controlled generators; the shrinking generator and the self-shrinking generator. The attack on the shrinking generator is based on a new observation that the majority bits of a block surrounding the tap positions in the LFSR output also fulfils the linear recurrence equation. The attack on the self-shrinking generator identifies two new classes of weak feedback polynomials. For the first class, both a distinguishing attack and an initial state recovery attack are presented. This distinguishing attack is remarkable in the sense that the required length of the observed keystream only grows linearly in the length of the shift register. For the second class of weak feedback polynomials a distinguishing attack is given.<br/><br>
<br/><br>
The final part of this thesis concerns the design of stream ciphers. Two new designs are presented, SNOW 1.0 and SNOW 2.0, the latter being an improvement on the former. These ciphers are designed to be very fast, especially in a software implementation.}},
author = {{Ekdahl, Patrik}},
isbn = {{91-628-5868-8}},
keywords = {{self-shrinking generator; shrinking generator; E0; A5; sober; stream cipher; LFSR; snow; Informatics; systems theory; Informatik; systemteori}},
language = {{eng}},
publisher = {{Department of Information Technology, Lund Univeristy}},
school = {{Lund University}},
title = {{On LFSR based Stream Ciphers - analysis and design}},
year = {{2003}},
}