Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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?

share|improve this question
    
Fourier transforms? –  jk. Nov 5 '12 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. –  blz Nov 5 '12 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. :) –  Bjarke Freund-Hansen Nov 5 '12 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. –  Bjarke Freund-Hansen Nov 5 '12 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) –  MichaelT Nov 5 '12 at 15:30

2 Answers 2

up vote 4 down vote accepted

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.

share|improve this answer

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:

http://delab.csd.auth.gr/~dimitris/courses/cpp_fall05/books/SIAM_JNL_Comp_77_KMP_string_matching.pdf

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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