Fibră finită de SHA512

Este acolo $y\în\{0,1\}^{512}$ cu $\emptyset \neq s^{-1}(\{y\})$ și $s^{-1}(\{y\})$ este finit?

Pentru SHA-512 așa cum este definit de fapt, trivial da, deoarece dimensiunea de intrare este limitată la $2^{128}-1$ pic. Asta face $s^{-1}(\{y\})$ adevărat pentru orice $y\în\{0,1\}^{512}$. Și $y$ hash-ul șirului de biți gol îndeplinește condiția $\emptyset \neq s^{-1}(\{y\})$. În cele ce urmează presupunem acest lucru $2^{128}-1$ limita de biți este eliminată.

Pariurile mele sunt că propunerea este acum falsă, prin următorul argument (nu o dovadă).

1. Pare plauzibil ca fiecare hash de 512 biți să fie atins de SHA-512 pentru un mesaj de cel mult 895 de biți (cel mai mare mesaj aliniat la bloc care necesită o singură rundă). Argument: în conformitate cu un model de cifru bloc ideal pentru cifrul bloc din inima unei runde SHA-512, fiecare dintre hash-ul unui astfel de mesaj este aleatoriu și independent în $\{0,1\}^{512}$. Langa legat de colector de cupoane, ne așteptăm să obținem toate valorile după aproximativ $2^{520.5}$ trage, iar estimarea cozii în esență exclude (probabilitate $<2^{-(2^{384})}$) nu le-am primi pe toate după $2^{896}-1$ încercări. În mod realist, acest lucru ar putea eșua doar dacă modelul nostru este extrem de prost.

2. Este și mai plauzibil ca fiecare hash de 512 biți să fie atins de SHA-512 pentru un mesaj de cel mult 1919 de biți (cel mai mare mesaj aliniat la bloc care necesită două runde), deoarece cu două runde numărul de intrări posibile în primele runde atinge $2^{1024}$, făcând (prin argumentul 1) probabil atât de aproape de $2^{512}$ valorile pot ajunge la intrarea de stare de 512 biți a rundei a doua; și primim $2^{896}-1$ blocuri de introducere a mesajelor ca în prima rundă. Astfel, am depășit și mai mult limita colectorului de cupoane și, mai important, din moment ce avem încă 512 biți de intrare care variază, pare și mai puțin probabil ca modelul nostru să fie atât de rău.

3. Acest raționament pentru a doua rundă poate fi repetat pentru orice număr mai mare de runde, conducând la concluzia că fiecare valoare în $\{0,1\}^{512}$ probabil este atins cel mult rotund.

4. Ar fi și mai surprinzător că atunci când lăsăm lungimea mesajului modulo $2^{128}$ ia toate valorile posibile, oricare dintre $2^{512}$ valorile sunt atinse pentru niciun mesaj $2^{128}$ la $2^{129-1}$ bit: avem aproape o intrare suplimentară de 128 de biți care poate varia.

5. Și apoi, din moment ce lungimea mesajului este permisă să crească la nesfârșit, obținem probabilitatea, oricare $y$ are infinit $s^{-1}(\{y\})$.

6. The $\emptyset \neq s^{-1}(\{y\})$ o parte a propoziției o face și mai puțin probabil să se țină. Să presupunem că pe 512 biți valoarea inițială a lui SHA-512 se ajunge din nou (intern) după $2^{119}$ runde pentru cel puțin una (să zicem $w$) din $2^{(2^{129})}$ diferite mesaje începe de $2^{129}$ biți, care este probabil conform unei versiuni ușor modificate a 3 de mai sus (avem libertate deplină pentru fiecare dintre $2^{119}$ Blocuri de intrare pe 1024 de biți ale $w$). Acum dacă un anumit $y\în\{0,1\}^{512}$ este $\operatorname{SHA-512}(x)$, atunci este și $\operatorname{SHA-512}(w\mathbin\|x)$ si mai general $\operatorname{SHA-512}(w\mathbin\|\ldots\mathbin\|w\mathbin\|x)$ infirmând astfel în mod constructiv propunerea.