Cryptography Reference
In-Depth Information
17.2.2
Proof by Knowledge
In a
proof by knowledge
, the claimant proves to the verifier his or her identity by
showing knowledge of some secret information, such as a password, a personal
identification number (PIN), or a cryptographic key. This information, in turn,
may either be static or dynamically changing. Roughly speaking, static information
can be used to implement weak authentication, whereas dynamically changing
information can be used to implement strong authentication. Note that in either case,
the secret information may be too large or include too much entropy to be memorized
by human users. Consequently, the use of some auxiliary technology to store
and make available the secret information is widely deployed. Examples include
magnetic-stripe cards, smart cards, USB tokens, and personal digital assistants
(PDAs) that store secret information (in possibly encrypted form). Note, however,
that in contrast to the use of these technologies in a proof by possession, these
technologies are only used to extend the capacities of the human users (or their
memories) in a proof by knowledge. The existence of the physical device by itself
need not be verified.
It is possible and makes a lot of sense to combine a proof by possession with a
proof by knowledge. For example, if we want to withdraw money from an automatic
teller machine (ATM), then we routinely insert our ATM card and enter a PIN into
the terminal associated with the ATM. In this case, the insertion of the ATM card
represents a proof by possession, whereas the fact that the user enters his or her PIN
represents a proof by knowledge. An adversary who wants to illegitimely withdraw
money from an ATM must have both the ATM card and the user's PIN.
17.2.2.1
Static Information
As mentiond earlier, examples of static information that may be used in a proof by
knowledge include passwords, passphrases, PINs, and cryptographic keys. As of this
writing, passwords are by far the most widely deployed authentication technology
used in computer networks and distributed systems. This is because they are simple
to implement and use. Unfortunately, however, passwords and the way they are
managed have the following two major security problems:
1. Users tend to select passwords that are easy to remember. Consequently, such
passwords are not uniformly distributed and are often simple to guess [4,
5]. Password guessing is the process of correctly guessing the password of
a legitimate user. Dan Klein analyzed the feasibility of password-guessing
attacks for approximately 15,000 user accounts in 1990. As a result, he found
that he could guess 2.7% of the passwords in the first 15 minutes and 21%
