Knudsen, Lars

Lars Ramkild Knudsen
Datum narození 21. února 1962 (ve věku 60 let)( 1962-02-21 )
Země
Vědecká sféra matematika , kryptografie , teorie informace
Místo výkonu práce Dánská technická univerzita
Alma mater Aarhuská univerzita
vědecký poradce Ivan Damgord [d]
Známý jako autor mnoha kryptoútoků, vývojář šifer SAFER a SQUARE , jeden ze zakladatelů integrální kryptoanalýzy a kryptoanalýzy nemožných diferenciálů
Ocenění a ceny Člen IACR [d] ( 2013 )
webová stránka www2.mat.dtu.dk/people/L…
dtu.dk/service/telefonbo…
orbit.dtu.dk/en/persons/…
 Mediální soubory na Wikimedia Commons

Lars Ramkild Knudsen ( narozen 21. února 1962 ) je dánský matematik a výzkumník v kryptografii , profesor matematiky na Technické univerzitě v Dánsku . Jeho výzkum zahrnuje návrh a analýzu blokových šifer , hashovacích funkcí a ověřovacích kódů zpráv ( MAC ).

Knudsen je jedním ze zakladatelů kryptoanalýzy nemožných diferenciálů a integrální kryptoanalýzy . Lars je jedním z vývojářů Grøstlu .

Životopis

Lars Knudsen se narodil 21. února 1962 v Dánsku . Jeho kariéra začala několika ranými zaměstnáními v bankovnictví. Nicméně, v roce 1984 Lars vstoupil na dánskou Aarhus University .  Na radu svého nadřízeného Ivana Bjerre Damgarda vystudoval matematiku a informatiku. Podle Larse to bylo díky svému nadřízenému, že se rozhodl studovat diferenciální kryptoanalýzu.

V roce 1992 získal magisterský titul a již v roce 1994  - Ph.D. [1] V letech 1997 až 2001 působil na univerzitě v Bergenu v Norsku . Od ledna 2001 do prosince 2003 a od ledna 2004 do prosince 2006 byl dvakrát zvolen ředitelem Mezinárodní asociace pro kryptografický výzkum ( IACR ) . V letech 2003 až 2010 byl přidruženým redaktorem Journal of Cryptology, oficiálního časopisu IACR. Vystupoval na konferencích a seminářích IACR. Jeho zprávy jsou prezentovány na 7 vědeckých konferencích. Knudsen je v současnosti profesorem a vedoucím katedry matematiky na Technické univerzitě v Dánsku . Vede skupinu kryptoanalytiků univerzity a je jedním z vývojářů šifer, kryptografických protokolů IEEE forenzní a bezpečnosti. Jeden z vedoucích výzkumného centra FICS (Foundations in Cryptology and Security).

Lars Knudsen se aktivně zúčastnil soutěže o nový krypto standard AES . Na něm byl jediným kryptoanalytikem, který zastupoval dva projekty najednou DEAL (Norsko, Kanada) a Serpent (Velká Británie, Izrael, Norsko). Incident s tím, že se Knudsen všude objevuje jako zástupce Norska, vysvětluje extrémní mobilita dánského vědce, který v posledních letech před soutěží již působil ve Francii , Švýcarsku a Belgii . V době soutěže AES Lars vyučoval kryptologii na univerzitě v Bergenu v Norsku.

Je také známo, že jeho Erdősovo číslo je 3.

Vědecký výzkum

Lars Knudsen je po celém světě známý svými slavnými útoky na šifry SAFER a SQUARE , jeho prací na kryptoanalýze nemožných diferenciálů a integrální kryptoanalýze. Knudsen nejprve navrhl použití zkrácených diferenciálů k útoku na 6-kolové DES . Později byla tato metoda použita také pro útoky na Skipjacka a SAFER se zkráceným počtem kol. Lars také navrhl šifry DEAL a Serpent (poslední jmenovaný spolu s Angličanem Rossem Andersonem a Izraelcem Eli Bihamem ). Dalším Knudsenovým vývojem je Grøstl , hashovací funkce , jeden z pěti finalistů soutěže NIST SHA-3 .

