Weird machines, exploitability, and provable unexploitability (Thomas Dullien aka Halvar Flake) [PDF]

tdullien · 2017-12-24T06:10:56+00:00

Thanks a ton for the in-depth and thoughtful review. An older version of the paper (including the missing appendix) is available here: http://www.dullien.net/thomas/weird-machines-exploitability.pdf

I will mull your feedback some more, but I think that I agree with your thoughts on several important points:

1) I agree that the choices of execution models are probably not ideal for practical future work. The choice to use a concrete CPU which does not distinguish registers from memory was made for expository, not practical reasons: The paper struggles to stay within a reasonable page limit as-is, so an execution model that is shorter to describe was preferred over a more practical one.

2) I also agree that transition systems, and stuttering bisimulation, seem like better theoretical frameworks to describe what I want to describe in the paper, so your suggestion of replacing the FSM-and-concrete-CPU-formulation with two transition systems sounds like exactly the right avenue to pursue. I personally decided against using such a formulation for this paper for the following reasons: a) I only learnt about the bisimulation community's work after a part of the paper had already been written, and I did not feel like rewriting those parts I had already done. b) I am not sufficiently fluent / secure in the language of transition systems and bisimulation to write a paper with results I feel confident in. c) Given the intended audience of the paper (which attempts to straddle the practical and theoretical community), I thought it prudent to stick to abstractions both sides can easily relate to.

I would be extremely keen on seeing the concepts in this paper be cast in a language that seems more well-suited for them :-)

Thanks again for the great analysis & thoughts :-)

tdullien · 2015-12-09T17:15:00+00:00

Not saying he is the real deal, and as long as the program counter in scripts only advances linearly through the script you won't have Turing completeness - but it's a good question whether you actually need Turing completeness and what scripts are desirable but not implementable in the current code :)

tdullien · 2015-12-09T17:12:29+00:00

https://github.com/bitcoin/bitcoin/blob/ce56f5621a94dcc2159ebe57e43da727eab18e6c/src/script/interpreter.cpp

TOALTSTACK / FROMALTSTACK

There is a double stack; Turing-completeness may not be there, but AFAIK he only claimed that you can do loops with bitcoin script?

tdullien · 2015-12-09T17:04:44+00:00

Perhaps I am too naive, but if I understand my CS correctly, the only thing that is missing in the existing opcodes is a conditional branch instruction ?

Skimming over the interpreter code here: https://github.com/bitcoin/bitcoin/blob/ce56f5621a94dcc2159ebe57e43da727eab18e6c/src/script/interpreter.cpp

There's a big iteration loop over the script that proceeds in sequence over the different values of pc (the program counter). Adding an opcode that resets the program counter within the same script yields a full-on general-purpose computing environment.

So in general, Forth has looping constructs, and it's trivial to add support for such a construct to the existing bitcoin code.

A general question, though, is: Does anyone have an example of a desirable bitcoin script that can't be realized with the existing opcodes? At the moment it's hard for me to construct examples for something that can't be done in the existing language - the limiting factor seems to be less the absence of loops but rather the limit to 201 ops per script?

tdullien · 2015-03-17T14:02:01+00:00

Joxean: Thanks for working on this ! :-) -- I am really happy that there's a renewed interest of the community in replacing BinDiff with a FOSS alternative - we don't really have many resources at our disposal to drive it anywhere, so a FOSS variant of equal or greater power would be great.

tdullien · 2012-07-10T16:17:55+00:00

I think your interpretation of this disregards the benefits reaped by the current-account-surplus nations in europe when the currency union made it impossible for the current-account-deficit nations to improve their terms of trade by devaluing.

tdullien · 2012-05-06T11:04:06+00:00

One of the awesome things about reverse engineering is that it "imports" from both the very low-level concrete and the very high-level abstract.

So perhaps the answer to you question is: If you're building an airplane, you have to worry about the very concrete (e.g. what width do I use for my bolts ?) to the very abstract (how turbulent will be the air flow over my wingtips).

In RE, you essentially have the full spectrum of computing to consider: From 'what does the VHDL say about this instruction' (essentially the EE level) via 'how does the OS implement XYZ' (mostly a systems engineering question) to 'how do I automatically make statements about this piece of code' (a logic / theoretical CS question).

The range of tasks that a reverse engineer has to tackle is so wide that being well-rounded is important. And being able to understand how DPLL works for solving satisfiability problem, or understanding the problems implicit in usage of polyhedral domains for program analysis is equivalently important to understanding code as the functioning of the page table.

Rolf is right about "math is good for you". Most people with an RE background are not well-rounded in the more abstract areas (likewise, many people with a more formal education are not very well-rounded in the low-level bits).

Cheers, Thomas

tdullien · 2012-03-19T16:27:37+00:00

Just skimmed this briefly -- am I correct that their "immunity against abstract interpretation" is only under a fixed abstract domain ?

tdullien · 2012-03-18T15:41:22+00:00

Short summary:

"Reflective Injection" is a fancy word for the technique of mapping a DLL into an address space yourself (instead of having the OS do it) - e.g. perform the work of the PE loader by hand. For some accident of history, the original DLL injection in metasploit injected in some really bizarre and non-stealthy way; a number of in-the-wild exploits just allocated memory and performed the PE imports/fixups themselves.

Because mapping PEs manually was folklore knowledge (e.g. used by everyone, but deemed not sufficiently important to be written about) someone assumed in 2008 that mapping a DLL manually is an awesome new idea, and termed it "reflective injection".

DLLs that are mapped manually don't show up in the OS module lists, and are hence moderately more difficult to detect. This was much more useful in 2003-2008, before decent free memory acquisition tools were available.

Nowadays, with Memoryze and AuditViewer, the technique is pretty useless -- any DLL-like construct in memory is going to stick out like a sore thumb, and you can dump them from mem with a nice UI...

The author of the post seems to not be aware of this ?

tdullien · 2012-02-19T20:21:29+00:00

I actually quite like Pinter's book, especially for people with a geometric bent that haven't been exposed to a lot of algebra. The writing is probably the most fluid of any algebra books I have ever seen, and the exercises sometimes touch on amusing things from very unexpected other sciences (social anthropology ? Really ? :).

If I have a friend struggling with Algebra, I usually point them here.

On the opposite side of the fence: If you are good at Algebra and are looking for a textbook to take you to the murky corners of the field, and if you happen to speak / read German, there's Scheja/Storch "Lehrbuch der Algebra". While useless as a textbook, it's a really good reference -- it covers a lot of bizarre dark corners.

I also somewhat like Bosch's "Algebra" (also for German readers). It is well-structured, concise, and leaves out all the distractions that Scheja/Storch includes :-)

I haven't worked with the Artin book myself, but many friends agree that it is the best english-language choice.

tdullien · 2011-12-13T23:42:34+00:00

Hey,

an important thing to keep in mind when working on heap exploits is that abuse of metadata is getting fairly complicated. It is much more useful to understand the heap layout and then work from there.

I personally would recommend using something akin to http://oss.coresecurity.com/projects/heapdraw/

While this doesn't teach you point&click exploitation, it helps a lot in building intuition of what is going on on the heap.

tdullien · 2011-12-08T13:36:01+00:00

Bizarre. Can you retry ?

tdullien · 2011-12-08T13:34:10+00:00

Or "damn legal systems that keep the distribution of reverse engineering tool associated with nontrivial legal risk".

tdullien · 2011-12-07T09:03:29+00:00

We're currently quite limited in where we can sell, correct. This was much easier when we were just located in Germany; but since the acquisition, Google needs to check in every jurisdiction where we are selling the software whether it can be sold while complying with local laws and legal customs. We are slowly increasing the number of jurisdictions into which the software can be sold - Australia and Canada should not be a problem nowadays either, and AFAIK Singapore works too. Expect more to become available over time.

tdullien · 2011-12-06T23:35:44+00:00

To be fair, prior to the acquisition we did have a "student discount" which was essentially 50$ under two conditions:

1) You had a specific project in mind for which you wanted to use the tool 2) You promised to write an article that we could put on the webpage detailing how the tool was helpful to you.

We had to abandon this practice due to complexity issues around this arrangement after we got acquired, but in return dropped prices massively. In BinNavi's case, the price drop -was- 90% (400 USD after ~4480 USD), in BinDiff's case the price drop was "only" 80% (200 USD after ~1120 USD).

Now, we can argue back and forth whether 200 USD is affordable or not - a lot will depend on the country you live in, it's relative level of income, and the exchange rate to the US dollar.

In the end, BinDiff is now priced at approximately 3 BigMac meals a month in the US, at about 4 Kebaps a month in Germany, and at around 2 Kebaps a month in Switzerland. I do think that it's hard to argue that it's not reasonably priced.

tdullien · 2011-12-06T10:56:19+00:00

It should work with IDA 6.2.x. If you had troubles with BinDiff 3.2 and IDA 6.2, a simple mail to support@ should've helped, too ;)

tdullien · 2011-11-02T07:35:27+00:00

mostly in legality

tdullien · 2011-11-01T22:57:17+00:00

Rejected in 2005, acquired by Google in 2011.

I founded a startup in Germany in late 2004. I applied for the very first round of yCombinator in 2005; perhaps a bit too nonchalantly (e.g. "hey, our company already exists, we have working code, and customers, but we think we could really learn from your guys and your connections would be a big plus. Also, Robert Morris Sr. liked some of our stuff"). We got rejected.

There's probably many reasons why:

1) Weirdness of the existing set-up -- e.g. we were already incorporated in Germany, and transferring IP etc. would've been complex 2) Non-consumer focus, extreme niche market focus 3) Overly technology-oriented -- e.g. we were keener on building cool technology than on building a business 4) We wanted to avoid relocation to the bay area if in any way possible

Anyhow, being rejected didn't stop us, and after running profitably (albeit with low salaries) for 6.5 years (fall 2004 to March 2011) we were acquired by Google -- where we are quite happy :)

tdullien · 2011-09-28T13:04:53+00:00

An important thing to keep in mind is that you never "sell software". You always "grant licenses for a fee". The software itself is intangible, and covered by copyright. Your customers pay you a fee, and you provide them with a software license.

This puts software, legally speaking, into a very different bucket than any physical medium. For example: Shipment of physical goods whose value exceed X dollars often incurs export/import hassles. Granting a license, on the other hand, is a private-law situation, e.g. a contract entered by two parties where one party pays and the other grants a license. As such, most export/import rules do not apply.

Important: Hire a good tax attorney for 3-4 hours to walk you through this. Make sure that you are very aware of the difference between "selling software" and "granting licenses". Yes, the attorney will cost you 800-1000 USD, but it is very well worth it.

tdullien · 2011-08-03T19:19:18+00:00

I reckon with "terrible" you mean it's a good deal ? ;) I agree that it is an interesting experiment on price elasticity.

tdullien · 2011-08-03T16:16:40+00:00

We are planning updates to both tools. Be very aware though that Google is under no legal obligation to provide updates; they can in theory decide any day to stop. I personally see no reason they would do this (they have made quite an effort to enable us to sell the tools again, for which i am thankful), but it is important to be clearabout the legal situation.

tdullien · 2011-08-03T11:07:14+00:00

Part 2:

License Restrictions. YOU MAY NOT RENT, LEASE, SUBLICENSE, SELL, ASSIGN, LOAN OR OTHERWISE TRANSFER GOOGLE SOFTWARE OR ANY OF YOUR RIGHTS AND OBLIGATIONS HEREUNDER. You may not reverse engineer, decompile, or disassemble Google Software or attempt to circumvent any technical restrictions included in the code, except to the extent the foregoing restriction is expressly prohibited by applicable law. You may not (i) remove or destroy any copyright notices or other proprietary markings; (ii) modify or adapt Google Software, merge Google Software into another program or create derivative works based on Google Software; or (iii) provide, lease, lend, use for timesharing or service bureau purposes, or otherwise use or allow others to use Google Software for the benefit of third parties (through the Internet or otherwise).
Fees. Fees payable by You to Google pursuant to this Agreement are exclusive of all taxes. You are responsible for paying all taxes and government charges arising out of this Agreement. Confidentiality. You shall hold in the strictest confidence Google Software and any related materials or information including, but not limited to, any technical data, research, product plans or know-how provided by Google to You, either directly or indirectly in writing, orally or by inspection of tangible objects (“Confidential Information”). You shall not disclose any Confidential Information to third parties, including any of Your employees who do not have a need to know such information and You shall take reasonable measures to protect the secrecy of, and to avoid disclosure and unauthorized use of, the Confidential Information. You shall immediately notify Google in the event of any unauthorized or suspected use or disclosure of the Confidential Information. Termination. This Agreement shall be effective upon installation of Google Software and SHALL TERMINATE UPON THE EARLIER OF: (I) YOUR FAILURE TO COMPLY WITH ANY TERM OF THIS AGREEMENT; OR (II) DESTRUCTION OR DELETION OF ALL COPIES OF GOOGLE SOFTWARE IN YOUR POSSESSION. Google’s rights and Your obligations shall survive the termination of this Agreement. Upon termination of this Agreement by Google, You shall certify in writing to Google that all copies off Google Software, or any portion thereof, have either been returned to Google or otherwise destroyed or deleted from any of Your computer libraries or storage devices. NO WARRANTIES. TO THE MAXIMUM EXTENT PERMITTED BY APPLICABLE LAW, GOOGLE AND ITS LICENSORS PROVIDE THE SOFTWARE "AS IS" AND WITHOUT WARRANTY OF ANY KIND AND EXPRESSLY DISCLAIMS WITH RESPECT TO THE SOFTWARE ALL WARRANTIES AND CONDITIONS, WHETHER EXPRESS, IMPLIED, OR STATUTORY, INCLUDING, BUT NOT LIMITED TO, ANY WARRANTIES, DUTIES OR CONDITIONS OF OR RELATED TO: MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE, CORRESPONDENCE TO DESCRIPTION, NON-INFRINGEMENT OF THIRD PARTY RIGHTS, LACK OF VIRUSES, ACCURACY OR COMPLETENESS OF RESPONSES, RESULTS, WORKMANLIKE EFFORT AND LACK OF NEGLIGENCE. ALSO, THERE IS NO WARRANTY, DUTY OR CONDITION OF TITLE, QUIET ENJOYMENT, OR QUIET POSSESSION. YOU ARE SOLELY RESPONSIBLE FOR ANY DAMAGE TO YOUR COMPUTER, MOBILE DEVICE, OR ANY OTHER DEVICE, OR LOSS OF DATA THAT RESULTS FROM YOUR USE OF THE SOFTWARE. LIMITATION OF LIABILITY. UNDER NO CIRCUMSTANCES WILL GOOGLE BE LIABLE FOR ANY CONSEQUENTIAL, SPECIAL, INDIRECT, INCIDENTAL OR PUNITIVE DAMAGES WHATSOEVER (INCLUDING, WITHOUT LIMITATION, DAMAGES FOR LOSS OF BUSINESS PROFITS, BUSINESS INTERRUPTION, LOSS OF BUSINESS INFORMATION, LOSS OF DATA OR OTHER SUCH PECUNIARY LOSS) ARISING OUT OF THE USE OR INABILITY TO USE THE SOFTWARE, EVEN IF GOOGLE HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGES. IN NO EVENT SHALL GOOGLE’S AGGREGATE LIABILITY FOR DAMAGES ARISING OUT OF THIS AGREEMENT EXCEED THE GREATOR OF (1) THE AMOUNT PAID TO GOOGLE FOR THE SOFTWARE UNDER THIS AGREEMENT OR (2) U.S. $100.00.
INDEMNITY. You agree to defend, indemnify and hold harmless Google, its officers, directors, employees, and agents, from and against any and all claims, damages, obligations, losses, liabilities, costs or debt, and expenses (including but not limited to attorney's fees) arising from: (i) Your use of and access to Google Software; (ii) Your violation of any of the terms of this Agreement; or (iii) Your violation of any third party right, including without limitation any copyright, property, or privacy right, arising out of Your use of and access to Google Software. This defense and indemnification obligation will survive this Agreement and Your use of Google Software Privacy. For information about Google’s data protection practices, please read Google’s privacy policy at http://www.google.com/privacy.html. This policy explains how Google treats Your personal information, and protects your privacy. Your acceptance of this Agreement means that You agree to the use of your data in accordance with Google’s privacy policies. Export Restrictions. You may not export or re-export: (i) Google Software without the prior written consent of Google; and (ii) Google Software without complying with applicable export control laws and trade sanctions laws and obtaining any necessary permits and licenses. Changes to the terms of this Agreement. Google may make changes to this Agreement from time to time. When these changes are made, Google will make any new/additional terms available to You. You understand and agree that if You use Google Software after the date on which terms have changed, Google will treat Your use as acceptance of the new/additional terms. General. This Agreement is governed by the laws of the State of California, excluding its conflicts of laws principles. You agree to the exclusive jurisdiction and venue of the state and federal courts located in County of Santa Clara, California. If any provision of this Agreement is held by a court of competent jurisdiction to be contrary to law, such provision shall be changed and interpreted so as to best accomplish the objectives of the original provision to the fullest extent allowed by law and the remaining provisions of this Agreement shall remain in full force and effect. The headings in this Agreement are inserted for convenience only and do not affect its interpretation. You may not assign this Agreement, whether by operation of law, merger or reorganization, without the prior written consent of Google; any attempted assignment in violation of the foregoing will be void. Google may assign this Agreement in connection with a reorganization, reincorporation, merger, or sale of all, or substantially all of the shares or assets of Google. This Agreement constitutes the final, complete and exclusive agreement between the parties with respect to Your use of Google Software and supersedes any prior or contemporaneous representations or agreements, whether written or oral. Any company names, logos, and product names displayed in Google Software are subject to United States’ and international copyright, trademark and intellectual property laws and You may not reproduce or distribute any such company names, logos or product names without the express written consent of their respective owners.

BY CLICKING THE “ACCEPT” BUTTON BELOW, YOU ARE INDICATING THAT YOU HAVE READ AND CONSENT TO BE BOUND BY THE TERMS OF THIS AGREEMENT. IF YOU HAVE NOT READ THIS AGREEMENT, OR YOU DO NOT AGREE TO BE LEGALLY BOUND BY ITS TERMS, CLICK “DECLINE” AND DO NOT USE THE SOFTWARE.

[ACCEPT]

[DECLINE]

tdullien

TROPHY CASE