Extremely slow RSA key generation on web

[tjcampanella]

I am unsure if I am doing it wrong or something, but on the web using the function below to generate a RSA key pair takes over a minute if it even finishes it freezes the entire UI during the process. I have tested and I know for a fact it is getting stuck at this function. I know I could be doing this in an isolate however, the way I am generating the keys now is when a new user signs up and then I am sending a request to the server with the public key. If anyone recommendations please let know. static AsymmetricKeyPair<PublicKey, PrivateKey> getRsaKeyPair( SecureRandom secureRandom) { var rsapars = RSAKeyGeneratorParameters(BigInt.from(65537), 4096, 5); var params = ParametersWithRandom(rsapars, secureRandom); var keyGenerator = RSAKeyGenerator(); keyGenerator.init(params); return keyGenerator.generateKeyPair(); }

[AKushWarrior]

Cc @mwcw: didn't you change JS random number generation? Maybe the issue is direct usage of the entropy source; we can probably seed Fortuna with the source instead and then pull from that, which should be faster.

[AKushWarrior]

@tjcampanella I would recommend investigating the isolate idea to work in the background, at least as a hotfix to avoid freezing UI. I have an idea for an internal fix (above), but I'm not sure how feasible it is.

[tjcampanella]

@AKushWarrior Thank you for the quick response, I appreciate you and the rest of the contributors on making a great package. I will see what I can do with an isolate.

[AKushWarrior]

@tjcampanella the issue might be in your code, actually. I noticed that you have SecureRandom secureRandom in your parameters; are you generating a new instance of SecureRandom each time you create a keypair? That would call the underlying Node.js seed generation more often than necessary.

Otherwise, I'll keep looking. It looks like rsa keygen isn't calling the seed method, so the only slowdown would be the seeding on construction of Fortuna (or, more concerning, that Fortuna itself is slow on web).

[tjcampanella]

@AKushWarrior This method is only called when a new user signs up. So it would normally just be getting called once per device, unless the user decides to make more than one account. And I am seeding it just doing that elsewhere and I know it gets past that part in a reasonable time. It gets stuck in this function.

[mwcw]

Hi,

Yes it takes ages.

void time4096() {
  var start = DateTime.now().microsecondsSinceEpoch;

  final rnd = SecureRandom('Fortuna');
    // ..seed(
    //     KeyParameter(Platform.instance.platformEntropySource().getBytes(32)));

  var keyGenerator = KeyGenerator('RSA')
    ..init(ParametersWithRandom(
        RSAKeyGeneratorParameters(BigInt.parse('65537'), 4096, 5), rnd));

keyGenerator.generateKeyPair();

  var end = DateTime.now().microsecondsSinceEpoch;

  print("KeyGen time "+ ((end - start)/1000).toString()+"ms");
}

Let me know how you go.

[tjcampanella]

@mwcw I haven’t tried the code yet, but don’t you need to call the generateKeyPair method? Otherwise it isn’t generating the pair right?

[mwcw]

@mwcw I haven’t tried the code yet, but don’t you need to call the generateKeyPair method? Otherwise it isn’t generating the pair right?

Sorry yes, that was an own goal.

Yes it does take a long time.

[tjcampanella]

@mwcw No worries. You just got me excited for a second there lol.

[mwcw]

Ok that took about 370 seconds.

A 2048 bit key is taking between 6 and 8 seconds.

I cannot offer you an solution off the top of my head, I'll need to take a solid look at it.

MW

[tjcampanella]

@mwcw Are you running on chrome in release mode or debug mode? Also I tried using 2048 earlier and it was still taking a while is there something noticeably different with the code I used?

[mwcw]

@mwcw Are you running on chrome in release mode or debug mode? Also I tried using 2048 earlier and it was still taking a while is there something noticeably different with the code I used?

I just hacked up one of the tests, running it using:

pub run test -p node test/key_generators/rsa_key_generator_test.dart

I just had a run at 28 seconds on node and 12 seconds on chrome.

Those times makes it impractical.

[tjcampanella]

Do you have any ideas about why there is such a difference in performance across mobile to web. On mobile it takes a couple seconds vs on web taking much longer. I am just wondering what are my options to run and use the library in the most performant way. Thanks for looking into this.

[EP-u-NW]

I'm also using 4096bit keys, but on android, not on web. I've isolated the workload, maybe you wan't to take a look: https://github.com/EPNW/flutter_identity_manager/blob/2d61457c409f791d1460610f272762a56bafa047/flutter_identity_manager_android/lib/src/rsa_key_pair.dart#L36-L57

