Knudsen, Lars

Lars Ramkild Knudsen ( s. 21. helmikuuta 1962 ) on tanskalainen matemaatikko ja kryptografian tutkija , matematiikan professori Tanskan teknisessä yliopistossa . Hänen tutkimukseensa kuuluu lohkosalausten , hash-funktioiden ja viestien todennuskoodien ( MAC ) suunnittelu ja analysointi.

Knudsen on yksi mahdottomien differentiaalien kryptausanalyysin ja integraalisen kryptaanalyysin perustajista . Lars on yksi Grøstlin kehittäjistä .

Elämäkerta

Lars Knudsen syntyi 21. helmikuuta 1962 Tanskassa . Hänen uransa alkoi useista varhaisista työtehtävistä pankkialalla. Kuitenkin vuonna 1984 Lars tuli tanskalaiseen Århusin yliopistoon . Opiskeli matematiikkaa ja tietojenkäsittelytiedettä ohjaajansa Ivan Bjerre Damgardin ohjeiden mukaan. Larsin mukaan hänen ohjaajansa ansiosta hän päätti opiskella differentiaalista kryptoanalyysiä.  

Vuonna 1992 hän suoritti maisterin tutkinnon ja jo vuonna 1994  - tohtorin tutkinnon . [ 1 ] Vuodet 1997–2001 hän työskenteli Bergenin yliopistossa Norjassa . Hänet valittiin kahdesti kansainvälisen salaustutkimuksen liiton ( IACR ) johtajaksi tammikuusta 2001 joulukuuhun 2003 ja tammikuusta 2004 joulukuuhun 2006 . Vuodesta 2003 vuoteen 2010 hän oli IACR:n virallisen lehden Journal of Cryptology apulaistoimittaja. Hän on puhunut IACR:n konferensseissa ja seminaareissa. Hänen raporttejaan esitetään 7 tieteellisessä konferenssissa. Knudsen on tällä hetkellä professori ja matematiikan osaston johtaja Tanskan teknisessä yliopistossa . Hän johtaa yliopiston kryptanalyytikoiden ryhmää ja on yksi salakirjoituksen, salausprotokollien IEEE-rikosteknisten ja turvallisuuden kehittäjistä. Yksi tutkimuskeskuksen FICS (Foundations in Cryptology and Security) johtajista.

Lars Knudsen osallistui aktiivisesti kilpailuun uudesta AES -salausstandardista . Siinä hän oli ainoa kryptanalyytikko, joka edusti kahta projektia yhtä aikaa DEAL (Norja, Kanada) ja Serpent (Iso-Britannia, Israel, Norja). Tapaus siitä, että Knudsen esiintyy kaikkialla Norjan edustajana, selittyy tanskalaisen tiedemiehen äärimmäisellä liikkuvuudella, joka työskenteli jo Ranskassa , Sveitsissä ja Belgiassa viime vuosina ennen kilpailua . AES-kilpailun aikaan Lars opetti kryptologiaa Bergenin yliopistossa Norjassa.

Tiedetään myös, että hänen Erdős-numeronsa on 3.

Tieteellinen tutkimus

Lars Knudsen tunnetaan kaikkialla maailmassa kuuluisista SAFER- ja SQUARE -salauksia vastaan ​​tehdyistä hyökkäyksistä , mahdottomien erojen kryptausanalyysistä ja integraalisesta kryptausanalyysistä. Knudsen ehdotti ensin katkaistujen differentiaalien käyttöä 6-kierroksen DES :n hyökkäämiseen . Myöhemmin tätä menetelmää käytettiin myös hyökkäyksiin Skipjackia ja SAFERia vastaan ​​lyhennetyllä kierrosmäärällä. Myös Lars suunnitteli DEAL- ja Serpent -salaukset (jälkimmäinen yhdessä englantilaisen Ross Andersonin ja israelilaisen Eli Bihamin kanssa ). Toinen Knudsenin kehitystyö on Grøstl , hash-funktio , yksi viidestä NIST SHA-3 -kilpailun finalistista .

