SharedXOR_MCFG_IS.sagewsOpen in CoCalc
Multi-cycles-Interchange-structure-based attack on the XOR combiner of two hash functions
n = var('n')
l = var('l')
s = var('s')
t = var('t')
r = var('r')

restriction_l = (l >= n/2)
restriction_r = ( 2*r <=l)

Step1 = l
Step2 = n / 2
Step3 = n / 2 + s
Step4 = t
Step5_1 = n - t + r + n - s -2 * r - l
Step5_2 = n / 2 + 2 * r
Step6 = l

show('--------------------------------------------------------------------')
show('Complexity of Phases are (log2): ')
show('Step 1: ', Step1.simplify_full())
show('Step 2: ', Step2.simplify_full())
show('Step 3: ', Step3.simplify_full())
show('Step 4: ', Step4.simplify_full())
show('Step 5 term 1: ', Step5_1.simplify_full())
show('Step 5 term 2: ', Step5_2.simplify_full())
show('Step 6: ', Step6.simplify_full())
show('--------------------------------------------------------------------')

ts, ss, rs = solve([Step3 == Step4, Step3 == Step5_1, Step3 == Step5_2], t, s, r)[0]
show('--------------------------------------------------------------------')
show('Balance the Step 3, 4, and 5 by setting: ')
show(ts)
show(ss)
show(rs)
ts = ts.rhs()
ss = ss.rhs()
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])

Step3  = Step3(t = ts, s = ss, r = rs)
Step4  = Step4(t = ts, s = ss, r = rs)
Step5_1  = Step5_1(t = ts, s = ss, r = rs)
Step5_2  = Step5_2(t = ts, s = ss, r = rs)

show('--------------------------------------------------------------------')
show('Complexity of Phases are (log2): ')
show('Step 1: ', Step1.simplify_full())
show('Step 2: ', Step2.simplify_full())
show('Step 3: ', Step3.simplify_full())
show('Step 4: ', Step4.simplify_full())
show('Step 5 term 1: ', Step5_1.simplify_full())
show('Step 5 term 2: ', Step5_2.simplify_full())
show('Step 6: ', Step6.simplify_full())

ls = solve([Step1 == Step3], l)[0]

Step1 = Step1(l = ls.rhs())
Step2  = Step2(l = ls.rhs())
Step3 = Step3(l = ls.rhs())
Step4 = Step4(l = ls.rhs())
Step5_1 = Step5_1(l = ls.rhs())
Step5_2 = Step5_2(l = ls.rhs())
Step6 = Step6(l = ls.rhs())

show('--------------------------------------------------------------------')
show('The optimal complexity is (log2):')
show('Step 1: ', Step1.simplify_full())
show('Step 2: ', Step2.simplify_full())
show('Step 3: ', Step3.simplify_full())
show('Step 4: ', Step4.simplify_full())
show('Step 5 term 1: ', Step5_1.simplify_full())
show('Step 5 term 2: ', Step5_2.simplify_full())
show('Step 6: ', Step6.simplify_full())
show('Obtained for ')
show(ls)
show('--------------------------------------------------------------------')
--------------------------------------------------------------------
Complexity of Phases are (log2):
Step 1: $\displaystyle l$
Step 2: $\displaystyle \frac{1}{2} \, n$
Step 3: $\displaystyle \frac{1}{2} \, n + s$
Step 4: $\displaystyle t$
Step 5 term 1: $\displaystyle -l + 2 \, n - r - s - t$
Step 5 term 2: $\displaystyle \frac{1}{2} \, n + 2 \, r$
Step 6: $\displaystyle l$
--------------------------------------------------------------------
--------------------------------------------------------------------
Balance the Step 3, 4, and 5 by setting:
$\displaystyle t = -\frac{2}{7} \, l + \frac{11}{14} \, n$
$\displaystyle s = -\frac{2}{7} \, l + \frac{2}{7} \, n$
$\displaystyle r = -\frac{1}{7} \, l + \frac{1}{7} \, n$
This balance only valid under the restriction:
$\displaystyle 2 \, r \leq l$
Which implies:
$\displaystyle \frac{2}{9} \, n < l$
--------------------------------------------------------------------
Complexity of Phases are (log2):
Step 1: $\displaystyle l$
Step 2: $\displaystyle \frac{1}{2} \, n$
Step 3: $\displaystyle -\frac{2}{7} \, l + \frac{11}{14} \, n$
Step 4: $\displaystyle -\frac{2}{7} \, l + \frac{11}{14} \, n$
Step 5 term 1: $\displaystyle -\frac{2}{7} \, l + \frac{11}{14} \, n$
Step 5 term 2: $\displaystyle -\frac{2}{7} \, l + \frac{11}{14} \, n$
Step 6: $\displaystyle l$
--------------------------------------------------------------------
The optimal complexity is (log2):
Step 1: $\displaystyle \frac{11}{18} \, n$
Step 2: $\displaystyle \frac{1}{2} \, n$
Step 3: $\displaystyle \frac{11}{18} \, n$
Step 4: $\displaystyle \frac{11}{18} \, n$
Step 5 term 1: $\displaystyle \frac{11}{18} \, n$
Step 5 term 2: $\displaystyle \frac{11}{18} \, n$
Step 6: $\displaystyle \frac{11}{18} \, n$
Obtained for
$\displaystyle l = \frac{11}{18} \, n$
--------------------------------------------------------------------