2015-06-26

BusyBeaver and the state of near-native code in browsers

Curious how cryptography performs in asm.js vs. Google Native Client? Check it out for yourself:
A description of my path to these examples follows.



I was impressed recently with what I read about Google Native Client, which is embedded in Chrome, and Firefox's asm.js and Emscripten. I was further impressed by how I can play Prince of Persia in my browser, and it works via DOSBox inside JavaScript, and it's actually perfectly playable, aside from key lag. :-)

I've recently been working on BusyBeaver, a new password hashing, key derivation, and proof of work function. Existing commonly used password hashing approaches suffer from extreme brute forcing susceptibility on hardware as widely available as an AMD GPU. BusyBeaver is my attempt to improve upon PBKDF2 and scrypt in its resistance to optimization via execution on a GPU, FPGA, or most anything other than the intended usage platform - a 64-bit, general purpose CPU.

It seems I've done a decent enough job with BusyBeaver, as far as resisting GPU optimization is concerned, so I had the idea to see if I can use Emscripten, or Google Native Client, to have it run in browsers. It would, after all, be useful to a website that wants to offload the CPU cost of rigorous password hashing to the person who is intended to benefit from it — the user.

Oh boy.

Well, first of all, I was able to get BusyBeaver to compile with Emscripten, and it does run in Firefox, IE, and Chrome... in descending order of performance. It will become clear why I say this.

It takes a while for this to execute, but... BAM!



The test vectors run! And they are correct! Yay!

Note that this is an achievement in its own right. This is C++ code, compiled without modification into JavaScript, and it runs in a browser. That's pretty awesome.

But. There are buts.
  • The native EXE compiled with GCC is 100 kB. With Visual Studio 2013, it's 210 kB. With Emscripten, the .js file is 700 kB. Yikes. That's a lot of bandwidth to pay for a key derivation function.
  • In Firefox, the module loads in 150 ms on my computer. That's thanks to the SpiderMonkey optimizations for asm.js. It's probably much more on mobiles... But those run Chrome or Safari.
  • In Firefox, an execution of BusyBeaver with 50,000 operations, which takes about 6 ms in native code, runs for... 500 ms. Mmmm... okay. I guess that asm.js's claims of a factor of 2 slowdown over native compilation with clang are circumstantial, or hyperbolic, or clang must really suck.
  • Even so, I guess the figures in Firefox could work in practice. But how about Chrome?
  • In Chrome, the page is still loading...
  • Okay, so Chrome takes about 30 seconds to load the test page and run one execution of BusyBeaver. Once the page is loaded, subsequent runs take about 2 seconds. Sigh. Clearly, Chrome developers didn't implement the JavaScript optimizations for asm.js that Firefox did - which I guess is because they favor their Native Client.
  • Hey, how about IE? Well, would you look at that. The page loads in about 8 seconds, and then subsequent executions take about 4 seconds each. Not too much different from Chrome; just with a different - in this case better - initial analysis vs. subsequent performance tradeoff.
  • In Chrome on my Samsung Galaxy S4, the script took 311 seconds to load. It then took 13 seconds to calculate a subsequent digest.

Google Native Client

I also adapted BusyBeaver for Google Native Client. Results?
  • The portable executable compiles to 100 kB. Compare to 700 kB with Emscripten.
  • A single digest is calculated in 10 ms. Compare to 500 ms with Firefox and asm.js.
In my opinion - asm.js has:
  • no readability, compatibility, or safety advantage over a portable binary format; and is
  • an order of magnitude less efficient, both in performance and code size.
If you're going to have something as sophisticated as Emscripten, and a proposed standard like asm.js, why not just adopt a proper binary format?

Until then, we have statements like these, coming from Mozilla and Opera:
  • "NaCl seems to be 'yearning for the bad old days, before the web', to paraphrase Tim Berners-Lee."
    -- Håkon Wium Lie, Opera CTO
  • "We don't want to go back to a place where it's just binary delivery over the internet. We've seen people try to do it before."
    -- Chris Blizzard, Mozilla
:-/

2015-06-07

Against the hating of cheaters

Cheating, as in relationships, is not an upstanding thing to do. It is exemplary of an immature, confused, untrustworthy, undependable character. Let me be clear: I don't think it's wrong to fuck around. But it's important to be open about it. Relationships and sex are a big deal to people. If you're going to be doing that with more than one person, make sure that everyone involved is aware, and understands.

Now, that being said - there are those who hate cheaters. I must say I dislike that more than cheating. When it comes to cheating, the well-adjusted person is one who neither cheats, nor hates with a passion. But if I had to choose between a cheater, and someone really sour about it...

The cheater, you see, is only selfish in their seeking of pleasure. But the hater is ignorant and bitter; coercive and entitled in imposing their views. These views tend to be naively monogamous, as if to imply: My expectations should be met. This should just work. I shouldn't have to try to find the right person for it.

Cheating happens within a relationship. If you get cheated on, then you, also, fucked up. You accepted a task: to pick a person, and create a mutually functional relationship with them. You could choose anyone in the world. This is the person you chose; this is the relationship you built.

The pain of being cheated on is emotional. It comes from within, from a clash between expectations and reality. If you didn't take the relationship seriously, there is no pain in the first place. But if you did, then there can be great pain. Those who would rather blame their partner than deal with their emotions try to rationalize reasons to see cheating as an objective wrong, rather than a trigger for their pain.

