Simovits

Cryptopals – del 1 av ?

Introduktion

Dagens första bloggpost (av två!) är lite annorlunda mot vad dessa bloggar vanligtvis brukar handla om, och kommer prata lite grann om sidan:

cryptopals.com.

Kanske är detta början på en bloggserie? Vi får se. Troligtvis kommer denna text bestå av raljerande över strunt-detaljer, så läsaren beds ha överseende med detta. Dessutom kan nämnas att texten har skrivits ganska så snabbt, så fel förekommor utan tvekan.

Cryptopals är en sida skapad av Thomas Ptacek et al. och består av ett antal programmeringsuppgifter som kan användas för att lära sig grundläggande kryptografiska standarder som används på internet.

Planen med denna bloggpost är inte att gå igenom lösningarna till uppgifterna (dessa kan man säkerligen googla efter om man så önskar), utan istället gå igenom lite teori bakom uppgifterna och förklara lite kuriosa om dem. Vi får se hur långt vi kommer med dagens post.

Set 1: Basics

Challenge 1: Convert hex to base64

Denna uppgift går ut på att konvertera en sträng av hexadecimala tecken till en sträng skriven i bas 64. Ni får nu unna mig möjligheten att förklara vad detta betyder genom att börja från början:

När man lärde sig räkna som barn så lärde man sig sekvensen: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, osv. Dessutom lärde man sig att dessa tecken motsvarade specifika tal. Exempelvis lärde vi oss att:

tecknet “1” beskrev hur många extra kakor man fick äta till fikat (“Ja, du får ta 1 till…”),

tecknet “2” kunde användas för att beskriva hur många armar man hade (inget illa menat till de med fler eller färre antal armar), och att

tecknet “12” motsvarade antalet tim-streck på en klassisk väggklocka.

Just hur dessa tecken ser ut spelar egentligen ingen roll, och är bara någonting vi som samhälle har valt att standardisera. Använder man istället romerska siffror skriver man “VII” istället för “7”, men båda beskriver hur många dagar det är på en vecka. Notera också att vi i vårt samhälle i grunden enbart använder tio olika tecken (0,1,2,3,4,5,6,7,8,9) som vi sedan sätter ihop i olika kombinationer för att skriva större tal.

Varför vi använder just tio stycken tecken kan man filosofera länge om. Jag väljer att tro att det är för att vi har precis så många fingrar (igen, inget illa menat till de med ett annat antal fingrar), eftersom det är fingrarna vi oftast använt för att räkna med. Med fingrarna är det lätt att räkna till tio, men när vi får slut på fingrar så löser vi det genom att börja om räknandet av fingrar med “minnet” av att vi redan använt alla fingrar en gång:

Första räkningsvarvet: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9
Andra räkningsvarvet: 10, 11, 12, 13, 14, 15, 16, 17, 18, 19
Tredje räkningsvarvet: 20, 21, 22, 23, 24, 25, 26, 27, 28, 29
osv.

Med detta vill jag motivera varför det talsystem som vi dagligen använder talbasen tio – att vi använder tio olika tecken (en för varje finger). Man kan fråga sig hur det skulle vara om vi som diverse tecknade figurer skulle ha färre fingrar. Om vi exempelvis skulle haft tre fingrar på varje hand, så skulle vi kanske istället bara använt sex tecken (0,1,2,3,4,5) och då skrivit:


Första räkningsvarvet: 0, 1, 2, 3, 4, 5
Andra räkningsvarvet: 10, 11, 12, 13, 14, 15
Tredje räkningsvarvet: 20, 21, 22, 23, 24, 25
osv.

Detta är ett talsystem som använder basen sex. I detta fall så skulle “10” inte motsvara talet tio så som vi känner till det utan istället beskiva antalet strängar på en klassisk gitarr (som vi i daglig skrift skriver som “6”).

Nu kanske läsaren av denna text är lite undrande över var detta är på väg. Poängen vi vill komma till är att datorer (som är centrala för kryptografi) inte har tio fingrar, och därför är det inte naturligt för dessa att använda samma bassystem som oss människor.

På en grundläggande nivå kan man tänka sig att en dator har två fingrar – den kan avläsa om det går ström genom en transistor (1) eller inte (0). En innebörd av detta är att datorer är väldigt bra på att jobba med tal skrivna i basen två (det binära talsystemet):

Bas 2:     0   1   10  11  100 101 110  111
Bas 10:    0   1   2   3   4   5   6    7

Vi kan kalla detta en bit. Nu är det ju dock så att datorer består av fler än en transistor (i dagens CPUer kan dessa räknas i miljarder) så datorer kan använda flera transistorer parallellt för att skapa sig fler fingrar att räkna med (som alla blir olika potenser av 2 – antalet utfall från en transistor).

