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
Forskning » Kryptoblog

Posts Tagged ‘Forskning’

Implementation av Keccak i FPGA-teknologi

December 17th, 2008

Jag har precis lagt upp en artikel kallad Implementation of the Keccak Hash Function in FPGA Devicessidan med artiklar och dokument.

Artikeln beskriver en del försök jag gjort med att implementera en av SHA-3-kandidaterna, Keccak i olika FPGA-kretsar. Som utgångspunkt har jag använt de referensimplementationer i VHDL som skaparna av Keccak har tagit fram.

Att döma av resultatet verkar Keccak vara en hashfunktion som lämpar sig väl att implementera i FPGA:er. Jag gillar att den går att skala så mycket som den gör. Den minimala low_area_copro-implementationen är verkligen mycket liten ocg ger trots det bra prestanda.

Jag hade dock en del strul med referensimplementationerna vilket till största delen beror på hur VHDL-koden är skriven. Om Keccak skulle bli vald till SHA-3 kommer det att behövas en hel del uppstädning för att få koden till att bli en riktigt bra referensimplementation.

Notera att jag inte i det här läget tar ställning till säkerheten hos Keccak, utan detta är enbart ett försök att utvärdera hur effektivt det går att implementera Keccak i FPGA:er.

Jag tar mycket gärna emot kommentarer och tips.

NIST publicerar lista på alla SHA-3-kandidater

December 10th, 2008

NIST postade för några minuter sedan till den maillista som finns för SHA-3-tävlingen att det nu finns en sida med alla kandidater man accepterat. NISTs Bill Burr skriver om kandidaterna:


NIST received 64 SHA-3 candidate hash function submissions. Overall, NIST is very pleased with the obvious high quality of many of the submissions, as well as the general range of designs. NIST has accepted 51 first round candidates as meeting our minimum acceptance criteria. They are now posted on the NIST website

Den publicerade listan med kandidater ser ut så här:


Abacus
ARIRANG
AURORA
BLAKE
Blender
Blue Midnight Wish
BOOLE
Cheetah
CHI
CRUNCH
CubeHash
DCH
Dynamic SHA
Dynamic SHA2
ECHO
ECOH
EDON-R
EnRUPT
ESSENCE
FSB
Fugue
Gröstl (New spelling: Grøstl)
Hamsi
JH
Keccak
Khichidi-1
LANE
Lesamnta
Luffa
LUX
MCSSHA-3
MD6
MeshHash
NaSHA
SANDstorm
Sarmal
Sgàil
Shabal
SHAMATA
SHAvite-3
SIMD
Skein
Spectral Hash
StreamHash
SWIFFTX
Tangle
TIB3
Twister
Vortex
WaMM
Waterfall

I listan som NIST publiceras visas bara namnet på en av skaparna av respektive kandidat, men att döma av den listan finns det inget svenskt bidrag. Jag skall gå igenom listan mer i detalj och återkommer.

NIST skriver i sin postning lite mer om planerna för tävlingen:


We will review these first round candidates at the first SHA-3 Candidate Conference on February 25-28, 2009 at Leuven. During the summer of 2009 we plan to select about 15 second round candidates for more focused review at the Second SHA-3 Candidate Conference, tentatively scheduled for August, 2010. Following that second conference we expect to select about 5 third round candidates (or “finalists”). At our third conference we will review the finalists and select a winner shortly thereafter. At each stage we will do our best to explain our choices.

The Federal Register announcement specified minimum acceptability requirements for “complete and proper submissions.” These requirements included provisions for reference and optimized C code implementations, known answer tests, a written specification and required intellectual property statements.

NIST har uppenbarligen haft en del bestyr med att få ordning på kandidaterna, och har en del kommentarer om kod, specifikationer etc. Problem på dessa punkter var anledningen till att en del kandidater ej kom med. NIST skriver:


We asked for reference code and optimized 32 and 64-bit code. Some submissions did not include optimized implementations, so we will use the performance results from the reference implementations in our future deliberations. Some submissions were rejected because C code was not provided. NIST specified a specific API for the C code, and a few submissions did not use that API: these submissions were also rejected. In some cases, we made a number of minor corrections to the submitted code (largely in the include statements) in order to allow it to compile and run, but made no major repairs.

NIST attempted to verify that the submitted C programs gave outputs that corresponded to the submitted known answer test results when compiled and run on our reference platform. In several cases there were discrepancies between the known answer test results NIST got on our reference platform, and the known answer test results provided by the submitters. NIST will notify those submitters, and these discrepancies must be resolved in a timely manner if the submission is to be eligible to become a second round candidate.

