RFR: 8273977: Reduce unnecessary BadPaddingExceptions in RSAPadding

[Michael StJohns]

On 11/4/2021 9:13 PM, Michael StJohns wrote:
> 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) {
if (oneFlag == 0) {  // sorry about that.
> 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
>
>