Side-Channel Attacks in Digital Forensics
No Thumbnail Available
Journal Title
Journal ISSN
Volume Title
Perustieteiden korkeakoulu |
Master's thesis
Author
Date
2024-06-18
Department
Major/Subject
Mathematics
Mcode
SCI3054
Degree programme
Master’s Programme in Mathematics and Operations Research
Language
en
Pages
72+17
Series
Abstract
Side-channel attacks target the physical implementation of a cryptosystem, exploiting information leaked by the execution of an algorithm. Side-channels arise from variations in timing, power consumption, electromagnetic emanations, and other measurable properties that correlate with the secret data being processed. Side-channel attacks present a viable technique for digital forensics, as cryptography becomes more common in electronic devices. Bleichenbacher's fast Fourier transform-based solution to the hidden number problem is a powerful attack against the Elliptic Curve Digital Signature Algorithm (ECDSA). The attack assumes that a few bits of a secret nonce, a random one-time value used by the signature generation algorithm, can be recovered through side-channel analysis or other methods. The attack can recover the entire secret signing key from even a single bit of leakage over a large number of signatures. This thesis presents side-channel attacks in the three primary physical domains: timing, power consumption, and electromagnetic emanations. Then, we present a thorough mathematical analysis of Bleichenbacher's attack to demonstrate how methods from algebra and other areas of mathematics can be applied to perform sophisticated key-recovery attacks. The crucial range reduction phase of Bleichenbacher's attack involves finding sparse linear combinations of linear congruences Ki = Ci d + Hi (mod n) such that the Ci are minimized. We prove that the upper bound for the Ci can be relaxed by a factor of 8/5 compared to previous works. This reduces the requirements for range reduction, the most demanding part of the attack. We demonstrated Bleichenbacher's attack using the relaxed bound in practice against a 192-bit ECDSA target implementation. We recovered 4 bits of the secret nonces using a Gaussian classifier, commonly known as a template attack, trained with a known signing key. We recovered the entire signing key from the 4-bit leak using 9,425 classified signatures out of a total of 27,000 signatures. The number of signatures is feasible to obtain in many practical scenarios.Sivukanavahyökkäykset hyödyntävät salausjärjestelmien fyysisestä toteutuksesta vuotavaa informaatiota. Sivukanavat ilmenevät salausoperaatioihin kuluvan ajan, virrankulutuksen sekä sähkö- ja magneettikentän muutoksina, jotka ovat yhteydessä laitteen käsittelemään salaiseen informaatioon. Sivukanavahyökkäykset tarjoavat digitaaliselle forensiikalle ratkaisuja salausjärjestelmien yleistymisen aiheuttamiin haasteisiin. Bleichenbacherin ratkaisu piilevän numeron ongelmaan (engl., hidden number problem) on tehokas hyökkäys elliptisten käyrien allekirjoitusalgoritmia (ECDSA) vastaan. Hyökkäys edellyttää, että osa allekirjoitusalgoritmin käyttämän kertakäyttöisen satunnaisluvun biteistä saadaan selville sivukanavahyökkäyksellä tai muulla menetelmällä. Hyökkäyksen avulla koko allekirjoitusavain on mahdollista ratkaista jopa yhden bitin vuodosta, jos hyökkäys toteutetaan riittävän monen allekirjoitusoperaation yli. Tässä työssä kuvataan, miten ajoitus-, virrankulutus- ja sähkömagneettiset sivukanavat syntyvät ja miten sivukanavahyökkäyksiä voidaan toteuttaa käytännössä. Esitän myös aiempaa laajemman matemaattisen analyysin Bleichenbacherin hyökkäyksestä osoittaakseni, miten algebran ja muiden matematiikan osa-alueiden menetelmiä voidaan hyödyntää edistyneissä sivukanavahyökkäyksissä. Bleichenbacherin hyökkäyksen kriittisessä redusointivaiheessa (engl., range reduction) etsitään kongruensseista Ki = Ci d + Hi (mod n) harvoja lineaarikombinaatioita, jotka minimoivat Ci-kertoimet. Matemaattisen analyysin yhteydessä osoitan, että Ci-kertoimien ylärajaa voidaan kasvattaa 8/5-kertaiseksi aiemmissa hyökkäyksissä käytetystä rajasta, mikä laskee redusointivaiheen laskennallista vaativuutta. Toteutin Bleichenbacherin hyökkäyksen käytännössä 192-bittistä ECDSA-toteutusta vastaan. Selvitin kertakäyttöisten satunnaislukujen 4 vähiten merkitsevää bittiä malliperusteisella hyökkäyksellä (engl., template attack). Hyökkäys koostuu normaalijakautuneista malleista, jotka on estimoitu tunnetulla avaimella tehdyistä mittauksista. Ratkaisin allekirjoitusavaimen 9425 allekirjoituksesta, jotka on luokiteltu 23000 mittauksesta. Vastaava määrä on mahdollista hankkia käytännön hyökkäyksissä.Description
Supervisor
Hollanti, CamillaThesis advisor
Alpírez Bock, EstuardoHelanti, Lassi
Keywords
side-channel attack, digital forensics, power analysis, electromagnetic analysis, elliptic curve digital signature algorithm, Bleichenbacher's solution to the hidden number problem
