it-swarm-eu.dev

Praskání lineárního kongruenciálního generátoru

Nedávno jsem poslouchal zabezpečení, které je nyní podcastem, a oni při tom zmínili, že lineární kongrunenciální generátor (LCG) je bezva. Používám LCG v prvním ročníku statistiky výpočetní třídy a myslel si, že praskání by způsobilo pěkný „extra“ problém.

Existují nějaké pěkné způsoby, jak prasknout LCG, které nezahrnují hrubou sílu?


Nejsem si jistý, zda je tato otázka OT, ale nebyl jsem si jistý, kde kam poslat otázku. Moje značky také nejsou příliš užitečné, protože nemám dostatek opakování k vytvoření nových značek.

34
csgillespie

Ano. Existuje velmi účinný způsob, jak rozbít lineární kongruenciální generátor.

Lineární kongruenciální generátor je definován sn + 1 = a sn + b mod m, kde m je modul. Ve své nejjednodušší podobě generátor právě vydává sn jako npseudonáhodné číslo. Pokud útočník pozná m a a, b, není známo, Thomas popsal, jak jej rozbít.

Pokud není znám žádný z a, b, m, můžeme stále rozbít lineární kongruenciální generátor, a to nejprve zotavením m. Je zajímavé cvičení odvodit, jak toho dosáhnout efektivně; to se dá udělat. Ukážu, jak níže; nečtěte dál, pokud si to chcete vyzkoušet sami.

Chcete-li obnovit m, definujte tn = sn + 1 - sn a n = |tn + 2 tn - t2n + 1|;; pak s velkou pravděpodobností budete mít m = gcd (u1, u2, ..., u10). 10 je libovolné; pokud to uděláte k, pak je pravděpodobnost, že se to nezdaří, exponenciálně malá v k. Mohu sdílet ukazatel, proč to funguje, pokud má někdo zájem.

Důležitou lekcí je, že lineární kongruenciální generátor je nenávratně nezabezpečený a zcela nevhodný pro kryptografické použití.


Přidáno: @AviD mě bude ještě víc nenávidět :), ale tady je matematika, proč to funguje, pro ty, kdo o to požádali.

Hlavní myšlenka: tn + 1 = sn + 1 - sn = (a sn - b) - (a sn-1 - b a sn - tak jakon-1 = a tn) == mod m a tn + 2 = a2 tn mod m a tn + 3 = a3 tn mod m. Proto tn + 2 tn - tn + 12 = 0 mod m, tj. |tn + 2 tn - tn + 12| je náhodný násobek m. Fakt teorie šikovných čísel: gcd dvou náhodných násobků m bude m s pravděpodobností 6/π2 = 0,61; a pokud vezmete gcd z nich k, tato pravděpodobnost se dostane velmi blízko k 1 (exponenciálně rychle v k). Je to v pohodě, nebo co?

36
D.W.

Lineární kongruenciální generátor je lineární, což by mělo říkat všechno.

Konkrétně máte stav s, který je aktualizován s: s ← jako + b mod w, pro dvě konstanty a a b a vhodný modul w (obvykle 232: s, a a b jsou 32bitová slova); výstup spočívá v postupných hodnotách s. Pokud máte tři po sobě jdoucí výstupy (s, s1 a s2), dostanete dvě lineární rovnice ve dvou neznámých (a a b), které lze snadno vyřešit elementární aritmetikou.

To lze rozšířit na varianty, kde dostanete pouze část hodnot s, možná ne po sobě. Pokud jsou a a b dvě 32bitové konstanty, potřebujete pouze asi 96 bitů na výstup, abyste mohli konstanty znovu kompilovat.

18
Thomas Pornin

Jiná metoda řešení pro m pochází z tohoto papír .

Tato metoda v podstatě využívá skutečnosti, že lineární kongruenciální generátor dramaticky selže v testu letadel. Determinant matice 3x3 pomocí 4 výstupů je násobek m .

Gcd dvou násobků ( n_1 a n_2 z m je m , pokud x_1 = n_1 / m a x_2 = n_2 / m jsou spolupředseda.

Pravděpodobnost, že celá čísla k jsou ko-hlavní, je dána 1/ζ (k), takže pravděpodobnost, že x_1 a x_2 jsou spolu-prvočísla 1/ζ (2) nebo 6/π ^ 2, asi 61%.

Jak řekl @Thomas, jednou m se zjistí, že zbytek problému je snadný.

3
Jon Takagi