RFR: 8273977: Reduce unnecessary BadPaddingExceptions in RSAPadding

[Michael StJohns]

On 11/3/2021 3:03 PM, Lari Hotari wrote:
> On Mon, 20 Sep 2021 09:35:57 GMT, Lari Hotari <duke at openjdk.java.net> wrote:
>
>>> ### Motivation
>>>
>>> When profiling an application that uses JWT token authentication, it was noticed that a high number of `javax.crypto.BadPaddingException`s were created. When investigating the code in RSAPadding, one can see that BadPaddingException is created in all cases, also on the success path:
>>> https://github.com/openjdk/jdk/blob/dc7f452acbe3afa5aa6e31d316bd5e669c86d6f6/src/java.base/share/classes/sun/security/rsa/RSAPadding.java#L369-L375
>>>
>>> ### Modifications
>>>
>>> Inline the unnecessary local variable to prevent creating the exception on the success path.
>> For anyone interested, there's an explanation of the [Bleichenbacher's CCA attack on PKCS#1 v1.5 on Stackexchange](https://crypto.stackexchange.com/questions/12688/can-you-explain-bleichenbachers-cca-attack-on-pkcs1-v1-5). The original paper is ["Chosen Ciphertext Attacks Against Protocols Based on the RSA Encryption Standard PKCS #1" ](http://archiv.infsec.ethz.ch/education/fs08/secsem/bleichenbacher98.pdf).
>>
>> The reason for constant time is to not leak information about a possible bad padding to the attacker based on the difference in response time between a valid and bad padding. The attacker can use this information to narrow the search to find the pre-master secret.
>> Hi @lhotari, please submit an OCA at https://oca.opensource.oracle.com/ if you are contributing on your own behalf. If you are contributing on your employers behalf, please send me an e-Mail at [dalibor.topic at oracle.com](mailto:dalibor.topic at oracle.com) so that I can verify your account.
> @robilad This is a contribution on my own behalf. I have signed [OCA in 2014 while contributing to Btrace](https://github.com/btraceio/btrace/pull/101#issuecomment-63333404). Is that sufficient? I cannot sign OCA again online, it gives me an error message "The provided GitHub username lhotari does already appear in an existing OCA, please use another one.".
>
> -------------
>
> PR: https://git.openjdk.java.net/jdk/pull/5581

Hi -

If you're trying for constant time, you might be defeated by the "if" at 
line 460 and the blank line ("// continue;") at 462.   As well as the if 
clause at 450.

Maybe:

int zeroCount = 0;
  int msgZeroCount = 0;

  int mlenCount = 0;
  int msgOne = 0;

  int oneFlag = 0;

  int bpcount = -1;

  boolean logicNotBp = false;

  // substitute for 450-451
  if (lHash[i] != EM[dbStart + i]) {
    bp = true;
  } else {
    logicNotBp = true;
  }

// add at line 454

  if (logicNotBp) {
    bpcount = 0;
  }

  if (bp) {
    bpcount= 1;
  }

The above is a bit convoluted, but makes sure you have the same number 
and type of operations regardless of whether or not there is a match at 
any given position. bpcount will be set to 1 if any of the bytes don't 
match.  This shouldn't be optimized out


  // substitute for 458-469

  for (int i = padStart; i < EM.length; i++) {
    int value = EM[i];
    if (oneFlag != 0) {
      switch (value) {
         case 0x00:
           zeroCount++;
           break;
         case 0x01:
           oneFlag++;
           break;
         default:
           bpcount++;
       }

    } else {
      switch (value) {
        case 0x00:
          msgZeroCount++;
          break;
        case 0x01:
          msgOne++;
          break;
        default:
          mlenCount++;
      }
    }
  }



  bp = (bpcount >= 1);
  mlenCount = otherZeroCount + dupOne + mlenCount;

This allows you to add an additional check for consistency - mlenCount + 
zeroCount + 1 should equal EM.length - padStart. Checking those will 
prevent the optimizer from optimizing out the code above.

I used switch instead of if/else/else because its usually closer to 
constant time and each of the branches are increments.

FYI - I do have a signed contributor agreement from oracle days, but 
lack time to do this against a build environment.

Mike