Analysis of IPCC

[Tanja Lange]

We (Daniel J. Bernstein, Jolijn Cottaar, and Tanja Lange) would like
to announce our results on the IPCC system,

IPCC is based on graphs and key recovery requires finding a perfect
dominating set in a 3-regular graph.

However, we have found some properties which allow us to efficiently
compute the plaintext from the ciphertext. The main cause of this is
that the ciphertext polynomials are very sparse. At best there are
|I| * k * 4 * 4
variables involved. These come from
|I| sets being used in the computation of f_{G_i}^k
k variables coming from each choice of S_i
4 each of these variable having 3 neighbors
4 there are at most 4 polynomials in the given examples of F (2 for
f1, 3 for f3, and 4 for f4)

This means that in the given example systems there are at most
3 * 3 * 4 * 4 = 144
out of 400 variables and for most monomials no extra addition
happens. This means that the shares of the m_i appear as coefficients
of the monomials. E.g. in the case of f1-f4 there are typically only
15 different coefficients: 9 from the cross products of the 3 c_{1j}
shares of m_1 with the 3 c_{2j} shares of m_2, and 3 more from the new
shares of the polynomial for graph 1, and 3 more from the polynomial for
graph 2
m_1 * m_2 + m_3 + m_4
where m_3 = m_1, m_4 = m_2 for f1 and independently chosen for f4.

The core of the attack is that the sum of those 15 coefficients taken
modulo p gives the plaintext.

As an example, consider the first example in the KAT for the case of f1.
This is given a message m = 18790. The ciphertext produced by the
reference implementation contains the following list of coefficients
(here stated without their multiplicities):
[35, 9087, 14460, 16002, 16620, 21637, 22560, 24760, 33530, 36038, 36868, 38564, 39587, 39792, 62376].
Summing these up gives us 411916 = 18790 mod 65521, which indeed is
the plaintext. Note that the KAT file shows the hash of the
ciphertext, not the ciphertext itself.

We ran this attack on ciphertexts produced by the KAT. There are some
few cases (2 out of 100 for f1, 0 out of 100 for f3, 8 out of 100 for
f4) where this simple attack does not give the plaintext: in these
cases, there are more than 15 coefficients, because variables repeated
leading to combinations. We are still working on tracing through those
to determine which of the coefficients we need to skip in summing
up. We think that counting the frequency of occurrence will give us
information. But we wanted to announce our findings so far as a fast
attack with a success probability of more than 90% means that the
system is typically broken.

We understand that the implementation is for smaller parameters than
the authors suggest and that knowing F helps the attacker. However,
there are only k+1 different monomials of total degree k split over
the two graphs (terms in \mathcal F) and \sum_{i-1}^k (i+1)
polynomials of absolute degree \le k, which means that the resulting
polynomials are still likely to be sparse. Hence, even if only the
general choices of |I| and k are known the attacker knows how many
distinct coefficients to expect and the problem seems to persist
unless there are many more terms.

All the best
Dan, Jolijn, and Tanja

[Yongjin Yeom]

First of all, thanks for fatal but very helpful attack!
We acknowledge that the current version of our proposal is vulnerable to the attack described by reviewers.

It is basically due to the simplicity of invariant polynomials in the design that are multiplications of simple sums of neighbors.
It was indeed easy to guess the coefficients used for comprising the message by looking at the resulting polynomial, particularly in the reference code.

Fundamentally, as illustrated in our paper,
the message can be restored from ciphertext by Gaussian elimination regardless of complexity of invariant polynomials.
In other direction, your attack pointed out the limitation of IPCC due to the simplicity of linear relations (as trapdoor information).
Thanks to your review, we investigate the underlying theory and find a direction to revise our scheme.

We are trying to overcome our problem by adopting more complex and general invariant polynomials of higher order.
Unfortunately, we cannot avoid the (hopefully slight)loss of efficiency and it is not easy for us to make an instant patch.
It may takes few weeks or longer.

Thank you again for your analysis!

2022년 12월 24일 토요일 오전 3시 26분 0초 UTC+9에 Tanja Lange님이 작성: