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

Beskrivning av nya attackmetoder

February 12th, 2010

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?

Hårdvaruimplementationer av SHA-3-kandidater

February 12th, 2010

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:
Prestandatabell.

En mer intressant blir det om man tittar på prestanda kontra storlek på implementationen:
Prestanda vs area.

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.

Nya prestandarekord för AES

February 2nd, 2010

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.

A5/3-attacken publicerad

January 12th, 2010

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.

Mer om GSM-attacken

December 30th, 2009

Det verkar aldrig ta slut på uppmärksamheten kring Karsten Nohls attack på A5/1 (se tidigare bloggpostning ett och bloggpostning två). I dag har Sveriges Radio och Ekot plockat upp tråden och jösses vilket reportage det blev.

Ekots bild till artikeln.

Egentligen är Per Eurenius reportage (webbradio) från 26C3 i Berlin inte så illa, utan det är snarare påannonseringen och SRs nyhetstext som är tokfel:

Hemlig gsm-kod hackad av forskare

En tysk forskare har lyckats avslöja den kod som ska skydda mobiltrafiken i världens största telefonsystem, gsm.

Nej, SR, det är ingen kod som avslöjats, och det är inte hemligt.

Även Cryptome har uppdaterat sitt material In support of Karsten Nohl’s cracking of GSM A5 och den här sidan hos Cryptome är nog den mest kompletta samlingen av information om A5-krypton, säkerhet (eller avsaknad därav) i GSM, GPRS och UMTS.

För den som vill ha Karstens regnbågstabeller finns det nu torrentfiler.

SvD om attack på GSM-kryptot

December 29th, 2009

26:e(!) CCC-konferensen (26C3) pågår för fullt i Berlin med massor av högintressanta presentationer. Någon har uppenbarligen tipsat SvD (eller mer troligt är det denna NYT-artikel dom plockat, en artikel med något mer innehåll) att Karsten Nohl presenterat sin regnbågsattack på GSM-kryptot A5/1. (Att Karsten Nohl håller på med en regnbågsattack mot A5/1 har jag tidigare bloggat om här på Kryptoblog.)

SvDs artikel GSM-kod knäckt av tysk forskare innehåller inte mycket substans och missar att A5/1 varit knäckt sen lång tid tillbaka, och att Karsten försöker folk att inse detta. Vidare hänvisar man till GSM-organisationen med säte i London, vilket borde vara GSM Association (GSMA). En person där uttalar sig om att det Karsten presenterat är olagligt. (Tyvärr kan det vara sant – iaf kan Karstens regnbågstabeller vara olagliga i Tyskland där lagen §202c gör säkerhetsverktyg olagliga.)

Tittar man på A5/1-projektets Trac-sida finns presentationsbilderna från 2gC3 och projektnyheter. Bland annat berättade man att:

* The community has computed a large number of rainbow tables (Thank you!)

* We found new sources of known plaintext which allows decryption with a smaller subset of the codebook than previously thought

* A full GSM interceptor to collect GSM data could hypothetically be built from open source components, which we have not doing so may be illegal in some countries

JanJ tipsade om att Cryptome har en sida med länkar och info från gamla attacker på GSM-krypton.

Slutligen kan det vara värt att nämna att det verkar som att KASUMI – blockkryptot som används i UMTS och kallas A5/3 kan vara fetknäckt. På en rump session vid Asiacrypt 2009 presenterade Adi Shamir, Orr Dunkelman och Nathan Keller ett pågående arbete kallat A Practical-Time Attack on the Encryption Algorithm Used in Third Generation Telephony.

Ännu finns ingen artikel publicerad (vad jag kan hitta, ex på IACR), men räkna med att jag återkommer så fort jag hittat och läst den. Det ironiska är att det Karsten Nohl säger sig villa åstadkomma med sin A5/1-attack är att få till ett byte från A5/1 till A5/3, men om den algoritmen också är knäckt står vi alla med byxorna nere.

Så vitt jag vet är kryptofunktioner som A5/1 och A5/3 implementerade som HW-funktioner i terminaler. Vidare finns det ingen förhandlingsmekanism i GSM och UMTS motsvarande ex TLS som gör det enkelt att spärra bort och lägga till nya algoritmer. Tillsammans gör detta att det nog kommer att dröja innan det finns ett bra skydd för radiolänken i GSM och UMTS (om Adi & co:s attack stämmer – och eftersom det är dom stämmer det antagligen.)

NISTs statusrapport för SHA-3

October 4th, 2009

