Yarrow algoritm
Yarrow -algoritmen är en familj av kryptografiska pseudoslumptalsgeneratorer (CPRNG) framtagna av John Kelsey , Bruce Schneier och Niels Ferguson och publicerade 1999. Yarrow-algoritmen är uttryckligen opatenterad, royaltyfri och öppen källkod; ingen licens krävs för att använda den. En förbättrad design från Ferguson och Schneier, Fortuna , beskrivs i deras bok, Practical Cryptography
Yarrow användes i FreeBSD , men ersätts nu av Fortuna. Yarrow införlivades också i iOS och macOS för deras /dev/random- enheter, men Apple har bytt till Fortuna sedan 2020 Q1.
namn
Namnet Yarrow anspelar på användningen av röllekaplantan i den slumpmässiga genereringsprocessen av I Ching-spådomar . Sedan Xia-dynastin (ca 2070 till ca 1600 fvt) har kineser använt rölleka stjälkar för spådom. Spåmäklare delar upp en uppsättning av 50 rölleka stjälkar i högar och använder modulär aritmetik rekursivt för att generera två bitar av slumpmässig information som har en olikformig fördelning .
Principer
Yarrows huvudsakliga designprinciper är: motstånd mot attacker, enkel användning av programmerare utan kryptografisk bakgrund och återanvändning av befintliga byggstenar. De tidigare mycket använda designerna som ANSI X9.17 och RSAREF 2.0 PRNG har kryphål som ger attackmöjligheter under vissa omständigheter. Vissa av dem är inte utformade med verkliga attacker i åtanke. Yarrow syftar också till att tillhandahålla enkel integration, för att möjliggöra systemdesigners med liten kunskap om PRNG-funktionalitet.
Design
Komponenter
Utformningen av Yarrow består av fyra huvudkomponenter: en entropiackumulator , en reseed -mekanism, en genereringsmekanism och reseed-kontroll.
Yarrow ackumulerar entropi i två pooler: den snabba poolen, som ger frekventa reseeds av nyckeln för att hålla varaktigheten av nyckelkompromisser så kort som möjligt; den långsamma poolen, som ger sällsynta men konservativa reseeds av nyckeln. Detta säkerställer att återfröet är säkrat även när entropiuppskattningarna är mycket optimistiska.
Återsåddsmekanismen förbinder entropiackumulatorn med genereringsmekanismen. Återsådd från snabbpoolen använder den aktuella nyckeln och hashen för alla ingångar till snabbpoolen sedan start för att generera en ny nyckel; återseedning från den långsamma poolen beter sig på liknande sätt, förutom att den också använder hashen för alla ingångar till den långsamma poolen för att generera en ny nyckel. Båda återseedningarna nollställer entropiuppskattningen för den snabba poolen, men den sista ställer också in uppskattningen av den långsamma poolen till noll. Mekanismen för återseedning uppdaterar nyckeln konstant, så att även om nyckeln med poolinformation är känd för angriparen före reseed, kommer de att vara okända för angriparen efter reseed.
Reseed-kontrollkomponenten utnyttjar mellan frekvent omseedning, vilket är önskvärt men kan tillåta iterativa gissningsattacker , och sällsynt reseedning, vilket äventyrar mer information för en angripare som har nyckeln. Yarrow använder den snabba poolen för att återseed närhelst källan passerar några tröskelvärden, och använder den långsamma poolen för att återseed när minst två av dess källor passerar något annat tröskelvärde. De specifika tröskelvärdena nämns i Yarrow-160 -sektionen.
Designfilosofi
Yarrow antar att tillräckligt med entropi kan ackumuleras för att säkerställa att PRNG är i ett oförutsägbart tillstånd. Designerna ackumulerar entropi i syfte att behålla förmågan att återställa PRNG även när nyckeln äventyras. Liknande designfilosofi tas av RSAREF, DSA och ANSI X9.17 PRNGs.
Yarrow-160
Yarrow använder två viktiga algoritmer: en enkelriktad hashfunktion och ett blockchiffer . Den specifika beskrivningen och egenskaperna anges i tabellen nedan.
| Algoritmer | Egenskaper | Vad Yarrow-160 använder |
|---|---|---|
| Hashfunktion h(x) |
Givet M ingångsvärden är |M| val av utgångsvärden är likformigt fördelade över m -bitvärden. |
SHA-1 hashfunktion |
| Blockchiffer E() |
Hög statistisk prestanda för utgångar när de ges mycket mönstrade ingångar. |
Tre-nyckel Triple DES |
Generation
Yarrow-160 använder tre-nyckel Triple DES i räknarläge för att generera utgångar. C är ett n -bitars räknarvärde; K är nyckeln. För att generera nästa utgångsblock följer Yarrow funktionerna som visas här.
Yarrow håller räkningen av utgångsblocket, för när nyckeln har äventyrats kan läckan av den gamla utgången före den komprometterade stoppas omedelbart. När väl någon systemsäkerhetsparameter Pg . har nåtts kommer algoritmen att generera k bitar av PRNG-utdata och använda dem som den nya nyckeln I Yarrow-160 är systemsäkerhetsparametern satt till 10 , vilket betyder P g = 10 . Parametern är avsiktligt inställd på låg för att minimera antalet utgångar som kan spåras tillbaka.
Återsådd
Reseed-mekanismen i Yarrow-160 använder SHA-1 och Triple DES som hashfunktion och blockchiffer. Detaljerade steg finns i originalpapperet.
Implementering av Yarrow-160
Yarrow-160 har implementerats i Java och för FreeBSD . Exemplen finns i "An implementation of the Yarrow PRNG for FreeBSD" av Mark RV Murray.
För- och nackdelar med Yarrow
Fördelar
- Yarrow återanvänder befintliga byggstenar.
- Jämfört med tidigare PRNG:er är Yarrow någorlunda effektiv.
- Yarrow kan användas av programmerare utan kryptografisk bakgrund på ett någorlunda säkert sätt. Yarrow är portabel och exakt definierad. Gränssnittet är enkelt och tydligt. Dessa funktioner minskar risken för implementeringsfel något.
- Yarrow skapades med en attackorienterad designprocess.
- Entropiuppskattningen av Yarrow är mycket konservativ, vilket förhindrar uttömmande sökattacker . Det är mycket vanligt att PRNG:er misslyckas i verkliga applikationer på grund av entropiöverskattning och gissbara utgångspunkter.
- Återsåddsprocessen för Yarrow är relativt beräkningsmässigt dyr, så kostnaden för att försöka gissa PRNG:s nyckel är högre.
- Yarrow använder funktioner för att förenkla hanteringen av fröfiler, så filerna uppdateras ständigt.
- För att hantera kryptoanalytiska attacker är Yarrow designad att baseras på ett blockchiffer som är säkrat. Säkerhetsnivån för genereringsmekanismen beror på blockchifferet .
- Yarrow försöker undvika databeroende körningsvägar. Detta görs för att förhindra sidokanalattacker som timingattacker och effektanalys . Detta är en förbättring jämfört med tidigare PRNG:er, till exempel RSAREF 2.0 PRNG, som helt kommer att falla isär när ytterligare information om den interna verksamheten inte längre är säkerställd.
- Yarrow använder kryptografiska hash-funktioner för att bearbeta indataprover och använder sedan en säker uppdateringsfunktion för att kombinera proverna med den befintliga nyckeln. Detta säkerställer att angriparen inte enkelt kan manipulera inmatningsproverna. PRNGs som RSAREF 2.0 PRNG har inte förmågan att motstå den här typen av attacker med vald ingång.
- Till skillnad från ANSI X9.17 PRNG har Yarrow förmågan att återhämta sig från en nyckelkompromiss. Detta innebär att även när nyckeln äventyras, kommer angriparen inte att kunna förutsäga framtida utdata för alltid. Detta beror på återsåddsmekanismen hos Yarrow.
- Yarrow har entropisampelpoolen separerad från nyckeln och återställer endast nyckeln när entropipoolens innehåll är helt oförutsägbart. Denna design förhindrar iterativa gissningsattacker, där en angripare med nyckeln gissar nästa prov och kontrollerar resultatet genom att observera nästa utdata.
Nackdelar
- Yarrow är beroende av SHA-1, en hash som har gått sönder sedan Yarrows publicering och som inte längre är säker.
- Eftersom utdata från Yarrow är kryptografiskt härledda, kan systemen som använder dessa utdata bara vara lika säkra som själva genereringsmekanismen. Det betyder att angriparen som kan bryta genereringsmekanismen lätt kommer att bryta ett system som beror på Yarrows utdata. Detta problem kan inte lösas genom att öka entropiackumuleringen.
- Yarrow kräver entropiuppskattning, vilket är en mycket stor utmaning för implementeringar. Det är svårt att vara säker på hur mycket entropi som ska samlas in innan du använder den för att återinsätta PRNG. Detta problem löses av Fortuna (PRNG) , en förbättring av Yarrow. Fortuna har 32 pooler för att samla in entropi och tog bort entropiuppskattaren helt.
- Yarrows styrka begränsas av nyckelns storlek. Till exempel har Yarrow-160 en effektiv nyckelstorlek på 160 bitar. Om säkerheten kräver 256 bitar är Yarrow-160 inte kapabel att göra jobbet.