XSL attack
Főnév
XSL attack (tsz. XSL attacks)
A kriptográfiában az eXtended Sparse Linearization (XSL) támadás a blokkrejtjelek kriptoanalízisének egyik módszere . A támadást először 2002-ben publikálták Nicolas Courtois és Josef Pieprzyk kutatók . Ez némi vitát váltott ki, mivel azt állították, hogy gyorsabban feltörheti az Advanced Encryption Standard (AES) titkosítást , más néven Rijndael-t , mint egy kimerítő keresés . Mivel az AES-t már széles körben használják a kereskedelemben és a kormányzatban titkos információk továbbítására, egy olyan technika megtalálása, amely lerövidítheti a titkos üzenet lekéréséhez szükséges időt a kulcs birtokában, széles körű következményekkel járhat.
A módszernek magas a munkatényezője, ami, hacsak nem csökkentik, azt jelenti, hogy a technika nem csökkenti az AES megszakítására irányuló erőfeszítést a kimerítő kereséshez képest. Ezért a közeljövőben nem befolyásolja a blokk titkosítások valós biztonságát. Ennek ellenére a támadás néhány szakértőt nagyobb nyugtalanságra adott a jelenlegi AES algebrai egyszerűsége miatt.
Összefoglalva, az XSL-támadás először egy rejtjel belső elemeinek elemzésén és másodfokú szimultán egyenletek származtatásán alapul . Ezek az egyenletrendszerek jellemzően nagyon nagyok, például 8000 egyenlet 1600 változóval a 128 bites AES-hez. Az ilyen rendszerek megoldására számos módszer ismert. Az XSL-támadás során az eXtended Sparse Linearization nevű speciális algoritmust alkalmazzák ezen egyenletek megoldására és a kulcs helyreállítására .
A támadás figyelemre méltó, hogy csak néhány ismert egyszerű szövegre van szükség a végrehajtásához; A korábbi kriptográfiai módszerek, mint például a lineáris és a differenciális kriptoanalízis , gyakran irreálisan sok ismert vagy kiválasztott nyílt szöveget igényelnek .
Többváltozós másodfokú egyenletek megoldása A többváltozós másodfokú egyenletek (MQ) megoldása egy véges számhalmaz felett NP-nehéz probléma (általános esetben) a kriptográfiában számos alkalmazással. Az XSL támadás hatékony algoritmust igényel az MQ leküzdésére. 1999-ben Kipnis és Shamir kimutatta, hogy egy adott nyilvános kulcsú algoritmus , az úgynevezett Hidden Field Equations séma (HFE), redukálható egy túldefiniált másodfokú egyenletrendszerré (több egyenlet, mint ismeretlen). Az ilyen rendszerek megoldásának egyik módszere a linearizálás , amely magában foglalja az egyes másodfokú tagok független változókkal való helyettesítését, és az eredményül kapott lineáris rendszer megoldását egy algoritmus, például a Gauss-elimináció segítségével . A sikerhez a linearizáláshoz elegendő lineárisan független egyenletre van szükség (körülbelül annyi, ahány tag). A HFE kriptoanalíziséhez azonban túl kevés egyenlet volt, ezért Kipnis és Shamir az újralinearizálást javasolta , egy olyan technikát, ahol a linearizálás után extra nemlineáris egyenleteket adnak hozzá, és az eredményül kapott rendszert a linearizálás második alkalmazásával oldják meg. Az újralinearizálás elég általánosnak bizonyult ahhoz, hogy más sémákra is alkalmazható legyen.
2000-ben Courtois et al. egy továbbfejlesztett algoritmust javasolt az MQ-hoz, XL néven (for eXtended Linearization ), amely növeli az egyenletek számát azáltal, hogy megszorozza őket egy bizonyos fokú monomimmal . A bonyolultsági becslések azt mutatták, hogy az XL támadás nem működik a blokk titkosításokból, például az AES-ből származó egyenletekkel szemben. Az előállított egyenletrendszerek azonban sajátos felépítésűek voltak, és az XSL algoritmust az XL finomításaként fejlesztették ki, amely ki tudta használni ezt a struktúrát. Az XSL-ben az egyenleteket csak gondosan kiválasztott monomokkal szorozzák meg, és számos változatot javasoltak.
Az XL és származékos algoritmusai hatékonyságának kutatása továbbra is folyamatban van (Yang és Chen, 2004).
- XSL attack - Szótár.net (en-hu)
- XSL attack - Sztaki (en-hu)
- XSL attack - Merriam–Webster
- XSL attack - Cambridge
- XSL attack - WordNet
- XSL attack - Яндекс (en-ru)
- XSL attack - Google (en-hu)
- XSL attack - Wikidata
- XSL attack - Wikipédia (angol)