JustinT
Trusted SF Member
Joined: 17 Apr 2003
Posts: 1227
Location: Charlotte, NC, US / Uberlândia, MG, Brazil
|
 Posted: Sat May 01, 2004 9:55 pm Post subject: A dictionary-like breakdown, without the mathematics. |
 |
|
To help you establish a basis for how these cryptanalytical attacks are classed, I'll very briefly define them, by what category they fall under, and an overview of what they are meant to accomplish. Because of the lack of mathematical notation available in this text box, I'll not go into heavy mathematical explanation; rather, I will keep it simple and summed up in words, for the most part. In fact, let's just not do the math right now, so to speak. Because of this, notice that I am being extremely informal and general. The details of these are much more immense than what I can comfortably explain without mathematical notation and the prerequisite context that is associated with understanding the theory behind them.
Let's start with the two most generalized forms of cryptanalysis - linear cryptanalysis and differential cryptanalysis. We recognize Matsui, as the pioneering father of linear cryptanalysis (i.e., experimentation with, and analysis of, DES), who along with Yamagishi, devised the first working analyses on other conventional block algorithms (i.e., analysis of FEAL). Biham and Shamir pioneered the basis for differential cryptanalysis (i.e., analysis of DES), as we know its extension to conventional block algorithms today, even as the technique had long been silently known for decades, at IBM. Since then, a myriad of extensions and variations exist, for both of these areas of cryptanalysis, which are strikingly similar in many regards.
Linear cryptanalysis, in the most general conceptualization, is a known-plaintext attack, involving linear approximations that follow the behavior of a block cipher. DES, for example, is one of the first, and most notable, cases where the significance of this type of analysis was rendered. Significant, as in, producing attacks faster than key exhaustion. To sum the attack up is fairly simple. Consider XOR. XOR some bits of plaintext with one another. XOR some bits of ciphertext with one another. XOR the result. With this, you should return a single bit that is the XOR of some bits of the key. This is what we mean by a linear approximation, primitively. The probability, if bounded away from 1/2, allows for a successful exploitation of this relationship. You are merely using gathered plaintext-ciphertext pairs to take a stab at guessing bits of the key. Obviously, the more data you gather, the more reliable your analysis will be. The stronger the bias, the more probable the rate of success will be with a given amount of data. As aforementioned, take a look at how this applies, heavily, to the S-boxes of DES, for a clear example.
Differential cryptanalysis, in its most general conceptualization, is a chosen-plaintext attack, on the other hand. Of this type exist attacks faster than key exhaustion, for DES, which also marks its significance. With these attacks, you are specifically focusing your analysis on ciphertext pairs, by seeing where their associated plaintexts differ. You analyze these differences through the propagation of plaintexts, in its evolution through each round of DES, when the same key is use for encrypting them. You are merely juxtaposing the XOR of two plaintexts to the XOR of their corresponding ciphertexts. This is the primary difference between linear and differential cryptanalysis. Again, take a look at how this applies to the S-boxes of DES, for another clear example. From here, you will gather the importance of S-boxes to block ciphers, and how they require meticulous construction in order to mitigate, or completely repel, the effects of either of these types of analysis.
As briefly mentioned above, there are striking similarities between these two types of cryptanalysis. Because of these, there has been some rather interesting research into differential-linear cryptanalysis, which obviously utilizes of concatenation of techniques from both types. Hellman, to name one familiar name, has devised cryptanalytical attacks against DES, of this nature, that infer promising results from this perspective of methodology.
Next, let's move on to the Square attack, which I will assume you are referring to as the attack that originated for analysis of the Square block algorithm, which is the "predecessor" of Rijndael, by the same Belgian designers. This attack is generally of the chosen-plaintext variety and falls under a class of generic multiset attacks. You'll also see these referred to as, by other cryptographic publications, as saturation attacks and integral cryptanalysis. Even some forms of collision attacks fall under this category. Lars Knudsen has, most notably, pioneered a large portion of this stem of cryptanalytical research, including the cryptanalysis specifically for the Square block algorithm, and it is no surprise that he is one of the most clever cryptographers to date. Other house-hold names involved in this research include Rijmen, Daemen, Lucks, Wagner, Gilbert, and Minier. The attack is unlike that of our traditional differential attack in that it doesn't focus on the behavior of plaintext-ciphertext pairs; rather, it focuses on much larger sets, where portions of the input form what we refer to as a multiset, where given elements can appear more than once. In this multiset, we have a value, which is simply the element's value, and multiplicity, which is a count of the appearances that element makes within the multiset. From here, one analyzes the propagation of the multisets through the algorithm. Attacks of this sort have been among the most successful against AES, to date. This, in my opinion, is one of the most promising areas of cryptanalytical research, and quite interesting, at that.
Moving right along, we come to the interpolation attack. Thanks to Knudsen, along with Jakobsen, we have yet another effective cryptanalytical technique that can be applied to block ciphers. This is a bit different than the others, and much newer than many of them. It, basically, involves the analysis of block ciphers using trivial functions, algebraic in nature (more specifically, quadratic, for example), as S-boxes. If you are familiar with Lagrange interpolation, you may be find it easier to follow how this equation can be applied to this cryptanalytical attack methodology. Working with a generic iterated block cipher, we express figures in the form of polynomials. Let our block size be m. Express the ciphertext of the plaintext, in polynomial form, with n as our denotement of coefficients in this polynomial. If n is less than or equal to 2^m, then exploitation by interpolation attack exists, where there is a time complexity of n requiring n known plaintexts, which have been encrypted with the same key. This renders an algorithm equivalency, to encryption or decryption, under the key. There are variations of interpolation attack methodology, including a probabilistic configuration, and efficient tweaks involving Newton interpolation, in place of Lagrange interpolation. Interesting research into the cryptanalysis of SHARK was a formal starting point for successful interpolation attacks.
Last, but not least, we reach the final cryptanalytical technique - truncated differentials. Once again, let's thank Knudsen on this one. Going back to differential attacks (and let this be an extension to my earlier layman's definition), a differential is something we utilize to take a guess at an n bit value of the ciphertext, following a number of rounds, of which we then define a difference of two bits strings, which are equal in length. We can call (a,b) an i round differential, if the following exists: a is a difference in two blocks of plaintext and b is a difference in two blocks of ciphertext, where a yields b, after i rounds. As the name truncated differential might imply, you are not always required to predict the complete bit value of n. So, obviously, this partial prediction of n is dubbed as such. Simply enough, if (a,b) is an i round differential, then consider the following: a subsequence of a is a' and a subsequence of b is b', where (a',b') is an i round truncated differential. It's an incredibly lucid type of analysis to comprehend, once you've mastered the art of differentials. This type of analysis can, for example, be applied to iterated ciphers, such as the Feistel network design (i.e., DES).
The above research may lead you into other interesting areas of cryptanalysis, such as related-key attacks and higher order differentials.
Now, closing with two simple notions for security, often associated with block algorithms, such as AES. These notions are K-security and hermetic. We look at a block cipher as K-secure if any applicable attack associated with it has the same requirements, work-wise and storage-wise, comparative to that of most similar-in-dimension block algorithms. This notion cannot be held by an algorithm for which key recovering attacks faster than key exhaustion exist, as well as mapping properties (i.e., complementation), related-key attacks, or significant weak key classes. It's a serious notion, and one that's difficult to achieve in some cases. However, some weaknesses can exist, and still allow for this notion. Consider the hermetic notion. Suppose you have a block algorithm with a weak key. Using the algorithm for mere encryption may not pose a monumental threat, with just a single weak key. However, if this is used as an internal component for the compression function of a hash algorithm, it may allow for collision exploitation, which is monumental. So, we define a block cipher as hermetic if it exhibits no weakness that isn't exhibited by other similar-in-dimension block algorithms. If the algorithm is both K-secure and hermetic, we hope, with confidence in its cryptanalytical resilience, that it is as secure as one would naïvely expect a block algorithm of such structure and dimension to be.
For good examples with studying any of these attacks, I suggest researching the cryptanalyses of DES, FEAL, IDEA, PES, SHARK, and AES. Of course, these analyses can be extended to most any block algorithm, and even those of the stream nature, but these six algorithms have proven to be among the most extensively analyzed, in regards to these specific attacks, and I feel they will suit your studies well.
So, here you have it. The basic overview, along with algorithm starting points. From here, you must ask yourself, "What level of mathematics have I achieved?" This plays a vital role in whether or not you will be able to comfortably understand the mathematical theorems and security notions that these cryptanalytical branches propose. If you want to tackle the mathematics, and feel comfortable with doing so, I'll be glad to point you to documentation, as well as provide you with mathematical theorems and security notions. Until then, you have a dictionary-like breakdown of them to start you off.
_________________
"Strict Avalanche Criterion n. Restrictive clause in ski-insurance policy."
|
|
JustinT
Trusted SF Member
Joined: 17 Apr 2003
Posts: 1227
Location: Charlotte, NC, US / Uberlândia, MG, Brazil
|
| Posted: Sun May 02, 2004 6:45 pm Post subject: A few good resources. |
|
|
Some time back, I posted a thread on the important mathematical areas of cryptanalysis most commonly associated with block ciphers today. The thread, Conventional Algorithm Analysis Prerequisites: A Breakdown, briefly defines the necessary prerequisite mathematics for comfortably performing cryptanalytical techniques on cryptographic algorithms. Much of these mathematical branches is echoed in Bruce Schneier's Self-Study Course in Block Cipher Cryptanalysis, which is a superb reference to the bulk of the greatest analyses we have to date. I highly recommend you reading it.
Neither my post nor his study course teach mathematics, but they will give you an idea as to what you need to know, most of which can be found in most any library's selection or any school, college, or university's curriculum text books. You'd even be surprised at what you can find online, via simple Google searches on specific mathematical areas. Note that many educational facilities provide free courses, course material, projects, and lecture notes, by ease of download. If and when you decide to take this to the ultimate notch, the most extensive, yet the most moderately expensive, cryptanalytical tool resides within the confinement of the Lecture Notes in Computer Science, which is published by the cryptographically-renown Springer-Verlag. This includes the proceedings from highly-esteemed conferences and workshops, such as CRYPTO, ASIACRYPT, EUROCRYPT, and INDOCRYPT, just to name a few. This is a must-have addition to any serious cryptographer's arsenal of supplies. You may even consider the publications from the other cryptographically-renown Aegean Press; and in my opinion, consider, especially, the works of Friedman, who you'll find in their publications.
So, once you have found the necessary texts for acquiring the mathematical knowledge required, as outlined in my post on the matter, you'll be ready to tackle the analyses provided in Schneier's self-study course, as well as the references he provides; these references, many of which are available from Springer-Verlag's publications. The learning curve is quite friendly, given enough patience and effort. In the meanwhile, refer to Wolfram Research's Mathworld, for a superb reference along the way.
Either way, even if it means buying text books, reading and consuming all text on the subject is the best way to instill the necessary discipline for understanding the mathematics of cryptography and cryptanalysis. When purchasing text books for recreational purposes, such as teaching yourself cryptanalysis (which may very well evolve into something professional), you obtain the freedom of self-pace; so, you only learn what you wish to learn, how much of it you want to learn, and when you want to learn it.
In my opinion, the most beneficial solution for you, is purchasing mathematical text books, from Springer-Verlag, or acquiring them on loan, or purchase, from a library or some educational institution. Along with the freely available papers on cryptanalysis and mathematics, this is by far the most convenient, efficient, extensive, and beneficial solution, in the long run.
_________________
"Strict Avalanche Criterion n. Restrictive clause in ski-insurance policy."
|
|
