International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Donghoon Chang

Publications

Year
Venue
Title
2020
TOSC
Release of Unverified Plaintext: Tight Unified Model and Application to ANYDAE 📺
Authenticated encryption schemes are usually expected to offer confidentiality and authenticity. In case of release of unverified plaintext (RUP), an adversary gets separated access to the decryption and verification functionality, and has more power in breaking the scheme. Andreeva et al. (ASIACRYPT 2014) formalized RUP security using plaintext awareness, informally meaning that the decryption functionality gives no extra power in breaking confidentiality, and INT-RUP security, covering authenticity in case of RUP. We describe a single, unified model, called AERUP security, that ties together these notions: we prove that an authenticated encryption scheme is AERUP secure if and only if it is conventionally secure, plaintext aware, and INT-RUP secure. We next present ANYDAE, a generalization of SUNDAE of Banik et al. (ToSC 2018/3). ANYDAE is a lightweight deterministic scheme that is based on a block cipher with block size n and arbitrary mixing functions that all operate on an n-bit state. It is particularly efficient for short messages, it does not rely on a nonce, and it provides maximal robustness to a lack of secure state. Whereas SUNDAE is not secure under release of unverified plaintext (a fairly simple attack can be mounted in constant time), ANYDAE is. We make handy use of the AERUP security model to prove that ANYDAE achieves both conventional security as RUP security, provided that certain modest conditions on the mixing functions are met. We describe two simple instances, called MONDAE and TUESDAE, that conform to these conditions and that are competitive with SUNDAE, in terms of efficiency and optimality.
2015
EPRINT
2015
EPRINT
2015
EPRINT
2015
EPRINT
2015
EPRINT
2011
FSE
2008
FSE
2008
FSE
2008
EPRINT
Improved Cryptanalysis of APOP-MD4 and NMAC-MD4 using New Differential Paths
In case of security analysis of hash functions, finding a good collision-inducing differential paths has been only focused on. However, it is not clear how differential paths of a hash function influence the securities of schemes based on the hash function. In this paper, we show that any differential path of a hash function can influence the securities of schemes based on the hash function. We explain this fact with the MD4 hash function. We first show that APOP-MD4 with a nonce of fixed length can be analyzed efficiently with a new differential path. Then we improve the result of the key-recovery attack on NMAC-MD4 described by Fouque {\em et al.} \cite{FoLeNg07} by combining new differential paths. Our results mean that good hash functions should have the following property : \textit{It is computationally infeasible to find differential a path of hash functions with a high probability}.
2008
EPRINT
A Short Proof of the PRP/PRF Switching Lemma
Donghoon Chang Mridul Nandi
In Eurocrypt 2006, Bellare and Rogaway \cite{BeRo06} gave a proof of the PRP/PRF switching Lemma using their game-based proof technique. In the appendix of the same paper, they also gave an proof without games. In this paper, we give another proof of the switching lemma, which is simple and mathematically-clear and easy to uderstand. Our proof is based on \textit{the strong interpolation theorem}.
2008
EPRINT
Indifferentiable Security Analysis of choppfMD, chopMD, a chopMDP, chopWPH, chopNI, chopEMD, chopCS, and chopESh Hash Domain Extensions
We provide simple and unified indifferentiable security analyses of choppfMD, chopMD, a chopMDP (where the permutation $P$ is to be xored with any non-zero constant.), chopWPH (the chopped version of Wide-Pipe Hash proposed in \cite{Lucks05}), chopEMD, chopNI, chopCS, chopESh hash domain extensions. Even though there are security analysis of them in the case of no-bit chopping (i.e., $s=0$), there is no unified way to give security proofs. All our proofs in this paper follow the technique introduced in \cite{BeDaPeAs08}. These proofs are simple and easy to follow.
2008
EPRINT
Various Security Analysis of a pfCM-MD Hash Domain Extension and Applications based on the Extension
We propose a new hash domain extension \textit{a prefix-free-Counter-Masking-MD (pfCM-MD)}. And, among security notions for the hash function, we focus on the indifferentiable security notion by which we can check whether the structure of a given hash function has any weakness or not. Next, we consider the security of HMAC, two new prf constructions, NIST SP 800-56A key derivation function, and the randomized hashing in NIST SP 800-106, where all of them are based on the pfCM-MD. Especially, due to the counter of the pfCM-MD, the pfCM-MD are secure against all of generic second-preimage attacks such as Kelsey-Schneier attack \cite{KeSc05} and Elena {\em et al.}' attck \cite{AnBoFoHoKeShZi08}. Our proof technique and most of notations follow those in \cite{BeDaPeAs08,Bellare06,BeCaKr96a}.
2007
EPRINT
New FORK-256
The hash function FORK-256 was published at the ¯rst NIST hash workshop and FSE 2006. It consists of simple operations so that its performance is better than that of SHA-256. However, recent papers show some weaknesses of FORK-256. In this paper, we propose newly modi¯ed FORK-256 which has no microcoliisions and so is resistant against existing attacks. Furthermore, it is faster than the old one.
2007
EPRINT
Hash Function Design Principles Supporting Variable Output Lengths from One Small Function
In this paper, we introduce new hash function design principles with variable output lengths (multiple of $n$). It is based on a function or a block cipher which has output size $n$. In the random oracle model it has optimal collision resistance which requires $\Theta(2^{(t+1)n/2})$ queries to find $(t+1)n$-bit hash output collisions, where $t$ is any positive integer. Similarly, in the ideal cipher model, $\Theta(2^{(t+1)n/2})$ queries are required to find $(t+1)n$-bit hash output collisions.
2006
ASIACRYPT
2006
CHES
2006
FSE
2006
EPRINT
Preimage Attacks on CellHash, SubHash and Strengthened Versions of CellHash and SubHash
Donghoon Chang
CellHash \cite{DaGoVa91} and SubHash \cite{DaGoVa92} were suggested by J. Daemen, R. Govaerts and J. Vandewalle in 1991 and 1992. SubHash is an improved version from CellHash. They have 257-bit internal state and 256-bit hash output. In this paper, we show a preimage attack on CellHash (SubHash) with the complexity $2^{129+t}$ and the memory $2^{128-t}$ for any $t$ (with the complexity about $2^{242}$ and the memory size $2^{17}$). Even though we modify them in a famous way, we show that we can find a preimage on the modified CellHash (the modified SubHash) with the complexity $2^{200}$ and the memory size $2^{59}$ (with the complexity about $2^{242}$ and the memory size $2^{17}$).
2006
EPRINT
General Distinguishing Attacks on NMAC and HMAC with Birthday Attack Complexity
Donghoon Chang Mridul Nandi
Kim {\em et al}. \cite{KiBiPrHo06} and Contini {\em et al}. \cite{CoYi06} studied on the security of HMAC and NMAC based on HAVAL, MD4, MD5, SHA-0 and SHA-1. Especially, they considered the distinguishing attacks. However, they did not describe generic distinguishing attacks on NMAC and HMAC. In this paper, we describe the generic distinguishers to distinguish NMAC and HMAC with the birthday attack complexity and we prove the security bound when the underlying compression function is the random oracle.
2006
EPRINT
Preimage Attack on Hashing with Polynomials proposed at ICISC'06
Donghoon Chang
In this paper, we suggest a preimage attack on Hashing with Polynomials \cite{Shpilrain06b}. The algorithm has $n$-bit hash output and $n$-bit intermediate state. (for example, $n=163$). The algorithm is very simple and light so that it can be implement in low memory environment. Our attack is based on the meet-in-the-middle attack. We show that we can find a preimage with the time complexity $2^{n-t}+2^{t}*(n+1/33)$ and the memory $2^{t}$ even though the recursive formula $H$ uses any \textsf{f} whose each term's degree in terms of \textsf{x} is $2^a$ for a non-negative integer $a$. We recommend that hash functions such as Hashing with Polynomials should have the intermediate state size at least two times bigger than the output size.
2006
EPRINT
Preimage Attack on Parallel FFT-Hashing
Donghoon Chang
Parallel FFT-Hashing was designed by C. P. Schnorr and S. Vaudenay in 1993. The function is a simple and light weight hash algorithm with 128-bit digest. Its basic component is a multi-permutation which helps in proving its resistance to collision attacks. % In this work we show a preimage attack on Parallel FFT-Hashing with complexity $2^{t+64}+2^{128-t}$ and memory $2^{t}$ which is less than the generic complexity $2^{128}$. When $t=32$, we can find a preimage with complexity $2^{97}$ and memory $2^{32}$. Our method can be described as ``disseminative-meet-in-the-middle-attack'' we actually use the properties of multi-permutation (helpful against collision attack) to our advantage in the attack. Overall, this type of attack (beating the generic one) demonstrates that the structure of Parallel FFT-Hashing has some weaknesses when preimage attack is considered. To the best of our knowledge, this is the first attack on Parallel FFT-Hashing.
2006
EPRINT
Preimage Attacks On Provably Secure FFT Hashing proposed at Second Hash Workshop in 2006
Donghoon Chang
`Provably Secure FFT Hashing' (We call FFT-Hash in this paper) was suggested by Lyubashevsky et al.. in Second Hash Workshop in Aug. 2006. This paper shows preimage attacks on hash functions based on three modes of FFT-Hash. In case of `Nano' whose output size is 513 bits, we can find a preimage with complexity $2^{385}$. In case of `Mini' whose output size is 1025 bits, we can find a preimage with complexity $2^{769}$. In case of `Mini' whose output size is 28672 bits, we can find a preimage with complexity $2^{24576}$. This means that the structure of FFT-Hash is weak in the viewpoint of the preimage resistance. We recommend that FFT-Hash can not be used in case of the output size less than 256 bits because the full security against the preimage attack are crucial in such a short output size. And also we should not chop the hash output in order to get a short hash output like SHA-224 and SHA-384, because for example we can find a preimage with complexity $2^{128}$ (not $2^{256}$) in case of `Nano' with chopping 257 bits whose hash output is 256 bits.
2006
EPRINT
Do We Need to Vary the Constants? (Methodological Investigation of Block-Cipher Based Hash Functions)
Donghoon Chang Moti Yung
The recent collision attacks on the MD hash function family do not depend on the constants used in the function, but rather on its structure (i.e., changing the constants will not affect the differential analysis based attacks). Thus, is seems that the role of constants in maintaining security and preventing these attacks is unclear, at best, for this case and in particular fixing or varying the constants will not matter for these analyses. % In this work we present a methodological investigation into the case of block-cipher based PGV hash functions family, and investigate the importance of constants in securing these designs. % To this end we consider the twelve variants of the PGV family that yield secure hash in the generic ideal cipher case (as was shown by Black, Rogaway and Shrimpton), but consider them under concrete instantiation. % % To investigate the role of constant in the key derivation procedure we just ignore the constants. In this more uniform setting we further consider a very regular cipher, namely AES modified to have Mixcolumn also in the last round (which should still be a strong cipher). % Analyzing this modified-AES based hashing, we show that with about 16\% probability we can find collisions with complexity $2^{49}$ (much smaller than the birthday attack complexity $2^{64}$). While we do not claim to break the AES based version, this nevertheless shows that constants in block cipher have an important role in resisting collision attack (in particular there is a need to vary the constant). It also shows that (in the symmetric modified version) merely the concrete AES structure does not guarantee the security of AES-based hash function (shown secure under the ideal cipher model). This is undesirable and non-robust, because this means that even though a block cipher has complicated structures in its round function and its key scheduling algorithm, we can not have a confidence about the security of hash functions based solely on it (note that there are several block ciphers such as IDEA, 3-key triple DES which do not use any constants). % Given the above methodological findings, we suggest new AES-based hash function constructions (essentially modified PGV) which can be generalized to any block cipher. The functions inherit the security under the ideal cipher model on the one hand, while, on the other hand, concretely assure in their structure that the weakness exhibited herein is dealt with.
2006
EPRINT
Near-Collision Attack and Collision-Attack on Double Block Length Compression Functions based on the Block Cipher IDEA
Donghoon Chang
IDEA is a block cipher designed by Xuejia Lai and James L. Massey and was first described in 1991. IDEA does not vary the constant in its key schedule. In \cite{ChYu06}, Donghoon Chang and Moti Yung showed that there may be a weakness of hash function based on block cipher whose key schedule does not use various constants. Based on their result, we investigate the security of double block length compression functions based on the block cipher IDEA such that the key size of IDEA is 128 bits and its block length is 64 bits. We use the double block length hash functions proposed by Shoichi Hirose in the second hash workshop in 2006 \cite{Hirose06}. Then, we can easily find a near-collision by hand. And also, for a constant $c$ of DBL hash functions, we can find a collision by hand. This means that the constant $c$ may be used as a trapdoor to make the attacker find collision easily.
2006
EPRINT
A Practical Limit of Security Proof in the Ideal Cipher Model : Possibility of Using the Constant As a Trapdoor In Several Double Block Length Hash Functions
Donghoon Chang
Recently, Shoichi Hirose \cite{Hirose06} proposed several double block length (DBL) hash functions. Each DBL hash function uses a constant which has a role to make the DBL hash function collision-resistant in the ideal cipher model. However, we have to instantiate a block cipher. In this paper, we show that the constant may be used as a trapdoor to help a attacker to find a collision easily. In case of 256-bit output size, we can find a collision with the complexity $2^{64}$. This is a gap between the security of the DBL hash function in the ideal cipher model and the security of the DBL hash function based on any block cipher.
2004
EPRINT
A Generalization of PGV-Hash Functions and Security Analysis in Black-Box Model
In~\cite{B02} it was proved that 20 out of 64 PGV-hash functions~\cite{P94} based on block cipher are collision resistant and one-way-secure in black-box model of the underlying block cipher. Here, we generalize the definition of PGV-hash function into a hash family and we will prove that besides the previous 20 hash functions we have 22 more collision resistant and one-way secure hash families. As all these 42 families are keyed hash family, these become target collision resistant also. All these 42 hash families have tight upper and lower bounds on (target) collision resistant and one-way-ness.
2003
ASIACRYPT