Etikettarkiv: SHA-3

Nya kryptotävlingar

Knappt har röken från NISTs SHA-3-tävling lagt sig för det är dags igen.

CAESAR
Daniel J Bernstein har med ekonomiskt stöd från NIST i all korthet utlyst en ny tävling. Den nya tävlingen, CAESAR – Competition for Authenticated Encryption: Security, Applicability, and Robustness syftar till att få fram symmetriska kryptoalgoritmer som även ger autenticering av datat som bearbetas.

I dag är det väldigt tydligt att för den överväldigande mängden kommunikation är kryptering (som ger konfidentialitet) oftast mycket mindre viktigt än att veta att meddelanden kommer från rätt sändare och att det inte modifierats under överföring. Inte minst gäller detta industrisystem och inbyggda system där informationen sällan är känslig, men måste vara korrekt. Tyvärr är det få kryptoalgoritmer som ger både konfidentialitets- och autenticitetsskydd och det är vanligt att se system där bara konfidentialitet används.

Kryptot AES exempelvis kräver en kryptomod som GCM för att ge båda egenskaperna, en kryptomod som är relativt kostsam.

CAESAR avser att försöka standardisera en portfölj med bra ström- och blockkrypton samt kryptomoder som ger båda egenskaperna. Ett mycket bra initiativ.

Tidplanen för CAESAR är att kandidater ska vara inlämnade i början av 2014 och sedan sker utvärderingar under flera år för att slutligen 2017 förhoppningsvis leda till en portfölj med flera algoritmer.

Nya hashfunktioner
Det pågår även ett initiativ att starta en tävling motsvarande eSTREAM sponsrat av EU för att få fram nya hashfunktioner som är både kompakta och mycket snabbare än MD5, inte minst på enklare plattformar. Här finns det dock mindre konkreta planer än.

SHA-3 (Keccak) är en snabb algoritm på 64-bitars processorer. Men på 16- eller 32-bitars processorer samt i hårdvara har den visat sig vara svår att få riktigt snabb och samtidigt kompakt. SHA-2-algoritmerna har inte slagit, mycket på grund av att dom är så mycket långsammare än SHA-1 och MD5.

Många hoppades att SHA-3 skulle få fram radikalt snabbare algoritmer, men så blev det inte. Däremot har det efter SHA-3 dykt upp minst en intressant sådan algoritm. BLAKE2, en ny version av SHA-3-finalisten är mycket snabb och finns dessutom i ett par versioner för att möte krav från begränsade plattformar och för de med höga krav på säkerhet.

Presentationer från NISTS sista SHA-3-konferens

I slutet av mars anordnade NIST den sista SHA-3-konferensen. Målet med konferensen var att få in så mycket information som möjligt om finalisterna inför NISTs beslut om vilken algoritm som kommer att blir den nya hashfunktionen SHA-3. NIST har en sida för konferensen och där finns nu alla presentationer och artiklar som presenterades.

Det finns ett flertal intressanta presentationer om implementationer, både i hårdvara och i program. För högpresterande hårdvaruimplementationer i FPGA och ASIC ser finalisten Keccak ut att vara överlägsen, både i ren råprestanda och prestanda viktad mot kostnad. På senaste generationer av CPU:er ser dock BLAKE att vara överlägsen rent prestandamässigt.

För små, inbyggda system ser Gröstl och Blake att ge minimala implementationer med där Keccak återigen ger bäst prestanda viktad mot kostnad. Det finns även intressanta resultat vad gäller sidottacker på implementationer och säkerhetsanalyser av algoritmerna.

På konferensen ställde även NIST frågan till deltagarna om vilka kandidater de föredrar genom att humma. Skaparen av BLAKE, JP Aumasson rapporterde resultatet:

Top: Keccak, then BLAKE. Deafening silence: Skein. Ouch.

När skaparna av finalisterna fick frågan vilken algoritm förutom sin egen de föredrog blev resultatet:

  • Skein -> BLAKE
  • Groestl -> JH
  • JH -> Keccak
  • BLAKE -> Skein
  • Keccak -> Groestl

Om man jämför med humm-frågan ser det ut att vara rätt mycket taktik i de valen.

IETF 83 några dagar efter SHA-3-konferensen höll NIST en mycket intressant presentation om SHA-3 (länken pekar på PPT-fil). För att få en känsla av hur NIST resonerar är den här presentationen väl värd att bläddra igenom. I presentationen pekar man ut att SHA-3 inte kommer att ersätta SHA-2, inte minst då SHA-3 knappast kommer att ge mycket bättre prestanda. NIST ser att SHA-2 är effektiv, inte minst i inbyggda system. Däremot kommer SHA-3 att kunna ge mycket högre prestanda för hashbaserade meddelandekoder (MAC). NIST påpekar även i sin presentation att det analysarbete av kryptografiska hashfunktioner som bedrivits sedan 2005 gör att man i dag är mindre orolig för säkerheten hos SHA-256 och andra SHA-2-algoritmer. NIST ber i sin presentation IETF om synpunkter på hur hashfunktioner bör anpassas för olika protokoll och miljöer, detta för att ta med dessa synpunkter i sitt val av vinnande algoritm.

