GCC compiler “bug” broke my Haxe code

Posted on

In hxBitcoin I have this utility function:

/**
Unsigned greater than comparison.

Returns true if a > b when both a and b are
interpreted as unsigned integers; false otherwise.
**/
public static inline function u32gtu32(a : Int, b : Int) : Bool
{
return (a + -2147483648) > (b + -2147483648); // unsigned comparison, see "Hacker's Delight" p. 25.
}


This nifty little trick is from the most excellent book Hacker’s Delight by Henry S. Warren, Jr.

The function worked great, until I ran my unit tests on Linux. u32gtu32(-2147483648, 2147483647) should return true, but it was returning false. A look at the generated C++ offered nothing obvious:

bool FunInteger_obj::u32gtu32( int a,int b){
return ((a + (int)-2147483648) > (b + (int)-2147483648));
}


To make a long story short, I crafted this simple standalone test:

#include "stdio.h"
extern "C" int main(int argc, char ** argv)
{
int a = -2147483648;
int b = 2147483647;
bool compare = (a + (int)(-2147483648)) > (b + (int)(-2147483648));
printf("result = %d\n", compare ? 1 : 0);
return 0;
}


Now this is where it gets fun and interesting!

$g++ -O2 test.cpp && ./a.out result = 0$ g++ -O0 test.cpp && ./a.out
result = 1


Huh? Sure smells like a compiler optimization bug, doesn’t it?

Turns out this is a feature. For optimization purposes, by default GCC assumes there will be no overflow with integer arithmetic (see this).

There are a number of possible remedies, many of which are unappealing for various reasons (for example, adding -fwrapv or -fno-strict-overflow to the compiler options for Linux builds, or passing a special flag to the Haxe build and implementing the u32gtu32 function differently when necessary).

But this simple fix was just the thing — replace the addition with exclusive-or in the original function:

public static inline function u32gtu32(a : Int, b : Int) : Bool
{
return (a ^ -2147483648) > (b ^ -2147483648); // unsigned comparison, see "Hacker's Delight" p. 25.
}


As a result of this experience, I also added some “run-time tests” — quick tests that are executed at run time even in a distribution release. The reason being that, from the end-user’s perspective, hxBitcoin is a pure Haxe library. The fact that on some platforms it is generated into C++ and compiled automatically by the Haxe/hxcpp framework is an implementation detail. A library user who installs hxBitcoin via haxelib likely will not run the full suite of unit tests. But the validity of the results, as I discovered, can depend greatly on the particulars of the compiler used. (Previously the same code exhibited no issues when compiled as C++ on Windows, OSX, and iOS.) The particular issue I encountered here would cause subtle, silent issues for the end-user without the presence of at least some minimal run-time validation.

Announcing hxBitcoin, the Bitcoin and crypto library for Haxe

Posted on

hxBitcoin is a new open source Bitcoin and cryptocurrency support library in the Haxe language.

The initial release has these features:

• BIP0038 (encrypted private keys), WIF, private & public keys, addresses, Base58
• scrypt, AES, SHA-1, SHA-256, RIPEMD160
• Elliptic curve arithmetic, secp256k1 & NIST curves
• Modular arithmetic (Fp), Arbitrary-size (big) integer, Unicode 7.0

and supports iOS, Windows, OSX, Flash, and NekoVM targets (additional targets are easy, just ask).

It’s a clean, simple API in pure Haxe with no additional or external dependencies.

Built in Haxe, hxBitcoin has extensive reach to enable applications on desktop, mobile, web, and server platforms, targeting C++, Java, JS, PHP, AS3 and more with a single code base.

It’s also backed by an extensive test suite of over 22,000 individual tests and vectors to validate correct behavior on all supported platforms.

To start using, simply install the library via haxelib:

haxelib install hxBitcoin

Here’s an example of how to decrypt a BIP0038 private key:

import com.fundoware.engine.bitcoin.FunBitcoinContext;
import com.fundoware.engine.bitcoin.FunBitcoinEncryptedPrivateKey;
import com.fundoware.engine.bitcoin.FunBitcoinPrivateKey;

