ASM.js based backend

[indolering]

I just wanted to hang a link to these ASM.js benchmarks of the NaCL crypto library for anyone interested in porting this to Firefox/Firefox OS.

[TheBlueMatt]

All of the NaCL stuff is optional, you can do it pure js if you want already. Really I'm not sure what the way forward is, the curve25519 stuff in js is, afaik, completely unaudited, but I would like to remove all of the nacl stuff anyway. Maybe we can get curve25519 in webcrypto, but I'm not holding my breath.

[indolering]

I'm not an expert (hence the lack of PR requests) but if you are using the emscripten port then I would assume that the only thing you would need to have audited are cache-timings and similar low-level stuff that dynamic languages can mess up. I'm unsure if they important for curve25519 in particular.

[TheBlueMatt]

Yes, one of my major reservations about doing any crypto in js (hence the use of nacl to begin with) is the ability of dynamic on-the-fly-compiled languages to hugely fuck up side-channel leakages that were at least somewhat restricted in better implementations.

[indolering]

Well, this is promising,
"...asm.js code in firefox for example would be guaranteed to not have branches for overflow checks, for example..."

So yeah, I guess the best strategy would be to wait until WebCrypto gets worked out and then maintain the native client and ASM implementations for curve25519 in FireFox and Chrome. There is zero reason to worry about Safari or IE.

[rpicard]

Just leaving a note here that I'm going to spend my bench time at work this week looking into compiling curve25519 with emscripten. I'll keep this ticket updated.

[codedust]

👍

[garrettr]

Maybe we can get curve25519 in webcrypto, but I'm not holding my breath

Here's the working group bug for this request, if you want to get involved. I agree that we should not block any of this project on Web Crypto (but it would nice to be able to use Web Crypto when it's ready and supports the algos we need).

[garrettr]

@rpicard Have you looked at js-nacl? That has an asm.js curve25519 implementation in there somewhere, maybe you can pull it out and give it an appropriate interface somehow?

[rpicard]

@garrettr I'll look into that, but I'll probably stick with this emscripten compiled version. I think I'm pretty close to getting it working, then I'll wrap it up in a nice interface.

[rpicard]

I officially have a working emscripten port. 👍

My to-do list is now:

1. Wrap it up in a pretty API
2. Organize the repo and compile everything into a curve25519.js lib
3. Have it looked over by our crypto guys
4. Integrate into TextSecure browser

I'll refrain from releasing it until 3 is done. I don't want to put anything out there that has glaring security issues.

[indolering]

A bunch of relevant discussion on this topic happened over in ticket #42, mainly this.

TL;DR Google's end-to-end library has a non-emscripten library which appears to have addressed side-channel attacks and is eligible for Google's bug bounty program. It might be better to borrow their code which was designed to be safe while operating in a JIT rather than hope that emscripten carries the c-based protections forward.

[rpicard]

So I have a working emscripten compilation ready to release once it's been looked over. I do think it might make sense to trust Google over an emscripten version, as it's much more likely to be reviewed thoroughly. There's just no way you can go through the mess that emscripten compiles and follow it all.

With that said, what are the side channel attacks that we are concerned about in the extension? It's my understanding that the concern with an algorithm like this would be measuring how much work it does to figure out the exponent (i.e. the keys). Is there any way for an attacker to measure such a thing in a browser extension?

I'm admittedly still a novice with regards to crypto, so feel free to correct the crap out of me.

[indolering]

I would strongly suggest posting directly to the ticket I created for End-To-End, their engineers are actively discussing these concerns. They are probably willing to answer these questions.

[rpicard]

This is a tough one. I don't feel that I'm qualified to make a decision on this.

[TheBlueMatt]

Though I'm not sure about v8, my understanding of the way firefox handles asm.js code is to simply verify its correctness and then translate it into asm without an optimization pass. So even if it isn't ideal in chrome, it may make sense in firefox. Either way, it would be strictly better than what we have now.

Maybe I should reach out to someone on the v8 and Mozilla asm.js teams and ask for their much better-informed opinions.

On June 17, 2014 2:48:59 AM EDT, Robert Picard notifications@github.com wrote:

This is a tough one. I don't feel that I'm qualified to make a decision
on this.

---

Reply to this email directly or view it on GitHub:
#41 (comment)

[rpicard]

