Kryptoblog

Det har kommit så många olika typer av attacker på hashfunktionen MD5 att man nästan skulle kunna tycka att liket borde få vila i frid. (Bara IACR listar 21 artiklar om MD5.) Men fortfarande används MD5, fortfarande publicerades det nya artiklar om attacker på och svagheter hos MD5.

Den första riktigt stora attacken mot MD5 var den artikel av Wang, Feng och Yu som 2004 presenterade kollisioner mot MD5, HAVAL och RIPEMD.

En av mina sommarläsningsartiklar var A New Collision Differential For MD5 With Its Full Differential Path av Tao Xie, DengGuo Feng och FangBao Liu. Skälet till att jag valde att läsa den är att den inte känns som en i gänget av alla som smånyper lite i sidan på MD5. Nej här handlar det om ett frontangrepp. Mer specifikt hävdar författarna att dom hittat en ny, komplett kollision mot MD5. Författarna skriver:

Since the first collision differential with its full differential path was presented for MD5 function by Wang et al. in 2004, renewed interests on collision attacks for the MD family of hash functions have surged over the world of cryptology. To date, however, no cryptanalyst can give a second computationally feasible collision differential for MD5 with its full differential path, even no improved differential paths based on Wang’s MD5 collision differential have appeared in literature.

Firstly in this paper, a new differential cryptanalysis called signed difference is defined, and some principles or recipes on finding collision differentials and designing differential paths are proposed, the signed difference generation or elimination rules which are implicit in the auxiliary functions, are derived.

Then, based on these newly found properties and rules, this paper comes up with a new computationally feasible collision differential for MD5 with its full differential path, which is simpler thus more understandable than Wang’s, and a set of sufficient conditions considering carries that guarantees a full collision is derived from the full differential path.

Finally, a multi-message modification-based fast collision attack algorithm for searching collision messages is specialized for the full differential path, resulting in a computational complexity of 2**36 and 2**32 MD5 operations, respectively for the first and second blocks. As for examples, two collision message pairs with different first blocks are obtained.

Artikeln är tjock, med massor av information. Bland annat finns ett appendix med den kompletta differensvägen (om man skall tro artikeln) samt regler för att skapa kollisioner. Jag kan lätt erkänna att jag som lekman inte hängde med hela tiden, och det berodde inte bara på att skallen var i semester-mod.

Frågan man bör ställa sig är vad artikeln kommer att innebära. Som det verkar går det nu att på rimlig tid (även om 2**36 MD5-operationer inte görs i en handvändning) skapa kollisioner. Detta ökar risken för att den här typen av attackvektorer börjar utnyttjas. Men i vilka sammanhang kan detta vara ett problem?

Ström-, spänning- och effektbaserade sidoattacker på digitala hårdvaruimplementationer har tidigare fokuserat på logikdelen av implementationen. Ett exempel är attacker mot implementationer där det i algoritmen förekommer en multiplikator.

Antalet bitomslag i en multiplikator varierar väldigt mycket beroende på vilka operander som används. Denna varians ger i sin tur upphov till mätbara varianser på strömförbrukningen. Ett exempel på den här typen av attack beskrivs i artikeln DPA on n-Bit Sized Boolean and Arithmetic Operations and Its Application to IDEA, RC6, and the HMAC-Construction.

En av mina sommarläsningsartiklar var Information Leakage of Flip-Flops in DPA-Resistant Logic Styles och i den presenteras en sidoattack mot de register i en hårdvaruimplementation som används för att lagra interntillståndet. Författarna till artikeln skriver i sammanfatttningen att:

We show that many of the proposed side-channel resistant logic styles still employ flip-flops that leak data-dependent information. Furthermore, we apply simple models for the leakage of masked flip-flops to design a new attack on circuits implemented using masked logic styles.

Contrary to previous attacks on masked logic styles, our attack does not predict the mask bit and does not need detailed knowledge about the attacked device, e.g., the circuit layout. Moreover, our attack works even if all the load capacitances of the complementary logic signals are perfectly balanced and even if the PRNG is ideally unbiased.

Finally, after performing the attack on DRSL, MDPL, and iMDPL circuits we show that single-bit masks do not influence the exploitability of the revealed leakage of the masked flip-flops.

Med andra ord visar artikeln att även om implementationen innehåller olika typer av mekanismer för att skydda logikdelen mot siodoattacker läcker implementationen ändå information via registren.

En flanktriggad D-vippa. Kallas även (D-register eller bara register då det är den absolut vanligaste typen av register som används.

En D-vippa byggd med NAND-grindar.

Artikeln visar att den grundläggande struktur som alla processleverantörer (de företag som erbjuder kretstillverkning) har i sina cellbibliotek för en D-registret regerar olika när den läser in (sample) och låser (hold) ett nytt värde dels beroende på om det är en etta eller en nolla, och beroende på vilket värde (noll eller ett) som redan låg i registret.

Artikeln använder dessa skillnader i registren för att ta fram två olika attackmetoder och applicerar dessa på testkonstruktioner som är skyddade med tidigare publicerade metoder mot sidoattacker. Att döma av artikeln fungerar metoderna för att plocka ut information. Författarnas slutsats är att:

Since most of the prior analysis of side-channel resistant logic styles focused on the combinational logic, so did the research to improve those logic styles. We think it is time to switch the focus of research to find methods for designing side-channel resistant flip-flops with a decent area and power consumption and a low impact on the operation frequency.

One possible approach could be combining semi-custom design for combinational logic with full-custom flip-flop design.

Jag håller inte riktigt med om att en bra lösning kan baseras på full-custom-register, det skalar på tok för dåligt. Även om full-custom-delen begränsas till de delar i konstruktionen där säkerhetsfunktioner implementeras blir det snabbt väldigt mycket mer arbete. Dessutom skulle det bli lättare att identifiera säkerhetsimplementationen på kretsytan, detta då full-custom-logik har ett distinkt utseende.

Jag tror att artikeln skall tas som utgångspunkt för att ta reda på hur register i cellbibliotek görs immuna mot den här typen av informationsläckage.

En intressant fråga är hur man som konstruktör skall göra när man har än mindre kontroll över regsistrens fysiska uppbyggnad än med cellbaserad kretsteknik. Mer specifikt i FPGA:er. Går det exempelvis använda par eller grupper av register för att skapa sidoattackresistenta register?

Jag såg att det precis publicerades en ny artikel på IACR som beskriver en metod för att skydda implementationer av RSA mot sidoattacker. Jag gissar att den metod som presenteras i artikeln inte är skyddad mot registerattacken. Det finns i alla fall ingen referens till registerattacken.

För ett tag sedan skrev jag att kretsföretaget NXP stämt ett antal forskare i ett försök att stoppa publiceringen av svagheter i MiFare. Domstolen har kommit med sitt beslut, och NXP fick på pälsen.

Jag tycker att domstolen i sitt beslut sammanfattade situationen elegant: Damage to NXP is not the result of the publication of the article but of the production and sale of a chip that appears to have shortcomings.

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