\nbut not the key;<\/li>\n
That last property is actually a bit of a weasel. There are really a wide variety of attacks that try to crack an encryption
\nsystem – meaning, basically, to discover the key. What makes that
\nstatement of the property so weasely is that it omits the information available to the person trying to crack it. In the first three properties, I clearly stated what information you had available to produce a result. In the last, I didn’t.<\/p>\n
There’s a reason that I weaseled that. Partly, it’s because a correct statement of it would be ridiculously long and incomprehensible; and partly because it’s often deliberately<\/em> set up differently for different encryption systems. You can design systems that are extremely strong against certain attacks, but not so good against others. There’s no universally ideal encryption system: it’s always a matter of tradeoffs, where you can handle some scenarios better than others.<\/p>\n Today we’re going to look at one particularly fascinating attack that’s used against block ciphers. It’s called differential cryptanalysis<\/em>. <\/p>\n <\/p>\n So what is differential cryptanalysis? It’s a technique that looks at how making specific changes in the plaintext input to the cipher produce changes in the output from that cipher. The basic idea, in its simplest form, is that you’re able to select a collection of plaintexts, and encrypt them. Then based on the results of doing Differential cryptanalysis is a form of the basic chosen plaintext attack<\/em>. What makes it a differential attack is that you use related families of plaintext. That is, you’ve got a family of texts T0<\/sub>, T1<\/sub>, T2<\/sub>, …, where each text Ti<\/sub> is equal to T0<\/sub> plus some small difference. For many differential attacks, that small difference is one bit<\/em>.<\/p>\n How can you crack a cipher this way? To start, we assume that you know what cipher we’re using. For example, you know that we’re using DES with a 56 bit key. So you take your initial plaintext, C1<\/sub> differs from C0<\/sub> in some number of bits. Now, you’ve reduced the problem from “What key could produce the plaintext\/ciphertext pair (T0<\/sub>, C0<\/sub>)?” to This reduction can be dramatic. For example, in one of the early proposal rivals to DES, caled FEAL, it turned out that you could crack it with a set of 8 one-block (plaintext,ciphertext) pairs. The problem is reduced from a blind search of a search-space of 264<\/sup> possible keys to utter triviality by a set of 8 chosen plaintexts!<\/p>\n The subtlety of this attack is in how you choose the It can get even more subtle than that. Since you know<\/em> the algorithm, you can isolate a single stage of the cipher (as illustrated to the right), and throw bit-blocks at it in differential style. From that, you can work out the set of subkeys that could produce the observed differential result for that stage. If you do that for all of the stages, you’ll get a set of keys for each stage. Figure out which subkeys keys from each stage are mutually compatible, and then combine them, and you get a very small (usually one) key that could produce valid subkeys for each stage. <\/p>\n You can even repeat this process on multiple levels. If you’ve got a block cipher like DES, and you know the structure, you can do the differential analysis of a single stage by decomposing it into its individual S-boxes. Analyze each S-box, and come up with a set of potential subkey-fragments, and then combine those to create a set of potential subkeys for the stage. Then combine the stage results.<\/p>\n Differential analysis also reveals something fascinating about So how is DES so resistant to an attack that wasn’t discovered This, naturally, has driven a lot of interesting discussion. Why did the NSA want to keep that secret? They claim that they did it because revealing the differential attack and how DES protected against it would “weaken the competitive advantage that the US enjoyed over other countries in the field of cryptography”. But One last comment, and I’ll wrap up this post. Things like differential cryptanalysis are one of the many<\/em> reasons not to roll your own cryptographic cipher. Some of the best cryptographers in the world – people who spent all of their time working on designing secure cryptosystems – designed systems that were easy<\/em> to break using this technique. If you don’t know about every technique that could be used against your system, and you haven’t considered how your system will behave under probing by those techniques, then you have close to no chance of designing something unbreakable. Over time, so many cryptosystems have failed, because someone didn’t notice one tiny little problem, or didn’t think about one obscure technique, or didn’t notice one tiny little bug in their implementation. Those things are fatal to a good cryptosystem. Many of us who are math geeks have tried designing a cipher for the heck of it; how many of us who’ve done it are able to say that we’re sure that it couldn’t be cracked in five minutes of differential analysis? I’d wager that the answer is zero.<\/p>\n","protected":false},"excerpt":{"rendered":" Now, we’re finally reaching the point where the block-cipher stuff gets really fun: block cryptanalysis. As I’ve explained before, the key properties of a really good encryption system are: It’s easy to compute the ciphertext given the plaintext and the key; It’s easy to compute the plaintext given the ciphertext and the key; It’s hard […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2}},"categories":[84],"tags":[],"class_list":["post-688","post","type-post","status-publish","format-standard","hentry","category-encryption"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p4lzZS-b6","jetpack_sharing_enabled":true,"jetpack_likes_enabled":true,"_links":{"self":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/688","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/comments?post=688"}],"version-history":[{"count":0,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/688\/revisions"}],"wp:attachment":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/media?parent=688"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/categories?post=688"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/tags?post=688"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}
\nthat, you try to compute the key.<\/p>\n![\"differential.png\"](\"https:\/\/i0.wp.com\/scientopia.org\/img-archive\/goodmath\/img_331.png?resize=203%2C320\")
<\/p>\n
\nT0<\/sub>, and you encrypt it, giving you a ciphertext, C0<\/sub>. Then you change one bit of T0<\/sub>, giving you T1<\/sub>, and you encrypt that, giving you C1<\/sub>.<\/p>\n
\n“What set of keys could produce the variation<\/em> C0<\/sub> to C1<\/sub> by changing one bit of T0<\/sub>?”. I’ve drawn an outline of this process in a diagram to the right.<\/p>\n![\"extract-diff.png\"](\"https:\/\/i0.wp.com\/scientopia.org\/img-archive\/goodmath\/img_332.png?resize=240%2C285\")
<\/p>\n
\nset of plaintexts to use. For a typical Feistel network block
\ncipher, you need to do a very delicate analysis of the S-blocks. You trace out the possible paths of each bit through the network,
\nand using that, you can work out a set of probable<\/em> differences – that is, bit patterns that are likely to be able to produce an informative<\/em> difference in the ciphertexts. These probable patterns are called differential characteristics<\/em>. Once you’ve worked out a large enough set of probably characteristics, you can use them to assemble a set of informative plaintexts that should provide you with what you need to determine the key.<\/p>\n
\nDES. Most texts attribute the invention of this attack to Shamir in
\nthe late 1980s, when he published a set of papers describing
\ndifferential attacks. But when you analyze DES, you find that it’s
\nnot<\/em> very susceptible to differential attacks! In fact, it
\ntakes 255<\/sup> chosen plaintexts to crack 56-bit DES – so differential analysis is effectively no better than simple brute force. But if you make some very minor changes to S-boxes in the algorithm, it becomes nearly as susceptible as FEAL. <\/p>\n
\nuntil almost 15 years after DES was first published? It turns out
\nthat the IBM team that designed DES had figured out differential
\nattacks before they designed DES in 1974. They knew about that attack and its properties, and specifically designed DES to not<\/em> be susceptible to it. But at the time, they were working with the NSA to produce an official standard encryption system, and the NSA requested that they not<\/em> tell anyone about the attack they’d discovered.<\/p>\n
\na lot of people (to be honest including me) believe that the real
\nadvantage they wanted to maintain was the ability of the US
\nintelligence community to crack encryption systems used by other countries.<\/p>\n