Even on android, key generation takes about 5 seconds. I wonder if using an other random (like the on from dart directly, see #110) could speed things up?

[AKushWarrior]

I have a sneaking suspicion that random number generation is not the culprit here, because it wouldn't be much slower on web than native, and the issue would not be localized to RSA. The issue might be BigInt arithmetic; RSA key generation is one of the only algorithms that uses BigInt, so that would explain why the issue is so localized.

Would someone who has a testing setup mind profiling the keygen method to check where our bottleneck is?

[AKushWarrior]

Even on android, key generation takes about 5 seconds. I wonder if using an other random (like the on from dart directly, see #110) could speed things up?

The issue is that Dart's random (even Random.secure()) is non-specified and thus somewhat dangerous to rely on for cryptographic purposes. I think that the benefit probably outweighs this (relatively nitpicky) concern, but Fortuna is not significantly slower than Random.secure() anyways, so there wouldn't be a performance bottleneck there.

[EP-u-NW]

Even on android, key generation takes about 5 seconds. I wonder if using an other random (like the on from dart directly, see #110) could speed things up?

The issue is that Dart's random (even Random.secure()) is non-specified and thus somewhat dangerous to rely on for cryptographic purposes. I think that the benefit probably outweighs this (relatively nitpicky) concern, but Fortuna is not significantly slower than Random.secure() anyways, so there wouldn't be a performance bottleneck there.

Maybe you could copy that to #110 so we can do the dart Random discussion there and stopp abusing this issue 😄

[AKushWarrior]

Good point... :)

[tjcampanella]

@AKushWarrior @mwcw Have either of you thought about possible solutions to this? I am unsure how to handle the long times on the web. I don't want to have to use 2048 bit keys.

[mwcw]

@AKushWarrior @mwcw Have either of you thought about possible solutions to this? I am unsure how to handle the long times on the web. I don't want to have to use 2048 bit keys.

Generating 4096bit keys is a heavy operation that is usually done a lot closer to the machine than where js normally sits. As has been pointed out it is a 5 second generation time on Android and I know that implementation is a thin java wrapper that offloads some of the work to native code.

I was considering doing an experiment and reaching out to either crypto on nodejs, or the crypto web api that seems to be present in all modern browsers and offload the work to that but I am not going be able to get to that in the short term.

The only suggestion I can offer you right now is to generate the keys ahead of using them in the background or reach out the the underlying nodejs platform and generate the keys there but I suspect you will still need to generate the keys ahead of using them. Even on the JVM on a late model CPU it takes between 1 and 2 seconds to generate a 4096b RSA key pair.

MW

[AKushWarrior]

@mwcw if we're offloading work through interop, we should probably use WASM to get closer to native performance. I can investigate that.

[tjcampanella]

Generating them on mobile taking a few seconds I think is fine. The problem is on web taking minutes. I know there is another package called fast_rsa. I don’t believe you can seed their key generator though. Maybe you guys can find some insight from that package? I haven’t looked at their code or anything just the name saying fast_rsa is why I mention it. May be worth while I’m not sure. I appreciate both of you looking into this, I will have to do more research and figure out a solution. If I find anything of note I will mention it here.

[AKushWarrior]

Is fast_rsa... faster than pointycastle? On web?

I can take a look and do a rough diff of the code, but I don't want to waste my time chasing a red herring when that could be spent figuring out a JS interop solution.

[tjcampanella]

@AKushWarrior I don’t know if it is or not I just saw it and figured it would be worth mentioning. I haven’t done any comparisons as of now. I am just suggesting a potential lead. I will be looking into this issue more myself in the coming days.

[AKushWarrior]

@AKushWarrior I don’t know if it is or not I just saw it and figured it would be worth mentioning. I haven’t done any comparisons as of now. I am just suggesting a potential lead. I will be looking into this issue more myself in the coming days.

Yup, makes sense. If you do end up getting around to doing a comparison, let us know; it's possible that this is a bug in our particular implementation of RSA keygen, but it's hard to pinpoint it without a working example.

[tjcampanella]

@AKushWarrior The fast rsa web implementation seems to be running in web assembly directly. That is probably their claim to fame and why they used fast in their plugin title. I will do a comparison soon and show the results here.

[AKushWarrior]

@AKushWarrior The fast rsa web implementation seems to be running in web assembly directly. That is probably their claim to fame and why they used fast in their plugin title. I will do a comparison soon and show the results here.

That's essentially what I'm proposing above. WASM is way faster than anything else on web (JS or transpiled Dart, more or less the same thing).

[tjcampanella]

@AKushWarrior I tested their generation for a 4096 key and it still took about a minute on web. It seems like generating 4096 bit keys on the web isn't feasible. I may have to switch to using 2048 bit keys.

[AKushWarrior]

Well, it's FEASIBLE, as long as you wrap it in a model of concurrency; if you return to the isolate idea, that might be the best "solution". If the UI is completely dependent on the key, then yeah; 4096 bit RSA key generation is just too computationally intensive to work in that situation.

[tjcampanella]

Isolates on the web aren’t as easy as just calling the compute function on mobile. I will have to do some research on how to do it. Either way I am generating the keys at user sign up and I guess I can have it work in the background and then once they are ready allow the users to private message, but I didn’t wanna have to do that. I will have to figure something out.