Firefox Accounts: Flawed padding validation for RSA signatures

NEW
Unassigned

Status

a year ago
11 days ago

People

(Reporter: gaubugzilla, Unassigned)

Tracking

({sec-low, wsec-crypto})

unspecified
sec-low, wsec-crypto
Points:
---
Bug Flags:
sec-bounty -

Firefox Tracking Flags

(Not tracked)

Details

(Whiteboard: [reporter-external] [web-bounty-form] [verif?])

(Reporter)

Description

a year ago
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.
Flags: sec-bounty?
Hi Wladimir, thanks for the report. We'll take a look.
Group: websites-security → firefox-core-security
Component: Other → Firefox Accounts
Keywords: wsec-crypto
Product: Websites → Firefox
Group: firefox-core-security → cloud-services-security
Component: Firefox Accounts → Server: Firefox Accounts
Product: Firefox → Cloud Services
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?
(Reporter)

Comment 3

a year ago
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.
(Reporter)

Comment 5

a year ago
(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 :)
> 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.
(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.
(Reporter)

Comment 8

a year ago
(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.
(Reporter)

Comment 9

a year ago
(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.
> 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!
>> 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.
> 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.
(Reporter)

Comment 13

a year ago
(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.
(Reporter)

Comment 14

a year ago
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.
(Reporter)

Comment 15

a year ago
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.
While the discussion here is quite interesting, this bug does not qualify for a bounty reward.
Group: cloud-services-security
Flags: sec-bounty? → sec-bounty-
See Also: → bug 1477968
Keywords: sec-low
You need to log in before you can comment on or make changes to this bug.