We also asked for documentation, including a complete specification of the algorithms, known answer test results, a performance analysis on different platforms and a security analysis. The quality of the submitted documentation varied greatly. For the security and performance analyses, we were very liberal in what we accepted. We had difficulty determining that the algorithm specifications were complete in some cases. In some of these cases necessary information, such as initial values or padding rules, were omitted from otherwise well-written specifications, but we were able to easily determine this information from the code; these specifications were considered acceptable, since independent implementers can find what they need and the specification can be easily fixed. Some written specifications were incomprehensible without a careful examination of the C code; the more extreme cases were rejected. Inevitably, there were cases between the two extremes. There were several submissions which we accepted that required us to rely more on the programming code for clear understanding than we liked.

We expect that the algorithms selected as the SHA-3 finalists will have specifications that will allow independent implementers to program or design hardware that will produce results that match those provided by the submitters for the known answer tests. In the AES competition, Brian Gladman and others provided independent implementations of all the finalists. Marginal, hard to follow specifications may affect whether a submission is selected for the second round.

We reviewed the intellectual property statements for all of the submissions. While there remain minor issues in some of the statements, we believe that all the accepted submissions include IP statements that allow us to continue the evaluation process for those submissions for now. However, any IP statement issues must be fully resolved before a candidate can progress to be a second round candidate.

Slutligen noterar NIST att det pågått och pågår en febril aktivitet med kandidaterna utanför NISTs kontroll och NIST kommenterar SHA-3-Zoo:


Many of the accepted submissions have been posted on the SHA-3 Zoo site for some time, and a number have been analyzed and are claimed to be “broken.” In some cases, the submitters have conceded the break. In other cases, the submitters concede the break, but claim that it can be fixed with trivial changes (e.g. by adding a few rounds). In still other cases, it appears that the breaks are fundamental and cannot be fixed without extensive modifications. NIST does not want to spend time in the upcoming SHA-3 conference on accepted, but broken algorithms, unless the break is disputed, or the fix is truly trivial. On the other hand, there has been considerable discussion about what is considered to be a break, and we expect to continue that discussion in Leuven. We also expect to discuss allowing submitters to use their “tunable parameter” to make changes to their algorithm before the second round candidates are chosen.
We will continue to consider submissions where there is a dispute about whether the submission is in fact broken until we can make a determination about the facts of the case.

Första SHA-3-konferensen utlyst

December 5th, 2008

NIST har meddelat att den första konferensen om SHA-3-kandidater kommer att arrangeras i anslutning till konferensen Fast Software Encryption (FSE) 2009. Konferensen hålls 22-25 februari i Leuven i Belgien.

Det börjar samtidigt bli allt mer uppenbart att NIST blivit något överväldigad av alla kandidater som dom fått in. Fortfarande har NIST inte ens presenterat en lista över mottagna kandidater och NIST skriver i utlysningen av konferensen att:


It appears that the number of accepted submissions will considerably exceed the number that NIST and the community can analyze thoroughly in a reasonable time period. NIST is considering ways to involve the cryptographic community in quickly reducing the number of submissions to a more manageable number. The process and criteria for this selection will be a major topic of this conference.

Även Bruce Schneier tar upp det stora antalet kandidater i ett inlägg på sin blogg som egentligen handlar om uppdateringar av sin kandidat Skein. I postningen pekar Schneier bland annat på en artikel om kandidaterna och personerna som skapat dessa, bland annat Peter Schmidt-Nielsen, en 15-årig hashfunktionsutvecklare. Peters kandidat Ponic har dock redan knäckts.

Över huvud taget pågår det en febril verksamhet för att knäcka de kandidater som är kända. På den maillista som finns kommer det dagligen flera postningar om attacker, analyser etc. Och återigen känns det inte som om NIST är med i matchen, utan att SHA-3-tävlingen har fått ett eget liv.

Av de nu 36 kända kandidater som finns på SHA-3 Zoo är nio kandidater knäckta och att det finns någon slags kryptanalys av ytterligare 12.

En ny implementation av J-PAKE

November 29th, 2008

I somras bloggade jag om en ny metod för lösenordsbaserat nyckelutbyte kallad J-PAKE. J-PAKE erbjuder flera ördelar jämfört med andra metoder. Dock har det fram till nu bara funnits en Java-implementation.

