Hoppa yfir í efnið

XOR og einnota lyklar

Í 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.

XOR er ekki sjálfkrafa örugg dulritun

Það er auðvelt að skrifa forrit sem notar XOR. Það er ekki þar með sagt að forritið sé öruggt. Öryggið ræðst af lyklinum, hvernig hann er búinn til, hvort hann er endurnotaður og hvernig gögnin eru meðhöndluð.

XOR rifjað upp

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

Fyrri biti Seinni biti XOR
0 0 0
0 1 1
1 0 1
1 1 0

Í táknum er XOR oft skrifað ⊕.

Sýnidæmi: XOR á fjóra bita

  0101
⊕ 0011
──────
  0110

Við skoðum einn dálk í einu:

0 ⊕ 0 = 0
1 ⊕ 0 = 1
0 ⊕ 1 = 1
1 ⊕ 1 = 0

Niðurstaðan er 0110.

XOR hefur þrjá eiginleika sem verða sérstaklega mikilvægir:

x ⊕ 0 = x
x ⊕ x = 0
(x ⊕ y) ⊕ y = x

Síðasta jafnan segir að ef við beitum sömu XOR-aðgerð aftur fáum við upphaflega gildið.

Æfing: XOR á bitum

Æfing 1

Reiknaðu:

  1010       1100       1111
⊕ 0110     ⊕ 1010     ⊕ 1111
──────     ──────     ──────
Lausn við æfingu 1

Við berum saman bitana í hverjum dálki:

  1010       1100       1111
⊕ 0110     ⊕ 1010     ⊕ 1111
──────     ──────     ──────
  1100       0110       0000

Til dæmis er fyrsta niðurstaðan:

1 ⊕ 0 = 1
0 ⊕ 1 = 1
1 ⊕ 1 = 0
0 ⊕ 0 = 0

og því 1010 ⊕ 0110 = 1100. Síðasta dæmið sýnir regluna x ⊕ x = 0.

XOR á bæti

Tölvur vinna oft með XOR á heilum bætarunum í einu. Hvert bæti inniheldur átta bita, en við skrifum það oft í sextándakerfinu til að gera dæmin styttri.

Til dæmis er bókstafurinn A í ASCII bætið 0x41:

0x41 = 0100 0001

Við getum XOR-að eitt bæti með öðru:

  0x41
⊕ 0x20
──────
  0x61

0x61 er ASCII fyrir lágstafinn a. Við getum svo XOR-að 0x61 með 0x20 aftur:

  0x61
⊕ 0x20
──────
  0x41

Við erum komin aftur í A.

Í Python má skrifa:

>>> 0x41 ^ 0x20
97
>>> hex(0x41 ^ 0x20)
'0x61'
>>> chr(0x61)
'a'

Táknið ^ er XOR í Python. Það er ekki veldisvísir; veldi er skrifað með **.

Æfing: bæti og XOR

Æfing 2

  1. Reiknaðu 0x41 ^ 0x20 og skrifaðu niðurstöðuna í sextándakerfi.
  2. Hvaða ASCII-stafur er niðurstaðan?
  3. Hvað fæst ef þú XOR-ar niðurstöðuna aftur með 0x20?
Lausn við æfingu 2
  1. Í tvíundakerfi er:
0x41 = 0100 0001
0x20 = 0010 0000

XOR gefur:

  0100 0001
⊕ 0010 0000
───────────
  0110 0001 = 0x61
  1. 0x61 er ASCII-gildið fyrir a.
  2. 0x61 ^ 0x20 = 0x41, þannig að við fáum A aftur. Þetta er dæmi um að sama aðgerð getur bæði dulritað og dulráðað þegar sami lykill er notaður.

XOR sem einföld dulritun

Við getum notað XOR til að blanda saman ódulrituðum gögnum og lykli:

Dultexti = Ódulritaður texti ⊕ Lykill
Ódulritaður texti = Dultexti ⊕ Lykill

Við skulum nota eitt bæti í einu. Segjum að:

Ódulritað bæti = 0x41
Lykill          = 0x2a

Þá er dultextinn:

  0x41
⊕ 0x2a
──────
  0x6b

Til að dulráða notum við sama lykil:

  0x6b
⊕ 0x2a
──────
  0x41

Af hverju virkar þetta? Vegna þess að:

(P ⊕ K) ⊕ K = P ⊕ (K ⊕ K) = P ⊕ 0 = P

Hér stendur P fyrir plaintext og K fyrir key. Við munum nota íslensku heitin í textanum, en gott er að þekkja ensku bókstafina þegar við lesum kóða og verkefnalýsingar.

Sýnidæmi: tvö bæti í Python

texti = bytes([0x41, 0x42])  # AB
lykill = bytes([0x2a, 0x2a])

dultexti = bytes(a ^ b for a, b in zip(texti, lykill))
print(dultexti.hex())
# 6b68

upprunalegt = bytes(a ^ b for a, b in zip(dultexti, lykill))
print(upprunalegt)
# b'AB'

Í þessu dæmi eru textinn og lykillinn jafn langir. zip parar saman fyrsta bæti við fyrsta bæti, annað við annað og svo framvegis.

Gættu að lengdinni

zip hættir þegar styttri röðin klárast. Ef texti og lykill eru ekki jafn langir þarf forritið að ákveða sérstaklega hvað á að gera. Ekki gera ráð fyrir að stuttur lykill verði sjálfkrafa öruggur bara af því að forritið keyrir.

Einnota lykill

Einnota lykill (e. one-time pad) er sérstök leið til að nota XOR. Til að hún sé örugg þurfa öll eftirfarandi skilyrði að vera uppfyllt:

  1. Lykillinn er jafn langur og ódulritaða skilaboðið.
  2. Lykillinn er valinn af góðri slembni.
  3. Lykillinn er leyndur.
  4. Lykillinn er notaður nákvæmlega einu sinni.
  5. Lykillinn er aldrei endurnotaður eða hluti hans notaður aftur.

Sýnidæmi: einnota lykill á tveimur bæti

Við skulum nota textann HI og slembinn lykil:

Texti:  0x48 0x49
Lykill: 0x2a 0x7f

XOR-aðgerðin gefur:

  0x48 0x49
⊕ 0x2a 0x7f
────────────
  0x62 0x36

Dultextinn er því bætarunan 62 36 í sextándakerfi. Viðtakandinn, sem hefur sama lykil, getur endurheimt textann:

  0x62 0x36
⊕ 0x2a 0x7f
────────────
  0x48 0x49  →  HI

Lykillinn er jafn langur og skilaboðin og má ekki nota aftur. Ef við getum raunverulega uppfyllt öll skilyrðin hefur einnota lykill mjög sérstakan eiginleika: dultextinn lekur ekki upplýsingum um frumtextann nema lykillinn komist í hendur óviðkomandi.

Vissir þú?

Einnota lykill er eitt fárra dulmálskerfa sem hægt er að sýna fram á að hafi fullkomið leyndarstig við rétt skilyrði. Gallinn er hagnýtur: við þurfum leynilegan lykil jafn langan og öll skilaboðin og þurfum að koma honum örugglega til viðtakandans áður en skilaboðin eru send.

Æfing: fylgdu einnota lyklinum

Æfing 3

Við höfum eftirfarandi gögn:

Texti:  0x41 0x42 0x43
Lykill: 0x10 0x20 0x30
  1. Reiknaðu dultextann.
  2. Dulráðaðu dultextann aftur með sama lykli.
Lausn við æfingu 3

Við XOR-um hvert par:

  0x41 0x42 0x43
⊕ 0x10 0x20 0x30
────────────────
  0x51 0x62 0x73

Dultextinn er 0x51 0x62 0x73.

Til að dulráða notum við sama lykil:

  0x51 0x62 0x73
