Panama (hash-funktio)

Panama [1] on kryptografinen primitiivi, jota voidaan käyttää joko kryptografisena hash-funktiona tai virtasalauksena. Joan Dymen ja Craig Klep kehittivät sen vuonna 1998 parantamaan ohjelmistojen tehokkuutta 32-bittisille arkkitehtuureille. Se on yksi Keccak- hajautusalgoritmin edeltäjistä, josta tuli US National Institute of Standards and Technology -instituutin [2] kryptografisten primitiivien kilpailun voittaja . Luottaa voimakkaasti StepRightUp-suoratoiston hash-moduuliin. [3]

Ominaisuudet

Kehittäjien mukaan "Panamalla" oli kehityshetkellä korkea turvallisuustaso, mutta tämä saavutettiin valtavan laskentakuorman kustannuksella. Siksi, kuten kävi ilmi, "Panama" hash-funktiona osoittautui vähemmän sopivaksi viestien hajauttamiseen kuin sen kilpailijat. Jos puhumme "Panamasta" stream-salauksena, niin pitkä alustusmenettely osoittautui sen käytön erottuvaksi piirteeksi. Siksi, kun sitä käytetään tehtävissä, jotka vaativat suuria nopeuksia, on välttämätöntä tarjota kaikki olosuhteet, joilla pyritään vähentämään synkronoinnin määrää. [neljä]

Oletettiin, että "Panamaa" käytettäisiin videon salaamiseen tai salauksen purkamiseen päästäkseen joihinkin sovelluksiin, erityisesti "maksutelevisioon". [5] Kehittäjien logiikka oli, että digisovittimet ja digitelevisiot käyttäisivät nopeita prosessoreita, ja Panama ei kuormittaisi näitä prosessoreita liikaa salauksen purkamisen aikana.

Rakenne

"Panama" perustuu äärelliseen tilakoneeseen, joka koostuu kahdesta suuresta lohkosta: 544 tilabitistä ja 8192-bittisestä puskurista, joka toimii palautesiirtorekisterin periaatteella . Takaisinkytkentä varmistaa, että tulobitit käyvät läpi useita iteraatioita tulon jälkeen, mikä puolestaan varmistaa bittittäisen diffuusion. Minun on sanottava, että samanlaista puskuria käytetään SHA-pakkaustoiminnossa. [6] Panaman työobjekti on 32-bittinen sana ja tila koostuu 17 tällaisesta sanasta, kun taas puskurissa on 32 solua, joista jokainen sisältää 8 tällaista sanaa. [7]

Toiminnot

Panama voi päivittää puskurin ja tilat iteroimalla. Ja iteratiiviselle toiminnolle on toteutettu kolme tilaa: "Reset", "Push" ja "Pull". "Push"-tilassa kone vastaanottaa jonkin verran syötettä, mutta ei tulosta mitään. "Pull"-tilassa päinvastoin lähtötiedot muodostetaan, mutta mitään ei oteta syötteeksi. Myös "tyhjä vetoiteraatio" tarkoittaa, että iteroinnin tulos hylätään. "Reset"-tilassa tila ja puskuri nollataan. [kahdeksan]

Tilamuutokselle on ominaista korkea diffuusio ja hajautunut epälineaarisuus. [9] Tämä tarkoittaa, että pieni iteraatioiden määrä riittää hyvän dispersion saavuttamiseen. Tämä tehdään käyttämällä 4 lohkoa, joista jokainen ratkaisee oman tehtävänsä.

Ensimmäinen ratkaisee epälineaarisuuden ongelman.
Toinen tarjoaa bittikohtaisen dispersion.
Kolmas luo bittisuuntaisen diffuusion.
Neljäs sisältää puskurin ja syöttötiedot. [kymmenen]

Jos pidämme "Panamaa" hash-funktiona, sen toiminnan algoritmi on seuraava. Aluksi hash-funktio hyväksyy kaikki viestilohkot. Tämän jälkeen suoritetaan vielä useita "Push" iteraatioita, jotka mahdollistavat viimeisten vastaanotettujen viestilohkojen sirottamisen puskurin ja tilan sisään. Sen jälkeen suoritetaan viimeinen "Pull" iteraatio, jonka avulla voit saada hash-tuloksen. Suoratoiston salausmenetelmä alustetaan seuraavasti: ensin suoritetaan kaksi "Push"-iteraatiota avaimen ja hajautusparametrin saamiseksi. Sen jälkeen tapahtuu useita "Pull"-iteraatioita avaimen ja parametrin hajauttamiseksi puskurin ja tilojen sisällä. Tämä viimeistelee alustuksen ja Panama on valmis luomaan bittejä lähtösekvenssistä suorittamalla "Pull" iteraatioita. [3]

Kuinka se toimii

