Search

This paper presents a new hash chain traversal strategy which improves performance of hash chain based one-time authentication schemes. This work is motivated by the need for efficient message authentication in low-latency multicast systems. Proposed solutions such as TV-OTS rely on hash chain generated values for keys, achieving reliable security by using only a small subset of generated values from each chain. However, protocols using hash chains are limited by the rate at which a hash chain traversal is able to supply keys. The new algorithm uses the same structure as Fractal Hash Traversal, but eliminates redundant operations incurred when used with applications such as TV-OTS. Performance is measured in terms of savings and is proportional to the chain-distance between consecutively retrieved values. For a distance of delta, we achieve Theta(delta_2(delta)) savings, which is shown analytically and supported by empirical tests.

We have developed an extension of ACL2 that includes the implementation of hash-based association lists and function memoization; this makes some algorithms execute more quickly. This extension, enabled partially by the implementation of Hash-CONS, represents ACL2 data objects in a canonical way, thus the comparison of any two such objects can be determined without the cost of descending through their CONS structures. A restricted set of ACL2 user-defined functions may be memoized; the underlying implementation may conditionally retain the values of such function calls so that if a repeated function application is requested, a previously computed value may instead be returned. We have defined a fast association list access and update functions using hash tables. We provide a file reader that identifies and eliminates duplicate representations of repeated objects, and a file printer that produces output with no duplicate subexpressions.

Current techniques for collision search with feasible memory requirements involve pseudo-random walks through some space where one must wait for the result of the current step before the next step can begin. These techniques are serial in nature, and direct parallelization is inefficient. We present a simple new method of parallelizing collision searches that greatly extends the reach of practical attacks. The new method is illustrated with applications to hash functions and discrete logarithms in cyclic groups. In the case of hash functions, we begin with two messages; the first is a message that we want our target to digitally sign, and the second is a message that the target is willing to sign. Using collision search adapted for hashing collisions, one can find slightly altered versions of these messages such that the two new messages give the same hash result. As a particular example, a $10 million custom machine for applying parallel collision search to the MD5 hash function could complete an attack with an expected run time of 24 days. This machine would be specific to MD5, but could be used for any pair of messages. For discrete logarithms in cyclic groups, ideas from Pollard's rho and lambda methods for index computation are combined to allow efficient parallel implementation using the new method. As a concrete example, we consider an elliptic curve cryptosystem over GF(2155) with the order of the curve having largest prime factor of approximate size 1036. A $10 million machine custom built for this finite field could compute a discrete logarithm with an expected run time of 36 days.

Our previous research on one-probe access to large collections of data indexed by alphanumeric keys has produced the first practical minimal perfect hash functions for this problem. Here, a new algorithm is described for quickly finding minimal perfect hash functions whose specification space is very close to the theoretical lower bound, i.e., around 2 bits per key. The various stages of processing are detailed, along with analytical and empirical results, including timing for a set of over 3.8 million keys that was processed on a NeXTstation in about 6 hours.

The CASE statement evaluates an expression, selects an action according to the value of the expression and then executes the action. The most efficient runtime behavior is exhibited when the action can be selected via a jump table, which provides an entry for every possible value in the range of the expression but has execution time that is constant as the number of cases increases. If the range of the expression is too large then the jump table becomes impractical because of excessive space requirements. Implementations of the CASE statement that limit table size to increase linearly with the number of cases either require linear execution time or capitalize on the subrange structure of the expression to reduce the time requirement. Hash methods also limit space requirements, and in the case of hashing with chaining to resolve collisions can provide log n time performance. Open addressing methods provide constant time performance as the number of cases increases and, since the hash table is static and can be closely packed in an optimal fashion, the execution time can be limited to an average of less than two probes per selection even for closely packed tables. Open addressing in optimally packed tables leads to selection of the default case in fewer than eight probes. One can choose a hash function that facilitates extension of allowed data types from the usual byte and integer types to strings and double precision integers with minimal penalty in execution time.

A method is presented for implementing multi-attribute files using hashing. All inverted values are stored in a single shared hash area. The entries in the hash area are stored in variable-length form and contain the attribute values, the attribute name identifier, and one or more identifiers of records in the file which possess the attribute values. The file itself is directly accessable and stored in entry-sequence. In addition to retrieval methodology, the physical methodology for loading the hash area with the inverted values is given. Also, considerations for adding new records, and deleting and changing existing records are given.

This paper investigates a relatively new file structure known as an ordered hash table which combines the flexibility of indexed sequential files with the rapid access of traditional hashing methods. The main results of the paper are: (1) a characterization of optimal hash tables allowing for differing access frequencies among the keys, and (2) an algorithm to construct an optimal ordered hash table. The details of the algorithm are given for the special case of unit bucket size but it may be extended to cover large bucket sizes.