Knudsen, Lars

Lars Ramkild Knudsen ( født 21. februar 1962 ) er en dansk matematiker og forsker i kryptografi , professor i matematik ved Danmarks Tekniske Universitet . Hans forskning omfatter design og analyse af blokcifre , hash-funktioner og meddelelsesgodkendelseskoder ( MAC'er ).

Knudsen er en af ​​grundlæggerne af kryptoanalysen af ​​umulige differentialer og integral kryptoanalyse . Lars er en af ​​udviklerne af Grøstl .

Biografi

Lars Knudsen blev født den 21. februar 1962 i Danmark . Hans karriere begyndte med adskillige tidlige job i banksektoren. Men i 1984 kom Lars ind på Aarhus Universitet .  Studerede matematik og datalogi efter råd fra sin vejleder Ivan Bjerre Damgard. Ifølge Lars var det takket være hans vejleder, at han valgte at studere differentiel kryptoanalyse.

I 1992 modtog han en kandidatgrad, og allerede i 1994  - en ph.d. [1] Fra 1997 til 2001 arbejdede han ved Universitetet i Bergen , Norge . Han blev to gange valgt til direktør for International Association for Cryptographic Research ( IACR ) fra januar 2001 til december 2003 og fra januar 2004 til december 2006 . Fra 2003 til 2010 var han associeret redaktør af Journal of Cryptology, det officielle tidsskrift for IACR. Han har talt ved IACR-konferencer og seminarer. Hans rapporter præsenteres på 7 videnskabelige konferencer. Knudsen er i dag professor og leder af Matematisk Institut på Danmarks Tekniske Universitet . Han leder en gruppe af kryptoanalytikere på universitetet og er en af ​​udviklerne af chiffere, kryptografiske protokoller IEEE efterforskning og sikkerhed. En af lederne af forskningscentret FICS (Foundations in Cryptology and Security).

Lars Knudsen deltog aktivt i konkurrencen om den nye AES kryptostandard . På den var han den eneste kryptoanalytiker, der repræsenterede to projekter på én gang DEAL (Norge, Canada) og Serpent (Storbritannien, Israel, Norge). Hændelsen med, at Knudsen optræder overalt som repræsentant for Norge, forklares med den ekstreme mobilitet hos den danske videnskabsmand, der allerede havde arbejdet i Frankrig , Schweiz og Belgien de sidste par år før konkurrencen . På tidspunktet for AES-konkurrencen underviste Lars i kryptologi ved Universitetet i Bergen , Norge.

Det er også kendt, at hans Erdős-nummer er 3.

Videnskabelig forskning

Lars Knudsen er kendt over hele verden for de berømte angreb på SAFER og SQUARE ciphers , hans arbejde med kryptoanalyse af umulige differentialer og integreret kryptoanalyse. Knudsen foreslog først brugen af ​​trunkerede differentialer til at angribe 6-rund DES . Senere blev denne metode også brugt til angreb på Skipjack og SAFER med et trunkeret antal runder. Lars designede også DEAL- og Serpent -cifrene (sidstnævnte sammen med englænderen Ross Anderson og israeleren Eli Biham ). En anden Knudsen-udvikling er Grøstl , en hash-funktion , en af ​​fem finalister i NIST SHA-3- konkurrencen .

Integral kryptoanalyse

Integral kryptoanalyse er en form for kryptoanalyse, der delvist kan anvendes til angreb på blokcifre baseret på substitutions-permutationsnetværk . Det blev formuleret af Lars Knudsen, mens han ledte efter et angreb på SQUARE -chifferet , hvorfor det ofte kaldes Square-angrebet i litteraturen. Metoden er blevet udvidet og anvendt på de kvadratlignende cifre CRYPTON , Rijndael og SHARK . Modifikationer af Square-angrebet er også blevet anvendt på chifferne Hierocrypt-L1 , IDEA , Camellia , Skipjack , MISTY1 , MISTY2 , SAFER ++, KHAZAD og FOX (nu kaldet IDEA NXT ).

Integral kryptoanalyse er baseret på princippet om at overveje et sæt åbne tekster, hvor den ene del forbliver konstant, og den anden varierer på alle mulige måder. For eksempel kan et angreb bruge et sæt af 256 klartekster, hvor alle på nær 8 bits er varierede. Det er klart, at XOR for dette sæt er nul. XOR af det tilsvarende sæt chiffertekster giver os information om driften af ​​krypteringsalgoritmen. Denne metode med at bruge et stort sæt almindelige tekster i stedet for et par, som i differentiel kryptoanalyse , har givet navnet "integral".

Krypteringsanalyse af umulige forskelle

Krypteringsanalyse af umulige differentialer er en type differentiel krypteringsanalyse , der anvendes til blokcifre . I almindelig differentiel kryptoanalyse betragtes en forskel med en vis endelig sandsynlighed, i kryptoanalysen af ​​umulige differentialer betragtes en forskel med en sandsynlighed på 0, det vil sige "umulig".

Denne teknik blev først beskrevet af Lars Knudsen i AES DEAL chifferapplikationen . Navnet på teknikken blev givet af Eli Biham , Alex Biryukov og Adi Shamir på CRYPTO'98-konferencen.

Denne metode har fundet bred anvendelse og er blevet brugt i angreb på IDEA , Khufu og Khafre , E2 , Serpent - varianter , MARS , Twofish , Rijndael , CRYPTON , Zodiac (cipher) , Hierocrypt-3 , TEA , XTEA , Mini- AES-cifre , ARIA , Camellia og SHACAL-2 .

Angreb på den SIKRERE cipher

SAFER K-64 er en iterativ blokchiffer. Algoritmen fungerer med en 64-bit blok og en 64-bit nøgle. Knudsen opdagede en svaghed i nøglefordelingen. Deres generation i algoritmen var slet ikke svær. Den første undernøgle er selve brugernøglen. Følgende undernøgler genereres af proceduren . <<<-operationen er et cyklisk venstreskift med 3 bit inden for hver byte af nøglen.

Konstanten fås ud fra formlen , hvor j er konstantens bytenummer . Svagheden ved denne algoritme var, at der for næsten hver nøgle er mindst én (nogle gange endda 9) andre nøgler, som, når vi krypterer en anden besked, giver os den samme chiffertekst, dvs. Knudsen fandt, at antallet af forskellige klartekster, der er krypteret med de samme chiffertekster, cirka er  en af ​​de mulige tekster. Som et resultat, ved hjælp af analysen fra til almindelig tekst, kan du finde 8 bit af den originale nøgle, bestående af 64 bit. Derefter blev denne algoritme forbedret af Knudsen selv til SAFER SK-64.

Der er en vittighed om, at SK står for Stop Knudsen, eller "Stop Knudsen" i oversættelse. Det viste sig på grund af det faktum, at den nye algoritme gjorde Knudsen-angrebet mislykket. Faktisk står SK for Strengthened Key Schedule, hvilket betyder Strengthened Key Schedule.

Angreb på SQUARE -chifferet

I 1997 udviklede Lars Knudsen sammen med sine kolleger Joan Daemen og Vincent Rijmen et angreb på blokchifferet SQUARE [ 2] .  Selve algoritmen bestod af 6 runder, inklusive 4 operationer, lineær strengtransformation , ikke-lineær byte-erstatning, transponering og addition med en nøgle. De valgte et matchet klartekstangreb . Hovedideen var at vælge tekstsæt. Det blev konstateret, at ud af 256 valgte klartekster er der to, der entydigt ville bestemme krypteringsnøglen med overvældende succes, hvis chifferen bestod af 4 runder. Derefter blev angrebet fortsat i 5 og 6 runder og gennemført med succes, selvom det var umuligt på grund af manglen på moderne teknologi. Hun blev dog anset for relevant, da hun blev anset som en af ​​de hurtigste.  

Bloker chiffer baseret hash funktion

I sin artikel "Hash-funktioner baseret på blokcifre og kvaternære koder" [3] ("Hashfunktioner baseret på blokcifre og kvaternære koder") viste Lars Knudsen, at udviklingen af ​​en effektiv hashfunktion med minimal indlejret hukommelse baseret på m − bitblokcifre er en vanskelig opgave. Desuden gav ingen af ​​de hash-funktioner, han anså, bedre beskyttelse end de 2^m opnået ved "brute force"-metoden. Ved at modificere modellen en smule (f.eks. ved at øge størrelsen af ​​den interne hukommelse, samt ved at indføre outputtransformationer), kan man opnå en komprimeringsfunktion og dermed en hashfunktion, som sikkerhed kan bevises ud fra de plausible antagelser, der er formuleret. af Knudsen. Metoden, han foreslog, var både den bedste i øjeblikket (nemlig en krypteringshastighed lig med eller 4 for hashing af én blok), og gav et højt sikkerhedsniveau eller højere effektivitet ved de samme sikkerhedsniveauer. For en stor værdi af indbygget hukommelse er hastighederne tæt på dem, der kan opnås. Derudover giver hash-funktionen en høj grad af parallelitet , hvilket vil give en endnu mere effektiv implementering.

RMAC undersøgelse

RMAC [4]  er et autentificeringssystem baseret på blokcifre. I øjeblikket er blokchifferalgoritmerne, der er godkendt til brug i RMAC, AES og triple- DES . I sit arbejde analyserede Knudsen dette system og fandt ud af, at skemaet tillader en vis kontrol over en af ​​de to nøgler i hovedblokchifferet at blive angrebet, og dette tillader flere link-nøgle angreb på RMAC. Han beskrev også et effektivt angreb på RMAC, når det blev brugt med triple - DES , og et generelt angreb på RMAC, der kan bruges til at finde en nøgle ud af to hurtigere end brute force. Hans angreb på RMAC-DES kræver maskinskrevne beskeder, hvilket er praktisk muligt med nutidens behandlingshastighed.

3gpp- MAC undersøgelse

I sit arbejde undersøgte Knudsen gendannelsesnøgleforfalskning og angreb på 3gpp - MAC [5] -godkendelsesskemaet foreslået i 3gpp-specifikationen. Han foreslog tre hovedklasser af angreb. Angrebene i første klasse bruger et stort antal "valgte MAC'er", i anden klasse bruger de et stort antal "kendte MAC'er", og i tredje klasse kræves et stort antal MAC-tjek, men meget få " kendte MAC'er" og kræver slet ikke "valgte MAC'er". Den første klasse giver både forfalskning og angreb på gendannelsesnøglen, mens den anden og tredje klasse kun giver angreb på nøglen. Der tages hensyn til både enkelt- og dobbeltnøgler. Spoofangrebet gælder for begge typer nøgler, mens gendannelsesnøgleangrebet kun gælder for den anden mulighed (to-nøgle).

Analyse af CRUSH hash-funktionen

Strukturen af ​​CRUSH [6] hash-funktionen er vist på figuren. En funktion består af en databuffer, en Bijection Selection Component af booleske funktioner og en bijektiv funktion B (en effektiv blokchiffer, hvis tekst er taget fra databufferen). Knudsen har vist, at CRUSH eller den mere generelle Iterated Halving-metode ikke opfylder kravene til gode hashfunktioner hverken ud fra et sikkerheds- eller ydeevnemæssigt synspunkt. Han viste, hvordan man genererer kollisioner og andre preimages for at bruge Iterated Halving. Muligheden for at skabe sådanne kollisioner er baseret på B-funktionen. Kompleksiteten af ​​disse angreb er ekstremt lille og udgør kun et dusin dekrypteringer af B-funktionen, uanset størrelse. Angrebene bruges, når der bruges en blokchiffer, inklusive AES med 192-bit nøgler og AES med 256-bit nøgler.

Mest berømte værker

• 1996  - Sammen med Bart Preneel foreslog han en måde at skabe hashfunktioner  baseret på blokcifre . I papiret demonstrerede Knudsen et nyt LOKIDBH- angreb , der brød den sidste underklasse af den brede klasse af effektive hash-funktioner, der tidligere blev foreslået i litteraturen.
• Han overvejede ikke-lineære tilnærmelser i lineær kryptoanalyse og opnåede en generalisering af Matsuis kryptoanalytiske metoder. Dette gjorde det muligt at opnå større fleksibilitet i kryptoangreb. Præstationer blev demonstreret på eksemplet med angrebet på LOKI91 .
• Studerede i detaljer SAFER -chifferet for stabilitet [7] . Udviklede et angreb, der førte til en væsentlig ændring af krypteringsalgoritmen og udseendet af SAFER -SK (som en joke dechifrerede Lars' venner SK som Stop Knudsen, selvom det i virkeligheden betyder Styrket nøgle-skema).
• 1997  - i artiklen "The Block Cipher Square" [8] foreslog et angreb på 128-bit SQUARE cipheren , som markerede begyndelsen på en ny gren af ​​kryptoanalysen - integreret kryptoanalyse. Udforskede IDEA -chifferet i detaljer med et reduceret antal runder. Udgivet et papir om svaghederne ved denne algoritme.
• 1998  - i udviklingsteamet ( Ross Anderson , Eli Biham ) foreslog en symmetrisk blokkrypteringsalgoritme Serpent [9] , som blev en af ​​finalisterne i anden fase af AES-konkurrencen. Udviklede DEAL [10] krypteringsalgoritmen baseret på DES .
• 1999  -ledet forskning i hurtig hardwarekryptering .
• 2000  - Sammen med Willi Meier offentliggjorde han en  detaljeret analyse af den næste AES -kandidat  - RC6 .
• 2001  - påbegyndte forskning inden for online-cifre og Hash-CBC- konstruktioner. Arbejdede på stabiliteten af ​​Skipjack- algoritmen .
• 2002  - præsenterede rapporten "Advances in cryptography" på EUROCRYPT 2002, og omhandlede også digitale signaturer og fejlkorrigerende koder. Undersøgte sikkerheden af ​​Feistel- cifre med seks runder eller mindre.
• 2003 - 2004  - forsket i 3gpp-MAC og RMAC , og talte også ved ESORICS og AES konferencer.
• 2005  - udgav konceptet for den kryptografiske hash-funktion SMASH , og udviklede også angreb på MD2 og RMAC .
• 2007  - udgav en detaljeret analyse af CRUSH hash-funktionen .
• 2009  - holdt en præsentation på EUROCRYPT om randomisering for at styrke sikkerheden for digitale signaturer, samt på CRYPTO med en rapport om C2 -krypteringsanalyse .

I alt udgav Lars Knudsen mere end 70 artikler om en meget bred vifte af emner såsom R-MAC- skema, SHA-1 og MD2 hashfunktioner , mange blokcifre - DES , DFC , IDEA , ICE , LOKI , MISTY1 , RC2 , RC5 , RC6 , SC2000 , Skipjack , SQUARE og SAFER . Han talte også på konferencer med rapporter om fejlkorrigerende koder . Deltaget i udvikling af robotnavigationssystemer.

Kolleger

Lars Knudsen er i dag leder af kryptografi-sektionen på Danmarks Tekniske Universitet. Fra maj 2014 omfatter denne arbejdsgruppe (Ph.D.):

• Andrey Bogdanov - Professor  ,
• Christian Rechberger - Professor  ,
• Elmar Tischhauser ( engelsk  Elmar Tischhauser ) - professor,

samt flere postdocs og kandidatstuderende.

Noter

1. ↑ Lars Knudsen. Block Cipher - Analyse, design og applikationer, Ph.D. Speciale, 1994  (engelsk)  : tidsskrift. - 1994. - 1. juli. Arkiveret fra originalen den 10. juli 2007.
2. ↑ Joan Daemen, Lars Knudsen og Vincent Rijmen. Blokcifret Square  (neopr.) . - 1997.  (utilgængeligt link)
3. ↑ Lars Knudsen og Bart Preneel. Hash-funktioner baseret på blokcifre og kvartære koder  (engelsk)  : journal. - 1996.  (utilgængeligt link)
4. ↑ Lars R. Knudsen og Tadayoshi Kohno. Analyse af RMAC  (ubestemt) . — 2007.  (utilgængeligt link)
5. ↑ Lars R. Knudsen og Chris J Mitchell. Analyse af 3gpp-MAC og to-nøgle 3gpp-MAC  (udefineret) . – 2003.
6. ↑ Matt Henricksen og Lars R. Knudsen. Krypteringsanalyse af CRUSH-hash-funktionen  (udefineret) . — 2007.  (utilgængeligt link)
7. ↑ Lars Knudsen. En nøgleskemasvaghed i SAFER K-64  .
8. ↑ Joan Daemen, Lars Knudsen, Vincent Rijmen. Block Cipher SQUARE  (neopr.) .  (utilgængeligt link)
9. ↑ Lars Knudsen, Eli Biham, Ross Anderson. Serpent: A New Block Cipher Proposal  (neopr.) .  (utilgængeligt link)
10. ↑ Lars Knudsen. TILBUD - En 128-bit  blokcifer (neopr.) . — Institut for Informatik, Universitetet i Bergen, Norge, 1998. — 21. februar ( bind Teknisk rapport nr. 151 ). Arkiveret fra originalen den 28. marts 2009. Arkiveret kopi (ikke tilgængeligt link) . Hentet 25. november 2009. Arkiveret fra originalen 28. marts 2009. (ubestemt) 

Litteratur

• Schneier B. Kapitel 14. Og flere blokcifre // Anvendt kryptografi. Protokoller, algoritmer, kildekode i C-sprog = Applied Cryptography. Protokoller, algoritmer og kildekode i C. - M. : Triumf, 2002. - S. 382-384. — 816 s. - 3000 eksemplarer.  - ISBN 5-89392-055-4 .
• Matt Henricksen og Lars R. Knudsen. Krypteringsanalyse af CRUSH-hash-funktionen  (udefineret) .
• Lars R. Knudsen og Tadayoshi Kohno. Analyse af RMAC  (ubestemt) . – 1991.
• Lars Knudsen og Bart Preneel . Hash-funktioner baseret på blokcifre og kvartære  koder .
• Lars Knudsen og Chris J Mitchell. Analyse af 3gpp-MAC og to-nøgle 3gpp-MAC  .
• Joan Daemen , Lars Knudsen og Vincent Rijmen . Blokcifret Square  (neopr.) .

Links

• Lars Knudsen Hjemmeside Arkiveret 6. marts 2010 på Wayback Machine 
• Publikationer af Lars Knudsen Arkiveret 9. december 2009 på Wayback Machine 
• Informationssikkerhedskursus, Institut for Radioteknik (MIPT)
• Konkurrence om en ny kryptostandard AES
• The Block Cipher Companion (informationssikkerhed og kryptografi  )
• Lars R. Knudsens  værk

I sociale netværk	Twitter
Tematiske steder	Google Scholar Matematisk genealogi ORCID
I bibliografiske kataloger BNF : 17049768p GND : 1089562632 ISNI : 0000 0001 1588 8709 J9U : 987007449537605171 LCCN : no2011119429 , n99044424 NKC : utb2012683425 NUKAT : n99014770 VIAF : 2330148753684941320005 WorldCat VIAF : 2330148753684941320005