Voit määrittää tilan muotoon , ja 17 sanaa, jotka määrittelevät tilat, voidaan nimetä nimellä . Puskuri on merkitty nimellä , sen solun -th - as , ja yksi tämän solun sisällä olevista sanoista - as . Aluksi sekä tila että puskuri täytetään vain nolilla. "Push"-tilassa "Panama" vastaanottaa 8-bittisen sanan tulona, "Pull"-tilassa 8-bittinen sana muodostetaan ulostulona. [7] $A$ $a0...a16$ $B$ $j$ ${\displaystyle b^{j))$ ${\displaystyle b_{i}^{j))$

Jos määritämme puskurin päivittävän toiminnon nimellä , jos hyväksymme sen , voimme saada seuraavat säännöt puskurin päivittämiseen: $\lambda$ $d=\lambda (b)$

{\displaystyle d^{j}=b^{j-1))

klo ,

j\notin {0...25}

d^{0}=b^{31}\oplus q

{\displaystyle d_{i}^{25}=b_{i}^{24}\oplus b_{i+2mod8}^{31))

varten

0<i<8

jossa "Push"-tilassa on syöttölohko ja "Pull"-tilassa se on osa tilaa , eli 8 sen komponentteja, jotka määritellään $q$ $s$ $A$

q_{i}=a_{i+1}

varten

0<i<8

Tila päivitetään seuraavan säännön mukaan, joka on 4 eri muunnoksen superpositio: $\rho$

\rho ={\sigma }+\theta +\pi +\gamma

jossa on käänteinen lineaarinen muunnos, on jälleen käänteinen lineaarinen muunnos, on yhdistelmä sanabittien kiertoa ja sanan sijainnin sekoitusta, ja muunnos on puskurin ja syöttösanan bittikohtainen lisäys. $\theta$ $\gamma$ $\pi$ $\sigma$

В данном случае будет определять сумму операций, где сначала выполняется та, что стоит правее. $+$

Nyt voimme harkita jokaista näistä toiminnoista. määritellään seuraavasti: $\theta$

{\displaystyle c=\theta (a)\Leftrightarrow c_{i}=a_{i}\oplus a_{i+1}\oplus a_{i+4))

varten ,

i\in {0...17}

jossa kaikki indeksit otetaan modulo . Huomaa, että tämän muunnoksen palautuvuus johtuu siitä tosiasiasta, että on koprime kanssa . $17$ ${\displaystyle 1\oplus x\oplus x^{4))$ $1\oplus x^{17}$

$\gamma$ voidaan määritellä seuraavasti:

c=\gamma (a)\Leftrightarrow c_{i}=a_{i}\oplus (a_{i+1}TAI\neg a_{i+2})

varten ,

i\in {0...17}

jossa kaikki indeksit otetaan modulo . $17$

Jos muunnokselle määritetään, että paikoissa on siirtymä vähiten merkitsevästä bitistä merkittävimpään, niin: $\pi$ $t_k$ $k$

c=\pi (a)\Leftrightarrow c_{i}=t_{k}(a_{j})

ja , ja $j=7i{}{\pmod {17}}$ $k=i(i+1)/2{\pmod {32))$

Jos muunnos suoritetaan , niin $\sigma$ $c=\sigma (a)$

{\displaystyle c_{0}=a_{0}\oplus 00000001_{hex))

{\displaystyle c_{i+1}=a_{i+1}\oplus l_{i))

varten ,

0\leqslant i<8

{\displaystyle c_{i+9}=a_{i+9}\oplus b_{i}^{16))

varten

0\leqslant i<8

"Push"-tilassa on syöttöviesti ja "Pull"-tilassa - . $l$ $s$ ${\displaystyle l=b^{4))$

Ulostulosana "Pull"-tilassa määritellään seuraavasti: $z$

z_{i}=a_{i+9}

0\leqslant i<8

. [yksitoista]

"Panama" hash-funktiona

"Panama" hash-funktiona kartoittaa 256 bitin hash-tuloksen mielivaltaisen pituiseksi viestiksi. [11] Tässä tapauksessa hajautus tapahtuu kahdessa vaiheessa $M$

$M$ muunnetaan merkkijonoksi , jonka pituus on 256:n kerrannainen lisäämällä ykkösiä. $M'$
Vastaava merkkijono ladataan "Panamaan". $M'$

Voidaan merkitä syöttölohkojen sarjana . Sitten nollahetkellä generoidaan Reset-tila, jonka jälkeen jaksojen aikana syöttölohkot ladataan. Sen jälkeen suoritetaan 32 tyhjää "Pull" iteraatiota. Ja sitten 33. "Pull"-iteraatiossa hajautustulos palautetaan . $M'$ $V$ $s$ $V$ $h$

Panama-hajautusfunktion kehittämisen päätehtävänä oli löytää "hermeettinen" hash-funktio [11] eli funktio, jolle (jos hash-tulos koostuu bitteistä): $n$

törmäyshakuongelman odotettu monimutkaisuus on $2^{{n/2}}$
kuvan laskentaongelman odotettu monimutkaisuus on $2^{n}$
toisen kuvan laskentatehtävää varten odotettu monimutkaisuus on yhtä suuri kuin $2^{n}$

