GCM (Galois / Counter Mode), särskilt i kombination med AES, har varit en de facto guldstandard i flera år. Kryptera och autentisera i ett steg, det är alldeles för fantastiskt, och termer som AEAD fungerar bra för att imponera på en tjej, så det skulle vara vinn-vinn. Men skämt åt sidan …
Jag har alltid undrat vad som gör det så speciellt, och ju längre jag tänker på det, desto mindre förstår jag. Om du tittar på det, så är den övergripande magin inte alls så fantastisk. Eller kanske, jag är kanske bara för dum för att groka det (därav min fråga).
Mina tankar:
Först och främst är GCM en form av räknarläge . Vilket innebär att till skillnad från t.ex. cipher block chaining, beror utsignalen från ett block på exakt ett block av input. Ännu värre: Du kan ändra en enda bit och det dekrypterade resultatet kommer att skilja sig åt exakt den biten. För om du är ärlig är en blockkodning i räknarläge inte en ” blockkryptering ”, utan en (nycklad) PRNG följt av en XOR-operation. I grund och botten en ” blocky ” strömkryptering. Det krävs inte mycket för att föreställa sig ett scenario där någon kan missbruka detta för att ändra meddelanden på ett skadligt sätt (t.ex. ändra ” transaktion: +5 000 \ $ ” till ” transaktion: -5,000 \ $ ”). Blockkodningar har normalt den medfödda egenskapen att förvandlas till fullständigt gibberish när du vänder en enda bit (plus, med kedjning, hela resten av meddelandet). Det är faktiskt en ganska trevlig, önskvärd egenskap, som vi bara kastade överbord utan goda skäl.
Visst, med autentiseraren ovanstående attack är svår att uppnå eftersom manipuleringen kommer att upptäckas. Men i grund och botten fixar autentiseraren bara problemet att valet av driftsätt introduceras .
GHASH är en MAC som stöder extra autentiserad data. Enligt vad jag kan säga är det ”en fullständig lögn. Eller kallar det ” optimistisk överdrift ” om du vill. Det är bara en kompressionsfunktion med icke-intuitiv matematik (till icke-matematiker) bakom, men i slutändan gör det ingenting annat än en enkel multiplikation och slänga bort hälften av inmatningsbitarna med motsvarigheten till ” överflöde ”. Vilket är precis vad, med mer vardaglig matematik, kan göras i två rader C-kod per block inom ett dussin cykler (eller om du är OK med att använda 32-bitars multiplikationer snarare än 64, kan göras parallellt t.ex. med AVX2 ” s vpmulld för två kompletta block i ~ 4 cykler).
De som fortfarande kommer ihåg IDEA kommer ihåg att de använde additionsmod 2 16 och multiplikationsmod 2 16 + 1 som S-lådor som hade den fina egenskapen att vara reversibla (ganska nödvändigt om du vill dekryptera). Tyvärr kunde detta inte utvidgas till 32-bitar eftersom 2 32 +1 inte är ”ta primtal, så inte alla ingångar garanteras vara relativt primära för det, och därmed har du problem med att invertera operationen. Men … det är väldigt bra i vårt fall, vi vill inte vår kompressionsfunktion är inverterbar! Så verkligen, ” enkel ”, skulle vanlig multiplikation bara göra tricket också?
Så, den enkla, inte speciella, ingen magiska komprimeringen funktion råkar vara initierad med nyckeln och IV, vilket för övrigt gör den slutliga utgångsnyckelberoende på ett eller annat sätt, så att den vanliga funktionen effektivt blir en MAC. Om du har ” extra data ” matar du bara in det i hashen innan du krypterar dina data, gjort. Återigen, det är inte något särskilt speciellt.
Sammantaget är det ingenting som du inte kunde uppnå med ganska mycket alla andra hashfunktioner också.
Nu förutsätter Galois / räknare att räknarläge används. Räknarläge (och dess derivat) liksom GHASH har fördelen att du kan kryptera / dekryptera block parallellt. Dessutom är GHASH trivialt parallelliserbar. ! Men låt oss vara ärliga, är detta verkligen en fördel, eller snarare en enorm nackdel ?
Spelar det någon roll hur lång tid det tar att dekryptera en gigabyte- eller terabyte-storlek meddelande och hur bra kan du parallellisera det arbetet? Eller applikationer där du absolut vill kunna ” söka ” till slumpmässiga positioner? Det finns applikationer där det kan betyda, visst. Full disk kryptering kommer att tänka på. Men du skulle inte vilja använda GCM i så fall eftersom du vill att inmatningsstorlek och utdatastorlek ska vara identiska.
För en upptagen server (eller VPN) kommer det att betyda, eller så verkar det , men dessa kan behandla vad som helst parallellt ändå eftersom de har många samtidiga anslutningar.Så om du inte kan parallellisera en ström gör det egentligen ingen skillnad totalt sett. Vad sägs om applikationer där det bara finns få anslutningar? Du överför vanligtvis inte terabyte med data via en inloggningsterminal, och om du gör det är din internetanslutning troligtvis den begränsande faktorn ändå, eftersom prestanda med en enda kärna lättare än GbE-bandbredd även på 7-8 år gamla stationära processorer .
Okej, du kan behöva vänta 2-3 sekunder längre när du extraherar en krypterad 2TB 7z-fil på hårddisken (om du skapar tusentals katalogposter är inte riktigt flaskhalsen, som jag är benägen att tror kommer att vara fallet). Hur ofta har du gjort det under det senaste året? Jag: noll gånger.
De enda som det verkligen gör skillnad för är ” skurkar ”, dvs exakt de som du inte vill ha ett enkelt liv. Visst nog, om du trivialt kan parallellisera, blir attacker mycket lättare. Kasta ett rum fullt av dedikerad hårdvara (GPU: er, FPGA: er, vad som helst) på problemet och låt det mala bort. Ingen kommunikation mellan noder behövs? Tja, perfekt, det kan inte bli bättre.
Är det verkligen en fördel? Jag vet inte, för mig ser det ut som en enorm nackdel. Om något vill jag göra parallelliseringen så svår som möjligt, inte så lätt som möjligt.
Så … tillräckligt fundering och till frågan:
Vad är grundläggande sak som jag saknar om GCM som gör det så fantastiskt att du absolut borde använda det?
Kommentarer
- Men vem är ” skurkar ” är omöjligt att definiera. Och det har ENORM inverkan på regeringens rekommendationer och svaren i det här forumet.
Svar
TL; DR: GCM ger utmärkt prestanda med de bästa säkerhetsegenskaperna vi förväntar oss av chiffer idag (AEAD).
GCM använder CTR för att bygga en streamcipher. Detta är en väl studerad metod, som bara har en nackdel: den behöver absolut en del autentisering för att förhindra att bitar vänder. Innan GCM var CTR-då-MAC lösningen. En viktig fördel med strömkodare är frånvaron av utfyllnadsattacker (eftersom det inte finns något behov av utfyllnad). En annan fördel är att AES-CTR kan dra nytta av AES-NI-instruktionerna.
GCM är CTR-då-MAC med bättre prestanda . En viktig förbättring jämfört med CRT-då-MAC är möjligheten att överlappa exekveringen av kryptering och autentisering. Dessutom har det visat sig vara säkert i den konkreta säkerhetsmodellen och det belastas inte av patent, så det är ingen idé att använda den.
Det har vissa nackdelar: det är inte effektivt i inbäddad hårdvara. och det är svårt att implementera effektivt. Den sista punkten motverkas genom att använda bibliotek skrivna av andra. Det är dock skäl till varför xchacha20-poly1305 blev populär över GCM.
Kommentarer
- Jag skulle argumentera för en annan anledning till att ChaCha20 har vunnit popularitet är att det inte är AES. Inte ’ får inte fel på mig, AES är en bra algoritm, men att lägga bokstavligen alla våra ägg i en korg är kanske inte den smartaste av alla idéer. Och att ha en annan väl testad algoritm förutom AES är ganska värdefullt
- @ MechMK1 Jag håller med dig , men jag skrev inte att de är alla orsakerna till ChaCha20 ’ s popularitet, för att ’ s inte frågan här. Min poäng var t hat GCM anses inte vara ” fantastisk ” som OP menar.
- Helt sant. Det ’ är inte en gyllene gås, men ingen fick någonsin sparken för att använda AES-GCM, så att säga.
- Och det ’ är inte patenterade.
- @StephenTouset Tack, jag redigerade mitt inlägg för att inkludera din kommentar.
Svar
Först och främst är GCM en form av räknarläge. Vilket innebär att till skillnad från t.ex. cipher block chaining, beror utsignalen från ett block på exakt ett block av input. Ännu värre: Du kan ändra en enda bit och det dekrypterade resultatet kommer att skilja sig åt exakt den biten. För om du är ärlig är en blockkodning i räknarläge inte alls en ”blockcipher” utan en (nycklad) PRNG följt av en XOR-operation. I grund och botten en ”blocky” strömkryptering. Det krävs inte mycket för att föreställa sig ett scenario där någon kan missbruka detta för att ändra meddelanden på ett skadligt sätt (t.ex. ändra ”transaktion: +5 000 \ $” till ”transaktion: -5 000 \ $”).
Meddelandeautentisering som GCM-lager ovanpå CTR gör dess smidighet obetydlig.
Blockkodningar har normalt den medfödda egenskapen att förvandlas till fullständig gibberish när du vänder en enda bit (plus, med kedjning, hela resten av meddelandet) . Det är faktiskt en ganska trevlig, önskvärd egenskap som vi bara kastade överbord utan goda skäl.
Detta är väldigt, väldigt fel. Först och främst , CBC-läge lider också av en slags svaghet i formbarhet; om du vänder en bit av chiffertexten, krypterar du bara ett block och vänd motsvarande bit i nätblocket. Och det finns andra smidighetsattacker mot CBC; se till exempel EFail-attacken .
Mer allmänt är din informella uppfattning om att meddelanden ”förvandlas till ett fullständigt plåster” inte tillräckligt bra. Vi behöver absolut datorer för att mekaniskt upptäcka, med ett bestämt ”ja / nej” -svar, när ett krypterat meddelande har förfalskats. Att lita på att en människa kommer att vara tillräckligt tidigt för att upptäcka ”gibberish” är inte tillräckligt.
GHASH är en MAC som stöder extra autentiserad data. Enligt vad jag kan säga är det en lögn. Eller kalla det ”optimistisk överdrift” om du vill. Det är bara en kompressionsfunktion med icke-intuitiv matematik (till icke-matematiker) bakom, men i slutändan gör det ingenting annat än en enkel multiplikation och slänga bort hälften av inmatningsbitarna med motsvarande ”överflöd”.
MAC fungerar inte för att användarna inte förstår matematiken. Det är som att folk inte kan titta på satellit-TV för att de inte vet inte kalkyl. Finite field MACs är en standardkonstruktion, känd i årtionden nu.
Vilket är precis vad, med mer vardaglig matematik, kan göras i två rader av C kod per block inom ett dussin cykler (eller om du är OK med att använda 32-bitars multiplikationer istället för 64, kan göras parallellt, t.ex. med AVX2 ”s vpmulld för två kompletta block i ~ 4 cykler).
Det diskuteras faktiskt om MAC-baserade på Galois-fält som GHASH, eller MAC-baserade på primära fält som Poly1305, är ett mer praktiskt val. Mycket av det beror på avvägningarna mellan att designa MAC: er för att betona programvara kontra hårdvaruimplementeringar, t.ex. Galois-fältmultiplikationer är mardrömmande i programvara, men mycket enklare än aritmetiska multiplikationer i hårdvara. .
Men det finns ingen debatt om antingen Galois-fält eller primära fält i grunden är osäkra nd. Matematiken kolla in båda.
Yay, performance! Men låt oss vara ärliga, är detta verkligen en fördel, eller snarare en enorm nackdel?
Berätta för de oändliga paraderna av ingenjörer genom decennierna som har motstått att lägga till kryptering till produkter på grund av prestanda. Och tänk inte bara på kraftfulla datorer; tänk på inbäddade enheter och var väldigt rädd för sakernas internet.
Jag menar, det här är inte en död fråga alls. Under de senaste åren har det skett en kraftig debatt och utvecklingen av en ny kryptografisk konstruktion för att stödja fullskivkryptering på low-end Android-enheter som bedömdes inte tillräckligt kraftfullt för de AES-baserade algoritmerna som Android erbjuds tidigare.
De enda som [performance] verkligen gör skillnad är ”bad guys”, dvs. exakt de som du inte vill ha en enkelt liv. Visst nog, om du kan trivialt parallellisera, blir attacker mycket enklare. Kasta ett rum fullt av dedikerad hårdvara (GPU: er, FPGA: er, vad som helst) på problemet och låt det slipa bort.
Kodare löser detta genom att använda tillräckligt stora nyckelstorlekar, inte genom att låta koderna sakta ner. Det bekymmer du tar upp uppstår i lösenordsbaserad kryptografi där du inte ”t har tillräckligt entropiska hemliga nycklar. 256-bitars symmetriska nycklar kommer för alltid att vara mer än stora nog för att besegra alla brutala kraftattacker i vårt universum.
Vad är det grundläggande som jag saknar om GCM som gör det så fantastiskt att du absolut borde använda det?
Du behöver inte absolut använda GCM Det är samtidigt:
- Fundamentall y-ljud och mycket stött i hårdvara;
- Besvärade av ett antal nackdelar som du inte tog upp, som dålig programvaruprestanda och katastrofalt äkthetsfel vid icke-återanvändning, som ofta diskvalificerar det i vissa praktiska sammanhang .
Om du har hårdvara som har inbyggt AES-GCM-stöd och väl granskad programvara som utnyttjar den, skulle det vara klokt att inte ha den bland dina bästa kandidater.