Agreed, unwrapKey is inherently flawed with RSAES.

In an ideal world, it would be possible to use the encrypt/decrypt primitives in a manner similar to that described in RFC 5246, Section 7.4.7.1. However, as currently specified, a padding error is distinguishable from success by virtue of the promise being rejected versus an ArrayBuffer being allocated. This provides a timing bias that could be used to exploit an implementation.

We "could" potentially mitigate this by having RSAES explicitly take a length of the expected data size as an input. The UA would then generate & allocate a random ArrayBuffer of that length, R, prior to performing the operation. It would then perform the RSAES operation, check the padding, and check the size. If any of these failed, it would use R as the ArrayBuffer return, otherwise, it would use the decrypted data.

This would allow a construct like those described, but will force key data to be exposed to JS. Of course, something like that described in 7.4.7.1 inherently requires the PMS be exposed to JS (unless a TLS-specific PreMasterSecret alg is implemented), due to the need to inject the ClientHello.client_version into the first two octets.

The alternative is of course one that will make some happy - remove RSAES entirely - but I'm curious if there is a way to permit the 'safe [albeit dangerous]' use.

The changes needed to make this safe would make the API even more cryptic to devs than it already is.  I would prefer to just drop RSAES-PKCS1-v1_5 from unwrapKey.

As the API is now, any algorithm that supports encrypt/decrypt can be used for wrap/unwrap. If we want to prevent unwrapping with RSAES, we would have to either make an exception or remove RSAES decrypt all together in which case we may as well remove RSAES entirely. Either way, decrypt on its own is still a potential oracle.


Thinking out loud: I'm not a fan of complicating things in general, but if RSAES simply must be included, then making it more complicated for devs might at least be a disincentive to use it.

Regarding the attack in the title of this bug, is it not a general issue that where several primitive operations are concatenated it is a problem if the error codes indicate at which stage the combined operation failed ?

Or, is it the case that RSAES with unwrap is the one example where there is a known attack (due to the particular weakness of RSAES padding) which can exploit this knowledge of which stage failed ?

Wouldn't it be prudent to eliminate the distinction and just return a single error code in the case of any operation that can fail in multiple distinct ways ?

Regarding the timing attack mentioned by Ryan, it seems it is a general quality-of-implementation issue to mitigate such attacks with constant-time implementations. And it seems to me this could apply to many other operations, although it may be the case - as above - that RSA-ES may be the one example where there is a well-known attack.