⊕ 0x10 0x20 0x30
────────────────
  0x41 0x42 0x43

Við fáum upphaflegu bætarununa aftur. Það að sama lykill virki í báðar áttir er gagnlegt, en það segir ekkert eitt og sér um öryggið. Endurnotkun og slæm slembni geta samt eyðilagt kerfið.

Endurnotkun lykils: aldrei nota pad tvisvar

Einnota lykill missir mikilvægan eiginleika sinn ef við notum hann tvisvar. Segjum að við höfum tvö skilaboð P₁ og P₂ og notum sama lykil K:

C₁ = P₁ ⊕ K
C₂ = P₂ ⊕ K

Ef einhver fær bæði dultextana getur hann XOR-að þá saman:

C₁ ⊕ C₂
= (P₁ ⊕ K) ⊕ (P₂ ⊕ K)
= P₁ ⊕ P₂ ⊕ K ⊕ K
= P₁ ⊕ P₂

Lykillinn hverfur úr jöfnunni. Við fáum ekki endilega bæði skilaboðin strax, en við fáum sambandið á milli þeirra. Það getur verið nóg til að finna orð, staðsetningar eða bæði skilaboðin með orðagiskum.

Sýnidæmi: sama lykill á tveimur bæti

Látum:

P₁ = 0x41  # A
P₂ = 0x42  # B
K  = 0x2a

Þá verða dultextarnir:

C₁ = 0x41 ⊕ 0x2a = 0x6b
C₂ = 0x42 ⊕ 0x2a = 0x68

Hlerari sem hefur bara 0x6b veit ekki endilega að það hafi verið A. En með báðum dultextunum getur hann reiknað:

C₁ ⊕ C₂ = 0x6b ⊕ 0x68 = 0x03
P₁ ⊕ P₂ = 0x41 ⊕ 0x42 = 0x03

Þetta gefur sambandið milli skilaboðanna. Með lengri textum, þekktu sniði og orðagiskum getur slíkt samband orðið mjög upplýsandi.

Fróðleikur: Venona

Í Venona-verkefninu kom í ljós að hluti einnota lykla hafði verið endurnotaður í skilaboðum Sovétríkjanna. Þegar sama dulmálsefnið var notað oftar en einu sinni varð hægt að greina tengsl milli skilaboðanna. „Einnota“ er því ekki skrautlegt heiti — það er nákvæm notkunarleiðbeining.

Æfing: finndu lekið samband

Æfing 4

Tveir dultextar voru búnir til með sama XOR-lykli:

C₁ = 0x6b 0x68
C₂ = 0x68 0x6f
  1. Reiknaðu C₁ ⊕ C₂ bæti fyrir bæti.
  2. Hvað veistu þá um P₁ ⊕ P₂?
Lausn við æfingu 4

Við XOR-um samsvarandi bæti:

  0x6b 0x68
⊕ 0x68 0x6f
────────────
  0x03 0x07

Þar sem sami lykill var notaður gildir:

C₁ ⊕ C₂ = P₁ ⊕ P₂

Því vitum við að P₁ ⊕ P₂ er 0x03 0x07. Við vitum enn ekki endilega bæði frumskilaboðin, en við höfum fengið upplýsingar sem hefðu ekki átt að leka. Þetta er ástæðan fyrir því að endurnotkun einnota lykils er alvarleg villa.

Þekktur frumtexti getur lekið lyklinum

