Warning: Missing argument 2 for wpdb::prepare(), called in /home/stromber/public_html/kryptoblog/wp-content/plugins/wp-super-edit/wp-super-edit.core.class.php on line 109 and defined in /home/stromber/public_html/kryptoblog/wp-includes/wp-db.php on line 1222
SRAM för ID och slumptalsgenerering » Kryptoblog

SRAM för ID och slumptalsgenerering

September 26th, 2007 by Joachim Strömbergson Leave a reply »

För några veckor sedan dök det upp en spännande artikel av Daniel Holcomb, Wayne Burlesson och Kevin Fu med titeln Initial SRAM State as a Fingerprint and Source of True Random Numbers for RFID Tags. Artikeln presenterades på Conference on RFID Security 2007 och artikelns sammanfattning lyder så här:


RFID applications create a need for low-cost security and privacy in potentially hostile environments. Our measurements show that initialization of SRAM produces a physical fingerprint. We propose a system of Fingerprint Extraction and Random Numbers in SRAM (FERNS) that harvests static identity and randomness from existing volatile CMOS storage.

The identity results from manufacture-time physically random device threshold mismatch, and the random numbers result from run-time physically random noise. We use experimental data from virtual tags, microcontroller memory, and the WISP UHF RFID tag to validate the principles behind FERNS. We show that a 256byte SRAM can be used to identify circuits among a population of 160 virtual tags, and can potentially produce 128bit random numbers capable of passing cryptographic statistical tests.

Vad artikelns författare alltså försöker göra är att titta på innehållet i ett SRAM-minne som precis blivit strömsatt (initialtillståndet), och utifrån detta skapa två saker:

  1. Ett sätt att identifiera kretsen

  2. Extrahera slumptal (entropi)

På artikelförfattaren Daniel Holcombs webbplats finns en film som visar att den i artikeln presenterade FERNS-tekniken fungerar. Artikelförfattarna ger följande motiveringen till att behovet av ett nytt sätt att identifiera enheter:


In the most general terms, RFID circuits can be identified either through the use of non-volatile memories or the use of some identifying physical characteristic, which we call fingerprinting. The non-volatile approach involves programming an identity into a tag at the time of manufacture using EPROM, EEPROM, flash, fuse, or more exotic strategies.

While non-volatile identities are static and fully reliable, they have drawbacks in terms of the process cost and the area cost of supporting circuitry. Even if only a small amount of non-volatile storage is used, the process cost must be paid across the entire chip area. Additionally, supporting circuitry such as charge pumps for tunneling oxide devices, and programming transistors for fuse devices, are needed.

CMOS-teknik, krypto, RFID, hÃ¥rdvara och säkerhet – kan det bli bättre? Som ämne för Kryptoblog, antagligen inte. Men tyvärr är det säkerhetsmässigt inte sÃ¥ bra som man först kan tro. Men vi börjar med en beskrivning av tekniken. UtgÃ¥ngspunkten är CMOS-teknik, mer exakt hur en enskild SRAM-cell är uppbyggd och hur den beter sig när matningen kopplas in. (Jag lÃ¥ter här artikeln förklara.)

SRAM-cell
(Figuren är inte från artikeln, men visar samma typ av SRAM-cell med sex transistorer. Q och Q-tak motsvarar artikelns A och B.)


Each bit of SRAM is a 6 transistor storage cell, consisting of cross coupled inverters and access transistors. Each of the inverters drives one of the two state nodes, labeled A and B. When the circuit is unpowered, both state nodes are low (AB=00). Once power is applied, this unstable state will immediately transition to one of the two stable states, either ’0’ (AB=01) or ’1’ (AB=10).

The choice between the two stable states depends on threshold mismatch and thermal and shot noise. Because the stabilization depends only on mismatch between local devices, the impacts of common mode process variations such as lithography, and common mode noise such as substrate temperature and supply fluctuations, are minimized…

RAM cells with large threshold mismatches are heavily skewed toward one state, and are immune to the small disturbances of noise. Because these cells consistently stabilize to the same state, and vary across chips, they can be used to identify the tag. RAM cells that happen to have well matched thresholds are highly sensitive to noise. In these cells, physically random noise will determine the outcome.

För att utnyttja denna effekt extraheras SRAM-minnet från kretsen (dvs en komplett minnesdump). Detta sker ett upprepat antal gånger och mellan varje extraktion slås matningen till kretsen av och på igen. Utifrån minnesdumparna identifieras sedan vilka bitar som antar ett givet värde (noll eller ett). Eftersom dessa styrkan på entydigheten i initialtillstånd är statistiskt använder artikelförfattarna Hammingavstånd för att skapa ett fingeravtryck för kretsen.

Vid identifiering läser man sedan återigen ut minnet och matchar det mot en databas av skapade fingeravtryck (eller template på biometrispråk). Precis som för biometri kan denna teknik man komma fram till fel ID, så kallade false positives och false negatives, något artikeln påpekar.

Ett uppenbart problem är att SRAM-minnen har minne, dvs att det tar tid för att information lagrad i ett SRAM-minne försvinner efter att strömmen till minnet kopplats bort. Första gången jag såg denna minneseffekt (remanence på engelska) var när jag som finnig tonåring hackade kod på Commodore 64:an, en brödburk fylld med SRAM-kretsar:

Commodore 64

En sak som då var lätt att se var att om man hade ett program i minnet och slog om strömknappen (på-av-på) och tittade i minnet med en maskinkodsmonitor kunde man se att det fanns rester av det gamla programmet kvar. Ju längre tid strömmen var av desto mindre fanns det kvar av programmet. Denna minneseffekt fanns då, och den finns i dag också.

Det finns flera olika artiklar etc som tar upp minneseffekten i SRAM-kretsar:

Jag kontaktade författarna av artikeln för att se om dom tagit minneseffekten i beaktande. Svaret jag fick visar att det inte var något man tagit med i sin analys av tekniken:


We did not formally study data-remanence and read frequency, but are certainly aware of the work of Gutmann and Skorobogatov. These works collectively seem to indicate that long-term remanence is not a problem in modern chips (Gutmann), but that short term remanence is (Skorobogatov).

In our experiments, we simply made sure to wait “long-enough” between power-ups that the short term remanence would have died out and verified this by checking that correlation between successive trials had reached a minimum. With the SRAM chip “long enough” was less than a second, with the MSP430, it was much longer due seemingly to the design and external capacitors on the power lines. We intend for our method to be applied to chips that have been powered off for a while before use, and not for high throughput of random numbers.

Ett annat problem med tekniken artikeln beskriver är att bitarnas initiala beteende kommer att pÃ¥verkas av kretsens miljö, exempelvis av temperatur. Ett annat bekymmer är om det finns krypströmmar som kan rÃ¥ka mata minnet eller pÃ¥ annat sätt inducera fält i minnet. Och naturligtvis är flera av dessa yttre effekter är sÃ¥dana att den som vill kan pÃ¥verka dom och därmed vilket ID och slump som extraheras. Slutligen Ã¥ldras CMOS-kretsar (mer eller mindre lÃ¥ngsamt – beroende pÃ¥ miljö, användning etc), och dÃ¥ ändras även beteendet.

Dessa bekymmer gjorde att flera personer på Crypography-listan reagerade när artikeln dök upp. En av de som reagerade var Peter Gutmann som bland annat skrev:


The problem with using device state in this manner is that it’s completely dependent on the device technology and environment in which it’s used. Anychange in the manufacturing process can change the results. Any change in the environment (temperature, supply voltage, etc) can change the results.

A deliberate attack, for example irradiating the device to change the RAM cell threshold, can change the results. Even without deliberate modification, SRAM cells that store a constant value tend to acquire a set over time in which they’ll come up in that state when powered on (this has happened with crypto hardware storing keys over long periods of time in SRAM)... ECC memory scrubbing may set the RAM into a predetermined state. A slow memory test during POST (which writes all cells rather than doing a quick test with a large stride) would have the same effect. The list goes on and on…

The worst case is a change in the environment or manufacturing process, which typically occurs without the end user even knowing about it. You simply can’t guarantee anything about RAM state as an RNG source, you’d have to prove a negative (no change in manufacturing technology or the environment will affect the quality of the source) in order to succeed. It’s like the thread-timing-based RNGs, you can never prove that some current variation of or future change to the scheduler won’t result in totally predictable “random” numbers.

So RAM state is entropy chicken soup, you may as well use it because it can’t make things any worse, but I wouldn’t trust it as the sole source of entropy.

Även James A. Donald såg klara problem med tekniken i artikeln:


Using SRAM as a source of either randomness or unique device ID is fragile. It might well work, but one cannot know with any great confidence that it is going to work. It might work fine for every device for a year, and then next batch arrives, and it completely fails. Worse still, it might work fine on the test batch, and then on the production run fail in ways that are subtle and not immediately obvious.

Men jag ser ännu fler problem:

  • Konceptet att skicka iväg en minnesdump och sedan lÃ¥ta en extern enhet komma fram till vilket ID en krets har förändrar flera protokoll. Inte minst challenge/respons-baserad autenticering, vilket används för RFID blir extremt konstig om RFID:n mÃ¥ste prata (i klartext) med en extern enhet för att veta vem den själv är.

  • Artikeln förslÃ¥r att kretsen skall använda minnets initialtillstÃ¥nd som grund för att exempelvis generera kryptonycklar. Men om initialtillstÃ¥ndet skickas iväg till en extern enhet exponeras basen för nyckelgenerering.

  • Om inte kretsen kan kontrollera att long-enoung tid har gÃ¥tt och skickar iväg innehÃ¥llet i minnet riskerar kretsen att skicka iväg potentiellt känslig applikationsinformation frÃ¥n föregÃ¥ende operation. Informationsläckage alltsÃ¥.

Slutligen har jag svårt att se att man med samma kommunikationsresurser som man har i enkel RFID (passiv backscatter) skall hinna med att skicka över multipla kopior av minnet utan att det påverkar applikationen RFID-enheten används i. Vidare innebär den större mängden data som skall överföras och den mer komplexa identifieringen ökade systemkostnader. Med detta i beaktande tror jag inte att det finns någon som är beredd att byta ut en enkel process för att få ett entydigt chip-ID mot en komplicerad process som till slut ger ett statistikt ID med risk för felidentifiering.

Min slutsats är att artikeln visar på spännande nytänkande vad gäller att använda fysikaliska fenomen kopplade till tillverkningsprocessen i digital CMOS-kretsar. Vidare görs i artikeln intressanta kopplingar mellan biometriska signaturer och fysikaliska mönster i integrerade kretsar.

Men jag ser på tok för stora säkerhetsmässiga problem med minneseffekter, möjlighet att påverka kretsen och andra osäkerheter för att jag skulle vilja använda SRAM-minnet som entropikälla. Vidare känns ID-metoden både på tok för komplicerad och resultatet är för svagt för att jag skall se att det finns en praktisk nytta av tekniken.

Jag har dock skickat ett antal följdfrågor till författarna av artikeln. När jag får svar på dom frågorna återkommer jag.

No related posts.

Related posts brought to you by Yet Another Related Posts Plugin.

Advertisement

3 comments

  1. adam says:

    Mycket intressant genomgång och analys av aktuell forskning! Ser fram emot att läsa uppföljningen.

Leave a Reply

You must be logged in to post a comment.