Jag sprang på en artikel av Eli Biham & Co som ger en bra beskrivning till de nya krypanalytiska metoder de bland annat använt för att attackera kryptot KASUMI i UMTS/3G. Vill du veta mer om Related-Key Boomerang- och Rectangle attacker är detta artikeln att läsa. Ett helgnöje kanske?
Den senaste tiden har det kommit flera artiklar som beskriver hårdvaruimplementationer av hashfunktioner som är kandidater till NISTs kommande SHA-3-standard. Några av dessa artiklar är Evaluation of Hardware Performance for the SHA-3 Candidates Using SASEBO-GII och An FPGA Technologies Area Examination of the SHA-3 Hash Candidate Implementations och Compact Hardware Implementations of the SHA-3 Candidates ARIRANG, BLAKE, Gr0stl, and Skein.
Det pågår även flera forskningsprojekt där man bygger upp ramverk för att på olika sätt jämföra implementationer (SW och HW) av olika kryptografiska funktioner – krypton, hashfunktioner etc. Ett sådan projekt är Athena-projektet som fokuserar på hårdvaruimplementationer. Ett annat projekt är ECRYPTs eBASH som mer tittar på SW-implementationer över ett stort antal processorarkitekturer.
Ett bekymmer med alla olika HW-implementationer är att det finns så många design- och teknologimässiga frihetsgrader. Är en given implementation optimerad för maximal prestanda eller minimal storlek? Är målteknologin en ASIC-process (och i så fall vilken processnod) eller en FPGA? Vilka teknologispecifika funktioner utntyttjas etc. Det är lätt att det blir en jämförelse mellan äpplen och päron, och kanske äpplen och köttfärslimpa.
I höstas kom artikeln Artikeln High-Speed Hardware Implementations of BLAKE, Blue Midnight Wish, CubeHash, ECHO, Fugue, Gr{o}stl, Hamsi, JH, Keccak, Luffa, Shabal, SHAvite-3, SIMD, and Skein där man försökt hantera detta. Genom att välja samma målteknologi, samma verktygsflöde, samma metodik och implementationstategi har man försökt skapa implementationer av kandidater som skall gå att jämföra med varandra.
Rapporten ger en bra översiktlig beskrivning av samtliga HW-implementationer som skapats. Målteknologi är en 180nm Standard Cell-process (ASIC) från Faraday och man har tagit design genom syntes ned till nätlista och där gjort prestandaskattningar.
Utifrån ren prestanda når Keccak 21 Gbit/s och vinner med bred marginal:
En mer intressant blir det om man tittar på prestanda kontra storlek på implementationen:
Det verkar som de flesta kandidater ligger inom 40-60 kGates och där återfinns de fem snabbaste kandidaterna. I diagrammet ser man även hur Keccak och Luffa sticker ut prestandamässigt. Vidare är det värt att notera hur mycket mer komplexa de största kandidaterna är, och att det iaf inte ger någon prestandafördel. Om man skulle gå på dessa siffror (och utgår ifrån att säkerheten är lika hög hos alla kandidater) borde Keccak och Luffa ligga bra till samt att BMW och SIMD samt Skein sitta sämre till.
Det jag saknar nu är en bra jämförelse med SW-implementationer, ex från eBASH samt vad andra får fram för resultat av HW-implementationer (ex Athena). Visserligen riskerar det att bli äpplen och köttfärslimpa, men jag tror att den samlade bilden är viktig.
Sprang precis på artikeln Fast Implementations of AES on Various Platforms (pdf) av Joppe W. Bos, Dag Arne Osvik och Deian Stefan som beskriver flera nya mycket snabba implementationer av blockkryptot AES-128. Artikelns sammanfattning säger det mesta:
This paper presents new software speed records for encryption and decryption using the block cipher AES-128 for different architectures. Target platforms are 8-bit AVR microcontrollers, NVIDIA graphics processing units (GPUs) and the Cell broadband engine.
The new AVR implementation requires 124.6 and 181.3 cycles per byte for encryption and decryption with a code size of less than two kilobyte. Compared to the previous AVR records for encryption our code is 38 percent smaller and 1.24 times faster.
The byte-sliced implementation for the synergistic processing elements of the Cell architecture achieves speed of 11.7 and 14.4 cycles per byte for encryption and decryption.
Similarly, our fastest GPU implementation, running on the GTX 295 and handling many input streams in parallel, delivers throughputs of 0.17 and 0.19 cycles per byte for encryption and decryption respectively. Furthermore, this is the first AES implementation for the GPU which implements both encryption and decryption.
Artikeln ger bra information om optimeringar som gjorts för de olika arkitekturerna samt jämför med andra implementationer. Jag gillar även det faktum att man faktiskt nådde 59 Gbit/s(!) på en NVIDIA GTX 295, 1.24GHz.
Teamet bakom SHA-3 kandidaten, hashfunktionen Keccak har utlyst en implementationstävling:
We are looking for implementations of Keccak on exotic platforms!
We offer a prize for the most interesting implementation of Keccak on: – Graphic cards/GPU
– Embedded processors, (e.g. ARM, Cell processor…)
– any other analog/digital computing device
The price consists in a Himitsu-Bako (secret box, http://en.wikipedia.org/wiki/Himitsu-Bako).
Who wins the prize will be decided by consensus in the Keccak team. We will internally use a system of points. Some hints: – Fast implementation get more points – Uncommon devices get more points
We give freedom in the way Keccak is used. It is allowed to implement, for instance, tree hashing or batch hashing (several messages hashed in parallel), instead of plain sequential hashing, to take advantage of parallel computing and get better performance.
The results and source code must be publicly available on an URL that is sent to |keccak| /-at-/ |noekeon| /-dot-/ |org| before June 30, 2010 at 12:00 GMT+2. No specific licensing condition is requested (pick up the one you like!) We reserve the right to extend this deadline in the absence of interesting results. Otherwise, the winner will be announced during the Rump session of the second SHA-3 candidate conference in Santa Barbara.
Priset de pratar om är en sådan här:
En implementation i Erlang kanske vore något (LinusN, Alu)?
Den nya attack på kryptot A5/3 i 3G jag tidigare bloggat om har nu publicerats på IACR. A Practical-Time Attack on the A5/3 Cryptosystem Used in Third Generation GSM Telephony (här är pdf-version av artikeln) av Orr Dunkelman, Nathan Keller och Adi Shamir är klart intressant läsning. Författarna skriver i sin sammanfattning att:
The privacy of most GSM phone conversations is currently protected by the 20+ years old A5/1 and A5/2 stream ciphers, which were repeatedly shown to be cryptographically weak. They will soon be replaced in third generation networks by a new A5/3 block cipher called KASUMI, which is a modified version of the MISTY cryptosystem.
In this paper we describe a new type of attack called a sandwich attack, and use it to construct a simple distinguisher for 7 of the 8 rounds of KASUMI with an amazingly high probability of $2**-14.
By using this distinguisher and analyzing the single remaining round, we can derive the complete 128 bit key of the full KASUMI by using only 4 related keys, 2**26 data, 2**30 bytes of memory, and 2**32 time.
These complexities are so small that we have actually simulated the attack in less than two hours on a single PC, and experimentally verified its correctness and complexity. Interestingly, neither our technique nor any other published attack can break MISTY in less than the 2^**128 complexity of exhaustive search, which indicates that the changes made by the GSM Association in moving from MISTY to KASUMI resulted in a much weaker cryptosystem.
Eller om man vill sammanfatta det ännu mer: AJ!.
Samtidigt skall man påpeka att attacken ändå kan vara praktiskt svår att genomföra. Som författarna skriver: However, the new attack uses both related keys and chosen messages, and thus it might not be applicable to the specific way in which KASUMI is used as the A5/3 encryption algorithm in third generation GSM telephony. Att säkerheten skulle hänga på att inte kunna tvinga fram fyra olika nycklar och meddelanden av en viss typ låter dock inte bra.
Det skall bli intressant att se hur ETSI SAGE och 3GPP reagerar på detta resultat. Det var ETSI SAGE som specificerade KASUMI baserat på Mitsubishis blockkrypto MISTY1. Enligt Wikipedia är de ändringar som gjordes för att underlätta effektiv implementation i hårdvara.
Det vore dessutom intressant att höra vad författarna till exempelvis den här artikeln eller den här artikeln anser. Speciellt den senare hävdar att KASUMI är en bra PRNG, vilket den nya attacken väldigt tydligt motsäger.
På Eurocrypt presenterades tydligen ett arbete av Alex Biryukov, Dmitry Khovratovich och Ivica Nikoli´c som visar på en ny attack mot AES-256. Deras presentation AES-256 Is Not Ideal ser ut att visa att med kopplade nycklar (related keys) går det att urskilja en sekvens genererad med AES från en slumpmässig sekvens.
Jag begriper för lite av den kortfattade presentationen för att avgöra hur mycket bättre deras resultat är en den bästa kända attacken med 26 related keys, 2**114 data och 2**173 time. Enligt en kommentar på Cryptography-listan hävdade författarna vid sin presentation att det nu finns praktisk möjlighet att bryta hashfunktioner byggda på round-funktionen i AES. Detta gör resultatet intressant för den pågående SHA-3-tävlingen då flera av kandidaterna lånar delar av eller hela round-funktionen.
Författarnas artikel om sin nya attack är tydligen godkänd för CRYPTO 2009, så om inte förr så vet vi mer i slutet av Augusti.
FredrikL tipsade om att det på förra veckans Eurocypt 2009s rump session presenterats vad som verkar vara en ny attack på hashfunktionen SHA-1.
Den nya attacken presenterad av Cameron McDonald, Philip Hawkes och Josef Pieprzyk har en komplexitet på 2**52 (operationer). Som forskarna påpekar är detta en stor förbättring gentemot tidigare bästa resultat, 2**63. Jämför man exempelvis med de DES-knäckare (ex COPACOBANA som byggts för att klara DES komplexitet på 2**56 är detta i samma härad och attacker är för den som har budget och tillräcklig vilja/behov möjliga att genomföra.
COPACOBANA-prototyp med FPGAer.
Det finns ännu ingen riktig artikel publicerad så det går inte att verifiera resultatet. Vidare finns det ingen egentlig skala, dvs 2**52 av vad behöver man genomföra för att knäcka SHA-1. Dock är forskarna bakom kända som seriösa forskare som tidigare publicerat ett antal artiklar och bidrag till fältet.
Om resultatet visar sig stämma är det ett signifikant resultat. För vissa typer av applikationer av SHA-1, exempelvis certifikat (beroende på hur de beräknas) skulle attacken göra det möjligt att generera falska certifikat. (Enl uppgift sätter Verisign serienumret helt slumpmässigt vilket gör det klart svårare att generera ett falskt certifikat.)
Om det inte sagts tidigare är det hög tid att (iaf för vissa användningar) migrera bort från SHA-1 och det presenterade resultatet understrycker även vikten av att NISTs SHA-3 tävling leder till minst en (den NIST antar) familj av nya hashfunktioner.
Professor Ed Felten och hans team av forskare har precis presenterat en metod att identifiera fysiska dokument. Tekniken de använder är att helt enkelt scanna dokumenten med en vanlig scanner och detektera papprets struktur. Forskarna skriver:
This paper presents a novel technique for authenticating physical documents based on random, naturally occurring imperfections in paper texture. We introduce a new method for measuring the three-dimensional surface of a page using only a commodity scanner and without modifying the document in any way. From this physical feature, we generate a concise fingerprint that uniquely identifies the document.Our technique is secure against counterfeiting and robust to harsh handling; it can be used even before any content is printed on a page. It has a wide range of applications, including detecting forged currency and tickets, authenticating passports, and halting counterfeit goods. Document identification could also be applied maliciously to de-anonymize printed surveys and to compromise the secrecy of paper ballots.
Ed Felten har lagt upp en bild på strukturen i ett papper sett i ett mikroskop:
Det är två saker som jag tycker är intressanta med detta. För det första att fysiska papper skiljer sig strukturmässigt så mycket från ark till ark. Det andra är att en vanlig scanner kan användas för att detektera denna struktur. Ed Felten visar hur scannern tolkar papprets struktur med följande bild:
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.
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.
© 2010 Kryptoblog · Proudly powered by WordPress & Green Park 2 by Cordobo.
Valid XHTML 1.0 Transitional | Valid CSS 3
