abclinuxu.cz AbcLinuxu.cz itbiz.cz ITBiz.cz HDmag.cz HDmag.cz abcprace.cz AbcPráce.cz
AbcLinuxu hledá autory!
Inzerujte na AbcPráce.cz od 950 Kč
Rozšířené hledání
×
dnes 00:33 | Bezpečnostní upozornění

CSIRT.CZ upozorňuje na kritickou zranitelnost ve WordPressu umožňující vzdálené spuštění libovolného kódu. Prakticky se jedná o kombinací dvou různých zranitelností (Directory Traversal a Local File Inclusion), pro jejichž úspěšné zneužití musí útočník získat v rámci instance WordPressu alespoň oprávnění autora.

Ladislav Hagara | Komentářů: 0
včera 17:33 | Nová verze

Po dvou a půl letech od vydání verze 5.0.0 byla oficiálně vydána nová major verze 6.0.0 správce digitálních fotografií a nově i videí digiKam (digiKam Software Collection). Přehled novinek i s náhledy v oficiálním oznámení. Ke stažení je také balíček ve formátu AppImage. Stačí jej stáhnout, nastavit právo ke spuštění a spustit.

Ladislav Hagara | Komentářů: 0
včera 00:44 | Komunita

Do 2. dubna se lze přihlásit do dalšího kola programu Outreachy (Wikipedie), jehož cílem je přitáhnout do světa svobodného a otevřeného softwaru lidi ze skupin, jež jsou ve světě svobodného a otevřeného softwaru málo zastoupeny. Za 3 měsíce práce, od 20. května do 20. srpna 2019, v participujících organizacích lze vydělat 5 500 USD.

Ladislav Hagara | Komentářů: 1
včera 00:11 | Bezpečnostní upozornění

Byly zveřejněny informace o o bezpečnostní chybě CVE-2019-6454 ve správci systému a služeb systemd (PID 1). Běžný uživatel jej může shodit připravenou D-Bus zprávou. V upstreamu je chyba již opravena [reddit].

Ladislav Hagara | Komentářů: 3
18.2. 22:44 | Nová verze

Byla vydána nová verze 2019.1 průběžně aktualizované linuxové distribuce navržené pro digitální forenzní analýzu a penetrační testování Kali Linux (Wikipedie). Přehled novinek v changelogu. Vývojáři zdůrazňují Linux 4.19.13 a díky němu opětovnou podporu Banana Pi a Banana Pro, aktualizaci nástrojů jako theHarvester nebo DBeaver a Metasploit Framework ve verzi 5.0. Aktualizovat Kali Linux lze pomocí příkazů "apt update && apt -y full-upgrade".

Ladislav Hagara | Komentářů: 0
18.2. 13:33 | Zajímavý článek

Craig Loewen se v příspěvku na blogu Microsoftu věnuje novinkách ve WSL (Windows Subsystem pro Linux), které přinese Windows 10 1903. Jedná se především o možnost přístupu z Windows (Průzkumník souborů, explorer.exe) k souborům v nainstalovaných linuxových distribucích. Použit je protokol 9P.

Ladislav Hagara | Komentářů: 10
18.2. 10:44 | Zajímavý software

Byl vydán Hangover ve verzi 0.4.0. Jedná se o součást projektu Wine umožňující spouštět Windows aplikace pro x86 a x86_64 na architektuře ARM64 (AArch64). Zdrojové kódy této alfa verze jsou k dispozici na GitHubu.

Ladislav Hagara | Komentářů: 1
17.2. 03:00 | Nová verze

Byla vydána nová major verze 3.0.0-1 linuxového prostředí pro operační systémy Windows Cygwin (Wikipedie). Přehled novinek v oficiálním oznámení.

Ladislav Hagara | Komentářů: 6
17.2. 02:00 | Nová verze

Byl vydán Debian 9.8, tj. osmá opravná verze Debianu 9 s kódovým názvem Stretch. Řešeny jsou především bezpečnostní problémy, ale také několik vážných chyb. Předchozí instalační média Debianu 9 Stretch lze samozřejmě nadále k instalaci používat. Po instalaci stačí systém aktualizovat.

Ladislav Hagara | Komentářů: 0
15.2. 12:33 | Pozvánky

Příští týden bude na MFF UK zahájena série přednášek o architektuře a implementaci operačních systémů. Mezi přednášejícími budou odborníci z firem Kernkonzept, Oracle, Red Hat, SUSE či SYSGO. Pokud si chcete rozšířit obzory (virtualizace, ptrace, ZFS, kdump, ...), vyberte si z harmonogramu téma, které vás zajímá a přijďte. Přednášky se konají každý čtvrtek od 15:40 v učebně S4 na Malostranském náměstí 25 v Praze. Přednášky jsou přístupné veřejnosti (registrace není nutná), studenti UK a ČVUT si je mohou zapsat jako standardní předmět.

Vojtěch Horký | Komentářů: 19
Máte v desktopovém prostředí zapnutou zvukovou znělku po přihlášení se do systému?
 (7%)
 (1%)
 (90%)
 (1%)
Celkem 353 hlasů
 Komentářů: 11, poslední 14.2. 07:59
Rozcestník

Eliptické křivky - vztah Weierstrass, Montgomery, Edwards

14.2.2018 22:28 | Přečteno: 1229× | programování | Výběrový blog | poslední úprava: 14.2.2018 23:31

Po delší době jsem měl trocha času prozkoumat, jaký vztah mezi sebou mají Weierstrassovy, Montgomery, a (twisted) Edwards křivky. Jakou mají strukturu, jak je lze mezi sebou převádět, jaký mají řád grupy a řády prvků v grupě. Jaké nebezpečí hrozí a jaké úskalí přináší každá z nich.

Eliptické křivky prakticky nad konečným polem používané v kryptografii lze vyjmenovat těmito skupinami:

Weierstrassova forma

Weierstrassova forma je obecná forma zápisu křivek a všechny eliptické křivky na ní lze převést. Jednoduchá otázka je, proč nepoužívat obecnou formu? Protože je velmi těžké napsat algoritmus pro Weierstrassovu formu, který by běžel v konstantím čase. Adam Langley kdysi napsal návod, jak udělat operace nad Weierstrassovými křivkami v konstantním čase. Dnes to například implementuje knihovna libsecp256k1 - tato křivka se používá v Bitcoinu.

Ale obecně je napsání constant-time operací nad Weierstrassovou formou náročné. Snad všechny NIST křivky spadají právě pod tuto obecnou kategorii.

Montgomeryho křivky

Montgomeryho křivky již mají speciální formu. Asi nejznámější je Curve25519 od D. Bernsteina, která vznikla v 2005. Doporučuji se alespoň běžné mrknout na původní paper, Bernstein mi přijde, že proti ostatním vědcům píše relativně srozumitelně - i když nerozumíte algebře, něco si z toho paperu odnesete - třeba pochopení, proč je implementace rychlá nebo high-level overview security modelu.

Hlavní praktickou vymožeností Montgomeryho křivek je algoritmus zvaný Montgomery ladder, který umožňuje jednodušší implementaci skalárního násobení, jenom s jednou souřadnicí, ale hlavně v konstantím čase.

Obecně je možné převést Montgomeryho křivku do obecný Weierstrassovy formy, jako ukazuje tento příklad v případě zmíněné Curve25519).

(Twisted) Edwards křivka

Twisted Edwards křivka má opět určitou specifickou formu. "Obyčejná" Edwards curve se od Twisted Edwards curve liší jenom tím, že má koeficient a=1 v rovnici křivky. Tudíž Edwards curves je podmožinou Twisted Edwards curves.

Nejznámější Edwards curve (a taky Twisted Edwards curve) je Curve41417. Teď přichází čas na vhledy do struktury, protože i když je Curve25519 typicky nazývána jako Montgomery curve, lze twisted Edwards curves a Montgomery curves převádět "tam a zpátky". Použitá forma je spíš výsledkem toho, jak se s ní nejlépe počítá v tomto případě.

Úskalí jednotlivých kategorií křivek

Zde začneme vysvětlovat vlastnosti těch křivek a jaké kompromisy dělají, většina těchto vlastností bude vysvětlena v další sekci o převoditelnosti křivek. První otázka, který mě zajímala, je že je ideální mít grupu, nebo-li počet prvků na křivce, prvočíselný. Proč bychom si neudělali grupu prvočíselného řádu? S grupou prvočíselného řádu (tj. počet prvků je prvočíslo) se mnohem lépe pracuje z hlediska, aby člověk neudělal chybu, protože grupy neprvočíselného řádu mají dost neintuitivní a zrádné vlastnosti (lidi v tom dělají chyby). Ale zrovna Montgomery a Twisted Edwards curves typicky nemají prvočíselný řád.

