## CryptoDB

### Jin Hong

#### Publications

Year
Venue
Title
2014
JOFC
2013
JOFC
Three time-memory tradeoff algorithms are compared in this paper. Specifically, the classical tradeoff algorithm by Hellman, the distinguished point tradeoff method, and the rainbow table method, in their non-perfect table versions, are treated.We show that, under parameters and assumptions that are typically considered in theoretic discussions of the tradeoff algorithms, the Hellman and distinguished point tradeoffs perform very close to each other and the rainbow table method performs somewhat better than the other two algorithms. Our method of comparison can easily be applied to other situations, where the conclusions could be different.The analysis of tradeoff efficiency presented in this paper does not ignore the effects of false alarms and also covers techniques for reducing storage, such as ending point truncations and index tables. Our comparison of algorithms fully takes into account success probabilities and precomputation efforts.
2010
EPRINT
The three major time memory tradeoff algorithms are compared in this paper. Specifically, the Hellman tradeoff algorithm, the distinguished point tradeoff method, and the rainbow table method, in their non-perfect table versions, are considered. We show that, under parameters that are typically considered in theoretic discussions of the tradeoff algorithms, Hellman and distinguished point tradeoffs perform very close to each other and the rainbow table method performs somewhat better than the other two algorithms. Our method of comparison can easily be applied to other situations, where the conclusions could be different. The analysis presented in this paper takes the effects of false alarms into account and also fully considers techniques for reducing storage, such as the ending point truncation method and index files.
2009
PKC
2008
EPRINT
The time memory trade-off (TMTO) algorithm, first introduced by Hellman, is a method for quickly inverting a one-way function, using pre-computed tables. The distinguished point method (DP) is a technique that reduces the number of table lookups performed by Hellman's algorithm. In this paper we propose a new variant of the DP technique, named variable DP (VDP), having properties very different from DP. It has an effect on the amount of memory required to store the pre-computed tables. We also show how to combine variable chain length techniques like DP and VDP with a more recent trade-off algorithm called the rainbow table method.
2008
EPRINT
With any cryptanalytic time memory tradeoff algorithm, false alarms pose a major obstacle in accurate assessment of its online time complexity. We study the size of pre-image set under function iterations and use the obtained theory to analyze the cost incurred by false alarms. We are able to present the expected online time complexities for the Hellman tradeoff and the rainbow table method in a manner that takes false alarms into account. The effect of checkpoints in reducing the cost of false alarms is also quantified.
2008
ASIACRYPT
2005
ASIACRYPT
2005
FSE
2005
EPRINT
Some of the existing time memory tradeoff attacks (TMTO) on specific systems can be reinterpreted as methods for inverting general oneway functions. We apply these methods back to specific systems in ways not considered before. This provides the following startling results. No streamcipher can provide security equal to its key length; some important blockcipher modes of operations are vulnerable to TMTO; and no hash function can provide preimage resistance equal to its digest length.
2005
EPRINT
We give three weaknesses of a recently proposed streamcipher MICKEY. A small class of weak keys is found and we show time-memory-data tradeoff is applicable. We also show that the state update function reduces entropy of the internal state as it is iterated, resulting in keystreams that start out differently but become merged together towards the end.
2004
FSE
2004
FSE
2003
EPRINT
We apply the algebraic attacks on stream ciphers with memories to the summation generator. For a summation generator that uses $n$ LFSRs, the algebraic equation relating the key stream bits and LFSR output bits can be made to be of degree less than or equal to $2^{\lceil\log_2 n \rceil}$, using $\lceil\log_2 n \rceil + 1$ consecutive key stream bits. This is much lower than the upper bound given by previous general results.
2002
EPRINT
NTRU is an efficient public-key cryptosystem proposed by Hoffstein, Pipher, and Silverman. Assuming access to a decryption oracle, we show ways to recover the private key of NTRU systems that do not include a ciphertext validating procedure. The strongest of our methods will employ just a single call to the oracle, and in all cases, the number of calls needed will be small enough to be realistic.

FSE 2007