INSIGHTS | August 25, 2015

Money may grow on trees

By Fernando Arnaboldi

Sometimes when buying something that costs $0.99 USD (99 cents) or $1.01 USD (one dollar and one cent), you may pay an even dollar. Either you or the cashier may not care about the remaining penny, and so one of you takes a small loss or profit.

 

Rounding at the cash register is a common practice, just as it is in programming languages when dealing with very small or very large numbers. I will describe here how an attacker can make a profit when dealing with the rounding mechanisms of programming languages.
 
Lack of precision in numbers

IEEE 754 standard has defined floating point numbers for more than 30 years. The requirements that guided the formulation of the standard for binary floating-point arithmetic provided for the development of very high-precision arithmetic.

 

The standard defines how operations with floating point numbers should be performed, and also defines standard behavior for abnormal operations. It identifies five possible types of floating point exceptions: invalid operation (highest priority), division by zero, overflow, underflow, and inexact (lowest priority).

 

We will explore what happens when inexact floating point exceptions are triggered. The rounded result of a valid operation can be different from the real (and sometimes infinitely precise) result and certain operations may go unnoticed.
 
Rounding
Rounding takes an exact number and, if necessary, modifies it to fit in the destination’s format. Normally, programming languages do not alert for the inexact exception and instead just deliver the rounded value. Nevertheless, documentation for programming languages contains some warnings about this:

 

To exemplify this matter, this is how the number 0.1 looks internally in Python:

 

The decimal value 0.1 cannot be represented precisely when using binary notation, since it is an infinite number in base 2. Python will round the previous number to 0.1 before showing the value.
 
Salami slicing the decimals

Salami slicing refers to a series of small actions that will produce a result that would be impossible to perform all at once. In this case, we will grab the smallest amount of decimals that are being ignored by the programming language and use that for profit.

 

Let’s start to grab some decimals in a way that goes unnoticed by the programming language. Certain calculations will trigger more obvious differences using certain specific values. For example, notice what happens when using v8 (Google’s open source JavaScript engine) to add the values 0.1 plus 0.2:

 

Perhaps we could take some of those decimals without JavaScript noticing:

 

 

 

But what happens if we are greedy? How much can we take without JavaScript noticing?

 
 
That’s interesting; we learned that it is even possible to take more than what was shown, but no more than 0.00000000000000008 from that operation before JavaScript notices.
I created a sample bank application to explain this, pennies.js:
 
// This is used to wire money
function wire(deposit, money, withdraw) {
  account[deposit] += money;
  account[withdraw] -= money;
  if(account[withdraw]<0)
    return 1; // Error! The account can not have a negative balance
  return 0;
}
 
// This is used to print the balance
function print_balance(time) {
  print(“——————————————–“);
  print(” The balance of the bank accounts is:”);
  print(” Account 0: “+account[0]+” u$s”);
  print(” Account 1: “+account[1]+” u$s (profit)”);
  print(” Overall money: “+(account[0]+account[1]))
  print(“——————————————–“);
  if(typeof time !== ‘undefined’) {
     print(” Estimated daily profit: “+( (60*60*24/time) * account[1] ) );
     print(“——————————————–“);
  }
}
 
// This is used to set the default initial values
function reset_values() {
  account[0] = initial_deposit;
  account[1] = 0; // I will save my profit here 
}
 
account = new Array();
initial_deposit = 1000000;
profit = 0
print(“n1) Searching for the best profit”);
for(i = 0.000000000000000001; i < 0.1; i+=0.0000000000000000001) {
  reset_values();
  wire(1, i, 0); // I will transfer some cents from the account 0 to the account 1
  if(account[0]==initial_deposit && i>profit) {
    profit = i;
 //   print(“I can grab “+profit.toPrecision(21));
  } else {
    break;
  }
}
print(”   Found: “+profit.toPrecision(21));
print(“n2) Let’s start moving some money:”);
 
reset_values();
 
start = new Date().getTime() / 1000;
for (j = 0; j < 10000000000; j++) {
  for (i = 0; i < 1000000000; i++) { 
    wire(1, profit, 0); // I will transfer some cents from the account 0 to the account 1
  }
  finish = new Date().getTime() / 1000;
  print_balance(finish-start);
}
 

The attack against it will have two phases. In the first phase, we will determine the maximum amount of decimals that we are allowed to take from an account before the language notices something is missing. This amount is related to the value from which we are we taking: the higher the value, the higher the amount of decimals. Our Bank Account 0 will have $1,000,000 USD to start with, and we will deposit our profits to a secondary Account 1:

 

Due to the decimals being silently shifted to Account 1, the bank now believes that it has more money than it actually has.

 

Another possibility to abuse the loss of precision is what happens when dealing with large numbers. The problem becomes visible when using at least 17 digits.
 

Now, the sample attack application will occur on a crypto currency, fakecoin.js:

 

 
// This is used to wire money
function wire(deposit, money, withdraw) {
  account[deposit] += money;
  account[withdraw] -= money;
  if(account[withdraw]<0) {
    return 1; // Error! The account can not have a negative balance
  }
  return 0;
}
 
// This is used to print the balance
function print_balance(time) {
  print(“————————————————-“);
  print(” The general balance is:”);
  print(” Crypto coin:  “+crypto_coin);
  print(” Crypto value: “+crypto_value);
  print(” Crypto cash:  “+(account[0]*crypto_value)+” u$s”);
  print(” Account 0: “+account[0]+” coins”);
  print(” Account 1: “+account[1]+” coins”);
  print(” Overall value: “+( ( account[0] + account[1] ) * crypto_value )+” u$s”)
  print(“————————————————-“);
  if(typeof time !== ‘undefined’) {
     seconds_in_a_day = 60*60*24;
     print(” Estimated daily profit: “+( (seconds_in_a_day/time) * account[1] * crypto_value) +” u$s”);
     print(“————————————————-n”);
  }
}
 
// This is used to set the default initial values
function reset_values() {
  account[0] = initial_deposit;
  account[1] = 0; // profit
}
 
// My initial money
initial_deposit = 10000000000000000;
crypto_coin = “Fakecoin”
crypto_value = 0.00000000011;
 
// Here I have my bank accounts defined
account = new Array();
 
print(“n1) Searching for the best profit”);
profit = 0
for (j = 1; j < initial_deposit; j+=1) {
  reset_values();
  wire(1, j, 0); // I will transfer a few cents from the account 0 to the account 1
  if(account[0]==initial_deposit && j > profit) {
    profit = j;
  } else {
    break;
  }
}
print(”   Found: “+profit);
reset_values();
start = new Date().getTime() / 1000;
print(“n2) Let’s start moving some money”);
for (j = 0; j < 10000000000; j++) {
  for (i = 0; i < 1000000000; i++) { 
    wire(1, profit, 0); // I will transfer my 29 cents from the account 0 to the account 1
  }
  finish = new Date().getTime() / 1000;
  print_balance(finish-start);
}
 
 
We will buy 10000000000000000 units of Fakecoin (with each coin valued at $0.00000000011 USD) for a total value of $1,100,000 USD. We will transfer one Fakecoin at the time from Account 0 to a second account that will hold our profits (Account 1). JavaScript will not notice the missing Fakecoin from Account 0, and will allow us to profit a total of approximately $2,300 USD per day:

Depending on the implementation, a hacker can used either float numbers or large numbers to generate money out of thin air.
 
Conclusion
In conclusion, programmers can avoid inexact floating point exceptions with some best practices:
  • If you rely on values that use decimal numbers, use specialized variables like BigInteger in Java.
  • Do not allow values larger than 16 digits to be stored in variables and truncate decimals, or
  • Use libraries that rely on quadruple precision (that is, twice the amount of regular precision).