Googles kryptoninja och OpenSSL-utvecklaren Ben Laurie har implementerat nyckelutbytesalgoritmen J-PAKE i C som en en modul i OpenSSL. Detta gör att den som vill testa J-PAKE (givet att man har den nya modulen) nu kan använda J-PAKE direkt i OpenSSL. Ben skriver:


So, this weekend I implemented J-PAKE as a proper OpenSSL module. Plus support in s_server and s_client. You can test it like this:


openssl s_server -jpake secret
openssl s_client -jpake secret

If you want to use two different machines, as required by Mr. Churlish, then you’ll need to use the -connect option to s_client.

If you want to use it yourself, you can find example code in apps/apps.c. Look for the functions jpake_client_auth() and jpake_server_auth().

Ben Laurie har även en utmärkt blogg väl värd att läsa om man är intresserad av krypto och IT-säkerhet.

Ben Laurie
Ben Laurie från hans sida med publikationer på Google Research.

Lite SHA-3-nyheter

November 18th, 2008

NIST meddelade för några dagar sedan att de fått in 64 kandidater och att det kommer att dröja till i början av december innan NIST presenterar vilka kandidaterna är. Även om antalet kandidater är mindre än de minst 80 kandidater Bruce Schneier gissade på är det väldigt många.

Även om inte NIST publicerat listan med kandidater finns det en Wikisida kallad The SHA-3 Zoo som listar 28 stycken av kandidaterna inklusive länkar till artikel, webbplatser samt kandidaternas status vad gäller attacker. För attacker och kryptanalysresultat har redan börjat dyka upp.

På den maillista som NIST satt upp är det sedan en tid tillbaka en relativt hög aktivitet med postningar av resultat och diskussioner av hur dessa skall tolkas. Bland annat var några så ivriga att få in ett resultat att de publicerade en attack på kandidaten EnRUPT som är sämre än uttömande sökning. När de sedan fick kritik kom de med följande kommentar som låter väldigt mycket som First Post! på diverse forum:


We started working on the function yesterday. As soon as the paper was finished we sent a message.

Känns inte helt seriöst. Dock gav detta upphov till vad som skall klassificeras som en riktig attack – om attacker som tar längre tid eller kräver mer minne än atomer i hela universum skall anses som allvarliga attacker eller ej. Daniel J Bernstein kom för några dagar sedan med ett riktigt elegant debattinlägg:

2^185 preimage attack on MD6-256


After the recent flood of attacks on hash functions that I had never heard of before this month, I’m pleased to announce that I’ve found an attack on MD6-256 with time complexity just 2^185.

The attack is a “multiple-preimage attack” that simultaneously attacks 232 legitimate target signatures and successfully forges at least one signed message by finding a preimage of the underlying hash. Surely there will be more than 232 signatures generated using SHA-3, so this
is a realistic attack scenario if MD6 is being considered for SHA-3.

Recall from Rivest’s description of MD6 at Crypto that computing MD6 takes a fraction of a millisecond on a single CPU core. The total time for the attack is under 2^185 milliseconds—-I’m talking about actual wall-clock time, not some simplified model. The attack doesn’t fit on a single PC, but is easily implemented on a large cluster of a billion current Core 2 Quad PCs. Memory consumption per PC is negligible. Special-purpose hardware will be even less expensive.

The attack isn’t guaranteed to succeed; a detailed analysis shows that it has only about 1 chance in 100 of succeeding. However, repeating the attack will increase the success probability, and in any event I think we can agree that 1 chance in 100 is already an unacceptable threat for
SHA-3 users. Can we please kick MD6 out of the hash competition now?
—-D. J. Bernstein

Research Professor, Computer Science, University of Illinois at Chicago

P.S. Preliminary analysis suggests that, astonishingly, Skein and Keccak will both succumb to analogous attacks, and that the attack on Skein will be even faster than the attack on MD6. Who would have imagined that three hash-function designs with such different design principles would share a critical weakness?

Räknar man samman vad Bernsteins attack, som har motsvarande upplägg som några av de attacker som kommit på maillistan, ser ut att klara får man en attack på 2^256, dvs uttömande sökning (brute-force).

Det har kommit ett par ordentliga attacker. En av de första att falla var kandidaten NK2SD som är något så ovanligt som en hashfunktion baserad på en tvådimensionell cellautomat inspirerad av Stephen Wolframs A New Kind of Science:

Cellautomater
(Fina figurer från NK2SD-automater)

Just nu listar SHA-3 Zoo åtta stycken kandidater som i någon variant har attackerats. Dock verkar SHA-3 Zoo, NISTs egen maillista och andra aktiviteter leva ett eget liv utanför NISTs kontroll. NIST har gjort klart att inga kandidater i detta läget är borträknade. En sidoaktivitet som pågår är ECRYPTs eBASH där man kör och presenterar prestandatester av alla kandidater. Att döma av resultaten så här långt, med enbart ett fåtal kandidater är det ingen som framstår som snabbare än SHA-2. Ett problem med SHA-2, och tävlingen är tänkt att lösa är just att SHA-2-algoritmerna är så mycket långsammare än SHA-1.

En annan aktivitet är insamling av information om implementationer av kandidater i hårdvaraASIC eller FPGA. En av snabbaste ser ut att vara Keccak. Keccak har jag bloggat lite om tidigare och även om den svampfunktion som ligger till grund för funktionen. Kul att se att den verkar ge bra prestanda.

Jag har läst igenom de flesta artiklar som presenterar de (så här långt kända) kandidaterna. Att presentera resultat om hårdvaruimplementationer av sin kandidat verkar vara en trend bland kandidaterna. En annan trend jag tycker mig se är att beskriva skydd mot sidoattacker – återigen en implementationsaspekt. Både intressant och bra att se att de senaste årens sidoattacker börjar slå igenom och bli något som beaktas vid design av nya algoritmer.

Sättet som flera av kandidaterna hanterar problematiken med sidoattacker är att gå mot enkla grundunktioner – baserade på XOR, rotationer och bitskiftningar samt additioner. Desa grundfunktioner upprepas seda ett (mycket) stort antal gånger. Typiskt används inga S-box-liknande strukturer. Några exempel på detta är MD6, Skein (som bygger på Trieefish-kryptofunktionen) och Cubehash.

Påfallande många kandidater försöker även gå ifrån Merkle-Damgård-konstruktionen och mot helt nya principer för att bygga kompressorfunktioner och hashfunktioner. MD6, Keccak och NK2SD är exempel på detta.

Väsentligen alla kandidatbeskrivningar innehåller mer eller mindre ordentliga beskrivningar om kandidatens säkerhet och skydd mot olika attacker. Men flera av kandidaterna, bland annat MD6 och Skein innehåller bevis – alltså att algoritmen är bevisbart säker. Det skall bli intressant att se huruvida dessa bevis visar sig stämma, och om de antaganden och de villkor under vilka bevisen gäller håller.

Skaparna av kandidaten Skein, skapad av bland andra Bruce Schneier, Niels Ferguson, Stefan Lucks och Doug Whiting, sticker ut för att de har använt ett något annorlunda sätt att argumentera för sin algoritms säkerhet:


Skein was designed by a team of highly experienced cryptographic experts from academia and industry, with expertise in cryptography, security analysis, software, chip design, and implementation of real-world cryptographic systems. This breadth of knowledge allowed them to create a balanced design that works well in all environments.

Är Security by Authority en vettig term för den här typen av säkerhet tro?

Om någon undrar vad Skein betyder är det tydligen ett garnnystan, vilket är en bra liknelse för hur Treefish-funktionernas in- och utdata i Skein slingrar sig runt varandra.

Skein

Jag räknar med att återkomma med mer info om NISTs tävling när de presenterat samtliga 64 kandidater. Sedan lär det dröja några år innan jag får reda på om min gissning stämmer.

Uppdaterad eSTREAM-portfölj och nya attacker

November 17th, 2008

eSTREAM-projektet presenterade sin portfölj med strömkrypton i april i år. Portföljen som då presenterades inkluderade fyra krypton i profil ett avsedda i första hand för SW-implementation och fyra krypton i profil två avsedda för inbyggda system och hårdvaruimplementationer. Dessa krypton var:

Profil ett:

  • HC-128

  • Rabbit

  • Salsa 20/12

  • Sosemanuk

Profil två:

  • F-FCSR-H v2

  • Grain v1

  • Mickey v2

  • Trivium

Sedan april har det hänt en del. Det mest direkta är att eSTREAM-portföljen har uppdaterats med den stora förändringen att F-FCSR-H plockats bort från profil två.

Skälet till detta är att Hell och Johansson skrivit en artikel kallad Breaking the F-FCSR-H stream cipher som tydligen visar en praktiskt genomförbar artikel mot F-FCSR-H. Artikeln skall presenteras på Asiacrypt i december, men tydligen stämmer resultatet då eSTREAM valt att plocka bort F-FCSR-H.

