{"id":670,"date":"2008-08-15T09:01:32","date_gmt":"2008-08-15T09:01:32","guid":{"rendered":"http:\/\/scientopia.org\/blogs\/goodmath\/2008\/08\/15\/introducing-cryptanalysis\/"},"modified":"2008-08-15T09:01:32","modified_gmt":"2008-08-15T09:01:32","slug":"introducing-cryptanalysis","status":"publish","type":"post","link":"http:\/\/www.goodmath.org\/blog\/2008\/08\/15\/introducing-cryptanalysis\/","title":{"rendered":"Introducing Cryptanalysis"},"content":{"rendered":"

To understand why serious encryption algorithms are so complex, and why it’s
\nso important to be careful with the critical secrets that make an encryption
\nsystem work, it’s useful to understand something about how people break
\nencryption systems. The study of this is called cryptanalysis<\/em>, and it’s
\nan amazingly fascinating field of applied mathematics. I’m going to be
\ninterspersing information about cryptanalysis with my cryptography posts. One
\nthing to remember here is that we’ll be talking about it mainly in the context
\nof how you can break an encryption system – but cryptanalysis is also used for
\ndesigning cryposystems, because you can only design a successful cryptosystem by
\nthinking about how it can defeat the ways that it could be broken.<\/p>\n

One caveat: I’m going to be describing cryptanalysis in terms of how I understand it, which is sometimes different from classical descriptions by cryptanalysists. My
\nunderstanding is strongly rooted in computation and information theory, rather than pure math. So sometimes my presentation will be a bit different, but hopefully by staying in the ground where I’m most comfortable, I can do a better job of making it comprehensible.<\/p>\n

<\/p>\n

To be a bit formal for a moment, a simple cryptosystem consists of
\ntwo functions:<\/p>\n

    \n
  1. C = En(P, K)<\/li>\n
  2. P = De(C, K)<\/li>\n<\/ol>\n

    Where C is encrypted text (called the cipher-text<\/em>), P is the unencrypted text (called the clear-text<\/em>), K is the secret key at the heart of the system. We typically think of K as being something like a password, but it doesn’t have to be – in a simple substitution cipher, K is the mapping from clear-text characters to cipher characters.<\/p>\n

    A good cryptosystem is one where it’s easy to generate the cipher-text given
    \nthe clear-text and the secret key; easy to generate the clear-text given the
    \ncipher-text and the secret key; and very hard to figure out the secret key, even
    \ngiven a large number of clear-text\/cipher-text pairs.<\/p>\n

    When we analyze cryptosystems to try to divine their secrets, we
    \ncan look at them in terms of a number of different attack scenarios<\/em>. What I mean by attack scenario is that we’re looking at a cryptosystem
    \nthat we want to break. An attack scenario is a way of describing
    \nwhat kind of information the agent trying to crack the cryptosystem
    \nhas access to. For example, some of the common scenarios discussed
    \ninclude:<\/p>\n

      \n
    1. Cipher-only: we can watch encrypted messages sent from one user
      \nto another, giving us a large library of encrypted text. But we don’t know
      \nany of the clear-text.<\/li>\n
    2. Known clear-text: we have a library of encrypted text, like we did in
      \ncipher-only, and in addition, we have some collection of clear-text\/cipher-text
      \npairs.<\/li>\n
    3. Chosen clear-text: we have a library of encrypted text, like we did in
      \ncipher-only, and in addition, we can select a finite set of clear-texts,
      \nand have them encrypted.<\/li>\n
    4. Iterated chosen clear-text (also sometimes called “black-box”):
      \nlike chosen clear-text, but instead of
      \nonly being able to select a set of texts exactly once, we can submit
      \na set of texts, get back the cipher-text, and then based on what we learn
      \nfrom earlier sets of plain\/cipher-text pairs, we can select more sets of
      \nclear-text to encrypt.<\/li>\n<\/ol>\n

      These scenarios all assume that you know the basic cryptosystem. In
      \ngeneral, that’s a reasonable assumption. If you don’t have a clue
      \nabout what kind of cryptosystem was used to encrypt a cipher-text,
      \nthings get much<\/em> harder. There are some tricks that you can use
      \nto make a guess at what kind of cryptosystem was used, but for non-trivial
      \ncryptography, you’re often pretty much honked if you don’t have any idea of
      \nwhat sort of crypto was used.<\/p>\n

      To give you a sense of what it’s like to attack a cryptosystem,
      \nI’ll walk through a simple example. Below is a simple cipher-text,
      \nencrypted using a simple substititution, with spaces and punctuation
      \npreserved.<\/p>\n

      \nb czfbczc bh bu gqlvh hbxz hl uhgih vd xt lkp qrly. lpz\nhjbpy hjgh b jgaz plhbfzc bp xt hbxz qilkubpy hjz qrlyludjziz bu hjgh hjziz giz\ng kjlrz rlh lm hziibmbf ufbzpfz qrlyu lvh hjziz: ligf, djgitpyvrg, gzhblrlyt,\nevuh hl pgxz g mzk. qvh hjziz bu plh pzgirt ul xvfj lvh hjziz czcbfghzc hl xghj\n- gpc bp dgihbfvrgi hl hjz xbuvuz lm xghj. b hjbpw hjgh hjgh bu g cgxp ujgxz,\nqzfgvuz bp xt zodzibzpfz, lpz lm hjz xluh frzgi kgtu lm bczphbmtbpy g figfwdlh\nbu hjilvyj xghj. pl xghhzi hjz udzfbmbf uvqezfh, hjz figfwdlhu grkgtu zbhjzi\ngalbc li ufizk vd hjz xghj. kjzhjzi bh'u hjz \"xzifvit fgvuzu gvhbux\" mlrwu, hjz\nazrbwlauwbgpu, fizghblpbuhu, grh-xzcbfbpz svgfwu, izdvqrbfgp dlrruhziu, li\nufbzphlrlybuhu - tlv fgp grkgtu izflypbnz hjz figfwdlhu qt hjzbi xghj. ul b gx\nylbpy hl cl xt qzuh hl dilabcz g albfz lm xghjzxghbfgr ugpbht - qlhj qt ujlkbpy\nkjgh'u kilpy kbhj hjz qgc xghj urld dvxdzc lvh qt hjz rllpbzu, gpc qt ujlkbpy\njlk yllc xghj kliwu.\n<\/pre>\n
       The first question – and this is always<\/em> the first question in
      \nan attempt to break an encryption – is: “What do we know?”<\/p>\n
       In this case, we know quite a lot:<\/p>\n
        \n
      1.  The clear-text is english text.<\/li>\n
      2.  The encryption is a simple substitution, which preserves
        \nspaces and punctuation, but not case.<\/li>\n<\/ol>\n
        \t That might not look like a lot, but it’s actually huge. Knowing
        \nthat the clear-text is english gives us a huge amount of information
        \nthat we can use to break it. Knowing that work-breaks are preserved
        \nmakes it nearly trivial to solve.<\/p>\n
         To break it, we’ll use a simple form of frequency analysis<\/em>. Frequency analysis is a great technique for attacking simple ciphers. The
        \nidea of it is that we know a huge amount of information about patterns
        \nin human languages. Different letters don’t appear equally frequently in
        \nEnglish; for example, there are a lot more “E”s than “U”s. <\/p>\n
         A lot of people mistakenly think that frequency analysis means only<\/em> using the specific frequency of individual letters. That’s not true. A good
        \nfrequency analysis based attack on a cryptosystem uses not just the frequency of
        \nparticular letters, but of groups<\/em> of letters, relationships between
        \nletters, and frequencies of words.<\/p>\n
         So let’s start deciphering that message. To try to make it easier
        \nto see how we’re decrypting, as we figure out letters, I’ll write
        \nthe message with the clear-text and the cipher-text tangled – clear-text
        \nletters will be uppercase, and cipher-text letters will be lowercase. When
        \nwe figure out that a cipher-text letter “a” encodes to a particular
        \nclear-text letter “B”, we’ll write that as “a\/B”.<\/p>\n
         We’ll start off with a nice word-based frequency trick. There are only two
        \ncommon one-letter words in english: “A” and “I”, and “I” occurs more frequently
        \nat the beginning of a sentence than “A”. So there’s a good chance that a single
        \nletter word that occurs frequently, including at the beginning of sentences is
        \n“I”. So we’ll try that here: there are two one-letter words in the cipher-text:
        \n“b” and “g”, and “b” occurs at the beginning of sentences. So we’ll try “B\/I”
        \nand “G\/A”:<\/p>\n
        \nI czfIczc Ih Iu Aqlvh hIxz hl uhAih vd xt lkp qrly. lpz\nhjIpy hjAh I jAaz plhIfzc Ip xt hIxz qilkuIpy hjz qrlyludjziz Iu hjAh hjziz Aiz\nA kjlrz rlh lm hziiImIf ufIzpfz qrlyu lvh hjziz: liAf, djAitpyvrA, AzhIlrlyt,\nevuh hl pAxz A mzk. qvh hjziz Iu plh pzAirt ul xvfj lvh hjziz czcIfAhzc hl xAhj\n- Apc Ip dAihIfvrAi hl hjz xIuvuz lm xAhj. I hjIpw hjAh hjAh Iu A cAxp ujAxz,\nqzfAvuz Ip xt zodziIzpfz, lpz lm hjz xluh frzAi kAtu lm IczphImtIpy A fiAfwdlh\nIu hjilvyj xAhj. pl xAhhzi hjz udzfImIf uvqezfh, hjz fiAfwdlhu ArkAtu zIhjzi\nAalIc li ufizk vd hjz xAhj. kjzhjzi Ih'u hjz \"xzifvit fAvuzu AvhIux\" mlrwu, hjz\nazrIwlauwIApu, fizAhIlpIuhu, Arh-xzcIfIpz svAfwu, izdvqrIfAp dlrruhziu, li\nufIzphlrlyIuhu - tlv fAp ArkAtu izflypInz hjz fiAfwdlhu qt hjzIi xAhj. ul I Ax\nylIpy hl cl xt qzuh hl dilaIcz A alIfz lm xAhjzxAhIfAr uApIht - qlhj qt ujlkIpy\nkjAh'u kilpy kIhj hjz qAc xAhj urld dvxdzc lvh qt hjz rllpIzu, Apc qt ujlkIpy\njlk yllc xAhj kliwu.\n<\/pre>\n
         Now, in the first sentence, we see two two-letter words side by side starting with “I”. There are only three common two-letter words starting with “I”: “if”, “is”, and “it”. Since it’s a pair of words, we can consider the
        \ndifferent permutations: “it is”, “it if”, “if it”, “if is”, “is if”, and “is it”. “it if” and “if is” are both very unlikely. We can’t discard them out
        \nof hand, but we can consider them very unlikely. “is it” would usually imply
        \na question, but there’s no question mark. So it’s probably either “if it”, or “it is”. Looking into the next line, where we see “hjAh”, we can say that “h\/F” is very unlikely, because there are very few words in english that start and end with an “f”, but a lot that start and end with a T. So we’ll guess that the phrase is “it is”, and “h\/T” and “u\/S”.<\/p>\n
        \nI czfIczc IT IS AqlvT TIxz Tl STAiT vd xt lkp qrly. lpz\nTjIpy TjAT I jAaz plTIfzc Ip xt TIxz qilkSIpy Tjz qrlylSdjziz IS TjAT Tjziz Aiz\nA kjlrz rlT lm TziiImIf SfIzpfz qrlyS lvT Tjziz: liAf, djAitpyvrA, AzTIlrlyt,\nevST Tl pAxz A mzk. qvT Tjziz IS plT pzAirt Sl xvfj lvT Tjziz czcIfATzc Tl xATj\n- Apc Ip dAiTIfvrAi Tl Tjz xISvSz lm xATj. I TjIpw TjAT TjAT IS A cAxp SjAxz,\nqzfAvSz Ip xt zodziIzpfz, lpz lm Tjz xlST frzAi kAtS lm IczpTImtIpy A fiAfwdlT\nIS Tjilvyj xATj. pl xATTzi Tjz SdzfImIf SvqezfT, Tjz fiAfwdlTS ArkAtS zITjzi\nAalIc li Sfizk vd Tjz xATj. kjzTjzi IT'S Tjz \"xzifvit fAvSzS AvTISx\" mlrwS, Tjz\nazrIwlaSwIApS, fizATIlpISTS, ArT-xzcIfIpz svAfwS, izdvqrIfAp dlrrSTziS, li\nSfIzpTlrlyISTS - tlv fAp ArkAtS izflypInz Tjz fiAfwdlTS qt TjzIi xATj. Sl I Ax\nylIpy Tl cl xt qzST Tl dilaIcz A alIfz lm xATjzxATIfAr SApITt - qlTj qt SjlkIpy\nkjAT'S kilpy kITj Tjz qAc xATj Srld dvxdzc lvT qt Tjz rllpIzS, Apc qt SjlkIpy\njlk yllc xATj kliwS.\n<\/pre>\n
         Now, we see “Tl” in the first line. There’s only one common two-letter
        \nword starting with “T”: “to”. So we’ll do “l\/O”. We also see “STAiT”,
        \nwhich looks like it’s probably “start”; and we see that “i” occurs very frequently in the cipher-text; “R” is one of the most common consonants in english. So we’ll also add “i\/R”.<\/p>\n
        \nI czfIczc IT IS AqOvT TIxz TO START vd xt Okp qrOy. Opz\nTjIpy TjAT I jAaz pOTIfzc Ip xt TIxz qROkSIpy Tjz qrOyOSdjzRz IS TjAT TjzRz ARz\nA kjOrz rOT Om TzRRImIf SfIzpfz qrOyS OvT TjzRz: ORAf, djARtpyvrA, AzTIOrOyt,\nevST TO pAxz A mzk. qvT TjzRz IS pOT pzARrt SO xvfj OvT TjzRz czcIfATzc TO xATj\n- Apc Ip dARTIfvrAR TO Tjz xISvSz Om xATj. I TjIpw TjAT TjAT IS A cAxp SjAxz,\nqzfAvSz Ip xt zodzRIzpfz, Opz Om Tjz xOST frzAR kAtS Om IczpTImtIpy A fRAfwdOT\nIS TjROvyj xATj. pO xATTzR Tjz SdzfImIf SvqezfT, Tjz fRAfwdOTS ArkAtS zITjzR\nAaOIc OR SfRzk vd Tjz xATj. kjzTjzR IT'S Tjz \"xzRfvRt fAvSzS AvTISx\" mOrwS, Tjz\nazrIwOaSwIApS, fRzATIOpISTS, ArT-xzcIfIpz svAfwS, RzdvqrIfAp dOrrSTzRS, OR\nSfIzpTOrOyISTS - tOv fAp ArkAtS RzfOypInz Tjz fRAfwdOTS qt TjzIR xATj. SO I Ax\nyOIpy TO cO xt qzST TO dROaIcz A aOIfz Om xATjzxATIfAr SApITt - qOTj qt SjOkIpy\nkjAT'S kROpy kITj Tjz qAc xATj SrOd dvxdzc OvT qt Tjz rOOpIzS, Apc qt SjOkIpy\njOk yOOc xATj kORwS.\n<\/pre>\n
         We’re starting to see some really good progress. Some short words are
        \nstarting to pop up, and lots of places where the correct word is pretty obvious.
        \nFor example, “TjAT” is clearly “THAT”, so we know “j\/H”. And we see lots of
        \nthree letter words, starting with “T”. The most common three-letter word
        \nstarting with “T” is “the”, and we see lots of three-letter words with “T”
        \nfollowed by “j”; if our guess that “j” encodes “H” is correct, that means that
        \n“z” almost certainly encodes “E”.<\/p>\n
         I cEfIcEc IT IS AqOvT TIxE TO START vd xt Okp qrOy. OpE THIpy THAT I HAaE\npOTIfEc Ip xt TIxE qROkSIpy THE qrOyOSdHERE IS THAT THERE ARE A kHOrE rOT Om\nTERRImIf SfIEpfE qrOyS OvT THERE: ORAf, dHARtpyvrA, AETIOrOyt, evST TO pAxE A\nmEk. qvT THERE IS pOT pEARrt SO xvfH OvT THERE cEcIfATEc TO xATH - Apc Ip\ndARTIfvrAR TO THE xISvSE Om xATH. I THIpw THAT THAT IS A cAxp SHAxE, qEfAvSE Ip\nxt EodERIEpfE, OpE Om THE xOST frEAR kAtS Om IcEpTImtIpy A fRAfwdOT IS THROvyH\nxATH. pO xATTER THE SdEfImIf SvqeEfT, THE fRAfwdOTS ArkAtS EITHER AaOIc OR SfREk\nvd THE xATH. kHETHER IT'S THE \"xERfvRt fAvSES AvTISx\" mOrwS, THE aErIwOaSwIApS,\nfREATIOpISTS, ArT-xEcIfIpE svAfwS, REdvqrIfAp dOrrSTERS, OR SfIEpTOrOyISTS - tOv\nfAp ArkAtS REfOypInE THE fRAfwdOTS qt THEIR xATH. SO I Ax yOIpy TO cO xt qEST TO\ndROaIcE A aOIfE Om xATHExATIfAr SApITt - qOTH qt SHOkIpy kHAT'S kROpy kITH THE\nqAc xATH SrOd dvxdEc OvT qt THE rOOpIES, Apc qt SHOkIpy HOk yOOc xATH kORwS.\n<\/pre>\n
         Looking very good. We can see from things like “OvT” that “v” is cipher for “U”; from “HAaE”, we can guess that “a” is cipher for “V”; from “OpE”, we can guess that “p” is cipher for “N”.<\/p>\n
        \nI cEfIcEc IT IS AqOUT TIxE TO START Ud xt OkN qrOy. ONE\nTHINy THAT I HAVE NOTIfEc IN xt TIxE qROkSINy THE qrOyOSdHERE IS THAT THERE ARE\nA kHOrE rOT Om TERRImIf SfIENfE qrOyS OUT THERE: ORAf, dHARtNyUrA, AETIOrOyt,\neUST TO NAxE A mEk. qUT THERE IS NOT NEARrt SO xUfH OUT THERE cEcIfATEc TO xATH\n- ANc IN dARTIfUrAR TO THE xISUSE Om xATH. I THINw THAT THAT IS A cAxN SHAxE,\nqEfAUSE IN xt EodERIENfE, ONE Om THE xOST frEAR kAtS Om IcENTImtINy A fRAfwdOT\nIS THROUyH xATH. NO xATTER THE SdEfImIf SUqeEfT, THE fRAfwdOTS ArkAtS EITHER\nAVOIc OR SfREk Ud THE xATH. kHETHER IT'S THE \"xERfURt fAUSES AUTISx\" mOrwS, THE\nVErIwOVSwIANS, fREATIONISTS, ArT-xEcIfINE sUAfwS, REdUqrIfAN dOrrSTERS, OR\nSfIENTOrOyISTS - tOU fAN ArkAtS REfOyNInE THE fRAfwdOTS qt THEIR xATH. SO I Ax\nyOINy TO cO xt qEST TO dROVIcE A VOIfE Om xATHExATIfAr SANITt - qOTH qt SHOkINy\nkHAT'S kRONy kITH THE qAc xATH SrOd dUxdEc OUT qt THE rOONIES, ANc qt SHOkINy\nHOk yOOc xATH kORwS.\n<\/pre>\n
         From “SfIENfE”, we can guess that “f” is cipher for “C”;
        \nfrom “xATH”, “TIxE”, and “NAxE” we can guess that “x” is cipher for M.
        \nWe can see “NEARrt”, which should be either “NEARBY” or “NEARLY”; L occurs
        \nmuch more frequently than B, and some of the other instances of “r” appear likely to be “L”s. <\/p>\n
        \nI cECIcEc IT IS AqOUT TIME TO START Ud MY OkN qLOy. ONE\nTHINy THAT I HAVE NOTICEc IN MY TIME qROkSINy THE qLOyOSdHERE IS THAT THERE ARE\nA kHOLE LOT Om TERRImIC SCIENCE qLOyS OUT THERE: ORAC, dHARYNyULA, AETIOLOyY,\neUST TO NAME A mEk. qUT THERE IS NOT NEARLY SO MUCH OUT THERE cEcICATEc TO MATH\n- ANc IN dARTICULAR TO THE MISUSE Om MATH. I THINw THAT THAT IS A cAMN SHAME,\nqECAUSE IN MY EodERIENCE, ONE Om THE MOST CLEAR kAYS Om IcENTImYINy A CRACwdOT\nIS THROUyH MATH. NO MATTER THE SdECImIC SUqeECT, THE CRACwdOTS ALkAYS EITHER\nAVOIc OR SCREk Ud THE MATH. kHETHER IT'S THE \"MERCURY CAUSES AUTISM\" mOLwS, THE\nVELIwOVSwIANS, CREATIONISTS, ALT-MEcICINE sUACwS, REdUqLICAN dOLLSTERS, OR\nSCIENTOLOyISTS - YOU CAN ALkAYS RECOyNInE THE CRACwdOTS qY THEIR MATH. SO I AM\nyOINy TO cO MY qEST TO dROVIcE A VOICE Om MATHEMATICAL SANITY - qOTH qY SHOkINy\nkHAT'S kRONy kITH THE qAc MATH SLOd dUMdEc OUT qY THE LOONIES, ANc qY SHOkINy\nHOk yOOc MATH kORwS.\n<\/pre>\n
         You should be able to finish it from here: there are a ton of obvious
        \nsubstittions now: “c\/D”, “q\/B”, “y\/G”, “d\/P”, “m\/F”, etc. You should also
        \nnow really understand why simple substition is such a poor encryption technique: look how easily we just cracked that! In fact, there’s a
        \ncryptanalysis proof that on average, you need less that 50 characters of
        \ncipher-text to decode a simple substitution for english.<\/p>\n
         (The clear-text is the text of the first-ever post on the original version
        \nof this blog, with contractions and paragraph breaks removed.)<\/p>\n","protected":false},"excerpt":{"rendered":"
        To understand why serious encryption algorithms are so complex, and why it’s so important to be careful with the critical secrets that make an encryption system work, it’s useful to understand something about how people break encryption systems. The study of this is called cryptanalysis, and it’s an amazingly fascinating field of applied mathematics. I’m […]<\/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-670","post","type-post","status-publish","format-standard","hentry","category-encryption"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p4lzZS-aO","jetpack_sharing_enabled":true,"jetpack_likes_enabled":true,"_links":{"self":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/670","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=670"}],"version-history":[{"count":0,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/670\/revisions"}],"wp:attachment":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/media?parent=670"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/categories?post=670"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/tags?post=670"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}