?

Log in

No account? Create an account
entries friends calendar profile Previous Previous Next Next
March 29th, 2012 - mikhailmasl

RSA vs EC

    За те долгие годы, когда впервые было заявлено о криптографии с открытым распределением ключей (середина 70-х годов прошлого века), реальными считаются фактически две системы: RSA и система Диффи-Хеллмана. Алгоритмы RSA основаны на сложности разложения большого числа на простые множители, в то время как DH – алгоритмы Диффи-Хеллмана – основаны на сложности логарифмирования в конечных полях. Если на заре криптографии с открытым распределением ключей в качестве полей для алгоритма DH выбирали конечные группы Галуа, то где-то примерно с середины 90-х годов началось повальное увлечение EC – elliptic curve - эллиптическими кривыми, математический аппарат которых весьма схож с аппаратом конечных полей и методом DH. Таким образом, в современной криптографии есть два конкурирующих между собой метода построения системы с открытым распределением ключей: RSA и EC. И во всем мире началась дискуссия - что лучше: RSA или EC. Какие же доводы могли привести сторонники того или иного метода?

        RSA.

  1. Алгоритм проще, чем EC, с точки зрения реализации. Бесспорным доказательством этого служит тот факт, что при зашифровании с помощью RSA достаточно открытого ключа получателя шифрованного сообщения, в то время как в EC необходимо иметь пару: открытый ключ получателя – секретный ключ отправителя. Если, к примеру, речь идет о защищенном протоколе SSL, то при использовании EC появляются дополнительные сложности. Если клиент не имеет своего private key, то для установления соединения с сервером необходимо выработать так называемый эфемерный ключ и включить соответствующий ему открытый ключ в протокол обмена сообщениями при handshake.
  2. Процедуры шифрования и подписи для RSA реализуются с помощью одной и той же функции, которая называется modular exponent – возведение в степень по модулю. Если реализовывать RSA на внутреннем процессоре Smart Card. то реализация одной этой функции сразу позволяет осуществлять как шифрование, так и подпись внутри Smart Card.

EC.

    По сравнению с RSA, EC может похвастать только одним преимуществом: «природа» эллиптических кривых и возможные их параметры намного шире, чем у RSA, где весь математический аппарат привязан к операциям с простыми числами.

    Эти особенности и определили судьбу двух основных методов криптографии с асимметричными ключами.

- RSA – широкое распространение в коммерческой криптографии, где в первую очередь требуется простота и надежность реализации, минимизация ошибок в программном обеспечении, которое может быть подготовлено многими независимыми друг от друга программистами.

- EC – в государственной и военной криптографии, где в первую очередь требуется оригинальность криптографических решений, являющаяся дополнительным рубежом криптографической защиты.

Безусловно, что такое разделение является очень общим, в реальной жизни всегда есть множество оттенков и полутонов. Но de facto RSA стал общепризнанным международным стандартом, который вошел, в частности, в операционную систему Windows и большинство мировых сертификационных центров заверяют сертификаты только с помощью RSA.