One way that people try to make cheating an objective wrong is by arguing that cheaters expose their partners to health risks. Yes, technically. But I disagree with a majority of what this is meant to imply.

If you're alive, chances are you've had the flu a number of times, and you're not holding grudges against people about it. You've probably infected people with your flu, and you aren't expecting to be blamed. It's only in the sexual realm that we have this insane expectation that an infection is living proof of shameful sin, instead of something that just happens to people, and that we're trying to solve with medicine.

It's also not your partner's job to protect you. It's your job to protect you. Safety is not something you check off and then forget about. It's something to keep in mind, even with your long-term partner.

Finally, you chose your partner. By choosing your partner, you're choosing all the baggage that comes with them, STDs or not. If you're a poor judge of character; if you create a relationship in which someone cannot be honest, is being coerced, where you don't communicate; if your partner keeps secrets from you, and you don't detect this; all of that is your blindness. All of that is not only on them, but also on you.

A hater of cheating wants to have their cake, and eat it too. They want to have sex, but not incur any of the risks associated with bodily activity. They don't want to take responsibility for choosing a partner. They make themselves vulnerable while building a relationship whose parameters are downright adversarial. Then, in order to feel safer in this choice, they'll consider themselves owner of their partner's genitals.

The cheater seeks only pleasure. The cheater hater seeks to clutch love in their fist. They build relationships on top of taboos that discourage communication. They seek to coerce, to ignore; to make their partner into something they're not. Then, they blame their partner for dishonesty and betrayal.

Next similar post: The ethics of non-consensual monogamy: coercion and dead bedrooms

2015-06-05

Visual C++ ternary operator considered harmful

We've recently begun upgrading our code from Visual Studio 2005 to a newer version, and we ran into the following doozy.

Imagine that you have classes with the following relationships:

// Lightweight reference to data owned by another object.
struct Light { Light(); Light(Light const&); };

// Owns data freed on release. Constructor copies data. Conversion to Light does not copy.
struct Heavy { Heavy(); Heavy(Heavy const&); Heavy(Light const&); operator Light() const; };

In a reasonable world, you would then expect the following code, using the C++ conditional operator:

Light DataOrDefault(Heavy const* h)
    { return h ? *h : Light(); }          // BAD BAD BAD!

... to work like this code using a simple if statement:

Light DataOrDefault(Heavy const* h)
    { if (h) return *h; return Light(); }       // OK

... or like this code, using a template:

template <class T> inline T Cond(bool expr, T a, T b)
    { return expr ? a : b; }

Light DataOrDefault(Heavy const* h)
    { return Cond<Light>(h, *h, Light()); }     // OK

But it does not. Do you know how it works? This is how it works.

Light DataOrDefault(Heavy const* h)
{
    // Actual behavior of: h ? *h : Light()
    Heavy t;
    if (h)
        t = *h;
    else
        t = Light();
    return t;
}

Yes. The compiler decides that the common type of the two expressions is Heavy. A temporary Heavy object is then constructed to hold this result. A copy of the data is constructed; the copy is assigned to Light; and then it is promptly destroyed, so that Light now points to invalid data.

In GCC, this produces an error. But in Visual Studio, there is no warning, even with -Wall:



Which of the two behaviors is standards-compliant, I do not know. (Added: In comments, Lee Killough argues persuasively that GCC is compliant; VC++ is not.)

On the MSDN page for the conditional operator, you can find this notice:


The compiler authors are themselves warning you this behavior is bad, and telling you not to use this operator.

Let it be clear: my concern is not making the ambiguous code work. It's to prevent it from compiling in the first place. It should at least cause a warning, so that ambiguities can be found and rooted out, and so that new ambiguities will not be implemented.

I can visually check the code, but can I write it in a way that, if it was unsafe, it would produce a warning? What if there's a conversion I didn't think of? The code would just compile silently.

Workaround?

Due to namespace issues, I dislike macros, but this lambda-based macro is the best I've come up with:

#define If(EXPR, T, A, B) \
    (([&]()> T { if (EXPR) return (A); return (B); })())

You might be surprised at the performance. Using Visual Studio 2010, in the Debug configuration, it's only slightly slower than the ternary operator. In the Release version, it is several times faster. (And I did attempt to make sure that the useful effect of the code is not being optimized away.)

Further discussion

Some argue the real danger is the implicit conversions between Heavy and Light. I find this not to be the case. The conversions are safe and intuitive in other situations. The following, for example, will not build:

template <class T> inline T Cond(bool expr, T a, T b)
    { return expr ? a : b; }

Light DataOrDefault(Heavy const* h)
    { return Cond(h, *h, Light()); }    // Compiler error: T is ambiguous

Here, the compiler observes that the template type T could be either Light or Heavy. It refuses to make a potentially unsafe and incorrect assumption, and requires the type to be specified:

Light DataOrDefault(Heavy const* h)
    { return Cond<Light>(h, *h, Light()); }     // OK

In the case of the ternary operator, MSVC simply goes ahead with one of the possible paths; often one that is very counter-intuitive. There is no error, no warning.

If we just swap the operands as follows:

Light DataOrDefault(Heavy const* h)
    { return !h ? Light() : *h; }

... the compiler decides the proper type to use is Light, and the code will work fine.


2015-06-05: Ongoing edits in response to comments.
2015-06-06: Used tohtml.com/cpp for syntax highlighting instead of images.