@TheBlueMatt I think that'd be a good idea. You're right about it at least being better than what's in there now. Let me know if you'd like me to give you or anyone in particular access to my repo.

[rpicard]

I just commented on the e2e thread as well.

[rpicard]

@TheBlueMatt I think we're probably best going with e2e's implementation rather than my emscripten port. Maybe e2e won't be perfect, but it's more likely to work right than emscripten from where I stand. That's my vote.

[TheBlueMatt]

Really? I disagree entirely. Especially for firefox, asm.js makes way more sense to me.

On June 19, 2014 7:25:55 PM EDT, Robert Picard notifications@github.com wrote:

@TheBlueMatt I think we're probably best going with e2e's
implementation rather than my emscripten port. Maybe e2e won't be
perfect, but it's more likely to work right than emscripten from where
I stand. That's my vote.

---

Reply to this email directly or view it on GitHub:
#41 (comment)

[rpicard]

@TheBlueMatt From a security perspective or for other reasons?

[indolering]

I get where TheBlueMatt is coming from here: the Google engineers are only worried about its use in V8 and if the Firefox JIT and Emscripten do not optimize out the protections present in the original library then we are better off using Asm.js for Firefox and E2E for everything else (since it at least tries to protect against JIT optimizations).

rpicard, could you get your "crypto guys" to weigh in on this?

[TheBlueMatt]

To sum up my current understanding (which is mostly based on skimming and reading overviews of how things work):

• Our current curve25519.js has a number of problems. Namely, it is,
  AFAIK, unaudited, but afaict it is essentially a 1:1 conversion from C
  (probably curve25519-donna) to JS. Assuming we get to the last level of compilation, this should, in a simplified jit model, be checks that we're calling with the right argument types and (which are constant time and always true) and then it should run essentially the same as native.
• end-to-end: Their threat-model is, afaict, just to protect you
  against websites and other plugins within the browser. They rightly
  point out that if someone has access to run code on your computer,
  you're probably hosed no matter what, however, AFAICT, they neglect to
  really consider side-channels where someone might be able to identify
  private key material based solely on other side-channels, such as power
  usage, timing, electro-magnetic radiation, or even the sound your
  processor makes (seriously, all of these have been used to steal private
  key material...). Even worse, their curve25519 implementation appears to be a generic ec one, losing the nice properties that curve25519 provides.
• asm.js is, in firefox's engine, is used to derive types so it can fix some type checking and optimize earlier. This, afaict, means this is effectively the same as our current implementation except we get an ahead-of-time compiler instead of a just-in-time one!

Matt

On 06/20/14 15:15, Robert Picard wrote:

@TheBlueMatt https://github.com/TheBlueMatt From a security
perspective or for other reasons?

—
Reply to this email directly or view it on GitHub
#41 (comment).

[indolering]

I went over this with a very smart friend of mine and he said timing attacks are really only relevant on multi-user systems in and VMs. It's important for SSH, but not here. An attacker would have to flood the user with messages and run arbitrary code in the background to collect performance data. I think E2E relies on user interaction to try and combat this attack, and perhaps we could do the same.

I think this analysis makes performance and maintenance the core questions here. E2E has engineers paid to work on it, but the emscripten port isn't that much effort and I am concerned about performance on mobile devices.

[ghost]

@rpicard Might not be important since an implementation hasn't been decided yet but since you recommend pulling straight from agl's repo effa07c, it's not clear from the instructions if you made the same modification to it d213cb0 as here.

[rpicard]

@indolering I've talked to them about it a little, but they're pretty busy so they might not have the time to go through the massive mess that emscripten compiles to.

Regarding the attack vector, I do think that side channel attacks are mitigated by the particular use case we have. The user interaction thing is probably the best way to go, just to be sure, but there shouldn't be a way for someone to flood the user's machine with messages. If I'm not mistaken, it would require some massive amount of messages to do any sort of meaningful side channel analysis.

@maxrmp Why was that change made? Changing stuff in crypto code seems like a pretty bad idea as a general rule. If it's needed, why isn't it propagated back upstream?

[indolering]

@rpicard being unable to trust Emscripten/LLVM puts a large burden on your crypto people.

The threat model would appear to precludes side-channel attacks, meaning that the primary concern is over the correctness of the implementation. E2E is designed to survive a JIT and it has paid Google engineers working on it.