Några andra eSTREAM-krypton som inte ser ut att må speciellt bra är Trivium och Salsa 20, speciellt Trivium ser ut att må dåligt.

I höstas kom Adi Shamirs kubattack som i artikeln innehåller en allvarlig attack mot Trivium. Under hösten har även kommit ett par andra attacker mot Trivium.

I oktober kom artikeln Transforming chosen IV attack into a key differential attack: how to break TRIVIUM and similar designs med en komplexitet på 2**68.

En annan artikel, Slid Pairs in Salsa20 and Trivium, som attackerar både Trivium och Salsa 20 kom i slutet av september. Författarna Deike Priemuth-Schmid och Alex Biryukov skriver:


The stream ciphers Salsa20 and Trivium are two of the finalists of the eSTREAM project which are in the final portfolio of new promising stream ciphers. In this paper we show that initialization and key-stream generation of these ciphers is slidable, i.e. one can find distinct (Key, IV) pairs that produce identical (or closely related) key-streams.

There are 2**256 and more then 2**39 such pairs in Salsa20 and Trivium respectively. We write out and solve the non-linear equations which describe such related (Key, IV) pairs. This allows us to sample the space of such related pairs efficiently as well as detect such pairs in large portions of key-stream very efficiently.

We show that Salsa20 does not have 256-bit security if one considers general birthday and related key distinguishing and key-recovery attacks

Det ser allvarligt ut, men läser man Daniel J Bernsteins svar verkar det inte vara en attack som är bättre än brute force:


These claims are entirely without merit. The “attacks” on Salsa20 are vastly more expensive than the standard brute-force attacks discussed in the original Salsa20 documentation.

Vad gäller Trivium, med tre olika attacker på kort tid, skulle jag inte bli förvånad om den åker ut ur eSTREAM-portföljen och jag skulle vara försiktg att använda den.

Det som gör mig en aning bekymrad är att flera attacker alltså dykt upp strax efter att eSTREAM-projektet avslutats och porföljen presenterats – efter fyra år av utvärderingar.

Om man vore lite konspiratoriskt lagd skulle man kunna få för sig att det är mer prestige och publiceringsvärde i att attackera accepterade och utvalda algoritmer snarare än kandidater. Detta är naturligtvis rent trams, men om det skulle vara så vore det bekymmersamt för forskningen och andra försök att ta fram bra algoritmer – exempelvis för NISTs SHA-3-tävling.

En sista sak om eSTREAM värd att notera är att kryptot Rabbit, enligt en postning av Erik Zenner på eSTREAM-forumet, har fått ändrad licens:


On behalf of Cryptico A/S, the company who designed the Rabbit stream cipher, I’m happy to relay the following:

“Rabbit has been released into the public domain and may be used freely for
any purpose.”

So in retrospect, I think that it was a good decision not to make patent issues a key criterion for the eStream portfolio: The patent status can change, the algorithmic properties can’t.

Tyvärr är inte detta det mest officiella av uttalanden, och dessutom saknar jag information om hur Cryptico avser att agera vad gäller sina patent relaterade till Rabbit. Jag har letat på Cryptico A/S webbplats för att hitta ett mer officiellt uttalande, men där finns inte mycket nyheter.

Jag har kontaktat Erik Zenner för att se om det går att få ett mer officiellt uttalande. Hör jag något publicerar jag det här. eSTREAM-projektets text om licensen för Rabbit har i alla fall inte uppdaterats:


Cryptico A/S currently has patents pending on Rabbit. The algorithm is provided royalty-free for non-commectical use. Licenses for commercial use may be obtained from Cryptico A/S.

Om jag själv skall välja krypton från eSTREAM skulle jag i första hand gå på HC-128 och kanske Salsa 20. I profil två skulle jag välja Grain och Mickey, men då använda versionerna med 128 bit nycklar som inte kostar mer i implementation (bortsett från sex Bytes längre nyckel). Inbyggda system förtjänar lika bra skydd som PC-system.

MD6 och Skein – två SHA-3-kandidater

October 29th, 2008

Dörren för kandidater till NISTs hashfunktionstävling stängs om ett par dagar (2008-10-31). Att döma av trafiken på maillistan kommer det att dyka upp ett flertal kandidater. Men än så länge har inte speciellt många blivit officiella.

Först ut var Ron Rivest och hans kollegor som presenterade hashfunktionen MD6, även kallad Pumpkin Hash. MD6 är ett relativt stort steg från den struktur nuvarande SHA-algoritmerna har. MD6 bygger upp en komplext träd med många subnoder. Trädet processas sedan nerifrån och upp – på något sätt. Det ser komplicerat och kostsamt ut. Men enligt Rivest & Co skall det gå att enkelt serialisera processningen för att köra på små processorer, och samtidigt parallellisera för hög prestanda på multicore-maskiner och i hårdvara.

