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:

http://cryptome.org/ukpk-diffie.htm

http://cryptome.org/2013/03/cryptologs/cryptolog_103.pdf

NSA Cryptolog, August-September 1986, pp. 27-29.

SECRET

BOOK REVIEW

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 this tract.

(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 a₁,a₂, ... ,a_a of n (large) positive integers, known to everyone. The parameter n should be chosen large enough to prevent an exhaustive analysis of the 2ⁿ 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 2ⁿ 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 a_i are infinite!

(FOUO) Aha, you think -- a storage problem: where shall I retain these a_i? Never fear, that's not necessary. Instead, the sender will generate and transmit the a_i 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 a_i) and an integer B, determine whether or not there is an n-long binary vector x = (x₁, x₂, ... ,x_n) 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 one.