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
September » 2007 » Kryptoblog

Archive for September, 2007

Bra text om design av säkra inbyggda system

September 27th, 2007

Webbplatsen Embedded System Design har en artikel med undertiteln Encryption is not Security som, anser jag, ger en bra introduktion till hur man skall resonera vid design av säkra inbyggda system.

Ett skäl till varför jag tycker att artikeln är bra är att den tar upp ett fenomen jag stöter på ibland, ett fenomen som artikeln beskriver så här:


Ask some developers and device makers about the security of their mobile and embedded devices and they’re likely to tell you about their encryption strength. Then they will probably stop talking.

Artikeln övergår sedan till att beskriva hur man på ett praktiskt sätt kan göra en säkerhetsanalys av sitt system, de användningsfall och den miljö systemet är avsett att fungera i. Artikeln använder en smartphone som exempel:

Attackträd för smartphone
(Bilden är av rätt kass kvalitet, även i artikeln.)

När analysen är gjord kan man sedan identifiera de komponenter och delsystem som behövs för att säkra systemet. Bland dessa komponenter kan krypton finnas med, men det är inte givet på förhand.

En sak jag gillar med artikeln är att den betonar fokus på applikationen och affärsnyttan. Säkerhetsproblem kostar pengar när de inträffar och därför är det viktigt att börja med att identifiera vilka dessa kostnader är:


ying the threat to a business issue makes it much easier to communicate. If top managers don’t understand the threat, it will be much harder for you to win funding and other resources you need to address it. Also, writing the threat from a business perspective helps make sure it gets appropriate attention.

If the description at the base of your threat tree is complicated and/or vague, it can be tough to determine how much attention that issue really needs. Anybody, regardless of technical background, should be able to understand the root threat.

Med tanke på den debatt som pågår om behovet av kompetens, bland konstruktörer, projektledare etc vad gäller att kunna bygga säkra system är den här artikeln en utmärkt, kortfattad introduktion. Ett klart lästips från Kryptoblog.

Ändrade referenser till artiklar

September 27th, 2007

Jag har ändrat metodet som WordPress använder för att skapa referenser till artiklar/postningar på Kryptoblog. Nu skall länkarna vara uppbyggda av datum och titel på artikeln.

Allt ser ut att ha gått bra vad gäller gamla artiklar, men om du träffar på länkar som är trasiga så posta gärna en kommentar här.

Tack!
/Joachim – Kryptoblogmaster

SRAM för ID och slumptalsgenerering

September 26th, 2007

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.

Säkerhet och behovet av beställarkompetens

September 24th, 2007

Computer Sweden har en artikel om att det brister vad gäller säkerhetstänkande i utvecklingsprojekt.

I artikeln intervjuas bla Ann-Marie Eklund Löwinder som säger:


Säkerhet finns med i metoder för utveckling, men när det väl kommer till kritan får säkerhet ofta stryka på foten för att tidplaner och budgetar ska kunna hållas. Det tar tid att jobba med säkerhet, säger Anne-Marie Eklund Löwinder, ansvarig för informationssäkerhet på Stiftelsen för internetinfrastruktur och en av Sveriges ledande experter.

Ann-Marie fortsätter med:


Många utvecklare har inte drillats i säkerhet, säger Anne-Marie Eklund Löwinder.

En annan person som intervjuas i artikeln är Tomas Cardell, arkitekt på IT-Huset i Stockholm som säger:


Tekniska projektledare måste vara tuffare och börja jobba med säkerhet tidigare, även om utvecklarna inte gillar det.

Jag kan inte annat än hålla med. Att i dag som konstruktör inte ha läst böcker som Security Engineering och reflektera över säkerhetsaspekter borde vara närmast tjänstefel. Tyvärr träffar jag extremt sällan på vare sig konstruktörer eller projektledare som tänker på säkerhetsaspekter runt sina konstruktioner.

Att det exempelvis finns potentiella säkerhetsproblem med att exponera sitt inbyggda system mot omvärlden via en öppen IP-adress. Och att då utgå ifrån att inkommande data och kommandon alltid är korrekta och tom från en vänlig part är skrämmande nog helt normalt och vardag.

Men jag anser att artikeln och de som blir intervjuade missar en väsentlig sak: Beställarkompetens.

