— GESTAPÓ —
Í uppáhaldi:
Félagsrit:
Þarfagreinir
Friðargæsluliði.
Heiðursgestur og  skriffinnur.
Pistlingur - 3/11/04
Enigma

Ég lofaði frásögn af því hvernig gekk að brjóta Enigma - og viti menn; hér er hún. Varúð: Hún er löng, ítarleg, og dálítið sjálfbirgingsleg.

Í fyrra riti mínu lagði ég jarðveginn með því að lýsa faginu Tölvuöryggi og dulmálskóðun og reynslu minni af því. Nú er kominn tími til að segja frá hápunktinum; verkefni sem ég mun alltaf muna eftir og vera hvað stoltastur af, og hef ég þó leyst ýmis verkefni í gegnum tíðina, bæði í skóla og vinnu.

Verkefnið snerist um að brjóta kóða sem Kaninn kóðaði og útdeildi. Hann notaði til þess fjórar mismunandi aðferðir: DES, Diffie-Hellman, RSA, og Enigma. Hin síðastnefnda skar sig úr, þar sem hún er langelst þeirra; hinar eru allar tiltölulega nýlegar. Kennarinn útbjó tvenn skilaboð með hverri aðferð, og útdeildi handahófskennt á hópa sem hann valdi sjálfur. Þar sem að á þessum tímapunkti voru 31 manns í námskeiðinu, þá voru fjórir í öllum hópunum nema einum. Ég lenti í þeim eina sem var þriggja manna, og fengum við önnur Enigmaskilaboðin í hendur. Skilaboðin voru ekki sérlega löng; einungis 58 stafir af óskiljanlegri stafarunu. Til að hjálpa okkur áfram upplýsti kennarinn að þrír öftustu stafirnir í upphaflegu skilaboðunum væru KDB, sem er fangamark hans.

Fyrsta skrefið var að komast að því nákvæmlega hvernig Enigma virkar. Við vorum eitthvað búnir að læra um það í námskeiðinu áður, en ekki nóg til að geta útfært Enigmahermi nákvæmlega í tölvu. Sem betur fer er töluvert af ítarlegu efni um þessa vél að finna á netinu.

Enigmavélarnar voru ekki sérlega flóknar meðförum. Þær voru lítið annað en ritvélar með áföstu ljósaborði. Stafirnir voru 26, þar sem Enigma notaðist við enska stafrófið. Á ljósaborðinu voru einnig 26 ljós, hvert um sig merkt með bókstaf. Sá sem bar ábyrgð á því að kóða skilaboð á vélina settist niður við hana með skilaboð fyrir framan sig og sló þau inn, einn staf í einu. Þegar ýtt var á hvern staf fyrir sig lýstist upp sá stafur á ljósaborðinu sem viðkomandi stafur kóðaðist yfir í, og þetta skrifaði kóðarinn niður. Þegar hann var búinn að fara í gegnum öll skilaboðin með þessum hætti, þá voru þau tilbúin til sendingar, oftast með útvarpsbylgjum sem óvinurinn gat numið, og því var nauðsynlegt að Enigmavélin væri traust og óbrjótanleg. Þjóðverjarnir töldu engar líkur á öðru, en raunin var önnur, eins og frægt er orðið.

Hvernig reyndu Þjóðverjarnir að tryggja að Enigma væri óbrjótanlegt? Galdurinn fólst í því að mismunandi stafir voru kóðaðir á mismunandi hátt, og þessir hættir breyttust daglega. Þetta var útfært þannig að inni í vélunum voru þrjú hjól mismunandi gerðar, sem reglulega voru valin handahófskennd úr hópi fimm hjóla. Hvert hjól gat verið í 26 mismunandi stöðum hverju sinni - þessum stöðum var líka breytt reglulega. Það sem gerðist síðan þegar ýtt var á staf á lyklaborðinu var að straumur fór í gegnum hjólin, sem skilaði sér yfir í ljósaborðið eftir hjólunum. Leiðin sem straumurinn fór var mismunandi eftir stöðu hjólanna. Aðalgaldurinn fólst síðan í því að hjólin snerust með hverjum staf sem sleginn var inn, þannig að næsti stafur var þá kóðaður með allt öðrum hætti, og svo kolli af kolli. Það var mjög sniðugur þáttur í hönnun vélarinnar að til að afkóða skilaboð var nóg að velja sömu hjól og setja þau í sömu upphafsstöður og voru notaðar til að kóða þau, slá inn kóðuðu skilaboðin, og þá skiluðu upphaflegu skilaboðin sér. Því var einfalt að afkóða skilaboðin ef maður vissi hvaða hjól og upphafsstöður þeirra voru notuð til að kóða skilaboðin. Ef maður vissi það ekki, þá var það eins og að reyna að finna nál í heystakki með því að týna eitt heystrá úr stakknum í einu.

Að herma eftir þessu ferli í tölvu var ekki léttvægt mál. Einnig flækti það málin að Þjóðverjarnir voru líka gjarnir á að nota aukaraftöflu með vélunum sem víxlaði stafapörum áður en og eftir að stafirnir fóru í gegnum hjólin. Fjölda slíkra víxlanna, sem og hvaða staf var víxlað við hvern, var líka hægt að velja handahófskennt. Sem betur fer notaði kennarinn smávaxni ekki nema tvær slíkar víxlanir, og sagði okkur frá þeirri staðreynd.

Eftir nokkurt stapp náðum við þó loks að herma eftir Enigmavél og gátum rennt skilaboðunum dularfullu í gegnum allar mögulegar upphafsstöður og dælt út öllum afkóðununum. Baráttan var hins vegar langt í frá unnin. Mögulegar upphafsstöður voru nefnilega allt í allt 60 (mögulegar leiðir til að velja og raða hjólum) * (26 * 26 * 26) (mögulegar upphafsstöður hjólanna) * ((26! /(2! * 24!)) * (24! /(2! * 22!)) (mögulegar leiðir til að víxla tveimur stafapörum) = 94.594.032.000. Töluverðan tíma tók tölvuna að fara í gegnum alla þessa möguleika og skrifa allar mögulegar afkóðanir í skrá, og algjörlega ómögulegt fyrir nokkurn mann að renna í gegnum þann lista til að reyna að finna nokkuð sem vit var í.

Við höfðum þó eina leið til að sigta í gegnum möguleikana - rétt afkóðuð skilaboð urðu að enda á KDB. Auðvelt var að bæta því skilyrði við í tölvuforritið okkar, og best var þá auðvitað að framkvæma afkóðunina afturábak til að forritið myndi strax geta séð þegar það var að byrja á rangri afkóðun, sem sparaði töluverðan tíma. Þetta var skref í rétta átt, en dugði ekki til. Við sátum samt sem áður uppi með lista upp á milljónir afkóðanna - langt í frá nægilega fáar til að raunhæft væri að fara yfir þær í höndunum. Aðalvandinn var því þessi: Hvernig gátum við látið tölvuna sigta út hvaða afkóðanir voru líklegri en aðrar til að vera réttar? Svarið lá engan veginn beint við; tölvur eru kórrökrétt apparöt og geta ekkert gert sem brýtur þeirra þrönga stærðfræðiramma.

Eftir nokkra umhugsun datt ég niður á rétt svar. Minnugur þeirrar staðreyndar, sem kennari okkar hamraði oft á, að tungumál eru ekki handahófskennd, hugsaði ég með mér að lausnin hlyti að felast í því að raða afkóðununum eftir því hversu handahófskennd þær væru. Kóðaði textinn var auðvitað mjög handahófskenndur, og allt annað en rétt afkóðun myndi þá skila handahófskenndu bulli líka. En rétta afkóðunin var, að því sem ég vissi, texti á ensku, og því langt í frá handahófskennd sem slík.

Næsta spurningin sem þurfti að svara var þá hvað felst í handahófskennd, sérstaklega í stærðfræðilegum skilningi, þar sem það er jú eini skilningurinn sem tölva getur beitt til að ákvarða nokkurn hlut. Svarið hér felst í tölfræði.

Það sem gerir tungumál óhandahófskennd er meðal annars sú staðreynd að í þeim koma mismunandi stafir mismunandi oft fyrir. Í handahófskenndum texta má hins vegar búast við því að dreifing stafanna sé jafnari. Stærðin sem ákvarðar slíka dreifingu nefnist staðalfrávik - hversu langt að jafnaði hver tala í talnarunu er frá meðaltali þeirra. Aðferðin sem ég ákvað að beita (eða nánar til tekið að láta tölvuna beita) var því þessi: Telja hversu oft hver stafur í afkóðuninni kemur fyrir, og reikna staðalfrávikið þar. Búast má við því að rétta afkóðunin sé með hærra staðalfrávik en þær röngu.

Þetta er allt saman tiltölulega auðvelt að reikna, sérstaklega fyrir tölvu - hún getur gert þetta á örskotsstundu, og er alls ekki lengi að því að gera slíkt jafnvel fyrir milljónir runa. Tölvur eru einnig mjög góðar í að raða hlutum, og því var einfalt mál að láta tölvuna í leiðinni raða afkóðununum eftir staðalfráviki; með afkóðunina með hæsta staðalfrávikið efst í listanum, og afganginn síðan í lækkandi röð eftir staðalfrávikum.

Þessi aðferð breytti öllu. Núna var þetta bara orðin spurning um að renna í gegnum efstu afkóðanirnar í listanum; sú rétta hlaut að vera ofarlega ef allt var rétt gert. Svo reyndist vera - það tók mig innan við mínútu að finna þá sem ég sá að var rétt. Félagarnir í hópnum voru að vonum glaðir þegar ég tilkynnti þeim að verkefnið væri leyst, en þó án efa ekki nærri því jafn glaðir og ég var yfir því að hafa náð að brjóta hinn fornfræga Enigmakóða.

Þegar upp var staðið var minn hópur sá eini sem náði að leysa verkefnið. Engum öðrum kom til hugar það skemmtilega bragð að flokka afkóðanirnar eftir staðalfrávikum. Reyndar er hæpið að hún hefði nýst Diffie-Hellman hópunum, þar sem sú aðferð er notuð til að kóða hreinar tölur en ekki texta, en hinir hóparnir hefðu án efa notið góðs af þessari flokkunaraðferð, þar sem þeir stóðu allir fyrr eða síðar gagnvart því vandamáli að þurfa að sigta í gegnum ógrynni af afkóðunum. Að ég skuli hafa verið sá eini sem fann góða leið til þess fyllti mig miklu stolti, sem ég bý við enn í dag.

   (31 af 49)  
2/11/04 22:01

bauv

Flott hvernig þú fannst þetta út, skál!

2/11/04 22:01

Skabbi skrumari

Þú ert snillingur... vel af sér vikið...

2/11/04 22:01

Nornin

Þú ert of gáfaður. Ég skildi ekki einu sinni allt sem stendur í félagsriti þessu [fær gáfnafarsminnimáttarkennd]

2/11/04 22:01

hlewagastiR

Verulega skemmtilegt rit. Reyndar eru vissir hlutir í tungumálinu handahófskennir (arbiterir), þ.e.a.s. samband málhljóða og merkingar orða. Það er t.d. ekkert í hljónunum J, Ö, R og Ð sem vísa eitthvað frekar til jarðarinnar en annað. Einu undantekningarnar eru hljóðlíkingar sbr. þegar fugl er kallaður bíbí.
Þarfi fékkst hins vegar við stafsetningu hér en hún endurspeglar nokkrun veginn hljóðkerfi tungumáls. Öll hljóðkerfi eru mjög formföst og full af reglum og hömlum. Það er mitt fræðasvið. Það var sannarlega snjallt að leggja það til grundvallar við laun þessa skemmtilega og krefjandi verkefnis.

2/11/04 23:00

Jóakim Aðalönd

Jamm. Þetta var vel af sér vikið Þarfi. Ég er ekki viss um að ég hefði fattað þetta. Ég hefði verið til í að vera í þessu námskeiði.

2/11/04 23:00

B. Ewing

ég gat ekki lesið þetta en engu að síður, snilld. [Bókar tíma fyrir lestur á ritinu]

2/11/04 23:00

dordingull

Vel af sér vikið, vægast sagt. En hvernig tókst Englendingum að leysa dæmið, tölvulaust og án vísbendinga, komust þeir yfir vél eða hvað? Man þetta ekki alveg.

2/11/04 23:00

kolfinnur Kvaran

Go Þarfi

2/11/04 23:00

Jóakim Aðalönd

Ef ég man rétt, komust þeir yfir vél og kóða líka og náðu þannig að krakka þetta.

2/11/04 23:00

Þarfagreinir

Englendingarnir notuðu margar aðferðir og gríðarmikinn mannskap til að leysa gátuna. Einnig höfðu þeir mekanískar vélar til að fara í gegnum afkóðanir; gríðarstór apparöt sem voru látin malla allan sólarhringinn. Þeir höfðu líka dálítið forskot í boði pólsku leyniþjónustunnar, sem hafði rannsakað Enigma töluvert áður en stríðið byrjaði. Þegar útlit var fyrir að stríð væri að hefjast komu Pólverjarnir vitneskju sinni í mikilli leynd til Englendinganna svo þeir gætu haldið áfram vinnunni.

Ýmsum brögðum var hægt að beita til að einfalda þessa vinnu. Til dæmis má nefna að þar sem að upphafsstillingunum á Enigma-vélunum var breytt tiltölulega sjaldan, þá var töluverður fjöldi skilaboða kóðaður út frá sömu upphafsstillingu. Ef hægt var að giska á að ákveðin orð eða orðasambönd kæmu fyrir á ákveðnum stöðum í ákveðnum skilaboðum, þá var auðveldara að brjóta viðkomandi skilaboð. Þegar upphafsstillingarnar voru fundnar var síðan auðvitað lítið mál að afkóða öll hin skilaboðin í sama upphafsstillingahópi. Ef allt annað brást var meira að segja hægt að 'búa til' skilaboð. Þetta mátti gera með því að til dæmis láta eitthvert skip viljandi sjá ákveðna flugvél, og bíða eftir því að skipið sendi skilaboð - þá var auðvitað öruggt að orð á borð við 'flugvél', gerð flugvélarinnar, o.s.frv., myndu koma fyrir í skilaboðunum.

Þegar þetta starf var komið svo vel á veg að Englendingarnir gátu lesið stærstan hluta skilaboða Þjóðverjanna, þá var aðalvandamálið að ákveða við hverjum þeir áttu að bregðast og við hverjum ekki. Ef þeir hefðu brugðist við of mörgum þeirra, þá hefðu Þjóðverjarnir án efa uppgötvað að ekki kæmi annað til greina en að Enigma væri brotið, og hefðu þá hætt notkun vélanna - og þá hefði auðvitað allt verið unnið fyrir gíg. Að passa upp á það að ekki væri of augljóst að Englendingarnir læsu öll þessi skilaboð var list út af fyrir sig.

2/11/04 23:00

dordingull

Þakka þér fyrir þetta, það var gaman að fá þessa upplýsingar. Það hafa veri gerðar svo margar kvikmyndir og margar sögur skrifaðar um það hvernig bandamenn komust yfir dulmálsvél að maður var farinn að rugla öllu saman, en einhvervegin minnti mig að Englendingum hefði að mestu tekist þetta upp á eigin spýtur.

2/11/04 23:01

Vladimir Fuckov

Mjög fróðlegt og óvenjulegt verkefni sem hlýtur að hafa verið óvenju áhugavert. Eftir að hafa lesið þetta finnst oss sem að ef vjer hefðum einhverntíma lent í svona verkefni hefði oss líka getað dottið í hug að finna einhverja aðferð til að finna hvaða bókstafaruna 'líkist' texta mest í einhverjum stærðfræðilegum skilningi. Þetta er reyndar auðvelt að fullyrða eftir að hafa lesið þetta og ekki alveg víst hvað hefði gerst í reynd [Horfir með uppgerðargáfumannasvip út í loftið]. Svo eru auðvitað vissar bókstafaraðir er aldrei koma fyrir í tungumáli (t.d þýsku eða ensku).

Ein spurning vaknaði við lesturinn: Er Þjóðverjarnir sendu svona skilaboð sín á milli hvaða aðferð var notuð til að tryggja að móttakandinn vissi hvernig átti að afkóða skilaboðin, þ.e. hvaða hjól og hvaða upphafsstöður átti að nota við það ?

2/11/04 23:01

Þarfagreinir

Vladimir, mér skilst að þetta hafi verið framkvæmt með því að útbúa mánaðarlega blöð þar sem skráðar voru niður stillingarnar fyrir hvern dag mánaðarins. Þessum blöðum var síðan dreift á allar vélarnar. Þar sem þessi blöð voru augljós árásarpunktur, þá pössuðu Þjóðverjarnir mjög vel að þessi blöð kæmust ekki í óvinahendur. Þetta reyndist auðvitað þegar allt kom til alls þó ekki duga til að halda skilaboðunum leyndum.

3/11/04 00:00

Hakuchi

Fróðlegt í alla staði. Vel af sér vikið.

3/11/04 00:01

Steinríkur

Voðalegt vesen er þetta...
Ef textinn var kominn í textraskrá - gátuð þið þá ekki grep-að út línur sem byrjuðu á KGB og hent því í gegnum orðabókarleiðréttingu.
Línur sem breytast ekki væru þá á ensku...

3/11/04 00:01

Þarfagreinir

Þú átt væntanlega við línur sem enda á KDB, Steinríkur, en ég skil hvað þú ert að fara. Við þessu hef ég tvennt að segja:

1) Ég vissi varla hvað Linux var þegar ég vann þetta verkefni.
2) Þó svo að mér sýnist að aðferðin sem þú leggur til myndi án efa virka vel, þá er hún ekki nærri því jafn fræðileg né skemmtileg og hin.

