XOR og einskiptislyklar

Í síðasta kafla notuðum við leifareikning og aðrar stærðfræðilegar aðgerðir til að undirbúa okkur fyrir nútímalegri dulritun. Nú ætlum við að tengja saman bita, bæti og lykla með einni mikilvægustu bitaaðgerðinni: XOR.

XOR er einfalt í sjálfu sér, en það getur orðið mjög öflugt þegar það er notað með góðum, leyndum og slembnum lykli. Við munum líka sjá hvað gerist þegar lykill er of stuttur, fyrirsjáanlegur eða endurnotaður.

Hvað gerir XOR?

Misgildisaðgerð (e. XOR, exclusive OR) ber saman tvo bita. Hún skilar 1 þegar bitarnir eru ólíkir en 0 þegar þeir eru eins.

Önnur gagnleg leið til að hugsa um XOR er að seinni bitinn stjórni því hvort fyrri bitinn breytist, þannig að

• XOR með 0 heldur bitanum óbreyttum, en
• XOR með 1 snýr bitanum við (e. flips).

Þetta getum við táknað með

Stærðfræðitákn og tákn í forritun

Í stærðfræði táknum við XOR með \(\oplus\). Í Python, sem og flestum öðrum forritunarmálum er XOR táknað með ^.

XOR á bitarunur

Þegar XOR er beitt á tvær jafnlangar bitarunur, þá er XOR beitt á bita hvers sætis fyrir sig og niðurstaðan er ný bitaruna. Skoðum dæmi með bitarununum 0101 og 0011:

  0101
^ 0011
  ----
  0110

Við beitum XOR á sérhvern bita í fyrri og seinni rununni, þ.e.

og niðurstaðan er því bitarunan 0110.

Eiginleikar XOR

XOR hefur nokkra eiginleika sem eru sérstaklega gagnlegir. Þessir eiginleikar haldast, hvort sem XOR er beitt á bita eða bitarunur (bæti).

Fyrstu tveir eiginleikarnir tengjast \(0\).

Við getum skoðað sanntöflu XOR til að sannfæra okkur um að þetta standist, en þessir eiginleikar eru mjög mikilvægir. Sá fyrri segir að núll hefur engin áhrif þegar kemur að XOR, þ.e. ef við tökum XOR af einhverju gildi og \(0\), fáum við sama gildi til baka.

Seinni eiginleikinn er einn sá mikilvægasti, en hann gefur okkur að ef XOR er beitt á sama gildi, fáum við \(0\).

XOR er einnig, það sem kallast víxlin (e. commutative) og tengin (e. associative) aðgerð, þ.e.

Seinni reglan kann að virðast snúin, en hún segir einfaldlega að ef við ætlum að taka XOR af þremur gildum, þá skiptir ekki máli hvort við reiknum fyrst niðurstöðu fyrstu tveggja og endum á því síðasta, eða við byrjum á seinni tveimur og beitum þeirri niðurstöðu á því fyrsta.

Þessir eiginleikar sem við höfum talið upp gefa okkur allra mikilvægasta eiginleika XOR, sem er að ef XOR er beitt tvisvar sinnum með sama gildi, fæst upphaflega gildið aftur, þ.e.

Þessi eiginleiki segir okkur að við getum „stytt út“ eða „afturkallað“ XOR með ákveðnu gildi, með því að beita XOR aftur með sama gildi.

A 1101 0000 1111
B 1000 0111 1010

A     1101 0000 1111
B   ^ 1000 0111 1010
      --------------
      0101 0111 0101

(A^B)    0101 0111 0101
B      ^ 1000 0111 1010
         --------------
         1101 0000 1111

A     1010 1100 1111
B   ^ 0110 1010 1111

1010 1100 1111
B   ^ 0110 1010 1111
--------------
1100 0110 0000

Í flestum forritunarmálum er XOR framkvæmt á heiltölur. Í þeim tilgangi sem við ætlum að nota XOR er gagnlegt að hugsa að XOR sé beitt á bæti, sem er einfaldlega átta bita heiltala (á milli 0 og 255). Við skrifum bæti gjarnan í sextándakerfinu til að stytta framsetninguna.

