Kryptoblog

På EE Times dök det upp en artikel om en ny algoritm som kan mycket snabbt kan hitta symmetrier. Algoritmen i fråga heter Saucy och artikeln beskriver Saucy:

Combinatorial problems are one of the toughest nuts to crack in design automation and other applications that sift data. For instance, the number of Internet router path combinations for sending a message around the world is enormous. The shortest path is seldom chosen because there is no way to find the optimal distance among so many possibilities.

Now, the developers of an algorithm called “Saucy” claim it can solve such problems quickly by finding symmetries among large swaths of possibilities. In the global Internet routing problem, Saucy found so many symmetries–10 with 83,687 zeros–that it could sort through and an find an optimum path in under a second. Saucy was described this week at the Design Automation Conference.

Att artikeln presenterades på DAC-konferensen är inte så konstigt. Symmetriproblem finns det en stor mängd av inom EDA-området. Formell verifiering genom ekvivalenscheck är ett exempel där grafisomorfism används för att jämföra två konstruktioner.

Ett exempel - följande två grafer är isomorfa:

Andra EDA-områden där det finns symmetriproblem är syntes (BDD-träd), routing och layout. Eftersom Moores lag stampar vidare med fortsatt snabbt växande konstruktioner behöver verktygen bli allt snabbare för att inte utvecklingstiden skall skena iväg.

Saucy är utvecklad op University of Michigan och Berkeley. På sidan för Saucy-projektet finns mer information, bland annat ett par artiklar och en relativt ny presentation. På sidan sammanfattas Saucy med:

Many computational tools have recently begun to benefit from the use of the symmetry inherent in the tasks they solve, and use general-purpose graph symmetry tools to uncover this symmetry. However, existing tools suffer quadratic runtime in the number of symmetries explicitly returned and are of limited use on very large, sparse, symmetric graphs.

This paper introduces a new symmetry-discovery algorithm which exploits the sparsity present not only in the input but also the output, i.e., the symmetries themselves. By avoiding quadratic runtime on large graphs, it improves state-of-the-art runtimes from several days to less than a second.

Detta låter kanonbra, och är man som jag intresserad av EDA-verktyg och elektronikdesign är detta mycket spännande. Men varför ta upp detta på Kryptoblog?

Jo på grund av symmetriproblem och snabba lösningar av SAT-problem, vilket är samma slags problem som BDD-träd och isomorfism, går att använda för kryptanalys.

Några exempel på detta hittar vi i artiklarna Applications of SAT Solvers to Cryptanalysis of Hash Functions (pdf) och Logical Cryptanalysis as a SAT Problem: the Encoding of the Data Encryption Standard.

Den första artikeln (av Ilya Mironov och Lintao Zhang från Microsoft) är relativt ny och sammanfattningen av artikeln beskriver användningen av algoritmer för SAT-problem:

Several standard cryptographic hash functions were broken in 2005. Some essential building blocks of these attacks lend themselves well to automation by encoding them as CNF formulas, which are within reach of modern SAT solvers.

In this paper we demonstrate effectiveness of this approach. In particular, we are able to generate full collisions for MD4 and MD5 given only the differential path and applying a (minimally modified) off-the-shelf SAT solver.

To the best of our knowledge, this is the first example of a SAT-solver-aided cryptanalysis of a non-trivial cryptographic primitive. We expect SAT solvers to find new applications as a validation and testing tool of practicing cryptanalysts.

Det skulle vara otroligt intressant att se om det går att applicera Saucy på den attack mot hashfunktioner som Ilya Mironov och Lintao Zhang beskriver. Någon som är intresserad av att sponsra ett forskningsprojekt?

På USENIX-konferensen Large-Scale Exploits and Emergent Threats 08 (LEET08!) presenterade Samuel T. King, Joseph Tucek, Anthony Cozzie, Chris Grier, Weihang Jiang och Yuanyuan Zhou en mycket intressant artikel om hårdvarubaserade trojaner.

Artikeln Designing and Implementing Malicious Hardware, som utsågs till konferensen bästa artikel, är något av det mest intressanta och skrämmande jag läst på länge. Artikelns sammanfattning beskriver väl vad den handlar om:

Hidden malicious circuits provide an attacker with a stealthy attack vector. As they occupy a layer below the entire software stack, malicious circuits can bypass traditional defensive techniques. Yet current work on trojan circuits considers only simple attacks against the hardware itself, and straightforward defenses. More complex designs that attack the software are unexplored, as are the countermeasures an attacker may take to bypass proposed defenses.

We present the design and implementation of Illinois Malicious Processors (IMPs). There is a substantial design space in malicious circuitry; we show that an attacker, rather than designing one specific attack, can instead design hardware to support attacks. Such flexible hardware allows powerful, general purpose attacks, while remaining surprisingly low in the amount of additional hardware.

