Problemă generală / Introducere: criptarea relației (calculabile) între două numere aleatorii care sunt membre ale unui set cât mai mic posibil, în timp ce orice, cu excepția ordinii de execuție, este cunoscut de adversar.
Această întrebare este despre rezolvarea acelei probleme cu o concatenare a cifrului bloc.
Simplificare:
- luăm în considerare doar bloc-cifre care sunt similare cu AES
- în loc de $N$ bloc-cifre diferite cu care folosim un cifr-bloc $N$ taste diferite (sau chiar mai multe)
- cifrul bloc transferă doar o intrare la alta (deci rulează în modul ECB)
Ce se știe:
Dacă aplicăm un cifr-bloc $BC$ la o intrare dată $m$ iar și iar vom ajunge la intrare la un moment dat din nou.
$$BC^l(m,k) = m$$
Pentru o intrare aleatorie dată $m$ și cheie $k$ lungimea ciclului $l$ poate avea orice lungime de la $1$ la dimensiunea domeniului de $m$ cu (în cazul optim) aceeași probabilitate fiecare.
(destul de sigur că este și cazul:)
Dacă folosim $N$ chei diferite și concatenează cifrul bloc cu acele chei una pe cealaltă (întotdeauna aceeași ordine și întotdeauna multiplu de $N$ pași) rezultă lungimi de ciclu $N$ ori $[1,...,D]$ cu $D$ dimensiunea domeniului lui m.
$$BC(....BC(...BC(..BC(BC(BC(m,k_0),k_1),k_2)...,k_{N-1})...,k_{i \mod{N}})....,k_{l \equiv N-1 \mod{N}}) = m$$
Putem vedea această concatenare ca aplicarea de runde în interiorul unui singur BC.
Aplicând-o la problema generală de mai sus:
Pentru aceasta ordinea de execuție (deci ordinea cheilor folosite) este necunoscută adversarului (dar cheile în sine sunt cunoscute).
De exemplu o valoare $V$ poate fi calculat din valoare $W$ cu:
$$BC(BC(BC(BC(BC(W,k_5),k_2),k_3,k_5,k_1,k_1) =V$$
Adversarul chiar știe $V,W$ și, de asemenea, cheia de la sine, dar vrea să știe ordinea de execuție a cheii $5,2,3,5,1,1$ sau orice altă comandă care face și treaba.
Dacă nu mai folosim o comandă fixă a cheilor, proprietățile mărimii ciclului nu mai sunt valabile.
Încercarea soluției 1 (eșuată):
Dacă adversarul vrea să găsească un ordin de executare care transferă $W \rightarrow V$
el poate calcula $N$ posibile următoarele valori ale $W$ si $N$ posibile valori anterioare ale $V$ cu inversul BC. El poate repeta asta până când un mach a fost găsit.
Cu aceasta ar trebui să găsească un ordin de execuție în medie prin aproximativ $\sqrt{D}$ pași care nu sunt suficient de siguri.
Încercarea soluției 2 (eșuată):
Pentru o securitate mai mare limităm rezultatul $V$ la valorile care au fost calculate folosind $i$-a cheie la ultimul lor calcul BC.
Adversarul poate folosi doar inversul BC la asta $V$ cu ținta $i$-a cheie și procedați la fel ca în încercarea soluției 1.
Încercarea soluției 3 (întrebare/editare: eșuată...):
Pentru a câștiga securitate, putem limita numărul de execuție la multiplu de $E$ trepte și cu aceasta alterând și cheile fiecărei adâncimi.
Pe lângă utilizarea $i$-a cheie BC pentru calculul $V$ acum trebuie să fie și un multiplu al $E$ pași înaintea $W$
în exemplul nostru de sus cu $E=3$ asta ar fi:
$$BC(BC(BC(BC(BC(W,k_5^0),k_2^1),k_3^2,k_5^0,k_1^1,k_1^2)) =V$$
Deci pentru un dat $V$ cu $i$-ultima cheie la adâncime $d$ adversarul poate calcula relația cu un dat $W$ cu profunzime $d$:
Calculul inversului lui $V$:
$$BC^{-1}(V,k_i^{d-1 \mod E}) = V'$$
Și calculați valorile pas cu pas, așa cum a făcut în încercarea 1 a soluției.
Acest lucru ar trebui să dureze aproximativ $N^{\lfloor{\frac{E-1}{2}}\rfloor}$ încercări dacă o face cu forță brută.
Dacă de exemplu $D=2^{128}, N=2^{16}, E=2^{5}$ asta ar fi $2^{16 \cdot 15} = 2^{240}$ încercări.
.... după ce am scris tot acest text, am observat că nu are nevoie să calculeze fiecare parte din fiecare adâncime și doar are nevoie $\sqrt{D}$ pași din nou...
=====>
Întrebare: Are cineva vreo altă idee cum poate fi mai sigură o concatenare a cifrului bloc (aproape de $D$)?
Histroy
- $D$ dimensiunea setului de intrare și ieșire
- $V,W$ valori aleatorii care pot avea până la $D$ valori diferite
- $E$ numărul total de execuții de cifrare bloc trebuie să fie multiplu de $E$
- $N$ numărul de chei bloc-cifrare diferite pentru fiecare adâncime
- $k_a^b$ variabilă cheie folosită pentru cifrul bloc cu indici $a,b$ cu $a\în\{0,N-1\}, b\în\{0,E-1\}$
