Skillz Feb 07 Winning Entry – Technical

Viewing 2 reply threads
  • Author
    Posts
    • #1268
      Don Donzal
      Keymaster

      Gregory Fleischer

      ANSWERS

      1) What is the significance of various numbers in the story, including
        the speech patterns of the goose and Templeton?

      The various numbers represent different the first several digits of mathematical constants:

        1,618.03: 1.61803 is the golden ratio
        2,718.28: 2.71828 is e (the base of the natural log)
        3141592: 3.141592 is pi

      The speech patterns of the goose and Templeton are the beginning of well known mathematical sequences:

        the goose’s repetitions: the prime numbers (2,3,5,7,11)
        the length of Templeton’s words: Fibonacci numbers (1,1,2,3,5,8,13)

      2) How had Charlotte and the Geography Ants fooled Lurvy’s
        integrity-checking script?

      The integrity checking script was fooled because the two web-pages have the same MD5 sum.  The web pages begin with sequences that differ but have the same calculated MD5 sum value; this is a collision in the hashing algorithm.  Since the remainder of each web page is identical, the MD5 sum values are calculated the same for either page.  Each page uses JavaScript to display a different web page based on the initial sequence on the page.

      3) Why did Charlotte have to change the website before the
        integrity-checking script ran for the first time? Why couldn’t she
        deface it later?

      Charlotte had to change the web page first because the attack she is using is based on finding MD5 collisions.  She is exploiting the fact that for MD5, if H(m) == H(n), then H(m + y) == H(n + y).  It couldn’t be defaced later because doing so would have required a pre-image attack, which hasn’t yet been shown to be feasible.

      4) How should Lurvy’s script have functioned to improve its ability to
        detect the kinds of alterations made by Charlotte?

      Lurvy’s script should have used additional hash functions to the response and compared those as well.  For example, in addition to MD5, the script could also have calculated a hash using SHA1 (or RipeMD-160, Tiger, Haval, etc.).  The probability of several hash functions being subverted simultaneously is slim.

      5) What was Charlotte’s proposal to Lurvy for saving Wilbur?

      Charlotte’s proposal is that she’ll work as a web consultant for Lurvy at a customer rate of $150/hour but will only charge Lurvy $50.  This would result in a profit for Lurvy of $100 per hour or $4000 per 40 hour week.

      ANALYSIS

      1) “Numberology”

      Mathematical constants:

        1.61803: http://www.google.com/search?q=the+golden+ratio
        2.71828: http://www.google.com/search?q=e
        3.141592: http://www.google.com/search?q=pi

      Sequences:

        Goose:

          “Lurvy-urvy is even using the phrases from Charlotte’s old webs to
        try to sell Wilbur,”
            “Why, it’s unseemly-eemly-eemly.”
            “We’ve got-ot-ot-ot-ot to come up with some way to save the
            pig-ig-ig-ig-ig-ig-ig.  But, how can we do it without
            Charlotte-arlotte-arlotte-arlotte-arlotte-arlotte-arlotte-arlotte-arlotte-arlotte-arlotte?”

        Lurvy-urvy = 2
        unseemly-eemly-eemly = 3
        got-ot-ot-ot-ot = 5
        pig-ig-ig-ig-ig-ig-ig = 7
        Charlotte-arlotte-arlotte-arlotte-arlotte-arlotte-arlotte-arlotte-arlotte-arlotte-arlotte
        = 11

        The prime numbers:
        http://www.research.att.com/~njas/sequences/?q=2,3,5,7,11

        Templeton:

            “O, I do not enjoy starving progressively!”

        O = 1
        I = 1
        do = 2
        not = 3
        enjoy = 5
        starving  = 8
        progressively = 13

        Fibonacci numbers:
        http://www.research.att.com/~njas/sequences/?q=1,1,2,3,5,8,13

      2) Charlotte’s Web Pages

      Charlotte created her web pages using the ‘confoo’ tool written by Dan Kaminsky (http://www.doxpara.com/research/md5/confoo.pl).  This utility will retrieve two web pages and encode the respective contents to be built using JavaScript.  Two new files are created: “t1.html” and “t2.html”.  Each begins with one of the two Wang MD5 collisions (http://eprint.iacr.org/2004/199.pdf).  When either t1.html or t2.html is requested, the JavaScript will execute and determine which collision value is present at the beginning of the HTML and then decode and display the appropriate original page.

      The original web pages can be retrieved be writing a script to decode the JavaScript values.  The confoo tool stores the original web page URL values in a BASE tag so that images and other external resources are properly displayed, and these can be retrieved.

      $ ./deconfoo.rb t1.html
      original t1 url most likely
      http://www.counterhack.net/WilburPorkYumYum/Buy%20Yummy%20Pork.html
      original t2 url most likely
      http://www.counterhack.net/DoNotBuyWilbur/Do%20Not%20Buy%20Wilbur%21.html

      We’ll mirror these web pages for good measure:

      $ wget -q -m ‘http://www.counterhack.net/WilburPorkYumYum/Buy%20Yummy%20Pork.html’
      $ wget -q -m ‘http://www.counterhack.net/DoNotBuyWilbur/Do%20Not%20Buy%20Wilbur%21.html’
      $ find http://www.counterhack.net/ -type f -exec sha1sum {} ;
      e50119cd23a878c22b99e544c55a3e4ad5dfea22
      http://www.counterhack.net/WilburPorkYumYum/Buy Yummy Pork_files/terrific.jpg
      00f4d45232c4518af93ed9c73a0113203474d2a7
      http://www.counterhack.net/WilburPorkYumYum/Buy Yummy Pork_files/Buy Yummy Pork.css 34ecf71cbd64c89ca8384efb4875f04f5cbf0bbf
      http://www.counterhack.net/WilburPorkYumYum/Buy Yummy Pork_files/somepig.jpg
      7eb3ccf2b98024e4c8e11772a7cd3ed160fb71d1
      http://www.counterhack.net/WilburPorkYumYum/Buy Yummy Pork_files/shapeimage_1.jpg 34e41f78ae373847cbd304192eb5ecf63eb1336c
      http://www.counterhack.net/WilburPorkYumYum/Buy Yummy Pork_files/Buy Yummy Pork.js
      5b812adab06b6cefbf43229f268e9c69f372b1d9
      http://www.counterhack.net/WilburPorkYumYum/Buy Yummy Pork.html 06a8cc83c642a677cdaad8b4c52217c54bf54ecc
      http://www.counterhack.net/DoNotBuyWilbur/Do Not Buy Wilbur!_files/Do Not Buy Wilbur!.js
      7eb3ccf2b98024e4c8e11772a7cd3ed160fb71d1
      http://www.counterhack.net/DoNotBuyWilbur/Do Not Buy Wilbur!_files/shapeimage_1.jpg e7750d9655991f160e7bc75f7a077dfb9b13e0fa
      http://www.counterhack.net/DoNotBuyWilbur/Do Not Buy Wilbur!_files/somebook.jpg 4c9c03ab613108d603ff31627f69a6c3d43f3a7d
      http://www.counterhack.net/DoNotBuyWilbur/Do Not Buy Wilbur!_files/Do Not Buy Wilbur!.css
      7d8fd716d49284ef445fc9ce93d8d73ad3a54213
      http://www.counterhack.net/DoNotBuyWilbur/Do Not Buy Wilbur!_files/counterhackreloadedsteg.png
      0b5b61b77383671a72e16766262b05358a303dcc
      http://www.counterhack.net/DoNotBuyWilbur/Do Not Buy Wilbur!.html

      3) Charlotte’s Hack

      One of the problems with Charlotte’s approach is that the web pages don’t display properly when JavaScript is not enabled in the browser, or when the page is viewed with a text-based browser.

      The differences are readily apparent:

      $ elinks -dump http://counterhack.net/t0.html | md5sum
      9e9fb7b5bab410c3aa9ce6efe7a55d88  –

      $ elinks -dump http://counterhack.net/t1.html | md5sum
      27e81c4f9ea99ace20dd53150f401473  –

      $ elinks -dump http://counterhack.net/t2.html | md5sum 6ae0c7b50e96b7b35c2ed24768c41cff  –

      Visually, the pages differ as well.

      $ elinks -dump ‘http://counterhack.net/t0.html’ | tr -c ‘[[:print:]n]’ ‘.’

        ..
        ..
        ..
        Remember These Webs?
        ..
        Last year, we discovered these mysterious webs, which described the
        succulent flavor of Wilbur the pig. Now, you can buy this fine animal and
        enjoy numerous feasts, such as Apple sausage, Asparagus pork chops,
        Avocado pork rolls, Bacon, Edamame pork sandwiches, Eggplant pork loin,
        Marinated pork roast, Ribs, and Wild rice pork soup. To make a bid on
        Wilbur, please go to Meat-Bay, and bid on auction ID 3141592.
        ..

      $ elinks -dump ‘http://counterhack.net/t1.html’ | tr -c ‘[[:print:]n]’ ‘.’

        .1……i=…../….F~.@.X>….U.4.
        …….%qAZ.Q%……….7<[..>1V4.[.m..6….S…….9c..H….3B.W~..T.p..
        …!…….e+o.*p

      $ elinks -dump ‘http://counterhack.net/t2.html&#8217; | tr -c ‘[[:print:]n]’ ‘.’

        .1……i=…../….F~.@.X>….U.4.
        …….%.AZ.Q%……..r.7<[..>1V4.[.m..6….S.4…..9c..H….3B.W~..T.p.(
        …!…….e.o.*p

      However, there have been significant advances in finding MD5 collisions since the confoo tool was written.  In particular, it has been shown to be possible to create documents with chosen prefixes (http://www.win.tue.nl/hashclash/ChosenPrefixCollisions/).
      Additionally, improvements in the differential attacks have allowed for vast speed-ups in finding collisions.  What used to take super-computers can now be performed on laptops (see http://cryptography.hyperlink.cz/MD5_collisions.html).

      With that in mind, it should be possible to construct two web pages that have the same MD5 sum both in source form as well as when the page is viewed without Javascript.  Furthermore, it might be desirable to display the expected page as a default.  To do this, we take some of the ideas from the original confoo tool and create a new confoo utility: “confoonu”.

      $ ./confoonu.rb
      http://www.counterhack.net/WilburPorkYumYum/Buy%20Yummy%20Pork.html&#8217; ‘http://www.counterhack.net/DoNotBuyWilbur/Do%20Not%20Buy%20Wilbur%21.html&#8217; ‘http://www.counterhack.net/WilburPorkYumYum/Buy%20Yummy%20Pork.html&#8217;

      Check the MD5 sums:

      $ elinks -source http://pseudo-flaw.net/cws/t1.html | md5sum a0ca42e12c31ee1cdd3c0e474f83244d  –

      $ elinks -source http://pseudo-flaw.net/cws/t2.html | md5sum a0ca42e12c31ee1cdd3c0e474f83244d  –

      $ elinks -dump http://pseudo-flaw.net/cws/t1.html | md5sum
      9e9fb7b5bab410c3aa9ce6efe7a55d88  –

      $ elinks -dump http://pseudo-flaw.net/cws/t2.html | md5sum
      9e9fb7b5bab410c3aa9ce6efe7a55d88  –

      To compare to the original:

      $ elinks -dump http://counterhack.net/t0.html | md5sum
      9e9fb7b5bab410c3aa9ce6efe7a55d88  –

      And visually, a much better match.

      $ elinks -dump http://pseudo-flaw.net/cws/t2.html | tr -c ‘[[:print:]n]’ ‘.’
        ..
        ..
        ..
        Remember These Webs?
        ..
        Last year, we discovered these mysterious webs, which described the
        succulent flavor of Wilbur the pig. Now, you can buy this fine animal and
        enjoy numerous feasts, such as Apple sausage, Asparagus pork chops,
        Avocado pork rolls, Bacon, Edamame pork sandwiches, Eggplant pork loin,
        Marinated pork roast, Ribs, and Wild rice pork soup. To make a bid on
        Wilbur, please go to Meat-Bay, and bid on auction ID 3141592.
        ..

      4) Lurvy’s Script

      There are weaknesses in several hash algorithms when taken in isolation.  Again, the Wang results provide some examples of this.
      By utilizing multiple hash functions at the same time, the probability that all of them have been subverted is greatly reduced.

      For example, a simple shell script demonstrates this:

      $ for page in ‘t1.html’ ‘t2.html’; do
          echo $page
          for hash in md5 sha1 ripemd160; do
              printf “%12s: ” $hash
              curl -s “http://counterhack.net/$page&#8221; | openssl dgst -$hash
          done
          echo “”
      done

      t1.html
              md5: e0dbee13c331b6deee2db071c85baf56
              sha1: 8f8a1c9cdac611709b2d72b3433c83be52b1c399
        ripemd160: ed160d7d3e33e351853f7d0b27fa693660dc9bc9

      t2.html
              md5: e0dbee13c331b6deee2db071c85baf56
              sha1: 3695509a6aab4fc1f9183748e4c779d8bb3653dd
        ripemd160: b08acd2b072ddbbc7b5732860ece7de8c5781c9b

      NIST has begun the process of searching for a new hash function by holding a public competition similar to the AES competition (see http://csrc.nist.gov/pki/HashWorkshop/timeline.html).  I would assume some of the recently disclosed differential attacks will be taken into account when designing the new hash functions so that in maybe six years a secure hash function will be available.

      5) Charlotte’s Proposal

      Using the hint given, download “Digital Invisible Ink Toolkit” from http://diit.sourceforge.net.&nbsp; Since this is a steganography tool, it is safe to assume that one of images on the website has something hidden in it.  The “counterhackreloadedsteg.png” file is the likely candidate based on the file name.

      Decoding the image requires a password, and an empty password doesn’t seem to work.  Going back to the web page, it is obvious that some words begin with letters in red:
          _B_acon
          _A_pple
          _A_vocado
          _R_ibs
          _A_sparagus
          _M_arinated
          _E_ggplant
          _W_ild
          _E_damame

      A password of “BAARAMEWE” doesn’t work but “baaramewe” does so we save off the file as “decoded”.

      (Aside: the phrase “baa-ram-ewe” is from the movie Babe but could also be a reference to the “Home” episode from The X-Files.)

      But what kind of file have we decoded?

      $ file decoded
      decoded: Microsoft Office Document
      $ mv decoded decoded.doc

      Maybe a quick look at the file is in order.  Generally, it isn’t a good idea to fire up Microsoft Office and look at some random Word document.  Instead, use ‘strings’ or some other text based method.

      $ tr -cd ‘[:print:]’ >*,)M Dbjbj==”WWDl$ VXXXXXX>XDrQ20CHCXCharlottes ProposalDear
      Mr. Lurvy,Now that I have got your attention, I have a proposal for you.  You are obviously a bright businessman, trying to make some money on the sale of Wilbur.  But, surely you must recognize the fleeting nature of that one-time sale.  I propose to you a better business model, one that can keep this farm profitable for years to come.Employ me, Charlotte the Spider, as a web site designer, contracting my services out for $150 per hour.  I will charge you only $ 50 per hour.  Thus, working only 40 hours per week, I can bring in more cash for you every single week than the one-time sale of Wilbur.
      If you are interested in my offer, please send e-mail to  HYPERLINK “mailto:charlotte@counterhack.net” charlotte@counterhack.net ,with the
      subject: CHARLOTTES PROPOSAL.Yours truly,CharlotteD0JjUjU&’pq+,9:DD 1h/ =!”#$%DyKcharlotte@counterhack.netyKBmailto:charlotte@counterhack.neti8@8NormalCJ_HaJmHsHtH Paragraph Font.U@.Hyperlink>*B*phD&’pq+,9:F00000000000DDDDX$FF3CF
      bC:Documents and SettingsskodoApplication DataMicrosoftWordAutoRecovery save of Document3.asd 4Z:PapersCharlotte’s Web SiteCharlotteProposal.doc@ggLGDg’D`@UnknownGz
      Times New Roman5Symbol3&z Arial”qhymz!202Charlotte s Proposal  Oh+’0t0
      Word DocumentMSWordDocWord.Document.89q

      Besides the main text of the document, there are a couple of other interesting pieces of information displayed:

        C:Documents and SettingsskodoApplication DataMicrosoftWordAutoRecovery save of Document3.asd
        Z:PapersCharlotte’s Web SiteCharlotteProposal.doc

      These are stored in saved-by history section of the document and are typically not readily apparent, but the information can be extracted.

      $ ./author-info.pl decoded.doc

      —=== Author(s) Information ===—
      1. (unknown) : C:Documents and SettingsskodoApplication DataMicrosoftWordAutoRecovery save of Document3.asd 2. (unknown) : Z:PapersCharlotte’s Web SiteCharlotteProposal.doc

      The author’s name isn’t present, but one could assume that the original document name was CharlotteProposal.doc.

      $ mv decoded.doc CharlotteProposal.doc

      A formatted version of the document text can be retrieved by using one of the available conversion programs: antiword, catdoc, wvWare, etc.

      $ antiword CharlotteProposal.doc

      Charlotte’s Proposal

      Dear Mr. Lurvy,

      Now that I have got your attention, I have a proposal for you.  You are obviously a bright businessman, trying to make some money on the sale of Wilbur.  But, surely you must recognize the fleeting nature of that one-time sale.  I propose to you a better business model, one that can keep this farm profitable for years to come.

      Employ me, Charlotte the Spider, as a web site designer, contracting my services out for $150 per hour.  I will charge you only $ 50 per hour.  Thus, working only 40 hours per week, I can bring in more cash for you every single week than the one-time sale of Wilbur.  If you are interested in my offer, please send e-mail to charlotte@counterhack.net ,with the subject: CHARLOTTE’S PROPOSAL.

      Yours truly,
      Charlotte

      Essentially, this is a shakedown letter.  This is similar to some so-called “security consultants” who exploit sites and then offer to fix the problems for a fee.  It would be questionable for Lurvy to employ a known hacker such as Charlotte who appears to have no qualms about computer trespass or extortion.

      * Scripts available from: http://pseudo-flaw.net/cws/
        deconfoo.rb : http://pseudo-flaw.net/cws/deconfoo.rb
        confoonu.rb : http://pseudo-flaw.net/cws/confoonu.rb
        author-info.pl : http://pseudo-flaw.net/cws/author-info.pl.txt

      Congrats and well done,
      Don

    • #12396
      gfleischer
      Participant

      I realized I never posted the utility I wrote to find the MD5 prefix collision.  I’ve updated http://pseudo-flaw.net/cws/ to include a link to http://pseudo-flaw.net/cws/find_md5_prefix_collision.tar.gz

      There is a README that describes the functionality, how to go about building it and some examples.

      I just thought somebody might find this useful and may come across this entry if searching for information about finding MD5 prefix collisions.

      -Greg

    • #12397
      Anonymous
      Participant

      Thanks for the link, and congrats again on winning the challenge. A very good technical answer indeed.

      Jim

Viewing 2 reply threads
  • You must be logged in to reply to this topic.

Copyright ©2021 Caendra, Inc.

Contact Us

Thoughts, suggestions, issues? Send us an email, and we'll get back to you.

Sending

Sign in with Caendra

Forgot password?Sign up

Forgot your details?