Contact
CoCalc Logo Icon
StoreFeaturesDocsShareSupport News AboutSign UpSign In
| Download

Deep-iterates-based attack on the Concatenation combiner of kk hash functions

Views: 44
n = var('n') l = var('l') k = var('k') kappa = var('kappa') g2 = var('g2') g1 = var('g1') restriction_g1 = (g1 >= n/2, g1 >= n - l) Phase1 = l Phase2 = g1 - l + k*n - k * g1 Phase3_1 = g2 Phase3_2 = k*n - (k + 1) * (n - g1) + n - g2 show('--------------------------------------------------------------------') show('Complexity of Phases are (log2): ') show('Phase 1: ', Phase1) show('Phase 2: ', Phase2) show('Phase 3 term 1: ', Phase3_1.simplify_full()) show('Phase 3 term 2: ', Phase3_2.simplify_full()) show('--------------------------------------------------------------------') g2s = solve([Phase3_1 == Phase3_2], g2)[0] show('--------------------------------------------------------------------') show('Balance the first two terms in Phase 3 by setting: ') show(g2s) g2s = g2s.rhs() Phase3_1 = Phase3_1(g2 = g2s) Phase3_2 = Phase3_2(g2 = g2s) show('--------------------------------------------------------------------') show('Complexity of Phases becomes (log2): ') show('Phase2: ', Phase2) show('Phase 3 term 1: ', Phase3_1.simplify_full()) show('Phase 3 term 2:', Phase3_2.simplify_full()) g1s = solve([Phase2 == Phase3_1], g1)[0] show('--------------------------------------------------------------------') show('Balance Phase 2 and Phase 3 term 1 by setting:') show(g1s) g1s = g1s.rhs() show('This balance only valid under the restriction: ') show(restriction_g1) show('Which implies: ') bound_l = solve([g1s >= n - l, g1s >= n/2, l < n], l)[-1] bound_l_ = (bound_l[0], bound_l[1]) show(bound_l_) show('--------------------------------------------------------------------') Phase1_case1 = Phase1(g1 = g1s) Phase2_case1 = Phase2(g1 = g1s) Phase3_1_case1 = Phase3_1(g1 = g1s) Phase3_2_case1 = Phase3_2(g1 = g1s) show('--------------------------------------------------------------------') show('For the case') show(bound_l_) show('Complexity of Phases are (log2): ') show('Phase 1: ', Phase1_case1.simplify_full()) show('Phase 2: ', Phase2_case1.simplify_full()) show('Phase 3 term 1: ', Phase3_1_case1.simplify_full()) show('Phase 3 term 2: ', Phase3_2_case1.simplify_full()) show('--------------------------------------------------------------------') ls = solve([Phase1_case1 == Phase2_case1], l)[0] Phase1_case1 = Phase1_case1 (l = ls.rhs()) Phase2_case1 = Phase2_case1 (l = ls.rhs()) Phase3_1_case1 = Phase3_1_case1 (l = ls.rhs()) Phase3_2_case1 = Phase3_2_case1 (l = ls.rhs()) show('--------------------------------------------------------------------') show('The optimal complexity is (log2):') show('Phase1: ', Phase1_case1.simplify_full()) show('Phase2: ', Phase2_case1.simplify_full()) show('Phase 3, term 1:', Phase3_1_case1.simplify_full()) show('Phase 3, term 2:', Phase3_2_case1.simplify_full()) show('Obtained for ') show(ls) show('--------------------------------------------------------------------') for i in range(2, 4): show(' ------------------------------ ', k == i, ' ------------------------------') Phase1cplx = Phase1_case1(k = i) Phase1cplxs = Phase1cplx(kappa=log(i, 2)).simplify_full() Phase2cplx = Phase2_case1(k = i) Phase2cplxs = Phase2cplx(kappa=log(i, 2)).simplify_full() Phase3_1cplx = Phase3_1_case1(k = i) Phase3_1cplxs = Phase3_1cplx(kappa=log(i, 2)).simplify_full() Phase3_2cplx = Phase3_2_case1(k = i) Phase3_2cplxs = Phase3_2cplx(kappa=log(i, 2)).simplify_full() show('Phase 1: ', Phase2cplxs) show('Phase 2: ', Phase2cplxs) show('Phase 3 term 1: ', Phase3_1cplxs) show('Phase 3 term 2: ', Phase3_2cplxs)
--------------------------------------------------------------------
Complexity of Phases are (log2):
Phase 1: l\displaystyle l
Phase 2: g1k+kn+g1l\displaystyle -g_{1} k + k n + g_{1} - l
Phase 3 term 1: g2\displaystyle g_{2}
Phase 3 term 2: g1k+g1g2\displaystyle g_{1} k + g_{1} - g_{2}
--------------------------------------------------------------------
--------------------------------------------------------------------
Balance the first two terms in Phase 3 by setting:
g2=12g1k+12g1\displaystyle g_{2} = \frac{1}{2} \, g_{1} k + \frac{1}{2} \, g_{1}
--------------------------------------------------------------------
Complexity of Phases becomes (log2):
Phase2: g1k+kn+g1l\displaystyle -g_{1} k + k n + g_{1} - l
Phase 3 term 1: 12g1k+12g1\displaystyle \frac{1}{2} \, g_{1} k + \frac{1}{2} \, g_{1}
Phase 3 term 2: 12g1k+12g1\displaystyle \frac{1}{2} \, g_{1} k + \frac{1}{2} \, g_{1}
--------------------------------------------------------------------
Balance Phase 2 and Phase 3 term 1 by setting:
g1=2(knl)3k1\displaystyle g_{1} = \frac{2 \, {\left(k n - l\right)}}{3 \, k - 1}
This balance only valid under the restriction:
(g112n\displaystyle g_{1} \geq \frac{1}{2} \, n, g1l+n\displaystyle g_{1} \geq -l + n)
Which implies:
(13n<l\displaystyle \frac{1}{3} \, n < l, l<n\displaystyle l < n)
--------------------------------------------------------------------
--------------------------------------------------------------------
For the case
(13n<l\displaystyle \frac{1}{3} \, n < l, l<n\displaystyle l < n)
Complexity of Phases are (log2):
Phase 1: l\displaystyle l
Phase 2: (k+1)l(k2+k)n3k1\displaystyle -\frac{{\left(k + 1\right)} l - {\left(k^{2} + k\right)} n}{3 \, k - 1}
Phase 3 term 1: (k+1)l(k2+k)n3k1\displaystyle -\frac{{\left(k + 1\right)} l - {\left(k^{2} + k\right)} n}{3 \, k - 1}
Phase 3 term 2: (k+1)l(k2+k)n3k1\displaystyle -\frac{{\left(k + 1\right)} l - {\left(k^{2} + k\right)} n}{3 \, k - 1}
--------------------------------------------------------------------
--------------------------------------------------------------------
The optimal complexity is (log2):
Phase1: 14(k+1)n\displaystyle \frac{1}{4} \, {\left(k + 1\right)} n
Phase2: 14(k+1)n\displaystyle \frac{1}{4} \, {\left(k + 1\right)} n
Phase 3, term 1: 14(k+1)n\displaystyle \frac{1}{4} \, {\left(k + 1\right)} n
Phase 3, term 2: 14(k+1)n\displaystyle \frac{1}{4} \, {\left(k + 1\right)} n
Obtained for
l=14(k+1)n\displaystyle l = \frac{1}{4} \, {\left(k + 1\right)} n
--------------------------------------------------------------------
------------------------------ k=2\displaystyle k = 2 ------------------------------
Phase 1: 34n\displaystyle \frac{3}{4} \, n
Phase 2: 34n\displaystyle \frac{3}{4} \, n
Phase 3 term 1: 34n\displaystyle \frac{3}{4} \, n
Phase 3 term 2: 34n\displaystyle \frac{3}{4} \, n
------------------------------ k=3\displaystyle k = 3 ------------------------------
Phase 1: n\displaystyle n
Phase 2: n\displaystyle n
Phase 3 term 1: n\displaystyle n
Phase 3 term 2: n\displaystyle n