Í eftirfarandi dæmi eru tvö bæti í hvorri röð. Við notum \(P\) (plaintext) fyrir inntakið, \(K\) (key) fyrir gildið sem er XOR-að við það og \(C\) (ciphertext) fyrir niðurstöðuna.

P     0x49       0x7f
      0100 1001  0111 1111

K     0xff       0x00
    ^ 1111 1111  0000 0000
      ---------  ---------
C     1011 0110  0111 1111
      0xb6       0x7f

Í fyrra lyklabætinu, 0xff, eru allir bitarnir 1 og því snúast allir bitar fyrra bætsins við. Í seinna lyklabætinu, 0x00, eru allir bitarnir 0 og því helst seinna bætið óbreytt.

Í Python fáum við sömu niðurstöðu.

>>> hex(0x49 ^ 0xff)
'0xb6'
>>> hex(0x7f ^ 0x00)
'0x7f'

A       0x41
        0100 0001

        0x20
      ^ 0010 0000
        ---------
a       0110 0001
        0x61

def xor_byte(value: int, key: int) -> int:
    pass

def xor_byte(value: int, key: int) -> int:
    if not 0 <= value <= 0xff or not 0 <= key <= 0xff:
        raise ValueError("Value and key should be bytes")

    return value ^ key


result = xor_byte(0x49, 0xff)
print(hex(result))
# 0xb6

original = xor_byte(result, 0xff)
print(hex(original))
# 0x49

XOR dulritun með einu bæti

Við getum notað XOR til að skilgreina einfalda dulritun á eftirfarandi máta. Látum \(P\) tákna ódulritaðan texta (plaintext), \(K\) lykilrunan sem er fenginn með því að endurtaka lykilinn \(k\) (key) þannig að lengdin sé sú sama og \(P\). Dulritið \(C\) (ciphertext) fæst þá með

Til að dulráða, notum við okkur eiginleika XOR og „styttum“ út lykilinn með því að beita XOR aftur, þ.e.

        H          E          L          L          O          !
P       0x48       0x45       0x4c       0x4c       0x4f       0x21
        0100 1000  0100 0101  0100 1100  0100 1100  0100 1111  0010 0001

K       0xb7       0xb7       0xb7       0xb7       0xb7       0xb7
      ^ 1011 0111  1011 0111  1011 0111  1011 0111  1011 0111  1011 0111
        ---------  ---------  ---------  ---------  ---------  ---------
        1111 1111  1111 0010  1111 1011  1111 1011  1111 1000  1001 0110
C       0xff       0xf2       0xfb       0xfb       0xf8       0x96

C       0xff       0xf2       0xfb       0xfb       0xf8       0x96
        1111 1111  1111 0010  1111 1011  1111 1011  1111 1000  1001 0110

K       0xb7       0xb7       0xb7       0xb7       0xb7       0xb7
      ^ 1011 0111  1011 0111  1011 0111  1011 0111  1011 0111  1011 0111
        ---------  ---------  ---------  ---------  ---------  ---------
        0100 1000  0100 0101  0100 1100  0100 1100  0100 1111  0010 0001
P       0x48       0x45       0x4c       0x4c       0x4f       0x21
        H          E          L          L          O          !

Eins og við höfum séð áður, þá er ástæða þess að dulráðningin virkar sú að

def single_byte_xor(data: bytes, key: int) -> bytes:
    pass

def single_byte_xor(data: bytes, key: int) -> bytes:
    if not 0 <= key <= 255:
        raise ValueError("Key must be a single byte (0-255)")

    return bytes(byte ^ key for byte in data)


plaintext = b"SECRET"
key = 0x2a

ciphertext = single_byte_xor(plaintext, key)
print(ciphertext.hex())
# 796f69786f7e

original = single_byte_xor(ciphertext, key)
print(original)
# b'SECRET'

Hvernig brjótum við dulritun með einu bæti?

Þetta mætti kalla okkar fyrsta skref í átt að raunverulegri og nothæfri dulritun. Nú erum við ekki að einbeita okkur að bókstöfum, eins og með klassísku aðferðirnar, heldur getum við dulritað hvaða bæti sem er. En er þessi aðferð örugg? Svarið við því er einfalt: nei!

