SharedZipper_MCFG.sagewsOpen in CoCalc
Multi-cycles-base attack on Zipper of $k$ hash functions
n = var('n')
l = var('l')
lp = var('lp')
k = var('k')
kappa = var('kappa')
s = var('s')
t = var('t')
d = var('d')
r = var('r')

Step1 = n / 2
Step2 = t
Step3 = n / 2
Step4 = lp
Step5 = n - l
Step6 = r + n - t

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: ', Step5.simplify_full())
show('Step 6: ', Step6.simplify_full())
show('--------------------------------------------------------------------')

pairs1 = 2 * r
pairs2 = k * n - (k + 1) * n / 2 + n / 2 - lp
pairs_eq = (pairs1 == pairs2)
show('--------------------------------------------------------------------')
show('When the message length is not limited: ')
show('the success of the attack requires: ', pairs_eq)
rs = solve([pairs_eq], r)[0]
show('which implies: ', rs)
rs = rs.rhs()

Step6 = Step6(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: ', Step5.simplify_full())
show('Step 6: ', Step6.simplify_full())

show('--------------------------------------------------------------------')
show('Optimize the complexity by setting: ')
ts, lps = solve([Step2 == Step6, Step2 == Step4], t, lp)[0]
show(ts)
show(lps)
ts = ts.rhs()
lps = lps.rhs()

Step2  = Step2(t = ts, lp = lps)
Step4  = Step4(t = ts, lp = lps)
Step6  = Step6(t = ts, lp = lps)
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: ', Step5.simplify_full())
show('Step 6: ', Step6.simplify_full())
show('--------------------------------------------------------------------')

for i in range(2, 7):
show(' ------------------------------ ', k == i, ' ------------------------------')
Step2cplx = Step2(k = i)
Step2cplxs = Step2cplx(kappa=log(i, 2)).simplify_full()
show('Complexity is: ', Step2cplxs)

--------------------------------------------------------------------
Complexity of Phases are (log2):
Step 1: $\displaystyle \frac{1}{2} \, n$
Step 2: $\displaystyle t$
Step 3: $\displaystyle \frac{1}{2} \, n$
Step 4: $\displaystyle \mathit{lp}$
Step 5: $\displaystyle -l + n$
Step 6: $\displaystyle n + r - t$
--------------------------------------------------------------------
--------------------------------------------------------------------
When the message length is not limited:
the success of the attack requires: $\displaystyle 2 \, r = -\frac{1}{2} \, {\left(k + 1\right)} n + k n - \mathit{lp} + \frac{1}{2} \, n$
which implies: $\displaystyle r = \frac{1}{4} \, k n - \frac{1}{2} \, \mathit{lp}$
--------------------------------------------------------------------
Complexity of Phases are (log2):
Step 1: $\displaystyle \frac{1}{2} \, n$
Step 2: $\displaystyle t$
Step 3: $\displaystyle \frac{1}{2} \, n$
Step 4: $\displaystyle \mathit{lp}$
Step 5: $\displaystyle -l + n$
Step 6: $\displaystyle \frac{1}{4} \, {\left(k + 4\right)} n - \frac{1}{2} \, \mathit{lp} - t$
--------------------------------------------------------------------
Optimize the complexity by setting:
$\displaystyle t = \frac{1}{10} \, {\left(k + 4\right)} n$
$\displaystyle \mathit{lp} = \frac{1}{10} \, {\left(k + 4\right)} n$
--------------------------------------------------------------------
Complexity of Phases are (log2):
Step 1: $\displaystyle \frac{1}{2} \, n$
Step 2: $\displaystyle \frac{1}{10} \, {\left(k + 4\right)} n$
Step 3: $\displaystyle \frac{1}{2} \, n$
Step 4: $\displaystyle \frac{1}{10} \, {\left(k + 4\right)} n$
Step 5: $\displaystyle -l + n$
Step 6: $\displaystyle \frac{1}{10} \, {\left(k + 4\right)} n$
--------------------------------------------------------------------
------------------------------ $\displaystyle k = 2$ ------------------------------
Complexity is: $\displaystyle \frac{3}{5} \, n$
------------------------------ $\displaystyle k = 3$ ------------------------------
Complexity is: $\displaystyle \frac{7}{10} \, n$
------------------------------ $\displaystyle k = 4$ ------------------------------
Complexity is: $\displaystyle \frac{4}{5} \, n$
------------------------------ $\displaystyle k = 5$ ------------------------------
Complexity is: $\displaystyle \frac{9}{10} \, n$
------------------------------ $\displaystyle k = 6$ ------------------------------
Complexity is: $\displaystyle n$