International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Jin Hong

Affiliation: Seoul National University

Publications

Year
Venue
Title
2014
JOFC
2013
JOFC
A Comparison of Cryptanalytic Tradeoff Algorithms
Jin Hong Sunghwan Moon
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
A Comparison of Cryptanalytic Tradeoff Algorithms
Jin Hong Sunghwan Moon
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
Variants of the Distinguished Point Method for Cryptanalytic Time Memory Trade-offs (Full version)
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
The Cost of False Alarms in Hellman and Rainbow Tradeoffs
Jin Hong
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
Rediscovery of Time Memory Tradeoffs
Jin Hong Palash Sarkar
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
TMD-Tradeoff and State Entropy Loss Considerations of Streamcipher MICKEY
Jin Hong Woo-Hwan Kim
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
Algebraic Attacks on Summation Generators
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
Key recovery attacks on NTRU without ciphertext validation routine
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.

Program Committees

FSE 2007