Не се паникьосвайте от слабите RSA ключове
Успяхме дистанционно да компрометираме около 0,4% от всички публични ключове, използвани от уебсайтове за SSL. Всички компрометирани ключове бяха генерирани неправилно с помощта на предвидими „случайни“ числа, които също понякога се повтаряха. Общо можем да различим два типа проблеми: ключове, генерирани с предвидима случайност, и подмножество от тези ключове, за които липсата на случайност позволява на атакуващия бързо да факторизира публичния ключ и да получи секретния ключ. С секретния ключ нападателят ще може да се представя за уебсайт и евентуално да може да дешифрира шифрования трафик, насочен към този уебсайт. Разработихме програма, която за няколко часа може да факторизира публичните ключове и да издаде секретни ключове за всички хостове, уязвими на тази атака.
Въпреки това, не се паникьосвайте, тъй като проблемът засяга най-вече вградените системи като рутери и VPN и не засяга пълноценните сървъри. (Както и да е, това със сигурност не е причина да губите пълномощно за електронна търговия, както предлага New York Times). За съжаление открихме устройства с този проблем от почти всеки производител и подозираме, че около 200 000 устройства, представляващи 4,1% от всички ключове в нашите данни, са използвали лоша ентропия за генериране на ключове. Всеки намерен слаб ключ, генериран от устройство, предполага, че целият клас от тези устройства е уязвим за атака, ако бъде правилно анализиран.
Не се притеснявайте, банковият ви ключ най-вероятно е в безопасност.
SSL се използва от всеки голям сайт в Интернет, но както показва нашият анализ, тези ключове не са засегнати от проблемите, описани в тази публикация.
И така, какви сасистеми в риск? Почти всички уязвими ключове са генерирани и използвани във вградени системи като рутери и защитни стени и не са използвани в банкови или имейл уебсайтове. Само един от уязвимите SSL ключове е подписан от CA и вече е изтекъл. Открихме и няколко подписани сертификата, използващи дублиращи се ключове; някои от които са генерирани от уязвими устройства, други са изпратени за подпис от собствениците на сайтове като очевидно слаби, а за някои не можем да измислим добро обяснение.
Всеки знае, че вградените системи имат проблеми с ентропията. Досега обаче не беше ясно колко чести са тези проблеми в реални устройства, свързани с интернет.
Генериране на ключове
Уеб сайтовете и свързаните в мрежа компютри използват криптосистеми с публичен ключ за идентификация. След това ще говорим за типа удостоверяване, когато сървърът предоставя на клиента сертификат, за да удостовери клиента, че той е този, към когото клиентът иска да се свърже. Ако нападателят знае секретния ключ, той може да се представи за реалната система или в повечето случаи да дешифрира трафика между клиента и сървъра.
RSA е най-често използваната криптосистема за тази цел. Защитата на криптосистемата RSA се основава на факторизирането на големи числа. Публичният ключ на RSA се състои от двойка цели числа: публичният експонентeи модулътN, който е произведение на две големи прости числаpиq. Ако противникът може да разложиNобратно вpиq, тогава той може също така да дешифрира всеки текст, шифрован с публичния ключ. Въпреки това, дори и с помощта на най-бързите алгоритми за факторизация, никой все още не е успял да факторизира1024 битов модул.
Важна част от сигурността на ключа е наличието на произволни входни данни на етапа на генериране на ключа. Ако няма достатъчно ентропия в тези входове, тогава атакуващият може да ги познае и по този начин да получи секретния ключ, без болезненото факторизиране на числотоN.
На съвременните компютри и сървъри програмите за генериране на ключове използват случаен вход от различни физически източници (най-често чрез операционната система): мишка, клавиатура, движения на твърдия диск, мрежови събития и други непредсказуеми източници. Въпреки това, ако има малко източници, тогава ентропията няма да е достатъчна и ключът може да бъде уязвим за атака. Събирането на силна ентропия и тестването на нейната сила е много сложен проблем, който е породил много уязвимости през годините.
Две версии на проблема
Както установихме, проблемите с ентропията водят до два различни вида слабости:
Дублирани публични ключове.
Около 1% от всички RSA ключове са възникнали отново, най-вероятно поради проблеми с ентропията. Ако две устройства имат един и същ публичен ключ, тогава те също имат един и същ частен ключ. В действителност всички устройства с един и същи ключ са в една и съща позиция - нападателят може да компрометира най-слабото от тези устройства и да получи ключовете за всички останали. Този проблем е известен отдавна, но досега никой не е документирал в откритата литература колко е широко разпространен.
Ръчно проверихме, че 59 000 ключа са били повторени поради проблеми с ентропията, което представлява около 1% от всички сертификати или 2,6% от всички самоподписани сертификати. Установихме също, че 4,6% от всички устройства (585 000 сертификата) използват сертификатизададено по подразбиране. И въпреки че тези устройства не са използвали ключове, генерирани с лоша ентропия, те са обект на една и съща атака, тъй като секретните им ключове са еднакви за всички модели. Проверихме ръчно всички тези ключове, тъй като голям брой сайтове използват дублиращи се ключове при правилните условия и следователно не представляват риск за потребителя.
Факторизуеми публични ключове.
По-изненадващо открихме, че проблемите с ентропията могат да позволят на отдалечен нападател, без специален достъп, да извади значителна част от всички RSA ключове, използвани в Интернет. Успяхме да факторизираме 0,4% от всички RSA ключове в SSL сертификати. За да направим това, изчислихме най-големия общ делител (gcd) за всички двойки модули от RSA публични ключове в Интернет.
Ние определихме 1724 общи делителя, което ни позволи да факторизираме 24,816 SSL ключа и 301 общи делителя, за да факторизираме 2422 SSH ключа. Това означава, че успяхме да изчислим частни ключове за почти 0,5% от RSA ключовете, използвани за SSL. След това ще обясним как работи нашето изчисление.
Конкретни уязвими устройства
Вградените системи често генерират криптографски ключове при първо зареждане, когато цялото им състояние може да бъде предварително дефинирано фабрично. Което може да доведе до такива проблеми с ентропията, както е описано в това изследване.
Няма да изброяваме имената на устройствата, докато не го направим, но можете да видите някои примери по-долу:
Защитна стена X: 52.055 хоста в нашите SSL данни 6.730 със същите ключове 12.880 с факторизирани ключове
Рутер на потребителско ниво Y: 26,952 хоста в нашите SSL данни 9,345 със същите ключове 4,792 с факторизирани ключове
Решение заотдалечен достъп Z, за предприятия: 1,648 хоста в нашите SSL данни 24 със същите ключове 0 с факторизирани ключове
Как може да стане това?
Не е съвсем очевидно как проблемите с ентропията могат да доведат до проблеми с ключове, които лесно се факторизират. Сега ще обясним защо това е така за нашите по-любознателни читатели.
Ето как един програмист може да генерира модул за RSA: prgn.seed(seed) p = prgn.generate_random_prime() q = generate_random_prime() N = p*q Ако началният елемент за генератор на псевдослучайни числа има предвидима стойност, тогава няколко различни устройства могат да имат един и същ модулN, но ние не мислим един добър генератор на случайни числа може да произведе два различни модулаNсъс същия общ фактор.
Въпреки това, някои реализации добавят допълнителна произволност между генерирането на прости числаpиq, с идеята за повишаване на сигурността: при лоша ентропия това може да доведе до множество устройства с различни модули, състоящи се от едни и същи факториpи различни факториq. Така че можем да факторизираме двата модула с помощта на GCD: p = gcd(N1, N2).
Генерирането на RSA ключ в OpenSSL работи по следния начин: след всяко използване на произволни битове от ентропийния пул за генериране на прости числаpиq, текущото време в секунди се добавя към пула. Много, но не всички, уязвими ключове са генерирани с помощта на OpenSSL и OpenSSH, който използва OpenSSL за генериране на RSA ключове.
Изчисляване на GCD за всички двойкиключове
Ако някоя двойка RSA модулиN1иN2има един и същ коефициент, тогава можете просто да факторизирате двата модула с помощта на gcd. На моя настолен компютър операцията по изчисление на gcd за два 1024 RSA модула отнема около 17 микросекунди.
За математиците сега ще обясня как можем да използваме тази идея, за да факторизираме голям брой ключове.
Един прост подход към факторизацията на ключа включва изчисляване на gcd за всяка двойка RSA единици. Но ако преценим колко време ще отнеме тези изчисления, получаваме около 24 години на моя настолен компютър.
Основното математическо наблюдение в този проблем е, че можем да изчислим gcd за модулаN1заедно с всички други модули, използвайки следното уравнение: gcd(N1, N2 . Nm) = gcd(N1, (N1 * N2 * . Nm mod N1^2)/N1) ключове, число, състоящо се от 729 милиона цифри. Успяхме да факторизираме всички SSL данни за 18 часа на едноядрен процесор и да факторизираме SSH данни за 4 часа на 4-ядрен процесор.