Cryptography Reference
In-Depth Information
private exponent
e
to Mallory, who could then impersonate her, and the protocol
would still have the soundness and completeness properties. Thus, Alice must
ensure that no information about
e
is leaked, the zero-knowledge property. Alice
proves
knowledge of
e
(without revealing
e
) byher response
y
to the challenge
r
in step 3 of the protocol. If Mallorydoes not have knowledge of
e
, and he
tries to impersonate Alice, then he is in the position in step 3 of having to
compute
y
, which is a function of
e
, in response to Bob's challenge
r
. However,
computing
e
from
v
involves solving an instance of the DLP, which is assumed
to be intractable. Yet it has not been proved that Schnorr's protocol is secure.
Attacks
: There are three main types of attacks on identification protocols
in general. We have alreadymet the
replay attack
in Footnote 5.1 on page
197. Defense against such attacks can involve the use of challenge-response
methods, or the use of nonces. Another type of attack is the
chosen-text at-
tack
, which is an attack on a challenge-response protocol where Mallorychooses
challenges according to some design to recover information about Alice's pri-
vate key. For example, in Schnorr's protocol, Alice encrypts the challenge
r
with
y
, so this attack involves chosen-plaintext (see Footnote 3.4 on page 127).
Methods for thwarting such attacks include the embedding of a nonce in each
challenge-response. Last, there is the
forced delay attack
, which involves Mallory
intercepting a message and relaying it later. This is a type of man-in-the-middle
attack (see Footnote 3.7 on page 134). Defense against it mayinclude the use
of nonces tied in with short response time outs.
Comparisons
: There are variations of Schnorr's protocol that have been
proved to be secure under the assumption of a particular discrete log. One such
is Okamoto's protocol (see [170, pages 131-133] for a description, analysis, and
comparison). However, Okamoto's protocol and other variations that are prov-
ablymore secure, sacrifice speed. Moreover, even without a proof of security
(which is scarce in anycase), Schnorr's protocol still has not been crptana-
lyzed. In other words, no weaknesses have been found, and with its e
K
ciency
and suitabilityfor use in smart cards (to which we will return later in the text)
it is an excellent pragmatic choice. When compared with the Feige-Fiat-Shamir
protocol, Schnorr's protocol is also much more eKcient. The reason for this is
that the most computationallyintensive operation is the modular exponentia-
tion in step 1 of the protocol, which bydesign, maybe computed oTine. In step
3 there is one modular addition and one modular multiplication, so the online
computations are verymoderate. The computations for Feige-Fiat-Shamir pro-
tocol are significantlygreater. The Schnorr algorithm was designed with this
computational eKciencyin mind for such applications as smart cards with low
computing power. In general, the Schnorr protocol is quite suitable when Alice
has restricted computing power. Notice as well that more computational eK-
ciencyis gained byusing a subgroup of order
q
(
p
1), which lowers the number
of bits needed for transmission. The three-pass protocol involved in steps 1-3
was a built-in design of the protocol to reduce bandwidth (see Footnote 4.5 on
page 183), especiallyin comparison to the Feige-Fiat-Shamir protocol.
−
Search WWH ::
Custom Search