Þegar öllu er á botninn hvolft, þá er lykillinn í þessari aðferð aðeins eitt bæti. Eitt bæti getur aðeins tekið gildi frá 0 til og með 255. Það þýðir að það eru nákvæmlega 256 mögulegir lyklar!

Við getum því einfaldlega prófað að dulráða dulrit með öllum bætum frá 0 upp í 255, prentað út niðurstöðuna fyrir hverja tilraun, og svo getum við lesið yfir úttakið til að sjá hvaða tilraun skilaði læsilegum texta. Þetta er klassísk þrautleit (e. brute force).

Caesar-dulritun

Þessi aðferð gæti hljómað mjög kunnuglega. Í raun og veru er þessi dulritun, sem kallast XOR með einu bæti (e. Single-byte XOR) nákvæmlega sama hugmyndin og Caesar-dulritunin sem við lærðum um í fyrri kafla um klassískar dulritanir.

• Í Caesar-dulritun áttum við aðeins 25 mögulega lykla (tilfærslur í stafrófinu).
• Í Single Byte XOR eigum við aðeins 256 mögulega lykla.

Þótt lyklarnir séu aðeins fleiri í XOR-aðferðinni er munurinn á 25 og 256 enginn fyrir nútímatölvur; hvoru tveggja tekur brot úr sekúndu að brjóta með þrautleit. Þar að auki, rétt eins og með Caesar, hefur XOR með einu bæti þann sama galla að sami stafur í ódulritaða textanum mun alltaf breytast í sama staf í dulritinu. Ef lykillinn okkar er t.d. 0x2a, þá verður stóri stafurinn E (0x45) alltaf að 0x6f í dulritinu.

Þetta þýðir að auk þrautleitar er þessi aðferð einnig veik fyrir tíðnigreiningu (e. frequency analysis) eins og við notuðum til að brjóta klassísku umskiptin.

XOR-dulritun með endurteknum lykli

Ef við viljum bæta XOR dulritun með einu bæti, liggur beinast við að nota lengri lykil, þ.e. bætarunu í stað eins bætis. Ef lykillinn er styttri en textinn, þá endurtökum við hann, líkt og við gerðum í Vigenère. Þessi aðferð kallast XOR-dulritun með endurteknum lykli (e. repeating-key XOR cipher). Oft er lykillinn valinn sem orð, þó að hann megi velja sem hvaða bætarunu sem er.

        H          E          L          L          O          !
P       0x48       0x45       0x4c       0x4c       0x4f       0x21
        0100 1000  0100 0101  0100 1100  0100 1100  0100 1111  0010 0001

        K          3          y          #          K          3
K       0x4b       0x33       0x79       0x23       0x4b       0x33
      ^ 0100 1011  0011 0011  0111 1001  0010 0011  0100 1011  0011 0011
        ---------  ---------  ---------  ---------  ---------  ---------
        0000 0011  0111 0110  0011 0101  0110 1111  0000 0100  0001 0010
C       0x03       0x76       0x35       0x6f       0x04       0x12

C       0x03       0x76       0x35       0x6f       0x04       0x12
        0000 0011  0111 0110  0011 0101  0110 1111  0000 0100  0001 0010

        K          3          y          #          K          3
K       0xb7       0xb7       0xb7       0xb7       0xb7       0xb7
      ^ 0100 1011  0011 0011  0111 1001  0010 0011  0100 1011  0011 0011
        ---------  ---------  ---------  ---------  ---------  ---------
        0100 1000  0100 0101  0100 1100  0100 1100  0100 1111  0010 0001
P       0x48       0x45       0x4c       0x4c       0x4f       0x21
        H          E          L          L          O          !

def repeating_key_xor(text: bytes, keyword: bytes) -> bytes:
    pass

def repeating_key_xor(text: bytes, keyword: bytes) -> bytes:
    if not keyword:
        raise ValueError("Keyword must not be empty")

    return bytes(
        byte ^ keyword[i % len(keyword)]
        for i, byte in enumerate(text)
    )


text = b"HELLO WORLD"
keyword = b"KEY"

ciphertext = repeating_key_xor(text, keyword)
print(ciphertext.hex())
# 030015070a791c0a0b0701

original = repeating_key_xor(ciphertext, keyword)
print(original)
# b'HELLO WORLD'

Hvernig brjótum við endurtekinn XOR-lykil?