The use case also largely mitigates my usability concerns: the amount of encryption/decryption going on here is very low, a few messages at a time on the users own machine. I seriously doubt that speed will be a problem.

Unless there is some show-stopper reason not to use E2E, I vote to adopt E2E and close this ticket.

Even worse, their curve25519 implementation appears to be a generic ec one, losing the nice properties that curve25519 provides.

@TheBlueMatt could you elaborate on this?

[liliakai]

An attacker would have to flood the user with messages and run arbitrary code in the background to collect performance data.

there shouldn't be a way for someone to flood the user's machine with messages.

As an aside, the server rate-limits outgoing messages to about 1 message per second per client (and new client registrations to 2/minute).

Timing attacks are further mitigated at the protocol level by our use of ephemeral keys (?).

[ghost]

Why was that change made? Changing stuff in crypto code seems like a pretty bad idea as a general rule. If it's needed, why isn't it propagated back upstream?

@rpicard You would have to ask the developers. My understanding is it is a tweak for their needs only, much like their non standard HKDF.

It is done in the "untrusted" implementation as well.

[indolering]

Timing attacks are further mitigated at the protocol level by our use of ephemeral keys (?).

I raised this point with my friend who replied that making ephemeral keys still requires the use of the private keys. I wasn't sure how that specific analysis applied here, however, I got the drift that it made it still made it harder for the attacker. His overall point, however, was that it was already really hard anyway.

[TheBlueMatt]

end-to-end's model requires user interaction for any signing operation, which they claim mitigates side-channel attacks. Indeed, most side-channel attacks (such as timing ones which rely on precise timing) are mitigated by such methods. However, I think we should target for the most secure implementation, whether the attacks seem unlikely or not (some of the side-channel stuff is astounding, really). Especially since we're depending on EC multiplies, which, in many methods, branches based on the bits in private keys and does different work in either case (just about the worst possible case for side-channel attacks).

In this model, I think end-to-end's implementation is maybe one of the worse ideas of which implementation to pick. Its not a curve25519 implementation, its a generic EC one which has the curve25519 parameters specified. Curve25519 has some very specific parameters picked st. you can avoid some side-channels (ie keys always start with a constant or something like that IIRC). I'm not sure if using a generic EC implementation gets rid of some of the constant-time optimizations curve25519 provides, but it certainly cant help.

re: d213cb0 That's a TextSecure-specific thing where we get a different constant bit in public keys to differentiate identity keys from other types of keys. (there is some thing where you can fake a session if you dont do this, though its fairly non-exploitable IIRC...you'd have to ask Moxie for details on that one).

[TheBlueMatt]

re: Side-channels specific to TS: Yes, we are saved some by not using the identity key very often and using all other keys only once, but we should still be careful because the identity key is used to ECDH more than once.

[TheBlueMatt]

s/signing/ECDH/ in above comments, though it still applies since we still use EC multiplies with private points.

[TheBlueMatt]

To sum up the discussion, I think we're left with: is it worth maintaining something ourselves (ie curve25519.js or curve25519.ASM.js) that may be better in theory or do we give up and use end-to-end's implementation as it has some people full-time using it (does anyone know any of the engineers on the end-to-end team?)

[rpicard]

@TheBlueMatt How do we know that emscripten is actually maintaining the constant time optimizations that the C file makes? That's the real problem here I think. Which is more likely to have side-channel vulnerabilities, emscripten's compilation or end-to-end? I don't know enough about emscripten to answer that.

[TheBlueMatt]

