Пользователь
–1,6
рейтинг
18 июля 2013 в 04:35

Разработка → Безопасность GSM сетей: шифрование данных


Disclaimer Данная статья публикуется исключительно в ознакомительных целях, за использование материалов, опубликованных в данной статье автор ответственности не несет.
Так же хочу сразу предупредить, что если вы рассчитываете найти в этой статье пошаговое руководство к прослушиванию GSM трафика или надеетесь, прочитав данную статью, получить доступ к телефонным разговорам ваших друзей, знакомых, домашних животных, то лучше проигнорируйте ее. Здесь вы не найдете ничего интересного. Нет правда, не ходите под кат, там скука.

Часть 1: основные моменты GSM безопасности


Прежде чем приступить к описанию алгоритма шифрования используемого в GSM сетях рассмотрим каким образом происходит аутентификация пользователя и формирования ключа шифрования. Для этого воспользуемся картинкой, позаимствованной с википедии(за качество прошу прощения, не нашел ничего лучше).


На данном рисунке схематично представлены следующие шаги:
  1. Телефон оператора подключается к сети.
  2. Для подтверждения своей подлинности телефон посылает специальный идентификационный код, называемый TMSI(Temporary Mobile Subscriber Identity).
  3. Центр Аутентификации(ЦА) генерирует 128-битное случайное число RAND и посылает его на Мобильную Станцию(МС).
  4. МС зашифровывает полученное число RAND, используя свой секретный ключ Ki и алгоритм аутентификации A3.
  5. MC берет первые 32 бита из последовательности, полученной на предыдущем шаге(назовем их SRES(signed response)) и отправляет их обратно на ЦА.
  6. ЦА проделывает ту же операцию и получает 32 битную последовательность XRES(expected response).
  7. После чего ЦА сравнивает SRES и XRES. В случае, если оба значения равны, телефон считается аутентифицированным.
  8. МС и ЦА вычисляют сессионный ключ шифрования, используя секретный ключ Ki и алгоритм формирования ключа A8 Kc=A8ki(RAND)


Говоря об алгоритмах аутентификации A3 и алгоритме формирования ключа A8, следует отметить что на практике большинство сотовых операторов используют для этих целей один алгоритм, называемый COMP128(он имеет множество модификаций COMP128-1, COMP128-2, COMP128-3).
COMP128 представляет собой обыкновенную хэш-функцию, на входе которая принимает 128-битную последовательность и на выходе возвращает 96-битную.
Так вот, вместо применения разных алгоритмов для аутентификации и формирования сессионного ключа применяется следующая схема:
SRES=Первые 32 бита от COMP128(Ki||RAND)
Kс=Последние 64 бита COMP128(Ki||RAND).
Как всегда в криптографии, попытка сэкономить время разработчикам обернулась полным провалом. Безопасность GSM сетей изначально основывалась на принципе «безопасность за счёт неизвестности». И когда в 1998 году алгоритм был вскрыт группой исследователей состоящих из Marc Briceno, Ian Goldberg и David Wagner обранужилась одна занятная особенность: последние 10 бит секретного ключа Ki всегда равнялись нулю. Используя это любопытное свойство, а так же уязвимость COMP128 к «атаке дней рождений» Marc Briceno, Ian Goldberg и David Wagner смогли извлечь секретный ключ Ki из SIM-карты.
Результатом этого исследования стал повсеместный отказ от алгоритма COMP128 и его замена на более надежные модификации COMP128-2 и COMP128-3, технические детали которых держатся в тайне. Хм… вам это ничего не напоминает?

Часть 2: алгоритм шифрования A5/1


Давайте теперь перейдем от вещей более общих к вещам более частным и поговорим о том как в GSM реализовано шифрование телефонных разговоров.
В качестве алгоритма шифрования в GSM используются алгоритмы из семейства A5. На сегодняшний день их всего 3:
  • A5/1 — поточный шифр, наиболее распространенный на сегодня.
  • A5/2-вариант предыдущего алгоритма «для бедных». Очень похож на своего «старшего брата», но изначально задумывался, как сильно ослабленная версия A5/1. В настоящее время не используется
  • A5/3-блочный шифр. Разработан в 2002 году с целью заменить устаревший A5/1. Однако в настоящее время используется только в 3GPP сетях. У алгоритма найден ряд уязвимостей, но о практических атаках речи пока не идет.

Рассмотрим подробнее алгоритм A5/1.
Итак, как уже было сказано выше A5/1 это поточный шифр. И вновь на помощь спешит картинка с википедии:

Внутреннее состояние шифра A5/1 состоит из трех линейных регистров сдвига с обратной связью R1, R2, R3, длиной 19, 22 и 23 бита соответственно(всего 64 бита).
Сдвиг в регистрах R1, R2, R3 происходит только при выполнении определенного условия. Каждый регистр содержит " бит управления тактированием". В R1 это 8-й бит, а в R2 и R3 — 10-й. На каждом шаге сдвигаются только те регистры у которых значение бита синхронизации равно большинству значений синхронизирующих битов всех трех регистров.