var context = new FunBitcoinContext();
var encryptedKey = FunBitcoinEncryptedPrivateKey.fromString(
context, "6PRVWUbkzzsbcVac2qwfssoUJAN1Xhrg6bNk8J7Nzm5H7kxEbn2Nh2ZoGg");
var decryptedKey = encryptedKey.decryptString("TestingOneTwoThree");
encryptedKey.clear();
trace("private key (WIF) = " + decryptedKey.toWIF());
decryptedKey.clear();


Project website: http://hxBitcoin.com

Project on GitHub: http://github.com/cbatson/hxBitcoin

Feature requests are welcome!

How to use Bitcoin Key to create offline private keys

Posted on

The Bitcoin Key app (discussed here) takes the place of rolling dice when creating offline private keys. This is a tutorial of how to use it to create your offline keys.

The process is a bit involved, whether you use dice or the app. So why go to the trouble? Because when done right, keys generated in this way are never exposed to an online computer, and therefore not susceptible to online hacking or digital theft.

When you use an offline computer and print your keys for cold storage, then the problem of security for your keys is limited to securing the physical piece of paper on which your keys are printed, which can be much more manageable than trying to secure an online computer system.

You will need… Read the rest of this entry

Bitcoin Key app: Better than rolling dice?

Posted on

As a result of the apparently poor numerical distribution observed rolling my hex dice (see this earlier post), I was inspired to create an app to take the place of hex dice for the purpose of creating off-line Bitcoin private keys.

Bitcoin Key is now in the iOS App Store.

(At present it’s available only in the U.S., until I can figure out if it’s exempt from U.S. export regulations.)

The app generates a never-ending stream of random hexadecimal digits. The timer in the top-left corner counts down to the next digit, with a new one every two seconds. The previous digit is also shown here.

Move your finger around the screen to add your own randomness.

To create a Bitcoin private key, simply jot down (or enter into your offline computer running a live CD) 64 of the randomly-generated hexadecimal digits.

Worried that the app is recording every single digit produced and sending it somewhere? It’s not. You’re welcome to watch the wi-fi or your home network with a packet sniffer. Besides, even if it was, the collector of the data would have know way of knowing which of the endless stream of digits you’re actually writing down. Heck, maybe you’re only using every 2nd or 3rd digit produced.

Bitcoin Key uses ANSI X9.31 cryptographically secure random number generation via 256-bit AES in counter mode. The 256-bit key that’s fed into the AES comes from the system’s entropy source (SecRandomCopyBytes on iOS). The RNG is re-keyed from system entropy every minute (the timer in the top-right corner).

AES takes a 128-bit block as input. ANSI X9.31 specifies that this is to be a monotonically increasing value for secure random number generation. For this value, Bitcoin Key uses the system’s high-resolution timer (mach_absolute_time on iOS) as the upper 64 bits, and the user entropy value as the lower 64 bits.

The user entropy value is computed as follows: any time finger motion on the screen is sensed, the x,y coordinates of the finger are multiplied together, and the result is then added to the user entropy value.

Is it better than rolling dice? It depends on how you define “better.” Bitcoin Key includes a stats page that shows you a count of how many times each digit has appeared. I personally find that it has more even distribution compared to the hexadecimal dice I used previously.

And, at \$0.99, Bitcoin Key is certainly cheaper than the dice I purchased. Although admittedly, hexadecimal dice have a certain charming appeal, and are a great conversation piece. :-)

secp256k1 Test Vectors

Posted on

Finding test vectors for the secp256k1 curve is challenging. I was able to find some only in this StackExchange answer.

For posterity, here are some additional secp256k1 test vectors that I generated. They are presented in the format of these test vectors for the NIST curves.

 Curve: secp256k1
-------------
k = 1
x = 79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798

k = 2
x = C6047F9441ED7D6D3045406E95C07CD85C778E4B8CEF3CA7ABAC09B95C709EE5
y = 1AE168FEA63DC339A3C58419466CEAEEF7F632653266D0E1236431A950CFE52A

k = 3
x = F9308A019258C31049344F85F89D5229B531C845836F99B08601F113BCE036F9
y = 388F7B0F632DE8140FE337E62A37F3566500A99934C2231B6CB9FD7584B8E672