Om man exempelvis använder bas 16, den hexadecimala basen, uppstår dock ett problem om man är van vid att arbeta i vår klassiska bas 10. Det behövs nämligen sexton olika tecken för att kunna uttrycka alla tecken i den hexadecimala basen, vilket är fler än de tio (0-9) tecken som vi är vanliga med. Detta löses genom att vi inför “nya” tecken för de extra talen som nedan:

Bas 16: 0 1 2 3 4 5 6 7 8 9  a  b  c  d  e  f 10 11 12 13 14 15 16 17 18 osv
Bas 10: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 osv

Använder man baser med ännu fler tecken får man lägga till ännu fler tecken. I bas 64 använder man alla stora och små bokstäver, samt siffror och tecknen “+” och “/” för att komma upp i just 64. Notera att för denna bas är värdena som dessa tecken motsvarar inte samma som i vårt klassiska system:

Bas 64: A B C ... Z  a  b  c  ... z  0  1  2  ... 9  +  /
Bas 10: 0 1 2 ... 25 26 27 28 ... 51 52 53 54 ... 61 62 63

En annan trevlig bas som datorn använder är bas 128 – även känd som ASCII. I denna bas motsvarar exempelvis tecknet “M” talet 77 och “backspace” av talet 8. I datorer används oftast bytes som motsvaras av 8 bitar. En byte kan därför ha 2^8=256 olika värden. Det finns olika utvidgningar av ASCII till de resterande 256-128=128 värdena av en byte, vilket möjliggjort att vi kan använda exempelvis svenska tecken (å, ä, ö) i datorer på ett effektivt sätt.

För att återgå till bas 64 lite snabbt, kan man inse att 64=2^6 inte går jämnt ut med storleken av en byte (2^8). I datorer skrivs därför bas 64 i termer av tupler av 4 (4*6=24=8*3). På grund av detta görs specialfall med padding, genom tecknet “=”, i bas 64 så att det går jämnt ut med storleken på en byte.

Uppgiften går alltså ut på att man har en sträng av hexadecimala tecken – det vill säga ett stort tal uttryckt i bas 16 – och man ska skriva detta tal i basen 64 istället. Själva implementation av detta lämnas till läsaren.

Challenge 2: Fixed XOR

Som nämndes i texten ovan arbetar datorer med binära tal (tal skrivna i bas 2). Datorn kan som tur är göra mer än bara titta på dem. Exempelvis kan den utföra operationer på tal. Några av de mest grundläggande operationerna är AND, OR och XOR som opererar på separata bitar. Dessa kan definieras enligt nedan:

AND: 
1 AND 1 = 1       1 AND 0 = 0       0 AND 1 = 0       0 AND 0 = 0  

OR: 
1 OR 1 = 1        1 OR 0 = 1        0 OR 1 = 1        0 OR 0 = 0 

XOR: 
1 XOR 1 = 0       1 XOR 0 = 1       0 XOR 1 = 1       0 XOR 0 = 0

Tänker man på 1 som sant och 0 som falskt blir de två översta ganska naturliga:

XOR är inte lika naturlig i detta sammanhang – den är enbart sann om precis en av de två argumenten är sann.

Denna XOR-funktion blir istället mer naturlig i ett annat sammanhang. Klassisk addition av tal lär sig alla i grundskolan (12+3=15, etc). En annan form av addition som man lär sig i skolan är addition av olika klockslag. Där har man den extra egenskapen att summan av två timmar räknas på en cirkel (speciellt om man tänker sig en klassisk analog väggklocka), där till exempel 8+7=15=3 då 12 och 0 är samma sak.

Detta är ett exempel på moduloräkning. För att införa lite matematisk notation kan vi skriva mängden av timmar – 0,1,2,3,4,5,6,7,8,9,10,11 – som Z/12Z (där notationen syftar på att 12=0, och Z står för mängden av alla heltal) och additionen på denna mängd görs modulo 12. Detta är något som man kan ha fått höra talas om antingen på gymnasiet eller på högskolan/universitetet. Att definiera detta i detalj undviker vi dock i denna text.

XOR blir mer naturlig om man tänker på en bit som ett element i gruppen Z/2Z (heltalen modulo 2). Då kan man skriva “a XOR b” som “a+b (mod 2)”, vilket, åtminstone för författaren, känns som en naturlig operation.

En byte som består av 8 bitar kan man tänka på på (åtminstone) två olika sätt. Antingen som ett element i Z/256Z (heltalen modulo 256) eller som ett element i (Z/2Z)^8 (åtta kopior av Z/2Z). Innehållet i dessa två mängder är i princip samma (det finns en bijektion mellan mängderna som är att konvertera mellan bas 256 och bas 2). Skillnaden är hur den naturliga additionen på dessa två grupper är definierad. Antingen har man

