rtl-sdr и разни въпроси / Техника / Радио комуникации

Най-най-най-първоначалната ми идея беше да се занимавам с криптографията, конкретно A5/1.

Може би последното, което има връзка е че FC0013 тунера в Hama-та е гаден - от 848.00 до 849.90 има "дупка" (не работи). Имам подозрения че над 950 също не работи, защото няма никаква активност от 950 до 960, това би трябвало да е честотната лента лицензирана на Глобул, та последните (апропо бивш мой работодател ) са "имунизирани" срещу моите занимания :)

Uplink активност абсолютно не виждам на радио скенера, а от 920 до 928 имам нещо като "огледален образ" на 940-948, много странно, не знам хардуерен бъг ли е или е проблем в rtl-sdr. Предвид това, единствено за няколкото клетки на Мтел и Виваком мога да съм сигурен че ги хващам на честотата, на която му казвам - защото ARFCN-то се съдържа в system information фреймовете и съвпада.

Що се отнася до криптографията, ако случайно някой се интересува, накратко нещата стоят така: А5/1 е поточен шифър с 64-битов ключ. Поточните шифри може да се разглеждат (опростено) като генератор на псевдослучайни числа, който се seed-ва с ключа и последователно генерираните случайни стойности смесваме (xor-ваме) с плейнтекста, за да получим криптираното, декриптирането се състои в seed-ване на PRNG-то и xor-ване на криптираното със същата генерирана последователност (наречена keystream)

Тривиалната брутфорс атака съответно изисква 2^64 операции и някакъв известен плейнтекст (т.е поне 64 последователни бита от криптираните данни трябва да са известни). Това е относително лесно ако вземем предвид че се изпращат служебни феймове с частично или напълно известно съдържание. Лошото е че 2^64 операции са доста. Тривиалната, доста неоптимизирана single-threaded имплементация на A5/1 върху моя AMD FX-6100 докарва около 3 милиона операции (key-ване, 100 пъти clock-ване и генерирани 1 burst (114 бита) изход). С тази скорост, брутфорс атаката ще изтръшка keyspace-а за около 200.000 години. Разбира се, имплементацията може да се thread-не, за да утилизира 6-те ядра (да речем 6 пъти подобрение, макар и няма да е толкова), може доста да се оптимизира (има очевидни неща). Нека го подкараме дори 100 пъти по-бързо върху процесора, тогава атаката няма да отнеме 200.000 години, ще отнеме 2000. Съответно 2000 такива процесора като моя ще го изтръшкат за 1 година. Алтернативно, можем да използваме високопаралелен хардуер, примерно видеокарта, още не съм го направил, но първоначалните ми предвиждания са че high-end карта като 7970 ще докара около 1 милиард операции в секунда, брутфорс атаката съответно "само" за около 593 години, доста непрактично.

Разбира се има разни по-преки пътища. Например логично е че ако имаме known plaintext, можем лесно да получим (част от) keystream-а. Използвайки keystream-а, можем да се опитаме да отгатнем състоянието на алгоритъма (състоянието е 64-битово, 3 LFSR регистъра, съответно 19,22 и 23 битови). Това беше моята "гениална" идея - брутфорсваме част от състоянието и генерираме последователно изходния keystream, като той трябва да съвпада с истинския, което евентуално отхвърля бързо доста кандидат-ключове. Първоначалната ми идея беше че така ще сведем комплексността на атаката до някъде 2^45, което означава малко над 10 часа с видеокарта от сорта на 7970. Обаче греда - проблемът е в това че 3-те LFSR регистъра не се клокват на всяка стъпка, а това става по т.нар "majority rule", демек дали регистъра ще се клокне не зависи само от clock бит-а, но и от съответните битове на другите два регистъра. Това вдига комплексността на атаката доста, някъде към 2^51, което означава над седмица, не ми допада като идея.

Та хванах и се зачетох във всичко, което успях да намеря на тема криптоанализ на A5/1. Първите писания са от един пич от Сърбия, Голич, който е имал същата като моята идея с частичното брутфорсване на състоянието, само че по-малко по-извратен начин (представя го като система от линейни уравнения и я решава чрез Гаусова елиминация), по някакъв начин докарва сложност от 2^45, обаче най-вероятно на по-висока цена, последвано от ровене в някаква предварително преизчислена таблица, която е огромна. Но най-важното, което пичът е открил е че алгоритъмът може да се "подкара назад", т.е ако имаш състоянието към някакъв момент, можеш лесно да го "обърнеш" до състоянието в самото начало, не се изисква допълнителна информация. Така ако на произволен момент имаш текущото състояние, то лесно можеш да добиеш ключа с който е инициализиран алгоритъма.

След това първото велико писание на Shamir и компания, където на практика се предлага варианта с TMTO атаката (rainbow таблици) и всичко след това се върти около тази идея. Съответно изпълнението на Karsten Nohl през 2009? 2010? е просто прилагане на тези идеи на практика, с разни подобрения, които вече са били известни. 99.99% от всичкия research около А5/1 в последните години се върти и е зациклил около TMTO атаката.

Има няколко проблема с това. Изчислителното време за първоначалното пресмятане на таблиците е огромно, таблиците са големи (2 терабайта и далеч не покриват цялото множество, макар че това се коригира ако имаш повече known plaintext)....а да, и споменах ли че за да имаш прилична вероятност за успех ти трябват поне 4 burst-а plaintext данни....което може и да не е постижимо (в доста случаи не е). При мен стои и друга дилема - със скоростта с която тегля тези торънти с таблиците (няма много seeder-и мамка му), не знам дали няма да ги сметна по-бързо, отколкото да ги сваля, хех