Article Preview
TopIntroduction And Previous Work
Despite recent advances in biometric authentication (Melon, 2017) and account linking (Batista et al., 2018), passwords are still the main method of authentication used online and will probably remain so in the near future. Countless studies have been written on the pitfalls of password-based authentication (Jensen, 2013 ; Ma, 2010), initially focusing on low security, with users creating bad passwords (Bonneau et al., 2012) and repeatedly dodging security measures (Shay et al., 2010; Ur et al., 2015; Lipa 2016), but also on service providers ignoring best practices on how to secure password databases (Gressin, 2017). More recently, research on how to make passwords more usable has made advances (Blum et al., 2015; Melicher et al., 2016), and some of the effects of bad password policies are being reversed, to focus on longer passwords (Segreti et al., 2017). Unlike random passwords with special characters which suffer from low memorability (Marquardson, 2012), long and simple passwords and passphrases (Keith et al., 2007; Bonneau et al., 2012; Yang et al., 2016) can benefit from humans' superior ability to memorise strings that make sense, improving both security and usability (Pilar et al., 2012; Shay et al., 2014).
As authentication becomes an omnipresent task, being refused access is increasingly frustrating, with forgetting one's password being perceived about as frustrating as forgetting one's keys (Centrify, 2014). Moreover, users sometimes forget their passwords, and often mistype them. To prevent some of this frustration and improve usability, some services like Facebook have discreetly adopted typo correction for the 2-3 most frequent typos, such as forgetting the caps lock or capitalising the first character of a password on a mobile device (Lambert, 2012).
In an innovative paper in 2016, Chatterjee et al. discovered that a vast majority of authentication failures comes from a few simple typos, and that it could turn 3% of the users away. They developed a first typo-tolerant password checker which was highly secure (and computationally intensive) but could only correct about 20% of typos. The same team developed a second system called TypTop (Chatterjee et al., 2017), which is efficient both computationally and memory-wise, and corrects up to 32% of typos. This system works by keeping a cache of allowed password hashes corresponding to the frequent typos made by the user, and updates this cache at each successful authentication. Using a different approach, Blanchard also proposed a simple theoretical method based on homomorphic encryption that is too computationally expensive to be usable in practice (Blanchard, 2019). Finally, Woodage (2017) and some of the original authors created a new distribution-sensitive scheme that adjusted the error rate and hashing time, improving the resistance to certain attacks and providing better time/security trade-offs. Beyond the obvious usability improvements, those systems can actually have a positive impact on security as they make long passwords — which are more error-prone — much more usable, lowering the cost of using highly secure passwords.