(In reply to Mark Watson from comment #4)
> Regarding the attack in the title of this bug, is it not a general issue
> that where several primitive operations are concatenated it is a problem if
> the error codes indicate at which stage the combined operation failed ?

No.

A "secure" algorithm will be independent of how these errors are reported.

An "insecure" algorithm - such as RSA-ES or, for that matter, RSA-OAEP - WILL be particularly sensitive.

> 
> Or, is it the case that RSAES with unwrap is the one example where there is
> a known attack (due to the particular weakness of RSAES padding) which can
> exploit this knowledge of which stage failed ?

So, any RSAES decryption is at risk. As I explained in comment #1, any combination - whether it be simply 'encrypt' or 'unwrap' - will fail if there is any structure to the key OR if any internal state leaks.

> 
> Wouldn't it be prudent to eliminate the distinction and just return a single
> error code in the case of any operation that can fail in multiple distinct
> ways ?

Not in any meaningful way that will improve security, no.

> 
> Regarding the timing attack mentioned by Ryan, it seems it is a general
> quality-of-implementation issue to mitigate such attacks with constant-time
> implementations. And it seems to me this could apply to many other
> operations, although it may be the case - as above - that RSA-ES may be the
> one example where there is a well-known attack.

No, it's not a "quality of implementation" issue - it's a fundamental API design.

The API, as written, *cannot* provide a safe decrypt or unwrap operation. The mitigation for this - such as that employed by TLS - involves additional behaviours that would fundamentally alter the nature of the API.

That is, we would make it such that RSAES needs to know the key length, cannot unwrap keys with structure (ergo, it's only suitable for symmetric keys), has to ALWAYS succeed (returning a random key), and then, and even then, it's *still* possible for security to be botched (eg: in the case of XML DSig & friends, the failure to decrypt using the unwrapped key is itself a signal that the key unwrap failed).

Compare this with AES-KW or RSA-KEM, in which revealing success or not does not provide an oracle. RSA-OAEP still provides an oracle (Manger's attack), but that CAN be mitigated by a quality of implementation (of which most libraries - including Botan, Crypto++, and OpenSSL, do NOT have quality implementations) such that the success/failure is not an oracle.

Considering that at this point, any hope of allowing a 'safe' implementation would require a breaking API change to accomodate RSA-ES, I think it's reasonable to remove entirely. This is, however, why it was included in the list of algorithms to begin with - to explore all algorithms and their interaction with the API, and to ensure that the API would "fit". It's clear that the API we have does not "fit", and I am not convinced we can reasonably "break" the API such that it would. It's also clear, from this bug and mailing list discussion, that no one would be upset if it was removed.

+1 to remove

So, first, considering the issue actually in the subject line of this bug, if we change the specification so that padding errors and parse errors do not return distinct codes, then I believe the padding oracle attack of [B98] and variants is rendered infeasible for keys that have usage 'unwrap' and not 'decrypt' and where the wrapped key format has some structure: the chosen ciphertexts in the attack would not only need to result in correctly padded plaintext, but syntactically valid payloads. The chance of this for any given chosen ciphertext seems little better than random, rendering the attack infeasible.

Second, for the *separate* issue of the same attack using the decrypt method as the oracle, it does indeed seem convoluted to modify the API so that information is not leaked about the correctness or not of the padding. However, to practically exploit this, the attacker needs either to be able to run arbitrary code on the origin of the key, or to modify messages and observe the results (and for the distinction between success and padding errors to be exposed in those results).

For the first case of an attacker able to run arbitrary code on the origin of the key, it would seem much simpler for that attacker to simply replace the global webcrypto object with their own polyfill, giving them access to the RSA key itself at the time it is generated / imported / unwrapped. The exception is the case where the RSA key, or a non-extractable key used to unwrap it, is generated / imported / unwrapped at an earlier time at which the attacker is not present. An effective mitigation then, would be to always use the RSA key immediately, to unwrap a symmetric key, for example, and then discard the RSA one.

Finally, for the second case of an attacker able to modify and observe messages but unable to insert arbitrary code onto the client, it would be sufficient for the JS application to avoid exposing a distinction between the success and failure cases, for example as per the TLS approach Ryan cited.

I don't want to underplay the significance of the weaknesses with this padding scheme or suggest for a moment that one shouldn't always use RSA-OAEP instead if that is available. But it seems that support for RSA-OAEP is not going to be universal in browsers, at least initially.

I'd suggest that we fix this for the unwrap case as suggested above. For the decrypt case, the existence of the oracle attack seems to make things no worse with respect to an attacker able to run arbitrary code, provided RSA keys are not persisted, and can be mitigated through protocol design for an attacker able to modify messages but not run arbitrary JS on the origin. 

[B98] D. Bleichenbacher. Chosen ciphertext attacks against protocols based on the RSA encryption standard. In Advances in Cryptology: Proceedings of CRYPTO’98, volume 1462 of LNCS, pages 1–12, 1998.

(In reply to Mark Watson from comment #7)
> So, first, considering the issue actually in the subject line of this bug,
> if we change the specification so that padding errors and parse errors do
> not return distinct codes, then I believe the padding oracle attack of [B98]
> and variants is rendered infeasible for keys that have usage 'unwrap' and
> not 'decrypt' and where the wrapped key format has some structure: the
> chosen ciphertexts in the attack would not only need to result in correctly
> padded plaintext, but syntactically valid payloads. The chance of this for
> any given chosen ciphertext seems little better than random, rendering the
> attack infeasible.

Mark,

That's not a correct security analysis of B98. Structured results reveal even *more* details about the nature of the failure. You have to permeate the constant-timedness of the operations throughout the entire algorithm in order to mitigate, as any short-circuits reveal whether or not it was well-formed.

> 
> Second, for the *separate* issue of the same attack using the decrypt method
> as the oracle, it does indeed seem convoluted to modify the API so that
> information is not leaked about the correctness or not of the padding.
> However, to practically exploit this, the attacker needs either to be able
> to run arbitrary code on the origin of the key, or to modify messages and
> observe the results (and for the distinction between success and padding
> errors to be exposed in those results).

The distinction needs only be sufficient between "success" and "failure", and timing provides a clear source of this.

> 
> For the first case of an attacker able to run arbitrary code on the origin
> of the key, it would seem much simpler for that attacker to simply replace
> the global webcrypto object with their own polyfill, giving them access to
> the RSA key itself at the time it is generated / imported / unwrapped. The
> exception is the case where the RSA key, or a non-extractable key used to
> unwrap it, is generated / imported / unwrapped at an earlier time at which
> the attacker is not present. An effective mitigation then, would be to
> always use the RSA key immediately, to unwrap a symmetric key, for example,
> and then discard the RSA one.

This sort of advice is even more prone to failure than the proposed modifications to the unwrap/decrypt case.

> 
> Finally, for the second case of an attacker able to modify and observe
> messages but unable to insert arbitrary code onto the client, it would be
> sufficient for the JS application to avoid exposing a distinction between
> the success and failure cases, for example as per the TLS approach Ryan
> cited.

Timing is sufficient to expose this. Considering that different scripts running in different origin have access to high resolution timers, I do not feel comfortable at all saying that this is a non-issue if you "just use TLS" (or related)

> 
> I don't want to underplay the significance of the weaknesses with this
> padding scheme or suggest for a moment that one shouldn't always use
> RSA-OAEP instead if that is available. But it seems that support for
> RSA-OAEP is not going to be universal in browsers, at least initially.

That seems a premature conclusion.

It's true that support for *anything* is not going to be universal.

I have zero concerns with removing RSA-ES, and there seems sufficient consensus to do so.

> 
> I'd suggest that we fix this for the unwrap case as suggested above. For the
> decrypt case, the existence of the oracle attack seems to make things no
> worse with respect to an attacker able to run arbitrary code, provided RSA
> keys are not persisted, and can be mitigated through protocol design for an
> attacker able to modify messages but not run arbitrary JS on the origin. 
> 
> [B98] D. Bleichenbacher. Chosen ciphertext attacks against protocols based
> on the RSA encryption standard. In Advances in Cryptology: Proceedings of
> CRYPTO’98, volume 1462 of LNCS, pages 1–12, 1998.

This is, perhaps, the worst of all the options.

I do not support RSA-ES without further modifications to provide meaningfully robust defense - changes that fundamentally alter the API and it's reporting.

If you look at http://www.nds.rub.de/media/nds/veroeffentlichungen/2012/07/11/XMLencBleichenbacher.pdf , you can see a more practical application of the attack to the API exposed. This has previously been discussed on-list.

First, one general comment - I was mistaken in my earlier message in giving consideration at all to the case where an attacker can directly access the WebCrypto API in the origin in question. In all such cases, the attacker can, of course, simply decrypt arbitrary messages directly, using the API.

The oracle attack is of importance when considering an attacker who can insert protocol messages and observe responses. But in this case the application Javascript has control of what is or is not revealed in such messages and can take care to follow approaches such as the TLS approach you cite.

(In reply to Ryan Sleevi from comment #8)
> (In reply to Mark Watson from comment #7)
> > So, first, considering the issue actually in the subject line of this bug,
> > if we change the specification so that padding errors and parse errors do
> > not return distinct codes, then I believe the padding oracle attack of [B98]
> > and variants is rendered infeasible for keys that have usage 'unwrap' and
> > not 'decrypt' and where the wrapped key format has some structure: the
> > chosen ciphertexts in the attack would not only need to result in correctly
> > padded plaintext, but syntactically valid payloads. The chance of this for
> > any given chosen ciphertext seems little better than random, rendering the
> > attack infeasible.
> 
> Mark,
> 
> That's not a correct security analysis of B98. Structured results reveal
> even *more* details about the nature of the failure. You have to permeate
> the constant-timedness of the operations throughout the entire algorithm in
> order to mitigate, as any short-circuits reveal whether or not it was
> well-formed.

I'd be happy to be proven wrong, but I don't think what you say above is the whole story. The attack is based on the fact that the oracle reveals, when the padding check succeeds, that a chosen multiple of the plaintext lies within a known, simple, subset of the set of all possible plaintexts: specifically the subset with valid PKCS#1 padding. This is (roughly) 2^16 smaller than the set of all plaintexts, because the first two bytes are 0x00 and 0x02. If the oracle returns an error, little or nothing useful is revealed about the plaintext.

Now, it is clear that if the oracle instead reveals that a chosen multiple of the plaintext is both PKCS conforming *and* encodes a valid JWK or ASN.1 structure then this success result reveals much more information about the plaintext. The set of possible plaintext values with both properties is much smaller.

However, multipliers with this property are much much harder to find. The _average_ amount of information revealed with each trip to the oracle is, I expect, much less, since most of the time you get a failure. I admit I don't have a proof of this, though. Do you have a proof of, or evidence for, the converse ?

Furthermore, it's not clear that the additional restriction of the possible plaintext set admits a practical exploitation except for the obvious one that the plaintext is a multiple of 125 (in the JWK case). It seems to me that a practical attack based on this would be something worthy of publication, not something we should assume / expect to exist.

Regarding timing attacks, I think some evidence is required to suggest that this might be feasible based on the RSA-ES WebCrypto primitive alone. Of course it is possible to design protocols that expose timing attacks as in the XML security case, where the attacker can force the victim to decrypt 1MB of data in the success case and none on the failure case. 

> 
> > 
> > Second, for the *separate* issue of the same attack using the decrypt method
> > as the oracle, it does indeed seem convoluted to modify the API so that
> > information is not leaked about the correctness or not of the padding.
> > However, to practically exploit this, the attacker needs either to be able
> > to run arbitrary code on the origin of the key, or to modify messages and
> > observe the results (and for the distinction between success and padding
> > errors to be exposed in those results).
> 
> The distinction needs only be sufficient between "success" and "failure",

True - it is the success case that carries the exploitable information.

> and timing provides a clear source of this.

It's not clear that can't be mitigated for an attacker modifying / observing a network protocol.

> 
> > 
> > For the first case of an attacker able to run arbitrary code on the origin
> > of the key, it would seem much simpler for that attacker to simply replace
> > the global webcrypto object with their own polyfill, giving them access to
> > the RSA key itself at the time it is generated / imported / unwrapped. The
> > exception is the case where the RSA key, or a non-extractable key used to
> > unwrap it, is generated / imported / unwrapped at an earlier time at which
> > the attacker is not present. An effective mitigation then, would be to
> > always use the RSA key immediately, to unwrap a symmetric key, for example,
> > and then discard the RSA one.
> 
> This sort of advice is even more prone to failure than the proposed
> modifications to the unwrap/decrypt case.

This is irrelevant anyway given my opening comment above.

> 
> > 
> > Finally, for the second case of an attacker able to modify and observe
> > messages but unable to insert arbitrary code onto the client, it would be
> > sufficient for the JS application to avoid exposing a distinction between
> > the success and failure cases, for example as per the TLS approach Ryan
> > cited.
> 
> Timing is sufficient to expose this. Considering that different scripts
> running in different origin have access to high resolution timers, I do not
> feel comfortable at all saying that this is a non-issue if you "just use
> TLS" (or related)

Well, I didn't say "just use TLS". And we are talking about a network-based attack. Client-side high resolution timers are relevant only if the application under attack exposes its messaging protocol locally to other origins (over postMessage or I guess some convoluted WebSockets thing over localhost).

> 
> > 
> > I don't want to underplay the significance of the weaknesses with this
> > padding scheme or suggest for a moment that one shouldn't always use
> > RSA-OAEP instead if that is available. But it seems that support for
> > RSA-OAEP is not going to be universal in browsers, at least initially.
> 
> That seems a premature conclusion.

Ok, good. If RSA-OAEP is universally supported then I'm not so concerned about whether RSA-ES is included or not.

> 
> It's true that support for *anything* is not going to be universal.
> 
> I have zero concerns with removing RSA-ES, and there seems sufficient
> consensus to do so.

You don't have consensus at this stage.

> 
> > 
> > I'd suggest that we fix this for the unwrap case as suggested above. For the
> > decrypt case, the existence of the oracle attack seems to make things no
> > worse with respect to an attacker able to run arbitrary code, provided RSA
> > keys are not persisted, and can be mitigated through protocol design for an
> > attacker able to modify messages but not run arbitrary JS on the origin. 
> > 
> > [B98] D. Bleichenbacher. Chosen ciphertext attacks against protocols based
> > on the RSA encryption standard. In Advances in Cryptology: Proceedings of
> > CRYPTO’98, volume 1462 of LNCS, pages 1–12, 1998.
> 
> This is, perhaps, the worst of all the options.
> 
> I do not support RSA-ES without further modifications to provide
> meaningfully robust defense - changes that fundamentally alter the API and
> it's reporting.
> 
> If you look at
> http://www.nds.rub.de/media/nds/veroeffentlichungen/2012/07/11/
> XMLencBleichenbacher.pdf , you can see a more practical application of the
> attack to the API exposed. This has previously been discussed on-list.

That paper describes attacks that are based on more than just the weakness in RSA-ES. Other aspects of the XML security design are essential to the attacks.

What this proves is that it's possible for smart people to invent broken protocols with RSA-ES. That's not in dispute.

What I'm arguing against is the conjecture that it is so hard to design protocols with any practical application that we should not provide the primitive at all.

(In reply to Mark Watson from comment #9)
> First, one general comment - I was mistaken in my earlier message in giving
> consideration at all to the case where an attacker can directly access the
> WebCrypto API in the origin in question. In all such cases, the attacker
> can, of course, simply decrypt arbitrary messages directly, using the API.

No, of course they can't - if the RSA-ES key is only permitted for unwrap, and the wrapped key has structure.

> 
> The oracle attack is of importance when considering an attacker who can
> insert protocol messages and observe responses. But in this case the
> application Javascript has control of what is or is not revealed in such
> messages and can take care to follow approaches such as the TLS approach you
> cite.

No, they cannot.

Your assumption that this is only a remote attacker is NOT a reasonable threat analysis of RSA-ES.

> 
> (In reply to Ryan Sleevi from comment #8)
> > (In reply to Mark Watson from comment #7)
> > > So, first, considering the issue actually in the subject line of this bug,
> > > if we change the specification so that padding errors and parse errors do
> > > not return distinct codes, then I believe the padding oracle attack of [B98]
> > > and variants is rendered infeasible for keys that have usage 'unwrap' and
> > > not 'decrypt' and where the wrapped key format has some structure: the
> > > chosen ciphertexts in the attack would not only need to result in correctly
> > > padded plaintext, but syntactically valid payloads. The chance of this for
> > > any given chosen ciphertext seems little better than random, rendering the
> > > attack infeasible.
> > 
> > Mark,
> > 
> > That's not a correct security analysis of B98. Structured results reveal
> > even *more* details about the nature of the failure. You have to permeate
> > the constant-timedness of the operations throughout the entire algorithm in
> > order to mitigate, as any short-circuits reveal whether or not it was
> > well-formed.
> 
> I'd be happy to be proven wrong, but I don't think what you say above is the
> whole story. The attack is based on the fact that the oracle reveals, when
> the padding check succeeds, that a chosen multiple of the plaintext lies
> within a known, simple, subset of the set of all possible plaintexts:
> specifically the subset with valid PKCS#1 padding. This is (roughly) 2^16
> smaller than the set of all plaintexts, because the first two bytes are 0x00
> and 0x02. If the oracle returns an error, little or nothing useful is
> revealed about the plaintext.
> 
> Now, it is clear that if the oracle instead reveals that a chosen multiple
> of the plaintext is both PKCS conforming *and* encodes a valid JWK or ASN.1
> structure then this success result reveals much more information about the
> plaintext. The set of possible plaintext values with both properties is much
> smaller.
> 
> However, multipliers with this property are much much harder to find. The
> _average_ amount of information revealed with each trip to the oracle is, I
> expect, much less, since most of the time you get a failure. I admit I don't
> have a proof of this, though. Do you have a proof of, or evidence for, the
> converse ?
> 
> Furthermore, it's not clear that the additional restriction of the possible
> plaintext set admits a practical exploitation except for the obvious one
> that the plaintext is a multiple of 125 (in the JWK case). It seems to me
> that a practical attack based on this would be something worthy of
> publication, not something we should assume / expect to exist.
> 
> Regarding timing attacks, I think some evidence is required to suggest that
> this might be feasible based on the RSA-ES WebCrypto primitive alone. Of
> course it is possible to design protocols that expose timing attacks as in
> the XML security case, where the attacker can force the victim to decrypt
> 1MB of data in the success case and none on the failure case. 

You're wrong.

It should be painfully obvious that RSA-ES with unwrap creates two forms of oracles when dealing with structured data, that fundamentally CANNOT be removed from this API.

The first is quite simple: If using RSA-ES to unwrap a JWK, then on a successful padding check, the entire data will be provided to importKey, which will perform a JSON parsing operation or an ASN.1 decoding operation. On a failed padding check, importKey will not be called. That's a padding oracle, plain and simple.

Now let's say you said that it would still call importKey, but with random data. Because JSON/PKCS8 has structure, on a success case, every single octet of the decrypted data would be accessed. However, because random data would not, it would only access the first N octets up to an error. That's a timing oracle, plain and simple.

Now, let's say you tried to be clever, and said only unstructured keys could be used. Your random data stream is now a 'valid' key, so import succeeds and returns a Key object if the padding check fails. You now get into the issues described in the XML security paper - for which again, you've got both a padding and timing oracle.


> > The distinction needs only be sufficient between "success" and "failure",
> 
> True - it is the success case that carries the exploitable information.
> 
> > and timing provides a clear source of this.
> 
> It's not clear that can't be mitigated for an attacker modifying / observing
> a network protocol.
> 

Your failure to consider the 'local access' threat here is perhaps why we disagree on why this method is broken.

 
> > > Finally, for the second case of an attacker able to modify and observe
> > > messages but unable to insert arbitrary code onto the client, it would be
> > > sufficient for the JS application to avoid exposing a distinction between
> > > the success and failure cases, for example as per the TLS approach Ryan
> > > cited.
> > 
> > Timing is sufficient to expose this. Considering that different scripts
> > running in different origin have access to high resolution timers, I do not
> > feel comfortable at all saying that this is a non-issue if you "just use
> > TLS" (or related)
> 
> Well, I didn't say "just use TLS". And we are talking about a network-based
> attack. Client-side high resolution timers are relevant only if the
> application under attack exposes its messaging protocol locally to other
> origins (over postMessage or I guess some convoluted WebSockets thing over
> localhost).

No, I'm not talking about a network-based attack. I'm talking about the fundamental security - regardless of network or not.


> > > I don't want to underplay the significance of the weaknesses with this
> > > padding scheme or suggest for a moment that one shouldn't always use
> > > RSA-OAEP instead if that is available. But it seems that support for
> > > RSA-OAEP is not going to be universal in browsers, at least initially.
> > 
> > That seems a premature conclusion.
> 
> Ok, good. If RSA-OAEP is universally supported then I'm not so concerned
> about whether RSA-ES is included or not.

This is *not* something that is in scope for this WG to dictate, as has been noted before.

This WG simply documents ways to represent the algorithms. It is up to UAs to implement.

> > It's true that support for *anything* is not going to be universal.
> > 
> > I have zero concerns with removing RSA-ES, and there seems sufficient
> > consensus to do so.
> 
> You don't have consensus at this stage.

Thank you for making it clear your support from a broken and insecure algorithm. It is incredibly disheartening that you would continue to espouse it.

This document serves primarily to document how, if RSA-ES is implemented, it would look.

We can leave this algorithm in, but I think it will do a disservice to API reviewers, as
1) It remains unlikely that any implementor will implement/ship, for all the reasons documented here
2) It will confuse reviewers to document an unimplemented algorithm

Of course, we can simply defer that to REC status and we do the implementation status for every algorithm, but I would hope it would be obviously non-controversial to simply remove now.

> > This is, perhaps, the worst of all the options.
> > 
> > I do not support RSA-ES without further modifications to provide
> > meaningfully robust defense - changes that fundamentally alter the API and
> > it's reporting.
> > 
> > If you look at
> > http://www.nds.rub.de/media/nds/veroeffentlichungen/2012/07/11/
> > XMLencBleichenbacher.pdf , you can see a more practical application of the
> > attack to the API exposed. This has previously been discussed on-list.
> 
> That paper describes attacks that are based on more than just the weakness
> in RSA-ES. Other aspects of the XML security design are essential to the
> attacks.
> 
> What this proves is that it's possible for smart people to invent broken
> protocols with RSA-ES. That's not in dispute.
> 
> What I'm arguing against is the conjecture that it is so hard to design
> protocols with any practical application that we should not provide the
> primitive at all.

Noted.

As written, I still assert that it is impossible to design a "secure" usage of RSA-ES with this API, which you seem to dispute. While proposals to change the API could be explored, they would require dramatic altering to unwrapKey and importKey, and such changes seem to provide very little value in light of "secure" unwrapping/decryption alternatives.

Ok, so at least we are clear now that we are talking specifically about the unwrapKey API with RSA-ES, as per the title of the bug, and not the decryptKey API (if you still maintain there is a problem with decryptKey, please raise a separate bug - it's a very different attack if it has to be done over the network rather than with direct access to the API).

You claim that there is still a viable timing attack if the error codes for padding failure and parsing failure were the same. Whether that's true depends on the implementation: an implementation could certainly take care to make the combined operation constant-time*. I'm not sure what changes we could make to the API to require that, though ?

However, as I explained, this attack is only of interest for the case where the attacker is not present when the RSA key is generated / imported / unwrapped: if the attacker is present at that time they can replace webcrypto with their own polyfill and obtain the key directly - much easier.

So, I accept that for the specific case where an application persists an RSA-ES unwrapping key across browser sessions and on a browser with a sufficiently non-constant-time unwrapKey implementation, there is a relevant timing-based version of the padding oracle attack.

I want us to be clear about the technical rationale here and despite your strongly-worded assertions above, this limited scenario seems to be the only one left.

[* for example, if the padding check fails, the implementation could call importKey with a hard-coded JWK, discard the result and return the same error as it does for parsing failure.]

(In reply to Mark Watson from comment #11)
> Ok, so at least we are clear now that we are talking specifically about the
> unwrapKey API with RSA-ES, as per the title of the bug, and not the
> decryptKey API (if you still maintain there is a problem with decryptKey,
> please raise a separate bug - it's a very different attack if it has to be
> done over the network rather than with direct access to the API).

No, it doesn't, but considering that I'm not advocating support for RSA-ES, it's likely not worth exploring that in detail.

> 
> You claim that there is still a viable timing attack if the error codes for
> padding failure and parsing failure were the same. Whether that's true
> depends on the implementation: an implementation could certainly take care
> to make the combined operation constant-time*. I'm not sure what changes we
> could make to the API to require that, though ?

And that's what I was exploring in Comment 1. However, as written, it's *not* a quality of implementation issue. The spec makes NO requirements on how this needs to be constant-time.

Your proposal of a hardcoded-key still fail to address the timing issues, but I feel like this is going to be a bit back-and-forth detailing why the proposals are not constant time. (In this case, you still have cache lines, you still have memory access patterns, and you still have the possibility of distinguishing whether or not the hardcoded key is the same size as the expected key).

Mark, constant-time implementations are hard. Real hard. For example, of the open-source RSA-OAEP implementations I've seen, there's only one constant-time implementation not susceptible to Manger's attack. For many open-source implementations not named "NSS" or "OpenSSL", cache-safe AES and AES-GCM remain pipe dreams.

> 
> However, as I explained, this attack is only of interest for the case where
> the attacker is not present when the RSA key is generated / imported /
> unwrapped: if the attacker is present at that time they can replace
> webcrypto with their own polyfill and obtain the key directly - much easier.
> 
> So, I accept that for the specific case where an application persists an
> RSA-ES unwrapping key across browser sessions and on a browser with a
> sufficiently non-constant-time unwrapKey implementation, there is a relevant
> timing-based version of the padding oracle attack.

Which is, you know, a presumed major use case and part of making sure the API is safe with respect to implementation behaviours. After all, ensuring constant-time safe access to primitives was one of the key motivations for the API.

> 
> I want us to be clear about the technical rationale here and despite your
> strongly-worded assertions above, this limited scenario seems to be the only
> one left.

I disagree, if only because your mitigations proposed are demonstrably not safe, and certainly NOT part of the specification.

> 
> [* for example, if the padding check fails, the implementation could call
> importKey with a hard-coded JWK, discard the result and return the same
> error as it does for parsing failure.]

(In reply to Mark Watson from comment #9)
[..]
> 
> I'd be happy to be proven wrong, but I don't think what you say above is the
> whole story. The attack is based on the fact that the oracle reveals, when
> the padding check succeeds, that a chosen multiple of the plaintext lies
> within a known, simple, subset of the set of all possible plaintexts:
> specifically the subset with valid PKCS#1 padding. This is (roughly) 2^16
> smaller than the set of all plaintexts, because the first two bytes are 0x00
> and 0x02. If the oracle returns an error, little or nothing useful is
> revealed about the plaintext.
> 
> Now, it is clear that if the oracle instead reveals that a chosen multiple
> of the plaintext is both PKCS conforming *and* encodes a valid JWK or ASN.1
> structure then this success result reveals much more information about the
> plaintext. The set of possible plaintext values with both properties is much
> smaller.
> 
> However, multipliers with this property are much much harder to find. The
> _average_ amount of information revealed with each trip to the oracle is, I
> expect, much less, since most of the time you get a failure. I admit I don't
> have a proof of this, though. Do you have a proof of, or evidence for, the
> converse ?
> 
> Furthermore, it's not clear that the additional restriction of the possible
> plaintext set admits a practical exploitation except for the obvious one
> that the plaintext is a multiple of 125 (in the JWK case). It seems to me
> that a practical attack based on this would be something worthy of
> publication, not something we should assume / expect to exist.

Even if one could produce an implementation that doesn't leak by timing or some other channel that the padding attack passed or failed, just the fact that the final plaintext was a valid symmetric key of a particular length leaks enough information to admit an attack requiring (for 1024 bit RSA) a median of roughly 12 million messages - that's around 2^{23}. See Bardou et al "Efficient Padding Oracle Attacks.." CRYPTO 2012. This attack, like all others, will only get better. 


> What I'm arguing against is the conjecture that it is so hard to design
> protocols with any practical application that we should not provide the
> primitive at all.


I believe there is excellent evidence to support the conjecture that it is too hard to design a secure protocol with a practical application involving RSA PKCS#1v1.5 to justify including this primitive. For example, TLS is probably the most scrutinized protocol we know, and yet another vulnerability in a widely deployed implementation relying on the RSA PKCS#1v1.5 padding oracle attack was announced April 2014 (http://www.oracle.com/technetwork/topics/security/cpuapr2014-1972952.html , http://armoredbarista.blogspot.fr/2014/04/easter-hack-even-more-critical-bugs-in.html).

> > 
> > I want us to be clear about the technical rationale here and despite your
> > strongly-worded assertions above, this limited scenario seems to be the only
> > one left.
> 
> I disagree, if only because your mitigations proposed are demonstrably not
> safe, and certainly NOT part of the specification.

I conceded the timing attack for unwrap, so whether the timing mitigations are safe or not is irrelevant.

My point was that if the RSA-ES key is not persisted, the existence of this attack is of no value to an attacker who can inject arbitrary code. And if they cannot inject arbitrary code they have to conduct the timing attack remotely, which is much harder unless the application gives you some help (as in the XML case, where the attacker gets to choose whether the app decrypts 16 bytes or 16 megabytes before responding).

I am not trying to substantiate any major claim about RSA-ES here, only provide an existence proof of a usage that might be temporarily reasonable if RSA-OEAP was not available.

Also, I wanted to dis-entangle the unwrap and decrypt cases and the local and network attack cases as the considerations for all four combinations are quite different.

https://dvcs.w3.org/hg/webcrypto-api/rev/e78209123956