Hér sjáum við aftur hliðstæðu við klassíska dulritun. Við bárum saman XOR-dulritun með einu bæti við Caesar-dulritun, þá fylgir XOR með endurteknum lykli sama mynstri og Vigenère-dulritunin!

Í báðum aðferðum er stutt lykilorð endurtekið yfir allan textann. Þetta þýðir að þær deila nákvæmlega sama veikleikanum. Þ.e., ef árásaraðili getur fundið út (eða giskað á) hversu langt lykilorðið er, er hægt að brjóta dulritið niður í nokkrar eins bæta XOR dulritanir.

Ímyndum okkur að við vitum að lykilorðið í XOR-dulritun sé 5 bæti að lengd. Þá vitum við líka að:

• 1., 6., 11., o.s.frv. bæti dulritsins voru öll XOR-uð við fyrsta bæti lykilsins.
• 2., 7., 12., o.s.frv. bæti dulritsins voru öll XOR-uð við annað bæti lykilsins.

Þannig getum við tekið eitt stórt dulrit, skipt því upp í 5 smærri dulrit, og þá erum við komin með 5 sjálfstæðar XOR-dulritanir með einu bæti. Við getum svo beitt þrautleit (eða tíðnigreiningu) á hvern hóp fyrir sig (þar sem hver dálkur hefur aðeins 256 mögulega lykla). XOR-dulritun með endurteknum lykli er því í rauninni ekkert öruggari en dulritun með einu staku bæti, hún krefst bara aðeins meiri vinnu til að brjóta!

Einskiptislykill

Eftir tvær tilraunir, er rétt að spyrja sig, er einhver leið til að gera XOR-dulritun örugga? Við höfum tekið eftir því að veikleikar fyrri tilraunanna felast í endurtekningum í lyklinum sem gefa upp eðli undirliggjandi textans. En hvað ef við höfum engar endurtekningar? Segjum sem svo að við veljum lykil sem er jafn langur og gögnin sem á að dulrita.

Þessi aðferð kallast dulritun með einskiptislykli (e. one-time pad eða OTP) og er fyrsta raunverulega dulritunin sem við kynnumst. Ómögulegt er að brjóta dulritun með einskiptislykli án upplýsinga um lykilinn.

Til að dulritun með þessari aðferð sé örugg þarf einskiptislykillinn að uppfylla eftirfarandi skilyrði.

1. Lykillinn er jafn langur og ódulritaði textinn.
2. Lykillinn er sannarlega handahófskenndur.
3. Lykillinn er leyndur.
4. Lykillinn, eða hluti hans, er aldrei endurnotaður.

Einskiptislykill er eitt fárra dulmálskerfa sem hægt er að sýna fram á að hafi fullkomið leyndarstig (e. information-theoretically secure) við rétt skilyrði. Það þýðir að komist einhver yfir dulrit, óháð því hversu langan tíma og mikla reiknigetu sá aðili hefur, er ómögulegt fyrir hann að komast yfir upprunalegu skilaboðin. Einu upplýsingarnar sem dulritun með einskiptislykli lekur um ódulritaða textann er hámarkslengd hans.

Endurnotkun lykils

Þrátt fyrir hátt öryggisstig er dulritun með einskiptislykli ekki notuð víða í dag. Helstu ástæðu þess er að finna í nafninu, þ.e., aðeins er hægt að nota hvern lykil einu sinni. Það er vert að muna að dulritun snýst ekki aðeins um að smíða kerfi sem varðveitir leynd gagna, heldur þarf kerfið líka að vera gagnlegt og nothæft. Ef Anna vill eiga samskipti við Bjarna með einskiptislyklum, þurfa þau að koma sér saman um mikið magn langra lykla, og í hvaða röð á að nota þá, áður en samskiptin hefjast.

Einskiptislykill missir mikilvægan eiginleika sinn ef hann er notaður oftar en einu sinni. Segjum sem svo að við höfum tvenn skilaboð \(P_1\) og \(P_2\) sem voru dulrituð með sama einskiptislykli \(K\), þ.e.

Ef einhver kemst yfir bæði dulritin, er hægt að beita XOR á þau og þá fáum við

