## CryptoDB

### Donghoon Chang

#### Publications

**Year**

**Venue**

**Title**

2020

TOSC

Release of Unverified Plaintext: Tight Unified Model and Application to ANYDAE
📺
Abstract

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

2008

FSE

2008

EPRINT

Improved Cryptanalysis of APOP-MD4 and NMAC-MD4 using New Differential Paths
Abstract

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
Abstract

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
Abstract

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
Abstract

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
Abstract

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
Abstract

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

EPRINT

Preimage Attacks on CellHash, SubHash and Strengthened Versions of CellHash and SubHash
Abstract

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
Abstract

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
Abstract

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
Abstract

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
Abstract

`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)
Abstract

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
Abstract

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
Abstract

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
Abstract

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.

#### Coauthors

- Megha Agrawal (2)
- Tarun Kumar Bansal (1)
- Seongtaek Chee (3)
- Nilanjan Datta (1)
- Avijit Dutta (1)
- Mohona Ghosh (1)
- Seokhie Hong (8)
- Deukjo Hong (3)
- Arpan Jati (2)
- Kitae Jeong (1)
- Hyun Kim (1)
- Jongsung Kim (2)
- Bonseok Koo (1)
- Changhoon Lee (1)
- Jesang Lee (3)
- Eunjin Lee (1)
- Wonil Lee (2)
- Jaesang Lee (1)
- Sangjin Lee (9)
- Jongin Lim (1)
- Bart Mennink (1)
- Sweta Mishra (2)
- Dukjae Moon (2)
- Mridul Nandi (9)
- Kouichi Sakurai (1)
- Somitra Sanadhya (1)
- Somitra Kumar Sanadhya (5)
- Palash Sarkar (1)
- Ferdinand Sibleyras (1)
- Jaechul Sung (8)
- Soo Hak Sung (1)
- Moti Yung (3)