-
Notifications
You must be signed in to change notification settings - Fork 990
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
bn.powermod is painfully slow #172
Comments
Apparently, it's the whole Big Number implementation of SJCL that's painfully slow. Here's a JSPerf: http://jsperf.com/jsbnvsleemonvssjclbiginteger/5 |
Can I ask what your use-case is...? If you're using browser-based crypto, the connection should be over TLS. However, if don't want the user's password to be on or sent to the server at all ever, you could hash their password before it's sent. Hashing is certainly fast. |
Thank you for your interest. Anyway, whatever the use case is, I believe SJCL needs to improve a lot on the Big Integer side. We altered the test code above to use JSBN to do the powermod function (and only for that), and the whole system is now really smooth (feels like instantaneous). This is compared with SJCL that took approximately 5-7s. |
What I've done before is, when a client is encrypting data for themselves that they just want the server to store, they provide a hash of their password as authentication and use their raw password as the key for sjcl.encrypt. If you consider a hash a random oracle, then the server learns nothing about the user's password. Would that work instead? |
Yes, that is more or less what I described above (maybe with too many words :) ), with some changes. Before sending the password, the client hashes it with SHA-256. The notes are:
Indeed, I suppose this is what we are going to do, given that SRP is not implementable with SJCL (and bundling another big integer library would be an overkill). However, aside from what we are going to do, I still feel that SJCL needs to improve its BN component. Competitors are doing much better, and I'm sure there's plenty of room for improvement. |
Actually only powermod is really slow. |
Glad you noticed my jsperf test showing only powermod was the problem @Nilos :) |
As far as I remember sjcl's biginteger library was optimised for elliptic curve operations and as such is slow for powermod. |
Nilos, eventually we had to use a different library for SRP. I'm afraid SRP will not be usable with SJCL until the speed of powermod is increased by a big factor. I'm not being overly dramatic: powermod was crashing Chrome. |
@EgoAleSum What library did you use in the end? |
JSBN for this part only |
@EgoAleSum Does pull request #208 give you times on par with what you're looking for? |
@Bren2010 The new code is ~30x faster but it still doesn't seem to be on par with the others (~6.5x slower) |
Thank you @heavensrevenge for the JSPerf! @Bren2010 the patch is terrific and the speed improvement is incredible. It's still far behind but seems a bit more usable now. |
@EgoAleSum @heavensrevenge @EgoAleSum I did some cleaning and implemented sliding window exponentiation. It's still not as fast as JSBN, but it's better than it was before. (I think it's as fast as I can get it at the moment.) Thank you both!! |
not bad @Bren2010, your latest changes double the speed of the original code. |
Confirm that. From 0.58 ops/s on my laptop to ~25 ops/second. Still lags behind JSBN (135), but it's already 2 times or so Laemon Baird. It's certainly usable now! Great work @Bren2010 , and it's improved even more! |
👍 nice work |
@Bren2010 maybe you can take some ideas from https://github.com/vibornoff/asmcrypto.js/blob/release/src/bignum/modulus.js it's blazing fast when it comes to computation http://jsperf.com/jsbn-powermod/3 and http://jsperf.com/jsbn-vs-bigint-js-modular-exponentiation-montgomery/4 |
This is an old thread, but I wanted to chime in because I recently had to implement a system similar to the one described by @Bren2010 and @EgoAleSum, where the same password is used for both authentication and client-side encryption via While they are both right that hashing only client-side would effectively make the system equivalent to one that stores passwords in the clear, the solution they propose (hashing the password and sending that to the server) ignores the reason why we use key derivation functions like PBKDF2 instead of simple hashes. On modern hardware, it is not uncommon to be able to perform millions or even billions of hashes per second, so using the SHA-256 of the password for authentication is not much different in terms of security that using the raw password. The service provider could easily break plenty of passwords and access the encrypted payloads. The point of key derivation functions is that they are slow, and they must be because the password space is usually quite reduced, compared to hashing whole documents for example. The proper solution is to also perform key derivation client-side on the authentication password (obviously with a different salt than the one used in the |
@federicobond this issue was originally opened because we were trying to implement a system based on SRP for authentication, which completely removes the need to send the password to the server: http://srp.stanford.edu/ndss.html |
Yes, I agree that SRP is probably a better solution. I left the comment to warn people of the pitfall I mentioned when implementing systems which share authentication and encryption passwords. |
From my point of view the most desirable system is one that combines SRP and a "key" derivation function because even though an SRP system does not store password equivalent data, one can still perform a brute force attack with reasonable speed on the data, whereas every "key" derivation function has a hardening factor, and one guess on a derivation function takes a long (parameterized) time compared to one guess against an SRP based system. Combining SRP and derivation should be easy just do (pseudocode!): |
Still a fast bn.powermod would be desirable! |
@Nilos not just desirable, but if you consider the results from my test above (crashing a browser) is necessary. Otherwise SRP simply can't be done |
@EgoAleSum I am always happy to merge a PR :) |
We are implementing a full SRP system for browser-based authentication.
On the server side, we are using "mozilla/node-srp", which uses "justmoon/node-bignum" for dealing with big integers. Speed is excellent, but that is not surprising given that node-bignum uses native code.
On the client side, however, we wanted to use SJCL, as we are already using this library for other tasks in the same project.
Turns out that SJCL has already some methods implemented for SRP, and we were writing the missing ones.
In particular, we had problems with calculating
A = g^a
. This is the code:The call to
powermod
above takes ~7s on Chrome 34, on OSX Mavericks on a 2010 MacBook Air, 2GHz Core i7. In certain cases, the web page inside Chrome crashes, forcing me to reload it.On Safari, same machine, the browser hangs completely.
Changing the group from 2048 to 1024 improves the situation very slightly (~5s), but not enough.
Is there anything that could be done to improve performances of the big integer part of SJCL?
The text was updated successfully, but these errors were encountered: