Patent Application

of

David Wallace Croft

for

Using Digests to Validate Unattributed Content
in an
Insecure Cache


BACKGROUND

Cross-Reference to Related Inventions

This application claims the benefit of Provisional Patent Application Serial Number 60/091,499, filed 1998-07-02.

Field of the Invention

This invention relates to content distribution and storage security.

Definition of Terms

A definition of the terms as used in the context of this invention specification.
Content

Any ordered sequence of bits of finite size as expressed in a tangible form. This includes electronic content such as computer files, data retrieved from a database, a fixed-length stream of bytes, etc.

Cache

A storage memory used to store content for later retrieval in which the content is not pre-installed. This includes non-volatile and volatile memories, such as disk drives and random access memory, respectively. The cache may be insecure in that unknown and untrusted identities may possess shared access to read from and write to the memory or that content from such entities is stored therein. A familiar example of a cache is an Internet browser cache.

Digest

A fixed-length ordered sequence of bits generated from a function that processes content of arbitrary size as its input. The necessary characteristic of the function is such that it is computationally infeasible to purposely create a non-identical content input that will generate the same digest. Examples of digest functions as herein defined and presently used within the encryption community include SHA-1 and MD5.

Validation

The act of ensuring that an identical copy of the desired content is available for retrieval from a cache. This can be achieved by either reliably detecting that a copy of the content already exists in the cache or by updating the cache with a new copy of the content.

Attributed

A descriptor for content for which the originator can be reliably and conclusively linked to the content in question. For example, it is nearly impossible to forge "digitally signed" electronic mail as it is attributed by digest and encryption methods.

Prior Art

Earlier methods of securely retrieving content from an insecure cache relied upon reliably identifying the originator and/or distributor of the content. As an example, previous methods to reuse an image file cached in the local storage area of an Internet browser relied upon identifying and comparing the original distributor of the content by the Internet domain name, or, more securely, by an encryption authentication technique. What this does not permit, however, is to be able to reuse cached content distributed from one source when referenced by another distribution source. To clarify, if one downloaded and cached a file from one web site, it would not be retrieved from the cache and used when visiting another web site.

While some commercial applications will allow for the cache retrieval of text, image, and audio files when the distributor in the current context is deemed to be identical to the one which was accessed earlier, i.e., when the content was first cached, they do not permit the reuse of cached software without authentication. This is due to the extraordinary security risk of executing cached software as opposed to media files that may have been changed while in the cache, changed at the distribution site since cached, or cached as associated with a distributor identifier which may have been originally spoofed, i.e., mimicked for deceptive purposes. For example, it is possible that software, such as a Java applet, may be retrieved and cached from a web site which an Internet browser user believes to be from a particular trusted entity but which is in reality not so because the Internet domain name or protocol address has been spoofed. The next time the user attempts to access the site and actually reaches the trusted entity, he might utilize software that was cached from the untrustworthy entity in a trusted fashion, possibly causing substantial harm.

As a result, the use of Java applet software code in most Internet browsers tends to be limited in that the code is not persistently cached to the hard drive between application sessions. This requires that the code be downloaded again with each new session even though the same code is reused on a frequent basis. This tends to limit the size of the code since download bandwidth is constrained and few users have the patience to wait for lengthy durations on a regular basis. The size constraint in turn tends to limit the feature set of such code. Although, browser manufacturers have taken steps in the past to pre-install feature-rich software libraries with their client browser application, such libraries tended to be specific to just that one proprietary browser thereby forcing software applet developers to either to commit to a particular proprietary browser platform or to make portable libraries available for download as needed with the aforementioned problem of lengthy download delays. Subsequently, there was an effort to standardize on a dominant feature-rich library which would be pre-installed or pre-installable on most major browser platforms, but this in turn dampens innovation in the development of such feature-rich libraries as a standard has been locked in.

To partially resolve issues such as these where it is desirable that code be securely cached and reused, encryption and digest methods are utilized to verify the originator of the content in question. These methods are structured such that it is extremely difficult to spoof the identity of the originator and such that the content cannot be modified by anyone other than the originator without detection. Thus, even if the browser has cached untrustworthy code from what appears to be identical distributors, the content, as "digitally signed" by the originator, will not be authenticated. These methods require that the originator who wishes to release attributed content register with a third-party who is responsible for maintaining and distributing the encrypted identities of originators, to predisseminate his secure identity to the clients prior to use of the software, or to ask the clients to take a leap of faith. This places an additional burden on the originator for the secure release of such software.

These methods do not allow for unattributed software components, i.e., those of origin that cannot be authenticated, to be securely used when retrieved from a cache and do not allow for content to be used when retrieved from a cache when distributed by different entities -- even though the content is exactly the same in all cases.

OBJECTS and ADVANTAGES

Accordingly, the objects and advantages of my invention are:

One of the primary goals of the invention is to allow the more innovative and useful components of software libraries, components which may have been distributed by a number of different sites and authored by a number of different entities, in whole or in part, as revised or in the original, to be become cached over time in a preponderance of client browsers. As caching methods tend to eliminate content which is least frequently used while allowing for novel components to be stored and preserved if reused, this form of software component propagation is more natural and evolutionary than pre-installation methods. One might expect that, over time, software which is useful and efficient by its implementation characteristics, such as reliability, speed, and size, as opposed to its origin and initial distribution characteristics, would become the dominant "pre-installed" software on the majority of client systems by virtue of it having been selected by developers and cached.

This intended effect does not apply to software content alone. It is conceivable that, with the widespread application of this invention, other content such as image, audio, and other multimedia files may become predominantly cached and thus "pre-installed" if frequently used and reused by a number of different distributors. This may promote the development of an innovative and continuously updated "body" of public domain and open source content which would drive new efficiencies in information distribution.

DESCRIPTION of DRAWINGS

Figure 1 provides a flowchart for the process of validating cache content using digests. It maps onto claim 1.

Figure 2 provides a flowchart of the preferred embodiment of the process of deciding whether a copy of content already exists in the cache.

Figure 3 provides a flowchart of the preferred embodiment for the process of storing a copy of content in the cache.

LIST of REFERENCE NUMERALS

Reference numbers as used in the drawings and in the description of the invention:
  1. Process step, "Obtain the digest of content to be validated"

  2. Process decision "a", "Does any copy of content already in the cache possess a digest matching that of the content to be cached?"

  3. Process step "b", "Obtain a copy of the content to be validated and store it in the cache"

  4. Process substep "a.1", "Does the provided digest of the content to be validated exist as a key within a map of cached content?"

  5. Process substep, "Return 'No' to decision 'a'"

  6. Process substep, "Return 'Yes' to decision 'b'"

  7. Process substep, "Obtain a copy of the content to be validated and store it in the cache"

  8. Process substep, "While the copy of the content is being obtained, recalculate its digest"

  9. Process substep, "Store the recalculated digest as a key for association with the cached content for later retrieval"

SUMMARY

A method for using digests to validate unattributed content in an insecure cache.

DESCRIPTION of INVENTION

The main effect of this invention is secure validation. As described in the section "Definition of Terms" above, "validation" is "[t]he act of ensuring that an identical copy of the desired content is available for retrieval from a cache. This can be achieved by either reliably detecting that a copy of the content already exists in the cache or by updating the cache with a new copy of the content."

An simple method of reliably detecting whether content, such as an electronic file, exists identically within a cache is to compare, bit for bit, the targeted content to any other content already present in the cache. The obvious drawback to this method is the need to communicate a full copy of the content for comparison, generally eliminating the advantage of having a cache in the first place.

Another method of detecting whether content pre-exists within a cache, although much less reliably, is to use a semi-unique identifier that is associated with the content, such as a file name or error detection algorithm signature. In the case of a file name, it is extremely feasible that two non-identical copies of content, one targeted for validation and the other already in the cache, may exist. In the case of an error detection algorithm signature such as a parity bit or cyclical redundancy check (CRC) value, random changes to one copy of the content may be detected but a deliberate, purposeful, and perhaps malign effort to create a non-identical copy with the same parity or CRC value, once this value is known, is not difficult.

If a short identifier or value could be created for the content such that it was computationally infeasible to create a non-identical copy of the content, either by design or by chance, with or without preliminary possession of that identifier or value, it would be useful for secure and reliable cache content validation. This currently exists in the form of "digest" algorithms as described above in the section "Definition of Terms".

As digests created by algorithms such as SHA-1 and MD5 ensure that "it is computationally infeasible to purposely create a non-identical content input that will generate the same digest", they have been employed, previous to this invention, primarily to detect deliberate and sometimes malicious changes to content once received. For example, one primary use of digests is the ensure that content such as software has not been changed to exhibit undesirable behaviors. The digest may then further be encrypted with an authentication key identifying the author or distributor, or "attributed" as defined in the section "Definition of Terms" above, to ensure the recipient that the content has not been modified by anyone else during transmission.

Rather than use digest technology in its well-known application of reliably detecting changes in content received, the innovation of this invention is to use digests to reliably detect identical copies of content already in possession. While dominant standards for cache validation currently advocate the use of semi-unique, merely semi-reliable, and insecure identifiers such as source, path, and file name; content length; or last modified date, this invention uses digests as strong identifiers for secure and reliable cache validation.

Figure 1 provides a flowchart for the process of validating cache content using digests. It maps onto claim 1. The digest of the first process step 1, "Obtain the digest of content to be validated", may be precomputed and stored or dynamically calculated if and when needed.

The process decision step 2 of Figure 1, "a", "Does any copy of content already in the cache possess a digest matching that of the content to be cached?", may be implemented in a variety of ways. The preferred embodiment is shown in Figure 2 as substep 4, "a.1", "Does the provided digest of the content to be validated exist as a key within a map of cached content?" This is particularly efficient as it only requires the detection of the existence of the key which may be hashed or indexed for quick retrieval.

The process step 3 of Figure 1, "b", "Obtain a copy of the content to be validated and store it in the cache", is performed if and only if an identical copy of the content does not already exist in the cache, as determined by process decision step 2 through the utilization of digests. Process step 3 may also be implemented in a variety of ways. The preferred embodiment is shown in Figure 3 as substeps 7, 8, and 9, "Obtain a copy of the content to be validated and store it in the cache", "While the copy of the content is being obtained, recalculate its digest", and "Store the recalculated digest as a key for association with the cached content for later retrieval", respectively. Process substeps 8 and 9 work in conjunction with process substep 4, described above.

OPERATION of INVENTION

In this section, a preferred embodiment of the invention is detailed cleanly in the form of source code for the Java programming language. The promise of the Java programming language is that it will port easily to a plethora of processing devices so it is likely that the source code may be used in multiple applications without, or with only minor, modifications. While the source code is well documented and the design is sufficiently flexible to support multiple embodiments of the invention as described in claim 1, it is useful to briefly describe the workings of the code in the context of the description and operation of the invention.

The essence of the invention as shown in Figure 1 is encapsulated in the source code method "validate", detailed below. This method performs process steps 1, 2, and 3, respectively, by obtaining a digest as a method argument; calling the "isAvailable" method to detect whether a copy of the content already exists in the cache; and, if and only if an identical copy of the content does not already exist in the cache, calling a "getInputStream" method on a "ContentAccessor" object to obtain a full copy of the content and then storing in the cache through a call to the "store" method.

Process substep 4 is implemented in the "isAvailable" method. This method determines whether the digest currently exists as a key within a map of digest keys. For flexibility in the design, the secure digest key is then used to retrieve another key, which may be a semi-unique identifier used by a insecure caching mechanism, which it passes to a delegate Cache object determine whether it possesses the content. In the computer science field of "design patterns", this is known as "design by interface composition".

Process substep 7 is implemented in the "getInputStream" method of a "ContentAccessor" object. Note that a ContentAccessor object may be implemented in a variety of ways so long as it performs its semantic function of obtaining a full copy of the content for cache storage. As examples, a particular implementation of a ContentAccessor may dynamically generate the content on the fly as needed; another may attempt to retrieve a stored copy from multiple sources in succession or in parallel.

Process substep 8 is implemented in the "store" method. Here an instance of Content in its most generic form, a stream of bits, is passed to the Cache via the "store" method call as an argument. As the Java programming language provides advanced stream handling and security as core features, it is simple to implement code that will compute a digest on the stream while it is being transferred to a delegate Cache object for transient or persistent storage.

Process substep 9 follows within the "store" method. In this case, the delegate Cache object returns an identifier. As examples, depending upon the implementation of the delegate Cache object, the identifier returned may be an insecure file name or a secure digest. The identifier returned by the delegate is then mapped using the secure digest identifier created is process substep 8 for later use in process substep 4 as described above.

There are at least two variations on deciding when to initiate the process described by this invention that have been employed. One is to perform the validation for individual content only if and when needed. The second is to perform the validation for all instances of content expected to be used so that the cache is loaded up-front. For example, in the Java programming language, software components of an application may be downloaded and integrated only as and when necessary; validation for each individual software component, or "class" file, may be distributed over time or never occur at all. On the other hand, an intelligent web browser with look-ahead capabilities may attempt to validate an entire batch of graphics for a hyperlinked web page in order to quickly load such images from the cache should the hyperlink be selected by the user.

Likewise, there at least two variations on deciding when to obtain the digests for content to validated that have been employed. One is to obtain the digest for an instance of content only if and when necessary. The second is to obtain the digests for all instances of content expected to be used so that they are readily available when needed. For example, if a user clicks on a hyperlink in a web browser, the client browser may then immediately query the web server for the MD5 digest of the web page to be fetched and perform validation immediately. On the other hand, a Java application may fetch a list of digests of its entire set of resource files upon initial startup from a remote update server to reduce the numbers of socket connections should it be necessary to validate those files.

The Java source code for the preferred embodiment of this invention follows immediately. Note that the documentation embedded in the source code suggests multiple applications, not all of which bear immediately to the core of the claim of this invention, as in the case of additional enhancements to secure cache content retrieval as opposed to the act of secure validation.



     package com.orbs.util.cache.secure;

     import java.io.*;
     import java.security.*;
     import java.util.*;

     import com.orbs.open.a.mpl.util.SoftHashMap;
     import com.orbs.open.a.mpl.util.cache.Cache;
     import com.orbs.open.a.mpl.util.cache.ContentAccessor;
     import com.orbs.open.a.mpl.util.cache.WeakCache;
     import com.orbs.open.a.mpl.util.id.ID;

     /*********************************************************************
     *
     * Cache implementation that securely stores and retrieves content
     * using digests.
     *
     * <P>
     *
     * Applications where a SecureCache may be useful include when
     *
     * <UL>
     *
     * <LI> it is desired to be able to retrieve content from the cache
     *      even though originally copied and stored from an unknown and
     *      potentially untrusted source, so long as the content is
     *      bit-for-bit identical to what is currently required;
     *
     * <P>
     *
     * <LI> multiple entities want to share the same cache without the need
     *      to worry that the activities of another, potentially untrusted,
     *      entity might modify the stored content to be something other
     *      than what is expected;
     *
     * <P>
     *
     * <LI> the cache is stored on an insecure medium which may
     *      be accessed directly and corrupted by another entity; and
     *
     * <P>
     *
     * <LI> it is desired to detect changes to content stored elsewhere
     *      by comparing the digests and then, if necessary, updating the
     *      copy in the cache to match.
     *
     * </UL>
     *
     * <P>
     *
     * The security is based upon the use of cryptographically secure
     * content digests which have the property that it is computationally
     * infeasible to find two non-identical instances of content that
     * generate digests with the same value.
     *
     * <P>
     *
     * The SecureCache wraps around a delegate Cache, which itself may
     * or may not be secure.  Multiple digest algorithms may be
     * simultaneously used by "chaining" SecureCache objects.
     *
     * <P>
     *
     * Note further that an insecure implementation of the Cache interface
     * which validates content using the more traditional mechanisms, e.g.,
     * comparing values of content length, freshness date, version
     * number, semi-unique identifier, etc., may be secured by using a
     * SecureCache as a delegate.  For example, an insecure Cache that
     * validates content using URL or path/filename, content length,
     * and/or last modified date may map an ID object storing those values
     * to a SecureID object to be passed to a delegate SecureCache.
     *
     * <P>
     *
     * The Serializable interface is implemented to support persistence.
     * To use this feature, the delegateCache and delegateIDMap must also
     * be Serializable.
     *
     * <B>
     * Reference
     * </B>
     *
     * <P>
     *
     * Sun Microsystems, "Java Cryptography Architecture API Specification
     *   & Reference",
     * <A HREF="http://www.javasoft.com/products/jdk/1.2/docs/guide/securi
ty/CryptoSpec.html#MessageDigest">
     * "Message Digest"</A>, 1998-10-30.
     *
     * <P>
     *
     * @see
     *   java.security.MessageDigest
     * @see
     *   SecureID
     * @see
     *   com.orbs.open.a.mpl.util.id.ID
     * @see
     *   com.orbs.open.a.mpl.util.cache.Cache
     * @see
     *   com.orbs.open.a.mpl.util.cache.ContentAccessor
     * @see
     *   com.orbs.open.a.mpl.util.cache.WeakCache
     * @see
     *   com.orbs.open.a.mpl.util.SoftHashMap
     *
     * @version
     *   1999-04-20
     * @author
     *   <A HREF="http://www.alumni.caltech.edu/~croft/">David W. Croft</A>
     *********************************************************************/

     public final class  SecureCache implements Cache, Serializable
     //////////////////////////////////////////////////////////////////////
     //////////////////////////////////////////////////////////////////////
     {

     private final Cache    delegateCache;
     private final Map      delegateIDMap;
     private final String   algorithm;
     private final boolean  doVerification;

     //////////////////////////////////////////////////////////////////////
     // Constructor method
     //////////////////////////////////////////////////////////////////////

     /*********************************************************************
     *
     * Creates a new SecureCache that stores content to a delegate Cache.
     *
     * @param  delegateCache
     *
     *   Where the content is actually relayed to and from.  This may be
     *   an insecure Cache or another chained SecureCache.
     *
     * @param  delegateIDMap
     *
     *   A Map of delegateCache ID objects keyed by SecureID objects
     *   generated by this SecureCache.
     *
     * @param  algorithm
     *
     *   The secure message digest algorithm to use.
     *
     * @param  doVerification
     *
     *   If true, the content digest will be recalculated upon retrieval
     *   to confirm that it has not been altered while in the
     *   delegateCache.  This is especially recommended if the
     *   delegateCache is stored on an insecure medium such as a disk
     *   drive.
     *
     *   <P>
     *
     *   If false, it is up to the caller to verify that the digest of the
     *   returned content is the same.  If the delegateCache medium is
     *   reasonably secure, such as a shared memory area with
     *   exclusive access only through this SecureCache, the caller may
     *   be reasonably secure without needing to take the extra
     *   verification step.
     *
     *   <P>
     *
     *   Note that the doVerification parameter only applies to retrieval;
     *   the digest is always calculated from the content during storage.
     *
     *********************************************************************/
     public  SecureCache (
       Cache    delegateCache,
       Map      delegateIDMap,
       String   algorithm,
       boolean  doVerification ) throws NoSuchAlgorithmException
     //////////////////////////////////////////////////////////////////////
     {
       this.delegateCache  = delegateCache;
       this.delegateIDMap  = delegateIDMap;
       this.algorithm      = algorithm;
       this.doVerification = doVerification;

       // Test for NoSuchAlgorithmException
       MessageDigest.getInstance ( algorithm );
     }

     /*********************************************************************
     *
     * This example zero argument constructor caches the content in memory,
     * dumps the content when memory runs low, identifies the content
     * using the NIST Secure Hash Algorithm (SHA), and verifies the content
     * digest upon retrieval.
     *
     * <PRE>
     *
     * this ( new WeakCache ( ), new SoftHashMap ( ), "SHA", true );
     *
     * </PRE>
     *
     *********************************************************************/
     public  SecureCache ( ) throws NoSuchAlgorithmException
     //////////////////////////////////////////////////////////////////////
     {
       this ( new WeakCache ( ), new SoftHashMap ( ), "SHA", true );
     }

     //////////////////////////////////////////////////////////////////////
     //////////////////////////////////////////////////////////////////////

     /*********************************************************************
     *
     * "Validates" the content by
     *
     * <OL>
     *
     * <LI> confirming that identical content already exists in the cache;
     *      or, if otherwise necessary,
     *
     * <LI> storing a new copy of the content in the cache.
     *
     * </OL>
     *
     * @param  secureID
     *
     *   The content identifier passed to isAvailable() to determine if
     *   the content is already valid.  The parameter may be any SecureID
     *   with potentially matching algorithm and digest values.
     *
     * @param  contentAccessor
     *
     *   An object capable of making content accessible via an InputStream.
     *   For example, a ContentAccessor might retrieve content from a
     *   website via a URL, a database or file storage, a remote object
     *   such as another cache, or even dynamically generate the content
     *   upon demand.  As yet another possibility, a ContentAccessor object
     *   may potentially attempt to access the content from several
     *   different sources sequentially until it is successful.
     *
     * @return
     *
     *   Returns a SecureID object for the validated content which may be
     *   used later for retrieval.
     *
     *   <P>
     *
     *   If valid content was already available in the cache, the returned
     *   SecureID object will be the secureID parameter.
     *
     *   <P>
     *
     *   If valid content was not already available and the content could
     *   not be accessed and stored via the contentAccessor, the returned
     *   value will be null.
     *
     *   <P>
     *
     *   If valid content was not already available and the content could
     *   be accessed and stored via the contentAccessor, the returned
     *   value will be a new SecureID object with a digest that may or may
     *   not match that of the secureID object parameter, depending on
     *   the actual content available via the contentAccessor.
     *
     *********************************************************************/
     public ID  validate ( ID  secureID, ContentAccessor  contentAccessor )
       throws IOException
     //////////////////////////////////////////////////////////////////////
     {
       if ( isAvailable ( secureID ) ) return secureID;

       InputStream  inputStream = contentAccessor.getInputStream ( );

       if ( inputStream == null ) return null;

       return store ( inputStream );
     }

     /*********************************************************************
     *
     * Stores the content to the delegateCache and returns a SecureID
     * object which may be used to retrieve it.
     *
     * @param  inputStream
     *
     *   Any finite ordered sequence of bits.  The inputStream will be
     *   read until completion by the delegateCache before return.
     *
     * @return
     *
     *   Returns a SecureID object with a digest calculated from the
     *   content inputStream.
     *
     *********************************************************************/
     public ID  store ( InputStream  inputStream ) throws IOException
     //////////////////////////////////////////////////////////////////////
     {
       if ( inputStream == null )
       {
         throw new IllegalArgumentException ( "null inputStream" );
       }

       MessageDigest  messageDigest = null;

       try
       {
         messageDigest = MessageDigest.getInstance ( algorithm );
       }
       catch ( NoSuchAlgorithmException  ex )
       {
         return null;
       }

       DigestInputStream  digestInputStream
         = new DigestInputStream ( inputStream, messageDigest );

       ID  insecureID = delegateCache.store ( digestInputStream );

       SecureID  secureID
         = new SecureID ( algorithm, messageDigest.digest ( ) );

       delegateIDMap.put ( secureID, insecureID );

       return secureID;
     }

     /*********************************************************************
     *
     * Retrieves content with a matching content digest from the
     * delegateCache.
     *
     * <P>
     *
     * If the SecureCache instance variable doVerification is set to true,
     * the digest will be recalculated via a SecureInputStream while the
     * content is being read from the delegateCache.  When the last byte is
     * read, the newly calculated digest will be compared to that of the
     * SecureID parameter object.  If the digests differ, an IOException
     * will be thrown to prevent use of the corrupted content.
     *
     * @param  secureID
     *
     *   Any SecureID object with a potentially matching content digest.
     *
     * @return
     *
     *   Returns null if the content was not or is no longer available.
     *
     *********************************************************************/
     public InputStream  retrieve ( ID  secureID ) throws IOException
     //////////////////////////////////////////////////////////////////////
     {
       if ( secureID == null )
       {
         throw new IllegalArgumentException ( "null secureID" );
       }

       ID  insecureID = ( ID ) delegateIDMap.get ( secureID );

       if ( insecureID == null ) return null;

       InputStream  inputStream = delegateCache.retrieve ( insecureID );

       if ( inputStream == null ) return null;

       if ( doVerification )
       {
         try
         {
           return new SecureInputStream ( inputStream, algorithm,
             ( ( SecureID ) secureID ).getDigest ( ) );
         }
         catch ( NoSuchAlgorithmException  ex )
         {
           return null;
         }
       }
       else
       {
         return inputStream;
       }
     }

     /*********************************************************************
     *
     * Determines if the content with a matching digest is available in
     * the delegateCache.
     *
     * @return
     *
     *   Returns false if the content was not or is no longer available.
     *
     *********************************************************************/
     public boolean  isAvailable ( ID  secureID )
     //////////////////////////////////////////////////////////////////////
     {
       if ( secureID == null ) return false;

       ID  insecureID = ( ID ) delegateIDMap.get ( secureID );

       if ( insecureID == null ) return false;

       return delegateCache.isAvailable ( insecureID );
     }

     //////////////////////////////////////////////////////////////////////
     //////////////////////////////////////////////////////////////////////
     }


