Yarrow algoritm

Yarrow - algoritmen är en kryptografiskt säker pseudoslumptalsgenerator . Yarrow valdes som namn , vars torkade stammar fungerar som en källa till entropi i spådomar [1] .

Algoritmen utvecklades i augusti 1999 av Bruce Schneier , John Kelsey och Nils Ferguson från Counterpane Internet Security.[2] . Algoritmen är inte patenterad och royaltyfrioch ingen licens krävs för att använda den. Yarrow ingår i februari2002 medFreeBSD , OpenBSD och Mac OS X som en implementering av enheten /dev/random [3] .

Yarrows vidareutveckling var skapandet av Fergus och Schneier av Fortuna-algoritmen , som beskrivs i deras bok "Praktisk kryptografi" [4] .

Behovet av en algoritm

De flesta moderna kryptografiska applikationer använder slumptal. De behövs för att generera nycklar , erhålla engångsslumptal , skapa ett salt etc. Om slumptal är osäkra innebär detta uppkomsten av sårbarheter i applikationer som inte kan stängas med olika algoritmer och protokoll [5] .

1998 genomförde skaparna av Yarrow forskning om andra PRNG:er och identifierade ett antal sårbarheter i dem. De slumptalssekvenser som de producerade var inte säkra för kryptografiska tillämpningar [5] .

För närvarande är Yarrow-algoritmen en mycket säker pseudo-slumptalsgenerator. Detta gör att du kan använda den för ett brett utbud av uppgifter: kryptering , elektronisk signatur , informationsintegritet , etc. [5] .

Designprinciper

Under utvecklingen av algoritmen fokuserade skaparna på följande aspekter [6] :

Hastighet och effektivitet . Ingen av utvecklarna kommer att använda en algoritm som avsevärt saktar ner applikationen.
Enkelhet . Alla programmerare utan mycket kunskap om kryptografi borde kunna använda det säkert.
Optimering . Om möjligt bör algoritmen använda redan existerande instruktionsblock.

Algoritmstruktur

Komponenter

Yarrow-algoritmen består av 4 oberoende delar [7] :

Entropiackumulator . Samlar in prover från entropikällor och placerar dem i två pooler.
komplikationsmekanism . Komplicerar periodvis generatornyckeln med hjälp av entropi från pooler.
genereringsmekanism . Genererar PRNG- utgångssignaler från dongeln.
Komplikationshanteringsmekanism . Anger körtiden för komplikationen.

Entropiackumulator

Entropiackumulering är en process där en PRNG får ett nytt obegripligt internt tillstånd [8] . I denna algoritm ackumuleras entropi i två pooler: snabb och långsam [9] . I detta sammanhang är en pool ett lager av initierade och färdiga att använda bitar. Snabb pool ger ofta viktiga komplikationer . Detta säkerställer att nyckelkompromiss har en kort varaktighet. Den långsamma poolen ger sällsynta men betydande nyckelkomplikationer. Detta är nödvändigt för att säkerställa att en säker komplikation erhålls även i fall där entropiuppskattningarna är kraftigt överskattade. Ingångssamplen skickas växelvis till de snabba och långsamma poolerna [10] .

Komplikationsmekanism

Komplikationsmekanismen förbinder entropilagringen med genereringsmekanismen. När komplexitetskontrollmekanismen bestämmer att komplexitet behövs, då använder komplexitetsmotorn information från en eller båda poolerna, uppdaterar nyckeln som används av genereringsmekanismen. Således, om angriparen inte känner till den aktuella nyckeln eller poolerna, kommer nyckeln att vara okänd för honom efter komplikation. Det är också möjligt att komplexiteten kommer att kräva en stor mängd resurser för att minimera framgången för en attack baserat på att gissa ingångsvärdena [11] .

För att generera en ny nyckel använder den snabba poolkomplexiteten den aktuella nyckeln och hasharna för alla snabba poolingångar sedan den senaste nyckelkomplexiteten. När detta är gjort, uppskattar entropinför den snabba poolen ställs in på noll [11] [12] .

Den långsamma poolkomplikationen använder den aktuella nyckeln och hasharna för de snabba och långsamma poolingångarna. Efter generering av en ny nyckel återställs entropiuppskattningarna för båda poolerna till noll [13] .

Genereringsmekanism

Genereringsmekanismen ger utsignalen en sekvens av pseudoslumptal. Den måste vara sådan att en angripare som inte känner till generatornyckeln inte kan skilja den från en slumpmässig bitsekvens .[14] .

Genereringsmekanismen bör ha följande egenskaper [15] :

motstånd mot kryptografiska attacker ;
produktivitet ( engelska Efficiency );
förmågan att generera en mycket lång sekvens av signaler utan komplikationer;
motstånd mot brute-force attacker med backtracking ( eng. Backtracking ) efter att nyckeln har äventyrats .

Komplikationshanteringsmekanism

För att välja sofistikeringstiden måste kontrollmekanismen ta hänsyn till olika faktorer. Om du till exempel ändrar nyckeln för ofta blir en iterativ gissatack mer sannolik [16] . För långsamt, tvärtom, ger mer information till angriparen som komprometterade nyckeln. Därför måste kontrollmekanismen kunna hitta en mellanväg mellan dessa två tillstånd [17] .

När prover anländer i varje poolentropiuppskattningarna för varje källa lagras. Så snart denna uppskattning för någon källa når gränsvärdet uppstår en komplikation från snabbpoolen. I de allra flesta system sker detta många gånger per timme. En komplikation från den långsamma poolen uppstår när poängen för någon av källorna i den långsamma poolen överstiger en tröskel [17] . $k$ $n$

I Yarrow-160 är denna gräns 100 bitar för den snabba poolen och 160 bitar för den långsamma. Som standard måste minst två olika källor i den långsamma poolen vara större än 160 bitar för att komplikationer ska uppstå från den långsamma poolen [18] .

Yarrow 160

En möjlig implementering av Yarrow-algoritmen är Yarrow-160. Huvudidén med denna algoritm är användningen av en enkelriktad hashfunktion och ett blockchiffer [19] . Om båda algoritmerna är säkra och PRNG får tillräckligt med initial entropi , då blir resultatet en stark sekvens av pseudoslumptal [20] . $h()$ $E_{K}()$

Hashfunktionen måste ha följande egenskaper [21] :

vara irreversibel, det vill säga motståndskraftig mot restaurering av prototypen ;
vara motståndskraftig mot kollisioner ;
ge output -biten. $m$

Yarrow-160 använder SHA-1-algoritmen som [19] . $h()$

Blockchifferet måste ha följande egenskaper [22] :

ha en nyckel med längden -bitar och ett datablock med längden -bitar; $k$ $n$
vara resistent mot klartext och valda textattacker ;
har goda statistiska egenskaper för utsignalerna, även med mycket mallade insignaler.

Yarrow-160 använder 3-KEY Triple DES-algoritmen som [19] . $E_{K}()$

Generation

Generatorn är baserad på användningen av ett blockchiffer i räknarläge (se fig. 2) [23] .

Det finns ett n-bitars räknarvärde . För att generera nästa -bitar av den pseudo-slumpmässiga sekvensen, inkrementeras räknaren med 1 och krypteras med ett blockchiffer med nyckeln [24] : $C$ $n$ $C$ $K$

C\leftarrow (C+1){\bmod {2}}^{n}

R\leftarrow E_{K}(C)

var är utdata från PRNG och är nyckelns aktuella värde . $R$ $K$

Om nyckeln vid någon tidpunkt äventyras är det nödvändigt att förhindra läckage av tidigare utdatavärden som en angripare kan få. Denna genereringsmekanism har inte skydd mot attacker av detta slag, så antalet PRNG-utgångsblock beräknas dessutom. Så snart en viss gräns har nåtts ( systemsäkerhetsinställningen ${\displaystyle P_{g))$ , ), då genereras en -bit PRNG-utgång, som sedan används som en ny nyckel [15] . ${\displaystyle 1\leq P_{g}\leq 2^{n/3))$ $k$

K\leftarrow {\text{nästa k PRNG-utgångsbitar))

I Yarrow-160 är den 10. Den här parametern är medvetet låg för att minimera antalet utgångar som kan läras in med en backtracking- attack [ 25 ] . ${\displaystyle P_{g))$

Komplikation

Exekveringstiden för komplikationsmekanismen beror på parametern . Denna parameter kan fixeras eller ändras dynamiskt [26] . $P_{t}\geq 0$

Denna mekanism består av följande steg [26] :

