Kryptoblog

För ett tag sedan skrev jag om olika tekniker för att stoppa kloning av konstruktioner. En av dessa byggde på PUF:ar - Physically Unique Functions utvecklade av företaget Verayo.

I samband med det hittade jag artikeln Offline HW/SW Authentication for Reconfigurable Platforms om att använda PUF:ar för att skydda FPGA-konstruktioner. Jag undrade då hur det gick att implementera PUF:ar i en så kontrollerad och reglerad struktur som i en FPGA. Jag hade artikeln sum lunchläsning och vet nu lite mer. Och jag är rätt besviken.

Problemet författarna försöker lösa är att hindra att inköpt SW som exekveras på en processor implementerad i en FPGA kopieras. Själva processorn och annan HW implementerad i FPGA:n skyddas genom krypterad konfigurationsfil. Men SW lagrad i externt minne har inte samma skydd. Författarna skriver:

A hardware platform, designed by a System Developer, will be configured into an FPGA. The System Developer will also use third-party software IPs that execute on top of the platform. The System Developer can apply bitstream encryption to protect the hardware configuration in the FPGA, but an additional hardware-software authentication mechanism is needed to protect the software IPs.

Det är alltså inte systemutvecklarens väl och ve man avser att skydda utan leverantören av programvarukomponenten. Och tricket är att implementera en PUF i FPGAn. Alltså att FPGA-leverantören bygger in en PUF, inte att FPGA:n struktur används för att implementera en PUF. Dvs deras sjyddar inte SW implementerade i system på dagens FPGA:er, utan kräver att FPGA-leverantörerna bygger in en PUF-funktion i sina kretsar.

Då den föreslagna metoden innebär ökade produktionskostnader för karaktärisering av varje FPGA, samt att FPGA-leverantören skall skicka upp information om alla tillverkade kretsar på en server låter detta inte speciellt troligt.

Och när författarna testat sitt nya protokoll har dom inte ens använt en riktig PUF-modell:

We have not yet built a PUF implementation, but have simulated its behavior using another AES block with a fixed key.

En riktigt usel och irriterande artikel. Tur att min lunchlåda var extra smaskens. Dessutom hade jag en annan, mycket bättre artikel att läsa. Mer om den senare.

För några dagar sedan bloggade jag om företaget Verayo och deras PUF-teknologi för att stoppa kretskloning. I dag sprang jag på en artikel på EE Times om en annan teknik för att stoppa kretskloning, och den här är riktigt fräck.

Algotronix har utvecklat en mycket intressant teknik kallad DesignTag som gör det möjligt att skydda konstruktioner byggda med FPGA-kretsar. Problemet med SRAM-baserade FPGA-kretsar är att de tappar sin konfiguration när matningen försvinner. Konfigurationen måste därför laddas in från ett externt minne, exempelvis ett FLASH-minne. Och det gör att vill någon klona konstruktionen är det bara att läsa av konfigurationen mellan minnet och FPGA-kretsen.

(I det här läget skall det påpekas att FPGA-leverantörer som Altera och Xilinx har lösningar baserade på krypterad konfigurationsfil där kryptonyckeln lagras internt i FPGA-kretsen och strömsätts med batteri. Detta gör det även möjligt att bygga aktiva skalskydd.)

Algotronix DesignTag försöker stoppa detta genom att för varje konstruktion generera ett unikt konstruktionsblock som identifierar konstruktionen. Genom att läsa av identiteten går det att avgöra vilken konstruktion det är och därmed avgöra om konstruktionen är stulen eller ej.

Och det fräcka är hur DesignTag kommunicerar kretsens ID. DesignTag kommunicerar genom kretsens värmeutveckling!

När FPGAn startar börjar DesignTag-blocket att göra en massa operationer som ökar och minskar värmeutveckling vilket får temperaturen på utsidan av kapseln att variera. Hur temperaturen varierar beror på identiteten. Genom att läsa av temperaturen går det att få fram kretsens identitet. Fräckt eller hur?!

