A parallel time-memory tradeoff attack on the Hill cipher. Issue 5 (3rd September 2018)

• Record Type: Journal Article
• Authors: McDevitt, Tim; Lehr, Jessica; Gu, Ting
• Is Part Of: Cryptologia. Volume 42:Issue 5(2018)
• Page Start: 408
• Page End: 426
• Publication Date: 2018-09-03
• Subjects: Hill cipher -- goodness-of-fit -- index of coincidence; Cryptography -- Periodicals; 652.8
• DOI: 10.1080/01611194.2017.1422051
• Languages: English
• ISSNs: 0161-1194

Abstract

ABSTRACT: Leap et al. (2016 ) reduced the time complexity of the Bauer-Millward (2007 ) ciphertext-only attack on the Hill cipher from 𝒪 ( L n ) to 𝒪 ( L n −1 ), where L is the length of the alphabet, and n is the block size. This article presents an attack that reduces the complexity to 𝒪 ( L n −1− s ), 0 ≤ s ≤ n − 1. The practical limitation on the size of s is the memory available on the computer being used for the attack. Specifically, the computer must be able to hold L s integer arrays of length N, where N is the number of blocks of ciphertext. The key idea is not to iterate over potential rows of the decryption matrix, but to iterate over randomly chosen characters in the plaintext. This attack also admits a straightforward parallel implementation on multiple processors to further decrease the run time of the attack.