Całość z kawałków
Kontynuacja wpisu Hasła maskowane inaczej. Załóżmy, że mamy sekret:
123456
oraz dysponujemy następującymi hasłami jednorazowymi:
2346 356 125 236
Czy kolejność, w jakiej będziemy brać pod uwagę poszczególne hasła jednorazowe wpływa na efektywność odzyskiwania sekretu?
Pierwsze pytanie, na ile sposobów można ułożyć poszczególne hasła jednorazowe w maski? Długość sekretu to 6 znaków, przyjmijmy więc, że zadanie to sprowadza się do wyboru k numerów z zakresu 1-6 (n elementów), które będą określały pozycje znaków w masce. Oczywiście wybierać można bez powtórzeń. Są to kombinacje bez powtórzeń, tak więc ilość generowanych masek określamy ze wzoru:
n!/k!(n-k)!
Ilość możliwych kombinacji wynosi więc (w zależności od ilości wybieranych elementów, która w tym wypadku odpowiada długości hasła jednorazowego):
1 6 2 15 3 20 4 15 5 6 6 1
Ponieważ chodzi mi tutaj o ograniczenie ilości obliczeń, chcę ograniczyć ilość “możliwych” masek. Ilość ta jest najmniejsza dla najkrótszych i najdłuższych przypadków. W tym wypadku najdłuższe hasło jednorazowe ma 4 znaki, daje to więc 15 możliwych masek. Na początek.
Pozostałe hasła jednorazowe mają długość 3 znaków, tak więc każde z nich można ułożyć na 20 sposobów. Maksymalna ilość możliwych sekretów uzyskana po kroku drugim wynosi 15 * 20 = 300. Oczywiście w rzeczywistości jest ich dużo mniej, bo nie każda para pozwala na wygenerowanie “sensownej” maski.
Czy w tej chwili warto wybrać hasło jednorazowe bardziej, czy mniej podobne do hasła początkowego? Wydaje mi się, że w tym przypadku dobrze jest wybrać hasła odległe, zawierające jak najmniej wspólnych znaków. Dlaczego?
Porównajmy hasła jednorazowe 125, 356 i 234 dla przykładowej maski:
2346
Dla hasła 125 istnieje tylko jeden możliwy produkt:
125346
Dla hasła 356 też istnieje tylko jeden możliwy produkt:
324346
Dla hasła 234 możliwości jest więcej:
223346 _23346 2346
“Skrzyżowanie” ze sobą hasła 2346 oraz 234 w żaden sposób nie ogranicza ilości możliwych sekretów, zwiększa tylko ilość pracy, który w kolejnym kroku trzeba wykonać.
Można tu posłużyć się następującym rozumowaniem (szacowanie bardzo z góry). Dla maski 2346 pozostają dwie “wolne” pozycje. Znak z kolejnego hasła jednorazowego (np. 234) możemy wstawić, jeśli pozycja jest “wolna” lub na określonej pozycji znajduje się już taki znak. Im mniej pozycji, na które można wstawić znaki, tym mniej możliwości ich ustawienia.
Pomińmy w tej chwili na moment wymaganie, by znaki były wstawiane w (odpowiedniej) kolejności. Dla maski 2346 oraz hasła 234 zbiór dopuszczalnych pozycji zawiera:
- 1 – bo pozycja jest “wolna”,
- 2 – bo występuje tu znak 2, który występuje również w haśle jednorazowym,
- 3 – bo pozycja jest “wolna”,
- 4 – bo występuje tu znak 3, który występuje również w haśle jednorazowym,
- 5 – bo występuje tu znak 4, który występuje również w haśle jednorazowym,
Analogiczny zbiór dla hasła jednorazowego 356 zbiór tych pozycji jest mniejszy:
- 1 – bo pozycja jest wolna,
- 3 – bo pozycja jest wolna,
- 6 – bo występuje tu znak 6, który występuje również w haśle jednorazowym,
W pierwszym przypadku mamy więc 5 możliwych pozycji, w drugim – 3. W obu przypadkach ilość wybieranych elementów to 3 (długość hasła jednorazowego). W pierwszym przypadku daje to 10 możliwości, w drugim tylko jedną możliwość. W obu przypadkach ilość ta może być dalej redukowana przez dodatkowe wymagania, choćby kolejność występowania znaków.
Swoje “eksperymenty myślowe” wspieram eksperymentami praktycznymi. Nie pozostaje mi w takim razie nic innego, niż dopisać w moim skrypcie testowym funkcję sortowania haseł jednorazowych, która:
- wybiera hasło startowe h1 (najdłuższe z haseł jednorazowych),
- wybiera najdłuższe hasło kolejne hN takie, dla którego część wspólna (występujące znaki) w h1 do h(N-1), jest najmniejsza,
Ciekawe jak teoria sprawdzi się w praktyce ;)
Całość sprawdzam na sekrecie długości 15 znaków, maski pochodzą z pewnego, prawdziwego źródła. Eksperyment (jego wyniki) w praktyce wygląda tak... Posortowana już lista haseł jednorazowych (na wejściu 10 losowych masek):
['OgeOkmosk', 'Ogdykausk', 'Odyeamok', 'OgOkmusk', 'gdykaou', '6OAeOks', 'OAdekos', 'gdyOao', 'gAyOk', 'OAeO']
Na wyjściu otrzymuję listę możliwych haseł:
6OgAdyeOkamousk
A wszystko to w czasie:
TimeThis : Command Line : masked2.py TimeThis : Start Time : Mon Jan 09 20:33:59 2012 TimeThis : End Time : Mon Jan 09 20:36:14 2012 TimeThis : Elapsed Time : 00:02:15.501
Ten sam przypadek z nieco inną listą danych na wejściu:
['gAdeOkmouk', 'gdyOkmusk', 'OgdyOmou', 'OAdeOaok', 'OyOamsk', '6OAeOks', 'yekamu', '6yeOmo', 'Oyauk', 'Aeao']
Wynik (a to niespodzianka):
6OgAdyeOkamousk
Wszystko to w (lepszym) czasie:
TimeThis : Command Line : masked2.py TimeThis : Start Time : Mon Jan 09 20:37:38 2012 TimeThis : End Time : Mon Jan 09 20:38:37 2012 TimeThis : Elapsed Time : 00:00:59.085
Teraz przykład dla innego sekretu (pozostałe warunki takie same):
['aSyfipDyji', 'vyfiaDbji', 'Jvyfipybj', 'avfiybi', 'JffaDji', 'avyiybi', 'vSfipy', 'avyaj', 'yiybi', 'ypDy']
JavSfyfipaDybji JavSfyfiapDybji JavSyfifapDybji JavSyffipaDybji JavSyfifpaDybji JavSyffiapDybji JavSyfipfaDybji JavfSyfipaDybji JavfSyfiapDybji JafvSyfipaDybji JafvSyfiapDybji JfavSyfipaDybji JfavSyfiapDybji aJfvSyfipaDybji aJfvSyfiapDybji aJvSyfifpaDybji aJvSyfifapDybji aJvSyffiapDybji aJvSfyfipaDybji aJvSfyfiapDybji aJvSyfipfaDybji aJvSyffipaDybji aJvfSyfipaDybji aJvfSyfiapDybji
TimeThis : Command Line : masked2.py TimeThis : Start Time : Mon Jan 09 20:39:59 2012 TimeThis : End Time : Mon Jan 09 20:40:35 2012 TimeThis : Elapsed Time : 00:00:35.891
Jak widać w tym przypadku nie udało się ustalić jednoznacznie sekretu na podstawie dostępnych danych. A ten przypadek jest jeszcze bardziej pechowy:
['vSyfiybi', 'JSffiDyb', 'avSfpDbi', 'JffiDy', 'Jvfbji', 'vSayi', 'aSaji', 'JaSfy', 'JSaj', 'Sfpy']
JavSayfpfiDybji JavSyfpafiDybji (... w sumie 49 możliwych haseł ...)
TimeThis : Command Line : masked2.py TimeThis : Start Time : Mon Jan 09 20:41:13 2012 TimeThis : End Time : Mon Jan 09 20:51:56 2012 TimeThis : Elapsed Time : 00:10:42.430
...choć i dla niego czasami świeci słońce (bardziej):
['avSffipDyj', 'JaSyfapyb', 'aSyfipyi', 'avSfapDb', 'avSfpDy', 'ayfpji', 'JyffDb', 'vSfiyb', 'vaybj', 'ffpDb']
JavSyffiapDybji JavSyffaipDybji JavSyfafipDybji
TimeThis : Command Line : masked2.py TimeThis : Start Time : Mon Jan 09 20:54:08 2012 TimeThis : End Time : Mon Jan 09 20:54:31 2012 TimeThis : Elapsed Time : 00:00:22.687
W tym wypadku udało się bardzo szybko ustalić trzy możliwe sekrety.
Ten sam przypadek, gdy mogę wybierać spośród wszystkich istniejących w systemie masek dla tego sekretu:
['vSyfiaDybi', 'JvSyfiaDbj', 'Javyfiapji', 'JaSfiaDbji', (...) ]
JavSyffiapDybji
TimeThis : Command Line : masked2.py TimeThis : Start Time : Mon Jan 09 20:56:27 2012 TimeThis : End Time : Mon Jan 09 20:56:55 2012 TimeThis : Elapsed Time : 00:00:27.844
Jak na razie moja ciekawość odnośnie tego, jak bardzo skomplikowane jest odtworzenie całości sekretu z jego poszczególnych kawałków, została zaspokojona. Być może do tematu powrócę by poszukać takich parametrów “masek”, by odzyskanie sekretu w opisany tutaj (i wcześniej) sposób, kosztowało jak najwięcej. Inna sprawa, że jednocześnie można poprawić algorytm poszukiwania rozwiązania na taki, który jest mniej naiwny. Komuś się nudzi? :)
P.S. Jak się można było spodziewać, w moim PoC (funkcja sortowania haseł) były błędy. Konkretnie dwa, przez co hasła jednorazowe były sortowane nie do końca zgodnie z moimi zamierzeniami. Jaka różnica? Cóż, powiedzmy, że czas wykonania ostatniego przykładu teraz wygląda tak:
['vSyfiaDybi', 'JaSffipybj', 'vSaj', 'JSaj', 'ypDy', (...)
JavSyffiapDybji
TimeThis : Command Line : masked2.py TimeThis : Start Time : Mon Jan 09 21:37:06 2012 TimeThis : End Time : Mon Jan 09 21:37:14 2012 TimeThis : Elapsed Time : 00:00:08.218
Najlepszy dowód na to, że kolejność MA znaczenie :)
Oryginał tego wpisu dostępny jest pod adresem Całość z kawałków
Autor: Paweł Goleń