Contact
CoCalc Logo Icon
StoreFeaturesDocsShareSupport News AboutSign UpSign In
| Download

Deep-iterates-Interchange-structure-based attack on the XOR combiner of two hash functions

Views: 44
n = var('n') l = var('l') r = var('r') s = var('s') g1 = var('g1') g2 = var('g2') restriction_l = (l <= n/2) restriction_g1 = (g1 >= n/2, g1 >= n - l) restriction_r = ( 2*r <=l) restrictions = (g1 >= n/2, g1 >= n - l, 2*r <= l) Phase1 = l Phase2 = n + s - g1 Phase3_1 = g2 Phase3_p = r + 3 * g1 - n - s - 2 * r Phase3_2 = Phase3_p + n - g2 Phase3_3 = Phase3_p + l + g2 - n Phase3_4 = Phase3_p + l + s - g1 Phase3_5 = n/2 + 2 * r 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('Phase 3 term 3: ', Phase3_3.simplify_full()) show('Phase 3 term 4: ', Phase3_4.simplify_full()) show('Phase 3 term 5: ', Phase3_5.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) Phase3_3 = Phase3_3(g2 = g2s) 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('Phase 3 term 3: ', Phase3_3.simplify_full()) show('Phase 3 term 4: ', Phase3_4.simplify_full()) show('Phase 3 term 5: ', Phase3_5.simplify_full()) ss = solve([Phase2 == Phase3_1], s)[0] show('--------------------------------------------------------------------') show('Balance Phase 2 and Phase 3 by setting:') show(ss) ss = ss.rhs() Phase2 = Phase2(s = ss) Phase3_1 = Phase3_1(s = ss) Phase3_2 = Phase3_2(s = ss) Phase3_3 = Phase3_3(s = ss) Phase3_4 = Phase3_4(s = ss) 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('Phase 3 term 3: ', Phase3_3.simplify_full()) show('Phase 3 term 4: ', Phase3_4.simplify_full()) show('Phase 3 term 5: ', Phase3_5.simplify_full()) show('--------------------------------------------------------------------') show('Optimize the complexity by setting: ') show(g1 == n - l) Phase2 = Phase2(g1 = n - l) Phase3_1 = Phase3_1(g1 = n - l) Phase3_2 = Phase3_2(g1 = n - l) Phase3_3 = Phase3_3(g1 = n - l) Phase3_4 = Phase3_4(g1 = n - l) 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('Phase 3 term 3: ', Phase3_3.simplify_full()) show('Phase 3 term 4: ', Phase3_4.simplify_full()) show('Phase 3 term 5: ', Phase3_5.simplify_full()) rs = solve([Phase2 == Phase3_5], r)[0] show('--------------------------------------------------------------------') show('Balance Phase 2 and Phase 3 term 5 by setting:') show(rs) rs = rs.rhs() show('This balance only valid under the restriction: ') show(restriction_r) show('Which implies: ') bound_l = solve([rs <= l/2, l < n], l)[-1] show(bound_l[0]) show('--------------------------------------------------------------------') Phase1_case1 = Phase1(r = rs) Phase2_case1 = Phase2(r = rs) Phase3_1_case1 = Phase3_1(r = rs) Phase3_2_case1 = Phase3_2(r = rs) Phase3_3_case1 = Phase3_3(r = rs) Phase3_4_case1 = Phase3_4(r = rs) Phase3_5_case1 = Phase3_5(r = rs) show('--------------------------------------------------------------------') show('For the case') show(bound_l[0]) show('Complexity of Phases are (log2): ') show('Phase 1: ', Phase1_case1) show('Phase 2: ', Phase2_case1) show('Phase 3 term 1: ', Phase3_1_case1.simplify_full()) show('Phase 3 term 2: ', Phase3_2_case1.simplify_full()) show('Phase 3 term 3: ', Phase3_3_case1.simplify_full()) show('Phase 3 term 4: ', Phase3_4_case1.simplify_full()) show('Phase 3 term 5: ', Phase3_5_case1.simplify_full()) ls = n / 2 show('--------------------------------------------------------------------') show('The optimal complexity is (log2):') show('Phase1: ', Phase1_case1(l = ls).simplify_full()) show('Phase2: ', Phase2_case1(l = ls).simplify_full()) show('Phase 3, term 1:', Phase3_1_case1(l = ls).simplify_full()) show('Phase 3, term 2:', Phase3_2_case1(l = ls).simplify_full()) show('Phase 3, term 3:', Phase3_3_case1(l = ls).simplify_full()) show('Phase 3, term 4:', Phase3_4_case1(l = ls).simplify_full()) show('Phase 3, term 5:', Phase3_5_case1(l = ls).simplify_full()) show('Obtained for ') show(ls) show('--------------------------------------------------------------------') bound_l_low = (bound_l[0].rhs() <= bound_l[0].lhs()) rs = (r == l/2) Phase1_case2 = Phase1(r = l / 2) Phase2_case2 = Phase2(r = l / 2) Phase3_1_case2 = Phase3_1(r = l / 2) Phase3_2_case2 = Phase3_2(r = l / 2) Phase3_3_case2 = Phase3_3(r = l / 2) Phase3_4_case2 = Phase3_4(r = l / 2) Phase3_5_case2 = Phase3_5(r = l / 2) show('--------------------------------------------------------------------') show('For the case') show(bound_l_low) show('Set: ', rs) show('Complexity of Phases are (log2): ') show('Phase 1: ', Phase1_case2) show('Phase 2: ', Phase2_case2) show('Phase 3 term 1: ', Phase3_1_case2.simplify_full()) show('Phase 3 term 2: ', Phase3_2_case2.simplify_full()) show('Phase 3 term 3: ', Phase3_3_case2.simplify_full()) show('Phase 3 term 4: ', Phase3_4_case2.simplify_full()) show('Phase 3 term 5: ', Phase3_5_case2.simplify_full()) ls = bound_l_low.rhs() show('--------------------------------------------------------------------') show('The optimal complexity is (log2):') show('Phase1: ', Phase1_case1(l = ls).simplify_full()) show('Phase2: ', Phase2_case1(l = ls).simplify_full()) show('Phase 3, term 1:', Phase3_1_case1(l = ls).simplify_full()) show('Phase 3, term 2:', Phase3_2_case1(l = ls).simplify_full()) show('Phase 3, term 3:', Phase3_3_case1(l = ls).simplify_full()) show('Phase 3, term 4:', Phase3_4_case1(l = ls).simplify_full()) show('Phase 3, term 5:', Phase3_5_case1(l = ls).simplify_full()) show('Obtained for ') show(ls) show('--------------------------------------------------------------------')
--------------------------------------------------------------------
Complexity of Phases are (log2):
Phase 1: l\displaystyle l
Phase 2: g1+n+s\displaystyle -g_{1} + n + s
Phase 3 term 1: g2\displaystyle g_{2}
Phase 3 term 2: 3g1g2rs\displaystyle 3 \, g_{1} - g_{2} - r - s
Phase 3 term 3: 3g1+g2+l2nrs\displaystyle 3 \, g_{1} + g_{2} + l - 2 \, n - r - s
Phase 3 term 4: 2g1+lnr\displaystyle 2 \, g_{1} + l - n - r
Phase 3 term 5: 12n+2r\displaystyle \frac{1}{2} \, n + 2 \, r
--------------------------------------------------------------------
--------------------------------------------------------------------
Balance the first two terms in Phase 3 by setting:
g2=32g112r12s\displaystyle g_{2} = \frac{3}{2} \, g_{1} - \frac{1}{2} \, r - \frac{1}{2} \, s
--------------------------------------------------------------------
Complexity of Phases are (log2):
Phase 1: l\displaystyle l
Phase 2: g1+n+s\displaystyle -g_{1} + n + s
Phase 3 term 1: 32g112r12s\displaystyle \frac{3}{2} \, g_{1} - \frac{1}{2} \, r - \frac{1}{2} \, s
Phase 3 term 2: 32g112r12s\displaystyle \frac{3}{2} \, g_{1} - \frac{1}{2} \, r - \frac{1}{2} \, s
Phase 3 term 3: 92g1+l2n32r32s\displaystyle \frac{9}{2} \, g_{1} + l - 2 \, n - \frac{3}{2} \, r - \frac{3}{2} \, s
Phase 3 term 4: 2g1+lnr\displaystyle 2 \, g_{1} + l - n - r
Phase 3 term 5: 12n+2r\displaystyle \frac{1}{2} \, n + 2 \, r
--------------------------------------------------------------------
Balance Phase 2 and Phase 3 by setting:
s=53g123n13r\displaystyle s = \frac{5}{3} \, g_{1} - \frac{2}{3} \, n - \frac{1}{3} \, r
--------------------------------------------------------------------
Complexity of Phases are (log2):
Phase 1: l\displaystyle l
Phase 2: 23g1+13n13r\displaystyle \frac{2}{3} \, g_{1} + \frac{1}{3} \, n - \frac{1}{3} \, r
Phase 3 term 1: 23g1+13n13r\displaystyle \frac{2}{3} \, g_{1} + \frac{1}{3} \, n - \frac{1}{3} \, r
Phase 3 term 2: 23g1+13n13r\displaystyle \frac{2}{3} \, g_{1} + \frac{1}{3} \, n - \frac{1}{3} \, r
Phase 3 term 3: 2g1+lnr\displaystyle 2 \, g_{1} + l - n - r
Phase 3 term 4: 2g1+lnr\displaystyle 2 \, g_{1} + l - n - r
Phase 3 term 5: 12n+2r\displaystyle \frac{1}{2} \, n + 2 \, r
--------------------------------------------------------------------
Optimize the complexity by setting:
g1=l+n\displaystyle g_{1} = -l + n
--------------------------------------------------------------------
Complexity of Phases are (log2):
Phase 1: l\displaystyle l
Phase 2: 23l+n13r\displaystyle -\frac{2}{3} \, l + n - \frac{1}{3} \, r
Phase 3 term 1: 23l+n13r\displaystyle -\frac{2}{3} \, l + n - \frac{1}{3} \, r
Phase 3 term 2: 23l+n13r\displaystyle -\frac{2}{3} \, l + n - \frac{1}{3} \, r
Phase 3 term 3: l+nr\displaystyle -l + n - r
Phase 3 term 4: l+nr\displaystyle -l + n - r
Phase 3 term 5: 12n+2r\displaystyle \frac{1}{2} \, n + 2 \, r
--------------------------------------------------------------------
Balance Phase 2 and Phase 3 term 5 by setting:
r=27l+314n\displaystyle r = -\frac{2}{7} \, l + \frac{3}{14} \, n
This balance only valid under the restriction:
2rl\displaystyle 2 \, r \leq l
Which implies:
311n<l\displaystyle \frac{3}{11} \, n < l
--------------------------------------------------------------------
--------------------------------------------------------------------
For the case
311n<l\displaystyle \frac{3}{11} \, n < l
Complexity of Phases are (log2):
Phase 1: l\displaystyle l
Phase 2: 47l+1314n\displaystyle -\frac{4}{7} \, l + \frac{13}{14} \, n
Phase 3 term 1: 47l+1314n\displaystyle -\frac{4}{7} \, l + \frac{13}{14} \, n
Phase 3 term 2: 47l+1314n\displaystyle -\frac{4}{7} \, l + \frac{13}{14} \, n
Phase 3 term 3: 57l+1114n\displaystyle -\frac{5}{7} \, l + \frac{11}{14} \, n
Phase 3 term 4: 57l+1114n\displaystyle -\frac{5}{7} \, l + \frac{11}{14} \, n
Phase 3 term 5: 47l+1314n\displaystyle -\frac{4}{7} \, l + \frac{13}{14} \, n
--------------------------------------------------------------------
The optimal complexity is (log2):
Phase1: 12n\displaystyle \frac{1}{2} \, n
Phase2: 914n\displaystyle \frac{9}{14} \, n
Phase 3, term 1: 914n\displaystyle \frac{9}{14} \, n
Phase 3, term 2: 914n\displaystyle \frac{9}{14} \, n
Phase 3, term 3: 37n\displaystyle \frac{3}{7} \, n
Phase 3, term 4: 37n\displaystyle \frac{3}{7} \, n
Phase 3, term 5: 914n\displaystyle \frac{9}{14} \, n
Obtained for
12n\displaystyle \frac{1}{2} \, n
--------------------------------------------------------------------
--------------------------------------------------------------------
For the case
l311n\displaystyle l \leq \frac{3}{11} \, n
Set: r=12l\displaystyle r = \frac{1}{2} \, l
Complexity of Phases are (log2):
Phase 1: l\displaystyle l
Phase 2: 56l+n\displaystyle -\frac{5}{6} \, l + n
Phase 3 term 1: 56l+n\displaystyle -\frac{5}{6} \, l + n
Phase 3 term 2: 56l+n\displaystyle -\frac{5}{6} \, l + n
Phase 3 term 3: 32l+n\displaystyle -\frac{3}{2} \, l + n
Phase 3 term 4: 32l+n\displaystyle -\frac{3}{2} \, l + n
Phase 3 term 5: l+12n\displaystyle l + \frac{1}{2} \, n
--------------------------------------------------------------------
The optimal complexity is (log2):
Phase1: 311n\displaystyle \frac{3}{11} \, n
Phase2: 1722n\displaystyle \frac{17}{22} \, n
Phase 3, term 1: 1722n\displaystyle \frac{17}{22} \, n
Phase 3, term 2: 1722n\displaystyle \frac{17}{22} \, n
Phase 3, term 3: 1322n\displaystyle \frac{13}{22} \, n
Phase 3, term 4: 1322n\displaystyle \frac{13}{22} \, n
Phase 3, term 5: 1722n\displaystyle \frac{17}{22} \, n
Obtained for
311n\displaystyle \frac{3}{11} \, n
--------------------------------------------------------------------