RSA-8192 is already too big. This avoids needing to worry about
bn_mul_mont allocating more than a page of stack memory, makes it a lot
more comfortable to just stack-allocate all Montgomery temporaries.
Also RSA operations scale quadratically or cubicly. For reference, on my
machine:
Did 1638 RSA 2048 signing operations in 1015740us (1612.6 ops/sec)
Did 82000 RSA 2048 verify (same key) operations in 1000238us (81980.5 ops/sec)
Did 70000 RSA 2048 verify (fresh key) operations in 1001850us (69870.7 ops/sec)
Did 13580 RSA 2048 private key parse operations in 1013849us (13394.5 ops/sec)
Did 611 RSA 3072 signing operations in 1038497us (588.4 ops/sec)
Did 39000 RSA 3072 verify (same key) operations in 1009250us (38642.6 ops/sec)
Did 34000 RSA 3072 verify (fresh key) operations in 1005116us (33826.9 ops/sec)
Did 7799 RSA 3072 private key parse operations in 1016058us (7675.7 ops/sec)
Did 276 RSA 4096 signing operations in 1008941us (273.6 ops/sec)
Did 23000 RSA 4096 verify (same key) operations in 1029290us (22345.5 ops/sec)
Did 20000 RSA 4096 verify (fresh key) operations in 1006214us (19876.5 ops/sec)
Did 5137 RSA 4096 private key parse operations in 1001233us (5130.7 ops/sec)
Did 39 RSA 8192 signing operations in 1012397us (38.5 ops/sec)
Did 6039 RSA 8192 verify (same key) operations in 1061168us (5690.9 ops/sec)
Did 5181 RSA 8192 verify (fresh key) operations in 1000616us (5177.8 ops/sec)
Did 1749 RSA 8192 private key parse operations in 1074560us (1627.6 ops/sec)
Did 6 RSA 16834 signing operations in 1147874us (5.2 ops/sec)
Did 1562 RSA 16834 verify (same key) operations in 1086732us (1437.3 ops/sec)
Did 1386 RSA 16834 verify (fresh key) operations in 1057798us (1310.3 ops/sec)
Did 440 RSA 16834 private key parse operations in 1039747us (423.2 ops/sec)
This change removes our exposure to the last of these. Also align limits
for legacy DSA and DH so that Montgomery reduction can rely on this.
Update-Note: This lowers our maximum key sizes:
- The maximum RSA modulus size is now 8,192 bits, down from 16,384 bits
- The maximum DSA p is now 8,192 bits, down from 10,000 bits
- The maximum DH p is now 8,192 bits, down from 10,000 bits
Fixed: 402677800
Change-Id: I52c0205af568b66a2fbc586b1c7300e13a47c7ab
Reviewed-on: https://boringssl-review.googlesource.com/c/boringssl/+/80287
Auto-Submit: David Benjamin <davidben@google.com>
Commit-Queue: David Benjamin <davidben@google.com>
Commit-Queue: Adam Langley <agl@google.com>
Reviewed-by: Adam Langley <agl@google.com>
David Benjamin
3fd8220e3c