1447008 - Firefox Accounts: Flawed padding validation for RSA signatures

Status: RESOLVED WONTFIX

(Cloud Services :: Server: Firefox Accounts, enhancement)

Description

[Wladimir Palant]

Firefox Accounts uses RSA to sign assertions (see https://api.accounts.firefox.com/.well-known/browserid for the public RSA key), a fake signature would allow getting OAuth tokens for other people's accounts for example. The code validating RSA signatures can be seen under https://github.com/mozilla/browserid-crypto/blob/a372a53cffe27a84eebb85fc32d75edcb17a57f9/libs/external/rsa-sign.js#L134. As far as I can tell, there are three flaws here:

1. The 0001fffff... prefix is not validated. It is removed if present but its existence and validity isn't actually enforced. It is my understanding that this weakens the protection provided by the padding considerably.

2. This verification algorithm will accept SHA-1 signatures even though all signatures are generated using SHA-256 now. Assuming that SHA-1 was used here before and that somebody still has a SHA-1 signed assertion, generating a collision might be possible.

3. There are known attacks against fixed-pattern padding in RSA, with the result of PKCS#1 v1.5 paddings (the kind being used here) being discouraged. Mind you, my research seems to indicate that this currently isn't relevant for signing but only encryption. Still, not an ideal situation.

Comment 1

[Greg G]

Hi Wladimir, thanks for the report. We'll take a look.

Comment 2

[Frederik Braun [:freddy]]

Some preliminary thoughts (I suggest we find an actual cryptographer though.)
1) I think an early abort might introduce a padding oracle. 
2) I suppose that should be fixed :-)
3) talks about PKCS#1 v1.5, but documentation point to PKCS#1 v2.1, what's going on?

Comment 3

[Wladimir Palant]

1) Padding oracles are only relevant for encryption. This is about signatures, anybody can validate them locally.

3) Where can I see that documentation? Maybe that's about certificates signed by Firefox Accounts, that's not the same mechanism.

Comment 4

[Frederik Braun [:freddy]]

1) Ah. Right. :)
3) I was only seeing https://github.com/mozilla/browserid-crypto/blob/a372a53cffe27a84eebb85fc32d75edcb17a57f9/libs/external/rsa-sign.js#L30

Comment 5

[Wladimir Palant]

(In reply to Frederik Braun [:freddyb] from comment #4)
> 3) I was only seeing
> https://github.com/mozilla/browserid-crypto/blob/
> a372a53cffe27a84eebb85fc32d75edcb17a57f9/libs/external/rsa-sign.js#L30

Well, PKCS#1 v2.1 document specifies two signature scheme that are called RSASSA-PSS and RSASSA-PKCS1-v1_5. You can guess which one we have here :)

Comment 6

[Ryan Kelly [:rfkelly]]

> a fake signature would allow getting OAuth tokens for other people's accounts for example

It would also let you download their (encrypted) sync data.

> The code validating RSA signatures can be seen under
> https://github.com/mozilla/browserid-crypto/blob/a372a53cffe27a84eebb85fc32d75edcb17a57f9/libs/external/rsa-sign.js#L134.

This is a bunch of ancient code inherited from BrowserID/persona, so I'm not entirely surprised to find that it's not keeping up with latest recommendations.  I'd quite like us to just stop using it entirely, and move to plain JWTs implemented atop a modern and well-maintained library.  Unfortunately, we've got legacy code shipping Firefox that expects some BrowserID-style behaviour, so it's not a trivial change.

Like Bug 1320222, it's probably time that I sat down and figured out what this migration might look like...

> Assuming that SHA-1 was used here before and that somebody still has a SHA-1 signed assertion

FWIW I'm fairly confident that we've never used SHA1 on this service, but I won't go so far as to guarantee it.

> 1. The 0001fffff... prefix is not validated. It is removed if present but its existence and validity isn't actually
> enforced. It is my understanding that this weakens the protection provided by the padding considerably.

This worries me a bit, although I won't pretend to understand the implications in any detail.

Short-term, we could update this code to disable sha1 signatures and enforce the padding, but it'd only be a mitigation while we figure out how to get away from the legacy BrowserID codebase entirely.  Either way we'll need to do this:

> (I suggest we find an actual cryptographer though.)

:freddyb, we must have one of those on staff right? :-)
Can you suggest someone for us to talk to about the details here?  My first guess would be :mt but he's out this week.

Comment 7

[J.C. Jones [:jcj] (he/him)]

(In reply to Ryan Kelly [:rfkelly] from comment #6)
> > (I suggest we find an actual cryptographer though.)
> 
> :freddyb, we must have one of those on staff right? :-)
> Can you suggest someone for us to talk to about the details here?  My first
> guess would be :mt but he's out this week.

I recommend :franziskus. Last I checked he was out sick, but I cc'd him in the event that he is into the office Tues.

Comment 8

[Wladimir Palant]

(In reply to Ryan Kelly [:rfkelly] from comment #6)
> FWIW I'm fairly confident that we've never used SHA1 on this service, but I
> won't go so far as to guarantee it.

Yes, from the repository history it looks like it was always SHA-256. All the more reason to remove SHA-1 support.

Comment 9

[Wladimir Palant]

(In reply to Ryan Kelly [:rfkelly] from comment #6)
> This is a bunch of ancient code inherited from BrowserID/persona, so I'm not
> entirely surprised to find that it's not keeping up with latest
> recommendations.  I'd quite like us to just stop using it entirely, and move
> to plain JWTs implemented atop a modern and well-maintained library.

For reference, the signing part here uses fxa-jwtool module which in turn uses Node's built-in functionality (meaning: OpenSSL) to generate RSA signatures. Same could be done for verifying given that it runs on the server side as well, OpenSSL does proper padding validation. As of Node 8 it can also deal with RSA-PSS which avoids the fixed-pattern padding weaknesses.

Comment 10

[Ryan Kelly [:rfkelly]]

> Same could be done for verifying given that it runs on the server side as well, OpenSSL does proper padding validation.

Yep, and having reviewed this a little yesterday, I think we should make this move with some urgency.

Using the generic browerid-crypto library to validate assertions brings with it a *ton* of incidental complexity, including fetching  /.well-known/browserid from arbitrary hosts, following delegation chains, and more.  We don't need any of that for FxA and we should avoid pulling it in to reduce attack surface.

The one complication here is that the verifier also has to support verifying DSA signatures, which are added by the browser on top of the signed certificate produced by fxa-jwtool.  I expect we'll be able to do that using node builtinsas well, but have not confirmed it.

> As of Node 8 it can also deal with RSA-PSS which avoids the fixed-pattern padding weaknesses.

Thanks for the heads-up!

Comment 11

[Franziskus Kiefer [:franziskus]]

>> 1. The 0001fffff... prefix is not validated. It is removed if present but its existence and validity isn't actually
>> enforced. It is my understanding that this weakens the protection provided by the padding considerably.
> This worries me a bit, although I won't pretend to understand the implications in any detail.

The padding is there to avoid leaking information on the message during the RSA operations. But not checking it on the actual message check can of course have other implications not covered by any security considerations done for pkcs1v1.5. (There're no real security guarantees for anything in this encoding though.)

> 3. There are known attacks against fixed-pattern padding in RSA, with the result of PKCS#1 v1.5 paddings

These attacks regard encryption as you said. But given that signing and decrypting are essentially the same operations for RSA the signing service (not the verification) could potentially be used as oracle to leak information on the secret key (maybe even create signatures on arbitrary data). This depends on the implementation and would need more investigation.

> Yep, and having reviewed this a little yesterday, I think we should make this move with some urgency.

I'm frankly amazed how random (8 year old) crypto code from the internet is used for production libraries and would recommend switching away from this asap.

Comment 12

[Ryan Kelly [:rfkelly]]

> the signing service (not the verification) could potentially be used as oracle to leak information on
> the secret key (maybe even create signatures on arbitrary data). This depends on the implementation
> and would need more investigation.

The signing side of this is directly using signing primitives from the builtin nodejs `crypto` module:

  https://github.com/mozilla/fxa-jwtool/blob/master/index.js#L18

Per Comment 9, this bottoms out at OpenSSL, so I'm feeling a lot better about that part than about the verification side.

Comment 13

[Wladimir Palant]

(In reply to Franziskus Kiefer [:fkiefer or :franziskus] from comment #11)
> The padding is there to avoid leaking information on the message during the
> RSA operations. But not checking it on the actual message check can of
> course have other implications not covered by any security considerations
> done for pkcs1v1.5. (There're no real security guarantees for anything in
> this encoding though.)

Well, without padding any data would be accepted as a signature. One would still need a collision to make sure that this signature matches the data but at least with SHA-1 that's known to be possible. Consequently, padding validation reduces the chance of creating a signature that would be accepted and padding length is essential to keep that chance low. For RSA2048 with SHA256 the padding length is normally 224 bytes. The faulty padding validation here allows reducing it to merely 15 bytes (ASN.1 prefix indicating a SHA-1 hash). Of course, 2^119 tries would still be too much but I guess that somebody with better understanding of the math involved could find some shortcuts.

(In reply to Ryan Kelly [:rfkelly] from comment #12)
> > the signing service (not the verification) could potentially be used as oracle to leak information on
> > the secret key (maybe even create signatures on arbitrary data). This depends on the implementation
> > and would need more investigation.
> 
> The signing side of this is directly using signing primitives from the
> builtin nodejs `crypto` module:

But it still produces PKCS#1v1.5 signatures with a fixed-pattern padding. It can be made to produce RSA-PSS signatures with a single parameter change however, these are definitely the better alternative. Either way, I don't yet understand the attacks described there to a sufficient degree to tell what impact they have on signing.

Comment 14

[Wladimir Palant]

Actually, I just found this paper: https://iacr.org/archive/crypto2001/21390431.pdf. It says:

> In this paper we show that the size of P must be at least two-thirds of the size of N, i.e. we show that |P| < 2|N|/3 is insecure.

Here P is the fixed-pattern padding (can be reduced to 15 bytes here) and N is the modulus (256 bytes for RSA2048). Guess the signatures should be considered broken then.

Comment 15

[Wladimir Palant]

Never mind. I read more into the actual approach and now I understand why people say that these attacks don't affect signing. These attacks expect obtaining signatures for chosen plaintexts in order to construct a valid signature for an arbitrary message. If no plaintexts are being signed but only hashes then at least these attacks won't work. Also, for these attacks to succeed the signing service would have to produce signatures with insufficient padding, merely having the verifier accept them isn't sufficient.

Comment 16

[Julien Vehent]

While the discussion here is quite interesting, this bug does not qualify for a bounty reward.

Comment 17

[Tom Ritter [:tjr] (OOTO until 4/30 at least)]

It looks like we no longer use this library in the code to actually verify anything; except in programs in bin/ and test programs. (I presume the programs in bin/ are used - if at all - for testing also.)

If I'm right I think we can close this?

Comment 18

[Ryan Kelly [:rfkelly]]

I believe this code is still used, via browserid-verifier which uses browserid-local-verify which uses browserid-crypto. I was quite hoping that we would no longer be using BrowserID assertions for anything, but here we are in 2020 and they're still kicking around, due entirely to us not prioritizing that work.

Leaving the ni? for myself to come back to this bug with an explanation of how we're not going to be saying that again in 2021...

Comment 19

[Ryan Kelly [:rfkelly]]

We're still working on turning the plan into a concrete bug tree, which is complicated by the fact that it touches several different systems that track their bugs in different places. The plan is to deprecate and remove BrowserID support from all our products, in favour of plain old OAuth2.0 access tokens, and we're getting our heads around it in this document:

https://docs.google.com/document/d/1CnTv0Eamy7Lnbmf1ALH00oTKMPhGu70elRivJYjx5v0/

Comment 20

[Ryan Kelly [:rfkelly]]

We're made some good progress on deprecating BrowserID, and all our sync clients have now moved to OAuth by default. There's still work to do to completely disable the use of BrowserID assertions in our backend systems (ref https://github.com/mozilla/fxa/issues/6940) but it's far enough along that I'm comfortable closing this WONTFIX.