Integrální kryptoanalýza

Integrální kryptoanalýza je typ kryptoanalýzy částečně použitelný pro útoky na blokové šifry založené na substitučně-permutačních sítích . Byl formulován Larsem Knudsenem, když hledal útok na SQUARE šifru , a proto je v literatuře často nazýván čtvercovým útokem. Metoda byla rozšířena a aplikována na čtvercové šifry CRYPTON , Rijndael a SHARK . Úpravy útoku Square byly také aplikovány na šifry Hierocrypt-L1 , IDEA , Camellia , Skipjack , MISTY1 , MISTY2 , SAFER ++, KHAZAD a FOX (nyní nazývané IDEA NXT ).

Integrální kryptoanalýza je založena na principu uvažování množiny otevřených textů, ve kterých jedna část zůstává konstantní a druhá se všemi možnými způsoby mění. Například útok by mohl použít sadu 256 otevřených textů, ve kterých jsou všechny kromě 8 bitů různé. Je zřejmé, že XOR této sady je nula. XOR odpovídající množiny šifrových textů nám poskytuje informace o fungování šifrovacího algoritmu. Tato metoda použití velkého souboru holého textu místo páru, jak v diferenciální kryptoanalýze , dal jméno “integrální”.

Kryptoanalýza nemožných diferenciálů

Kryptoanalýza nemožných rozdílů je druh diferenciální kryptoanalýzy aplikovaný na blokové šifry . V běžné diferenciální kryptoanalýze se uvažuje rozdíl s určitou konečnou pravděpodobností, v kryptoanalýze nemožných diferenciálů se uvažuje o rozdílu s pravděpodobností 0, tedy „nemožné“.

Tuto techniku ​​poprvé popsal Lars Knudsen v aplikaci šifry AES DEAL . Jméno této techniky dali Eli Biham , Alex Biryukov a Adi Shamir na konferenci CRYPTO'98.

Tato metoda našla široké uplatnění a byla použita při útocích na IDEA , Khufu a Khafre , E2 , Serpent variety , MARS , Twofish , Rijndael , CRYPTON , Zodiac (cipher) , Hierocrypt-3 , TEA , XTEA , Mini- Šifry AES , ARIA , Camellia a SHACAL-2 .

Útok na BEZPEČNĚJŠÍ šifru

SAFER K-64 je iterativní bloková šifra. Algoritmus pracuje s 64bitovým blokem a 64bitovým klíčem. Knudsen objevil slabinu v distribuci klíčů. Jejich generování v algoritmu nebylo vůbec těžké. První podklíč je samotný uživatelský klíč. Následující podklíče jsou generovány postupem . Operace <<< je cyklický posun doleva o 3 bity v každém bajtu klíče.

Konstanta se získá ze vzorce , kde j je číslo bytu konstanty . Slabinou tohoto algoritmu bylo, že téměř pro každý klíč existuje alespoň jeden (někdy i 9) dalších klíčů, což nám při zašifrování nějaké jiné zprávy dává stejný šifrovaný text, tedy . Knudsen zjistil, že počet různých otevřených textů, které jsou zašifrovány stejnými šifrovými texty, je přibližně  jedním z možných textů. Výsledkem je, že pomocí analýzy od do prostého textu můžete najít 8 bitů původního klíče, který se skládá z 64 bitů. Poté byl tento algoritmus vylepšen samotným Knudsenem na SAFER SK-64.

Existuje vtip, že SK znamená Stop Knudsen, nebo v překladu „Stop Knudsen“. Ukázalo se to kvůli tomu, že nový algoritmus způsobil neúspěšný Knudsenův útok. Ve skutečnosti SK znamená Strengthened Key Schedule, což znamená Posílený klíčový plán.