Stundum þekkjum við hluta af ódulrituðu skilaboði. Til dæmis gæti CTF-þraut alltaf byrjað á gg{, eða skrá byrjað á þekktu skráarauðkenni. Þá getum við borið þekktan frumtexta saman við sama hluta dultextans.

Þetta kallast samtextaárás (e. known-plaintext attack). Ef:

C = P ⊕ K

getum við XOR-að báðum megin með P:

C ⊕ P = (P ⊕ K) ⊕ P = K

Við fáum lykilinn fyrir þann hluta sem við þekkjum.

Sýnidæmi: þekkt upphaf fána

Segjum að við vitum að frumtextinn byrji á HI:

Frumtexti: H  I
           0x48 0x49
Dultexti:  0x20 0x2a

Við finnum lyklabætið:

K = P ⊕ C

K₁ = 0x48 ⊕ 0x20 = 0x68
K₂ = 0x49 ⊕ 0x2a = 0x63

Lykillinn byrjar því á 0x68 0x63. Ef sami lykill er endurnotaður lengra í skilaboðinu getum við notað þessar upplýsingar til að afkóða meira.

Æfing: finndu lyklabæti

Æfing 5

Við vitum að frumtextinn byrjar á bókstafnum A, sem er 0x41 í ASCII. Fyrsta bæti dultextans er 0x13.

Hvaða bæti var notað sem lykill?

Lausn við æfingu 5

Við notum:

K = P ⊕ C

og setjum inn gildin:

  0x41
⊕ 0x13
──────
  0x52

Lykilbætið er því 0x52.

Við getum sannreynt:

0x41 ⊕ 0x52 = 0x13

Þekktur frumtexti gefur okkur ekki sjálfkrafa allan lykilinn, en hann getur gefið mikilvægan hluta hans. Það er sérstaklega hættulegt þegar lykill er stuttur eða endurtekinn.

Endurtekinn XOR-lykill

Í raunverulegum forritum er oft of óþægilegt að geyma lykil jafn langan og öll skilaboðin. Þá freistast fólk til að endurtaka stuttan lykil:

Texti:  H E L L O W O R L D
Lykill: K E Y K E Y K E Y K

Þetta kallast oft endurtekinn XOR-lykill (e. repeating-key XOR). Hann er ekki einnota lykill. Sama lykilbæti er notað aftur og aftur og það getur lekið mynstrum.

Sýnidæmi: Python með endurteknum lykli

def xor_endurtekinn(texti: bytes, lykill: bytes) -> bytes:
    if not lykill:
        raise ValueError("Lykillinn má ekki vera tómur")

    return bytes(
        stafur ^ lykill[i % len(lykill)]
        for i, stafur in enumerate(texti)
    )

texti = b"HELLO WORLD"
lykill = b"KEY"

dultexti = xor_endurtekinn(texti, lykill)
print(dultexti.hex())

# Sama fall dulráðar, því XOR aftur með sama lyklinum.
print(xor_endurtekinn(dultexti, lykill))
# b'HELLO WORLD'

i % len(lykill) velur stöðu innan lykilsins og lætur hana byrja aftur þegar við komum að enda hans. Það er einmitt veikleikinn: mynstrið í lyklinum endurtekur sig.

Ekki rugla þessu saman við trausta nútímadulritun

Endurtekinn XOR-lykill er gagnlegur í kennsludæmum og CTF-þrautum, en hann er ekki almennileg staðgengill fyrir AES eða önnur viðurkennd dulritunarkerfi.

Æfing: þekktu veikleikann

Æfing 6

Skoðaðu kóðann:

lykill = b"A"
dultexti = bytes(b ^ lykill[0] for b in b"SECRET")
  1. Hversu mörg mismunandi lyklabæti eru notuð?
  2. Hvað gerist ef frumtextinn inniheldur sama staf tvisvar?
  3. Hvernig myndir þú dulráða dultexti?
Lausn við æfingu 6
  1. Aðeins eitt lyklabæti er notað: ASCII-gildið fyrir A, sem er 0x41.
  2. Sami frumtextastafur fær alltaf sama dultextastaf, því sama XOR-gildið er notað aftur. Þetta getur gefið vísbendingar um mynstur og tíðni.
  3. Við notum sama XOR-lykil aftur:
frumtexti = bytes(b ^ ord("A") for b in dultexti)

XOR er andhverfanlegt, svo við fáum b"SECRET" aftur. En sá sem er að reyna að brjóta kerfið þarf ekki endilega að vita lykilinn fyrirfram; stuttur lykill býður upp á þrautleit og mynsturgreiningu.

Slembni skiptir máli

Einnota lykill þarf að vera slembinn. Það er ekki nóg að velja eitthvað sem lítur handahófskennt út fyrir okkur, eins og:

lykil = b"leyndarmal123"

Slík lykilorð hafa oft mynstur sem hægt er að giska á. Við þurfum slembitalnagjafa (e. random number generator) sem er hannaður fyrir öryggi þegar við búum til dulritunarlykla.

Í Python eigum við að nota secrets fyrir slíka lykla:

import secrets

lykill = secrets.token_bytes(32)  # 32 slembin bæti

Venjulegur random-pakki er góður fyrir leiki, hermun og slembin sýnidæmi, en ekki til að búa til leyndarmál í dulritun. Slíkur gervislembitalnagjafi getur verið fyrirsjáanlegur ef árásarmaður sér nægilega mikið af úttakinu.

Góð spurning að spyrja

Þegar þú sérð dulritunarverkefni skaltu spyrja: Hvernig var lykillinn búinn til? Er hann nógu langur? Er hann endurnotaður? Er hann fyrirsjáanlegur? Oft liggur veikleikinn í þessum spurningum, ekki í XOR-aðgerðinni sjálfri.

Lokaverkefni: skoða XOR-kerfi

Æfing 7

Skoðaðu eftirfarandi lýsingu:

Forritið býr til 4 bæta lykil með secrets.token_bytes(4). Það XOR-ar öll skilaboðin með þessum lykli og endurtekur lykilinn þar til skilaboðin klárast. Sami lykill er notaður til að dulrita tíu skilaboð.

Hvað eru að minnsta kosti þrjú vandamál við þetta kerfi?

Lausn við æfingu 7
  1. Lykillinn er stuttur. Fjórir bæti eru endurtekin yfir öll skilaboðin. Það getur leyft þrautleit, tíðnigreiningu og mynsturgreiningu.
  2. Lykillinn er endurnotaður. Öll tíu skilaboðin deila sama lykli. Með því að XOR-a dultexta saman eyðist lykillinn og samband milli frumtextanna lekur.
  3. Þetta er ekki einnota lykill. Einnota lykill þarf að vera jafn langur og skilaboðin og aðeins notaður einu sinni.
  4. Jafnvel þótt slembitalnagjafinn sé góður leysir hann ekki vandann við endurtekningu og endurnotkun.

Þetta er gott dæmi um að rétt verkfæri á röngum stað leysa ekki hönnunarvandann. secrets.token_bytes býr til góða slembni, en kerfið eyðileggur öryggið með því að nota sama stutta lykilinn aftur og aftur.

Samantekt

Í þessum kafla lærðum við að:

  • XOR skilar 1 þegar bitarnir eru ólíkir og 0 þegar þeir eru eins.
  • XOR með sama lyklinum tvisvar skilar upphaflegu gögnunum.
  • XOR er aðgerð, ekki sjálfkrafa öruggt dulritunarkerfi.
  • Einnota lykill þarf að vera jafn langur og skilaboðin, slembinn, leyndur og aðeins notaður einu sinni.
  • Endurnotkun lykils gerir okkur kleift að reikna C₁ ⊕ C₂ = P₁ ⊕ P₂.
  • Samtextaárás getur lekið lykli þegar hluti frumtextans er þekktur.
  • Endurtekinn XOR-lykill lekur mynstrum og er ekki traust nútímadulritun.
  • secrets.token_bytes er dæmi um verkfæri til að búa til slembna lykla í Python.

Næst færum við okkur frá þessum einföldu byggingareiningum yfir í samhverfa dulritun í raunverulegum kerfum, þar sem staðlað algrím, lykilstærðir, IV-gildi og nonces skipta öllu máli.