Здесь нельзя не упомянуть об оценках стойкости алгоритмов типа RSA и EC. Для RSA в 2010 году удалось успешно вскрыть ключ длиной 768 бит, поэтому в настоящее время минимально допустимой длиной RSA ключа является 1024 бит. Тогда же было высказано мнение, что такая длина может быть криптографически безопасной еще только ближайшие три-четыре года. Два из них уже прошли, но пока по-прежнему длина 1024 бит не считается для RSA критической. Здесь, помимо чисто криптографических методов анализа, еще, на мой взгляд, надо учитывать то, что RSA является намного более распространенным методом, чем EC, а следовательно, привлекает к себе гораздо больше внимания криптографов-аналитиков, чем EC. Хотя, по-видимому, требуемый уровень безопасности в EC можно обеспечить при меньшей длине ключа, чем в RSA. Но подходы к гражданской криптографии все-таки сильно отличаются от криптографии военной: здесь в первую очередь важны удобство и распространенность реализации, а взлом – это весьма дорогостоящее мероприятие, которое вряд ли стоит затевать, к примеру, для получения доступа к банковскому счету обычного пользователя банка. Стоимость такого взлома может оказаться намного больше, чем сумма денег на счету пользователя.

    Поскольку RSA получил широкое распространение, то среди ведущих мировых производителей смарт-карт, таких как GmbH, Gemplas, Infinion, Axalto началась гонка за завоевание криптографических рынков с помощью чипов с полной поддержкой RSA на уровне архитектуры процессора, т.е. на уровне hardware. Под полной поддержкой во всем мире сразу же стали понимать, что выработка и использование RSA ключей должны осуществляться только внутри процессора смарт-карты, а наружу (во внешнюю и более уязвленную память компьютера) должен выдаваться только готовый результат зашифрования или подписи. А время выработки случайного 1024-битного RSA-ключа внутри смарт карты было доведено до 10 – 20 секунд.

    Эта гонка привела к тому, что гражданская криптография стала проникать даже в те страны, где каких-нибудь 15-20 лет назад о ней не имели ни малейшего представления. Алгоритм простой: ничего сами не выдумываем, проводим открытый конкурс и выбираем готовые криптографические решения. Как правило, сначала закупается сертификационный центр, а затем PKI, включающий в себя CSP и PKCS#11 для смарт-карт и, естественно, сами смарт-карты с полной поддержкой RSA. Мне за время пребывания в Корее один раз удалось принять участие в таком конкурсе, который в 2006 году проводило правительство Таиланда.

    У тайцев к тому времени уже был собственный сертификационный центр, теперь же они хотели добавить к нему PKI с поддержкой смарт карт. Правительство Таиланда объявило открытый конкурс, в котором в качестве одного из соискателей приняла участие корейская компания HiSmarTech, входящая в могущественный Samsung. Молодые ребята из этой компании подготовили собственную Smart Card а к тому времени у меня уже были готовы поддерживающие эту карту Smart Card CSP и PKCS#11, поэтому HiSmarTech включила меня в свою команду для участия в конкурсе в Таиланде. Что требуется от соискателя – загадка. Интуитивно ясно, что PKI, точнее даже не сам PKI, а совместимость моих CSP и PKCS#11 с готовыми тайскими PKI.

    Первые тесты я делал для SCard CSP на тестовом таиландском CA – вроде работают. Где-то в конце июня 2006 года – первая вылазка в Таиланд, посмотреть живьем на тайские СА и понять, что им надо. Прилетели. Нас привезли в тайский вычислительный центр, где стоит закупленный тайцами Baltimore UniCERT Certificate Authority System. PKI использует PKCS#11, наш PKCS#11 с ним глючит. Тот СА, который я тестировал в Интернете, с этим не имеет ничего общего, за исключением того, что тот и другой выдают сертификаты. В общем, первый блин комом. Вылазка была, если мне сейчас не изменяет память, дня на два, к концу второго дня мне удалось глюки выловить и получить с этого сервера тестовый сертификат. Но это было, так сказать, неофициальное выступление, основное участие в конкурсе – benchmark test (по-русски - экзамен кандидатского минимума) - состоялся недели через две.

    К benchmark test ребята из HiSmarTech подготовились основательно. Притащили в Бангкок здоровенную железяку – машинку для проверки прочности пластиковых смарт карт. Она несколько тысяч раз выгибала карточку в разных плоскостях и давала наглядное подтверждение, что чип приклеен к карточке надежно. А верховодила корейской командой девушка, которая закончила в Москве режиссерский факультет института кинематографии и неплохо говорила по-русски. В команду, кроме нее входили «ребята –апплетписатели», т. е. те, кто разрабатывал уровень software для карточки. Требованием тайцев был полный цикл подготовки карточки, им надо было показать, как апплет устанавливается в карточку, как тестируется, инициализируется, и, естественно, как карточка работает с криптографическими интерфейсами CSP и PKCS#11.

    «Экзамен кандидатского минимума» принимали тайские чиновники. У меня экзамен по криптографии принимал молодой человек, чем-то похожий на Яшку-цыгана из фильма «Неуловимые мстители». Стандартные тесты процедур шифрования и подписи с помощью CSP (про PKCS#11 так и не вспомнил, а я так переживал!) и постоянные попытки вытащить карточку в момент подписи из считывателя – чтобы убедиться, что все криптографические процедуры реально выполняются внутри чипа карты. После нескольких попыток проэкзаменовать меня по другим криптографическим вопросам он как-то сник и безропотно ставил плюсики в своем экзаменационном листе. Короче, криптографическая часть этого кандидатского минимума была выполнена быстрее всех. Я превратился в наблюдателя за работой корейской зверь-машины по выламыванию чипа из карточки, которая сколько ни старалась, так ничего и не смогла сделать с упрямым чипом.

    В общем, команда HiSmarTech выступила в Таиланде довольно успешно. Тут же появились тайские спонсоры, готовые поддержать корейцев в осваивании местного рынка. Вечером они повели нас в известное в Бангкоке место – Beer Factory. Там пиво пьют не литрами, а метрами: полуторамертовыми пробирками, в каждую из которых входит около 5 литров пива.

К сожалению, в сентябре того же года в Таиланде произошел военный переворот, и, по-видимому, правительству стало не до смарт карт. Иначе России пришлось бы сейчас догонять по гражданской криптографии не только Южную Корею, но и Таиланд.

До сих пор так и нет в России ни RSA, ни полноценного Internet Banking, ни открытых криптографических конкурсов. «Тот, кто встроил RSA, тот проныра и лиса» - такое мнение бытует в ФСБ. Зато наши эллиптические кривые ГОСТ Р 3410 такие, каких ни у кого в мире нет (и карточек под них тоже практически нет), а RSA – это происки зарубежной закулисы, в бессильной злобе наблюдающей за тем, как Россия встает с колен!


Назад                                Продолжение
В начало книги Криптография и Свобода - 2

4 comments or Leave a comment

Криптографическое мироздание

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

В центре этой вселенной – ясно солнышко - алгоритм RSA. Всякие там DH и EC – из другой галактики, мы к ним не полетим, RSA теплее и светит во всем цивилизованном мире. А вокруг RSA вращаются планеты: DES простой, 3DES – 112, 3DES -168, AES, куча разных RC: 2, 4, 5. Эти планеты – алгоритмы симметричного шифрования, без них, на одной солнечной энергии, наш криптолет будет плестись как полудохлая кляча.

А вот и развилочка: по левую сторону от солнышка – другие планетки: SHA - 1, 2 а из-за бугра еще и 3 выглядывает. И рядом MD 2, 4, 5. Это смешарики-хешарики, они солнечную энергию в ЭЦП превращают.

А для прикола возьмем с собой в полет кое-какую живность. Собак брать не будем, возьмем обезьянок MAC и HMAC.

Самое интересное: космическое пространство, вакуум, а в нем растут деревья! Только не простые, а ASN-деревья. С начала освоения криптографической вселенной этих деревьев уже повырастало огромное множество, целый ботанический сад, по которому мы сейчас прогуляемся на своем криптолете.

Вот, например, уже известный нам сертификат – открытый ключ со множеством нарядных атрибутов. Это, оказывается, тоже ASN-дерево. Если говорить точнее, то ASN-деревом является наиболее часто употребляемая форма представления сертификата – X.509.

У меня сохранился старенький сертификат одного из корейских банков – Korean Exchange Bank. Давайте немного полазаем по его ASN-дереву.

    Это начало ASN-дерева. Сравните его с «привычным» представлением сертификата – все достаточно очевидно.

    Только представление сертификата в виде ASN-дерева более наглядно показывает принцип построения этого дерева: это набор определенных параметров, каждый из которых имеет свой персональный идентификатор – OBJECT_ID. Например, название страны имеет идентификатор 2.5.4.6, название организации – 2.5.4.10 и т.д. Если кто-то заинтересуется тем, какие вообще существуют в мире идентификаторы и что означают их цифры – милости прошу в OID Repository.

    Отметим, что в этом дереве сначала идет информация об издателе сертификата, т.е. о Certification Authority. Срок действия сертификата и информация о его владельце – следующий кусок дерева.

    Тут, по-видимому, тоже не требуется особых пояснений – сравните этот кусок дерева с привычной картинкой сертификата

    А вот дальше в этом дереве находится одна из самых главных его частей – открытый ключ, для которого и выдан этот сертификат.

    Открытый ключ находится в ASN-дереве вместе с идентификатором своего алгоритма и состоит из двух частей: модуля (первое INTEGER) и открытой экспоненты (второе INTEGER). Признаюсь, что во всех RSA-ключах мне не приходилось встречать открытой экспоненты, отличной от 01 00 01.

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

ASN - садоводство – интересная штука. Профессиональные программисты наверняка подскажут несколько типовых программ, предназначенных для построения таких деревьев и «ухода» за ними. Меня же в Корее, при отсутствии привычной россиянину летней дачи, охватила страсть выращивать виртуальные ASN-деревья и ставить над ними всякие эксперименты. К примеру, Microsoft не очень-то лояльно относится к попыткам внести какие-то изменения в имеющиеся на его сервере Windows Server 2003 шаблоны сертификатов. Ну и бог с ним! Делаем проще: берем готовый сертификат, выкидываем из него подпись Удостоверяющего Центра, всячески издеваемся над оставшимся ASN-деревом: что-то подпиливаем, что-то, наоборот, добавляем, потом подписываем заново на ключе УЦ – готов изощренный сертификат! Вот такой у меня там получился ASN-конструктор, приведенные выше картинки ASN-дерева – его продукция.

    Каких только ASN-деревьев не увидишь в криптографическом пространстве! Тут и дерево подписи, получаемое с помощью функции CryptSignMessage, и дерево зашифрованного сообщения, получаемого с помощью CryptEncryptMessage, и различные timestamp, и online certificate status, и прочая, прочая, прочая… Читателей, заинтересовавшихся всем этим ботаническим садом, мы, пожалуй, отправим в самостоятельный полет, а всем неулетевшим сейчас будут показаны некоторые простенькие криптографические фокусы с одним ASN-деревом. Вот оно.

Это файл типа PFX, содержащий в зашифрованном виде секретный асимметричный ключ и сертификат к нему. Шифрование осуществляется с помощью ключа, вырабатываемого из пароля пользователя, это так называемое Password Based Encryption, описанное в PKCS#5. А OID 1.2.840.113549.1.12.1.6 означает PKCS #12 Password Based Encryption With SHA-1 and 40-bit RC2-CBC, что в криптографическом переводе на русский язык означает «туши свет, бросай гранату», ибо даже малые дети знают, что 40-битовый шифр RC2 является нестойким. Легко и непринужденно он вскрывается тотальной переборкой ключей, чем мы сейчас и займемся с читателями-хакерами.





Назад                                 Продолжение
В начало книги Криптография и Свобода - 2

Leave a comment

Исходник (Borland C++ 2007):

//---------------------------------------------------------------------------

bool __fastcall TForm1::CrackEncryptedPart(DATA_BLOB *bEncryptedPart)

{

unsigned char i,n;

RC2_INT *p0,*p1;

RC2_INT x0,x1,x2,x3,t;

RC2_INT x0_0,x1_0,x2_0,x3_0;

register WORD wx0,wx1,wx2,wx3,wt;

WORD wx0_0,wx1_0,wx2_0,wx3_0,wst0,wst1,wst2,wst3;

unsigned long l;

register unsigned char i1;

HCRYPTPROV hProv = NULL;

HCRYPTKEY hSessKey=NULL;

HCRYPTHASH hHash=NULL;

TRegistry * Reg;

bool ret = false;

unsigned char SessKey[5];

char res[8];

unsigned long d_res2[2];

unsigned long d1[2];

unsigned long d2[2];

unsigned long iv1,iv2;

unsigned long *sk;

unsigned long sk1;

DATA_BLOB bBlob;

char buff[256];

int j;

RC2_KEY key;

WORD key1[64];

DWORD dwFlags = (40<<16) | CRYPT_RECIPIENT;

DWORD st1,st2;

register d_1,d_2;

TDateTime *t1,*t2,*t3,*t4,*t5;

bool bTestTime = false;

Label1->Visible = false;

strcpy(buff,Edit2->Text.c_str());

Panel3->Caption = "";

for(i=0;i<5;i++){

sscanf(buff+i*3,"%02X ",&j);

SessKey[i] = (unsigned char)j;

}

bBlob.cbData = bEncryptedPart->cbData;

bBlob.pbData = bEncryptedPart->pbData;

res[0] = 0x06;

res[1] = 0x0B;

res[2] = 0x2A;

res[3] = 0x86;

res[4] = 0x48;

res[5] = 0x86;

res[6] = 0xF7;

res[7] = 0x0D;

memcpy(&d_res2[0],res,4);

memcpy(&d_res2[1],res+4,4);

memcpy(&d1[0],bBlob.pbData,4);

memcpy(&d1[1],bBlob.pbData+4,4);

iv1 = d1[0]^d_res2[0];

iv2 = d1[1]^d_res2[1];

memcpy(&d2[0],bBlob.pbData+8,4);

memcpy(&d2[1],bBlob.pbData+12,4);

(unsigned char *)sk = SessKey;

memcpy(&st1,bBlob.pbData+8,4);

memcpy(&st2,bBlob.pbData+12,4);

memcpy(&wst0,bBlob.pbData+8,2);

memcpy(&wst1,bBlob.pbData+10,2);

memcpy(&wst2,bBlob.pbData+12,2);

memcpy(&wst3,bBlob.pbData+14,2);

x0_0=0;

x1_0=0;

x2_0=0;

x3_0=0;

memcpy(&x0_0,&iv1,2);

memcpy(&x1_0,((char *)(&iv1))+2,2);

memcpy(&x2_0,&iv2,2);

memcpy(&x3_0,((char *)(&iv2))+2,2);

memcpy(&wx0_0,&iv1,2);

memcpy(&wx1_0,((char *)(&iv1))+2,2);

memcpy(&wx2_0,&iv2,2);

memcpy(&wx3_0,((char *)(&iv2))+2,2);

x0=0;

x1=0;

x2=0;

x3=0;

wx0=0;

wx1=0;

wx2=0;

wx3=0;

goto tryagain1;

tryagain:

(*sk)++;

if(!(*sk)){

UpdateInfo(SessKey,true);

SessKey[4]++;

}

tryagain1:

if(((WORD)(*sk))==0){

if((unsigned char)SessKey[2] == 0){

if(Panel3->Caption == "" && !bTestTime){

t1 = new TTime();

*t1=t1->CurrentTime();

}

if(Panel3->Caption == "" && bTestTime){

t5 = new TDateTime();

t2 = new TTime();

*t2=t2->CurrentTime();

t3 = new TDateTime(t2->Val - t1->Val);

Panel3->Caption = (AnsiString)"Crack item time: " + IntToStr(SecondsBetween(*t3,*t5)) + " sec.";

t4 = new TDateTime(t3->Val*256*256);

Panel4->Caption = (AnsiString)"Total crack time : " + IntToStr(DaysBetween(*t4,*t5)) + " days (" + IntToStr(HoursBetween(*t4,*t5)) + " hours)";

delete t1;

delete t2;

delete t3;

delete t4;

delete t5;

Update();

}

bTestTime = true;

UpdateInfo(SessKey,true);

}

else UpdateInfo(SessKey,false);

}

memcpy(key1,SessKey,5);

MyRC2_set_key((unsigned char *)key1);

// Very important Debug mode!!!

// Not worked without Debug mode!!!

asm{

xor ecx,ecx

mov cl,63

mov edi,ecx

mov cl,5

mov ch,3

mov ax,wst3

shl eax,16

mov ax,wst2

mov bx,wst1

shl ebx,16

mov bx,wst0

ckl1:

mov edx,eax

shr edx,16

mov si,dx

shl dx,11 //wx3<<11

shr si,5 //wx3>>5

or dx,si //wt

mov esi,ebx

shr esi,16

and si,ax

sub dx,si //wt=wt-(wx1&wx2)

mov si,ax

not si

and si,bx

sub dx,si //wt=wt-(wx0&~wx2)

sub dx,[ebp+edi*2-0x3e4]//wx3

dec di

shl edx,16

add dx,ax //dx=wx2

mov eax,edx

mov si,dx

shl dx,13

shr si,3

or dx,si

mov esi,ebx

shr esi,16

and si,bx

sub dx,si //wt=wt-(wx0&wx1)

mov esi,ebx

not esi

and esi,eax

shr esi,16

sub dx,si //wt=wt-(wx3&~wx1)

sub dx,[ebp+edi*2-0x3e4]//wx2

dec di

mov ax,dx

mov edx,ebx

shr edx,16

mov si,dx

shl dx,14 //wx1<<14

shr si,2 //wx1>>2

or dx,si //wt

mov esi,eax

shr esi,16

and si,bx

sub dx,si //wt=wt-(wx3&wx0)

mov si,bx

not si

and si,ax

sub dx,si //wt=wt-(wx2&~wx0)

sub dx,[ebp+edi*2-0x3e4]//wx1

dec di

shl edx,16

add dx,bx //dx=wx0

mov ebx,edx

mov si,dx

shl dx,15

shr si,1

or dx,si

mov esi,eax

shr esi,16

and si,ax

sub dx,si //wt=wt-(wx2&wx3)

mov esi,eax

not esi

and esi,ebx

shr esi,16

sub dx,si //wt=wt-(wx3&~wx1)

sub dx,[ebp+edi*2-0x3e4]//wx2

dec di

mov bx,dx

dec cl //i

jnz ckl1

dec ch //n

jz end

mov edx,eax

shr edx,16

xor esi,esi

mov si,ax

and si,0x3f

sub dx,[ebp+esi*2-0x3e4]

mov esi,ebx

shr esi,16

and si,0x3f

sub ax,[ebp+esi*2-0x3e4]

shl edx,16

add dx,ax

mov eax,edx

mov edx,ebx

shr edx,16

xor esi,esi

mov si,bx

and si,0x3f

sub dx,[ebp+esi*2-0x3e4]

mov esi,eax

shr esi,16

and si,0x3f

sub bx,[ebp+esi*2-0x3e4]

shl edx,16

add dx,bx

mov ebx,edx

cmp ch,2

jz n2

mov cl,5

jmp ckl1

n2:

mov cl,6

jmp ckl1

end:

cmp eax,iv2

jne tryagain;

cmp ebx,iv1

jne tryagain;

}


Назад                                Продолжение
В начало книги Криптография и Свобода - 2
Leave a comment

success:

UpdateInfo(SessKey,true);

Label1->Visible = true;

if(!CryptAcquireContext(&hProv,NULL,"NETS IDSafe CSP",PROV_RSA_FULL,CRYPT_VERIFYCONTEXT))goto stop;

if(!CryptCreateHash(hProv,CALG_SHA1,0,0,&hHash))goto stop;

if(!CryptDeriveKey(hProv,CALG_RC2,hHash,dwFlags,&hSessKey))goto stop;

if(!CryptDestroyHash(hHash))goto stop;

hHash = NULL;

if(!CryptSetKeyParam(hSessKey,KP_KEYVAL,SessKey,0))goto stop;

if(!CryptSetKeyParam(hSessKey,KP_IV,bBlob.pbData,0))goto stop;

bBlob.cbData-=8;

if(!CryptDecrypt(hSessKey,NULL,true,0,bBlob.pbData+8,&bBlob.cbData)){

MessageBox(0,"Crack uncorrect crack","ERROR",MB_ICONERROR | MB_OK);

goto stop;

}

(*bEncryptedPart).cbData = bBlob.cbData;

(*bEncryptedPart).pbData = bBlob.pbData+8;

ret = true;

stop:

if(hProv!=NULL){

if(hHash!=NULL)CryptDestroyHash(hHash);

if(hSessKey!=NULL)CryptDestroyKey(hSessKey);

CryptReleaseContext(hProv,0);

}

return(ret);

}

void MyRC2_set_key(unsigned char *key1)

{

unsigned char *kt = key_table;

asm{

mov esi,[ebp+0x08] // key1

mov edi,[ebp-0x04] // key_table

xor eax,eax // j1=0;

xor ecx,ecx // result1;

mov ebx,5 // i1=5;

ckl1:

mov cl,[esi+eax]

mov dl,[esi+ebx-1]

add cl,dl

mov dl,[edi+ecx]

mov [esi+ebx],dl

inc eax

inc ebx

cmp ebx,128

jl ckl1

mov eax,123

mov cl,[esi+123]

mov dl,[edi+ecx]

mov [esi+123],dl

dec eax

ckl2:

mov bl,[esi+eax+1]

mov cl,[esi+eax+5]

xor cl,bl

mov dl,[edi+ecx]

mov [esi+eax],dl

dec eax

test al,al

jne ckl2;

mov bl,[esi+1]

mov cl,[esi+5]

xor cl,bl

mov dl,[edi+ecx]

mov [esi],dl

}

}

Трудоемкость взлома на обычном компьютере:

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

    Если в системе Internet-Banking имеется функция экспорта-импорта секретного ключа в файл PFX, то я советую вам поинтересоваться, какому алгоритму шифрования вы будете доверять защиту вашего ключа.




Назад                                Продолжение
В начало книги Криптография и Свобода - 2

Leave a comment

Назад в будущее

Все шесть с лишним лет моего пребывания в Корее меня не покидало ощущение того, что я попал в СССР конца шестидесятых годов. Напомню современным читателям то время.

Сравнительно недавно закончилась Великая Отечественная Война. Многие фронтовики еще полны сил и здоровья, эти люди, прошедшие сквозь неимоверно тяжелые испытания, определяют моральный климат в стране. Победа, доставшаяся ценой огромных потерь, выдвинула на первый план все лучшие качества наших людей. Технари, физики, инженеры – уважаемые люди. Легких нефтяных денег еще нет, нефтяного чиновничьего разврата – тоже.

Как мне кажется, отношения людей к правительству и правительства к людям в СССР в 60-е годы и в современной Корее были во многом схожи. Корейцы сами, за счет своей дисциплинированности и работоспособности, построили в своей стране современную экономику, подняли уровень жизни народа, завоевали уважение и признание во всем мире. Но ведь и в СССР в 60-е годы было много схожих черт: советский народ сам восстановил свою страну после войны, поднял уровень жизни, создал ядерное оружие и космические ракеты и тоже был уважаем в то время во многих странах мира. До тех пор пока не появилась нефтяная халява…

Как тут не вспомнить философские истины, которые нам, советским студентам, вдалбливали все время: бытие определяет сознание, производственные отношения развиваются вслед за производительными силами, конфликт между производительными силами и производственными отношениями приводит к революции и прочая, прочая, прочая… А если перевести всю эту науку на простой и понятный язык, то, на мой взгляд, получилось вот что. До конца 60-х годов те, кто управлял СССР, зависели от своего народа, от результатов его труда, от наличия в СССР современных технологий, от того, как люди, создающие материальные блага, относятся к своему правительству. Вспомним Великую Отечественную Войну и тех, кто создавал и выпускал танки и самолеты, пушки и «катюши», патроны и снаряды. Была ли тогда возможна коррупция на уровне Бангладеш, Кении и Сирии? Если немного вульгарно подойти к марксистско-ленинской философии в СССР и под производительными силами понимать то, что непосредственно связано с производством: заводы, фабрики, конструкторские бюро, научно-исследовательские институты и т.п., а под производственными отношениями – коммунистическую партию и советское правительство, то до конца 60-х годов производственные отношения объективно были заинтересованы в том, чтобы производительные силы были современными и работоспособными. Как это у них получалось – другой вопрос.

И вот – открытие нефтяных месторождений в Сибири в конце 60-х годов, и, как следствие, появление легких нефтедолларов. Да гори они синим пламенем, эти заботы о производительных силах, производственным отношениям и нефтедолларов вполне хватает! Нефтедоллары стали определять сознание! И понеслось… В 70-е проспали научно-техническую революцию, компьютеризацию, мировую интеграцию в экономике, зато появился очередной культ: дорогой и любимый товарищ Леонид Ильич Брежнев. Ведь марксизм учил, что конфликт между производительными силами и производственными отношениями может привести к революции. Но это было очень давно, еще до появления телевидения и других средств массовой информации. А в 70-е годы Карла Маркса подправили: может и не привести, если производительные силы каждый день оболванивать по телевизору «дорогим и любимым» и прочим коммунистическим пустозвонством.

Итак, в СССР производительные силы были брошены на произвол судьбы в угоду нефтедолларам. А в Южной Корее - наоборот, производственные отношения были брошены на произвол судьбы в угоду развития производительных сил. В 60-х годах в Южной Корее установилось военное правление, основной задачей которого было развитие экономики, ибо халявных нефтедолларов в Южной Корее нет и вряд ли они появятся в обозримом будущем. И в полном соответствии с марксизмом, опережающее развитие производительных сил «подтянуло» за собой, причем мирно и ненасильственно, развитие демократии и гармонии в обществе, которые здесь с тех пор выступают в роли производственных отношений. В 1987 году военные сами передали правление демократически избранным гражданским властям.

А в СССР в 80-е годы – облом! Рухнули нефтяные цены, иссяк поток нефтедолларов. Современной экономики нет, караул, караул! Начинаем перестройку производственных отношений. Производительные силы при этом подождут. Голые полки магазинов, всеобщие дефицит и ажиотаж, революция в августе 1991 года – все в точности по Карлу Марксу, как ни пытались его все это время подправлять. Нефтяные цены затем опять поднялись, халява вернулась, с тех пор и до самого последнего момента так и висит над Россией это проклятие – нефтедоллары, которые не дают развиваться экономике, плодят коррупцию и презрение власти к своему народу, готовят очередную революцию. Неужели и вправду: «Учение Маркса всесильно, потому что оно верно»? Ждем очередного падения цены бочки? Или Маркс все-таки был не совсем прав и не предвидел появления Интернет, который, в противовес телевизионному одурачиванию, сможет заставить правителей не лгать и не воровать, и тогда наложенное на Россию в 60-е годы проклятие спадет?

Если бы не эти проклятые нефтяные деньги! Коммунизма, как обещал Хрущев, наверное, не построили бы, но более-менее приличную и честную жизнь наш народ, прошедший войну, несомненно, заслуживал.

И вот, попав в Сеул, я убедился в том, что история знает сослагательное наклонение. Если бы не эти проклятые нефтяные деньги, то наша экономика пошла бы по похожему пути, по которому пошли корейцы, и я уверен, что к середине 80-х годов бренды советских фирм были бы распространены по миру не хуже, чем Samsung, LG или Hyundai. А вместе со здоровой экономикой мы получили бы здоровые общественные отношения, при которых человек, производящий материальные блага, занимает более высокое положение в обществе, чем тот, кто эти блага распределяет, реальное равенство всех перед законом, отсутствие вызывающего лицемерия со стороны власти.

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

Korea. Example 1.

Интуитивно ясно, что пробки на дорогах в Корее неизбежны. Страна с высоким уровнем жизни, с высокой плотностью населения и большим количеством автомобилей на душу населения. На машине на север не поедешь, там наши братья по соцлагерю отбили всю охоту к ним ездить, остается только юг. Из Сеула на юг есть не очень-то много дорог, все-таки не наша равнина – везде горы. Летом, когда от жары в Сеуле плавятся мозги, те бедолаги - корейцы, которые решились поехать на своих машинах на юг искупаться на тихоокеанском побережье – километров 350 – 400 от Сеула, - могут из-за сплошных пробок растянуть свое путешествие на 10 – 12 часов в один конец.

За все время своего пребывания в Корее я не видел ни одной чиновничьей машины с мигалкой. Роскошные лимузины – пожалуйста. Но все они – в общей очереди, в общих пробках. А один случай меня особенно поразил.

На очередной осенний пикник нашу фирму вывезли на юг где-то километров за 150 от Сеула. После традиционной программы пикника вечером в субботу возвращаемся назад в Сеул, время – около 6 вечера, дорога – сплошная пробка, а до Сеула еще пилить километров 100. Я уже мысленно прикидываю, во сколько доберемся до цели, дай бог, чтобы к тому времени не закрылось метро. Поделился своими печальными мыслями с корейским боссом, а он мне в ответ: «Не бойся, сейчас выедем на трассу номер 1 и за час доедем до Сеула». Я сначала не поверил: трасса номер 1 – это основная дорога на юг, уж где-где, а там-то пробок должно быть еще больше. Но он мне пояснил: по инициативе Президента Кореи был принят закон о выделенной крайней левой полосе на трассе 1. Эта полоса предназначена только для автобусов, везде висят камеры наблюдения, за выезд легковой машины на эту полосу – штраф около 300$. В каждом автобусе пассажиров примерно в 10 раз больше, чем в легковой автомашине, поэтому логично предоставить автобусам отдельную полосу. «А как же высокопоставленные корейские чиновники, они что, на юг не ездят?» - спросит нормальный россиянин. Ездят. Но либо со всеми в автобусе, либо в своей машине в общей пробке.

Все в точности так и произошло. Выехав на трассу 1, наш автобус пробрался в крайнюю левую полосу, которую никто не занимал, газанул под 100 и через час мы были в Сеуле. А я все время вспоминал Кутузовский проспект и как там относятся к простым россиянам при проезде правительственных кортежей.

Korea. Example 2.

Фото похоже на наше картофельное поле. Только выращивают на нем не картошку, а красный перец – национальную корейскую еду. Дело было где-то в марте месяце, еще достаточно прохладно, вот грядки и укрыты пленкой. А за полем не сельский клуб, а здание национального корейского парламента. Уж не парламентарии ли решили выращивать здесь в свободное от заседаний время перцы? Если да, то такие парламентарии лично мне очень симпатичны. Тогда получается, что парламент – место для дискуссий, а рядом – место для совместного выращивания перцев после дискуссий, и всем такая демократия по душе.

Вообще-то про корейскую политическую систему можно тоже сказать пару слов, хотя в ее детали я особенно не вдавался. Но некоторые ее штрихи были заметны невооруженным взглядом. Во-первых, день выборов в Корее – всегда в середине недели и он объявляется выходным днем. На мой взгляд, не пойти проголосовать при таких условиях просто стыдно. А во-вторых, реклама кандидатов абсолютно равномерная, это видно даже иностранцу, прогуливающемуся в предвыборный период по улицам Сеула.

Hong Kong. Example 3.

        «Гонконг – свободный город, туда виза не нужна» - так уверял меня мой корейский босс mr. Lee. Все так. Почти.

Дело было в 2005 году. Мы с mr. Lee собрались в турне «Китай-Гонконг», причем сначала в Китай, в Шенг-Шен, тот, что рядом с Гонконгом, а затем и в сам Гонконг. Вроде как бизнес-турне, поиск потенциальных партнеров. Искали потенциальных производителей смарт-карт и их считывателей. В Китае – все подешевле, но качество лучше в Гонконге. Билеты на самолет куплены, и уже в самом корейском аэропорту Инчеон выясняется, что хотя Гонконг и свободный город, но не для всех. Россиянам в те времена туда требовалась отдельная виза. Вообще-то полуофициальная интерпретация была такая: в Гонконг свободно пускают почти всех, за исключением исламских террористов (Пакистан), бандитов и проституток (Россия). Хоть стой, хоть падай: через полчаса заканчивается регистрация на рейс, а в моем загранпаспорте есть виза в Китай, но нет визы в Гонконг. Поскольку рейс на самолет был до Гонконга и обратно, то в корейском аэропорту Инчеон приняли соломоново решение о том, что делать с этим русским: в Гонконге, не выходя из аэропорта, сразу же двигай на Ferry-Terminal, откуда отправляется катер в Китай. А обратно – точно так же: сразу с катера – на самолет, не переходя зону пограничного контроля. Причем перелет «туда» пограничники смогли проконтролировать: в Гонконгском аэропорту меня, не доходя до зоны пограничного контроля, встречала миловидная девушка с плакатиком «mr. Maslennikov», которая и проводила до того самого Ferry-Terminal, откуда отплывал катер в Китай. А вот обратно…

Mr. Lee был настроен как-то не по-чиновничьи: запланирована встреча в Гонконге с крупным производителем считывателей для смарт-карт – Advanced Card Systems (ACS). На руках есть обратный билет в Сеул, неужели в Гонконге на пограничном контроле не поймут, что я не бандит и не проститутка и не пропустят по российскому загранпаспорту без визы? Короче, идем через пограничный контроль в Гонконге, а там куда кривая вывезет.

На пограничном контроле в Гонконге кривая, естественно, вывезла меня к начальнице службы пограничного контроля. Это была сравнительно молодая женщина лет 30-ти, стройная и говорящая на безукоризненном английском языке.

- Почему Вы прибыли в Гонконг без визы?

    Мой корейский босс объяснил ей, что мы бизнесмены и хотим наладить сотрудничество с гонконгской компанией ACS. А я, достав из сумки свой Notebook, стал объяснять этой очаровательной женщине про CSP, электронную подпись и систему Internet Banking. И дальше произошло то, что не укладывается в голове у любого россиянина, хоть раз в жизни сталкивавшегося с российскими чиновниками. Начальница службы пограничного контроля Гонконгского аэропорта, проще говоря, обычная гонконгская чиновница, вдруг заявляет:

    - Да, я вижу, что Вы представляете интерес для моей страны. Прошу Вас, подождите немного, я попробую связаться с моим боссом и помочь Вам.

    Минут через 30 ко мне подходит ее подчиненный и говорит, что разрешение выдать мне визу получено. Нужно ее оплатить, это, если мне сейчас не изменяет память, 74 доллара, но оплатить нужно в местной валюте. Даю ему 100-долларовую купюру. Он извиняется за то, что мне пока не разрешен выход за пределы зоны пограничного контроля, и если я не возражаю, он сейчас сходит и разменяет ее. Сон какой-то. Еще через 15 минут этот чиновник приносит мне паспорт с гонконгской визой и 26 долларов сдачи. Занавес.

    Представим себе, на минутку, аналогичную картину, например, в Шереметьево-2: кореец прилетел в Россию без визы и на пограничном контроле начал что-то парить про CSP, электронную подпись и Internet Banking…

    Нет, не нужно в этой книге раскручивать дальше сценарий подобного фильма ужасов.


Назад                                Продолжение
В начало книги Криптография и Свобода - 2

7 comments or Leave a comment

MCSSHA

SHA-1 – нестойкий! Такая новость облетела криптографический мир в 2005 году. Но ведь SHA-1 – алгоритм хеширования, а в алгоритме хеширования нет никаких секретных ключей, здесь ничего не шифруется, что понимается под его стойкостью? Тут надо заметить, что одной из основных сфер использования алгоритма хеширования является ЭЦП, когда для применения математического аппарата электронной подписи сообщение произвольной длины нужно «сжать» в его хеш-функцию фиксированной длины, из которой затем с помощью секретного асимметричного ключа вычисляется подпись, а с помощью открытого - проверяется. Здесь слово «сжать» умышленно поставлено в кавычки, поскольку классическое сжатие предполагает возможность последующего восстановления исходного сообщения из сжатого текста, а для алгоритма хеширования, наоборот, возможность восстановления исходного сообщения из его хеш-функции должна быть практически исключена. Насколько сложно по хеш-функции восстановить хешируемое сообщение или получить какую-нибудь информацию о нем – это первый критерий оценки стойкости хеш-функции.

Сообщений произвольной длины бесконечно много, а значений хеш-функции фиксированной длины – конечное число, поэтому заведомо существуют различные сообщения, обладающие одинаковыми хеш-функциями. Насколько сложно их найти – второй критерий стойкости алгоритма хеширования. Пару сообщений с одинаковыми хеш-функциями в криптографии принято называть коллизией хеш-функции, причем коллизии бывают двух сортов: первого, когда требуется подобрать сообщение с той же хеш-функцией к некоторому фиксированному сообщению, и второго, когда просто требуется найти произвольную пару сообщений с одинаковыми хеш-функциями.

Давайте попробуем представит себе идеальную хеш-функцию, т.е. такую, для которой по каждому из приведенных выше критериев самые лучшие из оценок – это brute force, метод грубой силы. Каковы будут оценки brute force для хеш-функции?

    Начнем с первого критерия. Тут, вроде, все понятно: дергаем случайные сообщения, вычисляем для каждого из них хеш-функцию и проверяем ее на совпадение с имеющимся у нас значением хеш-функции. Если предположить, что длина хеш-функции равна 2n бит, то самым эффективным должен быть метод выбора случайных сообщений и каждое из них должно давать в качестве хеш-функции случайный и равновероятный вектор длины n, или, выражаясь официальным языком, preimage resistance of approximately n bits. Та же самая оценка будет справедлива и для нахождения коллизии первого сорта. А вот для нахождения коллизии второго сорта потребуется в среднем 2n/2 опробований – тут вступает в силу парадокс дней рождения. На упоминавшемся выше официальном языке это называется collision resistance of approximately n/2 bits. Такая получается картина идеальной хеш-функции.

Что же произошло с SHA1? В статье Брюса Шнайера Cryptanalysis of SHA-1, опубликованной 18 февраля 2005 года, утверждается, что три китайских криптографа смогли найти метод построения коллизии второго сорта для SHA1 за 269 операций. Если учесть, что длина хеш-функции SHA1 составляет 20 байт или 160 бит, то идеальная хеш-функция такой длины должна требовать в среднем 280 опробований для решения подобной задачи. Следовательно, SHA1, как следует из этой статьи, не является идеальной хеш-функцией. А 269 – это примерно 1021. Не такая уж астрономическая величина, а с криптографической точки зрения просто критическая. У Брюса Шнайера даются оценки времени и трудоемкости ее практического решения - 1757 дней (4,81 лет) усилиями 331252 пользователей.

SHA1 является в настоящее время, пожалуй, самым распространенным в мире алгоритмом хеширования. Даже такие чисто абстрактные подозрения в его ненадежности вынудили американский NIST (National Institute of Standard and Technology) принять срочные меры. 2 ноября 2007 года был объявлен открытый конкурс на разработку хеш-функций третьего поколения – SHA-3. Тут надо заметить, что хеш-функции второго поколения – SHA-2 – уже есть, они были разработаны американским АНБ, но по каким-то причинам NIST решил подстраховаться и провести открытый конкурс на SHA-3.

Требования к кандидатам SHA-3 были опубликованы на сайте NIST, если взять их криптографическую часть, то требование было одно: NISTу требовались идеальные хеш-функции, не допускающие среди известных в настоящее время методов анализа иных, кроме brute force.

Я впервые услышал о конкурсе SHA-3 в конце июня 2008 года. Один из выпускников 4 факультета ВКШ КГБ Игорь С. одним из первых «прорубил окно в Европу» и уехал жить в Норвегию. Там он больше был связан с теоретической криптографией, чем я в Корее, и, прочитав в Internet мою первую книжку «Криптография и Свобода», прислал мне письмо, из которого я и узнал об SHA-3. Я с радостью ухватился за эту мысль: после всех программистских баталий вспомнить про теорию и предложить NIST свой оригинальный вариант SHA-3, благо идей на этот счет было предостаточно: читатель первой книги наверняка помнит шифры на новой элементной базе и логарифмические подстановки. Эти оригинальные криптографические решения, которым было отдано много лет жизни, так и остались во многом невостребованными, и это меня все время угнетало. Так родились алгоритмы хеширования типа MCSSHA.

Сроки поджимали. Deadline для приема заявок на участие в конкурсе SHA-3 – 31 октября 2008 года. Следовательно, на все про все (разработка, анализ и оформление) у меня оставалось около 4-х месяцев. Особенно удручала невозможность какого бы то ни было квалифицированного обсуждения моих идей по MCSSHA, ибо те корейцы, с которыми я в то время работал, о теоретической криптографии имели весьма туманное представление. Так что весь криптоанализ MCSSHA проходил по примерно такой схеме: в выходные на целый день я уходил в горы и там, лазая по горным тропам, все время прикидывал те или иные возможности использования идей шифров на новой элементной базе для хеширования. И вот до чего в конце концов долазился.

Попробуем использовать для хеширования упоминавшийся в первой книге «Криптография и Свобода» неавтономный регулярный регистр сдвига над кольцом вычетов по модулю 256 (над байтами). Вот его рисуночек.

Идея использования подобного регистра для хеширования напрашивается сама собой: фиксируем какое-то начальное заполнение регистра и подаем сообщение на вход - x1,x2,…xL. Или что-то в этом роде… Дело в том, что в явном виде подавать сообщение на вход нельзя, сразу же возникнут коллизии – получающаяся система из N нелинейных уравнений элементарно решается и строятся пары с одинаковыми хеш-функциями. Как с этим бороться и в этой борьбе не слишком сильно усложнить такую красивую и элементарную реализацию? С этим вопросом, мучавшим меня около двух месяцев, я лазил по Bukhansan и Dobongsan и все никак не мог придумать удовлетворительного решения. А вот на горе с простым и понятным названием Namhansanseong осенило: нужны дырки!

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

    Если символами (yi,yi+1,…,yi+N-1) обозначить заполнение регистра сдвига в i-ый такт работы, то в (i+1)-ый такт оно будет (yi+1,yi+2,…,yi+N), где yi+N= π(yi–yi+1–yi+N-4+ yi+N-1) + xi. Заполнение регистра полностью обновляется за N тактов работы:

yi+N= π(yi–yi+1–yi+N-4+ yi+N-1) + xi

yi+N+ 1= π(yi+1–yi+2–yi+N-3+ yi+N) + xi+1

……………………………………………………………….

yi+2N- 1= π(yi+N-1–yi+N–yi+2N-5+ yi+2N-2) + xi+N-1

    При простой подаче сообщения на вход регистра из этой системы коллизия видна невооруженным взглядом: берем произвольное сообщение, вычисляем соответствующее ему значение регистра сдвига и элементарными арифметическими операциями решаем систему из N уравнений с N неизвестными – находим все xi, необходимые для того, чтобы получить нужное конечное заполнение регистра. Ну а если сообщение на вход подавать не сплошняком, а с дырками, например на один знак сообщения две дырки, что это даст? Да почти все, что доктор прописал!

yi+N= π(yi–yi+1–yi+N-4+ yi+N-1) + xj

yi+N+1= π(yi+1–yi+2–yi+N-3+ yi+N)

yi+N+2= π(yi+2–yi+3–yi+N-2+ yi+N+1)

yi+N+3= π(yi+3–yi+4–yi+N-1+ yi+N+2) + xj+1

…………………………………………

    И логарифмические подстановки, если кто помнит первую часть «Криптографии и Свободы», здесь очень даже к месту оказываются. Давайте попробуем порешать такую систему на дальних подступах к итоговому заполнению регистра.


Назад                                 Продолжение
В начало книги Криптография и Свобода - 2

Leave a comment

Final probability for full capture: (yt,yt+1,…,yt+N-1) = (zt,zt+1,…,zt+N-1);

N = 64, delay=2


 
Step before captureSR statesNext stepConditionsProbability
1(yt-1,yt,…,yt+62)

(zt-1,zt,…,zt+62)

yt+63=π(yt-1–yt–yt+59+yt+62)+m1(j)
z
t+63=π(zt-1–zt–zt+59+zt+62)+m2(j)
Absent1
2(yt-2,yt-1,yt,…,yt+61)

(zt-2,zt-1,zt,…,zt+61)

yt+62=π(yt-2–yt-1–yt+58+yt+61)
z
t+62=π(zt-2–zt-1–zt+58+zt+61)
yt-2–yt-1=zt-2–zt-12-8
3(yt-3,yt-2,yt-1,yt,…,yt+60)

(zt-3,zt-2,zt-1,zt,…,zt+60)

yt+61=π(yt-3–yt-2–yt+57+yt+60)
z
t+61=π(zt-3–zt-2–zt+57+zt+60)
yt-3–yt-2=zt-3–zt-2≈1(step 67)
4(yt-4,…,yt-1,yt,…,yt+59)

(zt-4,…,zt-1,zt,…,zt+59)

yt+60=π(yt-4–yt-3–yt+56+yt+59) +m1(j-1) zt+60=π(zt-4–zt-3–zt+56+zt+59) +m2(j-1)Absent1
5(yt-5,…,yt-1,yt,…,yt+58)

(zt-5,…,zt-1,zt,…,zt+58)

yt+59=π(yt-5–yt-4–yt+55+yt+58)
z
t+59=π(zt-5–zt-4–zt+55+zt+58)
yt-5–yt-4=zt-5–zt-42-8
6(yt-6,…,yt-1,yt,…,yt+57)

(zt-6,…,zt-1,zt,…,zt+57)

yt+58=π(yt-6–yt-5–yt+54+yt+57)
z
t+58=π(zt-6–zt-5–zt+54+zt+57)
yt-6–yt-5=zt-6–zt-5≈1(step 70)
7(yt-7,…,yt-1,yt,…,yt+56)

(zt-7,…,zt-1,zt,…,zt+56)

yt+57=π(yt-7–yt-6–yt+53+yt+56) +m1(j-2) zt+57=π(zt-7–zt-6–zt+53+zt+56) +m2(j-2)Absent1
8(yt-8,…,yt-1,yt,…,yt+55)

(zt-8,…,zt-1,zt,…,zt+55)

yt+56=π(yt-8–yt-7–yt+52+yt+55)
z
t+56=π(zt-8–zt-7–zt+52+zt+55)
yt-8–yt-7=zt-8–zt-72-8
9(yt-9,…,yt-1,yt,…,yt+54)

(zt-9,…,zt-1,zt,…,zt+54)

yt+55=π(yt-9–yt-8–yt+51+yt+54)
z
t+55=π(zt-9–zt-8–zt+51+zt+54)
yt-9–yt-8=zt-9–zt-8≈1(step 73)
10(yt-10,…,yt-1,yt,…,yt+53)

(zt-10,…,zt-1,zt,…,zt+53)

yt+54=π(yt-10–yt-9–yt+50+yt+53) +m1(j-3) zt+54=π(zt-10–zt-9–zt+50+zt+53) +m2(j-3)Absent1
11(yt-11,…,yt-1,yt,…,yt+52)

(zt-11,…,zt-1,zt,…,zt+52)

yt+53=π(yt-11–yt-10–yt+49+yt+52)
z
t+53=π(zt-11–zt-10–zt+49+zt+52)
yt-11–yt-10=zt-11–zt-102-8
12(yt-12,…,yt-1,yt,…,yt+51)

(zt-12,…,zt-1,zt,…,zt+51)

yt+52=π(yt-12–yt-11–yt+48+yt+51)
z
t+52=π(zt-12–zt-11–zt+48+zt+51)
yt-12–yt-11=zt-12–zt-11≈1(step 76)
……………………….………………………………………………………………
60(yt-60,…,yt-1,yt,…,yt+3)

(zt-60,…,zt-1,zt,…,zt+3)

yt+4=π(yt-60–yt-59–yt+yt+3)
zt+4=π(zt-60–zt-59–zt+zt+3)
yt-60–yt-59=zt-60–zt-59≈1 (step 124)
61(yt-61,…,yt-1,yt,…,yt+2)

(zt-61,…,zt-1,zt,…,zt+2)

yt+3=π(yt-61–yt-60–yt-1+yt+2) +m1(j-20) zt+3=π(zt-61–zt-60–zt-1+zt+2) +m2(j-20)Absent1
62(yt-62,…,yt-1,yt,yt+1)

(zt-62,…,zt-1,zt,zt+1)

yt+2=π(yt-62–yt-61–yt-2+yt+1)
zt+2=π(zt-62–zt-61–zt-2+zt+1)
yt-62–yt-61–yt-2=zt-62–zt-61–zt-22-8
63(yt-63,…,yt-1,yt)

(zt-63,…,zt-1,zt)

yt+1=π(yt-63–yt-62–yt-3+yt)

zt+1=π(zt-63–zt-62–zt-3+zt)

yt-63–yt-62–yt-3=zt-63–zt-62–zt-32-8
64(yt-64,…,yt-1)

(zt-64,…,zt-1)

yt=π(yt-64–yt-63–yt-4+yt-1) +m1(j-21)

zt=π(zt-64–zt-63–zt-4+zt-1) +m2(j-21)

Absent1
65(yt-65,…,yt-2)

(zt-65,…,zt-2)

Yt-1=π(yt-65–yt-64–yt-5+yt-2)

zt-1=π(zt-65–zt-64–zt-5+zt-2)

--
66(yt-66,…,yt-3)

(zt-66,…,zt-3)

Yt-2=π(yt-66–yt-65–yt-6+yt-3)

zt-2=π(zt-66–zt-65–zt-6+zt-3)

--
67(yt-67,…,yt-4)

(zt-67,…,zt-4)

Yt-3=π(yt-67–yt-66–yt-7+yt-4) +m1(j-22)

zt-3=π(zt-67–zt-66–zt-7+zt-4) +m2(j-22)

yt-3–yt-2=zt-3–zt-2 =>

yt-3π(yt-66–yt-65–yt-6+yt-3) = zt-3–π(zt-66–zt-65–zt-6+zt-3)

≈1
68(yt-68,…,yt-5)

(zt-68,…,zt-5)

Yt-4=π(yt-68–yt-67–yt-8+yt-5)

zt-4=π(zt-68–zt-67–zt-8+zt-5)

--
69(yt-69,…,yt-6)

(zt-69,…,zt-6)

Yt-5=π(yt-69–yt-68–yt-9+yt-6)

zt-5=π(zt-69–zt-68–zt-9+zt-6)

--
70(yt-70,…,yt-7)

(zt-70,…,zt-7)

Yt-6=π(yt-70–yt-69–yt-10+yt-7) +m1(j-23)

zt-6=π(zt-70–zt-69–zt-10+zt-7) +m2(j-23)

yt-6–yt-5=zt-6–zt-5 =>

yt-3π(yt-66–yt-65–yt-6+yt-3) = zt-3–π(zt-66–zt-65–zt-6+zt-3)

≈1
71(yt-71,…,yt-8)

(zt-71,…,zt-8)

Yt-7=π(yt-71–yt-70–yt-11+yt-8)

zt-7=π(zt-71–zt-70–zt-11+zt-8)

--

 

Любой нормальный читатель после 71-й строчки наверняка подумает: «Лучше бы остался на пеньке кушать кондитерские изделия!» Спокойно, спокойно, спокойно! Мы почти на верхушке. Давайте оглянемся назад и попробуем понять, для чего было карабкаться непонятно куда.



Назад                                Продолжение
В начало книги Криптография и Свобода - 2
Leave a comment

Итак, у нас есть некоторое фиксированное конечное заполнение регистра после t тактов работы: (yt,yt+1,…,yt+N-1), которое было получено после подачи на вход регистра длины N некоторого сообщения M1 = m1(0),m1(1),…,m1(j) при том, что прокрутка осуществлялась с «дырками»: после подачи на вход одного байта сообщения – два «холостых» такта, т.е. таких, когда на вход подается 0. Мы хотим его «захватить» (capture), т.е. подобрать другое сообщение M2 = m2(0),m2(1),…,m2(j), такое, что его конечное заполнение (zt,zt+1,…,zt+N-1) будет совпадать с (yt,yt+1,…,yt+N-1). Сообщение начинаем подбирать не с начала, а с конца. Например, первая строка таблицы – это заполнения регистров за один шаг до совпадения - (yt-1,yt,…,yt+62) и (zt-1,zt,…,zt+62). Отличие в них может быть только по одной координате: yt-1 ≠ zt-1. Поскольку на последнем шаге значение m2(j) добавляется линейно, то обеспечить совпадение последней координаты не составит никаких проблем: m2(j) = π(yt-1–yt–yt+59+yt+62)+m1(j) - π(zt-1–zt–zt+59+zt+62). Здесь вероятность правильного подбора равна 1. А вот за два шага до совпадения ситуация иная. На вход подается дырка, и совпадение получается только в том случае, если было обеспечено выполнение условия yt-2–yt-1=zt-2–zt-1. Дырка свое дело сделала, подобрать какие-то соотношения для символов M2, при которых это равенство выполнялось бы безусловно, не удается, остается только предполагать, что такое может случиться с вероятностью 2-8. Именно это и требуется для хеширования. Поехали дальше. За три шага до совпадения. Условие совпадения: yt-3–yt-2=zt-3–zt-2. А вот тут-то, отъехав назад аж до 67 шага, видим, что подбором значения m2(j-22) можно добиться этого совпадения с вероятностью, близкой к 1. Действительно, это же элемент знакомой нам по первой книге матрицы частот P(π), у которой на пересечении i-ой строки и j-го столбца стоит число решений системы

x – y = i;

        π(x) – π(y) = j;

А в логарифмической подстановке это число почти всегда равно 1 для ненулевых i и j.

Так может не надо использовать логарифмические подстановки в MCSSHA? Нет, мне кажется, что именно логарифмические подстановки наиболее пригодны для MCSSHA, ибо с их помощью можно получить гарантированные оценки трудоемкости подобного метода захвата. Решение системы с большой вероятностью однозначное, следовательно, требуемое значение m2(j-22) - тоже только одно. Но тогда на других местах с «чистыми дырками» (например на упоминавшемся выше шаге 2 до захвата) требуемые соотношения получаются с вероятностью 2-8, ибо возможностей для подбора предыдущих значений M2 не остается никаких других, кроме случайных. А если взять, к примеру, антипод логарифмической подстановки – линейную подстановку π(x) = ax + b, то, как нетрудно видеть, ей никакие дырки не помогут, система разваливается и элементарно решается.

Исходя из этих соображений, я получил оценки вероятности «захвата» для алгоритма MCSSHA при различных значениях длины регистра:

SR length (bytes)

Steps with probability 1

Steps with probability ≈1

Steps with probability 2-8

Total Probability

64

22

20

22

<2-176≈10-52

128

44

40

44

<2-352≈10-105

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

Выдавать заполнение регистра в явном виде в качестве результата хеширования нельзя. Ну, например, потому, что от последнего знака текста зависит только последний знак регистра, а это противоречит требованиям NIST: любое изменение в тексте должно приводить к появлению абсолютно новой, случайной и равновероятной хеш-функции. Ну, тут уже проблем меньше: подача текста на вход закончилась, можно подать полученное заполнение в качестве входа на такой же или подобный регистр, но уже без всяких дырок, и прокрутить несколько раз. Именно это я и сделал, в результате получился алгоритм хеширования MCSSHA-3, который я и послал в NIST в установленные регламентом сроки, т.е. до наступления deadline.

«Головокружение от успехов». Именно такими словами товарища Сталина я бы сейчас охарактеризовал свои действия в последние недели перед deadline. За короткие сроки придуман оригинальный алгоритм, решена давно не дававшая мне покоя задача пристроить куда-нибудь логарифмические подстановки, оценки стойкости – ломовые, скорость – весьма приличная. А блеск и лакировка – дело десятое, главное – оригинальная идея!

«NIST will NOT accept modifications to the submitted algorithms during Round 1». Этой фразе в требованиях NIST я поначалу не придавал значения: исследовательская задача, как же с первого раза – и безо всяких изменений и доработок? А потом интуитивно ясно, что главная задача моего участия в этом конкурсе – публично заявить об оригинальных российских криптографических идеях и разработках, которые по разным причинам оказались похоронены в России. Надеяться на то, что эти идеи окажутся приняты в качестве нового мирового стандарта хеширования, можно было только втайне от самого себя. Мне больше была интересна реакция на них «мировой криптографической общественности», внешние криптографические аргументы и контраргументы за и против них.

Итак, наступил долгожданный deadline и появились описания всех алгоритмов-кандидатов, допущенных NIST для участия в первом раунде конкурса. Одновременно появился полуофициальный сайт с очень симпатичным названием: The SHA-3 Zoo. Там тоже есть все кандидаты, а также мнения о каждом из них независимых криптографических экспертов. Оппонентами алгоритмов хеширования типа MCSSHA стали Jean-Philippe Aumasson (Nagravision SA, Switzerland) and Mar´ıa Naya-Plasencia (INRIA projet-team SECRET, France). С MCSSHA-3 они обошлись по-простому, не вдаваясь ни в какие дебри. В нем длина регистра при подаче на него хешируемого сообщения была в точности равна длине требуемой хеш-функции. В регистре есть «критические точки», т.е. такие, на которые при построении последнего заполнения поступали знаки сообщения. Остальные, на которые поступали «дырки», назовем некритическими. В MCSSHA-3 на один знак сообщения приходилось три «дырки», поэтому ¼ часть точек – критическая, а ¾ - нет. Генерим случайные сообщения, совпадения критических точек обеспечиваем решением уравнений, а некритические точки – методом, использующим парадокс дней рождения. Сокрашение трудоемкости с требуемых 2N/2 до 23N/8. Тут же на «клетку» с MCSSHA-3 в SHA-3 Zoo повесили табличку «2nd preimage», что означает: получено снижение оценок стойкости по сравнению с brute force при анализе по поиску коллизий второго типа.

Лазил, лазил по горам, а до такой очевидной вещи так и не долез! И ведь защититься от нее – элементарно. Ну кто, спрашивается, просил меня на первом этапе, пока сообщение подается на вход регистра, делать длину регистра равной длине хеш-функции? Явное головокружение от успехов, сделал бы на первом этапе длину регистра раза в два больше, благо на скорости это почти никак не сказывается: в программной реализации сдвигаются не сами байты в регистре, а точки съема, значение которых затем приводится по модулю длины регистра. Даже в некоторых случаях будет быстрее. Например, при N = 224 и 384 я зачем-то приводил значения точек съема по этим модулям, в то время как если бы взять, например, длину регистра 256 или 512, то и приведение по этим модулям реализуется быстрее. Ну и самое главное: в MCSSHA-3 я использовал три «дырки» после каждого знака, а увеличив длину регистра можно вполне обойтись и двумя и опять-таки увеличить скорость. Приведение же к нужной длине запросто можно осуществить на втором этапе, когда включившее в себя все знаки сообщения заполнение регистра подается на вход другого регистра, длина которого уже совпадает с длиной хеш-функции.

«Поезд ушел» - примерно так ответили мне в NIST, когда я попросил внести изменения в свою заявку. Но описание алгоритма MCSSHA-4, в котором проблемы MCSSHA-3 были устранены, я всеми правдами и неправдами протащил в материалы The First SHA-3 candidate conference, которая проходила в бельгийском городе Leuven с 25 по 28 февраля 2009 года.

С «дырками» ситуация прояснилась, те подходы, которые имели место для MCSSHA-3 оказались непригодны, когда длина регистра при подаче на его вход сообщения была увеличена в два раза. Вроде остается пустячок: заполнение фиксированной длины пропустить пару раз через регистр нужной длины. И тут мои зоркие оппоненты подметили то, что от меня ускользнуло.

Возьмем, к примеру, длину хеш-функции равной 32 байтам. Одним из требований к идеальной хеш-функции является то, чтобы трудоемкость построения сообщения с фиксированным значение хеш-функции составляла в данном случае примерно 232*8 операций. На этом требовании и подловили меня мои оппоненты в MCSSHA-4.

На первом этапе (pre-image computation) используется регистр длиной 64 байта, а на втором (final hash computation) – 32 байта. Займемся повнимательнее вторым этапом. В нем на регистр длины 32 два раза подается одно и то же входное слово длины 64, при этом начальное заполнение регистра R0 = (0, 1, 2,…,31). Попробуем построить сообщение, которое на первом этапе дает конечное заполнение y0,y1,…,y63 такое, при котором на втором этапе R0 переходит само в себя. Методика простая: для произвольных случайных y0,y1,…,y31 вычисляем состояние R1 регистра и для него однозначно находим y32’,y33’,…,y63’, переводящие его в R0. Дергаем случайные сообщения, получаем какие-то y0, y1,…,y31, вычисляем для них y32’,y33’,…,y63’ и пытаемся дописать сообщение так, чтобы последующие 32 байта совпали с y32’,y33’,…,y63’. Из этих 32 байт 22 – случайные, приходящиеся на «дырки», а 10 – на символы текста, которые однозначно подбираем. Если удалось подобрать, то значение хеш-функции такого сообщения будет совпадать с R0. Трудоемкость – 222*8, не выполнено условие «preimage resistance of approximately n bits».

Да, JP & Marıa (именно так они всегда подписывали свои письма, посылаемые мне по e-mail) нельзя было отказать в оригинальности их криптографического мышления. На Namhansanseong не полезли, обошлись без экстрима.

Я тогда сильно переживал за свои «головокружения от успехов». Неужели хорошая и перспективная идея с «дырками» в неавтономном регулярном регистре сдвига оказалась перечеркнутой от того, что мне не пришло в голову сразу же навести на нее необходимый криптографический блеск? Лихорадочно сделанные и помещенные на мой корейский сайт (сейчас он, к сожалению, закрыт, и ссылки на него из NIST не работают) очередные две модернизации: MCSSHA-5 и MCSSHA-6, к сожалению, не прикрыли полностью проблемы второго этапа алгоритмов типа MCSSHA. Во второй раунд SHA-3 моя заявка не прошла, и я потерял к этому конкурсу первоначальный интерес.

Сейчас, спустя почти три года после этих событий, мне по-прежнему кажется, что идею «регистра с дырками» можно довести до совершенства и создать на ее основе идеальную хеш-функцию, не допускающую никаких снижений трудоемкости по сравнению с brute force. И защититься от атаки JP & Marıa тоже можно сравнительно несложно: например, второй раз подавать на вход регистра перевернутый вектор y0,y1,…,y63. Для оценки и сравнения скорости работы алгоритмов типа MCSSHA я послал их в Иллинойс профессору Бернштейну. Там сейчас проводится тестирование скорости всех присланных алгоритмов хеширования на различных компьютерах. Результаты показывают, что по скорости MCSSHA является далеко не худшим из известных алгоритмов хеширования. Вот, например, один из последних результатов.


Назад                                Продолжение
В начало книги Криптография и Свобода - 2

Leave a comment

amd64; Bulldozer (600f12); 2011 AMD FX-8150; 4 x 3600MHz; bulldozer, supercop-20120310

Cycles/byte for long messages

quartile

median

quartile

hash

6.51

7.00

7.22

blake512

8.09

8.10

8.12

keccakc512treed2

8.41

8.44

8.69

blake64

8.66

8.67

8.72

skein512256

8.67

8.68

8.70

skein512512

9.08

9.12

9.23

skein256256

8.87

9.16

9.58

bblake256

11.79

11.80

11.83

blake256

12.79

12.81

12.89

skein10241024

13.00

13.02

13.02

groestl256

13.40

14.02

14.24

sarmal512

14.00

14.03

14.21

keccakc256

15.77

16.15

16.34

sha512

16.26

16.33

16.40

keccakc448

17.13

17.23

17.32

keccakc512

17.40

17.41

17.41

jh224

17.41

17.42

17.43

jh384

17.42

17.42

17.42

jh256

17.42

17.43

17.44

jh512

18.28

18.37

18.41

keccak

18.62

18.63

18.64

groestl512

20.24

20.25

20.25

round3jh256

20.23

20.26

20.26

round3jh512

22.32

22.43

22.44

sha256

22.58

22.61

22.64

keccakc768

32.48

32.55

32.67

keccakc1024

32.72

33.28

33.73

mgrostl256

36.52

36.71

36.86

md6d224

39.35

39.46

39.91

md6d256

47.47

47.67

47.94

simd256

50.53

50.62

50.78

md6d384

50.83

51.12

51.33

shavite3512

56.80

57.44

57.77

mcssha5

56.76

57.51

58.70

mcssha4

57.23

57.77

58.65

mcssha6

61.41

61.55

61.80

md6d512


В 2009 году последствия мирового экономического кризиса затронули и Южную Корею. В начале 2009 года сильно упал курс национальной корейской валюты – вона. Еще в начале 2008 года 1 доллар стоил примерно 950 вон, то в феврале этот курс опустился до 1600, правда, ненадолго, всего через месяц он поднялся до 1300 вон. Меня все чаще стало тянуть домой, в Россию. Масса идей: как сделать полноценный Internet-Banking, как применять международные криптографические стандарты, CSP, PKCS#11, смарт-карты. И, наконец, сколько можно использовать тяжеловесные и медленные национальные криптографические алгоритмы, в частности алгоритм хеширования ГОСТ Р 3411? Былые обиды за 6 с лишним лет пребывания в Сеуле немного подзабылись, но иллюзий насчет открытых криптографических конкурсов и коренного изменения криптографической политики в России у меня не было. Был за плечами накопленный за 6 лет опыт работы в зарубежной компании, масса собственных разработок и, наконец, опыт выхода в «мировое криптографическое сообщество» со своими MCSSHA.

Может быть, в каком-то, не знаю уж и каком, будущем эти идеи смогут стать востребованными в России?

Назад                                Продолжение
В начало книги Криптография и Свобода - 2

10 comments or Leave a comment

12 мая 1943 года

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

    «Спасибо деду за победу» - такой слоган сейчас часто можно увидеть на заднем стекле многих машин. Это, на мой взгляд, не официоз, не навязанная пропаганда, а истинное желание нынешнего поколения поблагодарить своих отцов и дедов, выразить восхищение их подвигом – победой в жуткой и кровопролитной войне с немцами. Георгиевская ленточка тоже стала одним из самых популярных символов. Так почему бы мне не прикрепить свою георгиевскую ленточку к этой книге? Тем более, что эту ленточку, на мой взгляд, нужно тянуть к современным российским проблемам: если наши отцы не боялись немецких ягдкоманд, то почему сейчас мы, их наследники, должны бояться вороватых российских чиновников? Почему из-за них мы должны бежать из своей страны?

    Такие вопросы я стал все чаще задавать себе после нескольких лет жизни в Корее. И в результате в этой книге появилась своя Георгиевская ленточка.

...........................

    12 мая 1943 года, деревня Княжино Смоленской области, недалеко от границы с Белоруссией.

    - Партизаны, сдавайтесь, вы окружены, сопротивление бесполезно.

    Настроение у немецкой ягдкоманды – егерей, посланных по приказу фюрера в русские леса охотиться на партизан, - было превосходным. Сегодня охота должна быть успешной. Партизаны окружены ротой егерей, помощи ждать им неоткуда, по немецкой инструкции им дали время на размышление о своей судьбе, и теперь, в ясный майский день – заключительная и наиболее интересная часть охоты. А будут ли они вообще сопротивляться в этой глуши, километров за 200 от линии фронта, где нет никакой надежды на поддержку? Ведь вся высотка, где они засели, заблокирована ягдкомандой, у которой есть минометы и даже пушка. Эти русские партизаны должны быть захвачены, как следует избиты и публично повешены в Смоленске в назидание другим таким же партизанам, которые еще водятся в этих глухих местах. А егеря, как и положено охотникам, вечером выпьют шнапса за фюрера, великую Германию и удачную охоту.

    Предвкушая острые ощущения, немецкие егеря полезли на высотку, где засели русские партизаны...

.............................

    Никогда еще жители деревни Княжино не видели столько немецких трупов. Их вывозили немецкими военными машинами с той высотки, что неподалеку от деревни, и где несколько часов шел бой с партизанами. Оставшиеся в живых немцы были в шоке, подавлены и уже не мечтали ни о какой охоте, а слово «русский партизан» вызывало у них страх и ужас. А над Княжино так и витало: «Ну и наложили же здесь немцев наши партизаны!» Когда стемнело, местные жители Иван Захаренков, Матрена Шукаева и Мария Сазоненкова пошли к высотке посмотреть на место боя и на героев-партизан: сколько их было и кто они?

    А партизан было всего 6 человек, пятеро – 20 летние совсем молодые еще ребята и 24-летний командир. Все тела изуродованы осатаневшими немцами. «Сынки, сынки...» - заплакали над ними женщины. Тогда, сразу же после боя, они посадили на месте их гибели 6 кустов шиповника – каждому по кусту, и захоронили героев.

    Позже княжинцы узнали, что это были гвардейцы – минеры. Их забросили в Смоленскую область в середине апреля. На фронте после Сталинграда было затишье, но все понимали, что враг еще силен и лето 1943 года будет жарким. Смоленская область – удобный плацдарм для удара по Москве, это понимали и советское и немецкое командование. Наше командование активизировало заброску диверсионных групп для подрыва коммуникаций и нанесения максимального урона врагу, а немцы усилили охрану и стали направлять в смоленские леса свои ягдкоманды.

    В детстве я конечно же знал, что мой дядя – Вячеслав Ефимов – Герой Советского Союза. Но детали не принято было обсуждать среди родственников и все подробности я выискивал в Internet уже в Корее. Мать Вячеслава Ефимова – тетя Эмма – была эстонкой по национальности. Даже мне, совсем еще мальчишке, в 60-х годах было очевидно, что в молодости тетя Эмма была очаровательно красивой и что мои бабушка с дедушкой очень чутко относятся к ней. Все поездки на родину моих родителей – в город Тверь, тогда называвшийся Калинин, как правило сопровождались визитом к тете Эмме, которая в войну потеряла сначала мужа, а затем и сына. Муж тети Эммы, Борис Кириллович Ефимов, погиб в самом начале войны при бомбежке немцами Калинина. И Слава, которому тогда еще не исполнилось 18 лет, в октябре 1941 года пошел добровольцем на фронт – мстить за отца.

    Его зачислили в школу подрывников. Зиму 1941 – 42 гг. обучали в этой школе, а весной 42 года – курс молодого бойца: в составе 10 – го отдельного батальона минеров Слава был заброшен в немецкий тыл – Смоленскую область, к партизанам. «Сомненья прочь, уходит в ночь отдельный 10 – й наш десантный батальон» - это про них – гвардейцев-минеров.

    В смоленских лесах оставалось много партизан из состава частей Красной Армии, окруженных немцами в 1941 году под Смоленском и Вязьмой. К ним и послали Славу Ефимова «на стажировку» в 1942 году. Стажировка эта, по-видимому, была успешной, Слава освоил партизанскую науку и к концу 42 года стал профессиональным подрывником.

    Командование берегло гвардейцев. На зиму 1942 – 43 гг. их выводили за линию фронта, давая своеобразные «зимние каникулы». Ну а весной 43 года – опять к немцам в тыл, туда, где был плацдарм для наступления на Москву...

    Группа Николая Колосова, в которую входил Слава Ефимов, была заброшена на парашютах в Смоленскую область в ночь на 22 апреля 1943 года. Она входила в отряд старшего лейтенанта Дубовицкого. 8 мая 1943 года группе был дан приказ: на перегоне Голынки - Лелеквинская линии Витебск - Смоленск подорвать эшелон противника, разведать движение на автостраде Витебск - Смоленск и взорвать мост. Группа смогла подорвать армейский склад боеприпасов на станции Лелеквинская.

    «Все время ухожу от преследования» - такова была последняя радиограмма от группы Николая Колосова. Ребята стремились к Княжино, поскольку там, на высоте 207,8, партизанами был оставлен для них тайник со взрывчаткой и боеприпасами. И здесь их окружила немецкая ягдкоманда.

    Вот описание тактики действия ягдкоманд, которое я отыскал в Интернете.

В борьбе с партизанами немцы действовали педантично и рационально. Окружение стоянки начиналось под вечер, в последних лучах заходящего солнца. Подтягивались штурмовые группы с разных сторон, численностью не больше роты каждая. На обозначенном рубеже егеря рассыпались в цепи, которые смыкались друг с другом, окружая партизанскую стоянку полукольцом. Все делалось скрытно и быстро, в сгущающихся сумерках, пока еще можно было контролировать процесс визуально. Сразу же закреплялись для подстраховки от внезапного прорыва. Наступление начиналось на рассвете, сразу, как только можно было различить цель. Наступали с востока, со стороны восходящего солнца. На западе отступающих партизан ожидала западня....

    И вот – ночь с 11 на 12 мая 1943 года. Шестеро молодых ребят на высоте 207,8 у деревни Княжино окружены ягдкомандой.

    Старший – Николай Колосов, 24 года. Он старше остальных на 4 года, старший лейтенант и признанный авторитет. Ребята ему верят, верят в его жизненный опыт, смекалку, умение найти решение в самой трудной ситуации. Выше никаких командиров здесь нет, только Васильевич, как часто между собой называет его вся группа.

    Младший сержант Вячеслав Ефимов. 19 лет, пулеметчик. В завтрашнем бою на его пулемет – особая надежда. Слава не подведет – так считает вся группа.

    Рядовой Иван Базылев, 20 лет. Родом из Смоленской области, из крестьянской семьи. Его родная деревня Балтутино ближе, чем у всех остальных к Княжино. У Ивана есть свой счет к немцам на смоленской земле.

    Рядовой Филипп Безруков, 21 год. Сибиряк, из Челябинска. Прошел трудный жизненный путь, без отца, работал кочегаром и помощником машиниста на паровозе. В Красной Армии – с июня 1941 года.

    Старший сержант Владимир Горячев, 20 лет. Тоже сибиряк, из Омска. На фронте – с июня 1941 года. Именно он с Николаем Колосовым смог отыскать тайник со взрывчаткой и боеприпасами на высоте 207,8.

    Рядовой Михаил Мягкий, 21 год. Украинец, из под Харькова, из крестьянской семьи. Его усилиями подступы к высоте 207,8 оказались надежно заминированы.

    В группе Николая Колосова был еще и седьмой человек – Дмитрий Яблочкин, который после диверсии на Лелеквинской был тяжело ранен и ребята, отступая, оставили его у местных жителей.

    Ночь, чудная майская ночь с 11 на 12 мая 1943 года! Молодые, полные сил и энергии 20-летние парни осознают, что попали в окружение. По немецкой логике они должны были в эту ночь запаниковать, осознать свою беспомощность перед силой немецкого оружия и сдаться. Но вопреки этой логике ребята готовились к бою, окапывались и всю ночь минировали свои позиции. Не сдаваться, а мины ставить – другие варианты не обсуждались.

Мины расставлены, но шестерка молодых ребят вполне отдает себе отчет в том, что завтрашний бой будет для них последним. О чем они думали в эту ночь, что позволило им в этой сверхкритической ситуации сохранить честь и достоинство, стать настоящими Героями, подвиг которых не вызывает ни у кого ни малейших сомнений на протяжении уже почти что 70 лет? Эти вопросы долго не давали мне покоя. Ведь у каждого человека в жизни есть какой-то кумир, идеал, на которого он хочет быть похожим. Моим кумиром стал мой дядя, Вячеслав Ефимов, и вся группа Николая Колосова, устроившая у деревни Княжино свой «маленький Сталинград». Мне кажется, что желание показать немцам «маленький Сталинград» витало в ту майскую ночь среди шестерки гвардейцев.

    Наверное, каждый вспоминал и свою короткую жизнь. У Славы Ефимова эти воспоминания тесно переплетались с его семьей, матерью Эммой Гансевной, дружной Ефимовской семьей отца, Бориса Кирилловича, и предвоенной жизнью в Калинине. Сразу после революции католичка Эмма была очень негативно принята родителями Бориса Кирилловича, но его брат Михаил и сестра Мария, несмотря на возражения родителей, полюбили красавицу- эстонку Эмму. В октябре 1923 года у Эммы и Бориса Ефимовых родился первенец – Слава, а в январе 1924 у Марии Кирилловны Масленниковой, бывшей до замужества Ефимовой, родились сразу двое сыновей: Юра и Женя. Они были почти одногодки, вместе росли, ходили друг к другу в гости, вместе выдумывали разные ребяческие забавы. И вот что придумал старший – заводила Славка.

    Неподалеку от Пролетарки, района бывшей фабрики купца Морозова в Твери, был аэродром Мигалово. Он и сейчас там есть. Но в начале 30-х годов каждый полет самолета – событие. Люди, заслышав шум мотора, выскакивали на улицы из своих трехэтажных бараков, чтобы поглядеть на аэроплан. Славка, расставив Женьку и Юрку по 2-му и 1-му этажам, учудил спускать с 3-го этажа по лестничным перилам коромысло. Громыхание коромысла чем-то напоминало шум мотора самолета, а сами «летчики», после того, как народ вываливался на улицу, выбегали из-за сарая и с дразнилкой

Аэроплан, аэроплан,

Посади меня в карман,

А в кармане пусто

Выросла капуста

разбегались в разные стороны.

    Любимым занятием всего Ефимовского семейства были походы за грибами. Дач в те времена еще не было, рано утром выезжали на поезде по Ленинградской железной дороге в Теребино, километров 50 от Калинина в сторону Ленинграда. Славка был заядлым грибником, особенно любил собирать белые грибы. 1940 год был особенно богат на белые грибы, но старожилы предрекали: это неспроста, к большой войне.

    Пророчество сбылось. Немцы рвались к Москве и осенью 41 года захватили Калинин. Слава к тому времени был уже в школе подрывников, отец погиб, а мать осталась одна с малолетним сыном Вовкой. Слава часто вспоминал о ней и о своих двоюродных братьях – друзьях детства: что с ними стало? Калинин в конце того же 41 года освободили, и вскоре старшие из семейства Ефимовых вернулись в свои дома. Слава даже сумел повидаться с матерью, когда зимой с 42 на 43 год его отпустили на «зимние каникулы».

    В ту майскую ночь, вспоминая о матери, Слава наверняка подумал: «Ефимовы – дружное семейство. Мама с ними не пропадет».

........

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

- Получите за отца, гады!

    Его пулемет полоснул по немецкой цепи и несколько егерей, вскинув руки, рухнули на склоне высоты.

        - Ну что, охотники, как вам нравится охота на партизан в России?

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

- Беречь патроны, сейчас опять полезут!

приказал Васильевич.

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

- Неужели второй раз опять тупо в лоб полезут?

    Полезли и не раз. Тупо в лоб, напролом. Нас тут много, партизаны сейчас испугаются. Вели ураганный огонь из автоматов по позициям, где отстреливалась шестерка ребят. Но ребята за ночь основательно подготовились, да и позиция – на бугре среди валунов – очень выгодная. Выкурить их из своих щелей егерям было не по зубам. Партизаны так и не испугались, а на склоне высоты количество охотников, подстреленных дичью, все увеличивалось и увеличивалось. Но и у ребят не обошлось без потерь: убит Филипп Безруков, а Слава Ефимов тяжело ранен.

    Немецкие офицеры раздали оставшимся в живых егерям весь шнапс, припасенный для празднования удачной охоты, а в штаб послали донесение: «Срочно пришлите подкрепление и самолет-корректировщик. Очень большая группа партизан».

    «Очень большая группа партизан» получила небольшую передышку.

    - Парни, слушай мою команду! Минируем позиции и отходим на 100 метров!

приказал Николай Колосов.

    Все оставшиеся в живых, в том числе и раненый Слава Ефимов, отошли к маленькому болотцу, что лежало в окружении цветущих черемух.

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

«Аэроплан, аэроплан...» - вспомнил истекающий кровью Славка свои детские проделки. А ведь молодец Васильевич, сейчас и немцы клюнут на наш обман.

Услышав взрыв, хватанувшие шнапса егеря воспрянули духом и с победными криками рванули в полный рост к бугру с разбросанными взрывом валунами. И тут им показалось, что против них уже не люди, а сама природа. Из ослепительно белых цветущих черемух всех дорвавшихся до бугра егерей смело пулеметным огнем. Так Слава дал свой прощальный залп.

Подкрепление пришлось немцам кстати: от роты, которая окружила «большую группу партизан», практически ничего не осталось. Оставшиеся в живых ребята отстреливались до последнего патрона, но силы были очень неравны. Последним пал Николай Колосов...

.......................

    Разные оценки количества уничтоженных в этом бою немцев видел я в Интернете. Ю.И.Ивашкин, глава муниципального образования Руднянского района Смоленской области, на территории которого находится Княжино, говорит о более чем 120 уничтоженных гитлеровцах, в других источниках утверждается о более чем 300 уничтоженных фашистах. В моих детских воспоминаниях, когда взрослые обсуждали этот бой, отложилось, что немецкие трупы вывозили на двух армейских грузовых машинах. И, конечно же, условия, в которых ребята приняли бой: без малейшей надежды на поддержку извне, но на своей земле и на глазах у жителей деревни Княжино. Недаром о подвиге группы Колосова пошла молва по всему Северо-Западному фронту. 8 мая 1945 года по личному приказу И.Х.Баграмяна гвардейцам-минерам был воздвигнут монумент, который и сейчас, спустя почти 70 лет, стоит в центре мемориального комплекса в Руднянском районе Смоленской области поблизости от деревни Микулино, куда были перезахоронены тела погибших ребят.


Фото с сайта Администрации Руднянского района Смоленской области

    В ту ночь все ребята не могли не думать о будущем. О будущей Победе, о той жизни, которая наступит после нее. И я уверен, что это будущее представлялось им светлым и прекрасным, без оккупантов и ягдкоманд, так же как сейчас нам представляется будущее России без жуликов и воров из одноименной партии. И за это будущее они стояли насмерть!

Назад                               

В начало книги Криптография и Свобода - 2

13 comments or Leave a comment