CONCLUSIONS, RAMIFICATIONS, and SCOPE of INVENTION

Thus the reader will see that the invention provides a method of using digests to validate unattributed content in an insecure cache.

While my above description contains many specificities, these should not be construed as limitations on the scope of the invention, but rather as an exemplification of one preferred embodiment thereof. Many other variations are possible.

Accordingly, the scope of the invention should be determined not by the embodiment(s) described, but by the appended claims and their legal equivalents.


CLAIMS

I claim:

  1. A method for validating content in a cache, comprising:

    • obtaining a digest of content to be validated;

    • comparing said digest of content to be validated to digests of copies of content already stored in the cache;

    • obtaining a copy of said content to be validated and storing it in the cache if said comparison did not yield a match,

    whereby the successful validation will allow for the secure retrieval of content using an insecure storage memory as it is computationally infeasible to create an ordered sequence of bits possessing a digest that is identical to that of another ordered sequence of bits sought without that pair of ordered sequences of bits being likewise identical.


ABSTRACT

A method for validating content in a cache, comprising:

whereby the successful validation will allow for the secure retrieval of content using an insecure storage memory as it is computationally infeasible to create an ordered sequence of bits possessing a digest that is identical to that of another ordered sequence of bits sought without that pair of ordered sequences of bits being likewise identical.



