tag:blogger.com,1999:blog-15466174590939933192018-11-02T05:15:39.608-04:00RCE junkandrewlhttp://www.blogger.com/profile/15585896448040772484noreply@blogger.comBlogger69125tag:blogger.com,1999:blog-1546617459093993319.post-85304936857235005002012-02-08T02:04:00.001-05:002012-02-08T02:06:08.815-05:00Shmoocon 2012 "Blocky" (RE 400) Write-Up<a href="http://andrewl.dreamhosters.com/blog/2012-02-07/screenshot0.png"><img style="display:block; margin:0px auto 10px; text-align:center;cursor:pointer; cursor:hand;width: 269px; height: 293px;" src="http://andrewl.dreamhosters.com/blog/2012-02-07/screenshot0.png" border="0" alt="" /></a><br /><div><span style="font-family: Georgia, serif; ">Here's a write-up of possibly one of the coolest challenges in the CTF!</span></div><span ><div><span ><br /></span></div>http://andrewl.dreamhosters.com/blog/2012-02-07/</span>andrewlhttp://www.blogger.com/profile/15585896448040772484noreply@blogger.com2tag:blogger.com,1999:blog-1546617459093993319.post-59286123145892657692011-04-06T23:41:00.029-04:002011-04-09T02:20:24.524-04:00Shmoocon 2011 Crypto Pack Solved! And Pairings And SAGE!I'm happy to announce a thorough and impressive solution to all the Shmoocon 2011 cryptography challenges by crackmes.de denizen Dcoder.<br /><a href="http://1.bp.blogspot.com/-KjP_VbQWzB4/TZ6y5gvaMTI/AAAAAAAAAA8/GtEe14FqUcU/s1600/dcoder_sol_screenshot.png" onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}"><img src="http://1.bp.blogspot.com/-KjP_VbQWzB4/TZ6y5gvaMTI/AAAAAAAAAA8/GtEe14FqUcU/s400/dcoder_sol_screenshot.png" border="0" alt="" id="BLOGGER_PHOTO_ID_5593104488351805746" style="display: block; margin-top: 0px; margin-right: auto; margin-bottom: 10px; margin-left: auto; text-align: center; cursor: pointer; width: 400px; height: 219px; " /></a><div><a href="http://1.bp.blogspot.com/-KjP_VbQWzB4/TZ6y5gvaMTI/AAAAAAAAAA8/GtEe14FqUcU/s1600/dcoder_sol_screenshot.png" onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}"></a><br />Not long after Dcoder's solve, user ged_ posted valid serials for his name, but sadly never supplied an explanation of his methods.<br /><br />Like stated previously, the choice of python and the simplicity of the first few challenges were intended to entice contenders into actually doing the challenges. The 4'th and 5'th challenge were to inject some new material into the keygenme problem space and that's what I'll discuss here.<br /><br />Challenge 4 is a large rational function calculating the "multiply-by-m" map of a point on an elliptic curve. Formulas exist to add and double points, so it's sensible that they may be composed to derive formulas for multiplication by a given coefficient. This is just a giant formula for multiplying by 13. No way could you take care of the algebra by hand: I used SAGE's EllipticCurve function multiplication_by_m() which Dcoder independently used when he suggests recreating the map for verification. A guessing game wasn't intended: the degree of the polynomial being 169 (13<sup>2</sup>) is a clue. Blackboxing the function is even feasible.<br /><br />Challenge 5 is the BLS short signature scheme using pairings on elliptic curves. Pairings are freaking magic and here I'll try to explain why. We'll have the typical mapping from an elliptic curve group (where the group operation is written as addition and thus repeated operations are written as multiplication) to the multiplicative group of an extension field (where repeated operations are written as exponentiation). Thus we write the bilinear property as:<br /><br />e(a<b>P</b>, b<b>Q</b>) = e(<b>P</b>,<b>Q</b>)<sup>ab</sup><br /><br />So the map doesn't care if you first multiply the points and then ask for output, or if you ask for the output and then exponentiate the result. Why is a mapping with this property useful?<br /><br />Recall the computational DH problem (CDH) by thinking of the eavesdropper's perspective of an DH key exchange. Eve views <b>P</b>, a<b>P</b>, and b<b>P</b>, but cannot compute the shared secret ab<b>P</b>. But if Eve were handed the shared secret among a thousand other random group elements, could she discern ab<b>P</b> from the decoys? This is called the decision DH problem (DDH) and is solvable if the group is equipped with a pairing. How? Given (<b>P</b>, a<b>P</b>, b<b>P</b>, ab<b>P</b>) Eve tests e(<b>P</b>, ab<b>P</b>) = e(a<b>P</b>, b<b>P</b>) = e(<b>P</b>,<b>P</b>)<sup>ab</sup>.<br /><br />Now look at it from a public-key standpoint. Suppose I publish <b>E</b>=<<b>G</b>>, x<b>G</b> but keep x secret. You could challenge my claim of knowing x by asking me to multiply it on a new point <b>P</b>. I'd return x<b>P</b>, just not x. You'd then have (<b>G</b>, x<b>G</b>, <b>P</b>, x<b>P</b>) and could verify e(<b>G</b>, x<b>P</b>) = e(x<b>G</b>, <b>P</b>) = e(<b>G</b>,<b>P</b>)<sup>x</sup>.<br /><br />If this isn't magic enough, think now how you can operate on e(<b>G</b>,<b>P</b>)<sup>x</sup> without knowing x. The pairing kind of exposes the x for involvement in future computations without explicitly revealing its value. Three-party key agreement is the clearest use of this property. When the three parties {A,B,C} compute respectively {e(b<b>G</b>,c<b>G</b>)<sup>a</sup>, e(a<b>G</b>,c<b>G</b>)<sup>b</sup>, e(a<b>G</b>,b<b>G</b>)<sup>c</sup>}, everybody arrives at e(<b>G</b>,<b>G</b>)<sup>abc</sup>, yet each party knows only the value of their own {a,b,c}.<br /><br />The BLS signature scheme is is exactly the same as the first example with DDH above, except that the challenge point <b>P</b> is the message mapped to a point, and the x<b>P</b> is renamed the signature <b>S</b>. Verifying the signature is verifying the tuple (<b>G</b>, x<b>G</b>, <b>P</b>, <b>S</b>).<br /><br />There are a few pairings now, but the Weil pairing is seemed like the "hello world" of pairings and still it was very difficult to get working. I owe mostly to <a href="http://cs.stanford.edu/~blynn/">Ben Lynn</a> for writing his <a href="http://crypto.stanford.edu/pbc/thesis.html">thesis</a> in a clear, explanatory fashion and not being too "math leet" to include worked examples. Also, I had a bug when evaluating points on lines that went through infinity and couldn't have figured it out without <a href="http://www.mollerhansen.com/">David Hanson</a>'s Weil pairing implementation in SAGE.<br /><br />Producing curve parameters is an entirely separate problem. The <a href="http://www.cryptojedi.org/papers/pfcpo.pdf">paper on BN (Barreto, Naehrig) curves</a> had an algorithm that wasn't too difficult to type out and test. Here's the <a href="http://andrewl.dreamhosters.com/archive/20412991.txt">implementation</a> in SAGE. Finally crypto5 can be constructed:<br /><pre>sage: [E,g1] = search_embed_12(64)<br />Elliptic Curve defined by y^2 = x^3 + 13 over Finite Field of size 9524793152874449521<br />(1 : 4577206343548535956 : 1)<br />sage: r = E.order()<br />sage: is_prime(r)<br />True<br /></pre>As expected from the BN curve algorithm, we have a prime order curve. This means that r=#<b><i>E</i></b> and every point is in the r-torsion <b><i>E</i></b>[r]. This r-torsion's definition is a subgroup whose elements' orders divide r, but here every elements' order is exactly r. Call this group by a new name G1 = <<b>g1</b>> to detach it from <b><i>E</i></b> since we'll be moving <b><i>E</i></b> over larger fields.<br /><br />Over increasingly extended fields, #<b><i>E</i></b> grows, fast. Not until extension 12 (the embedding degree) does the group <b><i>E</i></b>(F<sub>p<sup>12</sup></sub>) contain <b><i>E</i></b>[r<sup>2</sup>]. </div><div><pre>sage: E=EllipticCurve(GF(9524793152874449521^12,'a'),[0,0,0,0,13])<br />sage: E.order()<br />557527939388338455999335177184553128648411435525495183120877629267756649506692825601416365268161565197227820626524244139422343537066988585815195692298420149498809296111861768128843274828063908967761768686256781963953791177011200<br /></pre>That's a lot of points! <b><i>E</i></b>[r<sup>2</sup>] is the direct product of <b>G1</b> and some other r-sized subgroup in <b><i>E</i><span class="Apple-style-span" style="font-weight: normal;"> we'll call G2</span></b>. To find G2, we take a random point and multiply by #<b><i>E</i></b>/r<sup>2</sup>.<br /><pre>sage: g2=E.random_point() * Integer(E.order()/r^2)<br />sage: g2.order()<br />9524793149788155121<br />sage: g2<br />(28930072329430674*a^11 + 3476916985694553167*a^10 + 7416446501236864153*a^9 + 1546806533803993509*a^8 + 9258625410126221791*a^7 + 3946459769382694037*a^6 + 9082757750092742366*a^5 + 4925994372571715422*a^4 + 9356115311475410715*a^3 + 3239246275650681784*a^2 + 2530023797852594208*a + 2582477270547956977 : 4569041207989982512*a^11 + 392122047555439583*a^10 + 53398003196643395*a^9 + 2471082114350274565*a^8 + 3769727620341931341*a^7 + 2253879482993753613*a^6 + 7323759157123465679*a^5 + 1956558743620835276*a^4 + 1065433853209237195*a^3 + 8009494946720473686*a^2 + 8874621118513866374*a + 544373368025887171 : 1)<br /></pre>We see that <b>g2</b> is not in G1 and its order is the prime r so G2 = <<b>g2</b>>. Now, <b>g1</b> and <b>g2</b> together form a sort of basis by which all of <b><i>E</i></b>[r<sup>2</sup>] can be generated; every element in <b><i>E</i></b>[r<sup>2</sup>] can be written as a*<b>g1</b> + b*<b>g2</b> where a,b from Z<sub>r</sub>.<br /><br />We'll have the pairing map G1 x G2 -> F<sub>p<sup>12</sup></sub>. The input groups must be different, otherwise the points will be linearly dependent and the pairing will become degenerate. G1's members' coordinates have a nice compact representation of a single ground field element while each of G2's members's coordinates require 12 ground field elements. The public key <b>P</b> should then live in G2 while the signature <b>S</b> lives in G1. Choose private key x and compute:<br /><pre>sage: x = 1223334444333221111<br />sage: P = g2*x<br />sage: P<br />(9234041514029458289*a^11 + 7779915664763212307*a^10 + 6346523241154805362*a^9 + 5513000999900352828*a^8 + 7183243026634094341*a^7 + 6887819078187130363*a^6 + 5522347192587339249*a^5 + 832499822664426562*a^4 + 1305341026780126317*a^3 + 5936146128578535690*a^2 + 474243480778556212*a + 6400173802196845754 : 4965553112357672903*a^11 + 3816268899954016796*a^10 + 359467867455554913*a^9 + 212427926173001815*a^8 + 5152204995298522178*a^7 + 915090504523216963*a^6 + 8111126461946895687*a^5 + 318194623178172360*a^4 + 8053089739653482422*a^3 + 171210160812342620*a^2 + 6985863117841018225*a + 122495515023342804 : 1)</pre>To convert a message (the user name input to the crackme) to a point in G1, we just convert the name to a number and multiply generator <b>g1</b>. Suppose the name converts to 123456, then the signature is simply:<br /><pre>sage: M = 123456*g1<br />sage: M<br />(5525487180627916384 : 8968938521026939071 : 1)<br />sage: S = x*M<br />sage: S<br />(7298443986699715260 : 507887173084537875 : 1)</pre>You can store just one of the coordinates and a bit to distinguish candidate roots when solving the other coordinate. Despite sections in the BN paper specifically aimed at helping the reader compress points by solving cube roots, I failed to understand and implement this in time and the crackme had to be supplied with both coordinates :( You can hardly call this a short signature. Anyways, verifying the signature now is verifying the DH tuple (<b>g2</b>, <b>P</b>, <b>M</b>, <b>S</b>) = (<b>g2</b>, x*<b>g2</b>, 123456<b>g1</b>, 123456x*<b>g1</b>). We compare e(x*<b>g2</b>, <b>M</b>) with e(<b>g2</b>, 123456x*<b>g1</b>) and hopefully get e(<b>g2</b>,<b>g1</b>)<sup>123456x</sup>:<br /><pre>sage: g2.weil_pairing(S,r)<br />3636921704439622827*a^11 + 7161351127997094877*a^10 + 7731397384313800342*a^9 + 2976376815617375612*a^8 + 6846986400478961310*a^7 + 7580008168259595715*a^6 + 715697510382978485*a^5 + 5707351599709597252*a^4 + 7748158347504684570*a^3 + 9039946616134562331*a^2 + 2408156042808436778*a + 72829371319520371<br />sage: P.weil_pairing(M,r)<br />3636921704439622827*a^11 + 7161351127997094877*a^10 + 7731397384313800342*a^9 + 2976376815617375612*a^8 + 6846986400478961310*a^7 + 7580008168259595715*a^6 + 715697510382978485*a^5 + 5707351599709597252*a^4 + 7748158347504684570*a^3 + 9039946616134562331*a^2 + 2408156042808436778*a + 72829371319520371<br />sage: g2.weil_pairing(g1,r) ^ (123456*x)<br />3636921704439622827*a^11 + 7161351127997094877*a^10 + 7731397384313800342*a^9 + 2976376815617375612*a^8 + 6846986400478961310*a^7 + 7580008168259595715*a^6 + 715697510382978485*a^5 + 5707351599709597252*a^4 + 7748158347504684570*a^3 + 9039946616134562331*a^2 + 2408156042808436778*a + 72829371319520371</pre>All the same result! Sanity check passed! Here's an attempt to diagram the entire process. Please don't trust this for correctness:<br /><br /><a href="http://3.bp.blogspot.com/-9vp1fQ_W0SY/TZ6xN3Kb4fI/AAAAAAAAAA0/GZiC2qCzZkI/s1600/pairing2.png" onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}"><img src="http://3.bp.blogspot.com/-9vp1fQ_W0SY/TZ6xN3Kb4fI/AAAAAAAAAA0/GZiC2qCzZkI/s400/pairing2.png" border="0" alt="" id="BLOGGER_PHOTO_ID_5593102638944870898" style="display: block; margin-top: 0px; margin-right: auto; margin-bottom: 10px; margin-left: auto; text-align: center; cursor: pointer; width: 400px; height: 300px; " /></a><div><g1><a href="http://3.bp.blogspot.com/-9vp1fQ_W0SY/TZ6xN3Kb4fI/AAAAAAAAAA0/GZiC2qCzZkI/s1600/pairing2.png" onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}"></a><br />To forge signatures... well that's the cracker's job. Read Dcoder's solution to learn how, along with quick ways to destroy the other challenges. Thanks and congratulations again to him, a clear champion among keygenners!</g1></div></div><div><g1><br /></g1></div><div><g1><a href="http://crackmes.de/users/andrewl.us/shmoocon_2011_crypto_challenge_pack/solution/dcoder">http://crackmes.de/users/andrewl.us/shmoocon_2011_crypto_challenge_pack/solution/dcoder</a></g1></div>andrewlhttp://www.blogger.com/profile/15585896448040772484noreply@blogger.com3tag:blogger.com,1999:blog-1546617459093993319.post-32171414226598689232011-04-06T22:11:00.007-04:002011-04-06T22:32:46.942-04:00[HBK]'s "Indiana Jones and the Wizard of Oz"<p>[difficulty: 2][protection: Stone Temple Puzzle]</p><div style="margin-left: auto; margin-right: auto"><br /><img src="http://1.bp.blogspot.com/-BWIktXvn-wk/TZ0eYnO36cI/AAAAAAAAAAs/T9a7bFy36ps/s320/indiana.png" /><br /></div><p>[HBK]'s first submissions is a fun and creative crackme. Don't let the difficulty fool you! "...to gain access to the cave, all the letter 'tablets' must be 'pushed' hmm.. no problem for indiana !!!" :)</p><a href="http://crackmes.de/users/hbk/indiana_jones_si_vrajitorul_din_oz/">http://crackmes.de/users/hbk/indiana_jones_si_vrajitorul_din_oz/</a>andrewlhttp://www.blogger.com/profile/15585896448040772484noreply@blogger.com0tag:blogger.com,1999:blog-1546617459093993319.post-55056197947343360682011-03-16T12:03:00.016-04:002011-03-22T01:47:55.381-04:00Wireshark as 010 Editor Alternative?<p>Why couldn't Wireshark's packet dissection capabilities be used as an open-source alternative to 010 Editor's binary template feature?</p><p>Pros:</p><ul><li>free, open source</li><li>C > 010's BT language</li><li>python support?</li></ul>Cons:<br /><ul><li>much harder to write</li><li>no editor, just viewer</li><li>extra preparation step</li><li>bugs</li></ul><div>To prepare a file for Wireshark's consumption, we must make it look like a PCAP capture file. Luckily <a href="http://wiki.wireshark.org/Development/LibpcapFileFormat">the PCAP format</a> is not too complicated. Data link type is chosen as DLT_USER0 which is supposedly reserved for private use. The rest of the details are implemented in this tool:<br /><br /><a href="http://2.bp.blogspot.com/-7q-kI4dgkps/TYg2mDWnzmI/AAAAAAAAAAk/0GEyNJsuJc8/s1600/asdf"><img src="http://2.bp.blogspot.com/-7q-kI4dgkps/TYg2mDWnzmI/AAAAAAAAAAk/0GEyNJsuJc8/s320/asdf" border="0" alt="" id="BLOGGER_PHOTO_ID_5586775365116218978" style="float: left; margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; cursor: pointer; width: 16px; height: 16px; " /></a><a href="http://andrewl.dreamhosters.com/archive/46757124.c">pcap-wrap.c</a> - wrap files in pcap capture format<br /><br /></div><div>The easiest way to setup an environment for building plugins is to <a href="http://www.wireshark.org/download.html">download the Wireshark source</a> (version 1.4.4 used here) and build it. It works very well being built in its source directory. Autogen, configure with --with-ssl, and make. In the root of the source tree will be the Wireshark executable and config.h which you will include in your plugin source to define preprocessor variables which are read in the other Wireshark includes. Plugins are just shared objects that are read (among other places) from ~/.wireshark/plugins/.</div><div><br /></div><div>Writing plugins is a real pain at first. See docs/README.developer. Each subtree must be described before its used. Each field, too, must be described in excruciating detail via an hf_register_info struct. I think the whole mess is justified by this line from the docs: "By strictly defining (or "typing") the data that can be attached to a proto tree, searching and filtering becomes possible." It's never fully explained that "items" are both the little data fields themselves, but also required for attachment by subtrees. A subtree cannot have subtree directly; it must have an item which can then have a subtree.<br /><br />Much code can be generated (will show in a future blog post) and in fact, some of the example plugins shown from epan/dissectors/* are generated. See packet-rrc.c which weights in at over 7MB! Anyways, as a proof of concept, I made a dissector for the <a href="https://ccrma.stanford.edu/courses/422/projects/WaveFormat/">canonical WAV file format</a>.<br /><br /><a href="http://2.bp.blogspot.com/-7q-kI4dgkps/TYg2mDWnzmI/AAAAAAAAAAk/0GEyNJsuJc8/s1600/asdf"><img src="http://2.bp.blogspot.com/-7q-kI4dgkps/TYg2mDWnzmI/AAAAAAAAAAk/0GEyNJsuJc8/s320/asdf" border="0" alt="" id="BLOGGER_PHOTO_ID_5586775365116218978" style="float: left; margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; cursor: pointer; width: 16px; height: 16px; " /></a><a href="http://andrewl.dreamhosters.com/archive/38116878.c">packet-wav.c</a> - dissector for canonical WAV files<br /><br />Nearly every rule in the coding style / compatibility section was broken in this code and there's probably leaks and security problems; just a disclaimer. So what does it look like?</div><div><br /></div><img src="http://andrewl.dreamhosters.com/archive/78542498.png" /><div><br /></div><div>You can click fields in the tree struct and the hex view will highlight the corresponding bytes and visa-versa.<br /><br />Now can we simplify things? If we forfeit the ability to do the advanced filter expressions, we can declare just one "dummy" field and subtree, and use its handle every time we add a field and subtree. Instead of relying on Wireshark to format the data for us (and using its complicated string lookup and bitfield mechanisms), we add most things with field type FT_NONE and with *_format() functions, supplying our own strings. Often you can just tack on additional data to an item via proto_item_append_text(). Here's take two:<br /><br /><a href="http://2.bp.blogspot.com/-7q-kI4dgkps/TYg2mDWnzmI/AAAAAAAAAAk/0GEyNJsuJc8/s1600/asdf"><img src="http://2.bp.blogspot.com/-7q-kI4dgkps/TYg2mDWnzmI/AAAAAAAAAAk/0GEyNJsuJc8/s320/asdf" border="0" alt="" id="BLOGGER_PHOTO_ID_5586775365116218978" style="float: left; margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; cursor: pointer; width: 16px; height: 16px; " /></a><a href="http://andrewl.dreamhosters.com/archive/59388721.c">packet-wav-new.c</a> - a clearer dissector for canonical WAV files<br /><br /></div><div><div>You'll also need:<br /><br /></div><a href="http://2.bp.blogspot.com/-7q-kI4dgkps/TYg2mDWnzmI/AAAAAAAAAAk/0GEyNJsuJc8/s1600/asdf"><img src="http://2.bp.blogspot.com/-7q-kI4dgkps/TYg2mDWnzmI/AAAAAAAAAAk/0GEyNJsuJc8/s320/asdf" border="0" alt="" id="BLOGGER_PHOTO_ID_5586775365116218978" style="float: left; margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; cursor: pointer; width: 16px; height: 16px; " /></a><div><a href="http://andrewl.dreamhosters.com/archive/48312620.">Makefile</a> - for GNU make to build pcap-wrap utility and wav dissectors</div></div><div><br />A WAV file is almost a disappointing example, but again it was just for POC. Here's Wireshark chewing on something a little more complicated:<br /><br /><img src="http://andrewl.dreamhosters.com/archive/54585568.png" /><br /><br /></div><div>A bug exists in wireshark where if more than one dissector for "wtap_encap" exists in the plugins directory, plugin tests will not continue after the first, even if the first plugin answers "no" (returning 0) from its dissect() function.</div><div>packet-whatever.c: dissect() (returns 0)<br />wireshark/epan/packet.c: call_dissector_work() (returns 0)<br />wireshark/epan/packet.c: dissector_try_port_new() (returns FALSE)<br />wireshark/epan/packet.c: dissector_try_port() (returns FALSE)<br />wireshark/epan/dissectors/packet-frame.c: dissect_frame() (doesn't try other dissectors in sub_dissectors)<br /><br />I don't have the wireshark know-how to make a proper fix/patch and <a href="https://bugs.wireshark.org/">Wireshark bug database</a> is down at the moment. It sucks but for now I make sure just one of these plugins are present to wireshark at a time.</div><div><br /></div><div>So do you think this practical? Or is it just not the right tool for the job?</div>andrewlhttp://www.blogger.com/profile/15585896448040772484noreply@blogger.com0tag:blogger.com,1999:blog-1546617459093993319.post-15735771062676301882011-02-15T17:00:00.007-05:002011-02-15T17:07:46.013-05:00Waganono's "Root Me #1"[difficulty: 5][protection: ???]<br /><center><br /><img src="http://4.bp.blogspot.com/-QtqcyTF6wUs/TVr4ovOFKQI/AAAAAAAAAAc/nsOAD1IiJD4/s320/waganono.PNG" /><br /></center><br />Waganono appears to be back! After solving CHAAK's maze crackme "Keygenme #1" earlier this month, he's submitted a new keygenme. It's not too hard and not too easy! Check it out!andrewlhttp://www.blogger.com/profile/15585896448040772484noreply@blogger.com3tag:blogger.com,1999:blog-1546617459093993319.post-49278071348158564582011-02-02T13:35:00.007-05:002011-02-02T13:46:55.931-05:00Shmoocon 2011 Crypto Challenge Pack<div style="text-align: center;"><img src="http://3.bp.blogspot.com/_RKOvgf9kD3s/TUmkKXX2kuI/AAAAAAAAAAM/2qFPXZkMaTQ/s320/pairing1.png" /><br /></div><br /><br />The Ghost In The Shellcode organizers gave me the privilege again this year to write some challenges for their CTF event. Here are the contents of the README:<br /><br /><span style="font-size:85%;"><br /><br /><span style="font-family:courier new;">Shmoocon 2011 Cryptography Challenge Pack</span><br /><span style="font-family:courier new;">-------------------------------------------------------------------------------</span><br /><a style="font-family: courier new;" href="http://www.ghostintheshellcode.com/">http://www.ghostintheshellcode.com/</a><br /><a style="font-family: courier new;" href="https://www.shmoocon.org/ghost_in_the_shellcode">https://www.shmoocon.org/ghost_in_the_shellcode</a><br /><span style="font-family:courier new;">-------------------------------------------------------------------------------</span><br /><span style="font-family:courier new;">These are the cryptography challenges submitted to the Shmoocon 2011 "Ghost In</span><br /><span style="font-family:courier new;">The Shellcode" organizers for potential use in the CTF event and December</span><br /><span style="font-family:courier new;">qualifier.</span><br /><span style="font-family:courier new;">-------------------------------------------------------------------------------</span><br /><span style="font-family:courier new;">Challenges were made with a few features to facilitate analysis:</span><br /><span style="font-family:courier new;">1) open source (skip the disassembly->algorithm translation phase)</span><br /><span style="font-family:courier new;">2) calculations, input, output are all in decimal, allowing easy entry of</span><br /><span style="font-family:courier new;">values between external tools</span><br /><span style="font-family:courier new;">-------------------------------------------------------------------------------</span><br /><span style="font-family:courier new;">Python?</span><br /><span style="font-family:courier new;">1) seems program logic is easy to understand even without knowing Python</span><br /><span style="font-family:courier new;">2) debugger is easy to use (python -mpdb chall1.py) but you probably won't need</span><br /><span style="font-family:courier new;">it</span><br /><span style="font-family:courier new;">3) installs nearly everywhere</span><br /><span style="font-family:courier new;">4) tested with 2.6.5</span><br /><span style="font-family:courier new;">-------------------------------------------------------------------------------</span><br /><span style="font-family:courier new;">I hope you find these algorithms easy to understand, interesting, but</span><br /><span style="font-family:courier new;">challenging to keygen. Chall4 and Chall5 are exceptions :)</span></span><br /><br /><a href="http://crackmes.de/users/andrewl.us/shmoocon_2011_crypto_challenge_pack/">http://crackmes.de/users/andrewl.us/shmoocon_2011_crypto_challenge_pack/</a>andrewlhttp://www.blogger.com/profile/15585896448040772484noreply@blogger.com0tag:blogger.com,1999:blog-1546617459093993319.post-15613358859299118942011-01-10T00:56:00.001-05:002011-01-10T00:57:06.135-05:002011 Shmoocon CTF Warmup ResultsThe 2011 Shmoocon Ghost In The Shellcode CTF warmup event went well this weekend. There were three challenges: an image puzzle riddle thing, a cryptography challenge, and an exploit challenge. See for yourself at <a href="http://ghostintheshellcode.com/2011/">http://ghostintheshellcode.com/2011/</a>.<br /><br />Unfortunately the crypto one fell faster than I expected and ended up being the easiest challenge of the three! LarsH and kaliman submitted a solution in just 28 minutes! From the chat, I gathered that people solved it in three ways:<br /><ol><li>typing the equations into wolfram alpha (this tool is becoming very popular! see recent solutions by tamaroth at crackmes.de among others)</li><li>using the <a href="http://en.wikipedia.org/wiki/Chinese_remainder_theorem">Chinese remainder theorem</a> (intended method)</li><li>using the <a href="http://en.wikipedia.org/wiki/Method_of_successive_substitution">method of successive substitution</a></li></ol><br />I've never seen the third method until now! Can there exist systems where CRT fails but this method finds a solution?<br /><br />The third challenge ended up being really really interesting and apparently the hardest. Awesie, the only solver and winner of the warmup and Shmoocon barcode, graciously details his methods for the public: <a href="http://ppp.cylab.cmu.edu/wordpress/?p=410">http://ppp.cylab.cmu.edu/wordpress/?p=410</a>. Congratulations awesie!andrewlnoreply@blogger.com1tag:blogger.com,1999:blog-1546617459093993319.post-49272692016950215622010-10-22T03:13:00.011-04:002010-10-25T09:52:18.833-04:00One Hell of an Anti-Debug! HideFromDebuggerA target appears to have no protection whatsoever, allowing debug attach, stepping, breakpoint, etc. When a critical area is reached, however, the debugger seems to not work at all - the breakpoint instruction and single-step exceptions (C0000003, C0000004) get passed right over the debugger and to the target, where it displays an error message.<br /><br />Since my breakpoints were at User32's WaitMessageWhatever return, this would happen if my mouse went over the window, giving the cool effect that the frozen target was still alive, detecting my efforts in real time. So what to do now?<br /><br /><ol><li>checked windbg on another machine, then olly - all tests exhibit same behavior<br /></li><li>compared PEB and TIB before and after the protection looking for some magical flag setting crap that the target may be doing.... no big differences<br /></li><li>the target loads drivers, so fearing some rootkit behavior, compared nt!KiTrap03 before and after the protection, no changes<br /></li><li>continuing this way, compared nt!CommonDispatchException and then nt!KiDispatchException, still no differences<br /></li><li>using the leaked Windows 2000 source (from torrent), omeg's fine comments on KiDispatchException (<a href=http://omeg.pl/code/XP_32_KiDispatchException.txt>http://omeg.pl/code/XP_32_KiDispatchException.txt</a>) and ReactOS (<a href=http://doxygen.reactos.org/db/da4/ntoskrnl_2ke_2i386_2exp_8c_a660d1a46ff201c5861caf9667937f73f.html#a660d1a46ff201c5861caf9667937f73f>http://doxygen.reactos.org/blah/blah</a>) it was easy to create an annotated IDA listing of my particular ontkrnlpa.exe<br /></li><li>traced the difference to a call to nt!DbgkForwardException which would return 0 during the protection - tracing is a little complicated by the way: KiDispatchException is part of the logic path that eventually communicates with KD itself - it splits into two paths several times depending on whether the exception came from user or kernel mode - obviously you can only use KD (insert BP, single-step) on the user mode paths otherwise the CPU will loop, interrupting on the same BP continuously<br /></li><li>tracing into this, found this crap:<br /><pre>nt!DbgkForwardException+0x2b:<br />80639e31 64a124010000 mov eax,dword ptr fs:[00000124h] <br />80639e37 f6804802000004 test byte ptr [eax+248h],4<br />80639e3e 7404 je nt!DbgkForwardException+0x3e (80639e44) ; success<br />80639e40 33c0 xor eax,eax ; zero return value, indicating failure<br /></pre>this value was 4 during the protection, so the je/jz was skipped and the failure path taken - patching this in memory allowed breakpoints and stepping to happen!<br /></li><li>so wtf is this check? ReactOS again is indispensible, with its code for DbgkForwardException - didn't take much to match this up:<br /><pre>00338 /* Check if this is to be sent on the debug port */<br />00339 if (DebugPort)<br />00340 {<br />00341 /* Use the debug port, unless the thread is being hidden */<br />00342 Port = PsGetCurrentThread()->HideFromDebugger ?<br />00343 NULL : Process->DebugPort;<br />00344 }<br /></pre></li><li>finally, googled for this HideFromDebugger and found ivanlef0u's page (<a href=http://www.ivanlef0u.tuxfamily.org/?p=48>http://www.ivanlef0u.tuxfamily.org/?p=48</a>) where he explains this protection completely over 3 years ago! man am I behind!<br /></ol>Anyways, two days lost to a protection that amounts to a single NtSetInformationThread() call from the target. Am I upset? No, I'm lucky these more skilled reversers published their findings otherwise this would have taken so much longer. <p><b>Oct 22, 2010 EDIT</b>: upb sent me this <a href=http://www.rootkit.com/board.php?did=edge284&closed=0&lastx=15>rootkit.com link</a> dating back to 2005 so this may not be news to anybody</p>andrewlnoreply@blogger.com1tag:blogger.com,1999:blog-1546617459093993319.post-75424868940931719282010-08-13T01:36:00.010-04:002010-08-17T11:20:53.027-04:00Shmoocon 2010 Crypto Pack Solved! And Hidden Monomials!<center><br /><img src="http://4.bp.blogspot.com/_I5FRefiygsU/TGqoh9U81XI/AAAAAAAAABs/RoH74diBCqY/s1600/crypto4.png " /><br /></center><br />So Shmoocon 2010 challenge pack finally has a published solution! See numernia's solution <a href="http://crackmes.de/users/andrewl.us/shmoocon_2010_crypto_challenge_pack/">here</a> where he used MAGMA's Grobner basis facilities and jB's keygen source <a href="http://jardinezchezjb.free.fr/crackmes.de/shmoocon/">here</a> where he never mentioned how the parameters of the keygen were arrived at. Of the five challenges only crypto4, the "taste of post-quantum" binary, had something new in it.<br /><br />The equations you see are the most explicit way to represent MQ system (no lookup table or other type of "compression" was used as in gbe32241's work). See the HFE challenge <a href="http://www.minrank.org/challenge1.tx">here</a> for a very similar setup.<br /><br />I think the start of all these schemes was the MI C* scheme (see paper "Public Quadratic Polynomial-Tuples For Efficient Signature-Verification and Message-Encryption" by Matsumoto and Imai). The best explanation I've found though is probably in Koblitz's <u>Algebraic Aspects </u><u>of Cryptography</u>.<br /><br />So the main idea is that you can compute certain exponentiations in an extension field in an alternative way. First you treat the extension field elements as a vector space over the base field. This vector space has many basis to choose from, and any element can also be represented in terms of any chosen basis (the canonical one works just fine). Carefully chosen exponents of these elements resolve to linear transformations and linear expressions of the vectors. And the product of two of these special exponents resolves to a quadratic system of equation. I gave clue "Remember that an extension field is a vector space over its ground field."<br /><br />The MI scheme and schemes to follow (HFE and so-on) do their best to hide this exponentiation by wrapping the expression for the exponentiation in linear transformations or adding/removing variables and equations. It's these obfuscating elements that become the private information. You didn't have to worry about any of this due to the clue: "there is no scheme in the system, no trapdoor".<br /><br />So how to solve this thing? Let's treat the system like a black box. If you suspect that the black box is performing exponentiation, what's the simplest test to affirm this? Send in the identity: {1}. No matter the exponent, the identity will be returned. In the polynomial basis representation of the elements, we still don't know which direction the coefficients are listed though. No problem. With a 40-bit input, we try a 1 coefficient at either end:<br /><pre>blackbox(0x8000000000); // returns 000000E0BCE7BA8A<br />blackbox(0x0000000001); // returns 0000000000000001</pre>Cool so now we know the LSB of the input is the 0'th coefficient, and it is easy to send in {1}, {x}, {x+1}, etc. But we are faced with a new problem: we don't know what reduction polynomial is used in the field computations. There is only one GF(2^40) field, but the same elements have drastically different representations depending on the reducing polynomial (math nerds talk about isomorphism here).<br /><br />Can we craft some probe inputs so that the black box will yield to us its reduction polynomial? Yes!<br /><br />We send element {x}. The blackbox will give us {x}^e (mod p) where e is the unknown exponent and p is the unknown reduction polynomial. We send also element {x^2} and the blackbox will return to us {x^2}^e (mod p) = {x}^(2e) (mod p).<br /><br />Both of these results are already reduced (mod p). But *OUTSIDE* of the blackbox, we square the first result ourselves on the left hand side, and equate to the second result on the right hand side:<br /><pre>({x}^e (mod p))^2 = {x}^(2e) (mod p)<br />-> p | ({x}^e (mod p))^2 - {x}^(2e)<br />-> p * q = ({x}^e (mod p))^2 - {x}^(2e)</pre>And q is just some other polynomial. So we compute the right hand side of this last equation and factor it, hoping to find some large 40-degree irreducible polynomial! Enough talk, let's do it!<br /><pre>blackbox(0x0000000002 /* {x} */); // returns 0x0EFFD5DBF6 which is {x^n}<br />blackbox(0x0000000004 /* {x^2} */); // returns 0x0400040008 which is {x^(2n)}</pre>Let's flee to our CAS now, the venerable PARI/GP! We convert these results to polynomials a, b:<br /><pre>a = (x^35 + x^34 + x^33 + x^31 + x^30 + x^29 + x^28 + x^27 + x^26 + x^25 + x^24 + x^23 + \<br /> x^22 + x^20 + x^18 + x^16 + x^15 + x^14 + x^12 + x^11 + x^9 + x^8 + x^7 + x^6 + \<br /> x^5 + x^4 + x^2 + x)*Mod(1,2)<br />b = (x^34 + x^18 + x^3)*Mod(1,2)</pre>And finally reveal our p!<br /><pre>lift(factor(a*a + b))<br />[x 2]<br />[x^2 + x + 1 1]<br />[x^12 + x^9 + x^5 + x^4 + x^2 + x + 1 1]<br />[x^14 + x^13 + x^11 + x^10 + x^7 + x^6 + x^3 + x + 1 1]<br />[x^40 + x^38 + x^37 + x^36 + x^35 + x^33 + x^30 + x^29 + x^27 + x^26 + x^24 + x^23 + x^22 + \<br /> x^19 + x^15 + x^14 + x^12 + x^11 + x^6 + x^5 + 1 1]</pre>It is the last 40-degree polynomial, converted to bit representation, it's 0x017A6DC8D861.<br /><br />Finding the exponent e is simple now: you may brute outright, brute only exponents that are coprime with ord(GF*(2^40)) (else the blackbox is not a bijection), or use Coppersmith or whatever your CAS uses. It's low, just 257.<br /><br />So the blackbox is doing exponentiation by 257 and field elements are represented bit-wise with the discovered polynomial. To invert, just exponentiate by d = 257^-1 (mod ord(GF*(2^40))) = 551894941568.andrewlnoreply@blogger.com0tag:blogger.com,1999:blog-1546617459093993319.post-13638851777245631052010-05-29T01:09:00.001-04:002010-05-29T01:09:55.977-04:00Conjan's "Jump Around"[difficulty: 3][protection: mild asm obfuscation, trigonometry equation]<br /><center><br /><img src="http://1.bp.blogspot.com/_I5FRefiygsU/TACgslrYXnI/AAAAAAAAABc/kE8RSEfH7Pk/s1600/conjan.PNG" /><br /></center><br />The serial verification function's instructions are reordered and linked with unconditional jumps. The solution shows how to disassemble the code into a linked list of instructions, remove the jumps, and recover the original code.andrewlnoreply@blogger.com0tag:blogger.com,1999:blog-1546617459093993319.post-60608107958447827142010-05-14T16:39:00.002-04:002010-05-28T14:28:55.423-04:00SEH ChecklistTrying to collect here the requirements that windows (32-bit) enforces before calling back an SEH handler that you've manually written into the SEH chain. Please comment anything you know.<br /><br /><ul><li>seh node must be on stack (thanks JPassing.com)</li><li>seh handler must be on non-stack (thanks JPassing.com)</li><li>seh handler nodes must appear in-order on the stack (imagine deeper functions' frames going up the stack, towards lower (less quantity) addresses) (thanks roxfan and Clandestiny post on woodmann)</li><li>seh handler must exist in safeseh list (if it exists, see IMAGE_LOAD_CONFIG_DIRECTORY.SEHandlerTable which is the IMAGE_DIRECTORY_ENTRY_LOAD_CONFIG directory entry in IMAGE_OPTIONAL_HANDLER)</li><li>handler addresses in the safeseh list must be sorted ascending</li><li>IMAGE_OPTIONAL_HEADER.DllCharacteristics must not have flag set IMAGE_DLLCHARACTERISTICS_NO_SEH (this is set by default for Visual Studio when compiling with /SafeSEH:no and no other handlers present (yes even for exe's) ...caught by RtlCaptureImageExceptionValues() WARNING: LET ME RETRACT THIS, NOT ALWAYS)</li></ul><b>May 28th, 2010 EDIT:</b><br />As Ivanlef0u commented, analysis of RtlIsValidHandler() itself trumps any type of listing we could possibly do. Check his links:<br /><ul><li>http://www.eeye.com/html/resources/newsletters/vice/VI20060830.html</li><li>http://sf-freedom.blogspot.com/2007/07/ms07-029-series-part-2-exploiting-dns.html</li></ul><ul></ul>andrewlnoreply@blogger.com2tag:blogger.com,1999:blog-1546617459093993319.post-30611181747778605332010-03-28T01:43:00.006-04:002010-05-13T16:35:09.202-04:00Neotren's CryptoME[difficulty: 7][protection: RSA (2034 bit), Schnorr Signature]<br /><center><div style="text-align: auto;"><br /></div><img height="190" src="http://3.bp.blogspot.com/_I5FRefiygsU/S67sVtnw_lI/AAAAAAAAABE/He9vw0snbk4/s400/neo2.PNG" width="400" /><br /></center><br /><br />Your registration data is RSA decrypted, then checked for signature (DLP type). But the signature check uses the same modulus as in the RSA decryption part, giving you a clue to the existence of a subgroup, and the generator of that group. The exponent is capped at 7 bytes, making it possible to search cleverly within this range. Once the subgroup is found, a factor is revealed (and thus the other also). This is a long standing unsolved crackme on crackmes.de and unfortunately neotren had to clue us to the p-1 factoring algorithm, dropping the difficulty significantly.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="http://2.bp.blogspot.com/_I5FRefiygsU/S67sYPz1y5I/AAAAAAAAABU/mCvYpljxX4Y/s1600/neo1.PNG" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="http://2.bp.blogspot.com/_I5FRefiygsU/S67sYPz1y5I/AAAAAAAAABU/mCvYpljxX4Y/s320/neo1.PNG" /></a></div><div style="text-align: left;"><br />Lately I read an article about how this one particular C64 user manual had nearly every detail of how the entire machine worked (insane depth compared to manuals of today) and then just a few days ago I read an announcement where the C64 is being re-released. I kind of want one of the classic machines for some reason :) And now this cool emulated game.</div>andrewlnoreply@blogger.com1tag:blogger.com,1999:blog-1546617459093993319.post-59157430741972758662010-03-17T00:43:00.008-04:002010-08-17T11:33:31.192-04:00MR.HAANDI's "Intersection #1.0"[difficulty: 8][protection: ECC]<br /><br /><br /><center><br /><img src="http://1.bp.blogspot.com/_I5FRefiygsU/TGqqKwuNPcI/AAAAAAAAAB0/kPntG6MFrug/s1600/intersect.PNG" /><br /></center><br /><br />It's compiled against NTL and *alot* of code has to be sifted through to understand what is going on. It's a custom scheme:<br /><br /><center><br /><img src="http://2.bp.blogspot.com/_I5FRefiygsU/TGqrnwsym4I/AAAAAAAAAB8/8gcJbmrLiwo/s1600/intersect2.PNG"><br /></center><br /><br />To solve it, you need to express the PointB in terms of PointA multiplied by some coefficient k (solving the DLP). This can be done by finding the curve order (#E) and tracing the provided name/serial. But the DLP discovered here is inflated for this particular name/serial. After discovering how "close" PointA and PointB are in a subgroup, it can be reduced to its real value.<br /><br />Now a cubic equation arises because of the serial's exponent. The equation is reduced mod #E, which is composite. So it doesn't always have solutions. But you can produce many variations of the equation (one which hopefully DOES have a solution) by carefully tweaking the coefficient on the X^0 term.<br /><br />All crackme calculations are done using curves in the Jacobian intersection form, see:<br /><br /><a href="http://en.wikipedia.org/wiki/Jacobian_curve">http://en.wikipedia.org/wiki/Jacobian_curve</a><br /><a href="http://www.hyperelliptic.org/EFD/g1p/auto-jintersect.html">http://www.hyperelliptic.org/EFD/g1p/auto-jintersect.html</a><br /><br />It was a real IRL killer. Equivalently, a great crackme :)andrewlnoreply@blogger.com0tag:blogger.com,1999:blog-1546617459093993319.post-10675455502985308912010-02-09T11:34:00.006-05:002010-05-13T16:41:06.201-04:00Shmoocon 2010 Crypto Challenge Pack<a href="http://andrewl.dreamhosters.com/archive/05130263.png" onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}"><img alt="" border="0" src="http://andrewl.dreamhosters.com/archive/05130263.png" style="display: block; height: 221px; margin-bottom: 10px; margin-left: auto; margin-right: auto; margin-top: 0px; text-align: center; width: 486px;" /></a><br /><div style="text-align: left;">These are the crypto challenges from Shmoocon 2010's "Ghost in The Shellcode" CTF event (see http://www.shmoocon.org/gits.html). My goal was to make algos that can be grasped quickly (minimal reversing), but remain challenging to keygen. Example codes are given in each respective crackmes' GUI. As always, true keygens are the only real solutions :)</div><div style="text-align: left;"><br /><a href="http://crackmes.de/users/andrewl.us/shmoocon_2010_crypto_challenge_pack/">http://crackmes.de/users/andrewl.us/shmoocon_2010_crypto_challenge_pack/</a></div><div><br /></div>andrewlnoreply@blogger.com0tag:blogger.com,1999:blog-1546617459093993319.post-68260435411251468192010-02-08T13:22:00.008-05:002010-02-09T11:34:24.620-05:00Really slick way to calculate x % (2^32-1)From Numernia's solution/analysis of WiteG #5:<br /><br />mul dword ptr ds:[40120C]<br />add eax, edx<br />adc eax, 0<br /><br />The result is that eax = (eax * [40120C]) % (2^32-1)... Can you prove why?andrewlnoreply@blogger.com1tag:blogger.com,1999:blog-1546617459093993319.post-89672287276540229602010-02-06T01:04:00.008-05:002010-02-09T02:11:55.616-05:00Chinese CRC In Operation AuroraGoogle "Operation Aurora: Clues in the Code" for a cool writeup by secureworks about a CRC algorithm found in the trojan used against Google.<br /><br />CRC lookup tables normally store a precomputed value for each byte, and thus their tables have 256 entries. This one has only 16, how? If you look closely, the temporary value used to hold the result of the current division is shifted by 4, not 8. Division is done twice. What is going on?<br /><br />This code is using a nibble lookup table. Two nibbles per byte processed. This optimization has decreased the size of the table by a factor of 16, but only decreased the code speed by a factor of 2, a very cool trade off!<br /><br />Also notice the direction of the shift, this implementation treats higher significance bits as higher order terms (unlike the typical crc-32, which does the opposite). You can thus find all coefficients except a_16 of the divider polynomial at entry 0x01 (instead of 0x80 in the crc-32 ordering). The polynomial is 0x1021 representing x^16 + x^12 + x^5 + 1. (The a_16 * x^16 term is implicit). The wikipedia page calls this CRC-16-CCITT.<br /><br />With a little care, we can recreate how this nibble lookup table was generated:<br /><pre><br />WORD table[16];<br />for(INT i=0; i<16; ++i) {<br />WORD crc = i<<12;<br />for(INT j=0; j<4; ++j) { // for each of 4 possible nibble terms<br /> if(crc & 0x8000) { // high order term present?<br /> crc <<= 1; // term=0 (by implied x^16 divider term)<br /> crc ^= 0x1021; // subtract rest of poly<br /> }<br /> else<br /> crc <<= 1; <br />}<br />table[i] = crc;<br />}<br /></pre><br />When more spare time arrives, I'll adapt a crc-32 implementation to use this trick! Also add it to your bag of tricks to be on the lookout for when reversing!<br /><br /><b>Feb 09th, 2010 EDIT</b>: check out the current file archive for the source to an adapted crc-32! It was more difficult than expected to get it to work!andrewlnoreply@blogger.com6tag:blogger.com,1999:blog-1546617459093993319.post-2271518852677630302010-01-27T10:32:00.002-05:002010-01-27T10:36:48.985-05:00Numernia's "Keygenme Tre"[difficulty: 4][protection: 0xECC9 :)]<br /><br />Check out Numernia's new crackme at <a href="http://crackmes.de/users/numernia/keygenme_tre/">http://crackmes.de/users/numernia/keygenme_tre/</a>!<br /><br />Probably a little more difficult than 4, but totally possible! Good luck!andrewlnoreply@blogger.com0tag:blogger.com,1999:blog-1546617459093993319.post-76247872469742419062010-01-07T02:59:00.007-05:002010-01-27T10:31:42.828-05:00gbe32241's SDDecoder<div>[difficulty: 6][protection: multivariate]</div><div><br /></div><div>I'm pleased to report that after nearly half a year of obsession, SDDecoder is solved. It is one of the most enigmatic crackmes posted to crackmes.de IMHO.</div><br /><span style="font-weight: bold;font-family:courier new;">NNE92-NS62P-TZ9QC-NGEII-6UJ4V (id: 0xDDDD)</span><br /><span style="font-weight: bold;font-family:courier new;">PMOFN-WJIJW-DQ9T9-IOM62-RXIIR (id: 0xBBBB)</span><br /><span style="font-weight: bold;font-family:courier new;">FGU6J-WAHFJ-T6ZD7-CBKOQ-6LJHD (id: 0x9999)</span><br /><span style="font-weight: bold;font-family:courier new;">JT2CQ-6HY7O-6B3DJ-HIAJC-BEC2Q (id: 0x5678)</span><br /><br />My attack should work in general for any overlapping s-box scheme. The first implementation was made against SDD64 (the very reason SDD64 was written!) and can generate every possible key for an arbitrary ID. While converting this to 128-bit, I made some error because some id's for the real SDDecoder won't solve, and without the private info, it's difficult to trace why.<br /><br />It took about 2 single-machine days to extract the private data needed from the public key, and each key generation takes a few minutes (the ones that succeed). When the keygen is debugged I'll submit a solution.<br /><br /><span style="font-weight: bold;">Jan 13th, 2010 EDIT</span>: Solution uploaded! SDDecoder JR v2 falls even better to this same attack, so I downgraded the difficulty to 2... I'm off now exploring other MQ stuff (original C*, HFE, Oil and Vinegar, etc.) Some bonus keys:<br /><br /><span style="font-weight: bold;font-family:courier new;">HSCTZ-KL9E2-OW67U-UBVEN-VYW7X</span><br /><span style="font-weight: bold;font-family:courier new;">PMAUJ-9CJ2W-3SBSY-3A26Y-HAR4V</span><br /><span style="font-weight: bold;font-family:courier new;">Z4ANL-MTVRL-3XVL3-A3NMB-3UI39</span><br /><span style="font-weight: bold;font-family:courier new;">U3Z3Y-UM337-ZPT9R-4RCKP-C7MSP</span><br /><span style="font-weight: bold;font-family:courier new;">SE2FI-B2LOS-EN4LK-HLJ9I-CWZ47</span><br /><span style="font-weight: bold;font-family:courier new;">PGPPP-ZVPJW-UEE2Q-FWLY3-3KPPX<br /><br /><span class="Apple-style-span" style="font-family:Georgia, serif;">Jan 27th, 2010 EDIT:<span class="Apple-style-span" style="font-weight: normal;"> Not challenged enough? See how SDDecoder (DRegZ) was built, and try JRegZ and QRegZ at <a href="http://www.webalice.it/giuliano.bertoletti/lca.html">http://www.webalice.it/giuliano.bertoletti/lca.html</a>.</span></span></span>andrewlnoreply@blogger.com0tag:blogger.com,1999:blog-1546617459093993319.post-3512907333212560232009-12-22T23:55:00.003-05:002010-05-13T16:41:29.862-04:00death's "Saddam Crackme"[difficulty: 5][protection: des, scrambled function table]<br /><br /><img alt="" border="0" src="http://andrewl.dreamhosters.com/archive/80614495.png" style="cursor: pointer; display: block; height: 192px; margin: 0px auto 10px; text-align: center; width: 285px;" />After being des-decrypted (key derived from GetVolumeInformation()), your serial is used to unscramble an array of function pointers which are critical to the protected application (a cool desktop switcher prog called Smirk).<br /><br />To solve it, you can make a a small number of guesses (relative to the entire size of the table) at proper locations of function pointers within the table, and then search which serials yield arrangements that fit your guess.andrewlnoreply@blogger.com0tag:blogger.com,1999:blog-1546617459093993319.post-73524184116289762652009-12-08T18:20:00.003-05:002010-10-22T13:51:34.711-04:00SDD64<pre>r[0] = x[0]*x[0] ^ x[2]*x[0] ^ x[3]*x[0] ^ x[3]*x[2] ^ x[3]*x[3] ^ x[4]*x[4] ^ x[5]*x[2]<br />r[1] = x[2]*x[1] ^ <u><b>x[3]*x[0]</b></u> ^ <u><b>x[3]*</b></u>x[1] ^ <u><b>x[3]*</b></u>x[3] ^ <u><b>x[4]*x[1]</b></u> ^ <u><b>x[4]</b></u>*<u><b>x[2]</b></u> ^ x[5]*x[3]<br />r[2] = x[1]*x[0] ^ <u><b>x[1]</b></u>*x[1] ^ <u><b>x[2]</b></u>*<u><b>x[0]</b></u> ^ <u><b>x[2]</b></u>*<u><b>x[2]</b></u> ^ <u><b>x[3]</b></u>*x[0] ^ <u><b>x[3]</b></u>*<u><b>x[2]</b></u> ^ x[4]*x[0]<br />r[3] = x[2]*x[0] ^ <u><b>x[2]*x[1]</b></u> ^ <u><b>x[3]</b></u>*<u><b>x[0]</b></u> ^ <u><b>x[3]</b></u>*<u><b>x[1]</b></u> ^ <u><b>x[3]</b></u>*x[3] ^ <u><b>x[4]</b></u>*<u><b>x[1]</b></u> ^ x[4]*x[2]<br />r[4] = x[1]*x[1] ^ x[2]*<u><b>x[0]</b></u> ^ <u><b>x[2]</b></u>*<u><b>x[1]</b></u> ^ <u><b>x[3]</b></u>*<u><b>x[0]</b></u> ^ <u><b>x[3]*x[1]</b></u> ^ <u><b>x[3]*x[2]</b></u> ^ x[4]*x[0]<br />r[5] = x[2]*x[0] ^ x[2]*<u><b>x[2]</b></u> ^ <u><b>x[3]</b></u>*<u><b>x[2]</b></u> ^ <u><b>x[3]</b></u>*<u><b>x[3]</b></u> ^ <u><b>x[4]</b></u>*<u><b>x[1]</b></u> ^ x[4]*<u><b>x[2]</b></u> ^ x[4]*x[3]<br />r[6] = x[0]*x[0] ^ x[1]*<u><b>x[0]</b></u> ^ <u><b>x[2]</b></u>*<u><b>x[1]</b></u> ^ <u><b>x[2]</b></u>*<u><b>x[2]</b></u> ^ <u><b>x[3]</b></u>*<u><b>x[0]</b></u> ^ x[3]*<u><b>x[1]</b></u> ^ x[3]*x[2]<br />r[7] = x[0]*x[0] ^ <u><b>x[2]*x[1]</b></u> ^ <u><b>x[3]*x[0]</b></u> ^ <u><b>x[3]*x[2]</b></u> ^ <u><b>x[4]*x[0]</b></u> ^ x[4]*<u><b>x[2]</b></u> ^ x[5]*x[0]<br />r[8] = x[1]*x[0] ^ x[1]*x[1] ^ x[2]*x[1] ^ x[2]*x[2] ^ x[3]*x[2] ^ x[3]*x[3] ^ x[4]*x[0]<br />r[9] = x[1]*x[0] ^ x[1]*x[1] ^ x[2]*x[1] ^ x[3]*x[0] ^ x[3]*x[3] ^ x[4]*x[0] ^ x[4]*x[1]<br /><br />WHAT:<br />SDD64<br /><br />This is a 64-bit bit version of Giuliano Bertoletti's<br />DRegZ/SDDecoder license scheme.<br /><br />No code lifted!<br /><br />References:<br />"Asymmetric Cryptography with S-Boxes" - Jacques Patarin<br />"Algorithm for license codes" - Giuliano's sci.crypt post<br />"License Code Algorithms" - Giuliano's website:<br /><a href="http://www.webalice.it/giuliano.bertoletti/lca.html">http://www.webalice.it/giuliano.bertoletti/lca.html</a><br />"SDDecoder" - crackmes.de<br /><br />andrewl<br />dec07_2009 - first release<br />http://andrewl.brainstemprojects.com<br /><br />HOW:<br /><br />Use sdd64.cpp to generate a random keypair, which are<br />output into public_key.h and private_key.h.<br /><br />Use encoder.cpp with private_key.h to make valid licenses.<br /><br />Use decoder.cpp with public_key.h check license validity.<br /><br />encoder takes as input the license id (decimal format 20-bit<br />integer) and emits an encoded license<br /><br />decoder takes as input an encoded license (hexadecimal format<br />64-bit integer) and emits "pass" or "fail" message<br /><br />COMPILATION:<br /><br />Written/tested with Visual Studio 9.0 express. With VC6,<br />much wincrypt stuff is not found (HCRYPTPROV, PROV_RSA_FULL,<br />etc. not defined). It can be made to work with VC6, but I do<br />not have time.<br /><br />Compile sdd64.cpp alone.<br /><br />Execution of sdd64 produces public_key.h and private_key.h.<br /><br />Compile encoder.cpp + private_key.h.<br /><br />Compile decoder.cpp + public_key.h.<br /><br />Example command line:<br /><br />cl sdd64.cpp /link advapi32.lib<br />sdd64.exe<br />cl encoder.cpp<br />cl decoder.cpp<br /><br />WHERE:<br /><br />Browse my website for the currently updated file archive and<br />text search for "sdd64".<br /><br />An early version of the software is also included with the<br />SDDecoder Jr. v2 crackme on <a href="http://crackmes.de/">http://crackmes.de</a>.<br /></pre>andrewlnoreply@blogger.com0tag:blogger.com,1999:blog-1546617459093993319.post-53965966164647837482009-11-12T00:50:00.006-05:002010-05-13T16:41:55.448-04:00death's "electric-camel"[difficulty: 6][protection: tiger,sha1,blowfish,el-gamal]<br /><br /><a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="http://andrewl.dreamhosters.com/archive/82709920.PNG"><img style="margin: 0px auto 10px; display: block; text-align: center; cursor: pointer; width: 366px; height: 179px;" src="http://andrewl.dreamhosters.com/archive/82709920.PNG" alt="" border="0" /></a><br />It does some sha/tiger/blowfish which has to produce the right el-gamal private key to decrypt the goodboy message. See solution and keygen for details. The hardest thing about this crackme is the message of c++ code that goes along with crypto++ library. There's just so much code. I downloaded an old compiler and service pack in order to build the two versions of crypto++ that straddle the 2001 time that this crackme was made, and produced IDA signatures from these.<br /><br />One of the coolest thing to be learned from this crackme is just how fast <a href="http://magma.maths.usyd.edu.au/">MAGMA</a> can solve the DLP for this crackme:<br /><br /><span style="font-size:85%;"><span style="font-family:courier new;">P: cc7346a8b4ffb3f2393b</span><br /><span style="font-family:courier new;">G: 00000000000000000003</span><br /><span style="font-family:courier new;">Y: 3e2cb006ad3961beda9d</span></span><br /><br />I left <a href="http://www.alpertron.com.ar/DILOG.HTM">alpertron</a> on overnight and it had not found anything... About 17 hours of computation was continuing when Dcoder from EFNET #cryptography helped me his script:<br /><br /><span style="font-size:85%;"><span style="font-family:courier new;">p := 965489229592273293031739;</span><br /><span style="font-family:courier new;">K := GF(p);</span><br /><span style="font-family:courier new;">g := K ! 3;</span><br /><span style="font-family:courier new;">y := K ! 293611062693023723739805;</span><br /><span style="font-family:courier new;">x := Log(g, y);</span><br /><span style="font-family:courier new;">x;</span></span><br /><br />It finds x=0792A1952223 in about .3 seconds!andrewlnoreply@blogger.com0tag:blogger.com,1999:blog-1546617459093993319.post-23952679549512475072009-11-03T13:46:00.006-05:002009-11-04T10:41:52.539-05:00upb's "Keygenme Sheg"[difficulty: 2][protection: digital logic]<br /><br />Your serial number encodes instructions for a stack-based machine that has instructions for AND, XOR, and PUSH.<br /><br />The VM is called 16 times and the output must match some values calculated from your username.<br /><br />This is extremely similar to Malfunction's "Digital Arithmetic" (which came later). In DA, your serial encoded a circuit of NAND gates, and it was shown that NAND gates can be used to make any circuit. In sheg, you have a stack machine, so it is a little harder to produce a functioning "circuit" (the binary operations can ONLY use the two values at the top of the stack, and can ONLY put a result at the top of the stack). Since NOT(x)=XOR(x,1), we get can combine with AND to get NAND, and thus we get anything.<br /><br /><span style="font-weight: bold;">EDIT:</span> upb has informed me that his machine is evaluating a <a href="http://en.wikipedia.org/wiki/Zhegalkin_polynomial">Zhegalkin polynomial</a>, which is neat view of a logic circuit as a polynomial over GF(2).andrewlnoreply@blogger.com0tag:blogger.com,1999:blog-1546617459093993319.post-46492294484662035222009-10-08T13:33:00.004-04:002010-05-13T16:42:12.809-04:00Amenesia's "Howl"[difficulty: 6][protection: custom finite field cipher activity]<br /><br /><a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="http://andrewl.dreamhosters.com/archive/16307903.PNG"><img style="margin: 0px auto 10px; display: block; text-align: center; cursor: pointer; width: 305px; height: 177px;" src="http://andrewl.dreamhosters.com/archive/16307903.PNG" alt="" border="0" /></a><br />Contains a block cipher utilizing finite field arithmetic. You can invert it by reversing the operations and inverting certain field operations. Your serial must encrypt to some values generated from the name and Allen Ginsberg's poem "Howl" (what is an angelheaded hipster anyways!?).<br /><br />Check out the code for some real calculation of multiplicative inverses in the field using the Euclidean algorithm (no bruteforcing this time!!)andrewlnoreply@blogger.com0tag:blogger.com,1999:blog-1546617459093993319.post-31567434552622480202009-09-28T15:19:00.004-04:002010-05-13T16:42:26.752-04:00so61pi's "Keygenme#1"[difficulty: 2][protection: miniature RSA and subset sum]<br /><br /><a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="http://andrewl.dreamhosters.com/archive/65389556.PNG"><img style="margin: 0px auto 10px; display: block; text-align: center; cursor: pointer; width: 293px; height: 137px;" src="http://andrewl.dreamhosters.com/archive/65389556.PNG" alt="" border="0" /></a><br />A fun little keygenme! See if you can make serials containing only printable characters!andrewlnoreply@blogger.com0tag:blogger.com,1999:blog-1546617459093993319.post-49155498728523801222009-09-25T18:06:00.005-04:002010-05-13T16:42:35.368-04:00Numernia's "Keygenme Tvaa"[difficulty: 3][protection: crc32, GF(2^19) arithmetic]<br /><br /><a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="http://andrewl.dreamhosters.com/archive/15352237.PNG"><img style="margin: 0px auto 10px; display: block; text-align: center; cursor: pointer; width: 548px; height: 132px;" src="http://andrewl.dreamhosters.com/archive/15352237.PNG" alt="" border="0" /></a><br />I won't post too much about this yet (it is less than 2 days old on crackmes.de right now) and I am curious what other people submit. It is a very nicely, tightly coded crackme that I'm sure you will enjoy.andrewlnoreply@blogger.com0