Integraalinen kryptausanalyysi

Integraalinen kryptausanalyysi on eräänlainen kryptausanalyysi, jota voidaan osittain soveltaa lohkosalauksiin kohdistuviin hyökkäyksiin, jotka perustuvat korvaus-permutaatioverkkoihin . Sen muotoili Lars Knudsen etsiessään hyökkäystä SQUARE -salausta vastaan , minkä vuoksi sitä kutsutaan usein kirjallisuudessa Square-hyökkäykseksi. Menetelmää on laajennettu ja sitä on sovellettu neliön kaltaisiin salakirjoihin CRYPTON , Rijndael ja SHARK . Square-hyökkäyksen modifikaatioita on sovellettu myös Hierocrypt-L1- , IDEA- , Camellia- , Skipjack- , MISTY1- , MISTY2- , SAFER ++-, KHAZAD- ja FOX-salauksiin (nykyisin IDEA NXT ).

Integraalinen kryptausanalyysi perustuu periaatteeseen, jossa otetaan huomioon joukko avoimia tekstejä, joissa yksi osa pysyy vakiona ja toinen vaihtelee kaikin mahdollisin tavoin. Esimerkiksi hyökkäys voisi käyttää 256 selvätekstin joukkoa, joissa kaikki paitsi 8 bittiä vaihtelevat. Ilmeisesti tämän joukon XOR on nolla. Vastaavan salatekstijoukon XOR antaa meille tietoa salausalgoritmin toiminnasta. Tämä menetelmä käyttää suurta joukkoa selkeitä tekstejä parin sijaan, kuten differentiaaliskriptianalyysissä , on antanut nimen "integraali".

Mahdottomien erojen krypta-analyysi

Mahdottomien differentiaalien krypta-analyysi on eräänlainen differentiaalinen kryptaanalyysi , jota sovelletaan lohkosalauksiin . Tavallisessa differentiaalisalausanalyysissä otetaan huomioon ero tietyllä äärellisellä todennäköisyydellä, mahdottomien differentiaalien kryptausanalyysissä eroa todennäköisyydellä 0, eli "mahdotonta".

Lars Knudsen kuvasi tämän tekniikan ensimmäisenä AES DEAL - salaussovelluksessa . Tekniikan nimen antoivat Eli Biham , Alex Biryukov ja Adi Shamir CRYPTO'98-konferenssissa.

Tämä menetelmä on löytänyt laajan sovelluksen ja sitä on käytetty hyökkäyksissä IDEA , Khufu ja Khafre , E2 , Serpent - lajikkeet , MARS , Twofish , Rijndael , CRYPTON , Zodiac (salaus) , Hierocrypt-3 , TEA , XTEA , Mini- AES-salaukset , ARIA , Camellia ja SHACAL-2 .

Hyökkäys SAFER-salaukseen

SAFER K-64 on iteratiivinen lohkosalaus. Algoritmi toimii 64-bittisellä lohkolla ja 64-bittisellä avaimella. Knudsen löysi heikkouden avainten jakelussa. Niiden luominen algoritmissa ei ollut ollenkaan vaikeaa. Ensimmäinen aliavain on itse käyttäjäavain. Proseduuri luo seuraavat aliavaimet . <<<-toiminto on syklinen siirto vasemmalle 3 bitin verran avaimen jokaisessa tavussa .

Vakio saadaan kaavasta , jossa j on vakion tavuluku . Tämän algoritmin heikkous oli se, että lähes jokaiselle avaimelle on olemassa ainakin yksi (joskus jopa 9) muuta avainta, joka salattaessa jotain muuta viestiä antaa meille saman salatekstin eli . Knudsen havaitsi, että samoilla salateksteillä salattujen eri selkeiden tekstien määrä on suunnilleen  yksi mahdollisista teksteistä. Tuloksena on, että käyttämällä analyysiä alkaen tekstiin , voit löytää 8 bittiä alkuperäisestä avaimesta, joka koostuu 64 bitistä. Sitten Knudsen itse paransi tämän algoritmin SAFER SK-64:ksi.

