Posts Tagged ‘sha-3’

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.