Description of GSM and its hacking
Introduction
Somehow after the New Year, I read about the standards used in GSM. It was especially fun after reading the words of James Moran, director of the unit responsible for security and protection of the system from fraud in the GSM consortium: “No one in the world has demonstrated the ability to intercept calls on the GSM network. This is a fact ... As far as we know, there is no equipment capable of such an interception. " And what nonsense do you sometimes find on the Internet about GSM.
But the GSM standard (Global System for Mobile communications) today owns 80% of the global digital mobile communications market. And it is used by over 250 million people. Duck why not take advantage of them? Hmm ... a question of ethics or finding a radio scanner (is this legal?). Although the operators in Russia are allowed to use stolen phones, and their protection is at the heart of GSM, and for this there are black lists of International Mobile Equipment Identity (in the West). Or maybe those who sell stolen phones are sharing with them?
GSM protection and how it was created
In principle, according to its concept, the GSM digital mobile communication system could well be extremely secure. It is based on a set of documents called the “Memorandum of Understanding the GSM Standard” or the MoU Groupe Special Mobile standard. This Memorandum was prepared at the end of the Cold War on the initiative of leading telecommunication companies in Western Europe. The European Institute of Telecommunications Standards (ETSI) developed technical documentation for GSM, and NATO special services took an active part in creating a security scheme that was generally designed to protect the new system from interception, wiretapping and fraud.
The basis of the GSM security system is composed of three secret algorithms (not officially disclosed to this day, communicated only to those who need it by necessity - equipment suppliers, telecom operators, etc.):
A3 - authentication algorithm that protects the phone from cloning;
A8 is an algorithm for generating a crypto key, in fact a unidirectional function that takes a fragment of the output from A3 and turns it into a session key for A5;
A5 - the actual encryption algorithm for digitalized speech to ensure the confidentiality of negotiations. GSM uses two main varieties of the algorithm: A5 / 1 - the "strong" version of the cipher for selected countries and A5 / 2 - weakened for everyone else (for Russia).
Mobile stations (telephones) are equipped with a smart card containing A3 and A8, and the phone itself has an ASIC chip with the A5 algorithm. Base stations are also equipped with an AS5 chip with A5 and an “authentication center” using A3-A8 algorithms to identify the mobile subscriber and generate a session key.
All this architecture, with proper execution and high-quality algorithms, is designed to guarantee reliable user authentication, protecting mobile stations from cloning and other fraud methods, as well as high-quality encryption of confidential negotiations. As a matter of fact, this is exactly what is declared by companies successfully engaged in the deployment of GSM worldwide and already embracing convenient communication services, according to various estimates, from 210 to 250 million people on the planet.
But the reality is that the special services involved in protecting government communications are also involved in activities of the opposite kind: interception and decryption of communications for intelligence purposes. For this reason, as eyewitnesses testify, considerable passions raged around the degree of protection of GSM, since the special services of NATO countries had rather different points of view on this matter. Germany insisted on strong algorithms, since it had the longest border with the communist bloc, while other countries were inclined towards a weakened version. In the end, the French development was chosen as the basis of the crypto scheme for A5.
Description of GSM encryption algorithms and hacking
A5 implements stream cipher based on three linear shift registers with uneven movement. Such schemes in the language of experts are called "military-grade cryptography" and, with the right choice of parameters, can provide a very high cipher strength. However, in A5, the register lengths are chosen to be very short - 19, 22 and 23 bits, which in total gives a 64-bit GSM session encryption key. Already these shortened register lengths provide a theoretical opportunity for a well-known frontal attack when they sort through the filling of the first two registers (complexity of about 240), restoring the contents of the third register from the output encryption sequence (with a total complexity of about 245).
Hands on the Serbian cryptographer Dr. Jovan Golich, a specialist in stream ciphers, got to the analysis of A5. From a purely theoretical point of view, he described an attack that allowed to open the initial register fillings for only 64 bits of cipher sequence with labor costs of about 240. An experiment conducted within Microsoft walls really led to the key being opened, but it took about two weeks for the 32-node cluster of PII-300 machines to work (All of them are not like people or were they interested in a poor implementation of the algorithm? Now a couple of seconds is enough).
In April 1998, a group of computer experts from California widely announced and demonstrated that they were able to clone a GSM mobile phone. Previously, everyone assumed by default that GSM digital networks were much more protected from this scourge, causing millions of losses to analog cellular telephony networks. The group was headed by Mark Briseno, director of the so-called “Smartcard Developer Association”, which represents interests smart card software developers. Choosing as their goal the resistance of GSM to cloning attempts, the researchers set about reverse engineering the SIM module. This is the same smart card that is inserted into a cell phone, contains A3-A8 algorithms and uniquely identifies the subscriber. In the process of preparing for work on opening the contents of the chip, in the hands of researchers in mysterious ways came the description of the “COMP128 algorithm” - the most widespread practical implementation of A3-A8 in SIM-modules. This documentation helped to quickly and completely restore all the necessary information about the circuit. After that, Briseno invited David Wagner and Ian Goldberg, two young, but already well-known cryptanalysts, graduate students at the University of California at Berkeley. It took only a few hours for those to find fatal gaps in the scheme and to develop a method for extracting secret content from the card using only 219 polls of the smart card chip. (?! Another nonsense - so many polls of the smart card must be done if you don’t know the algorithm, but because they had documents).
Hacking A3-A8: too elementary: just read the description and if it’s still not clear, then pay attention to the fact, changing the bytes i + 16, i + 24 of the input COMP128, we can hope for a collision in bytes i, i + 8, i + 16, i + 24 after two rounds of encryption. The paradox of birthdays (if we assume that birthdays are distributed evenly, then in a group of 24 people with a probability of 0.5, two people will celebrate birthdays) it guarantees this quite quickly (since there are only 4 bytes). A collision in the second round will be detected after detecting a collision in the overall COMP128 output. And each collision can be used to study the bytes of i, i + 8 keys based on differential analysis.
Hacking A5 / 2: (Although MoU recognizes that cipher cracking was the goal of developing A5 / 2, nevertheless, the official results of the SAGE analysis said that they were not aware of any cryptographic defects in A5 / 2 .. Xa-xa- hu - this is for Russia. What defects can be in the sieve? Conclusion: carry water in the sieve.) It is known that in this scheme one more short register with a length of 17 bits is added, which controls the movement of bits in the other three registers. To open the system, it is enough frontal busting (difficulty 216 = 65536 to find the control register filling. This is done only by two frames of the communication session 114 bits in length (in the GSM system, the first two frames of the cipher sequence are known, because only zeros are encrypted). For the rest, you will not find information anywhere, so I I’ll give a hint: A5-crypto scheme based on linear feedback shift registers has a combining generator to obtain an encryption sequence, so we need to use weaknesses in the combining function, which Some allow one to obtain information on the individual input sequences of the complexity node from the output sequence. In this case, it is said that there is a correlation between the output sequence and one of the internal sequences. Due to this correlation, a separate internal sequence can be analyzed individually until the initial filling of the corresponding register is restored, then attention must be switched to one of the other internal sequences. The whole generator can be restored in a similar way - this method is often called a split-and-open attack. And the first of the registers you need to choose the one that is easier than the rest to restore. Think ...
Source: www.skrembler.ru
Introduction
Somehow after the New Year, I read about the standards used in GSM. It was especially fun after reading the words of James Moran, director of the unit responsible for security and protection of the system from fraud in the GSM consortium: “No one in the world has demonstrated the ability to intercept calls on the GSM network. This is a fact ... As far as we know, there is no equipment capable of such an interception. " And what nonsense do you sometimes find on the Internet about GSM.
But the GSM standard (Global System for Mobile communications) today owns 80% of the global digital mobile communications market. And it is used by over 250 million people. Duck why not take advantage of them? Hmm ... a question of ethics or finding a radio scanner (is this legal?). Although the operators in Russia are allowed to use stolen phones, and their protection is at the heart of GSM, and for this there are black lists of International Mobile Equipment Identity (in the West). Or maybe those who sell stolen phones are sharing with them?
GSM protection and how it was created
In principle, according to its concept, the GSM digital mobile communication system could well be extremely secure. It is based on a set of documents called the “Memorandum of Understanding the GSM Standard” or the MoU Groupe Special Mobile standard. This Memorandum was prepared at the end of the Cold War on the initiative of leading telecommunication companies in Western Europe. The European Institute of Telecommunications Standards (ETSI) developed technical documentation for GSM, and NATO special services took an active part in creating a security scheme that was generally designed to protect the new system from interception, wiretapping and fraud.
The basis of the GSM security system is composed of three secret algorithms (not officially disclosed to this day, communicated only to those who need it by necessity - equipment suppliers, telecom operators, etc.):
A3 - authentication algorithm that protects the phone from cloning;
A8 is an algorithm for generating a crypto key, in fact a unidirectional function that takes a fragment of the output from A3 and turns it into a session key for A5;
A5 - the actual encryption algorithm for digitalized speech to ensure the confidentiality of negotiations. GSM uses two main varieties of the algorithm: A5 / 1 - the "strong" version of the cipher for selected countries and A5 / 2 - weakened for everyone else (for Russia).
Mobile stations (telephones) are equipped with a smart card containing A3 and A8, and the phone itself has an ASIC chip with the A5 algorithm. Base stations are also equipped with an AS5 chip with A5 and an “authentication center” using A3-A8 algorithms to identify the mobile subscriber and generate a session key.
All this architecture, with proper execution and high-quality algorithms, is designed to guarantee reliable user authentication, protecting mobile stations from cloning and other fraud methods, as well as high-quality encryption of confidential negotiations. As a matter of fact, this is exactly what is declared by companies successfully engaged in the deployment of GSM worldwide and already embracing convenient communication services, according to various estimates, from 210 to 250 million people on the planet.
But the reality is that the special services involved in protecting government communications are also involved in activities of the opposite kind: interception and decryption of communications for intelligence purposes. For this reason, as eyewitnesses testify, considerable passions raged around the degree of protection of GSM, since the special services of NATO countries had rather different points of view on this matter. Germany insisted on strong algorithms, since it had the longest border with the communist bloc, while other countries were inclined towards a weakened version. In the end, the French development was chosen as the basis of the crypto scheme for A5.
Description of GSM encryption algorithms and hacking
A5 implements stream cipher based on three linear shift registers with uneven movement. Such schemes in the language of experts are called "military-grade cryptography" and, with the right choice of parameters, can provide a very high cipher strength. However, in A5, the register lengths are chosen to be very short - 19, 22 and 23 bits, which in total gives a 64-bit GSM session encryption key. Already these shortened register lengths provide a theoretical opportunity for a well-known frontal attack when they sort through the filling of the first two registers (complexity of about 240), restoring the contents of the third register from the output encryption sequence (with a total complexity of about 245).
Hands on the Serbian cryptographer Dr. Jovan Golich, a specialist in stream ciphers, got to the analysis of A5. From a purely theoretical point of view, he described an attack that allowed to open the initial register fillings for only 64 bits of cipher sequence with labor costs of about 240. An experiment conducted within Microsoft walls really led to the key being opened, but it took about two weeks for the 32-node cluster of PII-300 machines to work (All of them are not like people or were they interested in a poor implementation of the algorithm? Now a couple of seconds is enough).
In April 1998, a group of computer experts from California widely announced and demonstrated that they were able to clone a GSM mobile phone. Previously, everyone assumed by default that GSM digital networks were much more protected from this scourge, causing millions of losses to analog cellular telephony networks. The group was headed by Mark Briseno, director of the so-called “Smartcard Developer Association”, which represents interests smart card software developers. Choosing as their goal the resistance of GSM to cloning attempts, the researchers set about reverse engineering the SIM module. This is the same smart card that is inserted into a cell phone, contains A3-A8 algorithms and uniquely identifies the subscriber. In the process of preparing for work on opening the contents of the chip, in the hands of researchers in mysterious ways came the description of the “COMP128 algorithm” - the most widespread practical implementation of A3-A8 in SIM-modules. This documentation helped to quickly and completely restore all the necessary information about the circuit. After that, Briseno invited David Wagner and Ian Goldberg, two young, but already well-known cryptanalysts, graduate students at the University of California at Berkeley. It took only a few hours for those to find fatal gaps in the scheme and to develop a method for extracting secret content from the card using only 219 polls of the smart card chip. (?! Another nonsense - so many polls of the smart card must be done if you don’t know the algorithm, but because they had documents).
Hacking A3-A8: too elementary: just read the description and if it’s still not clear, then pay attention to the fact, changing the bytes i + 16, i + 24 of the input COMP128, we can hope for a collision in bytes i, i + 8, i + 16, i + 24 after two rounds of encryption. The paradox of birthdays (if we assume that birthdays are distributed evenly, then in a group of 24 people with a probability of 0.5, two people will celebrate birthdays) it guarantees this quite quickly (since there are only 4 bytes). A collision in the second round will be detected after detecting a collision in the overall COMP128 output. And each collision can be used to study the bytes of i, i + 8 keys based on differential analysis.
Hacking A5 / 2: (Although MoU recognizes that cipher cracking was the goal of developing A5 / 2, nevertheless, the official results of the SAGE analysis said that they were not aware of any cryptographic defects in A5 / 2 .. Xa-xa- hu - this is for Russia. What defects can be in the sieve? Conclusion: carry water in the sieve.) It is known that in this scheme one more short register with a length of 17 bits is added, which controls the movement of bits in the other three registers. To open the system, it is enough frontal busting (difficulty 216 = 65536 to find the control register filling. This is done only by two frames of the communication session 114 bits in length (in the GSM system, the first two frames of the cipher sequence are known, because only zeros are encrypted). For the rest, you will not find information anywhere, so I I’ll give a hint: A5-crypto scheme based on linear feedback shift registers has a combining generator to obtain an encryption sequence, so we need to use weaknesses in the combining function, which Some allow one to obtain information on the individual input sequences of the complexity node from the output sequence. In this case, it is said that there is a correlation between the output sequence and one of the internal sequences. Due to this correlation, a separate internal sequence can be analyzed individually until the initial filling of the corresponding register is restored, then attention must be switched to one of the other internal sequences. The whole generator can be restored in a similar way - this method is often called a split-and-open attack. And the first of the registers you need to choose the one that is easier than the rest to restore. Think ...
Source: www.skrembler.ru
Original message
Описание GSM и ее взлом
Введение
Как-то после Нового года я прочитал про стандарты применяемые в GSM. Было особенно весело после прочтения слов Джеймса Морана, директора подразделения, отвечающего в консорциуме GSM за безопасность и защиту системы от мошенничества: "Никто в мире не продемонстрировал возможность перехвата звонков в сети GSM. Это факт... Насколько нам известно, не существует никакой аппаратуры, способной осуществлять такой перехват". А какой бред иногда встречаешь в Internet про GSM .
А ведь стандарту GSM (Global System for Mobile communications) сегодня принадлежит 80% мирового рынка цифровой мобильной связи. И им пользуются свыше 250 млн. людей. Дак почему же не попользоваться за их счет? Хмм... вопрос этики или нахождения радиосканера (законно ли это ?). Хотя ведь операторы в России разрешают пользоваться ворованными телефонами, а у них защита заложена в основе GSM и для этого имеются черные списки International Mobile Equipment Identity ( на Западе ). А может с ними делятся те кто продает ворованные телефоны ?
Защита GSM и как она создавалась
В принципе, по своему замыслу, цифровая система мобильной связи GSM вполне могла бы быть чрезвычайно защищенной. В основе ее лежит свод документов под названием "Меморандум о понимании стандарта GSM" или MoU Groupe Special Mobile standard. Этот Меморандум был подготовлен на излете Холодной войны по инициативе ведущих телекоммуникационных компаний Западной Европы. Разрабатывал техническую документацию GSM Европейский институт стандартов по телекоммуникациям (ETSI), а в создании схемы безопасности, в целом призванной защитить новую систему от перехвата, прослушивания и мошенничества, активное участие приняли спецслужбы стран НАТО.
Основу системы безопасности GSM составляют три секретных алгоритма (официально не раскрытые и поныне, сообщаемые лишь тем, кому это требуется по необходимости - поставщикам оборудования, операторам связи и т.д.):
А3 - алгоритм аутентификации, защищающий телефон от клонирования;
А8 - алгоритм генерации криптоключа, по сути дела однонаправленная функция, которая берет фрагмент выхода от A3 и превращает его в сеансовый ключ для A5;
A5 - собственно алгоритм шифрования оцифрованной речи для обеспечения конфиденциальности переговоров. В GSM используются две основные разновидности алгоритма: A5/1 - "сильная" версия шифра для избранных стран и A5/2 - ослабленная для всех остальных (для России).
Мобильные станции (телефоны) снабжены смарт-картой, содержащей A3 и A8, а в самом телефоне имеется ASIC-чип с алгоритмом A5. Базовые станции также снабжены ASIC-чипом с A5 и "центром аутенитификации", использующим алгоритмы A3-A8 для идентификации мобильного абонента и генерации сеансового ключа.
Вся эта архитектура при надлежащем исполнении и качественных алгоритмах призвана гарантировать надежную аутентификацию пользователя, обеспечивая защиту мобильных станций от клонирования и прочих методов мошенничества, а также качественное шифрование конфиденциальных переговоров. Собственно говоря, именно это и декларируется компаниями, успешно занимающимися разворачиванием GSM по всему миру и уже охватившими услугами удобной связи, по разным подсчетам, от 210 до 250 миллионов человек на планете.
Но реальность такова, что спецслужбы, занятые защитой правительственных коммуникаций, одновременно вовлечены и в деятельность противоположного рода: перехват и дешифрование коммуникаций в разведывательных целях. По этой причине, как свидетельствуют очевидцы, вокруг степени защиты GSM бушевали немалые страсти, поскольку спецслужбы стран НАТО имели довольно разные точки зрения на этот счет. Германия настаивала на сильных алгоритмах, поскольку имела самую длинную границу с коммунистическим блоком, другие же страны склонялись к ослабленному варианту. В конце концов в качестве основы криптосхемы для A5 была избрана французская разработка.
Описание алгоритмов шифрования GSM и взлом
A5 реализует поточный шифр на основе трех линейных регистров сдвига с неравномерным движением. Такого рода схемы на языке специалистов именуются "криптографией военного уровня" и при верном выборе параметров способны обеспечивать очень высокую стойкость шифра. Однако, в А5 длины регистров выбраны очень короткими - 19, 22 и 23 бита, что в сумме и дает 64-битный сеансовый ключ шифрования в GSM. Уже одни эти укороченные длины регистров дают теоретическую возможность для хорошо известной лобовой атаки, когда перебирают заполнение двух первых регистров (сложность порядка 240 ), восстанавливая содержимое третьего регистра по выходной шифрующей последовательности (с общей сложностью порядка 245).
До анализа A5 дошли руки у сербского криптографа д-ра Йована Голича специалиста по поточным шифрам . С чисто теоретических позиций он описал атаку, позволяющую вскрывать начальные заполнения регистров всего по 64 битам шифропоследовательности с трудозатратами около 240. Проведенный в стенах Microsoft эксперимент действительно привел к вскрытию ключа, но понадобилось для этого около двух недель работы 32-узлового кластера машин PII-300 .( Все-то у них не как у людей или они были заинтересованы в плохой реализации алгоритма ? Сейчас достаточно пары секунд).
В апреле 1998 г. группа компьютерных экспертов из Калифорнии широко объявила и продемонстрировала, что ей удалось клонировать мобильный телефон стандарта GSM . Ранее всеми по умолчанию предполагалось, что цифровые сети GSM гораздо надежнее защищены от этой напасти, приносящей миллионные убытки сетям аналоговой сотовой телефонии.Возглавлял группу Марк Брисено, директор так называемой "Ассоциации разработчиков смарт-карт" или SDA (Smartcard Developer Association), представляющей интересы разработчиков программного обеспечения для смарт-карт. Избрав своей целью стойкость GSM к попыткам клонирования, исследователи занялись обратной разработкой модуля SIM. Это та самая смарт-карта, что вставляется в сотовый телефон, содержит алгоритмы A3-A8 и однозначно идентифицирует абонента. В процессе подготовки к работам по вскрытию содержимого чипа, в руки к исследователям неисповедимыми путями попало описание "алгоритма COMP128" - наиболее широко распространенной практической реализации A3-A8 в SIM-модулях. Эта документация помогла быстрее и полностью восстановить всю необходимую информацию о схеме. После этого Брисено пригласил для ее анализа двух молодых, но уже известных криптоаналитиков, аспирантов Калифорнийского университета в Беркли Дэвида Вагнера и Иэна Голдберга. Тем понадобилось всего несколько часов, чтобы отыскать в схеме фатальные прорехи и разработать метод извлечения из карты секретного содержимого с помощью всего 219 опросов чипа смарт-карты.(?! очередной бред - столько опросов смарт-карты надо делать, если не знаешь алгоритма, а ведь документы у них были ).
Взлом A3-A8: слишком элементарен : достаточно прочитать описание и если не понятно все еще, то обратить внимание на факт,изменяя байты i+16,i+24 ввода COMP128 мы можем надеятся на коллизию в байтах i,i+8,i+16,i+24 после двух раундов шифрования. Парадокс дней рождения ( если считать, что дни рождения распределены равномерно, то в группе из 24 человек с вероятностью 0,5 у двух человек празднования дней рождения совпадут) гарантирует это довольно быстро (так как всего 4 байта ). Коллизия в втором раунде будет обнаруженна после выявления коллизия в общем выводе COMP128. И каждая коллизия может использоватся для изучения байт i,i+8 ключа на основе дифференционального анализа.
Взлом A5/2 : (Хотя в MoU признают, что вскрываемость шифра и была целью разработки A5/2, тем не менее в официальных результатах анализа SAGE сказано, что им неизвестно ни о каких криптографических дефектах в A5/2.. Xa-xa-ха - это же для России. Какие дефекты могут быть в решете? Вывод: носите воду в решете. ) Известно, что в этой схеме добавлен еще один короткий регистр длиной 17 бит, управляющий движением бит в остальных трех регистрах, .для вскрытия системы достаточно лобовым перебором (сложность 216 = 65536 отыскать заполнение управляющего регистра. Делается это всего по двум фреймам сеанса связи длиной по 114 бит (в системе GSM первые два фрейма шифрпоследовательности известны, поскольку шифруются одни нули).Про остальное вы нигде информации не найдете, поэтому я дам подсказку: A5- криптосхема на основе регистров сдвига с линейной обратной связью имеет комбинирующий генератор для получения шифрующей последовательности. Поэтому надо использовать слабости в комбинирующей функции, которые позволяют по выходной последовательности получить информацию об отдельных входных последовательностях узла усложнения. В этом случае говорят, что имеется корреляция между выходной последовательностью и одной из внутренних последовательностей. Вследствие такой корреляции отдельная внутренняя последовательность может быть проанализирована индивидуально вплоть до восстановления начального заполнения соответствующего регистра, затем внимание надо переключить на одну из других внутренних последовательностей. Подобным способом может быть восстановлен весь генератор - этот метод часто называют атака "разделяй-и-вскрывай". Причем первым из регистров надо выбрать тот, который проще чем остальные восстановить. Подумайте ...
Источник:www.skrembler.ru
Введение
Как-то после Нового года я прочитал про стандарты применяемые в GSM. Было особенно весело после прочтения слов Джеймса Морана, директора подразделения, отвечающего в консорциуме GSM за безопасность и защиту системы от мошенничества: "Никто в мире не продемонстрировал возможность перехвата звонков в сети GSM. Это факт... Насколько нам известно, не существует никакой аппаратуры, способной осуществлять такой перехват". А какой бред иногда встречаешь в Internet про GSM .
А ведь стандарту GSM (Global System for Mobile communications) сегодня принадлежит 80% мирового рынка цифровой мобильной связи. И им пользуются свыше 250 млн. людей. Дак почему же не попользоваться за их счет? Хмм... вопрос этики или нахождения радиосканера (законно ли это ?). Хотя ведь операторы в России разрешают пользоваться ворованными телефонами, а у них защита заложена в основе GSM и для этого имеются черные списки International Mobile Equipment Identity ( на Западе ). А может с ними делятся те кто продает ворованные телефоны ?
Защита GSM и как она создавалась
В принципе, по своему замыслу, цифровая система мобильной связи GSM вполне могла бы быть чрезвычайно защищенной. В основе ее лежит свод документов под названием "Меморандум о понимании стандарта GSM" или MoU Groupe Special Mobile standard. Этот Меморандум был подготовлен на излете Холодной войны по инициативе ведущих телекоммуникационных компаний Западной Европы. Разрабатывал техническую документацию GSM Европейский институт стандартов по телекоммуникациям (ETSI), а в создании схемы безопасности, в целом призванной защитить новую систему от перехвата, прослушивания и мошенничества, активное участие приняли спецслужбы стран НАТО.
Основу системы безопасности GSM составляют три секретных алгоритма (официально не раскрытые и поныне, сообщаемые лишь тем, кому это требуется по необходимости - поставщикам оборудования, операторам связи и т.д.):
А3 - алгоритм аутентификации, защищающий телефон от клонирования;
А8 - алгоритм генерации криптоключа, по сути дела однонаправленная функция, которая берет фрагмент выхода от A3 и превращает его в сеансовый ключ для A5;
A5 - собственно алгоритм шифрования оцифрованной речи для обеспечения конфиденциальности переговоров. В GSM используются две основные разновидности алгоритма: A5/1 - "сильная" версия шифра для избранных стран и A5/2 - ослабленная для всех остальных (для России).
Мобильные станции (телефоны) снабжены смарт-картой, содержащей A3 и A8, а в самом телефоне имеется ASIC-чип с алгоритмом A5. Базовые станции также снабжены ASIC-чипом с A5 и "центром аутенитификации", использующим алгоритмы A3-A8 для идентификации мобильного абонента и генерации сеансового ключа.
Вся эта архитектура при надлежащем исполнении и качественных алгоритмах призвана гарантировать надежную аутентификацию пользователя, обеспечивая защиту мобильных станций от клонирования и прочих методов мошенничества, а также качественное шифрование конфиденциальных переговоров. Собственно говоря, именно это и декларируется компаниями, успешно занимающимися разворачиванием GSM по всему миру и уже охватившими услугами удобной связи, по разным подсчетам, от 210 до 250 миллионов человек на планете.
Но реальность такова, что спецслужбы, занятые защитой правительственных коммуникаций, одновременно вовлечены и в деятельность противоположного рода: перехват и дешифрование коммуникаций в разведывательных целях. По этой причине, как свидетельствуют очевидцы, вокруг степени защиты GSM бушевали немалые страсти, поскольку спецслужбы стран НАТО имели довольно разные точки зрения на этот счет. Германия настаивала на сильных алгоритмах, поскольку имела самую длинную границу с коммунистическим блоком, другие же страны склонялись к ослабленному варианту. В конце концов в качестве основы криптосхемы для A5 была избрана французская разработка.
Описание алгоритмов шифрования GSM и взлом
A5 реализует поточный шифр на основе трех линейных регистров сдвига с неравномерным движением. Такого рода схемы на языке специалистов именуются "криптографией военного уровня" и при верном выборе параметров способны обеспечивать очень высокую стойкость шифра. Однако, в А5 длины регистров выбраны очень короткими - 19, 22 и 23 бита, что в сумме и дает 64-битный сеансовый ключ шифрования в GSM. Уже одни эти укороченные длины регистров дают теоретическую возможность для хорошо известной лобовой атаки, когда перебирают заполнение двух первых регистров (сложность порядка 240 ), восстанавливая содержимое третьего регистра по выходной шифрующей последовательности (с общей сложностью порядка 245).
До анализа A5 дошли руки у сербского криптографа д-ра Йована Голича специалиста по поточным шифрам . С чисто теоретических позиций он описал атаку, позволяющую вскрывать начальные заполнения регистров всего по 64 битам шифропоследовательности с трудозатратами около 240. Проведенный в стенах Microsoft эксперимент действительно привел к вскрытию ключа, но понадобилось для этого около двух недель работы 32-узлового кластера машин PII-300 .( Все-то у них не как у людей или они были заинтересованы в плохой реализации алгоритма ? Сейчас достаточно пары секунд).
В апреле 1998 г. группа компьютерных экспертов из Калифорнии широко объявила и продемонстрировала, что ей удалось клонировать мобильный телефон стандарта GSM . Ранее всеми по умолчанию предполагалось, что цифровые сети GSM гораздо надежнее защищены от этой напасти, приносящей миллионные убытки сетям аналоговой сотовой телефонии.Возглавлял группу Марк Брисено, директор так называемой "Ассоциации разработчиков смарт-карт" или SDA (Smartcard Developer Association), представляющей интересы разработчиков программного обеспечения для смарт-карт. Избрав своей целью стойкость GSM к попыткам клонирования, исследователи занялись обратной разработкой модуля SIM. Это та самая смарт-карта, что вставляется в сотовый телефон, содержит алгоритмы A3-A8 и однозначно идентифицирует абонента. В процессе подготовки к работам по вскрытию содержимого чипа, в руки к исследователям неисповедимыми путями попало описание "алгоритма COMP128" - наиболее широко распространенной практической реализации A3-A8 в SIM-модулях. Эта документация помогла быстрее и полностью восстановить всю необходимую информацию о схеме. После этого Брисено пригласил для ее анализа двух молодых, но уже известных криптоаналитиков, аспирантов Калифорнийского университета в Беркли Дэвида Вагнера и Иэна Голдберга. Тем понадобилось всего несколько часов, чтобы отыскать в схеме фатальные прорехи и разработать метод извлечения из карты секретного содержимого с помощью всего 219 опросов чипа смарт-карты.(?! очередной бред - столько опросов смарт-карты надо делать, если не знаешь алгоритма, а ведь документы у них были ).
Взлом A3-A8: слишком элементарен : достаточно прочитать описание и если не понятно все еще, то обратить внимание на факт,изменяя байты i+16,i+24 ввода COMP128 мы можем надеятся на коллизию в байтах i,i+8,i+16,i+24 после двух раундов шифрования. Парадокс дней рождения ( если считать, что дни рождения распределены равномерно, то в группе из 24 человек с вероятностью 0,5 у двух человек празднования дней рождения совпадут) гарантирует это довольно быстро (так как всего 4 байта ). Коллизия в втором раунде будет обнаруженна после выявления коллизия в общем выводе COMP128. И каждая коллизия может использоватся для изучения байт i,i+8 ключа на основе дифференционального анализа.
Взлом A5/2 : (Хотя в MoU признают, что вскрываемость шифра и была целью разработки A5/2, тем не менее в официальных результатах анализа SAGE сказано, что им неизвестно ни о каких криптографических дефектах в A5/2.. Xa-xa-ха - это же для России. Какие дефекты могут быть в решете? Вывод: носите воду в решете. ) Известно, что в этой схеме добавлен еще один короткий регистр длиной 17 бит, управляющий движением бит в остальных трех регистрах, .для вскрытия системы достаточно лобовым перебором (сложность 216 = 65536 отыскать заполнение управляющего регистра. Делается это всего по двум фреймам сеанса связи длиной по 114 бит (в системе GSM первые два фрейма шифрпоследовательности известны, поскольку шифруются одни нули).Про остальное вы нигде информации не найдете, поэтому я дам подсказку: A5- криптосхема на основе регистров сдвига с линейной обратной связью имеет комбинирующий генератор для получения шифрующей последовательности. Поэтому надо использовать слабости в комбинирующей функции, которые позволяют по выходной последовательности получить информацию об отдельных входных последовательностях узла усложнения. В этом случае говорят, что имеется корреляция между выходной последовательностью и одной из внутренних последовательностей. Вследствие такой корреляции отдельная внутренняя последовательность может быть проанализирована индивидуально вплоть до восстановления начального заполнения соответствующего регистра, затем внимание надо переключить на одну из других внутренних последовательностей. Подобным способом может быть восстановлен весь генератор - этот метод часто называют атака "разделяй-и-вскрывай". Причем первым из регистров надо выбрать тот, который проще чем остальные восстановить. Подумайте ...
Источник:www.skrembler.ru
