Kryptoblog

(Fixat trasig länk - tack JörgenL.)

På Light Blue Touchpaper, bloggen från säkerhetsguppen vid Cambridge Computer Laboratory har det dykt upp en intressant postning om ett nytt sätt att utföra lösenordsbaserad nyckelutbyte.

Lösenordsbaserad nyckelutbyte (Password Authenticated Key Exchange - PAKE) är en metod för att utbyta sessionsnycklar för säker kommunikation mellan parter baserad på lösenord (delad hemlighet). De två mest kända versionerna av PAKE är Encrypted Key Exchange - EKE och Simple Password Exponential Key Exchange - SPEKE.

Artikeln Password Authenticated Key Exchange by Juggling är skriven av Feng Hao och Peter Ryan. Artikelns sammanfattning förklarar nyttan med J-PAKE:

Password-Authenticated Key Exchange (PAKE) studies how to establish secure communication between two remote parties solely based on their shared password, without requiring a Public Key Infrastructure (PKI). Despite extensive research in the past decade, this problem remains unsolved. Patent has been one of the biggest brakes in deploying PAKE solutions in practice. Besides, even for the patented schemes like EKE and SPEKE, their security is only heuristic; researchers have reported some subtle but worrying security issues. In this paper, we propose to tackle this problem using an approach different from all past solutions.

Our protocol, Password Authenticated Key Exchange by Juggling (J-PAKE), achieves mutual authentication in two steps: first, two parties send ephemeral public keys to each other; second, they encrypt the shared password by juggling the public keys in a verifiable way. The first use of such a juggling technique was seen in solving the Dining Cryptographers problem in 2006. Here, we apply it to solve the PAKE problem, and show that the protocol is zero-knowledge as it reveals nothing except one-bit information: whether the supplied passwords at two sides are the same.

With clear advantages in security, our scheme has comparable efficiency to the EKE and SPEKE protocols.

(Jonglering med nycklar - om din nyckel heter som ditt husdjur…)

Artikeln innehåller en hel del referenser till koncept och metoder jag inte kände till innan, exempelvis Dining Cryptographers. (Det verkar pågå verksamhet på Wikipedia för att skriva om förklaringen av problemet - se den här och den här sidan.)

Implementationsmässigt verkar den nya metoden inte vara så hemsk. Författarna skriver:

Since our protocol involves several zero-knowledge proofs, one might concern about its cost. We now count the number of exponentiations in the protocol and evaluate its computational effciency..in our protocol, each party would need to perform 14 exponentiations in total – including 8 in the first step, 4 in the second step, and 2 in computing the session key.

To better assess the cost in real terms, we implement the protocol in Java on a 2.33-GHz laptop running Mac OS X. The modulus p is chosen 1024-bit and the subgroup order q 160-bit
…
The results demonstrate that the protocol – executed only once in a session – runs sufficiently fast. The total computation time is merely 0.075 sec. As compared to the time that the user keys in his password, this latency is negligible at the client.

However, the cost at the server may accumulate to be significant if requests are dealt with simultaneously. Therefore, the threat of Denial of Service (DoS) attacks still needs to be properly addressed in practical deployments.

Vad gäller säkerheten skriver författarna att:

EKE requires changing the protocol in its existing form for a secure implementation. As for a SPEKE, it has the drawback that an active attacker may test multiple passwords in one protocol execution. Furthermore, neither protocol – in the original form – accommodates short exponents securely. Finally, neither protocol is provably secure; formal security proofs seem unlikely without introducing new security assumptions or relaxing security requirements.

We choose to solve the PAKE problem using a different approach. The novelty of our design is that we encrypt the password by juggling the public keys in a way that can be verified. As a result, our scheme is provably secure, allows flexible use of short exponents, and strictly limits an active attacker to test only one password per protocol execution.

För ett tag sedan blev Java-koden till implementationen av J-PAKE tillgänglig. Jag har inte testat den själv. Intressant nog kallas den för JPAKE2, vilket skulle kunna betyda att det funnits en tidigare version av algoritmen som man av någon anledning inte var nöjd med.

Författarna har även skickat in J-PAKE som förslag till en framtida utökning av IEEE P1363.

När J-PAKE uppmärksammades på Cyptography-listan dök det upp referenser till en annan, ny PAKE-algoritm. Det finns en Internet Draft, EAP Authentication Using Only A Password som tydligen är under utvärdering av IEEE för den kommande WLAN-standarden 802.11s.

