Faster Poly1305 block processing

[winne42]

Performance of Poly1305 can be improved by ~30..50% changing only Poly1305.update().

The solution is a little bit more complex code-wise than #2476. May still be worth pursuing - I will provide it as a draft PR for discussion/as a starting point.

Who benefits

• BC TLS (bctls) with ChaCha20-Poly1305 suites. This is the most important one, for both crypto back ends:
  • BcChaCha20Poly1305 (lightweight) encrypts the whole record, then MACs the full ciphertext in one call.
  • JceChaCha20Poly1305 does the same through Mac.getInstance("Poly1305"), which comes from the BC provider.
  • So each record gets the measured ~1.5× on its MAC part. With today's scalar ChaCha that is roughly 10% off a 16 KB record; with Faster Salsa20Engine #2476 as well, both halves get faster.
• Direct MAC users:
  • the lightweight Poly1305 and Poly1305 built on a block cipher;
  • the provider's Mac POLY1305 and POLY1305-<cipher> (AES, ARIA, Camellia, CAST6, LEA, Noekeon, RC6, SEED, SM4, Serpent, Twofish). The JCA passes the caller's chunks straight through.
  • The gain is 1.3–1.5× for chunks of 1 KB and up, and close to nothing at 64 bytes.
• OpenSSHPrivateKeyUtil (OpenSSH keys encrypted with chacha20-poly1305@openssh.com) technically takes the new path, but the blob is a few hundred bytes, so the effect is negligible.

Who doesn't benefit (yet)

• ChaCha20Poly1305 and XChaCha20Poly1305 feed the MAC 64 bytes per call, and no change was measured (81.3 → 80.3 µs at 16 KB). Everything built on them inherits this:
  • the provider's Cipher ChaCha20-Poly1305 and XChaCha20-Poly1305;
  • HPKE with aead_CHACHA20_POLY1305;
  • MLS's ChaCha20-Poly1305 suites (BcMlsAead).
  • The one exception is associated data, which these modes pass to the MAC in one piece; it is usually small.
• Short messages and byte-at-a-time callers of update(byte).

To reach the AEAD users, ChaCha20Poly1305's data paths need batching - I will provide this as a separate draft PR. With that batching, the new Poly1305 made 16 KB encryptions about 14% faster even with the original ChaCha (i.e., before #2476).

Finding

Poly1305.update copied every 16-byte block into its currentBlock buffer with System.arraycopy. It then called processBlock() once per block, which read the block back out of the buffer and loaded and stored the accumulator (h0 - h4) and the key limbs from fields each time. The arithmetic itself, 26-bit limbs and 25 32x32->64 products per block, is the usual portable form and was fine.

Fix

• When update is at a block boundary and has more than one block left, it absorbs all but the last block straight from the input. One loop, processBlocks, keeps the accumulator and key in local variables and writes the accumulator back once at the end.
• The last 1 - 16 bytes go to the buffer as before. So the instance ends up in exactly the state the old code left, with the same accumulator and buffer, not merely an equivalent one.
• processBlock (buffered blocks and the padded final block) now calls the same loop for one block, passing the 2^128 bit (hibit) only for a full block. The block arithmetic exists once, as before.

The commit also adds a release note under 1.87 "Additional Features and Functionality". Nothing outside Poly1305.java changed.

Verification

• The core crypto.test suite (org.bouncycastle.crypto.test.AllTests) passes against the built jar, including Poly1305Test, ChaCha20Poly1305Test and XChaCha20Poly1305Test.
• Old and new classes side by side, with main's Poly1305 compiled under another name. Two seeds of 3,000 random instances produced about 5,300 tags and 16,000 updates (40 MB) per seed, with identical tags:
  • plain and AES-based Poly1305;
  • random keys, all-0xff keys and messages;
  • messages up to 40 KB, fed whole, in pieces of 0 - 3,000 bytes, in whole blocks, and as single bytes;
  • reset part way through, and tags at different output offsets.
• Verified to catch a defect: dropping the 2^128 bit for directly absorbed blocks fails the harness at once.
• Checkstyle passes.

Benchmark

JMH average time, old (main) and new implementation in the same run: 2 forks x 5 x 1 s after 5 x 1 s warm-up. A MAC with a fresh one-time key per message (init, update, doFinal), as ChaCha20-Poly1305 uses it. AMD Ryzen 9 5900HX (AVX2), OpenJDK 25.0.4, Linux. The 1-minute load was 1.5 - 2.5; one core was held throughout by a runaway wireplumber (the desktop's audio service, 100% CPU), and no other benchmark ran.

Size	Before	After	Speed-up
64 B	115 ns	111 ns	1.04x
1 KB	1,365 ns	913 ns	1.49x
16 KB	21,132 ns (775 MB/s)	13,714 ns (1.19 GB/s)	1.54x

At 64 bytes, 4 blocks, setting up the one-time key and the final reduction outweigh the block processing.

On the older JDKs, from a shorter run (1 fork x 5 x 1 s after 3 x 1 s warm-up, the same machine):

JDK	Size	Before	After	Speed-up
17.0.20	1 KB	1,375 ns	954 ns	1.44x
17.0.20	16 KB	20,953 ns	14,272 ns	1.47x
21.0.12	1 KB	1,340 ns	1,019 ns	1.31x
21.0.12	16 KB	20,982 ns	15,245 ns	1.38x

Not yet inside ChaCha20-Poly1305

main's ChaCha20Poly1305 interleaves the cipher and the MAC 64 bytes at a time. Poly1305 therefore only ever sees 3-block runs, and the gain disappears in the AEAD: 16 KB encryption took 81,301 ns before and 80,288 ns after (1 KB: 5,632 and 5,629 ns). The gain comes from the long loop, not from the saved copies.

There already exists a local branch on the developer's PC that batches those data paths: encryption runs the cipher over every whole block of a call, then the MAC over the result. I measured a renamed copy of that ChaCha20Poly1305 against this branch (same output as main's on 2,000 random encryptions; same JMH settings):

Size	Batched AEAD, old Poly1305	Batched AEAD, new Poly1305	Speed-up
1 KB	5,541 ns	5,103 ns	1.09x
16 KB	84,325 ns	73,929 ns	1.14x

That is with main's slow scalar ChaCha still taking most of the time. With #2476 as well, ChaCha20-Poly1305 would gain from both (not measured together). Porting the batching to main would be a another, separate change.

Notes

• A faster scalar Poly1305 needs bigger limbs: 44-bit limbs, three per accumulator, with 64x64->128 products. Java only has those through Math.multiplyHigh (Java 9+), which the base tree cannot use (Java 1.4 source floor), so it would mean a version overlay. It is not an easy gain.