Om inte den som beställer projektet kräver att systemet som skall utvecklas blir säkert, och man som beställare tar höjd i budgeten för ökade utvecklingskostnader för att säkra konstruktionen kommer det aldrig att ske. Man kan skylla på konstruktörer och projektledare för att slarva med säkerhetsaspekterna, men ges dom inte krav och resurser så går det inte att i efterhand komma och kräva att detta jobb skall utföras.

Vidare mÃ¥ste de utvecklingsprocesser som används utökas, detta för att säkerhet inte bara är nya funktioner, utan i hög grad handlar om att analysera vad som kan gÃ¥ fel (bÃ¥de slumpmässiga fel och avsiktliga fel – attacker) och bestämma hur systemet dÃ¥ skall reagera. Vidare mÃ¥ste verifieringen och granskningen av implementationen utökas med flera nya aktiviteter.

När detta blir vardag kommer (tror jag) utveckling av säkra (säkrare) system inte att upplevas som ett extra bekymmer.

Frågan är hur vi får beställarna att börja ställa dessa krav? Min gissning är att snabbaste vägen är via deras plånböcker.

Ekonomi och IT-säkerhet

September 24th, 2007

Ross Andersson, författaren till den fantastiska boken Security Engineering (som finns för nedladdning – läs!) är forskare vid Cambridge Computer Laboratory – den i mitt tycke forskningsgrupp i Europa som producerar flest intressanta forskningsresultat inom IT-säkerhet. Deras blogg Light Blue Touchpaper innehÃ¥ller ständigt nya spännande rön.
Ross Andersson
(Ross Andersson)

Tillsammans med Tyler Moore har Ross Andersson skrivit en större artikel som försöker ange riktning och möjligheter till framtida forskning som försöker behandla IT-säkerhet utifrÃ¥n ekonomiska termer och incitament. Information Security Economics – and Beyond släpptes i slutet av Augusti och har genererat en hel del diskussioner bland forskare inom IT-säkerhet. (Ross har även hÃ¥llit en presentation i ämnet och presentationsmaterialet finns att ladda ner.)

Sammanfattningen för artikeln förklarar närmare:


The economics of information security has recently become a thriving and fast-moving discipline. As distributed systems are assembled from machines belonging to principals with divergent interests, incentives are becoming as important to dependability as technical design.

The new field provides valuable insights not just into ‘security’ topics such as privacy, bugs, spam, and phishing, but into more general areas such as system dependability (the design of peer-to-peer systems and the optimal
balance of effort by programmers and testers), and policy (particularly digital rights management).

This research program has been starting to spill over into more general security questions (such as law-enforcement strategy), and into the interface between security and sociology. Most recently it has started to interact with psychology, both through the psychology-and-economics tradition and in response to phishing. The promise of this research program is a novel framework for analyzing information security problems – one that is both principled and effective

Ett exempel på problem inom IT-säkerhet som artikeln tar upp är bankbedrägerier och bankernas kostnader för IT-säkerhet:


In the USA, banks are generally liable for the costs of card fraud; when a customer disputes a transaction, the bank must either show she is trying to cheat it, or refund her money. In the UK, the banks had a much easier ride: they generally got away with claiming that their systems were ‘secure’, and telling customers who complained that they must be mistaken or lying. “Lucky
bankers,” one might think; yet UK banks spent more on security and suffered more fraud. This may have been what economists call a moral-hazard effect: UK bank staff knew that customer complaints would not be taken seriously, so they became lazy and careless, leading to an epidemic of fraud

Ett annat problem är hur man får ut bättre och säkrare protokoll på Internet:


Network effects can also influence the initial deployment of security technology, whose benefit may depend on the number of users who adopt it. The cost may exceed the benefit until a minimum number adopt; so everyone might wait for others to go first, and the technology never gets deployed. Recently, Ozment and Schechter have analyzed different approaches
for overcoming such bootstrapping problems [17].

This challenge is particularly topical. A number of core Internet protocols, such as DNS and routing, are considered insecure. Better protocols exist (e.g., DNSSEC, S-BGP); the challenge is to get them adopted. Two widely-deployed security protocols, SSH and IPsec, both overcame the bootstrapping problem by providing significant internal benefits to adopting firms, with the result that they could be adopted one firm at a time, rather than needing everyone to move at once. The deployment of fax machines was similar: many companies initially bought fax machines to connect their own offices.

