How do you figure? Each revocation is by certificate serial number, which typically run 4 to 20 bytes, and the revocation date, with possible extensions for more information.
Add a little overhead for the signature on the list, etc.
Exaggerate wildly and call that 100 bytes per revocation: we're down to at most 100MB of revocation data for the million user case; that's not a lot of data.
It's probably closer to 20 or so bytes per revocation, ~20MB of revocation data. Spread out over as many CDPs as the CA wants to maintain.
The system used in the Canadian federal government creates one CDP per 375 users, so that CDPs are capped at roughly 750 certs each (each user has two key pairs, one for verification, one for encryption). At 20-100 bytes per revocation, that's 15KB to 75KB per CDP.
That's not much at all. And given that any given user interacts with a subset of all possible users, they won't have anywhere near all of the CRLs downloaded.
Please elaborate. The CDP (CRL Distribution Point) allows for multiple strategies, some of which can scale quite well.
The Canadian government runs several PKIs with tens of thousands of active certs, many thousands of revoked, no problems at all, because of CDPs.
(Full disclosure: I worked for several years for the company that invented the CDP. I was not involved in the invention.)
(BTW, FF 28 detected the revoked cert just fine.)