Við höfum þá náð að „stytta“ lykilinn út úr dulritinu! Þó að dulritið hafi ekki verið brotið, höfum við náð að finna misgildingu upprunalegu skilaboðanna tveggja, þ.e. \(P_1\) og \(P_2\). Þar sem þau eru ekki handahófskennd, eins og lykillinn, getur það verið nóg til að við getum endurheimt upprunalegu skilaboðin, að hluta til eða að öllu leyti.

# Tvö dulrit í hex sem við höfum hlerað
c1 = bytes.fromhex("751f5ebca047644e16428ee2363e1842b983f09b153f3c6a8a1701c049cec5678f27e9d71611d21e679587")
c2 = bytes.fromhex("76121bf7bd4d701c075ecbb6297f1f59abccee9056327371d94301cc0dd9c57bd92bf5d70b0a975660889a")

# 1. Finnum XOR dulritanna tveggja (C1 ^ C2 = P1 ^ P2)
c1_xor_c2 = bytes(a ^ b for a, b in zip(c1, c2))

# Okkar "crib", þ.e. orð sem okkur grunar að sé til staðar
crib = b" the "

# 2. Við drögum orðið (e. crib drag) eftir öllum strengnum
print("Prófum alla mögulega staði fyrir ' the ':")
for i in range(len(c1_xor_c2) - len(crib) + 1):
    hluti = c1_xor_c2[i:i+len(crib)]
    res = bytes(a ^ b for a, b in zip(hluti, crib))

    # Prentum aðeins út ef niðurstaðan inniheldur læsilega ASCII stafi
    if all(32 <= b <= 126 for b in res):
        print(f"Staða {i:02}: {res}")

Staða 07: b'ret t'
Staða 13: b'asswo'
Staða 24: b's hid'
Staða 35: b' is h'

Fyrirsjáanleg slembni

Eitt af skilyrðunum fyrir öryggi einskiptislykla var að lykillinn þyrfti að vera sannarlega slembinn (e. truly random). Eitt af því sem tölvur eru ekkert sérstaklega góðar í er slembni, þ.e. að velja tölur af handahófi. Ein algeng leið til að framkalla slembitölur með tölvum er að nota svokallaða hálfslembitalnagjafa (e. pseudo-random number generators). Þeir virka þannig að við gefum þeim sáð (e. seed), sem er tala eða gildi sem er notað til að frumstilla gjafann, og í kjölfarið getum við óskað eftir tölum, sem líta út fyrir að vera handahófskenndar. Þessi runa sem hálfslembitalnagjafinn framleiðir er þó alltaf eins fyrir hvert sáð.

Þessi virkni er hentug, til dæmis, ef við erum að framleiða gögn til prófana. Ef eitthvað fer úrskeiðis eða við finnum villu, þá getum við auðveldlega framleitt nákvæmlega sömu gögn til að hjálpa okkur við aflúsun. Aftur á móti býður það hættunni heim að nota slíkan slembitalnagjafa við dulritun. Ef við skoðum, til dæmis, dulritun með einskiptislyklum. Ef sáð slembitalnagjafans uppgötvast, er ekki aðeins hægt að dulráða ein skilaboð, heldur framtíðarskilaboð þar til slembitalnagjafinn hefur verið endurstilltur.

Við dulritun notum við slembitalnagjafa sem er ófyrirsjáanlegur og sérstaklega hannaður með öryggi í huga og kallast dulritunarslembitalnagjafi (e. cryptographically secure random number generator, eða CSPRNG). Til að framkalla ófyrirsjáanlegar slembitölur safnar stýrikerfið saman ýmsum mælingum á handahófskenndum atburðum eins og hreyfingu á mús og tímasetningar á innslætti á lyklaborði, tímasetningu á ákveðnum aðgerðum, svo dæmi séu nefnd. Nútímaörgjörvar styðja einnig við framleiðslu ófyrirsjáanlegra slembitalna.

Flest forritunarmál bjóða upp á þessar tvær tegundir slembitalnagjafa og það er mikilvægt að nota rétt verkfæri við réttar aðstæður. Python býður upp á dulritunarslembitalnagjafa í secrets safninu, en hálfslembitalnagjafa má finna í random safninu.

import secrets

lykill = secrets.token_bytes(32)  # Býr til 32 slembin bæti