Browse Prior Art Database

PASSWORD HASHES WITH UPDATABLE MASTER KEYS THAT ARE DIFFICULT TO BRUTE-FORCE

IP.com Disclosure Number: IPCOM000231464D
Publication Date: 2013-Sep-30
Document File: 4 page(s) / 21K

Publishing Venue

The IP.com Prior Art Database

Related People

Scott Fluhrer: AUTHOR

Abstract

Techniques are presented herein to express a hashed password as the relationship between two encrypted group elements. As a result, brute force efforts are made difficult to derive a user password, yet updates are allowed to be made to a master password.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 44% of the total text.

Page 01 of 4

PASSWORD HASHES WITH UPDATABLE MASTER KEYS THAT ARE DIFFICULT TO BRUTE-FORCE

AUTHOR:

Scott Fluhrer

CISCO SYSTEMS, INC.

ABSTRACT

    Techniques are presented herein to express a hashed password as the relationship between two encrypted group elements. As a result, brute force efforts are made difficult to derive a user password, yet updates are allowed to be made to a master password.

DETAILED DESCRIPTION

    In cryptography, salt is random data that are used as an additional input to a one- way function that hashes a password or passphrase. The primary function of salts is to defend against dictionary attacks and pre-computed rainbow table attacks. One common way to authenticate a user-selected password is to store a hash of the password (along with salt) on the system. When the user enters a password, the hash function is applied to the password and the salt, to determine whether there is a match to the previously computed hash.

    One problem with this procedure is that if an attacker gets access to the list of hashed passwords, the attacker can take a dictionary of "the one billion most common passwords" and hash each one (with the salt the attacker has). If the hash the attacker obtains matches the hash from the list, the attacker has learned that password. This is a particular danger if the hashed passwords reside in an administrator accessible area.

    One way to attempt to address this would be to have a master password on the system. This master password is kept in a secure location on the system, and it used as a part of the formula used to hash a password. In order to verify a guess of the password, the attacker would need to guess both the user password, and the master password. Ideally, if there are N plausible user passwords, and M plausible master passwords, this take O(NM) time; that is, each possible combination of user password and master Copyright 2013 Cisco Systems, Inc.

1


Page 02 of 4

password would need to be checked separately. If the dictionary of both is even moderately large, this becomes impractical. In addition, an administrator would need to update the master password. It is desirable to be able to update the password hashes computed with the previous master password to use the new master password.

    There are two obvious ways to stir in a user password with a master password. First, a hash is made Hash(user_password, master_password). This, with an appropriate one-way hash function, obviously takes O(NM) time for an attacker to recover the user_password and master_password (because the attacker would need to compute the hash for each pair of user and master passwords separately). The problem with this solution is that if the master_password is updated, it is not possible to update the hash to reflect it.

    Second, a hash is made Encrypt(master_password, Hash(user_password)), that is, encrypt a hash of the user's password with the master password. Then, if the master_password is updated, we take the above hash, decrypt...