Jag tycker att Ross och Tylers artikel är mycket läsvärd och leder förhoppningsvis till ny forskning där ekonomiska, sociala och psykologiska aspekter kopplas samman med IT-säkerhet. Att det finns goda möjligheter att hitta nya förklaringsmodeller och därmed lösningar på befintliga problem tycker jag efter att ha läst artikeln verkar klart.

När datorerna blev farliga

September 24th, 2007

(Jag har läst ett antal intressanta artiklar och rapporter som jag tänkt blogga om, men inte hunnit med – sÃ¥ nu kommer en radda postningar med lästips.)

Lars Ilshammar, historiker, journalist och chef för Arbetarrörelsens arkiv och bibliotek, har skrivit en rapport/essä om när datorerna blev farliga.

Lars Ilshammar

Vad Ilshammars text handlar om är inte när datorerna rent tekniskt blev farliga – utan när den mediala debatten och den politiska uppfattningen i Sverige om datorer, bÃ¥de tekniken i sig och användningen av tekniken, övergick frÃ¥n i grunden teknokratiskt och optimistiskt till att vara kritiskt. Ilshammars sammanfattning förklarar det hela:


During the 1960s, Swedish society underwent a rapid and revolutionary computerisation process. Having been viewed as a harmless tool in the service of the engineering sciences during the first part of the decade, the computer became, during the second part, a symbol of the large-scale technology society and its downsides.

When the controversy reached its peak in 1970, it was the threats to privacy that above all came into focus. This debate resulted in the adoption of the world’s first data act in the early 1970s. This paper will study and analyse the Swedish computer discourse during the 1960s, with special focus on the establishment of the Data Act. The core issues are what factors of development and what main figures were instrumental to the changing approach to computer technology during the later part of the decade.

Rapporten är mycket intressant att läsa, inte minst med tanke på den debatt som i dag förs om datalagring, buggning och avlyssning av olika typer av kommunikation. I slutet av 60-talet och bara några få in på 70-talet rasade en rejäl debatt om integritet och då speciellt de hot mot den privata integriteten som datatekniken gav möjlighet till.

Det är tvÃ¥ saker som jag reagerar pÃ¥ när jag läser Ilshammars rapport. Dels hur fort omslaget frÃ¥n en i grunden positiv inställning till en negativ inställning gick. PÃ¥ nÃ¥gra fÃ¥ Ã¥r, frÃ¥n 1968 till ungefär 1972, slÃ¥r attityden om närmast fullständigt och innebär konkreta förändringar som införandet av datalagen och inrättandet av Datainspektionen. Den andra saken jag reagerar pÃ¥ är vilka som gick i frontlinjen för att värna den personliga integriteten – det var nämligen Folkpartiet tätt följda av Moderaterna, samma partier som i dag gÃ¥r i frontlinjen för att inskränka integriteten med hjälp av datorer.

Jag hoppas att företrädare för dessa partier från den tiden pratar med dagens företrädare och diskuterar hur man då resonerade vad gäller skydd för den personliga integriteten kontra effektiv myndighetsutövning och skillnaden mot dagens samhälle. Jag tror vi i det här fallet har mycket att lära av dåtiden.

En bok som då kunde vara bra att läsa är Datamakt, skriven 1975 av den Folkpartistiska riksdagsledamoten Kertin Anér (ISBN 91-7070-421-X). Boken är alltså skriven i efterdyningarna av den debatt Ilshammar skriver om, och en bra sammanfattning av hur man inom Folkpartiet och borgarna resonerade. Boken ser man ofta på antikvariat och är värd att plocka upp. (Jag betalade 20 SEK för mitt ex.)

