—Password-based authentication is essential to any online service. It is normally powered by a database of user credentials, for example a RADIUS server. However, even with various indexing techniques (e.g., B+-tree), password-based authentication can still be resource-consuming on large-scale systems (e.g., Internet and IoT), and is thus vulnerable to distributed denial-of-service (DDoS) attacks. In this paper, we propose a cloud-based firewall that uses Bloom filters to pre-screen and reject suspicious requests with wrong password before they reach the authentication server. The main challenge is the security of the firewall because it can be operated by a third party, so the Bloom filters might be accessed by adversaries to assist their brute-force password guessing. To ensure security, we start with the assumption of trusted cloud server and design a key-based semantic secure Bloom filter (KSSBF) for the best efficiency. We then design a generically secure Bloom filter (GSBF) for non-trusted cloud servers, which is key-independent and with strictly provable security. Through theoretical and empirical analysis, we show both of them can mitigate malicious requests without compromising the security of passwords.