NIST arrangerar en tävling för att få fram en ny hashfunktion avsedd att komplettera SHA-2, en hashfunktion som kommer att kallas SHA-3. Tävlingen har pågått sedan hösten 2007 och i slutet av juli 2009 avslutades den första omgången av tävlingen och den andra omgången startade. För ett par veckor sedan publicerade NIST en statusrapport med lägesbeskrivning för tävlingen efter första omgången..

När tävlingen startade begärde NIST in kandidater och fick totalt in 64 stycken kandidater. Av dessa kandidater ansåg NIST att 51 uppfyllde minimikraven och accepterades som kandidater i slutet av oktober 2008. Det senaste året har dessa kandidater undersökts och attackerats av såväl NIST som kryptosamfundet i stort. För den som är intresserad listar SHA-3 Zoo status för alla kandidater vad gäller attacker.

En av de saker rapporten beskriver är vilka kriterier NIST har satt upp för att bedöma de olika kandidaterna. Dessa är uppdelade i tre kategorier:

  1. Säkerhet. Den nya hashfunktionen måste vara minst lika säker som SHA-2-funktionerna.
  2. Prestanda och kostnad. Ett problem med SHA-2 är att dessa funktioner är väldigt mycket långsammare än SHA-1 och den nya funktionen måste därför vara snabbare än SHA-2. Prestandan mäts både på referensplattformen Intel Core 2 Duo i 32- och 64-bitarsmod, men man tittar även på 8-bitplattformar och HW-implementationer. Kostnaden handlar om mängd program- och dataminne samt storlek vid HW-implementationer.
  3. Algoritm och implementation. Detta kriterie handlar mer om ifall algoritmen är mer eller mindre flexibel, kan utnyttja nya arkitekturer som SIMD-instruktioner eller AES-instruktioner, går att parallellisera samt om algoritmen är enkel eller invecklad.

Utifrån sina egna bedömningar och andras analyser vad gäller säkerhet och prestanda (exemeplvis eBASH-projektets prestandamätningar) har NIST valt ut 14 algoritmer som går vidare till andra omgången. Dessa är:


BLAKE, BLUE MIDNIGHT WISH (BMW), CubeHash, ECHO, Fugue, Grøstl, Hamsi, JH, Keccak, Luffa, Shabal, SHAvite-3, SIMD, Skein

Rapporten innehåller en kortfattad beskrivning av varje kandidatalgoritm där NIST beskriver grundläggande idé och struktur, hur olinjäritet skapas i algoritmen, vad NIST ser som det unika med algoritmen, prestanda samt säkerhetsläget. Utifrån dessa beskrivningar kan man göra några enklare observationer:

  • Tre grundläggande idéer/strukturer återkommer hela tiden. Tre är baseade på HAIFA, sex är olika varianter och utökningar av Merkele-Damgård (MD) och övriga fem är baserade på de relativt nya svampfunktionerna (Sponge functions). Det är skönt att se att det inte bara är MD-baserade kandidater kvar, utan att det finns kandidater med rejält olika utgångspunkt kvar i tävlingen.
  • Fyra av kandidaterna använder på något sätt AES som en del av sin funktionalitet. Vissa återanvänder S-boxen, andra återanvänder delar eller hela round-funktionen från AES.
  • Flera av kandidaterna behöver väsentligen implementeras med SIMD- eller AES-specialiserade instruktioner för att ge riktigt bra prestanda.
  • Antalet kandidater med substitutionstabeller är ganska få, och dessa är förhållandevis små. Detta kan antagligen ses som ett resultat av de senaste årens uppmärksammade problem med att göra implementationer utan sidoeffekter av algoritmer med S-boxar.
  • Förhållandevis många kandidater bygger på att använda enkla funktioner (XOR, modulär addition, skiftoperationer) som upprepas ett stort antal gånger, gärna med möjlighet till parallellism. Ingen verkar använda multiplikationer eller andra typer av mer avancerade transformer, ex FFT som en av de andra kandidaterna använde.

NISTs förhoppning är att det begränsade antalet kandidater i andra omgången skall göra att samtliga kandidater blir rejält genomlysta. NIST noterar i sin beskrivning av kandidaterna att det skiljer ganska väsentligt i hur mycket analys som skett av de olika kandidaterna så här långt.

Den andra omgången är planerad att pågå i ett år och hösten 2010 avser NIST att välja ut fyra-fem stycken av de 14 kandidaterna som finalistkandidater. Detta innebär att tävlingen pågått i två år och kommer att hålla på i ett, troligen två år till. Det tar tid att skaka fram en hashfunktion.

Ny attack på AES

May 24th, 2009

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.

Trolig attack på SHA-1

May 3rd, 2009

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.
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.

Identifiering av dokument genom att scanning

March 13th, 2009

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:

Papprets struktur.

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:

Struktur sedd med scanner.