We show two such hardware designs, and implement them in a real system. Further, we show three powerful attacks using this hardware, including a login backdoor that gives an attacker complete and highlevel access to the machine. This login attack requires only 1341 additional gates: gates that can be used for other attacks as well.

Malicious processors are more practical, more flexible, and harder to detect than an initial analysis would suggest.

Författarna börjar med att beskriva hur olika attacker rört sig nedåt från applikation och OS till firmware och till virtualiseringssystem. Men, frågar sig författarna, hur svårt är det att modifiera en hårdvarukonstruktion, en processor, så att den dels gör systemet som kör på hårdvaran osäkert, och om det går att göra så att systemet inte märker av modifieringen.

Författarna har valt att modifiera open-source-processorn LEON3 från Göteborgsbaserade Gaisler Research.

LEON3-processorn är placerad i ett högst ordinärt och typiskt HW-system med USB-kontroller, VGA-kontroller m.m. På LEON3-processorn kör man sedan ett normalr GNU/Linux-system. Hela klabbet har realiserats på en Xilinx-FPGA.

I LEON3 har man sedan implementerat olika attacker. Den första attacken är en modifiering till LEON3-processorns MMU som gör att en process som känner till modifieringen kan trigga procesorn att ignorera minnesskydd och låta processen ge sig själv rootaccess. Författarna förklarar:

Our memory access mechanism provides hardware support for unprivileged malicious software by allowing access to privileged memory regions. Malicious software triggers the attack by forcing a sequence of bytes on the data bus to enable the memory access circuits. This sequence can be arbitrarily long to avoid false positives, and the particular sequence must be agreed upon before deployment.

Once the sequence is observed, the MMU in the data cache ignores CPU privilege levels for memory accesses, thus granting unprivileged software access to all memory, including privileged memory regions like the operating system’s internal memory. In other words, loading a magic value on the data bus will disable protection checking.

We implement this technique by modifying the data cache of our processor to include a small state machine that looks for the spe-cial sequence of bytes, plus some additional logic in the MMU to ignore privilege levels when malicious software

Författarna beskriver även en shadow-mod som gör det möjligt att gömma trojan genom att skapa en extra processormod, och kod som körs i denna mod döljs från resten av systemet. Denna shadow-mod används sedan av författarna för att implementera en funktion som snor lösenord samt ett sätt att implementera en bakdörr rätt in i OS:et. Mycket imponerande, fräckt och skrämmande.

Det författarna visar är hur lite som krävs för att implementera den här typen av funktioner. Författarna lade till mindre än 200 rader kod till VHDL-koden LEON3 består av. Minnesmodifieringen krävde knappt 1000 gates och shadow-funktionen drygt 1300 gates. Närmast avrundningsfel i en modern HW-konstruktion.

Författarna avslutar sin artikel med en diksussion om hur man kan skydda sig mot den här typen av attacker. Bla om man kan använda sidoeffekter för att detektera om en krets utför operationer man inte tänkt. Författarna konstaterar att det i dag antagligen finns få/inga vettiga skyddmekanismer, vilket jag håller med om.

Frågan man bör ställa sig i det här läget är dock: Men hur stor är risken egentligen?

Som exempel på ett ökande risk för trojaner i hårdvarukonstruktioner citerar författarna en rapport från USAs Department of Defence Science Board som bland annat skriver att

First, it has become economically infeasible to procure high performance ICs other than through commercial suppliers. Second, these commercial suppliers are increasingly moving the design, manufacturing, and testing stages of IC production to a diverse set of countries, making securing the IC supply chain infeasible. Together, commercial-off-the-shelf (COTS) procurement and global production lead to an “enormous and increasing” opportunity for attack

Att det finns problem med äktheten hos kretsar visar om inte annat att det nu bildas organisationef för att försöka stävja den snabbt ökande förekomsten av piratkopierade kretsar.

Det är inte så svårt att tänka sig att dessa kretsar skulle kunna innehålla mer än den piratkopierade konstruktionen. Man får ett mervärde man kanske inte hade tänkt sig. (Tomas Gilså uppmärksammade detta i en artikel om risker med piratkopierade routrar och switchar - ja jag är citerad.

På Cryptography-listan kommenterade Karsten Nohl trenden mot snabbt ökande komplexitet på chipnivå och användningen av IP-cores med:

Hardware designs currently move away from what in software would be open source. Chip obfuscation meant to protect IP combined with the ever increasing size of chips makes it almost impossible to reverse-engineer an entire chip.

Helt sant. I dag bygger man chip med allt fler och allt större IP-cores. Men hur vet man att dom faktiskt bara gör det dom säger att dom gör. Att kontrollera att konstruktionen följer en spec är en sak, men att visa att den även kan göra något mer?

Så möjligheten att modifiera konstruktioner, och den vägen få in en elak HW-funktion finns, frågan är om det finns kompetens och motivation? Kompetens kan man tyvärr köpa, så frågan är om någon är intresserad. Skall man döma av den snabbt ökande ekonomiska IT-brottsligheten finns det en hel del som är beredda att jobba hårt och lägga mycket pengar på att vara elaka.

Den här artikeln har uppmärksammats en del på krypto- och säkerhetslistor. Även Matt Blaze har bloggat kloka tankar som är värda att läsa. I diskussionen på Cryptography påpekades det att mikrokoden i Intels och AMDs processorer går att uppdatera. Hur kontrolleras att den mikrokod som laddas ner är ok? Någon som vet?

Jag tycker att artikeln som presenterades på LEET08 är mycket, mycket intressant. Och jag hoppas att artikeln får uppföljning i form av metodik och verktyg för att inspektera HW-konstruktioner och chip. Jag tror att vi kommer att behöva återkomma till den här frågan.

Jag har tidigare skrivit om MiFare-systemet och dess uppenbarligen urusla säkerhet. Sedan dess har det kommit ytterligare en attack där forskare från Holland visade att de genom att samla in en mängd data och sedan bearbeta dessa offline kunde återvinna den 48-bit långa nyckeln i MiFare Classics krypto CRYPTO1. Men nu har det kommit ett resultat till.

I en artikel på IACR av Nicolas T. Courtois, Karsten Nohl och Sean O’Neil kallad Algebraic Attacks on the Crypto-1 Stream Cipher in MiFare Classic and Oyster Cards visar författarna att säkerheten i MiFare är riktigt, riktigt trasig. Författarna skriver:

MiFare Crypto 1 is a lightweight stream cipher used in London’s Oyster card, Netherland’s OV-Chipcard, US Boston’s CharlieCard, and in numerous wireless access control and ticketing systems worldwide. Recently, researchers have been able to recover this algorithm by reverse engineering [11, 13].

We have examined MiFare from the point of view of the so called algebraic attacks. We can recover the full 48-bit key of the MiFare algorithm in 200 seconds on a PC, given 1 known IV (from one single encryption).

The security of this cipher is therefore close to zero. This is particularly shocking, given the fact that, according to the Dutch press, 1 billion of MiFare Classic chips are used worldwide, including many government security systems.

Som en läsare på Kryptoblog tidigare påpekat används även MiFare Classic i GL:s nya kontaktlösa biljettsystem här i Göteborg.

Egenhackade krypton är ofta en riktig usel idé, Ett egenhackat krypto med 48-bit nyckel känns riktigt brunt. Men det här kanske leder till bättre kravställning vid upphandling av den här typen av system. Man kan väl hoppas i alla fall…

(Uppdaterad med lite egna åsikter om strömkryptons vara eller inte vara.)

Jag kom att det fanns ett par saker till från avslutningen av eSTREAM värda att nämna.

I slutrrapporten som presenterar eSTREAM-portföljen finns det även med resultatet från den omröstning som genomfördes på workshopen State of the Art Stream Ciphers - SASC 2008.

Deltagarna i workshopen ombads att dela ut poäng till de olika eSTREAM-kandidaterna. +5 för kandidater som ansågs vara very suitable och -5 för kandidater som ansågs vara not very suitable.

För kandidaterna i profil ett blev utfallet så här:

Rabbit 2.80
Salsa20 2.80
Sosemanuk 1.20
HC-128 0.60
NLS v2 -0.60
LEX v2 -1.20
CryptMT v3 -1.40
Dragon -1.60

För kandidaterna i profil två blev utfallet så här:

Trivium 4.35
Grain v1 3.50
F-FCSR-H v2 0.52
MICKEY v2 0.17
Decim v2 -1.38
Edon80 -1.72
Pomaranch v3 -2.24
Moustique -2.50

Som man kan se av detta var det de kandidater som totalt sett fick positiva omdömen som till slut kom med i eSTREAM-portföljen. I Profil ett var det ganska jämt, och inga kandidater som var mycket populärare än andra. I profil två sticker Trivium och Grain ut ordentligt som klart mer populära än de andra.

Slutrapporten avslutas med en diskussion och noteringar de som organiserat eSTREAM har gjort.

Flera av kandidaterna i eSTREAM hade stöd för autenticiering av datat, men ingen av de kandidater som kom med i eSTREAM-portföljen har denna egenskap. Det var bara ett fåtal av kandidaterna som var självsynkroniserande, och ingen av dessa tog sig igenom eSTREAM. Organisatörerna noterar även att den kryptanalys som utförts iaf bitvis har varit ad hoc, snarare än metodisk.

Organisatörerna påpekar även att strömkrypton som Snow 2.0, även om det inte var med i eSTREAM antagligen är ett krypto som borde kunnat vara med i portföljen. Vidare nämner man TPy och Phelix (två kandidater som åkte ut) som intressanta nog att fortsätta utveckla.

Rapporten avslutas med en fråga: Stream ciphers: dead or alive? Min personliga åsikt att från vare sig ett säkerhetsperspektiv eller ett systemperspektiv är det intressant om det symmetriska kryptot är ett strömkrypto eller ett blockkrypto. Det som är intressant är om kryptot är säkert, att det kan leverera den prestanda som krävs och att storleken på implementationen är så liten som möjligt och inte medför några sidoattacker.

Blockkryptot AES med lämplig kryptomod kan erbjuda samma metodmässiga beteende som ett strömkrypto. Men om ett strömkrypto kan ge bättre prestanda än AES är det intressant för applikationer med stora bandbreddskrav - och här har vi med eSTREAM fått HC, Rabbit och Salsa20. För inbyggda system med hårda kostnadskrav är AES en dyr lösning och då är eSTREAMs krypton Grain och Trivium bra tillskott till möjliga lösningar.

Slutligen är jag lite rädd för en på tok för stor homogenitet, mer specifikt att säkerheten beror av att en enskild komponent fortsatt är säker. Några av eSTREAM-kandidaterna lånade mer eller mindre mycket från AES. Vidare har det kommit flera förslag till hashfunktioner som bygger på koncept och komponenter från AES.

Skulle det dyka upp allvarliga problem med AES är det bra att det finns alternativ. Och därför tycker jag att eSTREAM som projekt, den portfölj av kryptot vi fått med eSTREAM samt fortsatt utveckling av strömkrypton (och andra krypton, hashfunktioner etc) är bra.

Vad är din uppfattning?

HC-128, Rabbit, Salsa20/12, SOSEMANUK, F-FCSR-H v2, Grain v1, Mickey v2 och Trivium!

För ett par dagar sedan skrev jag en bloggpostning om slutspurten i eSTREAM och avslutade med att nu är det bara att vänta och se vad de kloka kryptologerna kommer fram till. Det visade sig att väntan blev kort.

Samtidigt som jag skrev min postning blev eSTREAM klar och dagen samtidigt med att jag postade uppdaterades eSTREAM. Så kan det gå. Och tack till den läsare som påpekade att resultatet var klart - jag hängde inte alls med.

Nå, resultatet är klart och vad skall vi då säga om det? Massor!

En första spontan kommentar är att det är kul att det blev så många algoritmer som fick en plats i den slutgiltiga eSTREAM-portföljen. Det blev inte en algoritm i vardera profilen (profil ett - snabba SW-algoritmer och profil två - effektiva i HW och inbyggda system), nej vi fick fyra algoritmer i respektive profil!

Detta gör iofs att det inte blir en algoritm som alla kommer att använda (jämför med AES), men samtidigt öppnar det upp att kunna välja utifrån krav och preferenser. Om man exempelvis inte kan leva med att Rabbit bara får användas fritt i icke-kommersiella tillämpningar finns det tre andra algoritmer i profil ett.

De ansvariga, kloka kryptologer som organiserat eSTEAM har publicerat en rapport kallad The eSTREAM Portfolio som beskriver arbetet som utförts i eSTREAM, varför de algoritmer som inkluderats i portföljen har valts samt varför andra algoritmer inte valdes. Vad gäller eSTREAM som aktivitet skriver de att:

The goal of eSTREAM was to stimulate work in the area of stream ciphers. In this, undoubtedly, the project has been a success. While eSTREAM has much of the appearance of a competition such as that used to establish the AES (or the forthcoming SHA-3) this comparison should be resisted.

We prefer not to use the word “winners”, or to necessarily pick one (or even two) algorithms as the sole outcome of eSTREAM. Rather, we are conscious that most of the stream ciphers in the portfolio are very new and while we believe them to be promising—for a variety of reasons—we must leave it to others to decide when analysis is sufficiently mature for an algorithm to be considered in standards or used in a deployment.

Jag personligen vill ändå kalla algoritmerna som valdes in i portföljen som vinnare. De har genomgått ett ganska rejält stålbad och bland de 30+ kandidater blivit en av åtta som tog sig hela vägen fram. Vad gäller Profil ett-algoritmerna skriver eSTREAM-arrangörerna att:

The goal for ciphers submitted to Profile 1 was that they should be “good” in software. By this we meant that they should significantly outperform the AES when used in a suitable stream cipher mode and all the final phase ciphers in Profile 1 achieve this.

Our vision wasn’t necessarily of a stream cipher that had a good all-round profile; our focus was on raw encryption speed with a bias towards encrypting large amounts of data after a single initialisation. Our intended security level was set to 128 bits which we believe to be adequate for contemporary applications.

Det man lyckats med bland profil ett-algoritmerna är att få en bra spridning på typen av algoritm, dvs basen för hur kryptot fungerar. HC-128 är ett extremt snabbt krypto som arbetar med stora tabeller (som iofs tar lång tid att initiera) vilket gör den intressant för bulk-kryptering.

Rabbit är ett gammalt krypto (visades publikt på FSE 2003) och har klarat sig utan större problem sedan dess. Rabbit är även ett snabbt krypto, och utan omfattande initieringsfaser.

Salsa20/12 är ett snabbt och skalbart krypto, men bygger på delvis nya principer - även om det klarat sig bra genom eSTREAM. Sosemanuk å sin sida bygger på delar från gamla krypton.

Vad gäller Profil två-algoritmerna skriver eSTREAN-organisatörerna att:

The goal for ciphers submitted to Profile 2 was that they should be “good” in constrained hardware environments. By this we meant that ciphers should significantly out-perform the AES in a restricted environment in at least one significant regard. The final phase candidates in Profile 2 were chosen because we believed they had the potential to achieve this.

We were anticipating that ciphers in Profile 2 might be suitable for deployment on passive RFID tags or low-cost devices such as might be used in sensor networks. Such devices are exceptionally constrained in computing potential because of the number of logic gates available or the amount of power that might realistically be available.

Our intended security level for this profile was 80 bits which we believe to be adequate for the lower-security applications where such devices might be used.

Som jag skrivit tidigare tycker jag att det är bra att man hade en separat profil för inbyggda system och att HW-implementationer togs i beaktande. Men jag tycker att det var synd att man hade 80 bitar som säkerhetsnivå för denna profil, något som många andra uttryckt som ett problem under hela eSTEAM-arbetet.

Jag ser inte att inbyggda system klarar sig med sämre säkerhet. Snarare är det så att dessa system är i användning under längre tid och uppdateras mycket mer sällan än PC-system. Detta, anser jag talar snarare för att inbyggda system behöver högre säkerhet, inte minst för att många av dessa system används för att automatisera, dvs styra och reglera den infrastruktur vi alla är beroende av.

Slutligen, att 48 bitar dvs sex Bytes skulle kosta för mycket för ett inbyggt system köper jag inte. Det som är intressant är hur många bitar som interntillståndet i kryptot kräver - RC4 som exempel kräver 256 Bytes (plus minst 16 bitar till för pekare).

Av de algoritmer som till slut hamnade i portföljen är det dock bara Trivium som har en nyckellängd på 80 bitar, de andra (F-FCSR, Grain och Mickey) har alla 128 bitars nycklar. Bra.

Bland profil två-algoritmerna är spridningen av nytänkande och konservatism stor. F-FCSR-H bygger på principer som testats sedan 90-talet. Grain å sin sida är imponerande, både i sin grundläggande enkelhet och sin skalbarhet (något jag gillar skarpt). Mickey är väsentligen två (stora) skiftregister, men har stått upp bra mot alla attacker som kastats mot den. Trivium slutligen är ett experiment i enkelhet och nytänkande som visade sig hålla hela vägen. Kul!

Det jag kan tycka är lite synd är ingen av de kandidater som skickades in till båda profilerna fick vara kvar hela vägen. Salsa20 skickades in som kandidat till båda profilerna, men fick bara fortsätta som profil ett-algoritm, även om den går bra att implementera i HW. Grain å sin sida är mycket snabb även i SW, och Grain borde (anser jag) fått vara med som profil ett-krypto.

eSTREAM har lett till en stor hög med forskning, undersökningar och artiklar. Bara eSTREAMs egen artikelsida listar 205 olika artiklar, och till det skall läggas allt som publicerats på konferenser och andra ställen. På eSTREAMs diskussionsforum har det varit aktivitet under hela arbetet, ett forum där diskussionerna (speciellt när DJB varit inblandad) gått höga. Jag inbillar mig att detta varit bra för kryptoforskningen över huvud taget.

En sak jag noterar är att fyra av vinnar-algoritmerna är representerade bland de som organiserat eSTREAM. Steve Babbage (Mickey), Christophe De Canniére (Trivium), Anne Canteaut (SOSEMANUK), Henri Gilbert (SOSEMANUK), Thomas Johansson (Grain) och Bart Preneel (Trivium). Jag tror inte att det handlar om att eSTREAM letts av några av de bästa kryptologerna, vilka naturligvis har rätt att skicka in kandidater.

En annan sak jag noterar är att forskningsorganisationen COSIC är starkt representerad, både i organisationskommitén (med bland annat Vincent Rijmen och Bart Preneel) i de vinnande bidragen. Hongjun Wu (HC), Bart Preneel (Trivium), har alla COSIC som arbetsplats. COSIC är antagligen Europas, kanske världens just nu bästa institution för kryptoforskning.

Hur var det då med den internationella aspekten på eSTREAM? Rätt bra tycker jag att det ser ut som. De krypton som hamnade i portföljen kommer från Frankrike (SOSEMANUK, F-FCSR), Belgien (HC, Trivium), England (Mickey), Danmark (Rabbit), Sverige (Grain), Schweiz (Grain) och USA (Salsa20/12). Inga från Asien och få personer från USA.

Så, eSTREAM är över. Vad skall man göra nu? Jag tänker göra två saker: Bevaka NISTs AHS-tävling samt börja jobba med att göra bra HW-implementationer av eSTREAM-algoritmerna.

Jag har tidigare byggt testimplementationer av Salsa20, Grain, Mickey och Trivium och tycker att de är trevliga algoritmer. Jag skall försöka bygga implementationer av de andra algoritmerna i portföljen. Men Rabbit skuttar jag över - på grund av dess licens.

Vad jag har sett är Salsa20 är något problematisk vid routing (dra ledningar på chip). Min erfarenhet är även att Mickey är mycket lättare att skala än vad de flesta som beskrivit HW-implementationer för eSTEAM hävdar. Förhoppningsvis kan jag publicera lite siffror på implementationsresultat för eSTREAM-algoritmer senare under 2008.

Det var det hele. Tack eSTREAM för den tid som varit! Nu skall jag äta frukost.

(BTW: Nu är även Wikipedias sida om eSTREAM uppdaterad.)

Karl Jonsson har bloggat om att Kristoffer Schollin, doktorand vid Handelshögskolan i Göteborg skall presentera en avhandling om Digital Rights Management (DRM).

Webbplatsen för juridiska institutionen på Handels har mer information om disputationen:

Fredagen den 28 mars disputerar Kristoffer Schollin på sin avhandling Digital Rights Management – the New Copyright.

Disputationen äger rum i SKF-salen och börjar kl. 13:00. Avhandlingen är en kritisk analys av Digital Rights Management (DRM) som rättsligt fenomen i ett föränderligt område: ”DRM is examined from a range of perspectives as a tool of normative communication and regulation as well as ideological systematization of rights and positions of control”.

(Jag är tillbaka från några veckors semester där ingen IT-säkerhet fanns att fundera på. Räkna med bättre fart på Kryptoblog.)

Som en del av sin normala säkerhetskonferens anordnar USENIX en konferens kallad Workshop on Offensive Technologies. Syftet med WOOT08 är att diskutera frånstötande koncept och tekniker inom IT-säkerhet. Vad som avses är:

Submissions should reflect the state of the art in offensive computer security technology—either surveying previously poorly known areas or presenting entirely new attacks.

We are interested in work that could be presented at more traditional, academic security forums, as well as more applied work that informs the field about the state of security practice in offensive techniques.

A significant goal is producing published artifacts that will inform future work in the field. Submissions will be peer-reviewed and shepherded as appropriate.

Submission topics include:

* Vulnerability research (software auditing, reverse engineering)
* Penetration testing
* Exploit techniques and automation
* Network-based attacks (routing, DNS, IDS/IPS/firewall evasion)
* Reconnaissance (scanning, software, and hardware fingerprinting)
* Malware design and implementation (rootkits, viruses, bots, worms)
* Denial-of-service attacks
* Web and database security
* Weaknesses in deployed systems (VoIP, telephony, wireless, games)
* Practical cryptanalysis (hardware, DRM, etc.)

Är du intresserad av att presentera något är det dags att skicka in en anmälan.

Det har dykt upp en artikel på IACR om attacker på Feistelbaserade blockkrypton. Generic Attacks on Feistel Schemes av Jacques Patarin skriver i sammanfattningen:

Let A be a Feistel scheme with 5 rounds from 2n bits to 2n bits. In the present paper we show that for most such schemes A:
1. It is possible to distinguish A from a random permutation from 2n bits to 2n bits after doing at most O(2n) computations with O(2n) non-adaptive chosen plaintexts.

2. It is possible to distinguish A from a random permutation from 2n bits to 2n bits after doing at most O(3n/2) computations with
O(3n/2) random plaintext/ciphertext pairs.

Since the complexities are smaller than the number 22n of possible inputs, they show that some generic attacks always exist on Feistel schemes with 5 rounds. Therefore we recommend in Cryptography to use Feistel schemes with at least 6 rounds in the design of pseudo-random permutations.

We will also show in this paper that it is possible to distinguish most of 6 round Feistel permutations generator from a truly random permutation generator by using a few (i.e. O(1)) permutations of the generator and by using a total number of O(2**2n) queries and a total of O(2**2n) computations.

This result is not really useful to attack a single 6 round Feistel permutation, but it shows that when we have to generate several pseudo-random permutations on a small number of bits we recommend to use more than 6 rounds. We also show that it is also possible to extend these results to any number of rounds, however with an even larger complexity.

Först skall jag nog säga att artiklar som publiceras på IACR inte självklart har granskats och därmed är det svårt att bedöma om det som presenterats stämmer eller ej.

Vad det handlar om är alltså skiffer uppbyggda enligt den struktur som Horst Feistel hittade på där blocket som bearbetas delas upp i två sidor (delar) och sidorna bearbetas var för sig. Mellan varje varv byter sidorna plats:

Det artikeln visar (så vitt jag fattar) är att oavsett nyckel och väsentligen oavsett vilka operationer som utförs på de olika sidorna i ett varv går det att identifiera utdata från kryptot i jämförelse med en en ren slumpmässig mängd data.

Rent praktiskt innebär inte detta att ett stort antal krypton plötsligt blivit osäkra (ens om resultaten i artikeln stämmer). De flesta Feistel-krypton, ex 3DES har ett stort antal varv och som författaren till artikeln skriver:

it is possible to distinguish most generators of 6 round Feistel permutations from truly random permutations on 32 bits, within approximately 2**32 computations and 2**32 chosen plaintexts (and this whatever the length of the secret key may be)

Det är alltså för ett krypto med ett block på 32 bit och sex varv. För ex 3DES med 64 bit block och 48 varv är det fortfarande praktiskt omöjligt. Men ett krypto där säkerhetsmarginalen i och med artikelns resultat kanske börjar bli liten kan vara KASUMI, kryptot i 3G.

Eller tänker jag snett?

Jag sitter och söndagsfunderar på vilka eSTREAM-kandidater i fas tre som till slut blir rekommenderade strömkrypton.

Det vi borde kunna göra är att titta på de utvärderingar som gjorts så här långt. Vi behöver titta både på prestanda och komplexitet samt hur man vid avslut av fas två röstat - vilka kandidater som tidigare varit mest populära. Här är en sammanställning av fas tre-kandidaterna och det viktade röstresultatet:

SW-profil
Salsa20 1.80
SOSEMANUK 1.03
HC 128/256 1.08
LEX 0.90
Rabbit 0.88
Dragon 0.47
CryptMT 0.29
NLS -0.60

HW-profil
Grain 1.63
Trivium 1.54
Mickey128 0.66
F-FCSR 0.29
LEX 0.21
Mickey 0.11
Edon80 0.00
Pomaranch −0.38
DECIM −0.39
Moustique −0.65

För de kandidater som förekommer flera gånger (ex Salsa20) har jag valt att ta det värde som är högst. Här ser vi att Salsa20 ligger i topp för SW-profilen följd av SOSEMANUK och HC. CryptMT och NLS är de minst populära SW-kandidaterna.

I HW-profilen ligger Grain i topp, tätt följd av Trivium och MICKEY. I botten ligger DECIM och Moustique.

Ett annat sätt att mäta skulle kunna vara att titta på antalet artiklar med resultat från någon form av kryptanalys samt antalet uppdateringar som har kommit till specifikationen för kandidaten.

Visst, eftersom artiklarna innehåller så otroligt skilda resultat blir det att jämföra apelsiner med lime och chili (eller nåt). Men jag tycker ändå att detta bör vara relevant. Har det uppdagats många svagheter och modifieringar till specifikationen tror jag att den kandidaten är mindre intressant än en som visat sig vara stabil.

Jag gjorde en snabb sammanställning baserad på vad som publicerats hos eSTREAM för respektive kandidat vad gäller kryptanalys och uppdatering av specifikationerna och fick följande:

CryptMT: 2
Dragon: 3
HC: 0
LEX: 3
NLS: 3
Rabbit: 2
Salsa20: 5
SOSEMANUK: 2
DECIM: 2
Edon80: 6
F-FCSR: 3
Grain: 3
MICKEY: 2
Moustique: 2
Pomaranch: 9
Trivium: 5

Här sticker HC ut genom att det inte kommit en enda artikel med kryptanalys som visar på någon svaghet. Pomaranch och Edon80 å andra sidan är de kandidater med flest publicerade resultat från kryptanalys samt uppdateringar till specifikationen. Dock kommer det på FSE 2008 att publiceras två artiklar med analysresultat för Salsa20 samt en för Trivium, vilket gör att dessa seglar upp i statistiken.

Skall man utifrån dessa två datamängder försöka sig på en gissning skulle jag tro att HC kommer att vara en av de krypton från SW-profilen eSTREAM kommer att rekommendera. För HW-profilen skulle jag satsa mina slantar på minst en av Grain, Trivium eller MICKEY.

Vad tror du?

Det börjar bli dags för årets upplaga av konferensen Fast Software Encryption (FSE) - mer exakt 10-13 februari i Lausanne, Schweiz. På konferensens webbplats finns nu ett preliminärt program och en lista med godkända artiklar. Tittar man på dessa sidor ser det ut att presenteras en hel del intressanta saker.

En första observation är att trenden sedan ett par år tillbaka med analyser/attacker mot olika hashfunktioner fortsatt håller i sig. Bland artiklarna finns bland annat de här:

MD4 is Not One-Way
Collisions on SHA-0 in one hour
Improved indifferentiability security analysis of chopMD Hash Function
Collisions for step-reduced SHA-256
New Techniques for Cryptanalysis of Hash Functions and Improved Attacks on Snefru
A (Second) Preimage Attack on the GOST Hash Function
Second Preimage Attack on 3-Pass HAVAL and Partial Key-Recovery Attacks on NMAC/HMAC-3-Pass HAVAL
Cryptanalysis of LASH

Av dessa är väl kollisioner mot SHA-256 det mest intressanta resultatet.

FSE 2008 är även en av de sista stora konferenserna innan eSTREAM-projektet skall avslutas. Därför är det extra intressant att se att det dyker upp resultat mot några av eSTREAM-finalisterna:

New Features of Latin Dances: Analysis of Salsa, ChaCha, and Rumba
Pen-and-Paper Collisions for the Full Salsa20 Hash Function

Differential Fault Analysis of Trivium

Här är det alltså frågan om två separata grupper som hittat problem med Salsa20 och dess släktingar ChaCha och Rumba. Dessa resultat är mycket intressanta av flera skäl. Salsa20 är nämligen inte bara en finalist i eSTREAM, utan dess släktingar ChaCha och Rumba är kompressions- och hashfunktioner skapade av Daniel J Bernstein.

Dessa funktioner är försök till avsteg från Merkele-Damgård-strukturen och finns även i andra, relativt nya strömkrypton och hashfunktioner, ex Schneiers Helix/Phelix. Om det visar sig att denna struktur har grundläggande fel finns det flera algoritmer som kan sitta pyrt till.

Att döma av hur Daniel J Bernstein brukar reagera gissar jag att om han är på FSE 2008 inte kommer att låta de här artiklarna stå obesvarade.

Vad gäller Trivium, har bloggen Cryptanalysis tidigare publicerat delar av det resultat som antagligen kommer att presenteras på konferensen. Resultaten är baserade på en förenklad variant av Trivium, men är ändå mycket intressanta.

Ett skäl till detta är att Trivium, precis som Salsa20 är ett försök att hitta en ny struktur. Som artikeln som specar Trivium beskriver det: Trivium is a hardware oriented synchronous stream cipher. It was designed as an exercise in exploring how far a stream cipher can be simplified without sacrificing its security, speed or flexibility.

Ok, det var eSTREAM-finalisterna. Konferensen inkluderar även en del resultat vad gäller blockkrypton:

Experiments on the Multiple Linear Cryptanalysis of Reduced Round Serpent
A Meet-in-the-Middle Attack on 8-Round AES
Impossible Differential Cryptanalysis of CLEFIA

Här är det väl ganska uppenbart att attacken mot en reducerad version av AES är det mest intresssanta.

CLEFIA är ett blockkrypto som Sony utvecklat för att skydda digitala media (Digital Rights Management - DRM). CLEFIA presenterades på FSE 2007, dvs förra året. Och nu kommer det alltså en kryptanalys.

Ett annat område med ett par intressanta artiklar är slumptalsgeneratorer.

Post-processing functions for a biased physical random number generator
How to Encrypt with a Malicious Random Number Generator

Den i mitt tycke mest intressanta artikeln här är den andra. Skälet till detta är att för inte så länge sedan presenterade Bruce Ferguson och en kollega resultat som pekade på att en av de NIST-specificerade slumptalsgeneratorerna (PRNG) innehåller en bakdörr. Den här artikeln verkar visa på att man med rätt metod kan lita på sina kryptonycklar även om man inte litar på slumptalsgeneratorn.

Den sista kategorin artiklar handlar om det gamla sorgebarnet RC4:

New Form of Permutation Bias and Secret Key Leakage in Keystream Bytes of RC4
Efficient Reconstruction of RC4 Keys from Internal States

Det verkar som om detta stackars strömkrypto inte får vila i frid, utan att folk är framme och sparkar på liket… Å andra sidan är RC4 ett krypto som används väldigt mycket så liket lever antagligen tyvärr på tok för mycket.

Som sagt, det ser ut att bli en mycket spännande konferens - även om det kanske inte är lika spännande som det här:

Som Månster uttryckte det: Vardagsedge!.