`
`
`
`Case 8:11-cv-01681-DOC-JPR Document 71-2 Filed 07/03/12 Page 1 of 76 Page ID
` #:673
`
`
`
`1
`
`2
`
`3
`
`4
`
`5
`
`6
`
`7
`
`8
`
`9
`
`10
`
`11
`
`12
`
`13
`
`14
`
`15
`
`16
`
`17
`
`18
`
`19
`
`20
`
`21
`
`KARIN G. PAGNANELLI (SBN 174763)
`kgp@msk.com
`MITCHELL SILBERBERG & KNUPP LLP
`11377 West Olympic Boulevard
`Los Angeles, California 90064-1683
`Telephone: (310) 312-2000
`Facsimile:
`(310) 312-3100
`
`STEPHEN J. JONCUS (pro hac vice)
`stephen.joncus@klarquist.com
`SALUMEH R. LOESCH (pro hac vice)
`salumeh.loesch@klarquist.com
`JOHN D. VANDENBERG (pro hac vice)
`john.vandenberg@klarquist.com
`KLARQUIST SPARKMAN, LLP
`121 SW Salmon Street, Suite 1600
`Portland, Oregon 97204
`Telephone: (503) 595-5300
`
`Attorneys for Defendants
`Microsoft Corporation, Hewlett-Packard Company,
`Dell Inc., and Acer America Corporation
`
`UNITED STATES DISTRICT COURT
`CENTRAL DISTRICT OF CALIFORNIA
`SOUTHERN DIVISION
`
`PROXYCONN, INC.,
`
`Plaintiff,
`
`v.
`
`MICROSOFT CORPORATION et al.,
`
`Defendants.
`
`
`
`
`
`
`
`
`
`
`
`
`CASE NO. SA CV11-1681 DOC (ANx)
`[Consolidated With Case Nos. SA CV11-
`1682 DOC (ANx), SA CV11-1683 DOC
`(ANx), and SA CV11-1684 DOC (ANx)]
`DECLARATION OF DARRELL D. E.
`LONG IN SUPPORT OF DEFENDANTS
`MICROSOFT CORPORATION,
`HEWLETT-PACKARD COMPANY,
`DELL INC., AND ACER AMERICA
`CORPORATION’S MOTION FOR
`SUMMARY JUDGMENT OF
`
`INVALIDITY
`
`8:30 a.m.
`Time:
`August 20, 2012
`Date:
`9D
`Ctrm:
`Before: Hon. David O. Carter
`
`MICROSOFT
`
`EXHIBIT 1014
`
`
`
`
`
`
`
`
`DECLARATION OF DARRELL D. E. LONG
`IN SUPPORT OF DEFENDANTS’ MOTION FOR SUMMARY JUDGMENT
`
`Page 1 of 76
`
`

`

`
`Case 8:11-cv-01681-DOC-JPR Document 71-2 Filed 07/03/12 Page 2 of 76 Page ID
` #:674
`
`
`
`
`
`1
`
`2
`
`3
`
`4
`
`Declaration of Professor Darrell D. E. Long
`Regarding U.S. Patent No. 6,757,717
`
`
`I.
`
`FIELD OF THE INVENTION
`
`The field of the purported inventions of this patent is comprised of the areas
`
`5
`
`of distributed data storage systems and networking, coding theory including error
`
`6
`
`detection and correction codes, and cryptographic hash functions commonly called
`
`7
`
`message digest functions. These were all mature fields in 1999.
`
`8
`
`9
`
`II. LEVEL OF SKILL IN THE ART IN 1999
`
`A person of ordinary skill in this art in 1999 would hold a B.S. degree in
`
`10
`
`computer science and would have as part of his study courses in operating systems,
`
`11
`
`networking, data compression and computer security. In addition he would have
`
`12
`
`several years of practical experience working in operating systems, in particular
`
`13
`
`the data storage subsystem.
`
`14
`
`A person of ordinary skill in the art would understand the storage subsystem
`
`15
`
`of computer operating systems. This topic is covered briefly in most undergraduate
`
`16
`
`operating systems courses, but few require the student to examine actual source
`
`17
`
`code. As a result, actual experience in working with this operating system
`
`18
`
`subsystem would normally occur after several years of experience working for a
`
`19
`
`company with a focus on systems software.
`
`20
`
`21
`
`
`
`1
`DECLARATION OF DARRELL D. E. LONG
`IN SUPPORT OF DEFENDANTS’ MOTION FOR SUMMARY JUDGMENT
`
`Page 2 of 76
`
`

`

`
`Case 8:11-cv-01681-DOC-JPR Document 71-2 Filed 07/03/12 Page 3 of 76 Page ID
` #:675
`
`
`
`
`
`1
`
`Alternatively, a person would develop the level of ordinary skill in the art in
`
`2
`
`1999 by obtaining an M.S. in computer science and by writing his or her thesis in
`
`3
`
`an area related to data storage and/or computer security.
`
`4
`
`A person of ordinary skill in the art would understand network protocols.
`
`5
`
`This was normally part of undergraduate programs in computer science in 1999. A
`
`6
`
`person of ordinary skill in the art would also understand coding theory, in
`
`7
`
`particular error detection and correction codes, as well as cryptographic hash
`
`8
`
`functions and message digest functions. Introduction to basic hash functions is a
`
`9
`
`normal part of most undergraduate curricula, but coding theory is normally part of
`
`10
`
`specialized courses (although it is commonly part of electrical engineering
`
`11
`
`programs), and cryptographic hash functions would normally be taught only in
`
`12
`
`courses in computer security.
`
`13
`
`I have first-hand experience teaching and working with such persons of
`
`14
`
`ordinary skill in the art. For example, I have taught students having about that level
`
`15
`
`of skill in this art since at least as early as 1990.
`
`16
`
`III. QUALIFICATIONS
`
`17
`
`I am a Professor of Computer Science and have served as Associate Dean
`
`18
`
`for Research and Graduate Studies in the Jack Baskin School of Engineering at the
`
`19
`
`University of California at Santa Cruz. I hold the Kumar Malavalli Endowed Chair
`
`20
`
`of Storage Systems Research and I am the Director of the Storage Systems
`
`21
`
`Research Center, an internationally recognized center of excellence in data storage.
`
`2
`DECLARATION OF DARRELL D. E. LONG
`IN SUPPORT OF DEFENDANTS’ MOTION FOR SUMMARY JUDGMENT
`
`Page 3 of 76
`
`

`

`
`Case 8:11-cv-01681-DOC-JPR Document 71-2 Filed 07/03/12 Page 4 of 76 Page ID
` #:676
`
`
`
`
`
`1
`
`I am also the Director of the Working-group on Applied Security and Privacy
`
`2
`
`(WASP), the laboratory at the University of California at Santa Cruz that studies
`
`3
`
`computer security. I teach graduate and undergraduate courses in computer
`
`4
`
`security, operating systems, and have taught courses in networking and distributed
`
`5
`
`systems. I received my B.S. degree in Computer Science from San Diego State
`
`6
`
`University, and my M.S. and Ph.D. from the University of California, San Diego. I
`
`7
`
`am a Fellow of the Institute of Electrical and Electronics Engineers and of the
`
`8
`
`American Association for the Advancement of Science. My research interests
`
`9
`
`include data storage systems, operating systems, computer security, distributed
`
`10
`
`systems and networking. My qualifications are further described in my Curriculum
`
`11
`
`Vitae attached as Exhibit A.
`
`12
`
`
`
`I have published numerous papers including in the ACM Transactions on
`
`13
`
`Storage, and various IEEE journals, and I am the co-author of two books. These
`
`14
`
`publications are listed in Exhibit A. I am the founder of the premier conference in
`
`15
`
`the data storage field known as the Symposium on File Storage Technologies
`
`16
`
`(“FAST”). I have participated in organizing numerous academic conferences
`
`17
`
`including:
`
`18
`
`19
`
`20
`
`21
`
`
`
`2012:
`
`Steering Committee: Petascale Data Storage Workshop (PDSW),
`
`Symposium on Modeling, Analysis and Simulation of Computer and
`
`3
`DECLARATION OF DARRELL D. E. LONG
`IN SUPPORT OF DEFENDANTS’ MOTION FOR SUMMARY JUDGMENT
`
`Page 4 of 76
`
`

`

`
`Case 8:11-cv-01681-DOC-JPR Document 71-2 Filed 07/03/12 Page 5 of 76 Page ID
` #:677
`
`
`
`
`
`1
`
`2
`
`3
`
`4
`
`5
`
`6
`
`7
`
`8
`
`9
`
`10
`
`11
`
`12
`
`13
`
`14
`
`15
`
`16
`
`17
`
`18
`
`19
`
`20
`
`21
`
`Telecommunication Systems (MASCOTS), Symposium on File and
`
`Storage Systems Technology (FAST).
`
`Program Committee: Symposium on File and Storage Systems
`
`Technology (FAST).
`
`2011:
`
`Steering Committee: Petascale Data Storage Workshop (PDSW),
`
`Symposium on Modeling, Analysis and Simulation of Computer and
`
`Telecommunication Systems (MASCOTS), Symposium on File and
`
`Storage Systems Technology (FAST).
`
`Program Committee: Symposium on Modeling, Analysis and
`
`Simulation of Computer and Telecommunication Systems
`
`(MASCOTS).
`
`2010:
`
`Program Chair: Symposium on Modeling, Analysis and Simulation of
`
`Computer and Telecommunication Systems (MASCOTS).
`
`Steering Committee: Petascale Data Storage Workshop (PDSW),
`
`Symposium on Modeling, Analysis and Simulation of Computer and
`
`Telecommunication Systems (MASCOTS), Symposium on File and
`
`Storage Systems Technology (FAST).
`
`
`
`4
`DECLARATION OF DARRELL D. E. LONG
`IN SUPPORT OF DEFENDANTS’ MOTION FOR SUMMARY JUDGMENT
`
`Page 5 of 76
`
`

`

`
`Case 8:11-cv-01681-DOC-JPR Document 71-2 Filed 07/03/12 Page 6 of 76 Page ID
` #:678
`
`
`
`
`
`1
`
`2
`
`3
`
`4
`
`5
`
`6
`
`7
`
`8
`
`9
`
`10
`
`11
`
`12
`
`13
`
`2009:
`
`Program Committee: International Workshop on Software Support
`
`for Portable Storage (IWSSPS), Inaugural International Conference on
`
`Virtualization and Cloud Computing, Symposium on Modeling,
`
`Analysis and Simulation of Computer and Telecommunication
`
`Systems (MASCOTS), Petascale Data Storage Workshop (PDSW).
`
`Program Chair: Web Information Systems Engineering (WISE).
`
`General Chair: Symposium on Applications and the Internet
`
`(SAINT).
`
`Steering Committee: Symposium on Modeling, Analysis and
`
`Simulation of Computer and Telecommunication Systems
`
`(MASCOTS), Symposium on File and Storage Systems Technology
`
`(FAST).
`
`14
`
`I have also consulted for industry in the area of storage systems including for
`
`15
`
`Hewlett-Packard Laboratories and IBM. I have also been a consultant to the U.S.
`
`16
`
`Department of Defense including the Army, the Chief of Naval Research, and the
`
`17
`
`Defense Intelligence Agency, as well as the Department of Energy and the
`
`18
`
`National Nuclear Security Administration.
`
`19
`
`
`
`Within the last four years I have testified in the cases listed in Ex. A.
`
`20
`
`21
`
`
`
`5
`DECLARATION OF DARRELL D. E. LONG
`IN SUPPORT OF DEFENDANTS’ MOTION FOR SUMMARY JUDGMENT
`
`Page 6 of 76
`
`

`

`
`Case 8:11-cv-01681-DOC-JPR Document 71-2 Filed 07/03/12 Page 7 of 76 Page ID
` #:679
`
`
`
`
`
`1
`
`2
`
`IV. COMPENSATION
`
`My compensation rate for this case is $500/hour for consulting and
`
`3
`
`$600/hour for testimony in deposition or trial, plus reimbursement for reasonably
`
`4
`
`incurred expenses. I have no interest in the outcome of this case.
`
`5
`
`6
`
`V. ANALYSIS
`
`I have read U.S. Patent No. 6,757,717. I also have read and considered an
`
`7
`
`“Amendment” dated July 9, 2002 related to this patent. (Exhibit B). The patent
`
`8
`
`concerns technology within my areas of expertise. I have considered the patent’s
`
`9
`
`disclosures from the perspective of a person of ordinary skill in the art in 1999.
`
`10
`
`From that perspective, as well as from the perspective of an expert in this field, the
`
`11
`
`patent is internally inconsistent and unclear. Below I explain this conclusion and
`
`12
`
`my bases for this conclusion.
`
`13
`
`14
`
`A. Hash Function And Message Digest
`
`A function is a computation that takes a value, say x, and maps it onto
`
`15
`
`another value y. The value x is chosen from a set called the domain and y is chosen
`
`16
`
`from a set called the range. A function may be one-to-one where for each y there is
`
`17
`
`exactly one x, or many-to-one where many x1, x2, …, may all map to the same y. A
`
`18
`
`hash function f is one that takes a key k, and maps it to exactly one of at most n
`
`19
`
`20
`
`21
`
`values. That is, Ͳ ൑ ݂ሺ݇ሻ ൏ ݊.
`
`A message digest H is a form of one-way hash function that takes a message
`
`M of arbitrary length and produces a hash value of a fixed number of bits (“bit”
`
`6
`DECLARATION OF DARRELL D. E. LONG
`IN SUPPORT OF DEFENDANTS’ MOTION FOR SUMMARY JUDGMENT
`
`Page 7 of 76
`
`

`

`
`Case 8:11-cv-01681-DOC-JPR Document 71-2 Filed 07/03/12 Page 8 of 76 Page ID
` #:680
`
`
`
`
`
`1
`
`2
`
`3
`
`4
`
`5
`
`6
`
`7
`
`8
`
`9
`
`10
`
`11
`
`12
`
`13
`
`14
`
`stands for binary digit and has a value of 0 or 1.) If ܪሺܯሻ ൌ ݄ then ݄ ൏ ʹ௠
`
`where m is the length in bits of the hash value of this hash function. Widely used
`
`message digest functions in 1999 included MD5, which produces 128 bits and
`
`SHA-1 that produces 160 bits. CRC-32 and CRC-64 can be thought of as
`
`particularly small message digest functions, although their original purpose was
`
`error detection and, as discussed below, they are not collision resistant.
`
`B. Mathematical Properties Of A Message Digest
`
`Just as human fingerprints are expected to be unique to individuals, the
`
`message digest of a given message (e.g., a string or block of data) ideally is unique
`
`to that message. The ability of a hash function to produce a unique fingerprint of
`
`the message depends in part on the number of bits that the message digest produces
`
`and on the number of messages that may be hashed. If the number of messages is
`
`sufficiently large, and the number of bits produced by the message digest function
`
`insufficiently low, then a collision will occur and multiple messages will produce
`
`15
`
`the same hash value.
`
`16
`
`17
`
`Message digest functions have the following additional properties that make
`
`them one-way and thus desirable for a designed purpose (see Bruce Schneier,
`
`18
`
`Applied Cryptography (2nd ed. 1996) at p. 429 (Exhibit C)):
`
`19
`
`20
`
`21
`
`
`
`1. Given a message M, it is easy to compute h. The computing of a message
`
`digest must be efficient, since they are typically applied to large amounts
`
`of data.
`
`7
`DECLARATION OF DARRELL D. E. LONG
`IN SUPPORT OF DEFENDANTS’ MOTION FOR SUMMARY JUDGMENT
`
`Page 8 of 76
`
`

`

`
`Case 8:11-cv-01681-DOC-JPR Document 71-2 Filed 07/03/12 Page 9 of 76 Page ID
` #:681
`
`
`
`
`
`1
`
`2
`
`3
`
`4
`
`5
`
`6
`
`7
`
`8
`
`9
`
`10
`
`11
`
`12
`
`13
`
`14
`
`15
`
`16
`
`17
`
`18
`
`19
`
`20
`
`21
`
`2. Given h, it is hard to compute M such that H(M) = h. It must be
`
`computationally hard, that is nothing short of exhaustive search, to find
`
`the original message M given h. In fact, since M contains more bits than
`
`h, information is lost and so there are many messages ܯԢ that hash to the
`
`same h.
`
`3. Given M, it is hard to find another ܯԢ such that ܪሺܯሻ ൌ ܪሺܯᇱሻ. Even
`though there are many ܯԢ that hash to the same h, m (the fixed length in
`
`bits of the hash value) should be sufficiently large that it is difficult to
`
`find such an ܯԢ and they are extraordinarily unlikely to occur
`
`accidentally.
`
`One of the uses of a message digest function is to determine if any bits in a
`
`message M have been changed. For a well-designed message digest, even changing
`
`a single bit will result in a vastly different value being returned by the message
`
`digest computation. It is not the case that two messages that are close (e.g., a small
`
`Hamming or Levenshtein (also called edit), distance apart) will have message
`
`digests that are also close. While a poorly designed hash function may result in
`
`clustering in the range, there were no known message digest functions in 1999
`
`where two messages that are close in terms of edit distance will result in hash
`
`values that are close either numerically or in terms of Hamming distance. As a
`
`result, none of CRC-32, CRC-64, MD4, MD5, or any of the SHA family can be
`
`used to determine similarity between two messages. A well-designed hash function
`
`8
`DECLARATION OF DARRELL D. E. LONG
`IN SUPPORT OF DEFENDANTS’ MOTION FOR SUMMARY JUDGMENT
`
`Page 9 of 76
`
`

`

`
`Case 8:11-cv-01681-DOC-JPR Document 71-2 Filed 07/03/12 Page 10 of 76 Page ID
` #:682
`
`
`
`
`
`1
`
`2
`
`3
`
`4
`
`5
`
`6
`
`7
`
`8
`
`9
`
`10
`
`11
`
`12
`
`13
`
`14
`
`15
`
`16
`
`17
`
`18
`
`19
`
`20
`
`21
`
`is flat, that is all values Ͳ ൑ ݄ ൏ ݊ are equally likely to occur, regardless of the
`
`distribution of input messages.
`
`C. Collision Resistance
`
`One of the properties that typically we desire in a message digest function is
`
`called collision resistance. A message digest function is collision resistant if two
`
`unrelated messages are unlikely to result in the same hash value. A requirement
`
`that the hash function produces a nearly flat distribution is a requirement, but it
`
`also requires that the function produce a relatively large number of bits. By modern
`
`standards, even MD5’s 128 bits are considered insufficient to be deemed collision
`
`resistant. The 32 bits of CRC-32 would not have been considered sufficient for
`
`collision resistance in 1999 for practical data storage systems, nor would the 64
`
`bits of CRC-64 except for the smallest of data storage systems.
`
`D. Calculating Collision Probabilities
`
`Hash collisions often are the result of a well-known problem in probability
`
`theory known as the birthday problem, and cryptographic attacks on these
`
`functions typically take the form of birthday attacks. The birthday problem is:
`
`Given a room full of people, how many people need to be at the party before the
`
`likelihood of two people sharing a birthday is larger than ½? Assuming that
`
`birthdays are evenly spread over the course of a year, the answer is surprisingly
`
`small: it is only about 23. This applies to hash collisions as well as birthdays, and
`
`we ask the question: How many messages must be hashed before the likelihood of
`
`9
`DECLARATION OF DARRELL D. E. LONG
`Page 10 of 76
`IN SUPPORT OF DEFENDANTS’ MOTION FOR SUMMARY JUDGMENT
`
`

`

`
`Case 8:11-cv-01681-DOC-JPR Document 71-2 Filed 07/03/12 Page 11 of 76 Page ID
` #:683
`
`
`
`
`
`1
`
`a collision is greater than some value. The next question is how high of a chance of
`
`2
`
`collision is considered acceptable? A typical acceptable value might be 1 in 1015 (1
`
`3
`
`in 1,000,000,000,000,000) for a small data storage system, while for a large data
`
`4
`
`center the value would be much lower (since there are many more files that might
`
`5
`
`collide). You may ask where 1 in 1015 comes from, and it is related to the
`
`6
`
`undetected error rate in modern hard drives and reflects the capability of a typical
`
`7
`
`error correction code that they employ such as Reed-Solomon.
`
`8
`
`9
`
`10
`
`11
`
`12
`
`13
`
`14
`
`15
`
`16
`
`17
`
`18
`
`19
`
`20
`
`21
`
`The expected number of messages before a collision occurs can be
`
`approximated using the formula ݊ ൌ ටʹ ݀ Ž ଵ
`ଵି௣ where Ě is the range of the hash
`
`function, and p is the desired probability. For example, if we let Ě = 365 and Ɖ = ½,
`
`then we get Ŷ = 22.4944. If we consider CRC-32, and assume that the hash values
`
`produced are uniformly random then ݀ ൌ ʹଷଶ and if Ɖ = ½, then we get Ŷ = 77,162.
`
`In fact, CRC-32 is not uniformly random and so the value of n will be significantly
`
`lower. In other words, we can expect to hash fewer than 77,162 random and
`
`different messages with a CRC-32 function, in a benign environment, to have a 50-
`
`50 chance that two different messages will produce the same hash value. This is a
`
`very small number of messages given that the average personal computer may
`
`have more than a million files. If we choose ݌ ൌ ͳͲିଵହ as a desired collision
`
`probability then CRC-32 cannot meet the desired collision resistance for even two
`
`files, and CRC-64 can reach that risk of collision after only 203 files. Given the
`
`
`
`10
`DECLARATION OF DARRELL D. E. LONG
`Page 11 of 76
`IN SUPPORT OF DEFENDANTS’ MOTION FOR SUMMARY JUDGMENT
`
`

`

`
`Case 8:11-cv-01681-DOC-JPR Document 71-2 Filed 07/03/12 Page 12 of 76 Page ID
` #:684
`
`
`
`
`
`1
`
`same collision probability goal then MD5 can expect that risk of collision after
`
`2
`
`3
`
`4
`
`5
`
`6
`
`7
`
`8
`
`9
`
`10
`
`11
`
`12
`
`13
`
`14
`
`15
`
`16
`
`17
`
`18
`
`19
`
`20
`
`21
`
`ͺǤ͸ͻʹͶൈͳͲଵଵfiles. While this is quite a large number of files today, given that a
`
`cloud storage site has a trillion files today, it will not be in just a few years. The
`
`acceptable error probability will also decrease as the density of hard disks
`
`increases, rendering even MD5 useless in the near future.
`
`E. Message Digests Are Designed To Be Collision Resistant
`
`Message digest functions are designed to be collision resistant. The CRC
`
`family of functions was not designed as a message digest function, and so collision
`
`resistance was not a design goal. CRC functions are designed to detect burst errors
`
`in a sequence of data symbols (typically sequences of bits).
`
`MD5 is one of a family of message digest functions that were designed by
`
`Ronald Rivest. Prof. Rivest is one of the most renowned cryptographers, and he
`
`designed these functions to be collision resistant both to accidental and a
`
`purposeful attack. Even so, MD5 has been shown (as have others of the MD
`
`family) to be vulnerable to engineered attacks. The SHA (Secure Hash Algorithm)
`
`family of message digest functions is published by the National Institutes of
`
`Science & Technology as U.S. Federal Information Processing Standards (FIPS).
`
`The SHA family continues to evolve as weaknesses are demonstrated.
`
`
`
`11
`DECLARATION OF DARRELL D. E. LONG
`Page 12 of 76
`IN SUPPORT OF DEFENDANTS’ MOTION FOR SUMMARY JUDGMENT
`
`

`

`
`Case 8:11-cv-01681-DOC-JPR Document 71-2 Filed 07/03/12 Page 13 of 76 Page ID
` #:685
`
`
`
`
`
`1
`
`2
`
`3
`
`4
`
`5
`
`6
`
`7
`
`8
`
`9
`
`10
`
`11
`
`12
`
`13
`
`14
`
`15
`
`16
`
`17
`
`18
`
`19
`
`20
`
`21
`
`F.
`
`The Patent Says That Its “Digital Digest” Has
`Properties That No Message Digest Known In 1999 Had
`
`By their very design, the value of a hash function for any two inputs, even
`
`two inputs that are highly similar, will be unrelated. As a result, hash functions are
`
`useful for determining the identity of a message but not for detecting similarity.
`
`For example, message digest functions are commonly used to provide digital
`
`signatures. A digital signature of a message or document is commonly
`
`implemented by computing a message digest of a message or document coupled
`
`with a cryptographic key. If even a single bit of the message is altered, then the
`
`message digest will be completely different. The key is typically held by an
`
`independent escrow entity so that, for example, a court could verify the
`
`authenticity of a message or document.
`
`A person of ordinary skill in the art in 1999 would have known that none of
`
`CRC-16, CRC-32, CRC-64, MD5, or any error detection code or message digest
`
`function then existing could be used to determine similarity of two messages.
`
`Therefore, stating in 1999 that two substantially equal outputs of a particular
`
`function indicate that the respective inputs also are substantially equal, would rule
`
`out all message digest functions then known.
`
`The patent states that its “digital digest” could be computed using CRC or
`
`MD5. The patent also states that its “digital digest” could be used to detect
`
`similarity, e.g., in the following passages:
`
`
`
`12
`DECLARATION OF DARRELL D. E. LONG
`Page 13 of 76
`IN SUPPORT OF DEFENDANTS’ MOTION FOR SUMMARY JUDGMENT
`
`

`

`
`Case 8:11-cv-01681-DOC-JPR Document 71-2 Filed 07/03/12 Page 14 of 76 Page ID
` #:686
`
`
`
`
`
`1
`
`2
`
`3
`
`4
`
`5
`
`6
`
`7
`
`8
`
`9
`
`10
`
`11
`
`12
`
`13
`
`14
`
`said method comprising the steps of intercepting a message containing
`a digital digest transmitted from said sender/computer to said
`receiver/computer, and transmitting data with a digital digest
`substantially identical to the digital digest received from said
`sender/computer to said receiver/computer. (Patent at col. 4, lines 46-
`51);
`
`intercepting a message containing an indication signal other than a
`positive indication signal transmitted from said receiver/computer to
`said sender/computer in response to said message containing a digital
`digest, and transmitting data with a digital digest substantially
`identical to the digital digest received from said sender/computer to
`said receiver/computer. (Patent at col. 4, lines 61-67);
`
`server preparing a response to said request, searching for data with a
`digital digest substantially identical to one of the digital digests
`received in said request, and producing the difference between said
`response and the uncovered data. (Patent at col. 5, lines 7-11);
`
`If it finds data with a digital digest substantially equal to one of the
`auxiliary digests, it issues a partial indication signal to the
`sender/computer, with a reference to the digest. . . . Upon receiving a
`partial indication signal, the sender/computer transmits the difference
`between the digital digest of the data required to be sent and that of
`the data whose digital digest was found by the receiver/computer.
`(Patent at col. 8, lines 28-37).
`
`These two statements are at odds with each other: the purpose of a message
`
`15
`
`digest is to determine identity or lack of identity, not similarity or lack of
`
`16
`
`similarity. Two messages will result in vastly different message digest values even
`
`17
`
`if the messages differ by only a single bit; while a function that determines
`
`18
`
`similarity would produce a value with numerical values that differ only slightly if
`
`19
`
`20
`
`21
`
`the messages are similar. In 1999 no known message digest function existed for
`
`computing similarity, and certainly none of the CRC or MD families of functions
`
`have this property (and in fact were designed with the opposite goal in mind). In
`
`13
`DECLARATION OF DARRELL D. E. LONG
`Page 14 of 76
`IN SUPPORT OF DEFENDANTS’ MOTION FOR SUMMARY JUDGMENT
`
`

`