k = 4
x = E493DBF1C10D80F3581E4904930B1404CC6C13900EE0758474FA94ABE8C4CD13
y = 51ED993EA0D455B75642E2098EA51448D967AE33BFBDFE40CFE97BDC47739922

k = 5
x = 2F8BDE4D1A07209355B4A7250A5C5128E88B84BDDC619AB7CBA8D569B240EFE4
y = D8AC222636E5E3D6D4DBA9DDA6C9C426F788271BAB0D6840DCA87D3AA6AC62D6

k = 6
x = FFF97BD5755EEEA420453A14355235D382F6472F8568A18B2F057A1460297556
y = AE12777AACFBB620F3BE96017F45C560DE80F0F6518FE4A03C870C36B075F297

k = 7
x = 5CBDF0646E5DB4EAA398F365F2EA7A0E3D419B7E0330E39CE92BDDEDCAC4F9BC
y = 6AEBCA40BA255960A3178D6D861A54DBA813D0B813FDE7B5A5082628087264DA

k = 8
x = 2F01E5E15CCA351DAFF3843FB70F3C2F0A1BDD05E5AF888A67784EF3E10A2A01
y = 5C4DA8A741539949293D082A132D13B4C2E213D6BA5B7617B5DA2CB76CBDE904

k = 9

k = 10
x = A0434D9E47F3C86235477C7B1AE6AE5D3442D49B1943C2B752A68E2A47E247C7
y = 893ABA425419BC27A3B6C7E693A24C696F794C2ED877A1593CBEE53B037368D7

k = 11
x = 774AE7F858A9411E5EF4246B70C65AAC5649980BE5C17891BBEC17895DA008CB
y = D984A032EB6B5E190243DD56D7B7B365372DB1E2DFF9D6A8301D74C9C953C61B

k = 12
x = D01115D548E7561B15C38F004D734633687CF4419620095BC5B0F47070AFE85A
y = A9F34FFDC815E0D7A8B64537E17BD81579238C5DD9A86D526B051B13F4062327

k = 13
x = F28773C2D975288BC7D1D205C3748651B075FBC6610E58CDDEEDDF8F19405AA8
y = 0AB0902E8D880A89758212EB65CDAF473A1A06DA521FA91F29B5CB52DB03ED81

k = 14
x = 499FDF9E895E719CFD64E67F07D38E3226AA7B63678949E6E49B241A60E823E4
y = CAC2F6C4B54E855190F044E4A7B3D464464279C27A3F95BCC65F40D403A13F5B

k = 15
y = 581E2872A86C72A683842EC228CC6DEFEA40AF2BD896D3A5C504DC9FF6A26B58

k = 16
x = E60FCE93B59E9EC53011AABC21C23E97B2A31369B87A5AE9C44EE89E2A6DEC0A
y = F7E3507399E595929DB99F34F57937101296891E44D23F0BE1F32CCE69616821

k = 17
x = DEFDEA4CDB677750A420FEE807EACF21EB9898AE79B9768766E4FAA04A2D4A34

k = 18
x = 5601570CB47F238D2B0286DB4A990FA0F3BA28D1A319F5E7CF55C2A2444DA7CC
y = C136C1DC0CBEB930E9E298043589351D81D8E0BC736AE2A1F5192E5E8B061D58

k = 19
x = 2B4EA0A797A443D293EF5CFF444F4979F06ACFEBD7E86D277475656138385B6C
y = 85E89BC037945D93B343083B5A1C86131A01F60C50269763B570C854E5C09B7A

k = 20
x = 4CE119C96E2FA357200B559B2F7DD5A5F02D5290AFF74B03F3E471B273211C97
y = 12BA26DCB10EC1625DA61FA10A844C676162948271D96967450288EE9233DC3A

k = 112233445566778899

k = 112233445566778899112233445566778899
x = E5A2636BCFD412EBF36EC45B19BFB68A1BC5F8632E678132B885F7DF99C5E9B3
y = 736C1CE161AE27B405CAFD2A7520370153C2C861AC51D6C1D5985D9606B45F39

k = 28948022309329048855892746252171976963209391069768726095651290785379540373584
y = 71444009192228730CD8237A490FEBA2AFE3D27D7CC1136BC97E439D13330D55

k = 57896044618658097711785492504343953926418782139537452191302581570759080747168
y = 3F3979BF72AE8202983DC989AEC7F2FF2ED91BDD69CE02FC0700CA100E59DDF3

k = 86844066927987146567678238756515930889628173209306178286953872356138621120752
x = E24CE4BEEE294AA6350FAA67512B99D388693AE4E7F53D19882A6EA169FC1CE1
y = 8B71E83545FC2B5872589F99D948C03108D36797C4DE363EBD3FF6A9E1A95B10

k = 115792089237316195423570985008687907852837564279074904382605163141518161494317
x = 4CE119C96E2FA357200B559B2F7DD5A5F02D5290AFF74B03F3E471B273211C97
y = ED45D9234EF13E9DA259E05EF57BB3989E9D6B7D8E269698BAFD77106DCC1FF5

k = 115792089237316195423570985008687907852837564279074904382605163141518161494318
x = 2B4EA0A797A443D293EF5CFF444F4979F06ACFEBD7E86D277475656138385B6C
y = 7A17643FC86BA26C4CBCF7C4A5E379ECE5FE09F3AFD9689C4A8F37AA1A3F60B5

k = 115792089237316195423570985008687907852837564279074904382605163141518161494319
x = 5601570CB47F238D2B0286DB4A990FA0F3BA28D1A319F5E7CF55C2A2444DA7CC
y = 3EC93E23F34146CF161D67FBCA76CAE27E271F438C951D5E0AE6D1A074F9DED7

k = 115792089237316195423570985008687907852837564279074904382605163141518161494320
x = DEFDEA4CDB677750A420FEE807EACF21EB9898AE79B9768766E4FAA04A2D4A34
y = BDEE54F96B9CAE9716684F152D56C251312E0B5FB56A3F09304E660861A910B8

k = 115792089237316195423570985008687907852837564279074904382605163141518161494321
x = E60FCE93B59E9EC53011AABC21C23E97B2A31369B87A5AE9C44EE89E2A6DEC0A
y = 081CAF8C661A6A6D624660CB0A86C8EFED6976E1BB2DC0F41E0CD330969E940E

k = 115792089237316195423570985008687907852837564279074904382605163141518161494322
y = A7E1D78D57938D597C7BD13DD733921015BF50D427692C5A3AFB235F095D90D7

k = 115792089237316195423570985008687907852837564279074904382605163141518161494323
x = 499FDF9E895E719CFD64E67F07D38E3226AA7B63678949E6E49B241A60E823E4
y = 353D093B4AB17AAE6F0FBB1B584C2B9BB9BD863D85C06A4339A0BF2AFC5EBCD4

k = 115792089237316195423570985008687907852837564279074904382605163141518161494324
x = F28773C2D975288BC7D1D205C3748651B075FBC6610E58CDDEEDDF8F19405AA8

k = 115792089237316195423570985008687907852837564279074904382605163141518161494325
x = D01115D548E7561B15C38F004D734633687CF4419620095BC5B0F47070AFE85A

k = 115792089237316195423570985008687907852837564279074904382605163141518161494326
x = 774AE7F858A9411E5EF4246B70C65AAC5649980BE5C17891BBEC17895DA008CB
y = 267B5FCD1494A1E6FDBC22A928484C9AC8D24E1D20062957CFE28B3536AC3614

k = 115792089237316195423570985008687907852837564279074904382605163141518161494327
x = A0434D9E47F3C86235477C7B1AE6AE5D3442D49B1943C2B752A68E2A47E247C7
y = 76C545BDABE643D85C4938196C5DB3969086B3D127885EA6C3411AC3FC8C9358

k = 115792089237316195423570985008687907852837564279074904382605163141518161494328
y = 33CC76DE4F5826029BC7F68E89C49E165227775BC8A071F0FA33D9D439B05FF8

k = 115792089237316195423570985008687907852837564279074904382605163141518161494329
x = 2F01E5E15CCA351DAFF3843FB70F3C2F0A1BDD05E5AF888A67784EF3E10A2A01
y = A3B25758BEAC66B6D6C2F7D5ECD2EC4B3D1DEC2945A489E84A25D3479342132B

k = 115792089237316195423570985008687907852837564279074904382605163141518161494330
x = 5CBDF0646E5DB4EAA398F365F2EA7A0E3D419B7E0330E39CE92BDDEDCAC4F9BC
y = 951435BF45DAA69F5CE8729279E5AB2457EC2F47EC02184A5AF7D9D6F78D9755

k = 115792089237316195423570985008687907852837564279074904382605163141518161494331
x = FFF97BD5755EEEA420453A14355235D382F6472F8568A18B2F057A1460297556
y = 51ED8885530449DF0C4169FE80BA3A9F217F0F09AE701B5FC378F3C84F8A0998

k = 115792089237316195423570985008687907852837564279074904382605163141518161494332
x = 2F8BDE4D1A07209355B4A7250A5C5128E88B84BDDC619AB7CBA8D569B240EFE4
y = 2753DDD9C91A1C292B24562259363BD90877D8E454F297BF235782C459539959

k = 115792089237316195423570985008687907852837564279074904382605163141518161494333
x = E493DBF1C10D80F3581E4904930B1404CC6C13900EE0758474FA94ABE8C4CD13
y = AE1266C15F2BAA48A9BD1DF6715AEBB7269851CC404201BF30168422B88C630D

k = 115792089237316195423570985008687907852837564279074904382605163141518161494334
x = F9308A019258C31049344F85F89D5229B531C845836F99B08601F113BCE036F9
y = C77084F09CD217EBF01CC819D5C80CA99AFF5666CB3DDCE4934602897B4715BD

k = 115792089237316195423570985008687907852837564279074904382605163141518161494335
x = C6047F9441ED7D6D3045406E95C07CD85C778E4B8CEF3CA7ABAC09B95C709EE5
y = E51E970159C23CC65C3A7BE6B99315110809CD9ACD992F1EDC9BCE55AF301705

k = 115792089237316195423570985008687907852837564279074904382605163141518161494336
x = 79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798
y = B7C52588D95C3B9AA25B0403F1EEF75702E84BB7597AABE663B82F6F04EF2777


Roll Dice for Bitcoin Keys… Good Idea?

Posted on

I recently read about using physical dice to roll private Bitcoin keys, for example here. Intrigued, I ordered a pair of hexadecimal dice from GameStation.

Soon I began to wonder… How random are they? Do rolls result in an expected distribution? Can knowledge of the actual distribution characteristics of the dice be used to narrow private keys generated by this method into a practically searchable space, making such keys more susceptible to discovery?

I rolled my pair of hexadecimal dice 1,014 times for a total of 2,028 samples for the pair. Here are the results:

Already a severe underrepresentation of the values 3 and C is observed.

But how about a goodness of fit test? We begin with a null hypothesis that the dice are fair and distribute evenly. The data yield $\chi^2 \approx 105$. Using a chi square table such as this one and looking at the row for 15 degrees of freedom, we see that the value 105 is off the chart, or p < 0.01. In fact, using this calculator, we see that p < 0.0001. This means the data are very much statistically significant to reject the null hypothesis — indicating that the dice are not observed to be fair over these 2,028 rolls.

Here’s a good article that examines the question of how many rolls give good results for the goodness of fit test.

However, commenter Matthew Neagly makes an interesting point in this post that “the larger your sample size, the more exactly you have to match a potential distribution to not reject a match. So eventually you hit a point where you’re ‘cursed’ to always reject your hypothesis.” In other words, the more rolls, the higher the probability that the test will reject a die as unfair. (He mentions two terms for this phenomenon, “curse of significance” and “doomed to significance,” but I was unable to find any discussion or related use of these terms.)

He also says, “This is one of the reasons why some statisticians favor visual interpretation of plots.” From that perspective, the histogram above is pretty clear.

The dice didn’t have fair distribution for my test… So what? It’s a fair (pun!) question.

At what point are dice “good enough”? Can these dice I’ve acquired, given the apparent wildly uneven distribution observed, be used to create private Bitcoin keys no more susceptible to discovery than keys generated by other means? Is the unevenness attributable to something specific or unique to these two dice or the rolling method/conditions? Or would a similar pattern be observed with other dice, that is, attributable to systemic or common causes in the manufacturing process? Finally, if they are truly fair and random dice, then certainly the exact sequence observed for this test is a valid possibility, however “unfair” it may seem.