Ok, förutom integritetsapekter, vad har detta med IT-säkerhet att göra? Jo en koppling jag gör är att i dag finns det reella hot – phising, identitetsstöld, virus, spam, trojaner som folk är relativt medvetna om. Till detta tillkommer ökad övervakning med kameror, buggning etc – detta utan att farorna analyseras speciellt mycket. Samtidigt exponerar sig folk pÃ¥ Facebook, MySpace, Flickr etc och tycker att det är helt ok. Vi har alltsÃ¥ en mycket komplex blandning av psykologi, integritet, datoranvändning, reeella och imaginära hot samt utdelning och bearbetning av personlig information med i mÃ¥nga fall global exponering.

I detta läget kanske vi, precis som när datorerna blev farliga, borde ha en ordentlig offentlig debatt. Det kanske är dags att exempelvis sociala nätverk på Internet, messa, LOL-cats, övervakningskameror och e-myndigheter betraktas utifrån säkerhet och integritet? Att dom kanske är lite farliga.

Cyberattack mot Sverige

September 21st, 2007

Enligt en artikel hos IDG har flera webbplatser attackerats i Sverige. Olika webbplatser har drabbats av överbelastningsattacker eller blivit vandaliserade (defacement).

Enligt IDG är attackerna kopplade till Lars Vilks och hans rondellhund. En del vandaliserade webbplatser innehåller text på Turkiska, exempelvis IDG:s egen webbplats:

IDGs hackade webbplats

ISP:n Oderland är en av de drabbade operatörerna. Jack Oderland berättar:


Under de senaste veckorna har flera kunder hos webbhotellet Oderland fått sina webbsidor utbytta mot agressiva politiska budskap på svenska och turkiska. Säkerhetshål i mjukvara som installerats av kunderna har utnyttjats och Oderland har spårat angreppet till Turkiet.

– De som berördes var svenska sajter som inte hade någonting med politik att göra. Snarare så handlade det om var angriparna hittade säkerhetshål, säger Jack Oderland, vd på Oderland Webbhotell.

IDG kallar det hela ett IT-krig. Det är helt klart att gå för långt. Men att grupper av personer relativt enkelt kan attackera ett annat lands IT-resurser när man tycker att det behövs är lite otrevligt.

Detta påminner en del om attackerna mot Estland för några månader sedan. Wired hade en artikel om de attackerna, en artikel som iaf en av de inblandade anser vara en bra beskrivning.

Matematik, kryptologi och bevisbar säkerhet

September 16th, 2007

Neal Koblitz, som förutom att han åkt tåg i Peru är professor i matematik vid University of Washington:
Neal Koblitz

Neal har skrivit en tankeväckande och läsvärd artikel publicerad i senaste numret av American Mathematical Society Notices, kallad The Uneasy Relationship Between Mathematics and Cryptography om förhållandet mellan matematik och kryptologi samt varför han inte tror på begreppet bevisbar säkerhet.

Jag är inte kryptolog, och (kan jag erkänna) har aldrig känt mig helt komfortabel och naturligt hemma i matematikens magiska och fantastiska värld. För mig är det därför fascinerande att läsa en artikel av en person som tittar på kryptologi från det motsatta hållet (om man kan kalla det det).

Neal Koblitz börjar med en kort bakgrund till sitt engagemang inom kryptologin och hur han som matematiker var med och publicerade dom första rönen vad gäller att använda olika typer av kurvor (exempelvis elliptic curve) för att skapa assymetriska krypton. Men huvudelen av artikeln är fokuserad på matematikers och kryptologers olika bakgrund, hur man förhåller sig till sin forskning samt vad som egentligen är ett bevis.

En skillnad mellan kryptologi och matematik som Neal tar upp är hur resultat publiceras:


In 1996 I was the program chair of Crypto. To someone trained in mathematics this was an unsettling experience. About two-thirds of the submissions arrived by courier mail within 48 hours of the final deadline. Many had obviously been rushed and were full of typesetting errors. One author had sent me only the odd-numbered pages. A few had violated the requirement of anonymity (there was a policy of double-blind reviews). Several had disregarded the guidelines that had been sent to them.
And in many cases the papers had little originality; they were tiny improvements over something the same authors had published the year before or a minor modification of someone else’s work.

Mathematical publishing works differently. In the first place, most articles appear in journals, not conference proceedings—and journals don’t have deadlines. In the second place, people in mathematics tend to have a low opinion of authors who rush into print a large number of small articles—the derogatory term is LPU (least publish- able unit)—rather than waiting until they are ready to publish a complete treatment of the subject in a single article.

Mathematicians, who are part of a rich tradition going back thousands of years, perceive the passing of time as an elephant does. In the grand scheme of things it is of little consequence whether their big paper appears this year or next. Computer science and cryptography, on the other hand, are influenced by the corporate world of high technology, with its frenetic rush to be the first to bring some new gadget to market. Cryptographers, thus see time passing as a hummingbird does. Top researchers expect that practically every conference should include one or more quickie papers by them or their students.

Neal Koblitz verkar alltså anse att kryptologin som en del av datavetenskap skyndar med sina resultat, och detta syns inte minst på de bevis som används. Koblitz skriver:


The idea of “provable security” is to give a mathematically rigorous proof of a type of conditional guarantee of the security of a cryptographic protocol. It is conditional in that it typically has the form “our protocol is immune from an attack of type X provided that the mathematical problem Y is computationally hard.

The form that proofs of security take is what is known as a reduction. Reductions from one problem to another occur implicitly throughout mathematics; in computer science, reductions are the main tool used to compare and classify problems according to their difficulty.

In provable security papers the authors try to prove that a mathematical problem that is widely believed to be computationally hard, such as factoring large integers or finding elliptic curve discrete logs, reduces to a successful attack of a prescribed type on their cryptographic protocol.

Och vad är då kruxet? Jo ett stort krux som Koblitz pekar på är att även om de problem som man försöker reducera sitt säkerhetsproblem till är asymptotiskt svåra, innebär det inte att säkerhetsproblemen är säkra i de data/nyckelstorlekar som används praktiskt:


What had happened was that people had made recommendations for parameter values that were based on an asymptotic theorem. That theorem said that in the limit as N​ approaches infinity, you can securely generate O (log​log​N​) pseudorandom
bits each time you perform a squaring modulo the composite number N​. (Here “securely” means, roughly speaking, that no one can distinguish between the sequence and a truly random one by an algorithm that runs in reasonable time.) However, as I mentioned when discussing Joe Silverman’s xedni calculus, it is fallacious to use an asymptotic result as a practical guarantee of security. Rather, one needs to perform a detailed analysis using realistic ranges for the parameters.

Koblitz tar som exempel upp problemet med OAEP och den förbättring som Krawczyk publicerade 2005.

Jag kan som sagt för lite för att bedöma om Koblitz har rätt eller ej, men jag tycker att hans artikel är läsvärd och inte så lite småskrämmande. Koblitz ser ut att få stöd av iaf James A. Donald som på maillistan Cryptography postade följande tanke:


If a proof is a record of a mental journey in which one person has discovered an important truth, and then made a record of that journey adequate so that a second person can walk the same path and see the same truth, then cryptography could do with more and better proofs.

If, on the other hand, a proof is an argument impressively decorated with mathematical sounding jargon, cryptography could do with a good deal fewer of them.

Vad tror du?

Synkproblem och osäkra trådlösa bilnycklar

September 14th, 2007

I en kommentar till Bruce Schneiers artikel om knäckningen av KeeLoq, något jag bloggat om tidigare, dök det upp ett annat intressant problem med trådlösa bilnycklar.

En ful Chrysler Sebring

Bloggen Restlessobsessive beskriver att det iaf för den trÃ¥dlösa bilnyckeln till hans Chrysler Sebring finns ett problem hur mÃ¥nga gÃ¥nger bilnyckeln kan aktiveras när den inte är i närheten av bilen – och hur Chrysler hanterat detta problem:


The transmitter is matched to the car at the factory, but it has some kind of internal limitation on how many new unique codes can be generated without communication. According to the owner’s manual, if the keyless entry is keyed “more than 250 times” when not within range of the car, this pairing is lost. I suspect they really mean more than 255 times, but that’s a nit. Anyway, since there is a way the customer can lose the pairing, there has to be a way to resync.

The way to resync, on my car, is simply this: Lock the doors (using the door-lock switch on the door, of course, because your remote doesn’t work), then press the buttons on the remote in a particular way (which I will skip here to maintain a little security through obscurity). The remote resyncs and then can be used to unlock the door again.

Så vad är problemet? Jo, det här:


If you haven’t figured out the exploit by now, it is simply that if the owner of the car has locked his doors with the door-lock switch, any schmoe with the same remote can then press the appropriate sequence on his remote and get into the car.

Oops!

Ett enkelt sätt för Chrysler att fixa detta hade varit att kräva att nyckeln används för att starta tändningen i bilen för att synkroniseringen skall genomföras, vilket gör att den fysiskt korrekta nyckeln användas.

(Tipstack till Leif.)

Nej, Microsoft patenterar inte ett oknäckbart kopieringsskydd

September 11th, 2007

Nu pÃ¥ morgonen har det kommit flera artiklar om att Microsoft har patenterat ett oknäckbart kopieringsskydd. Artiklarna betonar gärna oknäckbart, för att markera att man tvivlar pÃ¥ att det är oknäckbart (lugn vi kommer till det). Jag väljer i stället att betona ordet kopieringsskydd, för det är fel. Det Microsoft har patenterat är inte ett kopieringsskydd, det är en metod för att digitalt märka kopior av en mediafil – en digital vattenstämpel.

Det finns ett antal metoder för lägga in extrainformation i mediafiler utan att det (för en människa) påverkar bild/ljud-upplevelsen. Detta används för att märka digitala media, exempelvis med information om upphovsrätt och identitet på specifika kopior. För den som är intresserad kan jag rekommendera boken Data Hiding Fundamentals and Applications, en bok jag recenserade i en IDG-tidning för något år sedan.
Boken Data Hiding Fundamentals and Applications

Den boken ger en mycket bra introduktion till metoder för att skapa digitala vattenstämplar, hur man detekterar vattenstämplar i en fil samt hur man gör vattenstämplarna robusta mot olika typer av attacker. Rent konkret handlar det om att på olika sätt koda in en mindre mängd data (säg en 64 bitars ID-kod) i mediadatats lägsta bitar. Är mediafilen stor går det att använda extremt låg bandbredd i sin steganografiska kommunikation och ändå få den inlagd med mycket redundans. Den digitala nålen i höstacken

Microsofts nya patent bygger på forskning utförd av Kirovskis och Malvars från Microsoft Research. Dessa två personer står även som uppfinnare av patentet. Vad Kirovski och Malvar verkar ha gjort är att hitta på en specifik version av en kodningsmetod kallad Correlated Hopping Enhanced Spread Spectrum (CHESS) och hur man skall applicera den för att lägga in robusta digitala vattenstämplar i ljudfiler.

Bild från MS patent

Kirovski och Malvar har publicerat flera stycken artiklar värda att titta närmare på om man vill förstå hur deras teknik fungerar. Enligt Citeseer har Kirovski och Malvar publicerat artiklar om detta sedan iaf 2001, men de citerar samtidigt artiklar av Ingemar J. Cox, Joe Kilian, Tom Leighton, Talal Shamoon etc som även de publicerat artiklar om spread spectrum-baserad watermarking från minst 1996 och framåt. I den sista av Kirovskis och Malvars artiklar (SSW.pdf) finns en intressant beskrivning om hur de testat sitt system:


We have designed a complete SS audio watermarking system using the enhancements described in the previous Section. A reference implementation of our audio watermarking technology on an x86 platform requires about 32 KB of memory for code
and 100 KB for data. The data buffer stores averaged frequency magnitudes for 12.1 seconds of audio, for a watermark length of 11 s. Watermarks are searched with FV′ = ± 2%, which requires ~ 40 tests per search point. Real-time watermark detection under these circumstances requires 15 MIPS. Watermark encoding is an order of magnitude faster, with smaller memory footprints.

While image watermarking techniques can be tested with the Stirmark tool [11], to date a similar benchmark has not been developed for audio. Thus, we have tested our proposed watermarking technology using a composition of common sound editing tools and malicious attacks [12], including all tests defined by the Secure Digital Music Initiative (SDMI) [13]. We tested the system against a benchmark suite of eighty 15-sec audio clips, which included: jazz, classical, voice, pop, instrument solos (accordion, piano, guitar, sax, etc.), and rock. In that dataset, there were no errors, and we estimated the error probability to be well below 10-6. Significantly lower error probabilities can be achieved by increasing the watermark length.

