Szyfr XOR

Jest to rodzaj szyfru strumieniowego wykorzystywanego przez firmę Microsoft we wczesnych wersjach jego produktów takich jak Word, Excel.

Word 2.0 – 95, Excel 4.0 – 95
Te wersje aplikacji Microsoft Office wykorzystywały słaby algorytm szyfrowania oparty na operacji XOR. Nawet w tamtych czasach siła tego algorytmu polegała raczej na zaciemnianiu niż szyfrowaniu. Wszystkie hasła do wszystkich wersji Worda i Excela do Office 95 włącznie można było odzyskać natychmiast; ataki siłowe nie były wymagane.

Działanie szyfru opiera się na działaniu logiki matematycznej XOR czyli alternatywie rozłącznej. W logice matematycznej alternatywę rozłączną zapisuje się jako

Alternatywa rozłączna dla ( p q) jest zdaniem prawdziwym, gdy co najmniej jedno z jej zdań składowych pq jest prawdziwe a drugie nie. Operację oznaczamy znakiem

Tablica prawdy dla alternatywy rozłącznej:

pq
000
011
101
110

Wykorzystując ten rodzaj szyfru, będziemy operować na komputerowych bitach, bit (binary digit, czyli cyfra dwójkowa) to najmniejsza jednostka informacji używana w odniesieniu do sprzętu komputerowego. Bit może posiadać dwa stany 1 albo 0, każdy znak, obraz, element wyświetlony na ekranie komputera ma swoją interpretację w systemie dwójkowym. Sprawdźmy poniższy kod:

Uruchamiając powyższy kod wyświetlimy interpretacje słowa „szyfr” w systemie dwójkowym.

szyfr – 01110011,01111010,01111001,01100110,01110010

Jeśli chcielibyśmy zaszyfrować nasze słowo i do zaszyfrowania użyjemy pojedynczej litery „c” której dwu-bitowa interpretacja wynosi 01100011 nasz szyfr będzie wyglądał następująco:

          01110011,01111010,01111001,01100110,01110010 – szyfr
      01100011,01100011,01100011,01100011,01100011 – ccccc
           —————————————————————————
          00010000,00011001,00011010,00000101,00010001 – 

Problem który na pierwszy rzut oka każdy zauważy to, że jeśli szyfrujemy literę za pomocą siebie samej to efekt będzie zawsze ten sam czyli 00000000, to bardzo ważna informacja która ułatwia atakującemu złamanie szyfru.

Efekt wykonania powyższego kodu, szyfrującego tekst „atak 20:00” przy pomocy klucza „cba” :

Jak widzimy z powyższego obrazka, nasz szyfrogram wygląda bardzo przyzwoicie a deszyfrowanie odbywa się poprzez użycie klucza i tej samej metody getBites() czyli odwrócenie szyfrowania:

Operator XOR jest niezwykle powszechny jako składnik bardziej złożonych szyfrów. Samo w sobie, używając stale powtarzającego się klucza, szyfr XOR można w prosty sposób złamać za pomocą analizy częstotliwości. Jeśli można odgadnąć treść wiadomości lub poznać ją w inny sposób, można ujawnić klucz. Jego podstawową zaletą jest to, że jest łatwy do wdrożenia, a operacja XOR jest tania obliczeniowo. Prosty, powtarzający się XOR jest zatem czasami używany do ukrywania informacji w przypadkach, gdy nie jest wymagane żadne szczególne zabezpieczenie. Szyfr XOR jest często używany w złośliwym oprogramowaniu komputerowym, aby utrudnić inżynierię wsteczną.

Jeśli klucz jest losowy i ma co najmniej taką samą długość jak wiadomość, szyfr XOR jest znacznie bezpieczniejszy niż w przypadku powtórzenia klucza w wiadomości. Gdy strumień klucza jest generowany przez generator liczb pseudolosowych, wynikiem jest szyfr strumieniowy. W przypadku klucza, który jest naprawdę losowy, wynikiem jest jednorazowa podkładka, której teoretycznie nie można złamać.

W każdym z tych szyfrów operator XOR jest podatny na atak znanego tekstu jawnego. Jest również możliwe przerzucanie dowolnych bitów w odszyfrowanym tekście jawnym poprzez manipulowanie tekstem zaszyfrowanym. Nazywa się to plastycznością i jest to cecha bardzo niepożądana w krypto systemie, nie odnosi się do zdolności atakującego do odczytania zaszyfrowanej wiadomości a do możliwości jej modyfikacji.

Sprawdźmy jak będzie wyglądało szyfrowanie pikseli obrazka, do celów testowych użyjemy naszego kotka:

Nasz obrazek ma wymiar 256×194, każdy piksel jest reprezentacją modelu przestrzeni barw RGB  (R – red (czerwonej), G – green (zielonej) i B – blue (niebieskiej)) każdy kolor przyjmuje wartość od 0 do 256 czyli jego reprezentacja to jeden bajt. Czyli w naszym wypadku mamy do zaszyfrowania 256 * 194 *3 = 148 992 bajty. To daje nam bardzo dużą szansę na spojrzenie z góry i wychwycenie powtarzających się schematów które mogą ułatwić odszyfrowanie obrazka bądź tekstu i uwypuklą wady szyfru XOR.
Do zaszyfrowania naszego obrazka użyjemy klucza generowanego pseudo losowo podczas każdej operacji XOR. Efektem będzie zaszyfrowany obrazek i klucz.

Powyższy kod służy do szyfrowania i deszyfrowania obrazka przy pomocy klucza pseudo losowego o długości ilości bajtów kolorów w obrazku.
Zajmiemy się teraz czymś ciekawym, porównamy inne operacje logiczne. Jak wiemy, w matematyce występują dwie podobne operacje OR i AND a efekt ich użycia wraz z kluczem pseudo losowym jest tak ciekawy, że nie mogę ominąć tej kwestii i muszę wam pokazać ten efekt

Aby dokonać tego typu zmian należy zaktualizować linię 121 naszego kodu:

Dla operatora logicznego „AND” Dla operatora logicznego „OR”

Wiemy jak używać naszego szyfru XOR z kluczem pseudo losowym ale jego zastosowanie nie wydaję się wygodne, klucz wielkości szyfrogramu jest niewygodny a jego utrata będzie wiązała się z utratą pliku bazowego.
Łatwiejszym sposobem jest utworzenie hasła i za jego pomocą szyfrowanie pliku. Zobaczmy jak to się sprawdzi w praktyce.
Naszym hasłem będzie: VisualMonsters.cba.pl
Efekt takiego szyfru nie jest zbyt imponujący:

Kod który posłużył do zaszyfrowania naszego pliku:

Bardzo dobrze widać na naszym obrazku sekwencje klucza:

Prosty trik zapewni nam względną losowość, zmiana linii 71 na:

spowoduje przemnożenie klucza przez pozycję piksela. Nasz obrazek zniknie w mgnieniu oka:

Nadal wyczuwalna jest nutka sekwencji ale prosty trik zapewnił nam akceptowalny poziom zabezpieczenia.
Pełen kod:

Permalink do tego artykułu: https://visualmonsters.cba.pl/szyfr-xor/