En trevlig egenskap hos addition modulo 2 är att addition och subtraktion blir samma sak.

Denna uppgift går ut på att använda den andra definitionen av addition (XOR) av bytes och utvidga denna till addition av strängar. Exempelvis blir XOR av två strängar med fyra bytes en ny sträng med fyra bytes:

“abcd” XOR “defg” = “(a XOR d)(b XOR e)(c XOR f)(d XOR g)”.

Challenge 3: Single-byte XOR cipher

En väldigt klassisk kryptoalgoritm är Ceasarchiffret. Klassiskt går den ut på att man förflyttar alla bokstäver som man vill kryptera med en viss längd.

Exempel:
Låt alfabetet bestå av A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T,U,V,W,X,Y,Z.
Krypterar man texten “CEASAR” med Ceasarchiffret med nyckeln: “D” – den tredje bokstaven till höger om A i alfabetet – innebär det att alla bokstäver byts ut mot tecknet 3 positioner senare i alfabetet:

A->D, B->E, C->F, …, V->Z, W->A, X->B, Z->C

Kryptotexten blir alltså:

“FHDVDU”

Notera här att denna substitution sker cykliskt så att bokstäver till höger om Z börjar räknas om från och med A.

Den observanta läsaren kan kanske här inse att detta kan uttryckas med hjälp av moduloräkning som beskrevs ovan. Ifall vi låter

A=0, B=1, C=2, …, Z=25,

så kan vi uttrycka vårt alfabet som Z/26Z och vårt Ceasarchiffer blir enbart addition modulo 26 med D=3. Dekryptering kan göras genom att göra motsatsen – ta subtraktion med D=3.

Om vi skulle vilja göra samma sak på en dator så kan man tänka sig att vi betraktar alla möjliga värden för en byte (en utvidgad ASCII) som vårt alfabet, och Ceasarchiffer som en addition på detta alfabet med ett fixerat värde. Som vi förklarade i den förra uppgiften så finns två möjliga additioner av bytes, och den addition som används i kryptosammanhang är ofta den som kommer från XOR-funktionen. Som exempel kan strängen “SIMOVITS” krypteras med nyckelbyten “X” genom att beräkna

“SIMOVITS” XOR “XXXXXXXX”.

För denna addition gäller det att kryptering och dekryptering görs på samma sätt (eftersom substraktion är samma sak som addition).

I uppgiften får man en sträng av bytes (skrivna hexadecimalt), som vi får veta är en krypterad sträng via ett Ceasarchiffer (med XOR-addition). Datorer är väldigt bra på att göra många uträkningar på kort tid, så denna uppgift är lätt att lösa genom att ta sin krypterade sträng och, med hjälp av XOR-funktionen från förra uppgiften, testa additionen (=subtraktion) med alla möjliga byte-värden (256 stycken) som kan ha använts vid krypteringen.

Någon av dessa 256 strängar kommer ge en begriplig text, och det enda man behöver göra är att ge datorn direktiv för vad vi tycker är mest “begripligt”. Detta kan göras genom att poängsätta strängar utifrån vilka tecken som strängen innehåller (ge höga poäng till skrivbara tecken och låga poäng till allt annat).

Challenge 4: Detect single-character XOR

Vi skippar att prata om uppgift 4 då den inte innehåller någon intressant ny information. Man ska bara göra samma sak som 3an på flera strängar.

Challenge 5: Implement repeating-key XOR

Vigenère-chiffer är en utveckling av Ceasarchiffret och bygger på att istället för att använda en enda nyckelbokstav (som D=3 ovan) använder man ett nyckelord istället. Exempelvis kan man använda nyckelordet “ABC” på texten “SIMOVITS”. Det betyder att man flyttar:

S:et på första positionen A=0 steg åt höger,
I:et på andra position B=1 steg åt höger,
M:et på tredje positionen C=2 steg åt höger.

Om texten man ska kryptera är längre än nyckelordet kan man göra på olika sätt – exempelvis (som förklaras i uppgiften) återupprepar man nyckelordet om och om igen. 

SIMOVITS
ABCABCAB

På samma sätt som i med Ceasarchiffret kan Vigenère-chifferet implementeras i en dator med hjälp av XOR-funktionen:

“SIMOVITS” XOR “ABCABCAB”

Uppgift 5 går ut på att implementera denna algoritm. Längre än så här hann vi inte idag.

Publicerat 2019-10-11 Skrivet av Gustav Sædén Ståhl