Other attacks against SS audio watermarking include: (i) desynchronization (discussed in Subsection 3.1), (ii) averaging which we prevent by placing watermarks at random positions in an audio clip, and (iii) exhaustive search of watermark bits

Citatet ovan innehåller flera intressanta saker. För det första är detektion beräkningsmässigt inte speciellt krävande (15 MIPS). Mest intressant är dock hur man testat sitt nya system. Dels har man alltså testat med en SDMI-standard och sedan har man använt ganska enkla metoder för att manipulera datat och visat att vattenstämpeln går att detektera.

I de artiklar jag läst verkar det inte vara Microsoft, utan snarare reportrar och andra bedömare som hävdat att den nya metoden är oknäckbar. Ett skäl kan vara att CHESS-kodning används inom militär verksamhet för att bygga mycket störtålig och svårupptäckt kommunikation. Det finns inte mycket om CHESS på nätet, en av få källor är en rapport från Pentagon. En annan är en rapport på IEEE Xplore. (Flera av artiklarna om Microsofts nya, oknäckbara kopieringsskydd tar just upp den militära kopplingen.)

Oavsett vem det är som kom upp med oknäckbar-prylen är det värt att notera att Darko Kirovski och Henrique Malvar inte testat metoder för att tvätta bort digitala vattenstämplar som även de bygger på spread spectrum-teknik, dvs attacker som är riktade mot den typ av digitala vattenmärken de utvecklat. Och denna typ av attacker finns. Lite Googling ger exempelvis den här artikeln som attackerar Kirovskis och Malvars system:


We analyze the fingerprinting method in [1] (JS: Kirovskis och Malvars artikel) and suggest attacks that are better than the ones presented therein. To do this, we observe and use some extra information available in the system. Selection of different attack channel distortion constraints are also discussed. See [2] for various recently proposed attacks on spread spectrum fingerprinting systems for private watermarking.

Att digitala vattenstämplar används för att spÃ¥ra kopior är ingen nyhet. Ett av de senaste exemplen är Erik Davis som pÃ¥ Burning Man-festivalen gav bort en promoskiva som sedan hittade ut pÃ¥ nätet – och den digitala vattenstämpeln kopplade skivan till honom. (Författaren Cory Doctorow har skrivit ett antal essäer för The Guardian, kallade Digital Rights, digital Wrongs om DRM och digitala vattenstämplar väl värda att läsa.)

Hur är det då med att systemet är oknäckbart eller ej? Rent tekniskt ser jag på det så här: Om du kan bygga ett system för att vattenmärka en digital fil. Om du sedan kan bygga någon form av anordning för att detektera ett digitalt vattemärke, då (hävdar jag) går det även att bygga ett anordning som kan ta bort det digitala vattenmärket.

Rent praktiskt handlar det om att fÃ¥ tag pÃ¥ instanser av media med och utan vattenmärkningen, och helst även en kopia pÃ¥ detektorn – vilket kanske inte blir sÃ¥ lätt. Men detektorn lär väl komma implementerad i en version av Windows Media Player, sÃ¥ för att testa sin DRM-tvättare behövs inte mycket mer än att köra det programmet, testa och iterera tills den inte längre klagar.

Hur lång tid det tar att knäcka systemet beror rätt mycket på hur poppis systemet blir. Detta innebär att om MS lyckas sälja sitt nya system till mediabolagen en masse är min gissning att man desto snabbare kommer att misslyckas.

Som jag ser det ligger styrkan i systemet egentligen i att det är patenterat och att MS kan komma att Ã¥beropa DMCA, patentlagar och andra skyddslagar (beroende pÃ¥ vad som finns i olika länder) för att stoppa försök att kringgÃ¥ systemet. Oavsett hur Micrsoft agerar för att skydda sin uppfinning skulle jag inte vilja sätta speciellt mÃ¥nga SwitchCore-aktier pÃ¥ att systemet inte kommer att bli knäckt – detta oavsett hur mycket fräck militär teknologi för dold kommunikation det är släkt med.

Slutligen påpekade min kollega Jonas en annan attackvektor: Att helt enkelt hacka bort detektorfunktionen i mediaspelaren. Kan man inte få upp dörren kan man alltid krossa rutan bredvid.