Bra och enkla och allmänt tillgängliga metoder för nyckelutbyte är klart intressant. Med två stycken nya, säkra och ej patenterade utan öppna algoritmer kanske PAKE kan få bättre spridning. Inte minst för inbyggda system är J-PAKE klart intressant.

Jag har postat ett par gånger tidigare om kretstillverkaren NXPs MiFare-system och det egenutvecklade och rejält trasiga kryptot CRYPTO1 som används i Classic-varianter av systemet. MiFare Classic används bland annat av Lokaltrafiken i London och kallas där Oyster Card.

Boingboing rapporterar nu att NXP satt press på forskare vid Radboud University i Nijmegen, Holland för att stoppa publiceringen av sina forskningsresultat som visar ännu fler svagheter i MiFare. NXP har helt enkelt stämt forskarna och åberopar säkerhet som skäl att stoppa publiceringen.

Och självklart innebar detta att artikeln NXP försöker stoppa har smitit ut på nätet. Ett tag fanns artikeln på Wikileaks, men försvann. Däremot har den dykt upp både på Cryptome och på ArXiv.

Artikeln A Practical Attack on the MIFARE Classic beskriver enligt sammanfattninen:

The MIFARE Classic is the most widely used contactless smart card in the market. Its design and implementation details are kept secret by its manufacturer.

This paper studies the architecture of the card and the communication protocol between card and reader. Then it gives a practical, low-cost, attack that recovers secret information from the memory of the card.

Due to a weakness in the pseudo-random generator, we are able to recover the keystream generated by the CRYPTO1 stream cipher. We exploit the malleability of the stream cipher to read all memory blocks of the first sector of the card. Moreover, we are able to read any sector of the memory of the card, provided that we know one memory block within this sector. Finally, and perhaps more damaging, the same holds for modifying memory blocks.

Värt att notera att attacken sker över radiogränssnittet (RFID-standarden ISO 14443). Dvs det är inte så att man plockat isär ett MiFare-kort och attackerat chipet, utan försöker efterlikna ett troligt scenario där någon trådlöst försöker klona ett kort.

Artikeln är rejält matig och innehåller en pedagogisk och bra genomgång av hur MiFare Classic fungerar. Då det finns svenska användare av MiFare är det värt att upprepa artikelns rekommendationer:

For short term improvements we recommend not to use sector zero to store secret information. Configure key B as readable and store random information in it. Do not store sensitive information in the first 6 bytes of any sector. Use multiple sector authentications in one transaction to thwart attackers in an attempt to recover plaintext. This is only helpful when value block commands are not allowed. Value block commands are shorter than a read command and will enable a shift of the keystream.

Another possibility, that might be viable for some applications, is to employ another encryption scheme like AES in the backoffice, and store only encrypted information on the tags. To prevent unauthorized modification of a data block, an extra authentication on this data could be added. This authentication
is then verified in the backoffice.

Proper fraud detection mechanisms and extra security features in the backoffice are necessary to signal or even prevent the types of attacks described above. In general, the backoffice systems collecting and processing data that comes from the readers are a very important second line of defense.

On the long term these countermeasures will not be sufficient. The mifare Classic card has a closed design. Security by obscurity has shown several times that at some point the details of the system will be revealed compromising security. Therefore we recommend to migrate to more advanced cards with an open design architecture.

Forskarna har även gjort en fin film som visar hur deras attack går till. Om deras scanning är så snabb som filmen visar är det här riktigt skrämmande:

Vad skall man säga om NXPs agerande? Istället för att arbeta tillsammans med forskarna och exempelvis i samband med publiceringen ordna seminarier för sina kunder om hur de skall agera för att skydda sig och sina kunder lyckas NXP med att:

1. Reta upp forskarna och förstöra möjligheterna till samarbete
2. Garantera att artikeln och information om hur MiFare Classic skall attackeras kommer ut på ett okontrollerat sätt
3. Framstå som ett otrevligt, aggressivt och ett säkerhetsmässigt inkompetent företag

Tre dumheter på samma gång, det är nästan bättre än ett Kinderägg.

(Ett Mifare-Kinderägg. Öppna och bli överraskad av NXP…)

Slutligen noterar jag att BBC rapporterar att Londons lokaltrafik har problem med sitt Oyster card-system. Oklart om det har att göra med en attack mot CRYPTO1 dock.

Jakob tipsade för ett tag sedan om en artikel som beskriver olika metoder för att införa steganografi i en VoIP-ström.

Artikeln Steganography of VoIP streams sammanfattning lyder:

In this paper, we circumscribe available steganographic techniques that can be used for creating covert channels for VoIP (Voice over Internet Protocol) streams.

Apart from characterizing existing steganographic methods we provide new insights by presenting two new techniques. First one is network steganography solution and exploits free/unused fields of the RTCP (Real-Time Control Protocol) and RTP (Real-Time Transport Protocol) protocols.

The second method provides hybrid storage-timing covert channel by utilizing delayed audio packets. The results of the experiment, that was performed, regardless of steganalysis, to estimate a total amount of data that can be covertly transferred in VoIP RTP stream during the typical call, are also included in this article.

Artikeln innehåller alltså en generell beskrivning av möjliga sätt att kommunicera med steganografi i en VoIP-kommunikation, en skattning av den bandbredd som går att dölja i en VoIP-ström samt två nya metoder för steganografi.

Av de två metoderna tycker jag den andra är mest intressant. Detta inte minst eftersom jag tidigare bloggat om en attack mot anonymiserad VoIP-kommunikation genom att märka VoIP-strömmen med distinkt varians mellan paketen. Här används väsentligen samma metod för att införa en steganografisk sidokanal.

Vi har precis sett att det går att utföra signalanalys på krypterad VoIP-trafik, och där lärdomen ser ut att vara att undvika CODEC:ar med variabel utbandbredd samt sända data i fixa blockstorlekar (om minst 128 bitar).

Här kommer alltså alternativa (eller komplementära) metoder där det intressanta inte går som röstkommunikation, utan det relevanta skickas i en sidokanal i RCTP och RTP alternativt som kontrollerad varians mellan paketen.

Tricket är kanske att sätta talsyntesen på att läsa upp några slumpmässigt valda Wikipedia-sidor. I denna babbelkommunikation skickas sedan (krypterad och integritetsskyddad) information gömd med steganografi.

IT-säkerhets- och kryptokapprustningen går vidare, en artikel i taget.

(Kompletterat med fler funderingar och tankar.)

För några veckor sedan hade Bruce Schneier en postning om en metod för att genomföra avlyssning av krypterad VoIP-trafik.

Bruce postning pekar på en artikel hos New Scientist som innehåller mer information. I artikeln berättas att forskare vid John Hopkins-universitetet på konferensen 2008 IEEE Symposium on Security and Privacy presenterat en artikel om hur de kan detektera ord och meningar även om kommunikationen är krypterad.

En av forskarna bakom artikeln är Charles V Wright.

På Charles webbplats finns två olika artiklar som beskriver olika aspekter av attacker mot krypterad VoIP-trafik. Artikeln Spot Me if You Can: Uncovering Spoken Phrases in Encrypted VoIP Conversations är den som New Scientist skriver om.

Båda artiklarna tar avstamp i att det i många digitala system för röstkommunikation används talkodare (speech encoder) som ger variabel bitlängd (VBR) på kodordet beroende på vad det är för ord som kodas. När sedan det kodade talet krypteras med ett strömkrypto som bevarar längden på kodordet upptår en varians i bitströmmen som är starkt korrelerad till orden i samtalet. Denna varians läcker alltså information om den krypterade kommunikationen, information som går att utnyttja.

Forskarna har fokuserat på CELP-baserade (Code-Exited Linear Prediction) talkodare, vilka ger upphov till variabel kod. CELB-baserade talkodare är mycket vanliga och återfinns bland annat i GSM, LTE (AMR-kodaren), flera “G.”-CODEC:ar (exempelvis G.728) och Speex. I sitt arbete har forskarna har använt Speex.

Forskarna har använt flera olika databaser med röster, databaser som används för att utveckla talkodare, för att upptäcka att det finns en korrelation mellan ord och kodat tal som är krypterat. En av de databaser som använts är TIMIT.

Ord och fraser har kodats med Speex och sedan analyserats utifrån varians. Forskarna har byggt upp en prediktor för varje fras de letar efter, Prediktorerna är Markov-modeller (HMM - Hidden Markov Model).

Prediktorerna har sedan fått titta på den krypterade bitströmmen och utvärdera om den överensstämmer med den varians som skall finnas för de fraser respektive prediktor är tränad på.

Eftersom CELP-kodare arbetar på korta fonem och frikativ blir mer komplicerade ord lättare att detektera. Ord som artificial och intelligence visade sig vara lätta att detektera. (Gissningsvis skulle Laplacetransformerade differentialekvationer sticka ut ordentligt..).