Lisäksi ei ole mahdollista havaita systemaattisia korrelaatioita minkään tulobittien lineaarisen yhdistelmän ja minkään hajautustulosbittien lineaarisen yhdistelmän välillä. [yksitoista]

Törmäysten etsiminen

Tätä hash-toimintoa on hyökätty onnistuneesti kahdesti. Jo vuonna 2001 osoitettiin, että tämä hash-toiminto ei ole kryptografisesti turvallinen, koska toimintojen törmäyksiä löydettiin. Lisäksi Joan Dymen osoitti, että törmäykset on mahdollista löytää jo operaatioita varten, ja luotettavuusparametrien täyttämiseksi on välttämätöntä, että törmäykset paikannetaan ainakin operaatioita varten. [12] $2^{82}$ $2^6$ $2^{128}$

Muistiinpanot

↑ Nopea tiivistys ja suoratoiston salaus Panaman kanssa, kirjoittanut Joan Daemen, Craig Clapp
↑ NIST valitsee Secure Hash Algorithm (SHA-3) -kilpailun voittajan . Käyttöpäivä: 5. marraskuuta 2016. Arkistoitu alkuperäisestä 5. lokakuuta 2012. (määrätön)
↑ 1 2 J. Daemen, "Salaus- ja hash-funktion suunnittelustrategiat, jotka perustuvat lineaariseen ja differentiaaliseen kryptausanalyysiin"
↑ Nopea tiivistys ja suoratoiston salaus Panaman kanssa" Joan Daemen, Craig Clapp
↑ Arkistoitu kopio (linkki ei saatavilla) . Haettu 16. joulukuuta 2016. Arkistoitu alkuperäisestä 15. elokuuta 2011. (määrätön)
↑ SHA1-versio 1.0 . Haettu 16. joulukuuta 2016. Arkistoitu alkuperäisestä 14. toukokuuta 2017. (määrätön)
↑ 12 Panama . _ Haettu 4. marraskuuta 2016. Arkistoitu alkuperäisestä 26. joulukuuta 2016. (määrätön)
↑ Panaman kryptografinen toiminto | Tohtori Dobbin (linkki ei saatavilla) . Käyttöpäivä: 4. marraskuuta 2016. Arkistoitu alkuperäisestä 23. helmikuuta 2016. (määrätön)
↑ * Joan Daemen, Craig Clapp "Fast Hashing and Stream Encryption with Panama"
↑ PANAMA koodi | Salausblogi . Haettu 5. marraskuuta 2016. Arkistoitu alkuperäisestä 5. marraskuuta 2016. (määrätön)
↑ 1 2 3 4 "Fast Hashing and Stream Encryption with Panama" Joan Daemen, Craig Clapp
↑ Tuottaa yhteentörmäyksiä Panamaan, välittömästi . Haettu 13. marraskuuta 2016. Arkistoitu alkuperäisestä 10. lokakuuta 2019. (määrätön)

Kirjallisuus

"Fast Hashing and Stream Encryption with Panama" Joan Daemen, Craig Clapp
A. Bosselaers, R. Govaerts, J. Vandewalle, "Fast Hashing on the Pentium"
J. Daemen, "Salaus- ja hajautusfunktion suunnittelustrategiat, jotka perustuvat lineaariseen ja differentiaaliseen kryptausanalyysiin"
CSK Clapp "Nopean stream-salauksen optimointi VLIW-, SIMD- ja superskalaariprosessoreille"
Asoskov A. V., Ivanov M. A., Mirsky A. A., Ruzin A. V., Slanin A. V., Tyutvin A. N. "Stream ciphers".

Linkit

Hash-funktiot
yleinen tarkoitus	Adler-32 CRC Fletcherin tarkistussumma FNV MurmurHash2 MurmurHash2A MurmurHash3 PJW-32 TTH - Hash Tree jenkins hash hash summa
Kryptografinen	Stribog GOST R 34.11-94 Vyö BLAKE BMW CubeHash KAIKU edonkey2k FSB Fuuga Grostl HAVAL Hamsi JH Kupyna LM hash Luffa MD2 MD4 MD5 MD6 N-hash RIPEMD-128 RIPEMD-160 RIPEMD-256 RIPEMD-320 SHA-1 SHA-2 Keccak (SHA-3) SHABAL SHAvite-3 SIMD SWIFFT Iho Snefru Tiikeri Whirlpool
Avainten luontitoiminnot	bcrypt PBKDF2 scrypt Argon 2 Lyra 2
Tarkista numero ( vertailu )	Tarkista summa Verhouffin algoritmi Kuun algoritmi Damm-algoritmi Viivakoodi pankkitilit pankkikortit ISIN SNILS OKPO TINA OKATO ISBN OGRN ja OGRNIP VIN
Hashes	Sekkinumeroiden vertailu Todennusprotokollat Viivakoodin vertailu Kryptografia Magneettilinkki Merklen allekirjoitus ed2k UURNA