Místo toho se na Montgomeryho nebo Twisted Edwards křivce vybere podgrupa, které generátor má prvočíselný řád. Nebo jinak: tyhle grupy (křivky) mají neprvočíselný řád (počet prvků). To je jejich nevýhoda. Jejich výhody jsou třeba ten Montgomery ladder nebo u twisted Edwards curves vlastnost, že můžete mít velmi jednoduchý algoritmus, jak počítat aritmetiku na křivce - je to jednoduchá modulární aritmetika, která je úplná. Tj. funguje pro všechny vstupy nebo všechny body. Není nutné mít speciální "if" pro bod v nekonečnu (identitu). Ta identita je u twisted Edwards curves definována jako bod (0, 1) a můžete s ním počítat s ním jako s jakýmkoli jiným bodem (viz sekci 2 v Twisted Edwards Curves).

Tak co uděláme s tím neprvočíselným řádem? Platí, že řád grupy je c*l, kde c je tzv. cofactor a l je nějaké velké prvočíslo. Takže abychom se nemuseli babrat s neprvočíselným řádem, vybereme si generátor podgrupy, který bude mít prvočíselný řád l, pak platí, že řád křivky = cofactor * řád generátoru. Pro mnoho aplikací křivky tohle funguje fajn. Třeba tohle je důvod, proč když generujete privátní klíč pro Curve25519, tak vynulujete nejnižší 3 bity, aby vám vaše body spadly do podgrupy prvočíselného řádu l místo celé grupy křivky, které má řád 8*l. Jinak má Curve25519 podgrupy velikosti 1, 2, 4, 8, l, 2l, 4l, 8l.

Problém s neprvočíselnou grupou - small order attack, ByteCoin/Monero hack

Ten zmíněný problém s neintuitivností grupy s neprvočíselným řádem se prakticky krásně ukázal v chybě v CryptoNote kryptoměnách - Monero, ByteCoin. Slajdy z mé přednášky o této chybě najdete zde (sorry za ten site, ale na abclinuxu nelze nahrávat přímo PDF do přílohy).

Chyba ve zkratce

CrytoNote protokol používá tzv. ring signature, která má za účel skrýt skutečného příjemce zkombinováním několika veřejných Curve25519 klíčů. A zde nastává ten problém. Protože do rovnice vstupuje veřejný klíč od útočníka (bod na křivce Curve25519) nazvaný key image, tak může mít malý řád (1, 2, 4, 8), protože nepřísluší k nějakému privátnímu klíči, kterému se při generování vynulují nejnižší tři bity (aby spadnul do té podgrupy s prvočíselným orderem l).

Chyba v implementaci byla, že nekontrolovala, zda vstupní má řád l a leží "na té správné podgrupě". Výsledkem byl doublespend v ByteCoinu, který udělali sami developeři, protože se stal v čase, kdy na vulnerability report bylo embargo a jedině admini o tom věděli. V těch slajdech mám im vymenovány ty transakce a ty body nízkého řádu, "prošel" jsem blockchain, abych je našel - je tam i Python skript na hledání těchto transakcí.

Co dodnes nechápu, jak je možné, že po provedení tohodle útoku stoupla cena ByteCoinu místo aby klesla, a celkem znatelně :D Go figure...

Převoditelnost (twisted) Edwards, Montgomery a Weierstrassových křivek

Zde si ukážeme, proč mají ty Edwards a Montgomery curves typicky neprvočíselný řád. Jak sme si již ukázali, Montgomeryho křivka je převoditelná na Weierstrass s trochou počítání. Zde si připomenem, že řád grupy je počet prvků grupy a řád prvku je "počet opakování" sčítání prvku sebe se samým, dokud se nedostaneme k identitě (neutrálnímu prvku/bodu v nekonečnu/"nule"). Dále platí (z paperu o Twisted Edwards Curves):

Věta 3.2: Každá Montgomeryho křivka nad polem charakteristiky != 2 lze převést na Twisted Edwards křivku. Jinak řečeno, s malou manipulací s koeficienty můžeme převádět Montgomery křivky na Twisted Edwards křivky tam a zpátky. Je to dobré třeba kvůli tomu, co se nám nad kterou formou lépe počítá. Podmínka, že pole nesmí být charakteristiky 2 značí, že to nesmí být nad GF(2^n), což jsou polynomy s koeficienty z množiny {0, 1}. Velmi zjednodušeně řečeno, GF(2^n) vypadá jako vektory bitů. V dnešní době se stejně moc nepoužívají, protože pro křivky nad polemi charakteristiky 2 se našlo mnoho efektivních útoků.

Věta 3.3: Ať opět máme pole k charakteristiky != 2. Libovolná křivka E nad tímhle polem k je "biracionálně ekvivalentní" Edwardsově křivce nad polem k právě když obsahuje bod řádu 4. Jinak řečeno, obecná křivka ve Weierstrassově forme je převeditelná na Edwardsovu křivku (tu jednodušší, která je podmnožinou twisted Edwards) tam a zpátky právě když má bod řádu 4 (opět s trochou "šachování s koeficientmi").

