Full Text Available
Note: Clicking the button above will open the full text document at the original institutional repository in a new window.
Correlation attacks on stream ciphers using convolutional codes
Dissertation (MEng (Electronic Engineering))--University of Pretoria, 2007.
Saved in:
| Other Authors: | |
|---|---|
| Format: | Thesis |
| Published: |
University of Pretoria
2013
|
| Subjects: | |
| Tags: |
No Tags, Be the first to tag this record!
|
| _version_ | 1867613639190511616 |
|---|---|
| access_status_str | Open Access |
| author2 | Penzhorn, W.T. |
| author_browse | Penzhorn, W.T. |
| author_facet | Penzhorn, W.T. |
| collection | Thesis |
| dc_rights_str_mv | © 2005, University of Pretoria. All rights reserved. The copyright in this work vests in the University of Pretoria. No part of this work may be reproduced or transmitted in any form or by any means, without the prior written permission of the University of Pretoria. |
| description | Dissertation (MEng (Electronic Engineering))--University of Pretoria, 2007. |
| format | Thesis |
| id | oai:repository.up.ac.za:2263/24740 |
| institution | University of Pretoria (South Africa) |
| last_indexed | 2026-06-10T12:39:20.633Z |
| license_str | Other — see source repository |
| provenance_str_mv | Harvested via OAI-PMH from UPSpace — University of Pretoria Institutional Repository |
| publishDate | 2013 |
| publishDateRange | 2013 |
| publishDateSort | 2013 |
| publisher | University of Pretoria |
| publisherStr | University of Pretoria |
| record_format | dspace |
| source_str | UPSpace — University of Pretoria Institutional Repository |
| spelling | oai:repository.up.ac.za:2263/24740 Correlation attacks on stream ciphers using convolutional codes Penzhorn, W.T. cbruwer@icon.co.za Bruwer, Christian S Linear feedback shift register Viterbi algorithm Cryptanalysis Stream cipher non-linear combining function Correlation attack Lempel-ziv complexity Binary discriminator Binary derivative UCTD Dissertation (MEng (Electronic Engineering))--University of Pretoria, 2007. This dissertation investigates four methods for attacking stream ciphers that are based on nonlinear combining generators: -- Two exhaustive-search correlation attacks, based on the binary derivative and the Lempel-Ziv complexity measure. -- A fast-correlation attack utilizing the Viterbi algorithm -- A decimation attack, that can be combined with any of the above three attacks. These are ciphertext-only attacks that exploit the correlation that occurs between the ciphertext and an internal linear feedback shift-register (LFSR) of a stream cipher. This leads to a so-called divide and conquer attack that is able to reconstruct the secret initial states of all the internal LFSRs within the stream cipher. The binary derivative attack and the Lempel-Ziv attack apply an exhaustive search to find the secret key that is used to initialize the LFSRs. The binary derivative and the Lempel-Ziv complexity measures are used to discriminate between correct and incorrect solutions, in order to identify the secret key. Both attacks are ideal for implementation on parallel processors. Experimental results show that the Lempel-Ziv correlation attack gives successful results for correlation levels of p = 0.482, requiring approximately 62000 ciphertext bits. And the binary derivative attack is successful for correlation levels of p = 0.47, using approximately 24500 ciphertext bits. The fast-correlation attack, utilizing the Viterbi algorithm, applies principles from convolutional coding theory, to identify an embedded low-rate convolutional code in the pn-sequence that is generated by an internal LFSR. The embedded convolutional code can then be decoded with a low complexity Viterbi algorithm. The algorithm operates in two phases: In the first phase a set of suitable parity check equations is found, based on the feedback taps of the LFSR, which has to be done once only once for a targeted system. In the second phase these parity check equations are utilized in a Viterbi decoding algorithm to recover the transmitted pn-sequence, thereby obtaining the secret initial state of the LFSR. Simulation results for a 19-bit LFSR show that this attack can recover the secret key for correlation levels of p = 0.485, requiring an average of only 153,448 ciphertext bits. All three attacks investigated in this dissertation are capable of attacking LFSRs with a length of approximately 40 bits. However, these attacks can be extended to attack much longer LFSRs by making use of a decimation attack. The decimation attack is able to reduce (decimate) the size of a targeted LFSR, and can be combined with any of the three above correlation attacks, to attack LFSRs with a length much longer than 40 bits. Electrical, Electronic and Computer Engineering unrestricted 2013-09-06T18:15:30Z 2006-01-24 2013-09-06T18:15:30Z 2005-06-14 2007-01-24 2006-01-24 Dissertation Bruwer, C 2005, Correlation attacks on stream ciphers using convolutional codes, MEng dissertation, University of Pretoria, Pretoria, viewed yymmdd < http://hdl.handle.net/2263/24740 > http://hdl.handle.net/2263/24740 http://upetd.up.ac.za/thesis/available/etd-01242006-090544/ © 2005, University of Pretoria. All rights reserved. The copyright in this work vests in the University of Pretoria. No part of this work may be reproduced or transmitted in any form or by any means, without the prior written permission of the University of Pretoria. application/pdf University of Pretoria |
| spellingShingle | Linear feedback shift register Viterbi algorithm Cryptanalysis Stream cipher non-linear combining function Correlation attack Lempel-ziv complexity Binary discriminator Binary derivative UCTD Correlation attacks on stream ciphers using convolutional codes |
| title | Correlation attacks on stream ciphers using convolutional codes |
| title_full | Correlation attacks on stream ciphers using convolutional codes |
| title_fullStr | Correlation attacks on stream ciphers using convolutional codes |
| title_full_unstemmed | Correlation attacks on stream ciphers using convolutional codes |
| title_short | Correlation attacks on stream ciphers using convolutional codes |
| title_sort | correlation attacks on stream ciphers using convolutional codes |
| topic | Linear feedback shift register Viterbi algorithm Cryptanalysis Stream cipher non-linear combining function Correlation attack Lempel-ziv complexity Binary discriminator Binary derivative UCTD |
| url | http://hdl.handle.net/2263/24740 http://upetd.up.ac.za/thesis/available/etd-01242006-090544/ |