[e-lang] An attack on a mint

David Wagner daw at cs.berkeley.edu
Sun Mar 2 20:34:14 EST 2008


I'd like to propose an attack on the Mint described in the
Caja spec.  (I couldn't find the definitive, up-to-date description
of the MintMaker pattern, so I don't know if this attack applies
generally.)  Would anyone be interested to take a look and see whether
I've missed anything?

I've reprinted the Mint code from the Caja spec:

  function Mint() {
    var brand = Brand();
    return function Purse(balance) {
      caja.enforceNat(balance);
      function decr(amount) {
        caja.enforceNat(amount);
        balance = caja.enforceNat(balance - amount);
      }
      return caja.freeze({
        getBalance: function() { return balance; },
        makePurse: function() { return Purse(0); },
        getDecr: function() { return brand.seal(decr); },
        deposit: function(amount,src) {
          var newBal = caja.enforceNat(balance+amount);
          var box = src.getDecr();
          brand.unseal(box)(amount);
          balance = newBal; // See Footnote 1
        }
      });
    }
  }

This code is claimed to enforce conservation of currency.

Suppose we create a Mint and a primordial Purse:
  var prim = Mint().Purse(1000);
Then we create a small purse for Andy the Attacker and give him
$100:
  var alligator =  prim.makePurse();
  alligator.deposit(100, prim);
To mount the attack, Andy creates several purses of his own and
a fake purse, and then he mounts the attack:
  var snakeskin = alligator.makePurse();
  var leather = alligator.makePurse();
  leather.deposit(50, alligator);
  var fake = {
    getDecr: function() {
      snakeskin.deposit(50, leather);
      return alligator.getDecr();
    }
  }
  // Here alligator has $50, leather has $50, snakeskin has $0
  leather.deposit(50, fake);
  // Here alligator has $0, leather has $100, snakeskin has $50
In this attack, Andy has created money out of thin air, violating
conservation of currency.

Here's what happens in the attack.  The leather.deposit() method sets
newBal to $100, then executes fake.getDecr(), which transfers $50 from the
leather purse to the snakeskin purse.  At that point, snakeskin.balance
= $50 and leather.balance = $0, but leather.deposit()'s newBal still
contains $0.  (The expected invariant newBal = leather.balance + amount
was true before calling fake.getDecr(), and the programmer might expect
it to remain true for the rest of the execution of the leather.deposit()
method, but in fact this invariant has been invalidated by the call
to fake.getDecr().)  Finally leather.deposit() sets leather.balance to
newBal, i.e., to $100.  The problem is that Purses are not safe for
reentrant calls.

Does this attack look correct to you?  Is it already known?  Does it
affect other variants of the MintMaker?

I found this attack using trust analysis (i.e., taint analysis) and
looking for opportunities for "plan interference".  Everywhere that
trusted code invokes an untrusted function is an opportunity for "plan
interference".

In a language with static typing, this particular attack could be
prevented by making Purse be a final class and declaring the deposit()
function to accept an integer and a Purse.  This prevents creation of
fake purses and ensures that we can trust the behavior of src.getDecr().
However, it isn't enough to fix the MintMaker.

Here is a second attack, closely related to the first, that doesn't
require creation of fake purses.  Assume the same initial setup as above,
so that Andy has an alligator purse containing $100.  He can execute
  // Here the alligator purse has $100
  alligator.deposit(100, alligator);
  // Here the alligator purse has $200
This works because of unexpected aliasing.  The deposit() method
first sets newBal to $200, then decreases alligator.balance by 100
down to $0, then sets alligator.balance to $200.  This second attack
can be fixed by changing the code of deposit() to look like this:
        deposit: function(amount,src) {
          caja.enforceNat(amount);
          var box = src.getDecr();
          brand.unseal(box)(amount);
          balance = caja.enforceNat(balance+amount);
        }
(I seem to recall discussing this second attack when we did the
Waterken security review.  I think Tyler may have already applied
the second transformation to defeat the second attack -- though I
cannot remember.  I'll note that the MintMaker in "The Ode" already
does contain this fix.)

As far as I tell, the second fix may be enough to defeat both
attacks -- even without some kind of type-checking to ensure that
the src parameter is a real Purse.  However I could certainly be
missing something, so others may want to double-check this.

There seem to be many versions of the MintMaker floating around.  Is
there a definitive, latest, greatest implementation?

I'd identify two lessons:

1) I'll notice that, with the second fix, it's effectively as though the
first thing the deposit() method does is to call src.getDecr().  Of course
that step is something deposit()'s caller could have done itself;
deposit() just does it as a convenience to its caller.  When invoking
untrusted code is the first thing you do, and if the caller could have
done it itself, there doesn't seem to be much of an opportunity for
plan interference.  Similarly, if the last thing you do is to invoke
untrusted code, there doesn't seem to be much of an opportunity for plan
interference (but we must be careful: if you invoke untrusted code, then
return a value that you had saved from before, you can easily have plan
interference -- so in this case, we'd better say that invoking untrusted
code was the next-to-last thing you did, and the last thing you did was
to return a value.)  The greatest risk of plan interference comes when
invoking trusted code in the middle of a sequence of steps.

So, this suggests a principle for code reviewers: be most alert for
plan interference hazards when invoking untrusted code in the middle of
a sequence of steps.  Likewise, a principle for code authors: you can
make it easier to review code for plan interference hazards by moving
invocations of untrusted code to the very first (or last) thing you do and
ensuring that the caller could have done that invocation itself instead.

2) Types can help ensure trustworthy behavior of objects you're relying
upon.  Here's a suggested coding pattern: All methods that are part
of a security perimeter should check that all untrusted values (their
arguments, any values received from untrusted code) are of the expected
type before using them.  Also, all relied-upon types should be made final
so they cannot be subclassed or extended by untrustworthy code.  Then,
when you see a method call on an object whose is known and known to be
final, you can rely upon the behavior of that method call.

This coding pattern is neither necessary nor sufficient for security,
but it seems to improve robustness against some kinds of attacks.  It is
most natural in a statically typed programming language, but can also
be applied in dynamically typed languages with guards (like E).  Also,
you can use sealer/unsealer pairs to simulate this pattern, though it
becomes more clumsy.


Any comments/reactions?



Footnote 1: The Caja spec actually has "balance += newBal;", but
I assume that's a typo.

P.S. I don't know if e-lang is the best place for this email.  Feel
free to forward it elsewhere if there is some more appropriate place
for this discussion.


More information about the e-lang mailing list