Útok na šifru SQUARE

V roce 1997 Lars Knudsen společně se svými kolegy Joan Daemen a Vincent Rijmen vyvinul útok na blokovou šifru SQUARE [ 2] .  Samotný algoritmus sestával ze 6 kol, včetně 4 operací, lineární transformace řetězců , nelineární náhrady bajtů, transpozice a sčítání pomocí klíče. Zvolili odpovídající útok v otevřeném textu . Hlavní myšlenkou byl výběr textových sad. Bylo zjištěno, že z 256 vybraných otevřených textů jsou dva, které by jednoznačně určily šifrovací klíč s ohromným úspěchem, pokud by se šifra skládala ze 4 kol. Poté útok pokračoval 5 a 6 kol a byl úspěšně dokončen, i když to bylo nemožné kvůli nedostatku moderní techniky. Byla však považována za relevantní, protože byla považována za jednu z nejrychlejších.  

Hašovací funkce založená na blokové šifre

Lars Knudsen ve svém článku "Hashovací funkce založené na blokových šifrách a kvartérních kódech" [3] ("Hashovací funkce založené na blokových šifrách a kvartérních kódech") ukázal, že vývoj efektivní hašovací funkce s minimální vestavěnou pamětí založenou na m − bitová bloková šifra je obtížný úkol. Navíc žádná z hašovacích funkcí, které považoval za neposkytla lepší ochranu než 2^m získané metodou „hrubé síly“. Mírnou úpravou modelu (například zvětšením velikosti vnitřní paměti a také zavedením výstupních transformací) lze získat kompresní funkci a tedy hashovací funkci , pro kterou lze prokázat bezpečnost na základě formulovaných věrohodných předpokladů. od Knudsen. Metoda, kterou navrhl, byla v tuto chvíli nejlepší (jmenovitě rychlost šifrování rovná nebo 4 pro hashování jednoho bloku) a poskytovala vysokou úroveň zabezpečení nebo vyšší účinnost při stejných úrovních zabezpečení. Pro velkou hodnotu vestavěné paměti se rychlosti blíží těm, které lze získat. Navíc hashovací funkce poskytuje vysoký stupeň paralelismu , což poskytne ještě efektivnější implementaci.

Studie RMAC

RMAC [4]  je autentizační systém založený na blokových šifrách. V současné době jsou algoritmy blokové šifry schválené pro použití v RMAC AES a triple- DES . Ve své práci Knudsen analyzoval tento systém a zjistil, že schéma umožňuje určitou kontrolu nad jedním ze dvou klíčů hlavní blokové šifry, které mají být napadeny, a to umožňuje provést několik útoků pomocí spojovacího klíče na RMAC. Popsal také účinný útok na RMAC při použití s ​​trojitým DES a obecný útok na RMAC, který lze použít k nalezení jednoho klíče ze dvou rychleji než hrubou silou. Jeho útok na RMAC-DES vyžaduje psané zprávy, což je při dnešní rychlosti zpracování prakticky možné.

3gpp- Studie MAC

Ve své práci Knudsen zkoumal falšování obnovovacího klíče a útok na autentizační schéma 3gpp- MAC [5] navržené ve specifikaci 3gpp. Navrhl tři hlavní třídy útoků. Útoky v první třídě používají velké množství "vybraných MAC", ve druhé třídě používají velké množství "známých MAC" a ve třetí třídě je vyžadováno velké množství kontrol MAC, ale velmi málo " známé MAC“ a „vybrané MAC“ vůbec nevyžadují. První třída poskytuje jak falzifikaci, tak útok na klíč pro obnovení, zatímco druhá a třetí třída poskytuje pouze útok na klíč. Berou se v úvahu jak jednoklíčové, tak dvouklíčové. Útok spoof se týká obou typů klíčů, zatímco útok pomocí klíče obnovy se týká pouze druhé možnosti (dvouklíčové).

