An investigation of data dependent structures in cryptographic ciphers

Kidney, Brian James (2010) An investigation of data dependent structures in cryptographic ciphers. Masters thesis, Memorial University of Newfoundland.

[English] PDF - Accepted Version Available under License - The author retains copyright ownership and moral rights in this thesis. Neither the thesis nor substantial extracts from it may be printed or otherwise reproduced without the author's permission. Download (7MB)

Abstract

This thesis studies the use of data dependent structures in cryptography. Since the introduction of RC5 by Rivest in 1994, which relied heavily on data-dependent rotations for its security [1], these structures have gained interest in cryptography. During the Advanced Encryption Standard selection process two candidate ciphers, RC6 and MARS, relied on data-dependent structures. -- The thesis focuses on CIKS-1, a cipher introduced in the Journal of Cryptography in 2002 [2], that relies mainly on data-dependent permutations for its security. Due to its reliance on these permutations, this cipher is chosen as a basis for the study of data-dependent structures in cryptographic algorithms. -- The first attack on CIKS-1 presented is a chosen plaintext attack which exploits the lack of change in the Hamming weight of the data as it is enciphered. The research shows that there is a class of weak keys with low weight that can be detected when the input weight is constrained. An attack on a 6 round reduced version of the cipher is outlined that can reduce the search space of the first round subkey to within a weight of two from the weight of the actual key. This attack is experimentally shown to work when the subkey weights are around six or less with a total time complexity for the attack of 2⁵² encryption operations. -- The second attack presented is a variant of classical differential cryptanalysis. Instead of focusing on the exact bit difference of the two inputs that make up the differential, the attack instead focuses on the difference in their weights. An experimental attack on a three-round reduced version of the cipher is presented using this technique which can retrieve the last round subkey of CIKS 1 with a data complexity of approximately 2³⁵ plaintext/ciphertext pairs and time complexity of approximately 2³⁵ encryption operations plus 2⁶⁸ partial decryption operations. It is also shown that this can theoretically be extended to the whole cipher with a total data complexity of 2⁵¹ plaintext/ciphertext pairs and time complexity of approximately 2⁵² encryption operations plus 2⁸⁴ partial decryption operations. -- Despite the weaknesses discovered in CIKS 1, there is potentially some merit in using data dependent permutations in ciphers. Therefore, the implementation of CIKS-1 in software is investigated. The cipher was originally designed to be fast in hardware and contains many operations that work at the bit level, which are inefficient to implement in software. A software version of the cipher is presented which uses bitslicing, effectively parallelizing the cipher on a single processor. This version experimentally shows a speed up of approximately 175 times over a more straight forward implementation using arrays of elements to hold individual bits.

Actions (login required)

View Item