Is it possible (and practical) to search a string for arbitrary-length repeating patterns?

by blz   Last Updated December 03, 2017 19:05 PM

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?

Answers 2

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:

November 06, 2012 16:22 PM

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.

Jerry Coffin
Jerry Coffin
November 06, 2012 23:08 PM

Related Questions search algorithm?

Updated December 03, 2017 19:05 PM

Data structure for pattern matching

Updated December 12, 2016 08:02 AM