My understanding of emscripten is that it runs the c through clang/llvm, including maybe an optimization pass (which is the same stuff that you would do normally, this shouldn't result in any surprises). Its just the javascript pass that is of concern, but it's the same concern whether we're in emscripten or end-to-end, just a question of how it optimizes the code in question. If we were to assume all code were correct, my guess would be the current code might be best for this (though maybe with only one function instead of a bunch and with an initialization pass of a few hundred calls to make it optimize right away). In firefox, asm.js is likely best by far, but I'd still think it is good in chromium too. Really, I'm just hesitant to use end-to-end's implementation since it appears to just be a generic ec and not an actual curve25519.

Matt

On June 26, 2014 7:32:58 PM EDT, Robert Picard notifications@github.com wrote:

@TheBlueMatt How do we know that emscripten is actually maintaining the
constant time optimizations that the C file makes? That's the real
problem here I think. Which is more likely to have side-channel
vulnerabilities, emscripten's compilation or end-to-end? I don't know
enough about emscripten to answer that.

---

Reply to this email directly or view it on GitHub:
#41 (comment)

[indolering]

I think it's clear that we need to just let the cryptographers make the call here. We are all second guessing best-practices, it's time for someoone who understands everything at a low level to sort this out.

[rpicard]

@indolering 👍

[TheBlueMatt]

That plus I think we need to reach out to people on the asm.js and v8 teams. They should be able to provide far more insight into what the js engine is likely to optimize away and what its not going to. Has there been any academic research into js crypto side channels?

On June 28, 2014 5:06:38 AM EDT, Robert Picard notifications@github.com wrote:

@indolering 👍

---

Reply to this email directly or view it on GitHub:
#41 (comment)

[ghost]

E2E's implementation looks nuked from the repo in the latest push, for whatever reason. Whoops, my mistake.

[liliakai]

No, just moved. https://code.google.com/p/end-to-end/source/diff?spec=svnb6a0b9b8cde9c446f42bc81d4bd7d394996e10b7&r=b6a0b9b8cde9c446f42bc81d4bd7d394996e10b7&format=side&path=/javascript/crypto/e2e/ecc/curve/curve25519.js&old_path=/javascript/crypto/e2e/ecc/curve_curve25519.js&old=ed4a8aa0a9d9def3dfb5794ab6c1785af54c05fb

[rpicard]

@TheBlueMatt Have you been in contact with those teams? What's the status of this?

[TheBlueMatt]

No, I had not. I'm working on this now.

On 07/17/14 16:22, Robert Picard wrote:

@TheBlueMatt https://github.com/TheBlueMatt Have you been in contact
with those teams? What's the status of this?

—
Reply to this email directly or view it on GitHub
#41 (comment).

[rpicard]

Cool beans. 👍

[TheBlueMatt]

Not a very confident answer, but this seems to agree with my initial intuition https://twitter.com/kripken/status/490338413770330112

[rpicard]

@TheBlueMatt I think we can safely disregard that answer for our purposes, as they don't seem to be particularly well informed on the issue.

[TheBlueMatt]

Yea, I mostly agree, but I have yet to find someone better versed here, and his answer does make a lot of sense in theory.

[rpicard]

I still feel the same about the security questions, but I made my curve25519.js repo public for reference. https://github.com/rpicard/curve25519.js

[zmanian]

@TheBlueMatt Just follow up our discussion last night,

Axolotl v3 requires both ed25519 and curve25519.

My memory of the state of tweet-nacl.js was partially correct. It does implement both curves but there is no key conversion function implemented. This might be something the various parties using tweetnacl might have use for. The Stellar implementation only use public keys for signatures. The minilock implementation only uses keys of encryption. They might both be interesting is using a common keypair for both use cases.
https://github.com/dchest/tweetnacl-js

I did a little bit of research into key conversion and found a brief discussion of key conversion here. Will look into it more closely.
https://stackoverflow.com/questions/19147619/what-implementions-of-ed25519-exist

[TheBlueMatt]

Yea, as mentioned there converting ed25519->curve25519 is doable, but curve25519->ed25519 (which v3 does) has an issue where each curve25519 key corresponds to 2 ed25519 keys.

Thus, short of either Chromium NaCL or asm.js, I'm not sure we have any other options anymore with v3 :(.

[midi]

i'm curious, from reading this thread i'm getting the message that a firefox extension is currently not planned due to problems, is this correct?
will chromium be the only open source platform, to run signal for desktop?

[TheBlueMatt]

No, quite the opposite. Due to issues with NaCL (and a strong desire to work outside of chromium), we'll probably be moving towards the asm.js version in the fugure.

[midi]

@TheBlueMatt that's a relief to hear. i'm so excited for this extension. desktop support is huge (having to use hangouts for cases where mobile access won't work feels wrong).
thank you!

[liliakai]

This weekend I put together an emscripten-compiled curve25519 module including curve25519_donna and ed25519 sigs.

It works but it's a lot slower than the native client implementation, so for now I've kept native client checked in and made the crypto code use native client opportunistically (if supported by the browser) over the js implementation. Hopefully this is just a starting point and the asm js stuff can be further optimized.

To build locally: bower install && grunt build (assuming you have bower, grunt, and emscripten installed).