Specyfika wykorzystania funkcji XOR w kryptografii

Submitted by admin on sob., 2008-10-25 15:19

Jedna z bitowych operacji logicznych stanowiących podstawę kryptografii. Daje w wyniku jedynkę dla dwóch różnych bitów, zero dla dwóch identycznych. Inne nazwy: exclusive OR, różnica symetryczna, dodawanie modulo 2. Symbolem jest plus w okręgu ($ \oplus $).

Jeśli zapiszemy operację XOR jako $ A \oplus B = C $ to tablica wyników będzie wyglądać następująco:

A B C
0 0 0
1 0 1
0 1 1
1 1 0

XOR można łatwo zrealizować przy pomocy operacji logicznych OR, AND i NAND:

XOR = (A NAND B) AND (A OR B)

Istotną cechą funkcji XOR jest jej przemienność, w kontekście kryptografii zwana symetrycznością.

$ A \oplus B = C $
$ C \oplus B = A $
$ C \oplus A = B $

Cecha ta powoduje, że XOR jest chętnie wykorzystywany do szyfrowania - wystarczy dodać za jego pomocą bit klucza ($ K $) do bitu tekstu jawnego ($ P $), by otrzymać bit kryptogramu ($ C $). Odszyfrowanie polega na dodaniu klucza do kryptogramu - wynikiem jest tekst jawny. Można to zapisać następująco:

  • Szyfrowanie: $ P \oplus K = C $
  • Deszyfrowanie: $ C \oplus K = P $

Operację XOR wykorzystują bardzo często szyfry strumieniowe. Wiąże się z tym jednak pewne niebezpieczeństwo, niekiedy nie zauważane przez autorów oprogramowania szyfrującego. Weźmy dwa teksty jawne $ P $ i $ Q $, zaszyfrowane tym samym tajnym kluczem $ K $:

$ P \oplus K = C_{1} $
$ Q \oplus K = C_{2} $

Uzyskaliśmy dwa kryptogramy $ C_{1} $ i $ C_{2} $. Ich przechwycenie przez atakującego nie powinno dać mu żadnych informacji o tekście jawnym bez znajomości klucza $ K $. Jednak w tym przypadku tak nie jest! Spójrzmy co stanie się po dodaniu tych dwóch tekstów do siebie za pomocą XOR:

$ C1 \oplus C2 = (P \oplus K) \oplus (K \oplus Q) = P \oplus Q $

W wyniku uzyskuje się więc dwa teksty jawne $ P $ i $ Q $, "sklejone" za pomocą XOR. Tajny czynnik w postaci klucza $ K $ został wyeliminowany, a rozdzielenie tekstów $ P $ i $ Q $ jest relatywnie proste jeśli zostaną spełnione określone warunki. Przykładowy zrzut przedstawia tekst w języku polskim ($ P $) xorowany z ciągiem liter "e" ($ Q $). Widać wyraźnie regularności, a znając całość lub fragmenty $ Q $ atakujący może łatwo odzyskać tekst jawny $ P $ (atak z wybranym tekstem jawnym).

00000000  45 45 45 32 d6 04 01 1f  8f 45 12 45 35 0a 09 16  |EEE2Ö....E.E5...|
00000010  06 00 45 08 0a da 00 45  15 17 1f 00 0f d4 83 45  |..E..Ú.E.....Ô.E|
00000020  15 0a 09 0c 06 0f 04 45  15 0a 09 0c 11 1c 06 1f  |.......E........|
00000030  0b 04 45 48 6f 45 45 45  15 17 1f 00 16 11 17 1f  |..EHoEEE........|
00000040  00 02 04 0f d4 45 15 0a  16 d6 0a 12 0c 00 45 35  |....ÔE...Ö....E5|
00000050  0c 36 49 45 35 2a 45 0c  45 29 35 37 49 45 06 1f  |.6IE5*E.E)57IE..|
00000060  d6 0a 0b 0e 0a 12 0c 00  6f 45 45 45 79           |Ö.......oEEEy|

Podsumowując: nie wolno stosować tego samego klucza do szyfrowania szyfrem strumieniowym więcej niż raz. Jeśli musimy zastosować ten sam klucz wiele razy, dodawajmy do niego za każdym razem inny modyfikator salt.

Przykładem błędnego zastosowania szyfrowania opartego o XOR są dwie stare wersje produktów Microsofti: PPTPv1 oraz Office 2002 (XP) i starsze.


Odpowiedzi

Dodaj nową odpowiedź

Zawartość tego pola nie będzie udostępniana publicznie. If you have a Gravatar account, used to display your avatar.
  • Allowed HTML tags: <a> <em> <strong> <cite> <code> <ul> <ol> <li> <dl> <dt> <dd> <b> <i> <table> <tr> <td> <th> <pre> <blockquote>
  • LaTex commands embedded in text will be interpreted and rendered. Additional information can be found at DruTex Documentation Pages
    • Line and paragraphs break automatically.
    • Assists automatic numbering of tex, equation, and equations environments.
    • Provides different environments to create rendered images (especially maths).
    • Znaki końca linii i akapitu dodawane są automatycznie.
    • Adresy internetowe są automatycznie zamieniane w klikalne odnośniki.
    • E-Mail addresses are hidden with reCAPTCHA Mailhide.

    Więcej informacji na temat formatowania

    CAPTCHA
    Poniższy test chroni przed automatami spammerskimi.