JDK-8188046 : java.lang.Math.mutliplyHigh does not run in constant time
  • Type: Enhancement
  • Component: core-libs
  • Priority: P4
  • Status: Resolved
  • Resolution: Fixed
  • Submitted: 2017-09-27
  • Updated: 2021-07-08
  • Resolved: 2021-07-02
The Version table provides details related to the release that this issue/RFE will be addressed.

Unresolved : Release in which this issue/RFE will be addressed.
Resolved: Release in which this issue/RFE has been resolved.
Fixed : Release in which this issue/RFE has been fixed. The release containing this fix may be available for download as an Early Access Release or a General Availability Release.

To download the current JDK release, click here.
JDK 18
18 b05Fixed
Related Reports
Relates :  
Description
The pure Java implementation of mutliplyHigh looks like this:

    public static long multiplyHigh(long x, long y) {
        if (x < 0 || y < 0) {
            // Use technique from section 8-2 of Henry S. Warren, Jr.,
            // Hacker's Delight (2nd ed.) (Addison Wesley, 2013), 173-174.
        } else {
            // Use Karatsuba technique with two base 2^32 digits.
        }

This two-way branch gains very little in speed but potentially leaks information to a timing attack. What little the fast path gains from one fewer multiply it loses on the conditional branch: I've not been able to measure any significant difference in speed.
Comments
Changeset: cb795893 Author: Brian Burkhalter <bpb@openjdk.org> Date: 2021-07-02 18:21:39 +0000 URL: https://git.openjdk.java.net/jdk/commit/cb795893be8e6dcf725d8022aca16f657d3cc03c
02-07-2021

A sample run of the attached benchmark "MultiplyHighBranches" is as follows: Benchmark Mode Cnt Score Error Units MultiplyHighBranches.hacker thrpt 10 325975643.022 �� 14535505.786 ops/s MultiplyHighBranches.karatsuba thrpt 10 341633205.858 �� 14241361.938 ops/s MultiplyHighBranches.multiplyHigh thrpt 10 307711216.853 �� 12665076.024 ops/s It appears therefore that the fast path is up to about 5% faster when the algorithms are run in isolation but that advantage is more than offset by the cost of the conditional branch. Given that the fast path can only be run with positive parameters, it would be better to remove it and the branching. This should result in a small performance improvement.
01-07-2021