I've recently developed a huge interest in cryptography, and I'm exploring some of the weaknesses of ECB-mode block ciphers. A common attack scenario involves encrypted cookies, whose fields can be represented as (relatively) short hex strings.

Up until now, I've relied on my eyes to pick out repeating blocks, but this is rather tedious. I'm wondering what kind of algorithms (if any) could help me automate my search for repeating patterns within a string.

Can anybody point me in the right direction?

  • Fourier transforms?
    – jk.
    Commented Nov 5, 2012 at 9:26
  • @jk. I'm vaguely familiar with Fourier transforms from signal processing, but could you explain how they would be applied in the present case? I'm afraid my understanding of them is very superficial. Commented Nov 5, 2012 at 9:47
  • 2
    In signal processing terms, what you want to perform is called an autocorrelation. It allows you to determine if there are similarity in a signal with itself, at different times. en.wikipedia.org/wiki/Autocorrelation for more information. :) Commented Nov 5, 2012 at 9:54
  • 1
    I guess an autocorrelation + a fourier transform could tell you if there are repeating patterns of similarity, and at which frequency. Commented Nov 5, 2012 at 9:55
  • When you say "relatively", how short do you mean? Additionally, what is the appropriate block size? (This piques my curiosity, though I've dabbled most with 1900 and earlier cryptography)
    – user40980
    Commented Nov 5, 2012 at 15:30

2 Answers 2


There are two widely-used algorithms for this task: the Index of Coincidence (IC) and Kasinski's method. Googling for either should yield a fair number of hits. Kasiski's method is is older -- at least IMO, the IC is a more effective, especially if you're working with a limited amount of ciphertext. Kasiski's method can work well, but generally requires more ciphertext before it becomes effective.

I should probably add: both of these are really intended for attacking polyalphabetic substitution ciphers. The first step in each is attempting to find the length of the key being used. In your case, working with block ciphers in ECB mode, you probably already know the block size (which is probably the closest equivalent of the key length in a polyalphabetic substitution cipher). What you're left with is largely a matter of just walking through the blocks, and counting how many times a block occurs to see if you can find repetitions. That being the case, it's probably about as easy to skip past most of the algorithm, and just use something like a hash table to count the number of times different block values occur.

Most normal string search algorithms (e.g., Knuth-Morris-Pratt, Boyer-Moore-Horspool) are of little use in this pursuit.


Donald Knuth wrote a lot about string matching pattern theory. A lot of algorithms are very efficient in time and hidden constant. You can found some good algorithms here:


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.