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.

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?