Enligt artikeln implementerar DesignTag ett enkelt LFSR-baserat strömkrypto där identiteten är nyckeln. LFSR-kedjan ger upphov till en PRNG-sekvens som styr värmegeneratorn. Vet man inte att det finns DesignTag aktivt i kretsen ser variansen (förhoppningsvis) ut som slumpmässiga temperaturvariationer.

Det står inte hur värmegeneratorn fungerar. Gissningsvis är det något som ger upphov till stora registeromslag och aktivitet. Ett antal styrbara T-register och/eller multiplikatorer med operander som ger upphov till långa carry-kedjor.

DesignTag-kommunikationen kan knappast vara speciellt snabb så antalet bitar som skickas är antagligen inte så stor. Enligt artikeln stängs DesignTag-blocket av efter 15 minuter.

DesignTag-blocket behöver antagligen kalibreras för varje familj av FPGA-kretsar den används för att kunna ge en bra varians i temperaturen. Vidare går det säkert att bygga en mekanism som detekterar om det finns DesignTag i en konstruktion eller ej. Dels borde det gå att attackera LFSR-kedjan och särskilja DesignTag-mönstret från normal slumpmässig temperaturvariation. Om inte annat borde det gå att vänta 15 minuter och se om det händer något med temperaturen.

Men att kommunicera genom temperaturen är ett otroligt elegant sätt som gör att DesignTag inte behöver ställa några krav på tillgång till kretsens ben.

Verayos teknik gör det möjligt för en krets att själv avgöra om den är klonad eller ej. Men samtidigt är det enkelt för skurken att kontrollera om han lyckats slå ut Verayos teknik eller ej. Algotronix teknik ger inte kretsen möjlighet att avgöra om den är klonad eller ej, men är desto svårare att upptäcka om man inte letar efter den.

Krypto, FPGA-kretsar och sidoattacker - tre önskningar i ett. Kan det bli bättre?

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

Vad passar bättre en regntung semesterdag än testkoda en emulator av den gamla processorn MOS 6502?

Jag kunde i alla fall inte komma på något bättre och hackade lite Python nu på eftermiddagen. 176 rader senare inklusive kommentarer, filhuvud och testfall kan jag i alla fall köra några instruktioner:


js@sotis:/Users/js/tmp>./6502.py
MOS 6502: CPU initializing.
MOS 6502: Dumping memory from 100 to 111
100: ea
101: ea
102: ea
103: ea
104: ea
105: ea
106: ea
107: ea
108: ea
109: ea
10a: ea
10b: ea
10c: ea
10d: ea
10e: ea
10f: ea
110: 60
111: 0
MOS 6502: Running program from start address 100
MOS 6502: Executing NOP
MOS 6502: Executing NOP
MOS 6502: Executing NOP
MOS 6502: Executing NOP
MOS 6502: Executing NOP
MOS 6502: Executing NOP
MOS 6502: Executing NOP
MOS 6502: Executing NOP
MOS 6502: Executing NOP
MOS 6502: Executing NOP
MOS 6502: Executing NOP
MOS 6502: Executing NOP
MOS 6502: Executing NOP
MOS 6502: Executing NOP
MOS 6502: Executing NOP
MOS 6502: Executing NOP
MOS 6502: Executing RTS
Cycles executed: 34


(Japp, min emulator räknar bland annat även cykler. Har alltid velat ha den funktionen. Tänk vad många cykler man räknade i sin finniga ungdom när man kodade på C64:an.)

Det saknas en massa instruktioner och jag är inte säker på om jag verkligen skall ha en separat decode-funktion och en exekverings-funktion. Det blir väldigt mycket upprepning av if-elsif-elsif-else i de två funktionerna.

En intressant (nåja) observation är att min emulator, skriven i ett intepreterande språk, antagligen är flera gånger snabbare än den verkliga processorn. Dock inte lika snabb som den variant av 6502 vi byggde in i InformAsics VPN-chip, den går i upp till 33 MHz.

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.