[Bug 25431] Error names allow RSAES-PKCS1-v1_5 oracle attack against wrapped keys

https://www.w3.org/Bugs/Public/show_bug.cgi?id=25431

--- Comment #9 from Mark Watson <watsonm@netflix.com> ---
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.

-- 
You are receiving this mail because:
You are on the CC list for the bug.

Received on Tuesday, 13 May 2014 15:48:28 UTC