On vitsi, että SK tarkoittaa Stop Knudsen, tai "Stop Knudsen" käännöksessä. Ilmeisesti se johtui siitä, että uusi algoritmi teki Knudsenin hyökkäyksen epäonnistuneeksi. Itse asiassa SK on lyhenne sanoista Strenghened Key Schedule, mikä tarkoittaa vahvistettua avainaikataulua.

Hyökkäys SQUARE -salaukseen

Vuonna 1997 Lars Knudsen kehitti yhdessä kollegojensa Joan Daemenin ja Vincent Rijmenin kanssa hyökkäyksen lohkosalausta SQUARE vastaan ​​[ 2] .  Algoritmi itsessään koostui 6 kierrosta, mukaan lukien 4 operaatiota, lineaarinen merkkijonomuunnos , epälineaarinen tavukorvaus, transponointi ja lisääminen avaimella. He valitsivat vastaavan selkeän tekstin hyökkäyksen . Pääideana oli valita tekstisarjat. Havaittiin, että 256 valitusta selkeästä tekstistä kaksi määrittäisi salausavaimen yksiselitteisesti ylivoimaisella menestyksellä, jos salaus koostuisi 4 kierroksella. Sitten hyökkäystä jatkettiin 5 ja 6 kierrosta ja se saatiin onnistuneesti päätökseen, vaikka se oli mahdotonta nykytekniikan puutteen vuoksi. Häntä pidettiin kuitenkin merkityksellisenä, koska häntä pidettiin yhtenä nopeimmista.  

Estä salauspohjainen hash-funktio

Artikkelissaan "Hash-funktiot perustuvat lohkosalauksiin ja kvaternäärisiin koodeihin" [3] ("Hash-funktiot perustuvat lohkosalauksiin ja kvaternäärisiin koodeihin") Lars Knudsen osoitti, että tehokkaan hash-funktion kehittäminen minimaalisella sulautetulla muistilla perustuu m −. bittilohkon salaus on vaikea tehtävä. Lisäksi mikään hänen mielestään hajautusfunktioista ei tarjonnut parempaa suojaa kuin "raaka voima" -menetelmällä saatu 2^m. Mallia hieman muuttamalla (esimerkiksi lisäämällä sisäisen muistin kokoa sekä ottamalla käyttöön tulosmuunnoksia) saadaan pakkausfunktio ja siten hash-funktio , jonka turvallisuus voidaan todistaa laadittujen uskottavien oletusten perusteella. kirjoittanut Knudsen. Hänen ehdottama menetelmä oli sekä tällä hetkellä paras (eli salausnopeus, joka on yhtä suuri tai 4 yhden lohkon hajauttamiseen ), että tarjosi korkean turvallisuustason tai suuremman tehokkuuden samalla suojaustasolla. Suuren sisäänrakennetun muistin nopeudet ovat lähellä saavutettavia. Lisäksi hash-funktio tarjoaa suuren rinnakkaisuuden , mikä antaa vielä tehokkaamman toteutuksen.

RMAC- tutkimus

RMAC [4]  on lohkosalauksiin perustuva todennusjärjestelmä. Tällä hetkellä RMAC:ssa käytettäväksi hyväksytyt lohkosalausalgoritmit ovat AES ja triple- DES . Työssään Knudsen analysoi tätä järjestelmää ja havaitsi, että järjestelmä mahdollistaa jonkin hallinnan päälohkosalauksen kahdesta avaimesta, johon hyökätään, ja tämä mahdollistaa useiden linkkiavainhyökkäysten tekemisen RMAC:iin. Hän kuvaili myös tehokkaan hyökkäyksen RMAC:ia vastaan, kun sitä käytetään kolminkertaisen DES :n kanssa , ja yleisen hyökkäyksen RMAC:ia vastaan, jolla voidaan löytää yksi kahdesta avaimesta raakaa voimaa nopeammin. Hänen hyökkäyksensä RMAC-DES:ää vastaan ​​vaatii kirjoitettuja viestejä, mikä on käytännössä mahdollista nykypäivän käsittelynopeudella.

3gpp- MAC -tutkimus

Knudsen tutki työssään palautusavainten väärentämistä ja hyökkäystä 3gpp- MAC [5] -todennusjärjestelmää vastaan, jota ehdotettiin 3gpp-spesifikaatiossa. Hän ehdotti kolmea päähyökkäysluokkaa. Ensimmäisen luokan hyökkäykset käyttävät suurta määrää "valittuja MAC:itä", toisessa luokassa käytetään suurta määrää "tunnettuja MAC:eja", ja kolmannessa luokassa vaaditaan suuri määrä MAC-tarkistuksia, mutta hyvin vähän " tunnetut MAC:t" eivätkä vaadi "valittuja MAC:eja" ollenkaan. Ensimmäinen luokka tarjoaa sekä väärentämisen että hyökkäyksen palautusavaimeen, kun taas toinen ja kolmas luokka tarjoavat vain hyökkäyksen avaimeen. Sekä yksinäppäimet että kaksoisnäppäimet otetaan huomioon. Huijaushyökkäys koskee molempia avaimia, kun taas palautusavaimen hyökkäys koskee vain toista vaihtoehtoa (kaksi avainta).

CRUSH - hajautusfunktion analyysi

CRUSH [6] -tiivistefunktion rakenne on esitetty kuvassa. Funktio koostuu tietopuskurista, loogisten funktioiden Bijection Selection -komponentista ja bijektiivisestä funktiosta B (tehokas lohkosalaus, jonka teksti otetaan tietopuskurista). Knudsen on osoittanut, että CRUSH tai yleisempi Iterated Halving -menetelmä ei täytä hyvien hash-funktioiden vaatimuksia turvallisuuden tai suorituskyvyn näkökulmasta. Hän osoitti, kuinka luodaan törmäyksiä ja toisia esikuvia Iterated Halving -käyttöön. Mahdollisuus luoda tällaisia ​​törmäyksiä perustuu funktioon B. Näiden hyökkäysten monimutkaisuus on erittäin pieni ja vastaa vain tusinaa B-funktion salauksen purkamista koosta riippumatta. Hyökkäyksiä käytetään, kun käytetään mitä tahansa lohkosalausta, mukaan lukien AES 192-bittisillä avaimilla ja AES 256-bittisillä avaimilla.

Tunnetuimmat teokset