`
`Case 8:11-cv-01681-DOC-JPR Document 71-2 Filed 07/03/12 Page 15 of 76 Page ID
` #:687
`
`
`
`
`
`1
`
`other words, the passages quoted above rule out all CRC and MD functions as
`
`2
`
`computing the patent’s “digital digest.”
`
`3
`
`The patent fails to identify any function that can be used to compute a
`
`4
`
`similarity check among documents (or messages, or blocks). In fact, no such
`
`5
`
`function useful as both an identity check and a similarity check was known in the
`
`6
`
`art. Therefore, if one gives credence to the above-quoted paragraphs and takes the
`
`7
`
`patent at its word that its “digital digest” possessed this property of detecting
`
`8
`
`similarity between two messages or files, then the patent does not identify any
`
`9
`
`function capable of computing such a “digital digest” and a person of ordinary skill
`
`10
`
`in the art in 1999 would not have known how to compute such a “digital digest.”
`
`11
`
`12
`
`G. The Patent Does Not Define “Low” Probability Of Collisions
`
`The patent defines “digital digest” to have a “low probability” of collisions
`
`13
`
`but does not define the term: “The term ‘digital digest’ as used herein refers to a
`
`14
`
`fixed-size binary value calculated from arbitrary-size binary data in such a way
`
`15
`
`that it depends only on the contents of the data and the low probability that two
`
`16
`
`different data or objects have the same digital digest.” (Patent at col. 2, lines 9-13).
`
`17
`
`Especially given that the patent also states that these same functions could be used
`
`18
`
`for similarity detection, there was no way for a person skilled in the art in 1999 to
`
`19
`
`understand what “low probability” might mean. As discussed in the introduction of
`
`20
`
`message digest functions, a well-designed message digest function (like any hash
`
`21
`
`function) is to have a flat distribution and any pair of inputs, even if close in edit
`
`14
`DECLARATION OF DARRELL D. E. LONG
`Page 15 of 76
`IN SUPPORT OF DEFENDANTS’ MOTION FOR SUMMARY JUDGMENT
`
`

`

`
`Case 8:11-cv-01681-DOC-JPR Document 71-2 Filed 07/03/12 Page 16 of 76 Page ID
` #:688
`
`
`
`
`
`1
`
`distance, will result in vastly different hash values. (It should be noted that this
`
`2
`
`flat-distribution property was not a design goal for the CRC family, which was
`
`3
`
`originally designed to detect burst errors.) The real question is not whether two
`
`4
`
`arbitrary inputs result in a collision, but in the context of the patent whether there
`
`5
`
`might be any pair that results in a collision. For example, on my personal computer
`
`6
`
`there are 1,001,926 files resulting in 114,246,884 data blocks in use, which results
`
`7
`
`8
`
`9
`
`10
`
`11
`
`12
`
`in ͸ǡͷʹ͸ǡͳ͹ͷǡͳͻͶǡ͹͵ͳǡʹͺ͸ possible pairs of blocks. Even using MD5, this results
`
`in a non-negligible probability of collision.
`
`The patent does not define the term “low” probability and there is no precise
`
`understood meaning of this word in the field. When one states that an event occurs
`
`with low probability, one is making a subjective and imprecise statement that is
`
`highly dependent on context. According to the National Weather Service, the odds
`
`13
`
`of being struck by lightning in one’s lifetime are approximately 1 in 105, which we
`
`14
`
`15
`
`16
`
`17
`
`18
`
`19
`
`20
`
`21
`
`find to be acceptably low. But we would not accept this as the probability of losing
`
`or corrupting one of our data files (on my personal computer this would virtually
`
`guarantee multiple instances of data loss). It is very simple to define
`
`mathematically what is meant by low probability, but the patent fails to do so.
`
`When the patent discusses “low probability” it fails to describe whether this
`
`is in a benign or an adversarial environment. Such environments are vastly
`
`different: in a benign environment any collisions would be purely incidental, while
`
`an adversarial environment has an adversary who is actively trying to engineer a
`
`15
`DECLARATION OF DARRELL D. E. LONG
`Page 16 of 76
`IN SUPPORT OF DEFENDANTS’ MOTION FOR SUMMARY JUDGMENT
`
`

`

