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:
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 211 operacji (ok. 2000), dla 64-elementowej permutacji – około 253 operacji (ok. 9 biliardów), a dla 256-elementowej permutacji – około 2260 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ą” 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 danychY. 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:.
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ówMehmet Karahan, „New Attacks on RC4A and VMPC” str. 39-53, Sierpień 2015.. 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
Linki zewnętrzne Strona domowa projektu VMPC opisująca funkcję VMPC oraz szyfrowanie algorytmem VMPC Kamil Kulesza: On inverting the VMPC one-way function
Kategoria:Funkcje skrótu Kategoria:Szyfry strumieniowe