VMPC

VMPC (ang. Variably Modified Permutation Composition; zmiennie modyfikowane złożenie permutacji) – funkcja oraz algorytm szyfrowania opracowane przez 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:

${\displaystyle g(x)=\operatorname {VMPC} (f(x))=f(f(f(x))+1){\pmod {n}}.}$

Przekształcenie to – mimo prostej budowy – okazuje się trudne do odwrócenia. Symulacje komputerowe pokazują, że znalezienie permutacji f na podstawie permutacji g dla 16-elementowej permutacji zajmuje około 2¹¹ operacji (ok. 2000), dla 64-elementowej permutacji – około 2⁵³ operacji (ok. 9 biliardów), a dla 256-elementowej permutacji – około 2²⁶⁰ 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 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:

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

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ą”^[1] 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 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^[2]

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^[3]. 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łkowaniem 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 WEP, w którym pierwszy bajt jest znany ze względu na kapsułkowanie LLC.

Przypisy

1. Kamil Kulesza: On inverting the VMPC one-way function. newton.ac.uk. [dostęp 2019-02-27]. (ang.).
2. 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:.
3. Mehmet Karahan, „New Attacks on RC4A and VMPC” str. 39-53, Sierpień 2015.

Linki zewnętrzne

• Strona domowa projektu VMPC opisująca funkcję VMPC oraz szyfrowanie algorytmem VMPC
• Kamil Kulesza: On inverting the VMPC one-way function