För den som vill bidra till SHA-3-processen vill NIST få in detta innan den första juni. Sedan är det dags för NIST-juryn att överlägga och berätta vem som är vinnare. (Inte säker på att SHA-3-överläggningen skulle göra sig lika bra i TV som Project Runway.). Enligt NIST kommer vinnaren att utses i slutet av året.

Har du information du anser att NIST bör ta med i sin bedömning är det dags att agera. Sedan blir det spännande att sätta tänderna i den nya, fräscha SHA-3. Nästan som en julklapp.

Bittester av kryptografiska hashfunktioner

Kryptografiska hashfunktioner (och krypton) har en egenskap kallas lavineffekten. Lavineffekten innebär att små förändringar av indata ger stora förändring på det genererade hashvärdet.

Hashvärden för SHA-256 när S ändras till T.
Hashvärden för SHA-256 när S ändras till T.

Men hur stor är lavineffekten, och finns det indata som ger olika stor lavineffekt? Jag bestämde mig för att testa på de hashfunktioner som finns i biblioteket OpenSSL (version 0.9.8r).

Jag har använt ordlistan från OpenWalls lösenordsknäckare John The Ripper och behandlat varje enskilt ord som ett sepatat meddelande. För varje meddelande har jag beräknat ett hashvärde. Sedan har jag inverterat den första biten i varje ord och genererat ett nytt hashvärde. Sedan räknar jag alla bitar som växlat mellan de två värdena. Sedan gör jag detta för varje hashfunktion och beräknar statistik. Men närmare 4 miljoner ord i listan blir det många hashfunktionsoperationer.

Så här ser resultatet från körningarna ut:

Statistics for md5
Digest size in bits: 128
Number of words tested: 3917116
Min number of bits changed: 36
Min percentage of digest changed: 28.1
Max number of bits changed: 93
Max percentage of digest changed: 72.7
Average number of bits changed 64.0

Statistics for sha1
Digest size in bits: 160
Number of words tested: 3917116
Min number of bits changed: 49
Min percentage of digest changed: 30.6
Max number of bits changed: 112
Max percentage of digest changed: 70.0
Average number of bits changed 80.0

Statistics for sha224
Digest size in bits: 224
Number of words tested: 3917116
Min number of bits changed: 72
Min percentage of digest changed: 32.1
Max number of bits changed: 150
Max percentage of digest changed: 67.0
Average number of bits changed 112.0
Expected average: 896.0

Statistics for sha256
Digest size in bits: 256
Number of words tested: 3917116
Min number of bits changed: 89
Min percentage of digest changed: 34.8
Max number of bits changed: 171
Max percentage of digest changed: 66.8
Average number of bits changed 128.0

Statistics for sha384
Digest size in bits: 384
Number of words tested: 3917116
Min number of bits changed: 144
Min percentage of digest changed: 37.5
Max number of bits changed: 243
Max percentage of digest changed: 63.3
Average number of bits changed 192.0

Statistics for sha512
Digest size in bits: 512
Number of words tested: 3917116
Min number of bits changed: 201
Min percentage of digest changed: 39.3
Max number of bits changed: 316
Max percentage of digest changed: 61.7
Average number of bits changed 256.0

För samtliga testade hashfunktioner växlar i medelfallet hälften av alla bitar. Däremot är variansen för de äldre funktionerna SHA-1 och speciellt MD5 större än för SHA-2-funktionerna. Den snävare variansen för SHA-2 gör att det blir svårare att genom exempelvis sidoattacker försöka säga något om vilka meddelanden hashfunktionen bearbetar. Ingen av funktionerna ger med något av testmeddelandena en förvånande liten eller stor bitväxlingar.

Nästa steg är att testa finalisterna i NISTS SHA-3-tävling samt även jämföra med hashfunktioner som inte kryptografiskt säkra. Då bör vi se större varians och kanske även lite krockar.

Prestandatester av hashfunktioner

Den senaste tiden har jag tittat en del på prestanda och beteende hos olika kryptografiska hashfunktioner. OpenSSL innehåller funktioner och kommandon (kommandot speed) för att utföra prestandatester på den plattform dom körs. Maskinen jag kör på är utrustad med en 2.7 GHz Intel Core i7 och kör ett 64-bitars operativsystem. Den testade versionen av OpenSSL är 0.9.8r. När jag testar på min huvudmaskin får jag följande resultat:

Resultat från prestandatest av OpenSSL
Resultat från prestandatest av OpenSSL

Som förväntat är MD5 snabbast, tätt följt av SHA-1. Men en sak värd att lägga märke till är prestandan för SHA-2-funktionerna SHA-256 och SHA-512. För alla andra testfall än 16 Bytes data är SHA-512 snabbare. Detta kan tyckas underligt, om man tänker sig att göra avvägning mellan prestanda och säkerhet – att SHA-512 ger högre säkerhet till priset av prestanda. SHA-512 utför även 80 iterationer för att bearbeta ett datablock, och SHA-256 bara 64 iterationer. Men SHA-512 använder 64-bitarsoperationer och arbetar på större block än SHA-256 – 128 Bytes kontra 64 Bytes. Detta gör att SHA-512 på en maskin som min blir effektivare.

