Re: RFR: 8273977: Reduce unnecessary BadPaddingExceptions in RSAPadding
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
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.to...@oracle.com](mailto:dalibor.to...@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-6404).
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
Re: RFR: 8273977: Reduce unnecessary BadPaddingExceptions in RSAPadding
On 11/3/2021 3:03 PM, Lari Hotari wrote:
On Mon, 20 Sep 2021 09:35:57 GMT, Lari Hotari 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.to...@oracle.com](mailto:dalibor.to...@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-6404). 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
Re: RFR: 8273977: Reduce unnecessary BadPaddingExceptions in RSAPadding
On Wed, 3 Nov 2021 21:56:10 GMT, Xue-Lei Andrew Fan wrote: >>> 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.to...@oracle.com](mailto:dalibor.to...@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-6404). >> 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.". > > @lhotari I think you have got the reason to create the BadPaddingExceptions. > Did you want to close this bug, or fix it alternativey without break the > constant-time purpose? @XueleiFan You are right. I'll follow up with a change which doesn't break the constant-time purpose. - PR: https://git.openjdk.java.net/jdk/pull/5581
Re: RFR: 8273977: Reduce unnecessary BadPaddingExceptions in RSAPadding
On Fri, 29 Oct 2021 06:07:26 GMT, Lari Hotari wrote: >> 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.to...@oracle.com](mailto:dalibor.to...@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-6404). > 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.". @lhotari I think you have got the reason to create the BadPaddingExceptions. Did you want to close this bug, or fix it alternativey without break the constant-time purpose? - PR: https://git.openjdk.java.net/jdk/pull/5581
Re: RFR: 8273977: Reduce unnecessary BadPaddingExceptions in RSAPadding
On Mon, 20 Sep 2021 09:35:57 GMT, Lari Hotari 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.to...@oracle.com](mailto:dalibor.to...@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-6404). 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
Re: RFR: 8273977: Reduce unnecessary BadPaddingExceptions in RSAPadding
On Mon, 20 Sep 2021 09:35:57 GMT, Lari Hotari 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.to...@oracle.com so that I can verify your account. - PR: https://git.openjdk.java.net/jdk/pull/5581
Re: RFR: 8273977: Reduce unnecessary BadPaddingExceptions in RSAPadding
On Mon, 20 Sep 2021 08:38:18 GMT, Lari Hotari 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. In Twitter, it was brought up to attention that "PKCS v1.5 is vulnerable to Bleichenbacher if the check is not constant-time, but there's no reason to leave it in the OAEP (second) function." , https://twitter.com/typish_cast/status/1439875435953786881 . For unpadV15 method one possible option to retain the "constant-time property of the code" would be to use a stackless exception (by overriding fillInStackTrace) that is an immutable / constant & singleton instance? That wouldn't cause a performance hit for 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. - PR: https://git.openjdk.java.net/jdk/pull/5581
Re: RFR: 8273977: Reduce unnecessary BadPaddingExceptions in RSAPadding
On Mon, 20 Sep 2021 08:43:24 GMT, Aleksey Shipilev wrote: > Submitted the bug for it, > [JDK-8273977](https://bugs.openjdk.java.net/browse/JDK-8273977). Please > change the PR title to "8273977: Reduce unnecessary BadPaddingExceptions in > RSAPadding" to get bots hooked properly. Thanks for submitting the bug @shipilev . I renamed the title accordingly. > Regarding the changes themselves, I think the key thing here is the method > comment: "Note that we want to make it a constant-time operation", which is > probably why this exception is always unconditionally created. Security folks > need to say for sure. +1 - PR: https://git.openjdk.java.net/jdk/pull/5581
Re: RFR: 8273977: Reduce unnecessary BadPaddingExceptions in RSAPadding
On Mon, 20 Sep 2021 08:38:18 GMT, Lari Hotari 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. Submitted the bug for it, [JDK-8273977](https://bugs.openjdk.java.net/browse/JDK-8273977). Please change the PR title to "8273977: Reduce unnecessary BadPaddingExceptions in RSAPadding" to get bots hooked properly. Regarding the changes themselves, I think the key thing here is the method comment: "Note that we want to make it a constant-time operation", which is probably why this exception is always unconditionally created. Security folks need to say for sure. - PR: https://git.openjdk.java.net/jdk/pull/5581
RFR: 8273977: Reduce unnecessary BadPaddingExceptions in RSAPadding
### 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. - Commit messages: - Reduce unnecessary BadPaddingExceptions that are created in success path Changes: https://git.openjdk.java.net/jdk/pull/5581/files Webrev: https://webrevs.openjdk.java.net/?repo=jdk=5581=00 Issue: https://bugs.openjdk.java.net/browse/JDK-8273977 Stats: 6 lines in 1 file changed: 0 ins; 4 del; 2 mod Patch: https://git.openjdk.java.net/jdk/pull/5581.diff Fetch: git fetch https://git.openjdk.java.net/jdk pull/5581/head:pull/5581 PR: https://git.openjdk.java.net/jdk/pull/5581