I dag presenterades en annan kandidat kallad Skein. Skein är skapad av Niels Ferguson, Stefan Lucks, Bruce Schneier, Doug Whiting m.fl. Enligt en postningen om Skein på Schneiers webbplats är hafunktionen byggd på ett blockkrypto kallad Threefish (vilket borde betyda släktskap med Blowfish och Twofish). Bruce skriver:


Skein is fast. Skein-512—our primary proposal—hashes data at 6.1 clock cycles per byte on a 64-bit CPU. This means that on a 3.1 GHz x64 Core 2 Duo CPU, Skein hashes data at 500 MBytes/second per core—almost twice as fast as SHA-512 and three times faster than SHA-256…

Skein is secure. Its conservative design is based on the Threefish block cipher. Our current best attack on Threefish-512 is on 25 of 72 rounds, for a safety factor of 2.9…

Skein is simple. Using only three primitive operations, the Skein compression function can be easily understood and remembered. The rest of the algorithm is a straightforward iteration of this function.

Skein is flexible. Skein is defined for three different internal state sizes—256 bits, 512 bits, and 1024 bits—and any output size. This allows Skein to be a drop-in replacement for the entire SHA family of hash functions. A completely optional and extendable argument system makes Skein an efficient tool to use for a very large number of functions: a PRNG, a stream cipher, a key derivation function, authentication without the overhead of HMAC, and a personalization capability.

Jag planerar att komma med mer detaljerad information när kandidaterna officiellt publicerat. Men det börjar dra ihop sig och det börjar se spännande ut.

P != NP !?

October 29th, 2008

Jag satt och surfade spännande artiklar på fantastiska arXiv och sprang på en märklig artikel.

Artikeln P is not equal to NP av Sten-Åke Tärnlund verkar hävda att den bevisar att P är skilt från NP.

P != NP

Vad det handlar om är alltså den del av komplexitetsteori som säger att det antagligen finns problem som inte går att beräkna på polynomiell tid, dvs en separat klass med problem som för trivialt antal element inte går att beräkna svaret på. Det har länge spekulerats att NP inte är en del av P och frågan är av sådan betydelse att det finns ett pris på en miljon USD för den som kan visa att NP är skilt från P.

Skälet till att detta är så intressant för IT-säkerhet är att det finns ett antal algoritmer där säkerheten beror på att problemen är NP-hårda. Ett sådant problem är Knapsack-problemet som används i kryptosystem med publika nycklar. Över huvud taget görs ofta antaganden om att algoritmer är NP-hårda, och därmed att NP-problem egentligen inte är P-problem. Wikipedia ger ett bra exempel:


Consider, for instance, the subset-sum problem, an example of a problem which is “easy” to verify, but whose answer is believed (but not proven) to be “difficult” to compute. Given a set of integers, does some nonempty subset of them sum to 0? For instance, does a subset of the set {−2, −3, 15, 14, 7, −10} add up to 0? The answer “yes, because {−2, −3, −10, 15} add up to zero”, can be quickly verified with a few additions. However, finding such a subset in the first place could take much longer. The information needed to verify a positive answer is also called a certificate. Given the right certificates, “yes” answers to our problem can be verified in polynomial time, so this problem is in NP.

An answer to the P = NP question would determine whether problems like the subset-sum problem are as “easy” to compute as to verify. If it turned out P does not equal NP, it would mean that some NP problems are substantially “harder” to compute than to verify.

Jag kan på tok för lite matte för att hänga med i Tärnlunds artikel. Den som fixar matten och kan kolla om det håller och om det gäller generellt eller ej får gärna höra av sig. Artikelns sammanfattning är kort och verkar hävda att generellt sett är P skilt från NP:


SAT !∈P is true, and provable in a simply consistent extension B′ of a first order theory B of computing, with a single finite axiomB characterizing a universal Turing machine. Therefore P !=NP is true, and
provable in a simply consistent extension B′′ of B.

SAT som artikeln hänvisar till är Boolean Satisfiability-problemet som tidigare visat sig vara NP-komplett. Det Sten-Åke verkat visa är hur detta resultat går att generalisera till alla NP-problem. Om jag fattar rätt.

Googlar jag på Sten-Åke Tärnlund hittar jag att han är (har varit?) professor i datalogi vid Uppsala universitet.

Avhandling om Informationssäkerhet i vården

October 15th, 2008

För några veckor sedan uppmärksammade GP att Rose-Mharie Åhlfeldt disputerat vid Högskolan i Skövde där hon forskat om Informationssäkerhet i vården.

Rose-Mharie Åhlfeldt
Rose-Mharie Åhlfeldt

Då vården är något väsentligen alla medborgare kommer i kontakt med och att patienter på många sätt redan befinner sig i en utsatt situation tyckte jag att Rose-Mharies avhandling lät relevant och spännande. Trots den del Googlande hittade jag inte avhandlingen. Men en snabb mailkontakt med Rose-Mharie gav länken till avhandlingen Information Security in Distributed Healthcare – Exploring the Needs for Achieving Patient Safety and Patient Privacy.

Jag har inte läst hela avhandlingen, men av det jag läst uppfattar jag det som att avhandlingen ger en rejäl genomlysning av de informationssäkerhetsproblem som finns inom vården. Inte minst viktigt är hur ny teknik och nya sätt att arbeta med utspridda vårdresurser gör det svårt att skydda patienternas integritet. Att över huvud taget hålla koll på var en patients information finns, vem som tittat på den och hur många kopior det finns verkar vara besvärligt och dåligt understött i nuvarande system. Rose-Mharie skriver:


The results show that a comprehensive view of the entire area concerning patient information management between different healthcare actors is missing. Healthcare, as well as patient processes, have to be analyzed in order to gather knowledge needed for secure patient information management.

Furthermore, the results clearly show that there are deficiencies both at the technical and the administrative level of security in all investigated healthcare organizations.

Avhandlingen innehåller en större introduktion som beskriver problemmiljön med aktörer, en sammanfattning av relevant lagstiftning, en beskrivning av informationssäkerhet i den specifika miljön samt definierar olika typer av problem som kan uppstå. Avhandlingen innehåller dessutom ett antal fallbeskrivningar och ett antal artiklar. I en av dessa konstaterar författaren att:


The municipalities do not have adequate experience handling care information and have not kept abreast with the development of systems handling this kind of information. The administration of authorizations is a problem in the municipalities. There is a large turnover of employees as well as different categories of employment positions with variant geographical range. It is unfortunate if choosing a more open strategy for authorization is because the administration is a burden.

Ett resultat jag tyckte var intressant är hur information och informationssäkerhet kan påverka patienters vilja att söka hjälp:


“increasing availability to patient information could also imply that patients do not search for care depending on that they don’t want to have their information available to everyone … that the healthcare personnel are not willing to make complete notes in the records because they are afraid of writing too much since so many other people can read it … this is what people have contacted us about” (respondent B)

Avhandlingen innehåller en rejäl bunt med rekommendationer och jag hoppas verkligen att vårdgivare på olika nivåer tar till sig av resultaten och rekommendationerna i avhandlingen. Tyvärr är det stor risk att det, speciellt på kommunal nivå inte finns utrymme eller ens kompetens att ta till sig avhandlingen resultat. Som författaren skriver:


The results also indicate a lack of IT-competence when the healthcare organization orders or develops a new IT-system. Who decides the competence need for the participants to be included in healthcare IT-
projects? Is there enough IT-proficiency and especially knowledge of information security within the ordering organization or is it necessary to consult expertise externally? According to Gaunt (2000) security education is necessary for the user of the IT-systems in healthcare.

But it is also necessary to ensure a high level of security education for healthcare persons involved in different IT-projects. If the organization does not have sufficient security competence they would benefit from involving other security experts when they create requirement specifications in order to achieve the successful implementation of new systems in healthcare.

Jag hoppas verkligen att Rose-Mharie Åhlfeldts avhandling leder till konkreta förändringar. Det här genuint viktiga frågor som berör enskilda personer, och avhandlingen är för bra för att hamna i ett kommun- eller landstingsarkiv.

Dagens HW-hack: Wolframs 30:e regel

October 13th, 2008

Jag fick en fråga om kryptorelaterade algoritmer som skulle kunna vara lämpliga att köra som exempel i en kurs om system-modellering. Tanken som jag förstod det var att på TLM-nivå simulera SW-funktioner som sedan flyttas till HW.

Intressanta algoritmer behöver både vara enkla att begripa och kunna ge stor skillnad i prestanda, genomströmning etc när funktionen flyttas från SW till HW. Utifrån detta var mitt förslag RC4 (som är enkel, men inte skalar speciellt bra i HW), XTEA, SHA-1 och SHA-2 (256).