Entropiackumulatorn beräknar hashen för alla poster i snabbpoolen. Resultatet av denna beräkning betecknas med . ${\displaystyle v_{0))$
Låt . $v_{i}:=h(v_{i-1}|v_{0}|i)~{\text{ för }}~i=1,\ldots ,t$
$K\leftarrow h^{'}(h(v_{P_{t))|K),k)$ .
$C\leftarrow E_{K}(0)$ .
Återställ alla entropiräknare i pooler till 0.
Rensa minnet som lagrar mellanliggande värden.
Om seed-filen används , skriv sedan över innehållet i denna fil med nästa bitar av utdata från den pseudoslumpmässiga sekvensen . $2k$

En funktion definieras i termer av en funktion enligt följande [27] : $h^{'}$ $h$

s_{0}:=m

s_{i}:=h(s_{0}|\ldots |s_{i-1}),\ \ {\text{där))\ \ i=1,\ldots

h^{'}(m,k):={\text{först))\ \ k\ \ {\text{bitar))\;(s_{0}|s_{1}|\ldots )

I själva verket är det en storleksanpassningsfunktion, det vill säga den konverterar en indata av valfri längd till en utdata med en specificerad längd. Om ingången fick mer data än förväntat, tar funktionen de ledande bitarna. Om storleken på indata och utdata är desamma är funktionen en identitetsfunktion . Om storleken på indata är mindre än förväntat, genereras ytterligare bitar med denna hash-funktion . Detta är en ganska dyr PRNG-algoritm när det gäller beräkning, men för små storlekar kan den användas utan problem [28] .

Att sätta ett nytt värde på räknaren görs inte av säkerhetsskäl, utan för att ge större implementeringsflexibilitet och upprätthålla kompatibilitet mellan olika implementeringar [26] . $C$

Olösta problem och planer för framtiden

I dagens implementering av Yarrow-160-algoritmen, storleken på poolernaentropiackumulering är begränsad till 160 bitar. Attacker på 3-KEY Triple DES-algoritmen är kända för att vara effektivare än uttömmande sökningar . Men även för brute-force backtracking-attacker ändras nycklar ganska ofta, och 160 bitar är tillräckligt för att säkerställa säkerheten i praktiken [29] .

Ämnet för pågående forskning är förbättringen av entropiuppskattningsmekanismer. Enligt skaparna av Yarrow-160 kan algoritmen vara sårbar just på grund av dåliga entropiuppskattningar, och inte ur kryptoanalyssynpunkt [30] .

Skaparna har planer för framtiden att använda den nya AES-blockchifferstandarden . Det nya blockchifferet kan enkelt passa in i den grundläggande designen av Yarrow-algoritmen. Men som utvecklarna betonar kommer det att vara nödvändigt att antingen ändra komplexitetshashfunktionen eller komma med en ny hashfunktion för att säkerställa att entropipoolen är fylld med mer än 160 bitar. För AES med 128 bitar kommer detta inte att vara ett problem, men för AES med 192 eller 256 bitar måste detta problem lösas. Det bör noteras att den grundläggande strukturen för Yarrow-algoritmen är kombinationen av ett AES-blockchiffer och en 256-bitars hashfunktion [31] .

Uppsättningen av regler för mekanismen för komplikationshantering är fortfarande provisorisk, men ytterligare studier kan förbättra den. Av denna anledning är det föremål för pågående forskning [30] .

Anteckningar

↑ Kelsey, Schneier, Ferguson, 2000 , sid. 29.
↑ Kelsey, Schneier, Ferguson, 2000 , sid. 13.
↑ Murray, 2002 , sid. 47.
↑ Ferguson, Schneier, 2004 , sid. 183.
↑ 1 2 3 Schneier om säkerhet. Frågor & svar om Yarrow . Tillträdesdatum: 1 december 2016. Arkiverad från originalet 11 november 2016.
↑ Kelsey, Schneier, Ferguson, 2000 , sid. 15-16.
↑ Kelsey, Schneier, Ferguson, 2000 , sid. 18-21.
↑ Shcherbakov, Domashev, 2003 , sid. 232.
↑ Viega, 2003 , sid. 132.
↑ Ferguson, Schneier, 2004 , sid. 189-193.
↑ 1 2 Shcherbakov, Domashev, 2003 , sid. 234-235.
↑ Ferguson, Schneier, 2004 , sid. 234-235.
↑ Shcherbakov, Domashev, 2003 , sid. 191-193.
↑ Ferguson, Schneier, 2004 , sid. 183-184.
↑ 1 2 Ferguson, Schneier, 2004 , sid. 183-185.
↑ Kelsey, Schneier, Wagner et al., 1998 , sid. 172.
↑ 1 2 Kelsey, Schneier, Ferguson, 2000 , sid. 22.
↑ Kelsey, Schneier, Ferguson, 2000 , sid. 28.
↑ 1 2 3 Kelsey, Schneier, Ferguson, 2000 , sid. 23.
↑ Ferguson, Schneier, 2004 , sid. 202.
↑ Schneier, 1996 , sid. 55-57.
↑ Shcherbakov, Domashev, 2003 , sid. 236.
↑ Ferguson, Schneier, 2004 , sid. 95-96,183-186.
↑ Ferguson, Schneier, 2004 , sid. 95-96,183-188.
↑ Kelsey, Schneier, Ferguson, 2000 , sid. 25.
↑ 1 2 3 Kelsey, Schneier, Ferguson, 2000 , sid. 26-27.
↑ Kelsey, Schneier, Ferguson, 2000 , sid. 27.
↑ Ferguson, Schneier, 2004 , sid. 188-189.
↑ Kelsey, Schneier, Wagner et al., 1998 , sid. 176-177.
↑ 1 2 Kelsey, Schneier, Ferguson, 2000 , sid. 28-29.
↑ Ferguson, Schneier, 2004 , sid. 109-111.

Litteratur

på ryska

Shcherbakov, L. Yu. , Domashev, A. V. Tillämpad kryptografi. Användning och syntes av kryptografiska gränssnitt. - Ryska upplagan, 2003. - 416 sid. — ISBN 5-7502-0215-1 .
Ferguson, N. , Schneier, B. Praktisk kryptografi. - Williams Publishing House, 2004. - 432 sid. — ISBN 5-8459-0733-0.

på engelska

Schneier, B. Applied Cryptography. - John Wiley & Sons, 1996. - 784 sid. - ISBN 978-1-119-09672-6 .
Agnew G. Random Sources for Cryptographic Systems // Advances in Cryptology - EUROCRYPT '87 :Workshop om teorin och tillämpningen av kryptografiska tekniker Amsterdam, Nederländerna, 13–15 april 1987 Proceedings / D. Chaum , W. L. Price - Springer Science + Business Media , 1988. - S. 77-81. — 316 sid. — ISBN 978-3-540-19102-5 — doi:10.1007/3-540-39118-5_8
Kelsey J. , Schneier B. , Wagner D. A. , Hall C. Cryptanalytic Attacks on Pseudorandom Number Generators // Fast Software Encryption :, FSE' 98 Paris, Frankrike, 23–25 mars 1998 Proceedings / S Vaudenay - Berlin , Heidelberg , New York, NY , London [etc.] : Springer Berlin Heidelberg , 1998. - P. 168-188. - ( Lecture Notes in Computer Science ; Vol. 1372) - ISBN 978-3-540-64265-7 - ISSN 0302-9743 ; 1611-3349 - doi:10.1007/3-540-69710-1_12
Kelsey J. , Schneier B. , Ferguson N. Yarrow-160: Notes on the Design and Analysis of the Yarrow Cryptographic Pseudorandom Number Generator // Selected Areas in Cryptography :, SAC'99 Kingston, Ontario , Kanada, augusti 9-10, 1999 Proceedings / H. M. Heys , C. Adams - Berlin , Heidelberg , New York, NY , London [etc.] : Springer Berlin Heidelberg , 2000. - S. 13-33. - ( Lecture Notes in Computer Science ; Vol. 1758) - ISBN 978-3-540-67185-5 - ISSN 0302-9743 ; 1611-3349 - doi:10.1007/3-540-46513-8_2
Murray, Mark RV En implementering av Yarrow PRNG för FreeBSD // BSDC'02 Proceedings of the BSD Conference 2002 on BSD Conference. - USENIX, 2002. - S. 47-53 . - ISBN 1-880446-02-2 .
Viega J. Practical Random Number Generation in Software (engelska) // 19th Annual Computer Security Applications Conference (ACSAC) 2003, 8-12 december 2003, Las Vegas, NV, (USA) - IEEE Computer Society , 2003. - P. 129 -140. - ISBN 978-0-7695-2041-4 - doi:10.1109/CSAC.2003.1254318

Länkar

Yarrow - Algoritmsida på B. Schneiers hemsida (engelska)