Resultatet är riktigt imponerande/skrämmande/överraskande:

Our results show that an eavesdropper who has access to neither recordings of the speaker’s voice nor even a single utterance of the target phrase, can identify instances of the phrase with average accuracy of 50%.

In some cases, accuracy can exceed 90%. Clearly, any system that is susceptible to such
attacks provides only a false sense of security to its users.

Frasen Young children should avoid exposure to contagious diseases predikterades perfekt i de tester som utförts. Forskarna fick dock en del falska träffar (false positives), men ju längre den sökta frasen var desto mindre falska fel erhölls.

I artikeln beskrivs även om försök att skydda kommunikationen genom att fylla ut den variabla bitströmmen till block om 128, 256 eller 512 bitar. Paddning visade sig fungera mycket bra. Nackelen med paddning är att det kostar i bandbredd. 512 bit stora block med Speex ger en extra bandbredd på drygt 30%. Paddning till 128 bit verkar vara minimum att använda, vilket ger en extra bandbredd på 16.5%.

Den andra, något äldre artikeln, Language Identification of Encrypted VoIP Traffic: Alejandra y Roberto or Alice and Bob? visar hur det går att identifiera vilket språk som talas i en krypterad VoIP-kommunikation. Detta utan orden i samtalet identifieras.

Författarna använder här variansen i samtalet i kombination med information om fördelning av ord, och speciellt bigram och trigram av ord för olika språk. Dessa fördelningar används för att skapa mönster eller prediktorer. Och det fungerar mycket bra. Forskarna skriver:

For instance, our 21-way classifier achieves 66% accuracy, almost a 14-fold improvement over random guessing. For 14 of the 21 languages, the accuracy is greater than 90%. We achieve an overall binary classification (e.g., “Is this a Spanish or English conversation?”) rate of 86.6%.

Även i den här artikeln har författarna undersökt hur väl det fungerar att försöka eliminera variansen genom att padda det kodade samtalet upp till fixa storlekar:

Padding to 128-bit blocks is largely ineffective because there is still sufficient granularity in the packet sizes that we can map them to basically to th esamet hree bins used by our improved classifier inSection4.2.

Even with192- or 256-bit blocks, where dimensionality reduction does not offer substantial improvement, the correct language can be identified on the first guess over 27% of the time — more than 5 times better than random guessing.

Sammantaget innebär resultaten i båda artiklarna alltså att även om det inte går avlyssna/tolka vad som sägs i ett samtal, går det att identifiera vilket språk som samtalet förs på!

Notera att det inte spelar någon som helst roll vilket krypto som används (så länge som variansen är bevarad). Kryptot kan vara hur bra som helst. Detta är ett exempel på en sidoattack och sättet att skydda sig mot detta är att inte tillåta någon varians, utan att kasta bandbredd på problemet och köra med en kodare som har en fix bandbredd ut. En sådan kodare är GSM Enhanced Full Rate, men även Speex innehåller en kodare med fix bandbredd.

En annan observation är att attackerna som presenteras i de två artiklarna är förhållandevis (förvånande) enkla. När väl prediktorerna har tagits fram krävs det lite beräkningskapacitet för att utföra attacken på strömmande data. Har man bara en kraftfull dator borde det inte vara något problem att titta på trafik realtid, iaf för ett begränsat antal samtal och begränsat antal fraser.

Jag hade dock valt att bygga en implementation av artiklarna med FPGA:er.

En trevlig FPGA från Altera.

Markovkodarna borde gå kanonfint att implementera som finita tillståndsmaskiner (FSM) med träningsmönster och tillstånd i block-RAM. En FSM-baserad HMM borde hinna med att hantera flera fraser (tidsmultiplex), och i en FPGA borde det gå att få in hundratals HMM:er.

Med hjälp av tekniken i den gamla artikeln detekterar man vilket språk som gäller. Utifrån den kunskapen laddar man in de träningsmönster som gäller i block-RAM. Sedan kan FPGA:erna leta efter intressanta mönster. Vid träff går man vidare och gör en mer detaljerad analys.

Så hade jag gjort.

På Charles Wrights webbplats finns en hel del andra intressanta artiklar vad gäller trafikanalys på krypterad trafik. Bland annat hur man kan identifiera och visualisera vilken typ av data (videoström, filöverföring, epost, webbsidor) som skickas i en krypterad ström. Mycket spännande om man är intresserad av att veta hur modern trafikanalys kan gå till, och vad man kan göra för att skydda sig.

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