In this post I will briefly describe an attack against the ECDSA signing algorithm which exploits known biases in the nonce employed in a signature.
The attack is based on the theory of short vectors in lattices and uses the LLL algorithm to recover the private key from multiple (biased) signatures.
The ECDSA signature algorithm
The Elliptic Curve Digital Signature Algorithm works over an elliptic curve E defined over a field \mathbb{F}_q of prime order p and generator G, i.e. \langle G\rangle = E and |E| = p).
A keypair in E is a pair (P, d) with d\in\mathbb{Z}_p and P=d\cdot G \in E: P is said to be the public key in E(\mathbb{F}_q) corresponding to the private key d.
Signature
To sign a \log p-length message m using a private key d:
- select a random value k\in\mathbb{Z}_p;
- calculate the \mathbb{F}_q-coordinates of the point (x,y) = k\cdot G;
- compute r = x \pmod p. If r=0\pmod p, go to step 1.
- compute s = k^{-1}(m + r\cdot d) \pmod{p}.
- Output the signature (r,s) for m.
Verification
Given a signature (r,s) for a \log p-length message m, it is verified against a public key P as (some checks are omitted):
- Compute u = ms^{-1} \pmod p and v = rs^{-1} \pmod p.
- Calculate the \mathbb{F}_q-coordinates of the point (x,y) = u\cdot G + v \cdot P; abort if (x,y) is the identity point of E.
- The signature is valid if r = x \pmod p.
Security considerations
It is crucial for the nonce k to be uniformly distributed in the interval (0,p). If the same nonce is re-used multiple times for the same private key d, the latter can be quickly recovered from the signature.
More sophisticated attacks which recover the private key are possible if one or more bits of the nonce k are known along with the corresponding signatures.
Lattices
In group theory, a lattice informally indicates a set of vectors constrained by a group structure induced by \mathbb{Z}, where vectors can be added and subtracted similarly as happens in a multi-dimensional vector space.
Slighlty bit more formally, given a set of vectors V = \{v_1,..,v_n\} with the v_i having coordinates in \mathbb{R}, the lattice induced by V is the set of all vectors that can be obtained as linear combinations over \mathbb{Z} of elements of V, that is
A minimum set of vectors which defines a lattice \mathcal{L} is called lattice basis and it usually represented with a matrix having as rows the vectors in the basis. With a little abuse of notation, we then have
Since a lattice is made of vectors with real coordinates, we can define a norm to induce a partial ordering of vectors in a lattice.
We skip the details on how the norm is computed or what we formally mean by “small” or, better, short lattice vectors: just to give some intuition, small lattice vectors are those who have average small (i.e. close to 0) components.
Finding the shortest non-zero vector in a lattice is considered a difficult mathematical problem (NP-hard) and many cryptographic schemes base their security on such problem or close variants (e.g. find the closest lattice vector v to a target vector t).
However there exists statistical algorithms like Lenstra-Lenstra-Lovász (LLL) able to produce in polynomial time a short lattice basis using as input any of the lattice basis. Here short means that the vectors in the output basis satisfy some bounds with respect to the shortest vector of the lattice, and thus can be used as a good approximation (and often as the correct solution) to the Shortest Vector Problem (SVP) in lattices.
In the following we will use LLL as a blackbox: we input a lattice basis and we obtain a new basis containing short (hopefully, the shortest) vectors in the same lattice.
ECDSA equations as lattice vectors combinations
Suppose we have access to multiple ECDSA signatures (r_1,s_1),...,(r_n,s_n) for known messages m_1, ..., m_n, all signed under the same private key d.
By expanding the ECDSA defining equations and by making explicit the modulo p reduction, we obtain
for some unknown integers l_i.
Here, red values denote secret (to the attacker) integers, while in black we denote public values.
Exploiting such equations, we want to construct a lattice which contains the vector
Aiming at this, we can consider the following basis:
Indeed, the integer linear combination of the basis vectors given by
is equal to (\color{red}{k_1}, \color{red}{k_2}, \ldots, \color{red}{k_n}).
If the nonces k_i are all small, that is are less than a certain value B << p, the LLL algorithm would find with a certain probability the short vector (\color{red}{k_1}, \color{red}{k_2}, \ldots, \color{red}{k_n}) using as input just the matrix M (B has to satisfy some conditions as well, but we skip these details for now).
We note that being able to recover just one correct nonce k_i used in a signature (r_i,s_i) would be enough to compute the private key \color{red}{d} as
The accuracy of the LLL algorithm’s output can be improved by exploiting the knowledge of the expected size of the unkown multipliers. This can be achieved by slightly changing the lattice basis to
which would then contain the short vector (B, B\color{red}{d}/p, \color{red}{k_1}, \color{red}{k_2}, \ldots, \color{red}{k_n}).
This change induces all components of the found short vector to be close to B and forces the first basis row vector to be considered during the LLL reduction with a small multiplier (we want it to be 1).
An attack example
We use the following Python3 script (the ecdsa module is required) to generate 40 signatures for different random messages under a certain private key k. The signature are generated so that the employed nonce are biased by having the first bias = 1 bytes set to zero.
from ecdsa.ecdsa import curve_256, generator_256, Public_key, Private_key
from random import randbytes, randint
G = generator_256
p = G.order()
def genKeyPair():
d = randint(1,p-1)
pubkey = Public_key(G, d*G)
privkey = Private_key(pubkey, d)
return pubkey, privkey
def sign(privkey, bias):
m = randbytes(32)
nonce = randbytes(32 - bias)
sig = privkey.sign(int.from_bytes(m, "big"), int.from_bytes(nonce, "big"))
return (m, sig.r, sig.s)
pubkey,privkey = genKeyPair()
print('Public key:', (int(pubkey.point.x()), int(pubkey.point.y())))
print('Private key:', int(privkey.secret_multiplier))
SIGs = []
for _ in range(40):
SIGs += [sign(privkey, 1)]
SIGs
We obtain
Public key: (97072186797211310505016479095232580218352290897911577856744836894403414937794, 39021415952191690909385107115390271479179743595779360677080390824579192648103)
Private key: 22141441591425191973935382816357307770859103957716805845492797027167587108502
#SIGs contains tuples (m, r, s) with (r,s) a signature for m under public key
SIGs = [
(38000798177211802687813163831537249461003818810823040747312627576979826149588, 87471860015059189703236137773642831184736841890632235084246109711627781257858, 63133927548059291417465730537335149045977952900569631737292314227056024506867),
(111740430575368962806997471824551417413932781476957672024218352232322323458716, 38799912782570650419042855286138858397897432845802489083656263946988797883634, 65673364723478809439788949730589345252668129356850004213499878788192753264114),
(109471736153500797600289399599603612417206514279656293125741029506460920705510, 33018778321245351255834911241912271877131678919197652984430445391180043578451, 68794573169245303192236194229553076673928329522217012731086730343915500609245),
(3428039712156506685063761213590010967589339701947343281990183115408095946955, 33847108210470745889263973706032099560456153945623285028926732879720243668966, 101032229617726041505001861922730042664940055441807580415482120450974622703840),
(112832547424785005330966270932839487272417451823063241613087021511567713102481, 4498640521207618834708983162876232184306498630236063750161182630881292823747, 2597284659263288679792034895017566170501372107525154963933928103422685578177),
(89210777451375939767912559345222365636703422273694561446259233182692266037514, 3148110516178317859826408207631436280518197414805997396430182056821450019243, 24884394397794915311164256392676833516045370503241228243722739666353174721946),
(92125687882265374451160632507660867263055238044979499729031817585027675944443, 18512695575447232516659199824763228069300593728595998375698889476971706245790, 69771644945162472054143663375004954317964526872056891309209917550341516046946),
(44931115767175857636783814038025143624497311367085988181021151662143075005816, 90159912684307733907716373306509402658750067307148014089060911664268537846186, 80040564567142277158965814149119657046619216592802786737140735531588142159672),
(99824216776912615684583461882134017927050863204838136476650411211740545691414, 72510042680529582256071794409225061516248227639347794693378158484387873903713, 1241372813699620220794164192191886010038251343852943790901786012935137465810),
(26423059661953627546082984253783853957228933225919544563703829761482932830581, 95089044171936832261837375372844439399858569540917319869847173773947615344508, 32415694356588882330419002600338362570673837988048942638952420722277714691328),
(39093736984257634117333691346985600862449508296548911171848710710992568508944, 46307435491146669847459441201199094677513959681337089713719334416853616553835, 52539060284018799612174913436030712352265037198469791674090903387218500273451),
(80915222634032587274836046954124200214734564919849973836791801552944566983238, 109024594447261400997359038933339812175707537112619546804450075557315904083064, 84914089719551937629888536187599064939417037544609200154813537621310562984949),
(53574938369514431642660498524071393532110012321262039760871057221495186075723, 87604213795648297940228804402036751109603876203727676817832848047760552274790, 38545126097527733651159628857398619841361810923763112771817587307485325020243),
(60249338573218083663278154193397386464080501263347810801846914736239512446446, 79550483512876045792305954677587194936916035239250031692971359671165338215371, 102046172604923097236560231026785086628521973652336032743911187490012721548258),
(71265571235982972160322582990507374188796339118442878648750897653435326031287, 67881994474120078757143661710314691306433858886087869397891278471827540456214, 6876467855417110631485858739226778678337990278292260069466337493425800008371),
(95387768900360121497781116181308388952040318490379409383806789474520668138305, 84086822957653093068674942257334820963368037016780531728886650523593613435090, 28477903800209663612636174501471988627893095548757564801826789385829075592472),
(109244701190078546692004985312747109123942481339340714492679264662280107122679, 29265795804565082547759266656590914003715070465692315449295466972069180238236, 52233856262914918644394985123656935383427507890485736071911468213723834810053),
(74230718909372612099627771189774184340028243398438147388428424413953951107882, 28344821553970147716913338149572396446456998471027163527577029375500388764874, 48058457846129439807923765066768962880259186415838844704689702233861643769812),
(11752602457181666943118604934263017415848301698468131970865124369693974700999, 36968937935485787206157602934039134021392130855159556344113000060697755038349, 104473118071910859619717683273250537999824926196585042949953690004612749912442),
(36468677799088106651751023597422286804329418705069302666496650396276958240541, 58858042482577549051769169041020204807044247585560660847859385759743573023102, 14329852185127149855977553948802773334036622272261861740042509291367457879273),
(91697633527936257022585624574687380707826622073381893192636711724017860529761, 87568746295157886537444944239455287623980241040288066558074550385068727088673, 100038312283111710415936206168074543863861388759408853379596650813770789855885),
(45470400978445659544801595981398071311843633104183691662819069479095406057440, 82752761153294728120397154293059845321750466453114246418645856475676034879698, 3528585878369093817271859608659342432862455320591962622597622561068536451085),
(75936983570064540341822879473660098625052174591880422384170300594883189933939, 24033853901476658326201452227478184071207886538982940099153182030825558739334, 57405753688485878187272307125953308141839275459980683893522604432900467339031),
(42987806299776412753022876666830593021256490370527363556813512444580569508925, 8803426219066744891197787373593687824643494995888782183178823629236964651257, 58326396635610169513497624825714626105445572291829353461909469888071216226845),
(61508337877071720938109371140643457018124464952131035220435618882381952058700, 87668313737379926069078168193458725941363102601710203855657953645091589369327, 103323208246513467599612224041381444119693631300981264809286358311557357340722),
(3029256104542783873188438456026712621807498920754087022991999471003894851828, 107742708555911103446361387222962891399723113675433059479411923061724697283022, 89931802786982269586198562289426822271025831120441751008514420218190829001407),
(96882777452218725748616639130620044777738585482837721493726566110183013117260, 8616970681936411845344364083480840874965114654681596840257833953383248916628, 38363747168265353080047610400507660363027897446825712396517289138970663878251),
(40110947893115911699652284016100777036251415737511025165756080938767464534347, 10094638054310176879055329807286640918475670183049482611900507879771059568104, 92373083510198880120981639013170540431727842875398500913818381788790256655748),
(49037534520394699297970804639773904601399800247449880170355822496172541338505, 55111844865951262235949074866995519211429839285970160074431713105415134247114, 109614079017417427220621088015418398120850939179761029521196516176452403193644),
(97736634077151479656405875194167913285714586002039548686848977314695456769550, 48864523784711471330059846254437387376604668432923924350798904895400620584219, 103671044850272596878118916238387562627751119997678733983525634235370556020498),
(87060754830158674533073775934551616693679486224328506652915700807148822723301, 39587846874472242304900515582359998182618011855151469732683869372305264939838, 56600936401295025305301361854465869314373190633275218778157981080442864910926),
(50443633067651391779679080908529257597781219591569701771432405936869992873214, 110611233591007858868112459738388942788340636252303529453429726197881783242270, 67534195065295593516996390982129650489591114291372055995525875299033906670455),
(70884773696247224814016649550658639608018458774426980967768640829710026941164, 80368942225792309400570561235331771461642601772497148066467842003402068111412, 94090601120237934578713455392187079226191277415230356954802056195766078272431),
(26150770910625322789760513928892818423863884590148101270860028708678385828681, 84548970054652804877520485334274147677769528552057273478560039941691330520451, 42665458565218029167287016302432661331932488363931123619603206426071177779096),
(72748199291922034632604888421095300971297452923057130966756499190435214503887, 96174480214362268395094167667088718601985531668984503273154965185322074304392, 99387334415452856806698060102090538918820228997400046177111836494406300297248),
(100590584631801697409936663200006715380972457755119364325390912628702022659892, 108203177273289245108674903916160754346571765543126615819970747011289761439672, 7023746332916853700118748570391904047852626343550893781185393012658256943107),
(100998952163858959875912495718437242830651071031414993322283176382784078224197, 11422003813771992476870467991983135007496534633484788701394015259062903507329, 105417742246060431455419061109662264399406698228295085506922631749765694576097),
(14923418863112121037578603792556948840932533022583262921513108407067337608145, 36783928236658736743889097944137743791100935115022666175544647985433881403535, 86951764623506071983483466589228285006111679413515713492307230678921043331138),
(70598287328063356939439960868301502950592710242335155248591521914942322831345, 10137002555781487951407260743359046248459167299714683495092057258517249699167, 108206422361579212773177075583369311836172084183023098737616460329284244732108),
(103682554983023523285773889322296267491748253572140650954042714177670168079057, 3728685596362981911852982183847568071028819285129189294264012192085974331279, 26101372316372242532237449816856040978466341644558159293227268830973869537791)
]
We now use the following SageMath script to import the public key and the generated signatures, build the lattice matrix and run the LLL algorithm (the following code snippets can be tested online on Cocalc by creating a Jupyter notebook with a Sagemath core).
## The ECDSA parameters
q = 115792089210356248762697446949407573530086143415290314195533631308867097853951
A = -3
B = 0x5AC635D8AA3A93E7B3EBBD55769886BC651D06B0CC53B0F63BCE3C3E27D2604B
F = GF(q)
E = EllipticCurve(F,[A,B])
Gx = 0x6B17D1F2E12C4247F8BCE6E563A440F277037D812DEB33A0F4A13945D898C296
Gy = 0x4FE342E2FE1A7F9B8EE7EB4A7C0F9E162BCE33576B315ECECBB6406837BF51F5
G = E(Gx,Gy)
p = 115792089210356248762697446949407573529996955224135760342422259061068512044369
assert G.order() == p
## The public key
P = E(97072186797211310505016479095232580218352290897911577856744836894403414937794, 39021415952191690909385107115390271479179743595779360677080390824579192648103)
## The collected biased signatures
# SIGs contains tuples (m, r, s) with (r,s) being a signature for m under P
SIGs = [
(38000798177211802687813163831537249461003818810823040747312627576979826149588, 87471860015059189703236137773642831184736841890632235084246109711627781257858, 63133927548059291417465730537335149045977952900569631737292314227056024506867),
(111740430575368962806997471824551417413932781476957672024218352232322323458716, 38799912782570650419042855286138858397897432845802489083656263946988797883634, 65673364723478809439788949730589345252668129356850004213499878788192753264114),
(109471736153500797600289399599603612417206514279656293125741029506460920705510, 33018778321245351255834911241912271877131678919197652984430445391180043578451, 68794573169245303192236194229553076673928329522217012731086730343915500609245),
(3428039712156506685063761213590010967589339701947343281990183115408095946955, 33847108210470745889263973706032099560456153945623285028926732879720243668966, 101032229617726041505001861922730042664940055441807580415482120450974622703840),
(112832547424785005330966270932839487272417451823063241613087021511567713102481, 4498640521207618834708983162876232184306498630236063750161182630881292823747, 2597284659263288679792034895017566170501372107525154963933928103422685578177),
(89210777451375939767912559345222365636703422273694561446259233182692266037514, 3148110516178317859826408207631436280518197414805997396430182056821450019243, 24884394397794915311164256392676833516045370503241228243722739666353174721946),
(92125687882265374451160632507660867263055238044979499729031817585027675944443, 18512695575447232516659199824763228069300593728595998375698889476971706245790, 69771644945162472054143663375004954317964526872056891309209917550341516046946),
(44931115767175857636783814038025143624497311367085988181021151662143075005816, 90159912684307733907716373306509402658750067307148014089060911664268537846186, 80040564567142277158965814149119657046619216592802786737140735531588142159672),
(99824216776912615684583461882134017927050863204838136476650411211740545691414, 72510042680529582256071794409225061516248227639347794693378158484387873903713, 1241372813699620220794164192191886010038251343852943790901786012935137465810),
(26423059661953627546082984253783853957228933225919544563703829761482932830581, 95089044171936832261837375372844439399858569540917319869847173773947615344508, 32415694356588882330419002600338362570673837988048942638952420722277714691328),
(39093736984257634117333691346985600862449508296548911171848710710992568508944, 46307435491146669847459441201199094677513959681337089713719334416853616553835, 52539060284018799612174913436030712352265037198469791674090903387218500273451),
(80915222634032587274836046954124200214734564919849973836791801552944566983238, 109024594447261400997359038933339812175707537112619546804450075557315904083064, 84914089719551937629888536187599064939417037544609200154813537621310562984949),
(53574938369514431642660498524071393532110012321262039760871057221495186075723, 87604213795648297940228804402036751109603876203727676817832848047760552274790, 38545126097527733651159628857398619841361810923763112771817587307485325020243),
(60249338573218083663278154193397386464080501263347810801846914736239512446446, 79550483512876045792305954677587194936916035239250031692971359671165338215371, 102046172604923097236560231026785086628521973652336032743911187490012721548258),
(71265571235982972160322582990507374188796339118442878648750897653435326031287, 67881994474120078757143661710314691306433858886087869397891278471827540456214, 6876467855417110631485858739226778678337990278292260069466337493425800008371),
(95387768900360121497781116181308388952040318490379409383806789474520668138305, 84086822957653093068674942257334820963368037016780531728886650523593613435090, 28477903800209663612636174501471988627893095548757564801826789385829075592472),
(109244701190078546692004985312747109123942481339340714492679264662280107122679, 29265795804565082547759266656590914003715070465692315449295466972069180238236, 52233856262914918644394985123656935383427507890485736071911468213723834810053),
(74230718909372612099627771189774184340028243398438147388428424413953951107882, 28344821553970147716913338149572396446456998471027163527577029375500388764874, 48058457846129439807923765066768962880259186415838844704689702233861643769812),
(11752602457181666943118604934263017415848301698468131970865124369693974700999, 36968937935485787206157602934039134021392130855159556344113000060697755038349, 104473118071910859619717683273250537999824926196585042949953690004612749912442),
(36468677799088106651751023597422286804329418705069302666496650396276958240541, 58858042482577549051769169041020204807044247585560660847859385759743573023102, 14329852185127149855977553948802773334036622272261861740042509291367457879273),
(91697633527936257022585624574687380707826622073381893192636711724017860529761, 87568746295157886537444944239455287623980241040288066558074550385068727088673, 100038312283111710415936206168074543863861388759408853379596650813770789855885),
(45470400978445659544801595981398071311843633104183691662819069479095406057440, 82752761153294728120397154293059845321750466453114246418645856475676034879698, 3528585878369093817271859608659342432862455320591962622597622561068536451085),
(75936983570064540341822879473660098625052174591880422384170300594883189933939, 24033853901476658326201452227478184071207886538982940099153182030825558739334, 57405753688485878187272307125953308141839275459980683893522604432900467339031),
(42987806299776412753022876666830593021256490370527363556813512444580569508925, 8803426219066744891197787373593687824643494995888782183178823629236964651257, 58326396635610169513497624825714626105445572291829353461909469888071216226845),
(61508337877071720938109371140643457018124464952131035220435618882381952058700, 87668313737379926069078168193458725941363102601710203855657953645091589369327, 103323208246513467599612224041381444119693631300981264809286358311557357340722),
(3029256104542783873188438456026712621807498920754087022991999471003894851828, 107742708555911103446361387222962891399723113675433059479411923061724697283022, 89931802786982269586198562289426822271025831120441751008514420218190829001407),
(96882777452218725748616639130620044777738585482837721493726566110183013117260, 8616970681936411845344364083480840874965114654681596840257833953383248916628, 38363747168265353080047610400507660363027897446825712396517289138970663878251),
(40110947893115911699652284016100777036251415737511025165756080938767464534347, 10094638054310176879055329807286640918475670183049482611900507879771059568104, 92373083510198880120981639013170540431727842875398500913818381788790256655748),
(49037534520394699297970804639773904601399800247449880170355822496172541338505, 55111844865951262235949074866995519211429839285970160074431713105415134247114, 109614079017417427220621088015418398120850939179761029521196516176452403193644),
(97736634077151479656405875194167913285714586002039548686848977314695456769550, 48864523784711471330059846254437387376604668432923924350798904895400620584219, 103671044850272596878118916238387562627751119997678733983525634235370556020498),
(87060754830158674533073775934551616693679486224328506652915700807148822723301, 39587846874472242304900515582359998182618011855151469732683869372305264939838, 56600936401295025305301361854465869314373190633275218778157981080442864910926),
(50443633067651391779679080908529257597781219591569701771432405936869992873214, 110611233591007858868112459738388942788340636252303529453429726197881783242270, 67534195065295593516996390982129650489591114291372055995525875299033906670455),
(70884773696247224814016649550658639608018458774426980967768640829710026941164, 80368942225792309400570561235331771461642601772497148066467842003402068111412, 94090601120237934578713455392187079226191277415230356954802056195766078272431),
(26150770910625322789760513928892818423863884590148101270860028708678385828681, 84548970054652804877520485334274147677769528552057273478560039941691330520451, 42665458565218029167287016302432661331932488363931123619603206426071177779096),
(72748199291922034632604888421095300971297452923057130966756499190435214503887, 96174480214362268395094167667088718601985531668984503273154965185322074304392, 99387334415452856806698060102090538918820228997400046177111836494406300297248),
(100590584631801697409936663200006715380972457755119364325390912628702022659892, 108203177273289245108674903916160754346571765543126615819970747011289761439672, 7023746332916853700118748570391904047852626343550893781185393012658256943107),
(100998952163858959875912495718437242830651071031414993322283176382784078224197, 11422003813771992476870467991983135007496534633484788701394015259062903507329, 105417742246060431455419061109662264399406698228295085506922631749765694576097),
(14923418863112121037578603792556948840932533022583262921513108407067337608145, 36783928236658736743889097944137743791100935115022666175544647985433881403535, 86951764623506071983483466589228285006111679413515713492307230678921043331138),
(70598287328063356939439960868301502950592710242335155248591521914942322831345, 10137002555781487951407260743359046248459167299714683495092057258517249699167, 108206422361579212773177075583369311836172084183023098737616460329284244732108),
(103682554983023523285773889322296267491748253572140650954042714177670168079057, 3728685596362981911852982183847568071028819285129189294264012192085974331279, 26101372316372242532237449816856040978466341644558159293227268830973869537791)
]
# We know that the first byte is biased, hence all nonces k satisfies k < B = 2^(256-8)
B = 2**(256-8)
# We construct the first two rows of the lattice
Mtilde = [B, 0]
Rtilde = [0, B/p]
for sig in SIGs:
m,r,s = sig
Mtilde += [inverse_mod(s,p)*m % p]
Rtilde += [inverse_mod(s,p)*r % p]
# We redefine the arrays as matrixes
Mtilde = matrix(QQ, 1, len(Mtilde), Mtilde)
Rtilde = matrix(QQ, 1, len(Rtilde), Rtilde)
# We contruct the diagonal submatrix with p entries
Pdiag = -p*identity_matrix(QQ, len(SIGs));
# We construct the lower left n x 2 zero block matrix
Z = matrix(QQ, len(SIGs), 2, [0 for i in range(len(SIGs)*2)] )
# We construct the final matrix assembling all blocks
M = block_matrix([[Z, Pdiag]])
M = block_matrix([[Mtilde], [Rtilde], [M]])
# We run the LLL algorithm
L = M.LLL()
# We check if any valid nonce was found
found = 0
for row in L.rows():
if found:
break
for i in range(len(SIGs)):
if found:
break
m,r,s = SIGs[i]
# we skip the first two vector components we used to improve LLL
solk = row[i+2]
# LLL might have swapped the sign of found short vectors
for k in [solk,-solk]:
d = inverse_mod(r,p)*(k*s-m) % p
if d*G == P:
print("Private key found!", d)
found = 1
break
LLL is a statistical algorithm and its results may vary from execution to execution. Also, it is sensible to many parameters that can be set when calling LLL(), but for this example we left everything to default. In the average case, the above code will print in few seconds the following:
Private key found!
d = 22141441591425191973935382816357307770859103957716805845492797027167587108502
Number of required biased signatures
In the above example we have a 1 byte bias in nonce generation, thus each signature leaks \approx1 byte of the private key. It follows that we need approximately \approx 32 biased signature to recover the private key (in our example we used 40 to balance the fact that we didn’t properly tune LLL parameters) or roughly
signatures (more formally, by possessing n signatures with nonces less than B, we expect to find the private key if the following relation
holds, see here for more information).
We note that the above attacks works even if nonces have just 1 biased bit, and using some ad-hoc lattices and parameters can work even when only a fraction of a nonce bit is a biased, i.e. is either 0 or 1 with probability >>50\%.
Attack vectors
At this point is clear how sensible ECDSA is with respect to nonce generation.
Weaknessess might accidentaly exists or backdoors might be deliberately inserted, for example, in:
- the pseudo random number generator used for generating nonces;
- in case deterministic nonces are used, by setting an improper hash block size for the employed HMAC (e.g. use the 160 bits SHA1 in place of SHA256), or
- any kind of software backdoor that makes some nonce bits deterministic. For example, regardless on how the nonce k is computed, an extra 1-bit left shift instruction such as
k = k >> 1would suffice to set the most significant bit of k to 0.
However, a software backdoor is not necessarily needed to mount a lattice key recovery attack against ECDSA. In fact, an attacker would succeed if is able to distinguish signatures computed with nonces having, for example, their most significant bits set to 0 from other ones.
Indeed, if the attacker has access to an oracle that tells him with a certain probability if a message-signature pair was generated with a nonce having its first b bits set to 0, then -even if the signature implementation was genuine and nonces were selected uniformly at random- he expects to compute a useful signature (for the lattice attack) every 2^b random signature computed: he then simply collects enough of such useful signatures distinguished by his oracle and runs the above lattice key recovery attack.
Side-channel attacks
From now on we assume that signatures are generated with a non-backdoored implementation.
Clearly, from a tuple (m, (r,s)) nothing can be inferred on the nonce used while computing the signature (r,s).
However, extra information might be obtained if it is possible to audit the hardware which generates the signatures, thus performing the so-called side-channel attacks.
To make such attacks more realistic with respect to modern secure hardware implementations, we assume ECDSA private keys are stored in a secure and inaccessible hadware enclave. Hence, we don’t have any direct access to ECDSA private key (either hardware or software) and any attempt to tamper the hardware will most likely result in a permanent loss of stored private keys.
However, it is possible to measure execution times, power consumptions and electro-magnetic emanations while the under-attack hardware computes a signature.
We note that any implementation that branches on private information (e.g. if the first bit of the key is 0 do …) will most likely leak side-channel information that can be used to directly recover it.
Just to provide a more concrete example for ECDSA, if the elliptic curve scalar point multiplication implementation is not side-channel resistant (informally, avoids such branches) both execution times and power consumptions may leak the most significant bits of the nonce.
Indeed, when the random nonce k is computed (no matter if randomly or deterministically), the point k\cdot G is computed as well during the signature computation. If k has its most significant bits set to 0, the computation of k\cdot G will be faster and use less energy since the last doubling/additions would be skipped.
If this is the case, it might be then possible to directly infer which signatures can be useful to mount a lattice attack.
If we have access to a hardware-clone for which we know the stored private keys, we might even be able to build a machine-learning based distinguisher (the oracle we mentioned above): we can measure side channel information leaked while generating several random signature employing nonces having the most significant bits set to 0 (and possibly under different private keys we control) and we use this dataset to train a machine-learning model. Then, we use such model to classify with certain probability signatures generated with the hardware we are attacking and we keep those useful to mount a lattice attack.
If implementations don’t take into consideration side-channels attacks, the latter are all really practical and effective: