Simon Blake-Wilson, Don Johnson, and Alfred Menezes
This paper proposes new protocols for two goals: authenticated key agreement and authenticated key agreement with key confirmation in the asymmetric (public-key) setting. A formal model of distributed computing is provided, and a definition of the goals within this model supplied. The protocols proposed are then proven correct within this framework in the random oracle model. We emphasize the relevance of these theoretical results to the security of systems used in practice. Practical implementation of the protocols is discussed. Such implementations are currently under consideration for standardization.
An Efficient Protocol for Authenticated Key Agreement
This paper proposes a new and efficient two-pass protocol for
authenticated key agreement in the asymmetric (public-key) setting.
The protocol is based on Diffie-Hellman key agreement and can be
modified to work in an arbitrary finite group and, in particular,
elliptic curve groups. Two modifications of this protocol are also
presented: a one pass authenticated key agreement protocol suitable
for environments where only one entity is on-line, and a three-pass
protocol in which key confirmation is additionally provided. The
protocols are currently under consideration for standardization
in ANSI X9.42, ANSI X9.63, and IEEE P1363.
PostScript File (August 28, 1998) (210K)
On the Security Properties of OAEP as an All-or-nothing Transform
This paper studies All-or Nothing Transforms (AONTs), which have been
proposed by Rivest as a mode of operation for block ciphers. An AONT is an
unkeyed, invertible, randomized transformation, with the property that
it is hard to invert unless all of the output is known. Applications of AONTs
include improving the security and efficiency of symmetric-key and public-key
encryption. We give several formal definitions of security for AONTs that are
stronger than the original ones and are more suited to practical applications.
We then prove that Optimal Asymmetric Encryption Padding (OAEP), which was
originally introduced by Bellare and Rogaway in a different context, satisfies
these definitions (in the random oracle model). This is the first construction
of an AONT that has been proven secure in the strong sense. The adversary's
advantage in getting information about the input of the OAEP is shown to be
inversely exponential in the number of bits removed from the output. Our bound
is nearly optimal, in the sense that no adversary can do substantially better
against the OAEP than by exhaustive search. We also show that no AONT can
achieve substantially better security than OAEP.
PostScript File (August 8, 1999) (676K)
Improving The Exact Security Of Digital Signature Schemes
We provide two contributions to exact security analysis of digital signatures:
PostScript File
(August 25, 1999) (619K)
Signing on a Postcard
We investigate the problem of signing short messages using a scheme that
minimizes the total length of the original message and the appended signature.
This line of research was motivated by several postal services interested by
stamping machines capable of producing digital signatures. Although several
message recovery schemes exist, their security is questionable. This paper
proposes variants of DSA and ECDSA allowing partial recovery: the signature
is appended to a truncated message and the discarded bytes are recovered
by the verification algorithm. Still, the signature authenticates the whole
message. Our scheme has some form of provable security, based on the
random oracle model. Using further optimizations we can lower the scheme's
overhead to 26 bytes for a 2-80 security level, compared to forty
bytes for DSA and ECDSA and 128 bytes 1024-bit RSA.
PostScript File (February 14, 2000) (4315K)
Generic Groups, Collision Resistance, and ECDSA
Proved here is the sufficiency of certain conditions to ensure
the Elliptic Curve Digital Signature Algorithm (ECDSA) existentially
unforgeable by adaptive chosen-message attacks. The sufficient conditions
include (i) a uniformity property and collision-resistance for the
underlying hash function, (ii) pseudo-randomness in the private key space
for the ephemeral private key generator, (iii) generic treatment of the
underlying group, and (iv) a further condition on how the ephemeral public
keys are mapped into the private key space. For completeness, a brief
survey of necessary security conditions is also given. Some of the
necessary conditions are weaker than the corresponding sufficient
conditions used in the security proofs here, but others are identical.
Despite the similarity between DSA and ECDSA, the main result is not
appropriate for DSA, because the fourth condition above seems to fail for
DSA. (The corresponding necessary condition is plausible for DSA, but is
not proved here nor is the security of DSA proved assuming this weaker
condition.) Brickell et al., Jakobsson et al. and Pointcheval et al. only
consider signature schemes that include the ephemeral public key in the
hash input, which ECDSA does not do, and moreover, assume a condition on
the hash function stronger than the first condition above. This work seems
to be the first advance in the provable security of ECDSA.
This work supersedes the paper "The Exact Security Of ECDSA", posted to
this site in January 2001.
New Security Results on Encrypted Key Exchange
Schemes for encrypted key exchange are designed to provide two entities communicating over a public network, and sharing a (short) password only, with a session key to be used to achieve data integrity and/or message confidentiality. An example of a very efficient and ``elegant'' scheme for encrypted key exchange considered for standardization by the IEEE P1363 Standard working group is AuthA. This scheme was conjectured secure when the symmetric-encryption primitive is instantiated via either a cipher that closely behaves like an ``ideal cipher'', or a mask generation function that is the product of the message with a hash of the password. While the security of this scheme in the former case has been recently proven, the latter case was still an open problem. For the first time we prove in this paper that this scheme is secure under the assumptions that the hash function closely behaves like a random oracle and that the computational Diffie-Hellman problem is difficult. Furthermore, since Denial-of-Service (DoS) attacks have become a common threat we enhance AuthA with a mechanism to protect against them.
Laurie Law, Alfred Menezes, Minghua Qu, Jerry Solinas and Scott Vanstone
Zipped PostScript File (August 28, 1998) (62K)
Adobe Acrobat (.pdf) File (August 28, 1998) (228K)
Victor Boyko
Zipped PostScript File (August 8, 1999) (150K)
Adobe Acrobat (.pdf) File (August 8, 1999) (306K)
Silvio Micali and Leonid Reyzin
Adobe Acrobat (.pdf) File
(August 25, 1999) (334K)
David Naccache and Jacques Stern
Zipped PostScript File (February 14, 2000) (151K)
Adobe Acrobat (.pdf) File (February 14, 2000) (259K)
Daniel R. L. Brown, February 2002
Emmanuel Bresson, Olivier Chevassut and David Pointcheval, October 2004
This page was last modified on October 7, 2004.
IEEE Home Page
IEEE Standards
IEEE P1363