/-------\
| Start |
\-------/
    |
    |
    v
----------------------------------------------------
| (1) Obtain the digest of content to be validated |
----------------------------------------------------
    |
    |
    v
   / \
  /   \
 /     \       /------\
/  (2)  \----->| Stop |
\  "a"  /  Y   \------/
 \     /
  \   / 
   \ /
    |           "a" == Does any copy of content already in the cache
    | N                possess a digest matching that of the content
    |                  to be cached?
    v
 -------        "b" == Obtain a copy of the content to be validated
 |     |               and store it in the cache.
 | (3) |
 | "b" |
 |     |
 -------
    |
    |
    v
/-------\
| Stop  |
\-------/

Figure 1. Validation of cache content using digests



The process of decision "a" has multiple variations.
The following is a preferred embodiment which provides
optional steps for additional security and efficiency.

/--------------\
| Start of "a" |
\--------------/
    |
    |
    v
   / \
  /   \
 /     \      /--------------------------------\
/  (4)  \--->| (5) Return "No" to decision "a" |
\ "a.1" / N   \--------------------------------/
 \     /
  \   /
   \ /
    |
    | Y
    |
    v
/----------------------------------\
| (6) Return "Yes" to decision "a" |
\----------------------------------/

"a.1" == Does the provided digest of the content to be
         validated exist as a key within a map of cached
         content?


Figure 2. Does the content already exist in the cache?



The process of step "b" has multiple variations.
The following is a preferred embodiment which provides
optional steps for additional security and efficiency.


/--------------\
| Start of "b" |
\--------------/
    |
    |
    v
-------------------------------------------
| (7) Obtain a copy of the content to be  |
|     validated and store it in the cache |
-------------------------------------------
    |
    |
    v
----------------------------------------------
| (8) While the copy of the content is being |
|     obtained, recalculate its digest       |
----------------------------------------------
    |
    |
    v
-----------------------------------------------------
| (9) Store the recalculated digest as a key for    |
|     association with the cached content for later |
|     retrieval                                     |
-----------------------------------------------------
    |
    |
    v
/------------\
| End of "b" |
\------------/

Figure 3. Storing the content in the cache