SharedXOR_DIFG_IS.sagewsOpen in CoCalc
Deep-iterates-Interchange-structure-based attack on the XOR combiner of two hash functions
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: $\displaystyle l$
Phase 2: $\displaystyle -g_{1} + n + s$
Phase 3 term 1: $\displaystyle g_{2}$
Phase 3 term 2: $\displaystyle 3 \, g_{1} - g_{2} - r - s$
Phase 3 term 3: $\displaystyle 3 \, g_{1} + g_{2} + l - 2 \, n - r - s$
Phase 3 term 4: $\displaystyle 2 \, g_{1} + l - n - r$
Phase 3 term 5: $\displaystyle \frac{1}{2} \, n + 2 \, r$
--------------------------------------------------------------------
--------------------------------------------------------------------
Balance the first two terms in Phase 3 by setting:
$\displaystyle g_{2} = \frac{3}{2} \, g_{1} - \frac{1}{2} \, r - \frac{1}{2} \, s$
--------------------------------------------------------------------
Complexity of Phases are (log2):
Phase 1: $\displaystyle l$
Phase 2: $\displaystyle -g_{1} + n + s$
Phase 3 term 1: $\displaystyle \frac{3}{2} \, g_{1} - \frac{1}{2} \, r - \frac{1}{2} \, s$
Phase 3 term 2: $\displaystyle \frac{3}{2} \, g_{1} - \frac{1}{2} \, r - \frac{1}{2} \, s$
Phase 3 term 3: $\displaystyle \frac{9}{2} \, g_{1} + l - 2 \, n - \frac{3}{2} \, r - \frac{3}{2} \, s$
Phase 3 term 4: $\displaystyle 2 \, g_{1} + l - n - r$
Phase 3 term 5: $\displaystyle \frac{1}{2} \, n + 2 \, r$
--------------------------------------------------------------------
Balance Phase 2 and Phase 3 by setting:
$\displaystyle s = \frac{5}{3} \, g_{1} - \frac{2}{3} \, n - \frac{1}{3} \, r$
--------------------------------------------------------------------
Complexity of Phases are (log2):
Phase 1: $\displaystyle l$
Phase 2: $\displaystyle \frac{2}{3} \, g_{1} + \frac{1}{3} \, n - \frac{1}{3} \, r$
Phase 3 term 1: $\displaystyle \frac{2}{3} \, g_{1} + \frac{1}{3} \, n - \frac{1}{3} \, r$
Phase 3 term 2: $\displaystyle \frac{2}{3} \, g_{1} + \frac{1}{3} \, n - \frac{1}{3} \, r$
Phase 3 term 3: $\displaystyle 2 \, g_{1} + l - n - r$
Phase 3 term 4: $\displaystyle 2 \, g_{1} + l - n - r$
Phase 3 term 5: $\displaystyle \frac{1}{2} \, n + 2 \, r$
--------------------------------------------------------------------
Optimize the complexity by setting:
$\displaystyle g_{1} = -l + n$
--------------------------------------------------------------------
Complexity of Phases are (log2):
Phase 1: $\displaystyle l$
Phase 2: $\displaystyle -\frac{2}{3} \, l + n - \frac{1}{3} \, r$
Phase 3 term 1: $\displaystyle -\frac{2}{3} \, l + n - \frac{1}{3} \, r$
Phase 3 term 2: $\displaystyle -\frac{2}{3} \, l + n - \frac{1}{3} \, r$
Phase 3 term 3: $\displaystyle -l + n - r$
Phase 3 term 4: $\displaystyle -l + n - r$
Phase 3 term 5: $\displaystyle \frac{1}{2} \, n + 2 \, r$
--------------------------------------------------------------------
Balance Phase 2 and Phase 3 term 5 by setting:
$\displaystyle r = -\frac{2}{7} \, l + \frac{3}{14} \, n$
This balance only valid under the restriction:
$\displaystyle 2 \, r \leq l$
Which implies:
$\displaystyle \frac{3}{11} \, n < l$
--------------------------------------------------------------------
--------------------------------------------------------------------
For the case
$\displaystyle \frac{3}{11} \, n < l$
Complexity of Phases are (log2):
Phase 1: $\displaystyle l$
Phase 2: $\displaystyle -\frac{4}{7} \, l + \frac{13}{14} \, n$
Phase 3 term 1: $\displaystyle -\frac{4}{7} \, l + \frac{13}{14} \, n$
Phase 3 term 2: $\displaystyle -\frac{4}{7} \, l + \frac{13}{14} \, n$
Phase 3 term 3: $\displaystyle -\frac{5}{7} \, l + \frac{11}{14} \, n$
Phase 3 term 4: $\displaystyle -\frac{5}{7} \, l + \frac{11}{14} \, n$
Phase 3 term 5: $\displaystyle -\frac{4}{7} \, l + \frac{13}{14} \, n$
--------------------------------------------------------------------
The optimal complexity is (log2):
Phase1: $\displaystyle \frac{1}{2} \, n$
Phase2: $\displaystyle \frac{9}{14} \, n$
Phase 3, term 1: $\displaystyle \frac{9}{14} \, n$
Phase 3, term 2: $\displaystyle \frac{9}{14} \, n$
Phase 3, term 3: $\displaystyle \frac{3}{7} \, n$
Phase 3, term 4: $\displaystyle \frac{3}{7} \, n$
Phase 3, term 5: $\displaystyle \frac{9}{14} \, n$
Obtained for
$\displaystyle \frac{1}{2} \, n$
--------------------------------------------------------------------
--------------------------------------------------------------------
For the case
$\displaystyle l \leq \frac{3}{11} \, n$
Set: $\displaystyle r = \frac{1}{2} \, l$
Complexity of Phases are (log2):
Phase 1: $\displaystyle l$
Phase 2: $\displaystyle -\frac{5}{6} \, l + n$
Phase 3 term 1: $\displaystyle -\frac{5}{6} \, l + n$
Phase 3 term 2: $\displaystyle -\frac{5}{6} \, l + n$
Phase 3 term 3: $\displaystyle -\frac{3}{2} \, l + n$
Phase 3 term 4: $\displaystyle -\frac{3}{2} \, l + n$
Phase 3 term 5: $\displaystyle l + \frac{1}{2} \, n$
--------------------------------------------------------------------
The optimal complexity is (log2):
Phase1: $\displaystyle \frac{3}{11} \, n$
Phase2: $\displaystyle \frac{17}{22} \, n$
Phase 3, term 1: $\displaystyle \frac{17}{22} \, n$
Phase 3, term 2: $\displaystyle \frac{17}{22} \, n$
Phase 3, term 3: $\displaystyle \frac{13}{22} \, n$
Phase 3, term 4: $\displaystyle \frac{13}{22} \, n$
Phase 3, term 5: $\displaystyle \frac{17}{22} \, n$
Obtained for
$\displaystyle \frac{3}{11} \, n$
--------------------------------------------------------------------