Věta 3.4: Ať máme pole k s počtem prvků, kdy po dělení #k/4 zůstatek 3 (#k = 3 mod 4). Pak každá obecná Weiestrassova křivka E nad tímhle polem k je "biracionálně ekvivalentní" Edwardsově křivce nad polem k. Jinak řečeno, obecná křivka ve Weierstrassově forme je převeditelná na Edwardsovu křivku (tu jednodušší, která je podmnožinou twisted Edwards) tam a zpátky právě když počet prvků pole po dělení 4-ma má zbytek 3.

Jak ale uvidíme dále, nemůžeme to zobecnit pro pole, kde po dělení jeho velikosti 4-ma nám zůstane zbytek 1.

Věta 3.5: Ať máme pole k s počtem prvků, kdy po dělení #k/4 zůstatek 1 (#k = 1 mod 4). Nad tímto polem máme obecnou Weierstrassovou křivku E. Zbytek předpokladů si přečtěte v původním zdroji, protože bych sem musel copypastovat hodně kontextu. Hlavní pointa je, že pak právě jeden z dvojice křivka E a její netriviální kvadratický twist je "biracionálně ekvivalentní" s nějakou Edwardsovou křivkou a obsahuje bod řádu 4. Jako příklad je to vidět u Curve41417, kde cofactor křivky je 4 a její twist má cofactor 8. To je rozdíl proti větě 3.4, kde vidíme, že jí nelze generalizovat.

Navíc tato věta je skvělým příkladem neintuitivnosti grup s neprvočíselným řádem. Křivka E i její kvadratický twist obsahují podgrupu izomorfní s Z/2Z ⨯ Z/2Z, neboli F4. Tahle podgrupa má za následek, že cofactor i řád křivky je násobkem 4, ale křivka nebo její twist nemusí obsahovat prvek řádu 4. Totiž Z/2Z ⨯ Z/2Z má 4 prvky (řád grupy 4), ale neobsahuje prvek řádu 4, jenom 1 prvek řádu 1 (identita) a 3 prvky řádu 2.

Shrnutí

Zde vidíme, proč Montgomeryho křivky a twisted Edwards křivky nemají prvočíselný řád, ale obsahují typicky bod řádu 4. Není to úplně ideální, ale vyvažuje to jiné implementační nepříjemnosti, a při správném pochopení je jednodušší se bodu s nízkým řádem vyvarovat, než-li vytvářet constant-time algoritmy pro aritmetiku na Weierstrassových křivkách.

       

Hodnocení: 100 %

        špatnédobré        

Tiskni Sdílej: Linkuj Jaggni to Vybrali.sme.sk Google Del.icio.us Facebook

Komentáře

Vložit další komentář

14.2.2018 22:45 Banán
Rozbalit Rozbalit vše Re: Eliptické křivky - vztah Weierstrass, Montgomery, Edwards
WTF
JiK avatar 15.2.2018 00:13 JiK | skóre: 8 | blog: Jirkoviny | Virginia
Rozbalit Rozbalit vše Re: Eliptické křivky - vztah Weierstrass, Montgomery, Edwards
Hluboký respekt. Myslel jsem, ze takoví lidé sem uz nechodí.
16.2.2018 10:36 trekker.dk | skóre: 71
Rozbalit Rozbalit vše Re: Eliptické křivky - vztah Weierstrass, Montgomery, Edwards
Co dodnes nechápu, jak je možné, že po provedení tohodle útoku stoupla cena ByteCoinu místo aby klesla, a celkem znatelně :D Go figure...

"Vykradli mi bitcoiny" - tomu každý rozumí - Bitcoin je špatný, nechi ho

"[spousta povídání a technikálií s dost vysokou matematikou]" - eeeeehm?
Quando omni flunkus moritati
16.2.2018 15:28 *
Rozbalit Rozbalit vše Re: Eliptické křivky - vztah Weierstrass, Montgomery, Edwards
>Go figure...
No success, please help.
17.2.2018 10:47 Petr
Rozbalit Rozbalit vše Re: Eliptické křivky - vztah Weierstrass, Montgomery, Edwards
Bavi te krypto? Rad ti udelam pracovni nabidku pokud jsi dobry.

Založit nové vláknoNahoru

ISSN 1214-1267   www.czech-server.cz
© 1999-2015 Nitemedia s. r. o. Všechna práva vyhrazena.