Þú ræður hvort þú lítur á þetta sem afsakanir eða rökstuðning.

Þarfagreinir:
  • Fæðing hér: 5/10/04 00:11
  • Síðast á ferli: 13/12/20 16:11
  • Innlegg: 13121
Eðli:
Ég er Þarfagreinir. Ég hef mikið yndi af því að þarfagreina. Ef ykkur vantar mann til að sjá um þarfagreiningarþarfir ykkar, þá er ég sá maður.
Fræðasvið:
Þarfagreining fyrst og fremst. Einnig etanólrannsóknir, orðkynngi, algrím, og listfræði.
Æviágrip:
Ég var eitt sinn týndur og sótti Menntaskólann í Reykjavík. Síðan gerðist ég tossi og fór í Fjölbraut í Breiðholti og hóf etanólneyslu. En það var ekki fyrr en í Háskóla Íslands að ég fann mína sönnu hillu í lífinu, en það er auðvitað hið merka fræðasvið er þarfagreining nefnist. Fyrir áhugasama um þarfagreiningu þá er það fyrst að nefna hún kennd innan tölvunarfræðinnar. Reyndar er ýmislegt fleira gagnslaust rusl kennt þar; mín skoðun er sú að fella mætti allt slíkt niður og kenna þarfagreiningu eingöngu, enda er það göfugasta fræðasvið þessa heims, sem og allra annarra.

Nú í dag stunda ég fræði mín við virðulega stofnun í höfuðstað Íslands. Samhliða því eyði ég óhemju miklum tíma í rannsóknarvinnu ýmis konar á Alnetunum. Miðar þetta allt að því að ég uppfylli mitt æðsta markmið, sem er að verða Yfirþarfagreinir alheimsins.