Analýza hashovací funkce CRUSH

Struktura hashovací funkce CRUSH [6] je znázorněna na obrázku. Funkce se skládá z datové vyrovnávací paměti, Bijekční výběrové komponenty booleovských funkcí a bijektivní funkce B (účinná bloková šifra, jejíž text je převzat z datové vyrovnávací paměti). Knudsen ukázal, že CRUSH nebo obecnější metoda Iterated Halving nesplňuje požadavky na dobré hashovací funkce ani z hlediska bezpečnosti, ani z hlediska výkonu. Ukázal, jak generovat kolize a druhé předobrazy pro použití Iterated Halving. Schopnost vytvářet takové kolize je založena na funkci B. Složitost těchto útoků je extrémně malá a představuje pouze tucet dešifrování funkce B bez ohledu na velikost. Útoky se používají při použití jakékoli blokové šifry, včetně AES se 192bitovými klíči a AES s 256bitovými klíči.

Nejslavnější díla

Dohromady Lars Knudsen publikoval více než 70 prací na velmi širokou škálu témat, jako je schéma R-MAC , hashovací funkce SHA-1 a MD2 , mnoho blokových šifer - DES , DFC , IDEA , ICE , LOKI , MISTY1 , RC2 , RC5 , RC6 , SC2000 , Skipjack , SQUARE a SAFER . Vystoupil také na konferencích se zprávami o kódech pro opravu chyb . Podílel se na vývoji robotických navigačních systémů.

Kolegové

Lars Knudsen je v současnosti vedoucím sekce kryptografie na Dánské technické univerzitě. Od května 2014 tato pracovní skupina zahrnuje (Ph.D.):

stejně jako několik postdoktorandů a postgraduálních studentů.

Poznámky

  1. ↑ Lars Knudsen. Bloková šifra - analýza, návrh a aplikace, Ph.D. Thesis, 1994  (anglicky)  : journal. - 1994. - 1. července. Archivováno z originálu 10. července 2007.
  2. ↑ Joan Daemen, Lars Knudsen a Vincent Rijmen. Bloková šifra Square  (neopr.) . - 1997.  (nepřístupný odkaz)
  3. ↑ Lars Knudsen a Bart Preneel. Hashovací funkce založené na blokových šifrách a kvartérních kódech  (anglicky)  : journal. - 1996.  (nepřístupný odkaz)
  4. ↑ Lars R. Knudsen a Tadayoshi Kohno. Analýza RMAC  (neurčitá) . — 2007.  (nedostupný odkaz)
  5. ↑ Lars R. Knudsen a Chris J Mitchell. Analýza 3gpp-MAC a dvouklíčového 3gpp-MAC  (nedefinováno) . — 2003.
  6. ↑ Matt Henricksen a Lars R. Knudsen. Kryptoanalýza hashovací funkce CRUSH  (nedefinováno) . — 2007.  (nedostupný odkaz)
  7. ↑ Lars Knudsen. Slabost klíčového plánu v SAFER K-  64 .
  8. ↑ Joan Daemen, Lars Knudsen, Vincent Rijmen. The Block Cipher SQUARE  (neopr.) .  (nedostupný odkaz)
  9. ↑ Lars Knudsen, Eli Biham, Ross Anderson. Had: Návrh nové blokové šifry  (neopr.) .  (nedostupný odkaz)
  10. ↑ Lars Knudsen. DEAL - 128bitová bloková šifra  (neopr.) . — Katedra informatiky, University of Bergen, Norsko, 1998. — 21. února ( sv. Technická zpráva č. 151 ). Archivováno z originálu 28. března 2009. Archivovaná kopie (nedostupný odkaz) . Získáno 25. listopadu 2009. Archivováno z originálu 28. března 2009. 

Literatura

Odkazy

  Přejděte na položku Wikidata  V sociálních sítích
Tematické stránky