Några andra algoritmer man borde kunna sätta i händerna på studenter är eSTREAM-kryptona Grain och Trivium. Båda dessa krypton är relativt enkla att förstå, har intressanta explicita skalbarhetsegenskaper och är välspecificerade med testvektorer, referensmodeller etc.

Sedan slog det mig att en annan, något annorlunda algoritm som skulle kunna användas är Stephen Wolframs cellautomat Rule 30.

Rule 30 är en endimensionell cellautomat som ger upphov till ett slumpmässigt (PRNG) mönster. Rule 30 används som slumptalsgenerator i Wolfram Research Mathematica. En fördel med att använda en endimensionell cellautomat är att den enkelt går att rita upp och grafiskt verifiera.

Rule 30
De första iterationerna av regel 30 samt de styrande tillståndskombinationerna.

En annan kul egenskap är att algoritmen är trivialt parallelliserbar, detta då alla celler kan uppdateras samtidigt. Antagligen går det att göra bra SW-implementationer, inte minst om man tar till SSE-instruktioner alt GPU-acceleration, men en ren HW-implementation blir väldigt enkel.

Jag blev så inspirerad av Rule 30 att jag satte mig ned och hackade ihop ett par implementationer. Först en version i Python (naturligtvis) för att få koll på att jag tänkte rätt. Det blev inte speciellt många rader kod, ca 20 inkl kommentarer. Och jag är säker på att om man är en riktig Pythonista går algoritmen att stampa ner till ett fåtal rader kod, ex med lite list comprehensions.

Sedan hackade jag ihop en RTL-generator (i Python) som kan generera Verilogkod för en Rule30-automat med godtyckligt antal bitar. Den genererade konstruktionen består väsentligen av ett tillståndsregister med en bit för varje cell. För varje cell finns det sedan en enbitars 8-till-1-MUX som implemeterar uppdateringsregeln.

En sak man behöver fundera på är vad som händer för första resp sista biten i arrayen. Jag har valt att göra en ring av arrayen. Detta innebär att vid uppdatering av den högsta biten tittar vi på bit 0 och tvärs om. Implementationsmässigt innebär detta två separata ledningar som går från kant till kant, inte bara lokalt mellan ett cellregisters närmaste grannar.

Jag genererade några stycken versioner av min Rule 30-konstruktion och använde sedan Alteras verktyg Quartus II för att implementera konstruktionen i en Cyclone II-FPGA. Lite resultat:


256 bitar: 687 LEs, 263 MHz
128 bitar: 344 LEs, 358 MHz
64 bitar: 128 LEs, 420 MHz
32 bitar: 64 LEs, 420 MHz
16 bitar: 32 LEs, 420 MHz
8 bitar: 16 LEs, 420 MHz

(Notera att implementationen kräver lika många register som bitar, jag redovisar dock inte det här.)

En snabb analys ger att varje MUX (samt logik för att ladda in ett användarstyrt initialvärde) implementeras med två logikelement (LE). Mellan 64 och 128 bitar ser det ut som att någon form av replikering behöver införas.

Vad gäller klockfrekvensen är 420 MHz max som Cyclone II är specad för. I en annan FPGA, ex Stratix III går det antagligen att få upp klockfrekvensen ytterliggare en bit. Eftersom uppdateringsfunktionen för resp bit består av en 8-1-MUX med ett grinddjup motsvarande ungefär tre NAND2-grindar eller en LE, blir det transportfördröjningen genom FPGA:ns switchnät som sätter gränsen för klockfrekvensen.

Nu är Rule 30 inte en kryptografiskt säker PRNG, men för att vara en PRNG som ger så bra slumpserier så att den duger för Mathematica förbrukar den väldigt lite resurser. Och med 256 PRNG-bitar varje cykel i 263 MHz får vi 67 Gbit/s! (Vilket skulle vara hopplöst att få ut på ett kort och använda utanför FPGA:n.)

Jag tänker slänga upp en version av Verilogkoden, antigen här eller hos InformAsic. Återkommer med det. Nästa steg är att att bygga ut generatorn med stöd för resursdelning, men det gör jag inte i kväll i alla fall.

Att cellautomater har försökt användas i kryptosammanhang finns det flera artiklar som vittnar om. Jag hittade en färsk sådan med titeln LCASE: Lightweight Cellular Automata-based
Symmetric-key Encryption
som just tar upp Rule 30. Värd att läsa om du vill veta mer.