Перед работой алгоритма выполняется инициализация регистров. Происходит это следующим образом:
  1. R1=R2=R3=0
  2. For i=0 to 63 do
    R1[0]=R1[0]⊕Kc[i]
    R2[0]=R2[0]⊕Kc[i]
    R2[0]=R2[0]⊕Kc[i]
    Сдвинуть все регистры на одну позицию, игнорируя биты синхронизации.
  3. For i=0 to 22 do
    R1[0]=R1[0]⊕FrameCount[[i]
    R2[0]=R2[0]⊕FrameCount[[i]
    R2[0]=R2[0]⊕FrameCount[[i]
    Сдвинуть все регистры на одну позицию, игнорируя биты синхронизации.
  4. For i=0 to 99 do
    Сдвинуть регистры на одну позицию, с учетом битов синхронизации.

Где FrameCount 32-х битная запись номера текущего фрейма.

После инициализации производится вычисление 228 бит выходной последовательности. 114 бит используется для шифрования данных исходящего из сети к мобильному телефону, остальные 114 бит для шифрования данных идущих от телефона к сети. Само шифрование представляет собой обыкновенный XOR между данными и произведенным алгоритмом A5/1 ключевым потоком.
После передачи данных номер фрейма увеличивается на единицу и заново производится инициализация регистров.

Воспользуемся приведенным выше описанием и реализуем шифрование A5/1 на С#.
Класс A5Enc на C#
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Collections;

namespace A5project
{
    class A5Enc
    {
        private bool[] reg = new bool[19];
        private bool[] reg2 = new bool[22];
        private bool[] reg3 = new bool[23];
        
        //конструктор, который позволяет сразу установить начальное состояние регистров и нужное значение
        public A5Enc(bool[][] startState)
        {
            reg = startState[0];
            reg2 = startState[1];
            reg3 = startState[2];
        }

        public A5Enc()
        {
            for (int i = 0; i < 19; i++)
                reg[i] = false;
            for (int i = 0; i < 22; i++)
                reg2[i] = false;
            for (int i = 0; i < 23; i++)
                reg3[i] = false;
        }

        //нормальная инициализация регистров, используется при обычном вызове метода A5
        public void KeySetup(byte[] key, int[] frame)
        {
            for (int i = 0; i < 19; i++)
                reg[i] = false;
            for (int i = 0; i < 22; i++)
                reg2[i] = false;
            for (int i = 0; i < 23; i++)
                reg3[i] = false;
            BitArray KeyBits = new BitArray(key);
            BitArray FrameBits = new BitArray(frame);
            bool[] b = new bool[64];
            for (int i = 0; i < 64; i++)
            {
                clockall();
                reg[0] = reg[0] ^ KeyBits[i];
                reg2[0] = reg2[0] ^ KeyBits[i];
                reg3[0] = reg3[0] ^ KeyBits[i];
            }
            for (int i = 0; i < 22; i++)
            {
                clockall();
                reg[0] = reg[0] ^ FrameBits[i];
                reg2[0] = reg2[0] ^ FrameBits[i];
                reg3[0] = reg3[0] ^ FrameBits[i];
            }
            for (int i = 0; i < 100; i++)
            {
                clock();
            }
        }

        //частичная инициализация, в регистры грузится только номер фрейма
        public void KeySetup(int[] frame)
        {                        
            BitArray FrameBits = new BitArray(frame);            
            for (int i = 0; i < 22; i++)
            {
                clockall();
                reg[0] = reg[0] ^ FrameBits[i];
                reg2[0] = reg2[0] ^ FrameBits[i];
                reg3[0] = reg3[0] ^ FrameBits[i];
            }
            for (int i = 0; i < 100; i++)
            {
                clock();
            }
        }

        private void clock()
        {
            bool majority = ((reg[8] & reg2[10]) | (reg[8] & reg3[10]) | (reg2[10] & reg3[10]));
            if (reg[8] == majority)
                clockone(reg);

            if (reg2[10] == majority)
                clocktwo(reg2);

            if (reg3[10] == majority)
                clockthree(reg3);
        }

        //набор функций реализующих сдвиги регистров
        private bool[] clockone(bool[] RegOne)
        {
            bool temp = false;
            for (int i = RegOne.Length - 1; i > 0; i--)
            {
                if (i == RegOne.Length - 1)
                    temp = RegOne[13] ^ RegOne[16] ^ RegOne[17] ^ RegOne[18];
                RegOne[i] = RegOne[i - 1];
                if (i == 1)
                    RegOne[0] = temp;
            }
            return RegOne;
        }

        private bool[] clocktwo(bool[] RegTwo)
        {
            bool temp = false;
            for (int i = RegTwo.Length - 1; i > 0; i--)
            {
                if (i == RegTwo.Length - 1)
                    temp = RegTwo[20] ^ RegTwo[21];
                RegTwo[i] = RegTwo[i - 1];
                if (i == 1)
                    RegTwo[0] = temp;
            }
            return RegTwo;
        }

        private bool[] clockthree(bool[] RegThree)
        {
            bool temp = false;
            for (int i = RegThree.Length - 1; i > 0; i--)
            {
                if (i == RegThree.Length - 1)
                    temp = RegThree[7] ^ RegThree[20] ^ RegThree[21] ^ RegThree[22];
                RegThree[i] = RegThree[i - 1];
                if (i == 1)
                    RegThree[0] = temp;
            }
            return RegThree;
        }

        private void clockall()
        {
            reg = clockone(reg);
            reg2 = clocktwo(reg2);
            reg3 = clockthree(reg3);
        }

        //метод возвращающий 114 бит сгенерированного потока
        public bool[] A5()
        {
            bool[] FirstPart = new bool[114];
            for (int i = 0; i < 114; i++)
            {
                clock();
                FirstPart[i] = (reg[18] ^ reg2[21] ^ reg3[22]);
            }
            return FirstPart;
        }

        //метод возвращающий всю 228 битную последовательность сгенерированного потока
        public bool[] A5(bool AsFrame)
        {
            bool[] FirstPart = new bool[228];            
            for (int i = 0; i < 228; i++)
            {
                clock();
                FirstPart[i] = (reg[18] ^ reg2[21] ^ reg3[22]);
            }
            return FirstPart;
        }

        public byte[] FromBoolToByte(bool[] key, bool lsb)
        {
            int bytes = key.Length / 8;
            if ((key.Length % 8) != 0) bytes++;
            byte[] arr2 = new byte[bytes];
            int bitIndex = 0, byteIndex = 0;
            for (int i = 0; i < key.Length; i++)
            {
                if (key[i])
                {
                    if(lsb)
                        arr2[byteIndex] |= (byte)(((byte)1) << (7 - bitIndex));
                    else
                        arr2[byteIndex] |= (byte)(((byte)1) << (bitIndex));
                }
                bitIndex++;
                if (bitIndex == 8)
                {
                    bitIndex = 0;
                    byteIndex++;
                }
            }
            return arr2;
        }
    }
}

Проверить правильность кода можно, запустив программу с ключом {0x12, 0x23, 0x45, 0x67, 0x89, 0xAB, 0xCD, 0xEF} и номером фрейма 0x134. Две сгенерированные последовательности по 114 бит каждая, должны быть равны соответственно { 0x53, 0x4E, 0xAA, 0x58, 0x2F, 0xE8, 0x15, 0x1A, 0xB6, 0xE1, 0x85, 0x5A, 0x72, 0x8C, 0x00 } и { 0x24, 0xFD, 0x35, 0xA3, 0x5D, 0x5F, 0xB6, 0x52, 0x6D, 0x32, 0xF9, 0x06, 0xDF, 0x1A, 0xC0 }.
Именно такие тестовые данные использовали Marc Briceno, Ian Goldberg и David Wagner в своей самой первой реализации алгоритма, написанной на С.

Функция шифрования/расшифровки, использующая данный класс, будет выглядеть следующим образом:
private byte[] A5Encyptor(byte[] msg,byte[] key)
        {
            A5Enc a5 = new A5Enc();
            int[] frame = new int[1];  
            bool[] resbits = new bool[msg.Count];
            int framesCount = msg.Length / 228;
            if ((msgbits.Length % 228) != 0)
                framesCount++;
            for (int i = 0; i < framesCount; i++)
            {
                frame[0] = i;
                a5.KeySetup(key, frame);
                bool[] KeyStream = a5.A5(true);
                for (int j = 0; j < 228; j++)
                {
                    resbits[i * 228 + j] = msgbits[i * 228 + j] ^ KeyStream[j];
                }
            }
            return a5.FromBoolToByte(resbits, false);
        }


Теперь когда у нас есть функция, позволяющая шифровать и расшифровывать данные, давайте поговорим об уязвимостях алгоритма A5/1.
На сегодняшний день известно большое количество успешных атак на GSM шифрование и все они относятся к атакам типа known-plaintext, т.е. для восстановления ключа атакующему помимо зашифрованных фреймов необходимо знать так же незашифрованные данные, которые соответствуют этим фреймам. На первый взгляд такое требование может показаться фантастическим, однако из-за специфики стандарта GSM, в котором помимо голосового трафика передаются различные системные сообщения, такого рода атаки из разряда теоретических переходят в разряд практических. Системные сообщения GSM содержат повторяющиеся данные и могут использоваться злоумышленником. В частности метод, предложенный Karsten Nohl в 2010 году основан как раз таки на поиске такого рода данных в шифротексте и простом переборе различных вариантов ключей, хранящихся в радужных таблицах, до тех пор пока не будет найден ключ, порождающий нужный шифротекст для известного заранее системного сообщения.

Часть 3: атака на алгоритм A5/1


Однако же у нас нет огромных ресурсов, необходимых для вычисления радужных таблиц, поэтому мы реализуем атаку попроще, относящуюся к т.н. «корреляционным атакам».
Раcсматриваемая нами атака была впервые описана в 2002 году двумя исследователями: Patrik Ekdahl и Thomas Johansson.
Из определения процедуры инициализации можно заключить, что начальное состояние регистров является линейной функцией от сессионного ключа K и номера фрейма Fn.
Зная так же, что выходной бит генератора является XOR-ом выходных бит всех трех регистров мы можем записать следующее равенство:

(1),

где si-последовательность генерируемая регистрами после загрузки в них только битов ключа K. fi-последовательность, после загрузки только битов номера фрейма, а x-выходной бит регистра.

Так же из определения инициализации мы знаем, что первые 100 циклов алгоритм работает «в холостую», т.е. не производит никаких выходных битов, и первый бит выходной последовательности на самом деле является 101-м сгенерированным битом. Таким образом, если учесть, что на каждом шаге вероятность сдвига для каждого регистра равняется 3/4, можно сделать предположение, что после 101 шага, каждый регистр сдвигался ровно 76 раз. Следовательно, формула (1) преобразуется в:

(2)

Обозначив правую часть (2) как перепишем формулу:

(3)

Т.к. выражение в правой части (3) нам известно, мы получаем 1 бит информации о ключевой последовательности S, а именно о состоянии 76-й позиции каждого регистра после инициализации. Действуя подобным образом, мы можем предположить, что на 102 позиции R1 остался также на позиции 76, а регистры R2 и R3 сдвинулись на позицию 77, таким образом мы получаем информацию о 77-й позиции регистра, и т.д. Всего нам необходимо вскрыть 64 бита, для успешного восстановления начального состояния.

Разумеется ситуация (76,76,76) возникает именно на 101 шаге с крайне низкой вероятностью, и если бы мы решили действовать подобным образом, то нам понадобилось бы перебрать огромное количество фреймов, пока наконец не попадется именно тот, в котором после 101 сдвига каждый регистр прокрутился на 76 позиций. Для того, чтобы уменьшить необходимое количество фреймов Ekdahl и Johansson предложили следующий метод.

Нет нужды угадывать конкретную позицию в которой регистры проворачиваются (cl1,cl2,cl3) раз. Достаточно просто знать, что с большой долей вероятности каждый регистр провернется от 76 до 102 на отрезке I=[100,140] выходных бит каждого фрейма.
Таким образом, для каждого фрейма мы можем вычислить вероятность: как

(4),

где



и обозначает вероятность того, что t-й бит был порожден позициями регистров (cl1, cl2, cl3).

Вычислив (4) для каждого доступного фрейма усредним полученные вероятности при помощи логарифма:

(5).

Если (5)> 0, значит s1(cl1)⊕s2(cl2)⊕s3(cl3)=0, в противном случае s1(cl1)⊕s2(cl2)⊕s3(cl3)=1.

Опишем атаку полностью в виде алгоритма:
  1. Выбираем интервал C. Например С=[79,86]
  2. Пусть переменные cl1,cl2,cl3 пробегают все значения из интервала C, для каждого фрейма вычисляем (4)
  3. Для всех полученный значений вычисляем (5)
  4. На основании значения Δ выбираем значение s1(cl1)⊕s2(cl2)⊕s3(cl3)

Результатом выполнения данного алгоритма будут 512 уравнений вида s1(79)⊕s2(79)⊕s3(79)=0, состоящие из 8 неизвестных. Решив эту систему уравнений простым перебором, мы получим по 8 бит начального значения каждого регистра.
Повторив алгоритм еще два раза для интервалов [87, 94] и [95, 102] мы получим по 24 бита начального состояния каждого из регистров. Этого нам более чем достаточно. Прокрутим каждый из регистров 101 раз назад мы получим как раз то состояние регистров, которое было после второго шага инициализации, т.е. после загрузки в регистры ключевых битов. И теперь мы можем сгенерировать всю ключевую последовательность целиком.

C# класс A5attack
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Collections;

namespace A5project
{
    class A5attack
    {
        private double[] factorials = new double[150];

        //Вычисление Pr(cl1,cl2,cl3 в позиции v)
        private double PinVth(int cl1, int cl2, int cl3, int v)
        {            
            double  y=0;
            double x = 0;
            double z = 0;
            double w = 0;
            if((v - (v - cl1) - (v - cl2) - (v - cl3))>=0)
                y=factorials[v - (v - cl1) - (v - cl2) - (v - cl3)];
            else
                y=1;
            if ((v - cl1) >= 0)
                x = factorials[v - cl1];
            else
                x = 1;
            if ((v - cl3) >= 0)
                z = factorials[v - cl3];
            else
                z = 1;
            if ((v - cl2) >= 0)
                w = factorials[v - cl2];
            else
                w = 1;
            double a = factorials[v] / (x * factorials[v - (v - cl1)]);
            double b = factorials[v - (v - cl1)] / (w * factorials[v - (v - cl1) - (v - cl2)]);
            double c = factorials[v - (v - cl1) - (v - cl2)] / (z * y);
            double d = Math.Pow(4, v);
            return (a * b * c) / d;
        }

        private double factorial(int x)
        {
            double result=1;
            for (int i = x; i > 1; i--)
                result = result * i;
            return result;
        }

        private bool[] reg = new bool[19];
        private bool[] reg2 = new bool[22];
        private bool[] reg3 = new bool[23];

        //неполная инициализация, предполагается что ключевые биты уже загруженные в регистры
        public void KeySetup(int[] frame)
        {
            for (int i = 0; i < 19; i++)
                reg[i] = false;
            for (int i = 0; i < 22; i++)
                reg2[i] = false;
            for (int i = 0; i < 23; i++)
                reg3[i] = false;
            BitArray FrameBits = new BitArray(frame);
            for (int i = 0; i < 22; i++)
            {
                clockall();
                reg[0] = reg[0] ^ FrameBits[i];
                reg2[0] = reg2[0] ^ FrameBits[i];
                reg3[0] = reg3[0] ^ FrameBits[i];
            }
        }

        //процедуры по управлению сдвигами регистров
        private void clock()
        {
            bool majority = ((reg[8] & reg2[10]) | (reg[8] & reg3[10]) | (reg2[10] & reg3[10]));
            if (reg[8] == majority)
                clockone(reg);

            if (reg2[10] == majority)
                clocktwo(reg2);

            if (reg3[10] == majority)
                clockthree(reg3);
        }

        private bool[] clockone(bool[] RegOne)
        {
            bool temp = false;
            for (int i = RegOne.Length - 1; i > 0; i--)
            {
                if (i == RegOne.Length - 1)
                    temp = RegOne[13] ^ RegOne[16] ^ RegOne[17] ^ RegOne[18];
                RegOne[i] = RegOne[i - 1];
                if (i == 1)
                    RegOne[0] = temp;
            }
            return RegOne;
        }

        private bool[] clocktwo(bool[] RegTwo)
        {
            bool temp = false;
            for (int i = RegTwo.Length - 1; i > 0; i--)
            {
                if (i == RegTwo.Length - 1)
                    temp = RegTwo[20] ^ RegTwo[21];
                RegTwo[i] = RegTwo[i - 1];
                if (i == 1)
                    RegTwo[0] = temp;
            }
            return RegTwo;
        }

        private bool[] clockthree(bool[] RegThree)
        {
            bool temp = false;
            for (int i = RegThree.Length - 1; i > 0; i--)
            {
                if (i == RegThree.Length - 1)
                    temp = RegThree[7] ^ RegThree[20] ^ RegThree[21] ^ RegThree[22];
                RegThree[i] = RegThree[i - 1];
                if (i == 1)
                    RegThree[0] = temp;
            }
            return RegThree;
        }

        private void clockall()
        {
            reg = clockone(reg);
            reg2 = clocktwo(reg2);
            reg3 = clockthree(reg3);
        }

        //вычисление возвращаемого бита, когда регистры находятся в положениях cl1, cl2 и cl3
        public bool Oj(int cl1,int cl2, int cl3)
        {            
            for (int i = 0; i < cl1; i++)
            {
                clockone(reg);                
            }
            for (int i = 0; i < cl2; i++)
            {                
                clocktwo(reg2);                
            }
            for (int i = 0; i < cl3; i++)
            {                
                clockthree(reg3);
            }
            return (reg[18] ^ reg2[21] ^ reg3[22]);
        }

        //Вероятность того, что для данного фрейма XOR выходных битов регистра равен нулю
        public double Pj(int cl1, int cl2, int cl3, int j, bool[] frame)
        {
            double result = 0;
            double rightPart = 0;
            int[] framenumb=new int[1]{j};            
            KeySetup(framenumb);
            bool[] tempReg = new bool[19];
            bool[] tempReg2 = new bool[22];
            bool[] tempReg3 = new bool[23];
            Array.Copy(reg, tempReg, 19);
            Array.Copy(reg2, tempReg2, 22);
            Array.Copy(reg3, tempReg3, 23);
            bool FramesBit = Oj(cl1, cl2, cl3);
            for (int i = 100; i < 100 + 50; i++)
            {
                Array.Copy(tempReg, reg, 19);
                Array.Copy(tempReg2, reg2, 22);
                Array.Copy(tempReg3, reg3, 23);
                double temp = PinVth(cl1, cl2, cl3, i);
                rightPart += temp;                
                if((FramesBit^frame[i-100])==false)
                    temp=temp*1;
                else
                    temp=0;
                result += temp;
            }
            result = result + ((1 - rightPart) / 2);
            return result;
        }

        //Общая вероятность того, что биты cl1, cl2, cl3 в сумме дают 0. Если >0 тогда значение записывается как 0
        //в другом случае, как 1
        public double LikehoodRatio(int cl1, int cl2, int cl3, bool[] keystream)
        {
            double result = 0;
            for (int i = 0; i < keystream.Length/228; i++)
            {
                bool[] temp=new bool[228];
                Array.Copy(keystream,i*228,temp,0,228);
                double x=Pj(cl1, cl2, cl3, i, temp);
                result = result + Math.Log(( x/ (1 - x)));
            }
            return result;
        }

        public bool FindKeyBit(int cl1, int cl2, int cl3, bool[] keystream)
        {
            for (int i = 0; i < 150; i++)
                factorials[i] = factorial(i);
            if (LikehoodRatio(cl1, cl2, cl3, keystream) >= 0)
                return false;
            else
                return true;
        }

        //Загружает в регистры полученные биты и восстанавливае начальное значение
        public bool[][] checkSol(byte[] first, byte[] second, byte[] third)
        {
            byte[] newFirst = new byte[3];
            newFirst[0] = first[0];
            newFirst[1] = second[0];
            newFirst[2] = third[0];
            byte[] newSecond = new byte[3];
            newSecond[0] = first[1];
            newSecond[1] = second[1];
            newSecond[2] = third[1];
            byte[] newThird = new byte[3];
            newThird[0] = first[2];
            newThird[1] = second[2];
            newThird[2] = third[2];
            bool[] firstArr1 = new BitArray(newFirst).Cast<bool>().ToArray().Reverse().ToArray();
            bool[] firstArr = new bool[19];
            Array.Copy(firstArr1, 5, firstArr, 0, 19);
            bool[] secondArr1 = new BitArray(newSecond).Cast<bool>().ToArray().Reverse().ToArray();
            bool[] secondArr = new bool[22];
            Array.Copy(secondArr1, 2, secondArr, 0, 22);
            bool[] thirdArr1 = new BitArray(newThird).Cast<bool>().ToArray().Reverse().ToArray();
            bool[] thirdArr = new bool[23];
            Array.Copy(thirdArr1, 1, thirdArr, 0, 23);
            for (int i = 0; i < 101; i++)
            {
                BackClockone(firstArr);
            }
            for (int i = 0; i < 101; i++)
            {
                BackClocktwo(secondArr);
            }
            for (int i = 0; i < 101; i++)
            {
                BackClockthree(thirdArr);
            }
            bool[][] result = new bool[3][];
            result[0] = firstArr;
            result[1] = secondArr;
            result[2] = thirdArr;
            return result;
        }

        private void BackClockone(bool[] RegOne)
        {
            bool temp = false;
            for (int i = 0; i < RegOne.Length-1; i++)
            {
                if (i == 0)
                    temp = RegOne[0];
                RegOne[i] = RegOne[i+1];
                if (i == (RegOne.Length-2))
                    RegOne[RegOne.Length - 1] = temp ^ RegOne[13] ^ RegOne[16] ^ RegOne[17];
            }            
        }

        private void BackClocktwo(bool[] RegTwo)
        {
            bool temp = false;
            for (int i = 0; i < RegTwo.Length-1; i++)
            {
                if (i == 0)
                    temp = RegTwo[0];
                RegTwo[i] = RegTwo[i + 1];
                if (i == (RegTwo.Length-2))
                    RegTwo[RegTwo.Length - 1] = temp ^ RegTwo[20];
            }            
        }

        private void BackClockthree(bool[] RegThree)
        {
            bool temp = false;
            for (int i = 0; i < RegThree.Length-1; i++)
            {
                if (i == 0)
                    temp = RegThree[0];
                RegThree[i] = RegThree[i + 1];
                if (i == (RegThree.Length-2))
                    RegThree[RegThree.Length - 1] = temp ^ RegThree[7] ^ RegThree[20] ^ RegThree[21];
            }            
        }
    }
}


Используя функцию FindKeyBit следующим образом:
private bool[] attack()
{            
            bool[] keypart=new bool[512];
            int count = 0;
            A5attack tryattack = new A5attack();
            for(int i=79; i<87;i++)
                for(int j=79; j<87; j++)
                    for (int k = 79; k < 87; k++)
                    {
                        bool temp=tryattack.FindKeyBit(i, j, k, keystream);
                        int time = finish - start;
                        keypart[count] = temp;
                        count++;
                    }
        return keypart;
        }

мы получим массив из 512 значений в котором записаны XOR ключевых бит начиная с позиции 79 по позицию 86.

Получив все 24 бита из каждого регистра, и переведя их в байтовые массивы проверяем наше решение:
Private void checkSolution()
{
A5attack LetsAttack = new A5attack();
int[] testframe = new int[1] { 0 };
bool[][] startState = LetsAttack.checkSol(first, second, third);
A5Enc a5check = new A5Enc(startState);
bool[] TempFrame = new bool[228];
a5check.KeySetup(testframe);
TempFrame = a5check.A5(true);
for (int l = 0; l < 228; l++)
{
     find = true;
     if (keystream[l] != TempFrame[l])
      {
           find = false;
           break;
       }
}
}

Если полученный фрейм совпадает с первым фреймом известного ключевого потока, значит атака была реализована успешно и мы вскрыли сеансовый ключ алгоритма A5/1.

Часть 4: заключительная


Подводя итог, хочу отметить что описанная атака является одной из первых подобных атак. Наиболее совершенная из них позволяет с 90% вероятностью вскрыть сеансовый ключ из всего 2000 фреймов(9 секунд разговора). Таким образом, корреляционные атаки — весьма серьезная угроза не только в теории, но и на практике.

Литература и ссылки




PS: автор будет признателен, если кто-нибудь поделится работой Barkan, Elad; Eli Biham (2005). «Conditional Estimators: An Effective Attack on A5/1». В ней описывается атака, которую я упомянул в заключительной части.
UPD: все вопрос снят, спасибо пользователю whitequark.
Алексей @NeverWalkAloner
карма
179,7
рейтинг –1,6
Пользователь
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Спецпроект

Самое читаемое Разработка

Комментарии (42)

  • +7
    Один замок лишний.
    • +1
      Мало того, остальные надо было вешать в параллель, а не последовательно. Так достаточно любой из них сломать и дверь откроется. В общем, классические проблемы безопасности :)
      • +4
        Так это замок, чтобы каждый владелец мог неазвисимо зайти, не дожидаясь другого владельца замка.
  • +1
    Из схемы видно, что алгоритм шифрования применяется только между мобильной станцией и базовой станцией. Между БС и ЦА (коммутатором) ни один из описанных выше алгоритмов не применяется.
    • –1
      Вот и я слышал, что шифруется до ближайшей соты: мол, достаточно поставить в соседнем с нужным офисом микросоту (которую ставят в офисах, чтобы улучшить качество сигнала) и слушать весь трафик.
  • +1
    И хотя практическое применение такого рода атак весьма сомнительно
    — почему так?
    • 0
      Понимаете мы же вскрываем не постоянный ключ, а сессионный. А собрать 2000 известных фреймов в течении одного разговора весьма затруднительно, одних только системных сообщений не хватит.
    • +1
      Хотя вы знаете, я сейчас начал читать «Conditional Estimators: An Effective Attack on A5/1» так вот там говорится что 2000 фреймов вполне реально собрать из разговора длиной 3-4 минуты, поэтому забираю свои слова обратно. Корреляционные атаки применимы таки на практике.
      • 0
        A5/1 ломается с помощью комплекса на плис с прегенерированными таблицами примерно за 2 минуты. А5/2 на обычном компьютере без дополнительных ломалок за теже 2 минуты.
        • +1
          Но тут то фишка в том, что никаких прогенерированных таблиц не нужно. Корреляционная атака работает без предвычислений.
          • 0
            ) С таблицами намного быстрее.
        • 0
          Можете дать ссылки?
          • 0
            К сожалению нет. Личный опыт.
            • 0
              Скольких минут/секунд разговора достаточно для взлома A5/1 с использованием таблиц?
              • 0
                :) Указанное примерно верно.
    • 0
      Большое спасибо.
  • +1
    А кто-то может вкратце описать ситуацию с возможностью или невозможностью способа перехвата разговоров? Так сказать «на пальцах». Какова цена вопроса создания работающего комплекса и каковы механизмы и особенности работы?
    • 0
      Мне кажется такие вещи уже давно есть.
      Ну в подполье разумеется.
      • 0
        Вот скажем такой кейс: Alice собирается отвезти для Bob мешок налички. Для чего должна созвонится с ним о дате и месте доставки. Какова вероятность того, что Jack, зная об этом, сможет купить/собрать/взять в аренду/ комплекс перехвата?

        Судя по новостям, подполье же может теперь быть доступно многим?
    • +1
      Упс, habrahabr.ru/post/186838/#comment_6503842 предназначался вам.
    • 0
      Те кто знают — описывать не будут. Государственная/коммерческая тайна.
      Цену вопроса можете аппроксимировать сами: комплекс с кучей СВЧ плат + ломалка на недешевых ПЛИС + написание софта под это всё.
      • +1
        Так вот и вопрос — нужна ли куча СВЧ плат и всё такое или ситуация такова, что «на основе USRP (~$2k) и OpenBTS — монитор там уже есть, надо только декодер добавить.»
    • +1
      Реализация MiTM на GSM подробно описана здесь: www.isti.tu-berlin.de/fileadmin/fg214/finished_theses/kostrzewa/diplom_kostrzewa.pdf

      Цена вопроса: ~$2k на USRP и некоторое количество человеко-часов на допил OpenBTS.
    • +2
      В моем информационном пространстве в 2009 проскакивала инфа про некую аппаратуру, которая делает нечто подобное, одновременное ведение 5 номеров — порядка 200 000 вполне российских рублей, ведение 100+ номеров от 1.5 млн рублей.

      У нашей славной службы из трех букв имеется аппарат с названием из пяти букв, который это умеет делать менее чем с 2000 фреймов. Предрасчетные таблицы используются тоже.

      Инфа достоверная 146% ;)

  • +1
    Покупаете SDR, пишете софт, готово. SDR нынче дёшевы.

    :)

    Из существующих решений, мне кажется, проще всего сделать что-нибудь на основе USRP (~$2k) и OpenBTS — монитор там уже есть, надо только декодер добавить.
    • 0
      Это не я :) Я за Alice и Bob или то, что от них останется переживаю.
      Т.е. условно, везде где риск потерять больше нескольких тыс. $ вероятного ущерба надеяться на защиту сотовой сети нельзя.
      • 0
        Конечно. И стоимость будет только падать — SDR дешевеют почти экспоненциально (а может, и не почти).
        • 0
          Когда искать лоты полностью готовых устройств на алиэкспрессе?
          • 0
            Никогда. Китайцы собирают все на МТК, а там уже готовая платформа, отчасти в бибилотеках.
  • –2
  • 0
    Результатом этого исследования стал повсеместный отказ от алгоритма COMP128

    Насколько мне известно даже сейчас все еще можно купить карту МТС или Билайн с COMP128-1 и получить Ki.
    Мегафон же изначально использовал не COMP128-1.
  • 0
    я так понимаю что авторизация стороны оператора вообще не предусмотрена?
    • 0
      Не предусмотрена :(
      Поэтому в реальной жизни возможен целый ряд атак на основе fake BTS (см. ссылку на pdf в ответе выше).
      • 0
        В реальной жизни атака на основе «fake bts» не так проста. Предположим, вам удалось создать эмуляцию MSC и BSC на обычном ноутбуке, вы настраиваете и подключаете BS и выжидаете «жертву». Если излучение антенны достаточно мощное, то, скорее всего, в ваше сети сразу зарегистрируется большое количество абонентов, но (!) при одном условии: телефон только что включили. Иначе, как произойдет хэндовер в вашу фэйковую сеть? Абонент зарегистрировался и хочет позвонить, но не сможет, т.к. вызываемого абонента скорее всего не будет в фэйковой сети, и дозвон в другие сети тоже отсутствует. Сеть то фэйковая. Абонент связывается с контактным центром своего оператора и жалуется. Количество жалоб растет. Оператор знает, что в указанном месте связь присутствует, поэтому делает вывод, что что-то мешает регистрироваться абонентам в сети, скорее всего посторонний сигнал. Эта информация доводится до радио-частотного центра. Их специалисты выезжают на место и пеленгуют источник излучения. Все! С момента первой жалобы до момента пеленга пройдет от одного до пары часов. Поэтому на практике атака на основе фэйковой БС сопряжена с риском быть обнаруженным в течение короткого промежутка времени.
        • +1
          Атаковать можно, например, в метро. Когда «жертва» заходит в метро, сигнал настоящей БС теряется, а тут мы такие красивые с ноутбуком. И ни у кого мысли позвонить в метро даже не возникнет. А если возникнет — то ошибка не будет чем-то сверхестественным. Можно осуществлять атаку на постоянный ключ, например, просто ездя в одном вагоне метро с жертвой. А если учесть, что атака может быть «размазана» по времени, то можно просто недельку-другую ездить с жертвой, и в итоге получить постоянный ключ.
        • 0
        • +1
          но (!) при одном условии: телефон только что включили. Иначе, как произойдет хэндовер в вашу фэйковую сеть?

          См. главу 2.4.2 в PDF-ке по ссылке из комментария выше: или глушить сигнал настоящей BTS, или вещать на более высокой мощности в следствии чего MS сам перейдет на ваш фейковый BTS в следствии forced BTS seclection.

          Абонент зарегистрировался и хочет позвонить, но не сможет, т.к. вызываемого абонента скорее всего не будет в фэйковой сети

          Матчать не читай @ сразу отвечай. Выше приводил ссылку на методологию атаки, ознакомьтесь.
          Fake BTS, помимо всего прочего, реализует функции еще и fake MS, для переадресации вызовов в реальную сеть.
          • 0
            Довожу до вашего сведения, что команду на хэндовер MS получает от BSC! т.е. должна быть связь между настоящим MSC и фэйкомым, что на практике не возможно. Ваша единственная возможность — отключить настоящую сеть, либо действовать там, где сети нет априори. Однако, даже это вызовет подозрения у абонентов — сеть есть там, где ее не было и звонки не проходят. Если вы заглушите сигнал настоящей БС, то вас обнаружат. Если вы увеличите мощность своего передатчика, вас обнаружат еще быстрее. С увеличением мощности, увеличится радиус «поражения», и, как следствие, количество жалоб на качество связи. Методология атаки — это «сферический конь в вакууме», на практике же подобные атаки сложны в техническом и организационном плане. К тому же, если ваш фэйковый BTS реализует функции MS, то вы вдвойне рискуете, ибо вообще засветите свой номер и обнаружить вас будет еще легче.
    • 0
      в 3G/4G сетях предусмотрена. 2G дырявый, да.

      Пару лет назад был скандал, когда какие-то шустрые ребята в газели ловили TMSI.
  • 0
    А что слышно про практические аспекты безопасности GSM? Известны ли случаи достоверного перехвата разговоров/сообщений через радиоканал? Сводит ли наличие СОРМ все технологии защиты к одной?
  • 0
    Тут вопрос в стоимости задачи и доступа третьих лиц. Одно дело СОРМ, где доступ могут получить только сотрудники органов, и то не все и не по всем.
    Другое дело, когда технология станет доступна кому попало. Вот я выше и пытался это выяснить.

    Есть правда еще один аспект. Когда для контроля активности может быть создана служба «Государственная Инспекция Безопасности Движения Данных (ГИБДД)» сотрудники которой смогут «стоять на информационных магистралях» и сшибать копеечку.

Только зарегистрированные пользователи могут оставлять комментарии. Войдите, пожалуйста.