• 1996  – Hän ehdotti yhdessä Bart Preneelin kanssa tapaa luoda lohkosalauksiin perustuvia hash -  funktioita . Kirjoituksessa Knudsen esitteli uuden LOKIDBH- hyökkäyksen , joka rikkoi viimeisen alaluokan laajasta kirjallisuudessa aiemmin ehdotetuista tehokkaista hash-funktioista.
• Hän tarkasteli ei-lineaarisia approksimaatioita lineaarisessa kryptausanalyysissä ja sai yleistyksen Matsuin kryptanalyyttisistä menetelmistä. Tämä mahdollisti suuremman joustavuuden kryptohyökkäyksissä. Saavutukset esiteltiin LOKI91 -hyökkäyksen esimerkissä .
• Tutkittu yksityiskohtaisesti SAFER - salausta vakautta varten [7] . Kehittänyt hyökkäyksen, joka johti salausalgoritmin merkittävään muutokseen ja SAFER -SK:n ilmestymiseen (vitsinä Larsin ystävät tulkitsivat SK:n nimellä Stop Knudsen, vaikka todellisuudessa se tarkoittaa vahvistetun avaimen aikataulua).
• 1997  - artikkelissa "The Block Cipher Square" [8] ehdotti hyökkäystä 128-bittistä SQUARE -salausta vastaan, mikä merkitsi uuden kryptausanalyysin - integraalisen kryptaanalyysin - alkua. Tutki IDEA - salausta yksityiskohtaisesti pienemmällä määrällä kierroksia. Julkaisi artikkelin tämän algoritmin heikkouksista.
• 1998  - kehitystiimissä ( Ross Anderson , Eli Biham ) ehdotti symmetristä lohkosalausalgoritmia Serpent [9] , josta tuli yksi AES-kilpailun toisen vaiheen finalisteista. Kehittänyt DES :ään perustuvan DEAL [10] -salausalgoritmin .
• Vuonna 1999  johtama tutkimus nopeasta laitteistosalauksesta .
• 2000  – Hän julkaisi yhdessä Willi Meierin kanssa  yksityiskohtaisen analyysin seuraavasta AES -ehdokas  - RC6 :sta .
• 2001  - aloitti tutkimuksen online-salausten ja Hash-CBC- rakenteiden alalla. Työskenteli Skipjack -algoritmin vakauden parissa .
• 2002  - esitti raportin "Advances in cryptography" EUROCRYPT 2002 -tapahtumassa ja käsitteli myös digitaalisia allekirjoituksia ja virheenkorjauskoodeja. Tutkii Feistelin salakirjoituksen turvallisuutta kuudella tai pienemmällä kierroksella.
• 2003 - 2004  - tutki 3gpp-MAC :tä ja RMAC :ia sekä puhui myös ESORICS- ja AES-konferensseissa.
• 2005  - julkaisi konseptin kryptografisesta hash-funktiosta SMASH ja kehitti myös hyökkäyksiä MD2 :ta ja RMAC :ia vastaan .
• 2007  - julkaisi yksityiskohtaisen analyysin CRUSH -hajautusfunktiosta .
• 2009  - piti esitelmän EUROCRYPT -tapahtumassa satunnaistamisesta digitaalisten allekirjoitusten turvallisuuden vahvistamiseksi sekä CRYPTOssa [ raportin C2 -kryptausanalyysistä .

Kaiken kaikkiaan Lars Knudsen julkaisi yli 70 artikkelia erittäin laajasta valikoimasta aiheita, kuten R-MAC- skeema, SHA-1 ja MD2 hash-funktiot , monet lohkosalaukset - DES , DFC , IDEA , ICE , LOKI , MISTY1 , RC2 , RC5 , RC6 , SC2000 , Skipjack , SQUARE ja TURVALLISempi . Hän puhui myös konferensseissa, joissa oli raportteja virheenkorjauskoodeista . Osallistunut robottinavigointijärjestelmien kehittämiseen.

Kollegat

Lars Knudsen on tällä hetkellä Tanskan teknisen yliopiston salausosaston päällikkö. Toukokuusta 2014 lähtien tähän työryhmään kuuluu (tohtori):

• Andrey Bogdanov - Professori  ,
• Christian Rechberger - Professori  ,
• Elmar Tischhauser ( englanniksi  Elmar Tischhauser ) - professori,

sekä useita jatko-opiskelijoita ja jatko-opiskelijoita.

Muistiinpanot

1. ↑ Lars Knudsen. Block Cipher - analyysi, suunnittelu ja sovellukset, Ph.D. Thesis, 1994  (englanniksi)  : lehti. - 1994 - 1. heinäkuuta. Arkistoitu alkuperäisestä 10. heinäkuuta 2007.
2. ↑ Joan Daemen, Lars Knudsen ja Vincent Rijmen. Lohkosalauksen neliö  (neopr.) . - 1997.  (linkki ei saavutettavissa)
3. ↑ Lars Knudsen ja Bart Preneel. Hash-funktiot, jotka perustuvat lohkosalauksiin ja kvaternaarisiin koodeihin  (englanniksi)  : päiväkirja. - 1996.  (linkki ei käytettävissä)
4. ↑ Lars R. Knudsen ja Tadayoshi Kohno. RMAC-analyysi  (määrittämätön) . — 2007.  (linkki ei käytettävissä)
5. ↑ Lars R. Knudsen ja Chris J Mitchell. 3gpp-MAC:n ja kahden näppäimen 3gpp-MAC:n analyysi  (määrittämätön) . – 2003.
6. ↑ Matt Henricksen ja Lars R. Knudsen. CRUSH-hajautusfunktion krypta-analyysi  (määrittämätön) . — 2007.  (linkki ei käytettävissä)
7. ↑ Lars Knudsen. Avainaikataulun heikkous SAFER K-64:  ssä .
8. ↑ Joan Daemen, Lars Knudsen, Vincent Rijmen. Block Cipher SQUARE  (uuspr.) .  (linkki ei saatavilla)
9. ↑ Lars Knudsen, Eli Biham, Ross Anderson. Serpent: A New Block Cipher Proposal  (uuspr.) .  (linkki ei saatavilla)
10. ↑ Lars Knudsen. TARJOUS - 128-bittinen  lohkosalaus (uus.) . — Informatiikan laitos, Bergenin yliopisto, Norja, 1998. — 21. helmikuuta ( tekninen raportti nro 151 ). Arkistoitu alkuperäisestä 28. maaliskuuta 2009. Arkistoitu kopio (linkki ei saatavilla) . Haettu 25. marraskuuta 2009. Arkistoitu alkuperäisestä 28. maaliskuuta 2009. (määrätön) 

Kirjallisuus

• Schneier B. Luku 14. Ja lisää lohkosalauksia // Applied Cryptography. Protokollat, algoritmit, lähdekoodi C-kielellä = Applied Cryptography. Protokollat, algoritmit ja lähdekoodit julkaisussa C. - M . : Triumf, 2002. - S. 382-384. — 816 s. - 3000 kappaletta.  - ISBN 5-89392-055-4 .
• Matt Henricksen ja Lars R. Knudsen. CRUSH-hajautusfunktion krypta-analyysi  (määrittämätön) .
• Lars R. Knudsen ja Tadayoshi Kohno. RMAC-analyysi  (määrittämätön) . – 1991.
• Lars Knudsen ja Bart Preneel . Hash-funktiot perustuvat lohkosalauksiin ja kvaternaarisiin  koodeihin .
• Lars Knudsen ja Chris J Mitchell. 3gpp - MAC:n ja kaksinäppäimen 3gpp-MAC  :n analyysi .
• Joan Daemen , Lars Knudsen ja Vincent Rijmen . Lohkosalauksen neliö  (neopr.) .

Linkit

• Lars Knudsenin kotisivu Arkistoitu 6. maaliskuuta 2010 Wayback Machinessa 
• Lars Knudsenin julkaisut Arkistoitu 9. joulukuuta 2009 Wayback Machinessa 
• Tietoturvakurssi, Radiotekniikan laitos (MIPT)
• Kilpailu uudesta kryptostandardista AES
• The Block Cipher Companion (tietoturva ja kryptografia  )
• Lars R. Knudsenin  työ

Sosiaalisissa verkostoissa	Viserrys
Temaattiset sivustot	Google tutkija Matemaattinen sukututkimus ORCID
Bibliografisissa luetteloissa BNF : 17049768p GND : 1089562632 ISNI : 0000 0001 1588 8709 J9U : 987007449537605171 LCCN : no2011119429 , n99044424 NKC : utb2012683425 NUKAT : n99014770 VIAF : 2330148753684941320005 WorldCat VIAF : 2330148753684941320005