Cryptology ePrint Archive: Report 2018/003

How to (not) share a password: Privacy preserving protocols for finding heavy hitters with adversarial behavior

Moni Naor and Benny Pinkas and Eyal Ronen

Abstract: Bad choices of passwords were and are a pervasive problem. Most password alternatives (such as two-factor authentication) may increase cost and arguably hurt the usability of the system. This is of special significance for low cost IoT devices. Users choosing weak passwords do not only compromise themselves, but the whole ecosystem. E.g, common and default passwords in IoT devices were exploited by hackers to create botnets and mount severe attacks on large Internet services, such as the Mirai botnet DDoS attack.

We present a method to help protect the Internet from such large scale attacks. We enable a server to identify popular passwords (heavy hitters), and publish a list of over-popular passwords that must be avoided. This filter ensures that no single password can be used to compromise a large percentage of the users. The list is dynamic and can be changed as new users are added or when current users change their passwords. We apply maliciously secure two-party computation and differential privacy to protect the users' password privacy. Our solution does not require extra hardware or cost, and is transparent to the user.

Our private heavy hitters construction is secure even against a malicious coalition of devices which tries to manipulate the protocol in order to hide the popularity of some password that the attacker is exploiting. It also ensures differential privacy under continues observation of the blacklist as it changes over time.

As a reality check we verified the following three tests: computed the guarantees that the system provides with respect to a few publicly available data points, ran simulations on various distributions, and implemented and analyzed a proof-of-concept on an IoT device.

Our construction can also be used in other settings to privately learn heavy hitters in the presence of an active malicious adversary. E.g., learning the most popular sites accessed by the TOR network.

Category / Keywords: differential privacy, heavy hitters, passwords, secure computation, malicious model.

Date: received 31 Dec 2017, last revised 17 May 2018

Contact author: eyal ronen at weizmann ac il

Available format(s): PDF | BibTeX Citation

Version: 20180517:172044 (All versions of this report)

Short URL: ia.cr/2018/003

Discussion forum: Show discussion | Start new discussion


[ Cryptology ePrint archive ]