23 March 2013
NSA Critiques Public Key Cryptography
Revelation of the early public key cryptography work of James Ellis, Malcolm
Williamson and Cliff Cocks at GCHQ occurred in 1997, eleven years after this
secret 1986 review cites them. Whitfield Diffie, one of the inventors or
PKC, commented in 1999 on the British precursors:
NSA Cryptolog, August-September 1986, pp. 27-29.
SECRECY, AUTHENTICATION, AND PUBLIC KEY SYSTEMS by Ralph C. Merkle UMI
(University Microfilms International) Research Press, Ann Arbor (c1982, 1979)
Reviewed by [redacted] P12
FOUO) Let us make it clear that this is not a book
in the usual sense but a revision of the author's doctoral dissertation written
under the guidance of Martin Hellman at Stanford University. As one would
expect, It is an immature work showing the narrow research of one student.
It is not a survey of the field as the title suggests. No library need acquire
C CCO) Merkle participated in the discovery, by Hellman
and his many students, of what has become known to the academic world as
public-key cryptography. (Actually, these systems were first conceived at
GCHQ by James Ellis in 1970.) Public-key cryptography allows "secure"
communications between subscribers to a large net though they have had no
previous knowledge of each other and share no key in the conventional sense.
Merkle's original scheme, based on solving "puzzles," as he describes it,
is "primarily of pedagogical and historical interest."
C CCO) The opening line of chapter 4 states incorrectly,
"This chapter describes the first public key system ever developed." Of course
Merkle could not have known that, several years earlier, such systems had
already been proposed by Malcolm Williamson and by Cliff Cocks at GCHQ.
S CCO) Perhaps it is a normal human failing to be blindly
proud of one's own ideas. The idea which Merkle and Hellman originated is
that of public-key systems based on the "knapsack" problem. Their design
has been discredited on the outside as the result of clever work of Adi Shamir,
Ernie Brickell, Andy Odlyzko, and Jeff Lazarias. [sentence redacted] Merkle
offered a prize of $100 to anyone who could solve the Merkle-Hellman knapsack;
this prize was paid to Shamir in 1982. Then Merkle risked $1,000 on the security
of the "iterated" Merkle-Hellman knapsack. This too was lost, to Brickell;
the work of Odlyzko and Lagarias also suffices to demonstrate the unworthiness
of the system.
C CCO) Merkle has not entirely missed the target. The opening
sentence of chapter 1 is spot on: "Cryptography is a fascinating subject,
even more so today than in the past." But he alludes to the S-boxes (unique,
so far as I know, to the Data Encryption Standard) as "found in many modern
cryptographic functions" (page 52). And in comparing his knapsack to the
sturdy public-key system developed outside by Ron Rivest, Adi Shamir, and
Len Adleman, (this is the system originally proposed by Cliff Cocks), he
states (p. 48): "the trapdoor knapsack appears less likely to possess a chink
in its armor."
C CCO) One of Merkle's ideas is that he has created an
"NP-complete conventional cipher" (the title of his chapter 8). In fact his
thinking is confused in several directions. Let us set the scene. A knapsack
is a set a1,a2, ... ,aa of n (large) positive
integers, known to everyone. The parameter n should be chosen large enough
to prevent an exhaustive analysis of the 2n possible cryptovariables
but small enough to allow timely operation of the encipherment scheme. Instead
of the usual "trapdoor" use of the knapsack, Merkle intends that the sender
and the receiver share key, one of the 2n binary n-vectors, which
they use to select some of the a. which add (as integers, not mod 2) to provide
a key. That is,
FOUO) Let's think about this a little. We're intending
to use this key to encipher a binary stream of data, with the usual equation
C = P ⊕ K, so that the plaintext can be recovered via P = C ⊕ K. That
means that we need an arbitrarily long key stream! He has in mind that the
knapsack elements ai are infinite!
FOUO) Aha, you think -- a storage problem: where shall
I retain these ai? Never fear, that's not necessary. Instead,
the sender will generate and transmit the ai bit-by-bit! That
is, in some (unspecified, but clearly essential for security) way the sender
generates the n streams (starting, of course with the least significant bits)
and with every bit of cipher must transmit an additional n bits of the knapsack
components. Talk about data expansion!
FOUO) Now Merkle makes a swipe at establishing NP-completeness
of his algorithm. But it's hopeless: complexity theory just cannot cope with
components of infinite length. Furthermore he admits that his "proof" fails
for another reason. The NP-completeness of the knapsack problem deals with
the following decision problem: given the set of knapsack weights (the ai)
and an integer B, determine whether or not there is an n-long binary vector
x = (x1, x2, ... ,xn) such that
FOUO) The problem we're faced with as cryptanalysts is,
instead, the corresponding search problem: given B, and knowing that an x
exists, find x. Merkle says, "From a cryptographer's point of view there
is not much difference between these two problems." It is just such difficulties
that make contemporary complexity theory generally inapplicable to cryptology.
FOUO) Knapsacks are not appropriate vehicles for solving
the authentication problem, in which secrecy of the contents is not an issue
but the recipient requires assurance of the source of the message. Typically
the message m is formed and then the sender A uses some function F (which
is publicly known) to "sign" the message. One condition is that A (only)
knows the inverse function F-1: Given m, only A can find x such
that F(x) = m. Now A calculates the signature x and transmits x only, along
with a statement that it is he who has sent the message. Everyone now has
the facility to read the message F(x) = m. No one knows F-1 so
no one else could have found the transmitted x.
(U) Because knapsacks typically have a very small image space, inverses of
arbitrary elements m are most unlikely to exist. That is, for a randomly
chosen m, it is very unlikely that, a binary vector x can be found such that
so knapsack systems are not useful for authentication.
(U) Recognizing this deficiency, Merkle has written a chapter entitled, "A
Certifled Digital Signature." His design is "tree authentication," which
is expensive, slow, and allows for the selection of only a small number of
messages. Tree authentication appears again in the longest chapter, on "protocols
for public-key cryptosystems," to no better effect. This chapter is not without
merit: it alerts the unwary to the many pitfalls of designing secure protocols.
S CCO) That Merkle fails to construct a satisfactory protocol
is no disgrace: many skilled researchers have had no more success. The best
work I've seen on this thorny problem has been done by [phrase redacted]
anyone familiar with their ideas will find Merkle's discussion very pale.
But I particularly liked one remark of his: in the doubtful world of thrust
and counterthrust, of masquerade and tampering, the message ,"My secret key
has been compromised" should always be accepted as a valid message.
(U) No book on cryptology is complete without mention of the Data Encryption
Standard. Merkle has a novel approach to DES. He shows how to simulate a
k-input m-output Sbox by a knapsack with 2k + k + m components. By assembling
components he is now able to argue that a general algorithm which could solve
a 10000-component knapsack could be used to solve DES. In a later chapter
he discusses "the security of multiple encryption" of DES.
FOUO) Our criticism of this book is not intended as a criticism
of the author. It would have been surprising indeed if such a young and
inexperienced student had made an important contribution. He has not.
Cryptography remains a fascinating subject, yes, but also a decidedly difficult