Warning: Missing argument 2 for wpdb::prepare(), called in /home/stromber/public_html/kryptoblog/wp-content/plugins/wp-super-edit/wp-super-edit.core.class.php on line 109 and defined in /home/stromber/public_html/kryptoblog/wp-includes/wp-db.php on line 1222
Forskning » Kryptoblog

Archive for the ‘Forskning’ category

Första SHA-3-konferensen genomförd

February 28th, 2009

I dag är sista dagen på SHA-3-konferensen som NIST anordnar. Än så länge har det inte dykt upp några fantastiska nyheter, och NIST har inte trots att det tidigare utlovats lagt upp sina presentationer. Dock finns ett stort antal presentationer på konferensen sida om de olika kandidaterna.

Förväntningarna från konferensen är att det skall trilla ut 10 till 15-16 kandidater (Ron Rivest har föreslagit 16 kandidater där två tas ut genom ett wildcard-system) utifrån det 50-tal kandidater som NIST fick in och accepterade vid tävlingens start. Förhoppningsvis kommer information om vilka kandidater som gått vidare inom några få dagar.

Ny version av Keccak

January 26th, 2009

Det finns nu en ny version av SHA-3-kandidaten Keccak.

Version 1.1 inkluderar ny användningsmoder och ny, mer optimerad SW-implementation. Efter att jag släppte min artikel om implementation av Keccak i FPGA har jag haft en del kontakter med skaparna av Keccak och den nya versionen av Keccak inkluderar även HW-implementation som fungerar mycket bättre.

Bra presentation om säkerheten i GSM och UMTS

January 19th, 2009

Sprang på en några år gammal men bra presentation om säkerheten i 2G- och 3G-mobilsystem.

Presentationen Design and Analysis of Cryptographic Algorithms for Mobile Communication Systems av Henri Gilbert från Orange Labs tar bland annat upp säkerheten på systemnivå såväl som algoritmer som används. Presentationen ger även en kort intro till Security Algorithms Group of Experts (SAGE), gruppen inom ETSI som arbetar med att specificera de algoritmer som används.

Om du är nyfiken på säkerheten i mobilsystem kan den här presentationen vara värd att bläddra igenom.

Återanvändning av AES för SHA-3

January 6th, 2009

Jag har ägnat nåra timmar åt att gå igenom alla specifikationer för de olika SHA-3-kandidaterna. En sak som blev ganska uppenbar är vilken framgång och vilket inflytande AES som krypto och designstrategin i den bakomliggande algoritmen Rijndael har fått.

Av de 55 kandidater som finns listade på ECRYPTs SHA-3-Zoo återanvänder inte mindre än 21 kandidater koncept, komponenter eller tom hela roundfunktionen från AES och Rijndael. Den lista jag slängt ihop ser ut som följer (det blir engelska nu då jag även klippt citat:

  • Abacus: MDS from AES.

  • Arirang: S-box from AES. MDS from AES for some versions of the hash.

  • Aurora: ShiftRows from AES.

  • Cheeta: “Inspired by AES

  • Echo: Stated goal to reuse as much of AES as possible (hence the
    name). Complete AES round reused.

  • Ecoh: AES “key wrap” reused.

  • Gr0stl. S-box and diffusion directly from AES.

  • JH: Differential propagation methodology from AES.

  • LANE: SubBytes, ShiftRows and MixColumns reused from AES.

  • Lesamnta: Reuse of the AES round as function F.

  • Luffa: “Based on Rijndael-like transform”

  • NaSHA: “Improved AES S-box.”

  • SANDstorm: AES S-box,

  • Sarmal: “An AES (or Whirlpool)-like nonlinear subround function g is used.”

  • SHAMATA: “uses one of the AES primitive functions MixColumns to incorporate the message into the internal state and a modified version of the AES round function to mix the internal state.”

  • SHAvite-3: “Iterates a round function based on the AES round.”

  • StreamHash: S-box based on AES S-box.

  • Tangle: Reuse of AES S-box.

  • Twister: MDS concept from Rijndael and S-box from AES. ShiftRows from AES.

  • Vortex: Based on Rijndael rounds.

  • Waterfall: Rijndael S-box.

Jag är inte helt säker på om detta är bra eller inte.

Å ena sidan är AES och dess ingående komponenter några av de mest välanalyserade som går att uppbringa. Detta faktum är något flera av kandidaternas skapare tar upp i sin motivering av sin kandidaters säkerhet. Implementationsmässigt är det dessutom bättre om samma programkod (funktioner) går att använda till flera saker. Speciellt för inbyggda system med hårda krav på liten kodstorlek är detta naturligtvis eftersträvansvärt.

Samtidigt kan jag inte släppa känslan av att vi riskerar att hamna i en monokultur – att säkerheten i alla dess olika delar (konfidentialitet, autenticitet, integritet) bygger på en eller ett fåtal algoritmer eller komponenter. Vad händer om S-boxen i AES faktiskt visar sig väldigt svag?

Vidare var den uttalande tanken från NIST att SHA-3-tävlingen skulle stimulera till nytänkande och uppmuntra till att hitta nya koncept för att bygga hashfunktioner. Att det sker ett rejält brott mot Merkle-Damgård är uppenbart, men nu är det istället AES och Rijndael. Är det bra eller dåligt?

Det verkar dock som de flesta verkligen försökt att tänka i nya banor. I min snabbläsning hittade jag för övrigt att tre kandidater (Abacus, Keccak och Luffa) bygger på de nya (relativt färska 😉 svampfunktionerna. Dessutom såg jag bara tre kandidater (Chi, DynamicSHA, DynamicSHA2) är direkta utökningar av SHA-1 och SHA-2.

Lite SHA-3-status

December 31st, 2008

Aktiviteterna med SHA-3 rullar på även under jul och nyår.

Randall Farmer har publicerat en ny version av Skein som använder SSE2-instruktioner i 32-bitmod för att accelerera algoritmen. Den nya koden når 23 cykler/byte. Jag testade lite snabbt att kompilera och köra koden på min Macbook.

Koden kompilerade utan några som helst problem och med O3optimering fick jag följande timingresultat (2 GHz Intel Core 2 Duo med 4 MByte cache och 2 GByte RAM kompilerad med i686-apple-darwin9-gcc-4.0.1 (GCC) 4.0.1 (Apple Inc. build 5488)):

#/usr/bin/time ./skein
75.32 real 74.89 user 0.17 sys

Jean-Philippe Aumasson har publicerat en ny, hårdbantad version av BLAKE-32. Den nya koden är på ca 200 rader, ca 6 kByte källkod inkl kommentarer. Denna kod är dock ej avsedd för att nå hög prestanda.

Vad gäller analysstatus har följade kandidater så här långt fallit:


Boole
DCH
EnRUPT
HASH 2X
MCSSHA-3
NKS2D
Ponic
Sgàil
Spectral Hash
Vortex
WaMM
Waterfall

Notera att NIST än så länge inte eliminerat dessa från kandidatlistan, utan det är på maillistan sha-forum och webbsidor som Skeins Engineering Comparison och ECRYPTs SHA-3 Zoo denna information kommer ifrån.

I vissa fall har skaparen av hashfunktionen (Waterfall och WaMM) officiellt dragit tillbaka sin kandidat, men i andra fall (EnRUPT) pågår diskussioner om att försöka hitta modifieringar för att reparera kandidaterna mot upptäckta problem.

Implementation av Keccak i FPGA-teknologi

December 17th, 2008

Jag har precis lagt upp en artikel kallad Implementation of the Keccak Hash Function in FPGA Devicessidan med artiklar och dokument.

Artikeln beskriver en del försök jag gjort med att implementera en av SHA-3-kandidaterna, Keccak i olika FPGA-kretsar. Som utgångspunkt har jag använt de referensimplementationer i VHDL som skaparna av Keccak har tagit fram.

Att döma av resultatet verkar Keccak vara en hashfunktion som lämpar sig väl att implementera i FPGA:er. Jag gillar att den går att skala så mycket som den gör. Den minimala low_area_copro-implementationen är verkligen mycket liten ocg ger trots det bra prestanda.

Jag hade dock en del strul med referensimplementationerna vilket till största delen beror på hur VHDL-koden är skriven. Om Keccak skulle bli vald till SHA-3 kommer det att behövas en hel del uppstädning för att få koden till att bli en riktigt bra referensimplementation.

Notera att jag inte i det här läget tar ställning till säkerheten hos Keccak, utan detta är enbart ett försök att utvärdera hur effektivt det går att implementera Keccak i FPGA:er.

Jag tar mycket gärna emot kommentarer och tips.

NIST publicerar lista på alla SHA-3-kandidater

December 10th, 2008

NIST postade för några minuter sedan till den maillista som finns för SHA-3-tävlingen att det nu finns en sida med alla kandidater man accepterat. NISTs Bill Burr skriver om kandidaterna:


NIST received 64 SHA-3 candidate hash function submissions. Overall, NIST is very pleased with the obvious high quality of many of the submissions, as well as the general range of designs. NIST has accepted 51 first round candidates as meeting our minimum acceptance criteria. They are now posted on the NIST website

Den publicerade listan med kandidater ser ut så här:


Abacus
ARIRANG
AURORA
BLAKE
Blender
Blue Midnight Wish
BOOLE
Cheetah
CHI
CRUNCH
CubeHash
DCH
Dynamic SHA
Dynamic SHA2
ECHO
ECOH
EDON-R
EnRUPT
ESSENCE
FSB
Fugue
Gröstl (New spelling: Grøstl)
Hamsi
JH
Keccak
Khichidi-1
LANE
Lesamnta
Luffa
LUX
MCSSHA-3
MD6
MeshHash
NaSHA
SANDstorm
Sarmal
Sgàil
Shabal
SHAMATA
SHAvite-3
SIMD
Skein
Spectral Hash
StreamHash
SWIFFTX
Tangle
TIB3
Twister
Vortex
WaMM
Waterfall

I listan som NIST publiceras visas bara namnet på en av skaparna av respektive kandidat, men att döma av den listan finns det inget svenskt bidrag. Jag skall gå igenom listan mer i detalj och återkommer.

NIST skriver i sin postning lite mer om planerna för tävlingen:


We will review these first round candidates at the first SHA-3 Candidate Conference on February 25-28, 2009 at Leuven. During the summer of 2009 we plan to select about 15 second round candidates for more focused review at the Second SHA-3 Candidate Conference, tentatively scheduled for August, 2010. Following that second conference we expect to select about 5 third round candidates (or “finalists”). At our third conference we will review the finalists and select a winner shortly thereafter. At each stage we will do our best to explain our choices.

The Federal Register announcement specified minimum acceptability requirements for “complete and proper submissions.” These requirements included provisions for reference and optimized C code implementations, known answer tests, a written specification and required intellectual property statements.

NIST har uppenbarligen haft en del bestyr med att få ordning på kandidaterna, och har en del kommentarer om kod, specifikationer etc. Problem på dessa punkter var anledningen till att en del kandidater ej kom med. NIST skriver:


We asked for reference code and optimized 32 and 64-bit code. Some submissions did not include optimized implementations, so we will use the performance results from the reference implementations in our future deliberations. Some submissions were rejected because C code was not provided. NIST specified a specific API for the C code, and a few submissions did not use that API: these submissions were also rejected. In some cases, we made a number of minor corrections to the submitted code (largely in the include statements) in order to allow it to compile and run, but made no major repairs.

NIST attempted to verify that the submitted C programs gave outputs that corresponded to the submitted known answer test results when compiled and run on our reference platform. In several cases there were discrepancies between the known answer test results NIST got on our reference platform, and the known answer test results provided by the submitters. NIST will notify those submitters, and these discrepancies must be resolved in a timely manner if the submission is to be eligible to become a second round candidate.

We also asked for documentation, including a complete specification of the algorithms, known answer test results, a performance analysis on different platforms and a security analysis. The quality of the submitted documentation varied greatly. For the security and performance analyses, we were very liberal in what we accepted. We had difficulty determining that the algorithm specifications were complete in some cases. In some of these cases necessary information, such as initial values or padding rules, were omitted from otherwise well-written specifications, but we were able to easily determine this information from the code; these specifications were considered acceptable, since independent implementers can find what they need and the specification can be easily fixed. Some written specifications were incomprehensible without a careful examination of the C code; the more extreme cases were rejected. Inevitably, there were cases between the two extremes. There were several submissions which we accepted that required us to rely more on the programming code for clear understanding than we liked.

We expect that the algorithms selected as the SHA-3 finalists will have specifications that will allow independent implementers to program or design hardware that will produce results that match those provided by the submitters for the known answer tests. In the AES competition, Brian Gladman and others provided independent implementations of all the finalists. Marginal, hard to follow specifications may affect whether a submission is selected for the second round.

We reviewed the intellectual property statements for all of the submissions. While there remain minor issues in some of the statements, we believe that all the accepted submissions include IP statements that allow us to continue the evaluation process for those submissions for now. However, any IP statement issues must be fully resolved before a candidate can progress to be a second round candidate.

Slutligen noterar NIST att det pågått och pågår en febril aktivitet med kandidaterna utanför NISTs kontroll och NIST kommenterar SHA-3-Zoo:


Many of the accepted submissions have been posted on the SHA-3 Zoo site for some time, and a number have been analyzed and are claimed to be “broken.” In some cases, the submitters have conceded the break. In other cases, the submitters concede the break, but claim that it can be fixed with trivial changes (e.g. by adding a few rounds). In still other cases, it appears that the breaks are fundamental and cannot be fixed without extensive modifications. NIST does not want to spend time in the upcoming SHA-3 conference on accepted, but broken algorithms, unless the break is disputed, or the fix is truly trivial. On the other hand, there has been considerable discussion about what is considered to be a break, and we expect to continue that discussion in Leuven. We also expect to discuss allowing submitters to use their “tunable parameter” to make changes to their algorithm before the second round candidates are chosen.
We will continue to consider submissions where there is a dispute about whether the submission is in fact broken until we can make a determination about the facts of the case.

Första SHA-3-konferensen utlyst

December 5th, 2008

NIST har meddelat att den första konferensen om SHA-3-kandidater kommer att arrangeras i anslutning till konferensen Fast Software Encryption (FSE) 2009. Konferensen hålls 22-25 februari i Leuven i Belgien.

Det börjar samtidigt bli allt mer uppenbart att NIST blivit något överväldigad av alla kandidater som dom fått in. Fortfarande har NIST inte ens presenterat en lista över mottagna kandidater och NIST skriver i utlysningen av konferensen att:


It appears that the number of accepted submissions will considerably exceed the number that NIST and the community can analyze thoroughly in a reasonable time period. NIST is considering ways to involve the cryptographic community in quickly reducing the number of submissions to a more manageable number. The process and criteria for this selection will be a major topic of this conference.

Även Bruce Schneier tar upp det stora antalet kandidater i ett inlägg på sin blogg som egentligen handlar om uppdateringar av sin kandidat Skein. I postningen pekar Schneier bland annat på en artikel om kandidaterna och personerna som skapat dessa, bland annat Peter Schmidt-Nielsen, en 15-årig hashfunktionsutvecklare. Peters kandidat Ponic har dock redan knäckts.

Över huvud taget pågår det en febril verksamhet för att knäcka de kandidater som är kända. På den maillista som finns kommer det dagligen flera postningar om attacker, analyser etc. Och återigen känns det inte som om NIST är med i matchen, utan att SHA-3-tävlingen har fått ett eget liv.

Av de nu 36 kända kandidater som finns på SHA-3 Zoo är nio kandidater knäckta och att det finns någon slags kryptanalys av ytterligare 12.

En ny implementation av J-PAKE

November 29th, 2008

I somras bloggade jag om en ny metod för lösenordsbaserat nyckelutbyte kallad J-PAKE. J-PAKE erbjuder flera ördelar jämfört med andra metoder. Dock har det fram till nu bara funnits en Java-implementation.

Googles kryptoninja och OpenSSL-utvecklaren Ben Laurie har implementerat nyckelutbytesalgoritmen J-PAKE i C som en en modul i OpenSSL. Detta gör att den som vill testa J-PAKE (givet att man har den nya modulen) nu kan använda J-PAKE direkt i OpenSSL. Ben skriver:


So, this weekend I implemented J-PAKE as a proper OpenSSL module. Plus support in s_server and s_client. You can test it like this:


openssl s_server -jpake secret
openssl s_client -jpake secret

If you want to use two different machines, as required by Mr. Churlish, then you’ll need to use the -connect option to s_client.

If you want to use it yourself, you can find example code in apps/apps.c. Look for the functions jpake_client_auth() and jpake_server_auth().

Ben Laurie har även en utmärkt blogg väl värd att läsa om man är intresserad av krypto och IT-säkerhet.

Ben Laurie
Ben Laurie från hans sida med publikationer på Google Research.

Lite SHA-3-nyheter

November 18th, 2008

NIST meddelade för några dagar sedan att de fått in 64 kandidater och att det kommer att dröja till i början av december innan NIST presenterar vilka kandidaterna är. Även om antalet kandidater är mindre än de minst 80 kandidater Bruce Schneier gissade på är det väldigt många.

Även om inte NIST publicerat listan med kandidater finns det en Wikisida kallad The SHA-3 Zoo som listar 28 stycken av kandidaterna inklusive länkar till artikel, webbplatser samt kandidaternas status vad gäller attacker. För attacker och kryptanalysresultat har redan börjat dyka upp.

På den maillista som NIST satt upp är det sedan en tid tillbaka en relativt hög aktivitet med postningar av resultat och diskussioner av hur dessa skall tolkas. Bland annat var några så ivriga att få in ett resultat att de publicerade en attack på kandidaten EnRUPT som är sämre än uttömande sökning. När de sedan fick kritik kom de med följande kommentar som låter väldigt mycket som First Post! på diverse forum:


We started working on the function yesterday. As soon as the paper was finished we sent a message.

Känns inte helt seriöst. Dock gav detta upphov till vad som skall klassificeras som en riktig attack – om attacker som tar längre tid eller kräver mer minne än atomer i hela universum skall anses som allvarliga attacker eller ej. Daniel J Bernstein kom för några dagar sedan med ett riktigt elegant debattinlägg:

2^185 preimage attack on MD6-256


After the recent flood of attacks on hash functions that I had never heard of before this month, I’m pleased to announce that I’ve found an attack on MD6-256 with time complexity just 2^185.

The attack is a “multiple-preimage attack” that simultaneously attacks 232 legitimate target signatures and successfully forges at least one signed message by finding a preimage of the underlying hash. Surely there will be more than 232 signatures generated using SHA-3, so this
is a realistic attack scenario if MD6 is being considered for SHA-3.

Recall from Rivest’s description of MD6 at Crypto that computing MD6 takes a fraction of a millisecond on a single CPU core. The total time for the attack is under 2^185 milliseconds—-I’m talking about actual wall-clock time, not some simplified model. The attack doesn’t fit on a single PC, but is easily implemented on a large cluster of a billion current Core 2 Quad PCs. Memory consumption per PC is negligible. Special-purpose hardware will be even less expensive.

The attack isn’t guaranteed to succeed; a detailed analysis shows that it has only about 1 chance in 100 of succeeding. However, repeating the attack will increase the success probability, and in any event I think we can agree that 1 chance in 100 is already an unacceptable threat for
SHA-3 users. Can we please kick MD6 out of the hash competition now?
—-D. J. Bernstein

Research Professor, Computer Science, University of Illinois at Chicago

P.S. Preliminary analysis suggests that, astonishingly, Skein and Keccak will both succumb to analogous attacks, and that the attack on Skein will be even faster than the attack on MD6. Who would have imagined that three hash-function designs with such different design principles would share a critical weakness?

Räknar man samman vad Bernsteins attack, som har motsvarande upplägg som några av de attacker som kommit på maillistan, ser ut att klara får man en attack på 2^256, dvs uttömande sökning (brute-force).

Det har kommit ett par ordentliga attacker. En av de första att falla var kandidaten NK2SD som är något så ovanligt som en hashfunktion baserad på en tvådimensionell cellautomat inspirerad av Stephen Wolframs A New Kind of Science:

Cellautomater
(Fina figurer från NK2SD-automater)

Just nu listar SHA-3 Zoo åtta stycken kandidater som i någon variant har attackerats. Dock verkar SHA-3 Zoo, NISTs egen maillista och andra aktiviteter leva ett eget liv utanför NISTs kontroll. NIST har gjort klart att inga kandidater i detta läget är borträknade. En sidoaktivitet som pågår är ECRYPTs eBASH där man kör och presenterar prestandatester av alla kandidater. Att döma av resultaten så här långt, med enbart ett fåtal kandidater är det ingen som framstår som snabbare än SHA-2. Ett problem med SHA-2, och tävlingen är tänkt att lösa är just att SHA-2-algoritmerna är så mycket långsammare än SHA-1.

En annan aktivitet är insamling av information om implementationer av kandidater i hårdvaraASIC eller FPGA. En av snabbaste ser ut att vara Keccak. Keccak har jag bloggat lite om tidigare och även om den svampfunktion som ligger till grund för funktionen. Kul att se att den verkar ge bra prestanda.

Jag har läst igenom de flesta artiklar som presenterar de (så här långt kända) kandidaterna. Att presentera resultat om hårdvaruimplementationer av sin kandidat verkar vara en trend bland kandidaterna. En annan trend jag tycker mig se är att beskriva skydd mot sidoattacker – återigen en implementationsaspekt. Både intressant och bra att se att de senaste årens sidoattacker börjar slå igenom och bli något som beaktas vid design av nya algoritmer.

Sättet som flera av kandidaterna hanterar problematiken med sidoattacker är att gå mot enkla grundunktioner – baserade på XOR, rotationer och bitskiftningar samt additioner. Desa grundfunktioner upprepas seda ett (mycket) stort antal gånger. Typiskt används inga S-box-liknande strukturer. Några exempel på detta är MD6, Skein (som bygger på Trieefish-kryptofunktionen) och Cubehash.

Påfallande många kandidater försöker även gå ifrån Merkle-Damgård-konstruktionen och mot helt nya principer för att bygga kompressorfunktioner och hashfunktioner. MD6, Keccak och NK2SD är exempel på detta.

Väsentligen alla kandidatbeskrivningar innehåller mer eller mindre ordentliga beskrivningar om kandidatens säkerhet och skydd mot olika attacker. Men flera av kandidaterna, bland annat MD6 och Skein innehåller bevis – alltså att algoritmen är bevisbart säker. Det skall bli intressant att se huruvida dessa bevis visar sig stämma, och om de antaganden och de villkor under vilka bevisen gäller håller.

Skaparna av kandidaten Skein, skapad av bland andra Bruce Schneier, Niels Ferguson, Stefan Lucks och Doug Whiting, sticker ut för att de har använt ett något annorlunda sätt att argumentera för sin algoritms säkerhet:


Skein was designed by a team of highly experienced cryptographic experts from academia and industry, with expertise in cryptography, security analysis, software, chip design, and implementation of real-world cryptographic systems. This breadth of knowledge allowed them to create a balanced design that works well in all environments.

Är Security by Authority en vettig term för den här typen av säkerhet tro?

Om någon undrar vad Skein betyder är det tydligen ett garnnystan, vilket är en bra liknelse för hur Treefish-funktionernas in- och utdata i Skein slingrar sig runt varandra.

Skein

Jag räknar med att återkomma med mer info om NISTs tävling när de presenterat samtliga 64 kandidater. Sedan lär det dröja några år innan jag får reda på om min gissning stämmer.