`
`Case 8:11-cv-01681-DOC-JPR Document 71-2 Filed 07/03/12 Page 17 of 76 Page ID
` #:689
`
`
`
`
`
`1
`
`collision. For many message digest functions it is known how to engineer
`
`2
`
`collisions, which has resulted in the deprecation or decertification of those
`
`3
`
`functions for use.
`
`4
`
`The patent gives as a stated goal the integrity of the data, but then
`
`5
`
`inconsistently states that CRC can be used to calculate a “digital digest.” The linear
`
`6
`
`property of CRC computation results in the ability of an attacker to make additions
`
`7
`
`and deletions from a message while leaving the computed CRC value unchanged.
`
`8
`
`For example, no CRC polynomial can detect errors consisting of additional or
`
`9
`
`missing leading zeroes. Therefore, CRC functions do not provide data integrity in
`
`10
`
`an adversarial environment. An adversary could easily engineer collisions if a CRC
`
`11
`
`function were used.
`
`12
`
`VI. CONCLUSION
`
`13
`
`For at least the reasons explained above, the patent is internally inconsistent
`
`14
`
`and unclear on the meaning and scope of its “digital digest” and how to calculate
`
`15
`
`its “digital digest.” This conclusion is true reading the patent from the perspective
`
`16
`
`of a person of ordinary skill in the art in 1999 as well as from the perspective of an
`
`17
`
`expert in this field either then or today. The Amendment (Exhibit B) does not cure
`
`18
`
`any of the above-described problems with the patent.
`
`19
`
`
`
`20
`
`21
`
`
`
`
`
`16
`DECLARATION OF DARRELL D. E. LONG
`Page 17 of 76
`IN SUPPORT OF DEFENDANTS’ MOTION FOR SUMMARY JUDGMENT
`
`

`

`Case 8:11-cv-01681-DOC-JPR Document 71-2 Filed 07/03/12 Page 18 of 76 Page ID
` #:690
`
`Page 18 of 76
`
`

`

`Case 8:11-cv-01681-DOC-JPR Document 71-2 Filed 07/03/12 Page 19 of 76 Page ID
` #:691
`
`
`
`
`
`EXHIBIT A
`
`Page 19 of 76
`
`

`

`Case 8:11-cv-01681-DOC-JPR Document 71-2 Filed 07/03/12 Page 20 of 76 Page ID
` #:692
`
`Cumulative Bio-Bibliography
`University of California, Santa Cruz
`April 17, 2012
`DARRELL DON EARL LONG
`Professor, Computer Science
`Kumar Malavalli Endowed Chair in Storage Systems Research
`
`EMPLOYMENT HISTORY
`
`2005–
`
`Kumar Malavalli Endowed Chair in Storage Systems Research
`
`2004–10
`
`Associate Dean for Research and Graduate Studies, Jack Baskin School of Engineering,
`University of California, Santa Cruz
`
`2001–
`
`1999–
`
`Director, Storage Systems Research Center, University of California, Santa Cruz
`
`Professor, Computer Science, University of California, Santa Cruz
`
`1998–01
`
`Associate Dean, Jack Baskin School of Engineering, University of California, Santa Cruz
`
`1994–99
`
`Associate Professor, Computer Science, University of California, Santa Cruz
`
`1988–94
`
`Assistant Professor, Computer Science, University of California, Santa Cruz
`
`1986–88
`
`Research Assistant, Computer Science & Engineering, University of California, San Diego
`
`1985–87
`
`Teaching Associate, Computer Science & Engineering, University of California, San Diego
`
`1984–87
`
`Lecturer in Mathematics, Department of Mathematical Sciences, San Diego State University
`
`1981–84
`
`Systems Programmer, University Computer Center, San Diego State University
`
`VISITOR HISTORY
`
`2011 (Winter)
`
`Professeur Invité, Conservatoire National des Arts et Métiers
`
`2010 (February)
`
`Professeur Invité, Université Paris–Dauphine
`
`2009 (February)
`
`Professeur Invité, Université Paris–Dauphine
`
`2008 (February)
`
`Visiting Professor, University of Technology, Sydney
`
`2007 (Winter)
`
`Visiting Scholar, University of California, San Diego
`
`2007 (Winter)
`
`Visiting Scholar, Center for Communications Research
`
`EDUCATION
`
`Ph.D. 1988 University of California, San Diego, Computer Science
`
`M.S.
`
`1986 University of California, San Diego, Computer Science
`
`B.S.
`
`1984
`
`San Diego State University, Computer Science
`
`1
`
`Page 20 of 76
`
`

`

`Case 8:11-cv-01681-DOC-JPR Document 71-2 Filed 07/03/12 Page 21 of 76 Page ID
` #:693
`
`HONORS
`
`2011
`
`2010
`
`2008
`
`2006
`
`2005
`
`2003
`
`2002
`
`2001
`
`1997
`
`1996
`
`1995
`
`1994
`
`1993
`
`1992
`
`1991
`
`1989
`
`1988
`
`Chancellor’s Achievement Award for Diversity
`
`Professor ad Honorem de la Universidad Católica del Uruguay
`
`Fellow, American Association for the Advancement of S