Tekst źródłowy strony VMPC

'''VMPC''' ([[język angielski|ang.]] ''Variably Modified Permutation Composition''; zmiennie modyfikowane złożenie [[permutacja|permutacji]]) – funkcja oraz [[Szyfr|algorytm szyfrowania]] opracowane przez [[Bartosz Żółtak|Bartosza Żółtaka]] i opublikowane przez autora na międzynarodowej konferencji kryptograficznej Fast Software Encryption w 2004 (FSE 2004).

Definicja funkcji VMPC dla n-elementowej permutacji f jest następująca:
: <math>g(x) = \operatorname{VMPC}(f(x)) = f(f(f(x))+1) \pmod n.</math>

Przekształcenie to – mimo prostej budowy – okazuje się trudne do odwrócenia. [[Symulacja komputerowa|Symulacje komputerowe]] pokazują, że znalezienie permutacji f na podstawie permutacji g dla 16-elementowej permutacji zajmuje około 2<sup>11</sup> operacji (ok. 2000), dla 64-elementowej permutacji – około 2<sup>53</sup> operacji (ok. 9 biliardów), a dla 256-elementowej permutacji – około 2<sup>260</sup> operacji.

Wraz z funkcją VMPC na konferencji FSE 2004 opublikowany został algorytm szyfrowania danych bazujący na funkcji VMPC. Jest to [[szyfr strumieniowy]] charakteryzujący się dużą wydajnością w [[Implementacja (informatyka)|implementacjach]] programowych. Jego budowa – podobnie jak funkcji VMPC – jest bardzo prosta. Algorytm działania szyfru VMPC pozwalający zaszyfrować L-znakową (bajtową) informację przedstawia się następująco:

<pre>
1. n = 0
2. Powtarzaj kroki 3-6 L razy:
3. s = P[ (s + P[n]) mod 256 ]
4. Output = P[ (P[P[s]]+1) mod 256 ]
5. Temp = P[n]
   P[n] = P[s]
   P[s] = Temp
6. n = (n + 1) mod 256
</pre>

gdzie P (256-elementowa permutacja) i s (1-bajtowa zmienna) są uzyskane z hasła szyfrującego przy użyciu VMPC-KSA (VMPC Key Scheduling Algorithm). Implementację VMPC-KSA, a także algorytmu VMPC-MAC, pozwalającego na tworzenie kodów uwierzytelniających wiadomość (Message Authentication Code) dla danych szyfrowanych szyfrem VMPC, można znaleźć na stronie domowej projektu VMPC.

== Bezpieczeństwo VMPC ==
W 2006 roku w Cambridge University Dr Kamil Kulesza pracował nad problemem odwrócenia VMPC i doszedł do konkluzji: „wyniki wskazują, że VMPC nie jest obecnie dobrym kandydatem na jednokierunkową funkcję kryptograficzną”<ref>{{Cytuj stronę |url = https://www.newton.ac.uk/files/preprints/ni06009_0.pdf |tytuł = On inverting the VMPC one-way function |nazwisko = Kulesza |imię = Kamil |opublikowany = newton.ac.uk |język = en |data dostępu = 2019-02-27}}</ref> Podstawą do takiej konkluzji jest:
* istnienie kluczy, które mogą być odwrócone w czasie liniowym
* istnienie kluczy słabych dla których wystarczy odgadnięcie dużej części wartości
* VMPC nie jest zawsze [[Funkcja różnowartościowa|funkcją różnowartościową]]
* otwarta możliwość znalezienia kolejnych zbiorów słabych kluczy innymi metodami i nadal mała ilość badań na tym polu
* istnienie ataków opartych o kryptoanalizę dużych zbiorów zaszyfrowanych danych<ref>[https://pdfs.semanticscholar.org/86a6/d5bdce46c112ece81982eb189d598e4b0414.pdf Y. Tsunoo, T. Saito, H. Kubo, M. Shigeri, T. Suzaki, and T. Kawabata, ‘The Most Efficient Distinguishing Attack on VMPC and RC4A’, eSTREAM, the ECRYPT Stream Cipher Project:].</ref>

Brak jest jednak informacji o znalezieniu ogólnego rozwiązania problemu odwrócenia funkcji VMPC dla dowolnych kluczy.

W latach 2005–2015 pojawiały się prace opisujące kolejne ataki na VMPC skupiające się na analizie kryptograficznej i korelacjach w generowanym zaszyfrowanym ciągu bajtów odbiegającym nieznacznie od ciągu rzeczywiście losowego. W realnym zastosowaniu do łamania szyfru wymagają one jednak dużej ilości zaszyfrowanych danych z użyciem tego samego klucza i powtarzającą się znaną atakującemu częścią bajtów<ref>[http://www.thesis.bilkent.edu.tr/0006989.pdf Mehmet Karahan, „New Attacks on RC4A and VMPC” str. 39-53, Sierpień 2015].</ref>. Podobnie jak przy szyfrze [[RC4]] oznacza to niebezpieczeństwo dla niektórych zastosowań. Przykładem podatnego na atak zastosowania może być szyfrowanie protokołu z [[kapsułkowanie]]m danych, w którym pierwszy bajt lub kilka bajtów jest publicznie znanych. Opracowane metody ataku są bardzo zbliżone w tym przypadku do stosowanych w atakach na sieci bezprzewodowe w standardzie [[Wired Equivalent Privacy|WEP]], w którym pierwszy bajt jest znany ze względu na kapsułkowanie [[Logical Link Control|LLC]].

== Przypisy ==
{{Przypisy}}

== Linki zewnętrzne ==
* [https://web.archive.org/web/20230531100104/https://www.vmpcrypt.pl Strona domowa projektu VMPC opisująca funkcję VMPC oraz szyfrowanie algorytmem VMPC]
* [http://talks.cam.ac.uk/talk/index/4950 Kamil Kulesza: On inverting the VMPC one-way function]

[[Kategoria:Funkcje skrótu]]
[[Kategoria:Szyfry strumieniowe]]