NIST, organisationen som specificerat SHA-2 (och SHA-1 samt arbetar med att ta fram SHA-3) har insett detta och presenterade i början av 2011 en ny version av specifikationen FIPS 180. Detta dokument specificerar SHA-1 och SHA-2. I den nya versionen finns det två nya funktioner – SHA-512/224 och SHA-512/256. Precis som SHA-384 är dessa funktioner SHA-512, men där det genererade hashvärdet kapas av till den bitstorlek som önskas. Använder du SHA-256 och har prestandaproblem kan det därför vara värt att titta SHA-512/256 på dessa funktioner.

Notera att SHA-384, SHA-512/224 och SHA-512/256 inte är exakt samma funktion som SHA-512. Det som skiljer är initialvärdena i interntillståndet. Dvs att implementera SHA-512/256 kräver lite mer än att köra med SHA-512 och kasta bort den högra halvan av hashvärdet. Koden i implementationen måste ändras, om än i liten grad.

För den som vill titta närmare på prestandan hos många olika hashfunktioner inklusive finalisterna i SHA-3-tävlingen finns det massor med data hos EU-projektet eBASH.

sphlib 3.0

För ett tag sedan släpptes version tre av biblioteket sphlib. Sphlib implementerar samtliga finalister samt flera av de tidigare kandidaterna till hashfunktionstävlingen för att få fram hashfunktionen SHA-3. Om man vill börja underrsöka och testa SHA-3-algoritmer är sphlib trevlig att arbeta med.

Sphlib ger inte maximal prestanda och har därför fått kritik för att kanske inte ge en perfekt bild av vad de olika kandidaterna kan åstadkomma. För den som vill se den typen av resultat finns EBASH-projektet att titta på. Men för den som inte är ute efter prestanda, utan titta på funktion, struktur etc är sphlib bra.

Testchip för SHA-3-finalisterna

För några dagar sedan meddelade forskare vid Center for Embedded Systems for Critical Applications, en del av ECE-labbet på Virginia Tech, att dom färdigställt ett testchip som implementerar finalisterna i hashtävlingen SHA-3.

Kretsen NIST SHA-3 ASIC @VT är tillverkad i en 130nm-process från IBM med cellbibliotek från Artisan (numera en del av ARM). De algoritmer som implementeras är de fem SHA-3-finalisterna BLAKE-256, Grostl-256, JH-256, Keccak-256 och Skein512-256. Dessutom inkluderar kretsen en referensimplementation av SHA-256. Layouten på kretsen ger en bra bild av kostnaden i hårdvara mellan de olika kandidaterna:

Layout av SHA-3-chipet
Layout av SHA-3-chipet

Blake ser ut att vara den algoritm som är närmast SHA-256 i storlek och Gröstl sticker ut som klart mest kostsam. Nästa steg är att se vilken prestanda algoritmerna ger. Tidigare resultat har visat att speciellt Keccak varit riktigt effektiv i hårdvara. Det viktiga är att den blivande SHA-3-algoritmen helst skall ge minst samma prestanda som SHA-256 i hårdvara och dessutom kosta lika mycket eller mindre. Som det ser ut just nu är det ingen kandidat som är billigare i hårdvara.

För den som är nyfiken på testchipet finns det ett datablad att läsa. Det finns även komplett källkod och utvecklingsprojektfiler för att implementera samtliga kandidater i andra omgången (som ledde fram till NISTs uttagning av de fem finalisterna) i FPGA-teknologi.

NISTs motivering till SHA-3-finalisterna

För ett par veckor sedan publicerade NIST ett dokument som sammanfattar status för SHA-3 tävlingen, hur NIST utvärderat och bedömt alla kandidater samt ger NISTs motivering till de fem finalister man valt ut och de man inte valde ut. För de fem finalisterna skriver NIST följande:

BLAKE

BLAKE was selected as a finalist, due to its high security margin, good performance in software,
and its simple and clear design.

Grøstl

Grøstl was selected as a finalist because of its well-understood design and solid performance,
especially in hardware. While Grøstl’s security margin is not ideal, NIST views it in light of the extensive amount of cryptanalysis that has been published, both on Grøstl itself and the larger AES structure on which Grøstl is based. Due to the large amount of existing cryptanalysis, NIST feels that future results are less likely to dramatically narrow Grøstl’s security margin than that of the other candidates.

JH

JH was selected as a finalist because of its solid security margin, good all-around performance,
and innovative design.

Keccak

Keccak was selected as a finalist, mainly due to its high security margin, its high throughput and
throughput-to-area ratio and the simplicity of its design.

Skein

Skein was selected as a finalist, mainly due to its high security margin and speed in software.

Mer info om respektive kandidat, hur dom utvärderats och bedömts finns i dokumentet. Och förhoppningsvis blir det som NIST skriver i dokumentet – att vi får nya, riktigt bra hashfunktioner i 2012.