Nie mogę natrafić na artykuł, ale jestem prawie pewien że coś takiego było.
Otóż jakaś część generowanych kluczy, chyba jedna czwarta daje się złamać.
Spowodowane jest to tym że nie ma niestety instrukcji procesora dającej
fizycznie losowe dane, a zamiast tego mamy generator pseudolosowy, poza tym
ustawiany też nawet jakby losowo to z małą ilością bitów losowych. Więc
przykładowo, klucz nie do złamania potrzebuje np. 2^256 operacji a tymczasem
wystarczy rząd 2^32 znając jaki to generowator pseudolosowy generował.

do góry

On Thursday, 4 April 2013 15:51:27 UTC+2, Borneq wrote:
> Nie mogę natrafić na artykuł, ale jestem prawie pewien że coś takiego było.
> Otóż jakaś część generowanych kluczy, chyba jedna czwarta daje się złamać.
> Spowodowane jest to tym że nie ma niestety instrukcji procesora dającej
> fizycznie losowe dane, a zamiast tego mamy generator pseudolosowy, poza tym
> ustawiany też nawet jakby losowo to z małą ilością bitów losowych. Więc
> przykładowo, klucz nie do złamania potrzebuje np. 2^256 operacji a tymczasem
> wystarczy rząd 2^32 znając jaki to generowator pseudolosowy generował.

Nic nie stoi na przeszkodzie aby generator liczb losowych do komputera podłączyć.

AdamK

do góry

Użytkownik "Adam Klobukowski" <a...@g...com> napisał w
wiadomości news:2c7b7126-0fb3-435f-94eb-5993f95cb358@googlegrou
ps.com...
> Nic nie stoi na przeszkodzie aby generator liczb losowych do komputera
> podłączyć.

Można wykorzystać zdarzenia uderzenia w klawisze i przesunięcia myszy.
Uwaga: to w jaki klawisz uderzymy nie jest losowe, a losowe są jedynie
ostatnie bity licznika rozkazów TSC. Przy czym lepsze rezultaty dałoby gdyby
to robił system na fizyczne przerwanie (chyba w Linuxie tak jest), natomiast
tu mamy gromadzenie do bufora i mierzymy w tym czasie kiedy system
obłsuguje, co nie przeszkadza jednak w losowości; tylko pewna część bitów
jest losowa, jeżeli zdarzenie przychodzi co 0.1 s to losowe są bity
oznaczające czas znacząco mniejszy niż 0.1 s. Coś takiego pisałem, nie
pamiętam jaka ilość bitów/sekundę udało się uzyskać z klawiatury, z myszką
można podobnie.
Podłączany generator przez USB też chyba nie jest szybki - kilkaset bitów/s
Gdyby była instrukcja, mogłaby dawać miliony bitów/s.
Ale z drugiej strony generatorowi dostarczamy raz np. 128 bitów, a potem on
juz działa

do góry

Użytkownik "Borneq" <b...@a...hidden.pl> napisał w wiadomości
news:kjk0h1$f8f$1@node2.news.atman.pl...
> Nie mogę natrafić na artykuł, ale jestem prawie pewien że coś takiego
> było. Otóż jakaś część generowanych kluczy, chyba jedna czwarta daje się
> złamać. Spowodowane jest to tym że nie ma niestety instrukcji procesora
> dającej fizycznie losowe dane, a zamiast tego mamy generator pseudolosowy,
> poza tym ustawiany też nawet jakby losowo to z małą ilością bitów
> losowych. Więc przykładowo, klucz nie do złamania potrzebuje np. 2^256
> operacji a tymczasem wystarczy rząd 2^32 znając jaki to generowator
> pseudolosowy generował.

Kiedys dawno temu - dla ciekawości zanalizowałem
sobie jak windows generuje klucz publiczny.

Procedura była mniej więcej taka
tworzono "dane losowe":
nazwa komputera,nazwa użytkownika,wiekosc pamieci dyskowej,
wielkośc pamięci operacyjnej, rozdzielczośc ekranu itd itp -
na końcu coś pseudo losowego tj. data i czas na chwile generacji.

Po wpakowaniu takich danych obszaru pamięci obliczno z tego
skrót - powiedzmy wtedy ( juz nie pmaiętam szczegółów) MD5
i tak powstawała liczb pseudo losowa 128 bitów.
Brano tę liczbe jako punkt startowy dla szukania najbliżeszej liczby pseudo
pierwszej
(np. 128 Bitów) . Potem cos tam przestawniano w tym obszarze pamięci
i liczno znowu MD5 i znowu szukano njabliższej liczby pierwszej.
Takie szczególy, że zapewniano z przodu "11" na dwóch pierwszych bitach
pomijam.

Te dwie liczby mnożono i mieliśmy N dla klucza publicznego.

Jak teraz zuważymy,że dla kogos kto zna te procedurę
odtworzenie jej nie jest problemem bo większąśc tych danych
każda przeglądarka rozdaje za darmo to chyba tylko
mikrosekundy czasu było losowe. Ale jak kto miał dostęp
do rejestru lub pliku z kluczem to razem z kluczem miał pewnie
i czas jego powstania :))))

Diabeł tkwi w szegółach jak pisał Ph il Zim_mer mann dopuki
nie przekonano go by przestał sie wymądrzać :))))))

pozdrawiam

do góry

On 04.04.2013 15:51, Borneq wrote:
> Nie mogę natrafić na artykuł, ale jestem prawie pewien że coś takiego
> było.

Jestem prawie pewien, że nie było czegoś takiego. były natomiast faile w
debianie i w BSD gdzie "sprytny" programista upośledził przypadkowo
generator pseudolosowy.

Otóż jakaś część generowanych kluczy, chyba jedna czwarta daje się
> złamać.

12/11

Da się złamać każdy klucz - tylko czas na to potrzebny...

> Spowodowane jest to tym że nie ma niestety instrukcji procesora
> dającej fizycznie losowe dane,

Ależ są. Np w sandy bridge.

> a zamiast tego mamy generator
> pseudolosowy,

Zakładając, że masz generator pseudolosowy inicjalizowany jedynie 64
bitową wartością to i tak masz dość entropii na najbliższe kilka wieków.

> poza tym ustawiany też nawet jakby losowo to z małą
> ilością bitów losowych.

Czyli próbujesz powiedzieć, że większość kluczy zawiera błąd wynikający
z jednego z podstawowych problemów analizowanych w generatorach?

> Więc przykładowo, klucz nie do złamania
> potrzebuje np. 2^256

Gdzie używa się 256 bitowych kluczy?

> operacji a tymczasem wystarczy rząd 2^32 znając
> jaki to generowator pseudolosowy generował.

Jeżeli generator był upośledzony to tak.

--
Pozdrawiam
Michoo

do góry

W dniu czwartek, 4 kwietnia 2013 15:51:27 UTC+2 użytkownik Borneq napisał:
> Nie mogę natrafić na artykuł, ale jestem prawie pewien że coś takiego było.
> Otóż jakaś część generowanych kluczy, chyba jedna czwarta daje się złamać.
Każdy daje się złamać, jeśli dysponujesz dostateczną ilością
pieniędzy i/lub czasu.

> Spowodowane jest to tym że nie ma niestety instrukcji procesora dającej
> fizycznie losowe dane, a zamiast tego mamy generator pseudolosowy, poza tym
> ustawiany też nawet jakby losowo to z małą ilością bitów losowych. Więc
Więc uruchamiasz program, jeździsz myszką po ekranie w tę i nazad, program
co kilka milisekund szczytuje koordynaty myszki, a jeśli koordynaty są
od 2-3 odczytów różne, to zapisuje ich ostatnie bity do pliku - i masz w
pełni losowy zarodek o pseudo random generator.


> przykładowo, klucz nie do złamania potrzebuje np. 2^256 operacji a tymczasem
> wystarczy rząd 2^32 znając jaki to generowator pseudolosowy generował.
Łamanie jest tak samo trudne, jak trudny jest rozkład na czynniki pierwsze.
http://pl.wikipedia.org/wiki/Rozk%C5%82ad_na_czynnik
i#Z.C5.82o.C5.BCono.C5.9B.C4.87_obliczeniowa

Pozdrawiam

do góry

On 2013-04-04, Michoo <m...@v...pl> wrote:
> On 04.04.2013 15:51, Borneq wrote:
>> Nie mogę natrafić na artykuł, ale jestem prawie pewien że coś takiego
>> było.
>
> Jestem prawie pewien, że nie było czegoś takiego. były natomiast faile w
> debianie i w BSD gdzie "sprytny" programista upośledził przypadkowo
> generator pseudolosowy.

Jeśli dobrze pamiętam, to w przypadku Debiana ten "sprytny" programista
najpierw zapytał na liście opiekunów, czy wolno mu.

>> Więc przykładowo, klucz nie do złamania
>> potrzebuje np. 2^256
>
> Gdzie używa się 256 bitowych kluczy?

Na przykład przy szyfrowaniu symetrycznym. Ale tu mowa o liczbie
potrzebnych operacji, a nie o długości klucza. To zupełnie różne rzeczy.
W kryptoanalizie szyfrów asymetrycznych właściwie zawsze stosuje się
metody analityczne, które dają lepsze wyniki niż metoda mastodonta.

--
Secunia non olet.
Stanislaw Klekot

do góry

On 04/04/2013 14:51, Borneq wrote:
> Nie mogę natrafić na artykuł, ale jestem prawie pewien że coś takiego
> było. Otóż jakaś część generowanych kluczy, chyba jedna czwarta daje się
> złamać. Spowodowane jest to tym że nie ma niestety instrukcji procesora
> dającej fizycznie losowe dane

jest taka instrukcja, a nawet dwie. Nowy dodatek, potrwa kilka lat zanim
zacznie być stosowany . Rozdział 9.2 w
http://download-software.intel.com/sites/default/fil
es/m/0/1/9/3/4/45207-319433-013b.pdf
, tutaj szczegóły
http://software.intel.com/en-us/blogs/2012/11/17/the
-difference-between-rdrand-and-rdseed
,
http://software.intel.com/en-us/articles/intel-digit
al-random-number-generator-drng-software-implementat
ion-guide/
, a tutaj artykuł zrozumiały dla wszystkich
http://spectrum.ieee.org/computing/hardware/behind-i
ntels-new-randomnumber-generator/0


B.

do góry

Dnia Thu, 04 Apr 2013 21:04:24 +0100, Bronek Kozicki wyszeptal:

> On 04/04/2013 14:51, Borneq wrote:
>> Nie mogę natrafić na artykuł, ale jestem prawie pewien że coś takiego
>> było. Otóż jakaś część generowanych kluczy, chyba jedna czwarta daje się
>> złamać. Spowodowane jest to tym że nie ma niestety instrukcji procesora
>> dającej fizycznie losowe dane
>
> jest taka instrukcja, a nawet dwie. Nowy dodatek, potrwa kilka lat zanim
> zacznie być stosowany . Rozdział 9.2 w
> http://download-software.intel.com/sites/default/fil
es/m/0/1/9/3/4/45207-319433-013b.pdf
> , tutaj szczegóły
> http://software.intel.com/en-us/blogs/2012/11/17/the
-difference-between-rdrand-and-rdseed
> ,
> http://software.intel.com/en-us/articles/intel-digit
al-random-number-generator-drng-software-implementat
ion-guide/
> , a tutaj artykuł zrozumiały dla wszystkich
> http://spectrum.ieee.org/computing/hardware/behind-i
ntels-new-randomnumber-generator/0

Jest używany, ktokolwiek go potrzebuje to ma. Dodatkowo TPM posiada
generator, którego można użyć i to od dawna. Połowa sprzętu z półki ma
TPMa.

To że nie wszyscy używają hw rng jeszcze nie znaczy, że "nie jest używany"
i "trzeba czekać kilka lat" (bo to taka futurystyczna technologia obiecana
przez kosmitów, dadzą nam jak pokonają kilka lat świetlnych z ich planety).

Kilka lat trzeba poczekać żeby sprawdzić na ile on jest random.
Jakoś mam większe zaufanie dla losowości ruchów fizycznych głowic dysku,
o ile nie potrzeba większej ilości entropii.

--
Edek

do góry

W dniu czwartek, 4 kwietnia 2013 23:19:52 UTC+2 użytkownik Edek Pienkowski napisał:

>
> Kilka lat trzeba poczekać żeby sprawdzić na ile on jest random.
> Jakoś mam większe zaufanie dla losowości ruchów fizycznych głowic dysku,
> o ile nie potrzeba większej ilości entropii.

O ile program nie pracuje na serwerku* z dyskiem SSD.

*) hmm, drogo to wyjdzie, ale pewnie sa zastosowania,
gdzie się opłaca.

pzdr
bartekltg

do góry