forked from vlsergey/infosec
-
Notifications
You must be signed in to change notification settings - Fork 0
/
Information Security.tex
1190 lines (881 loc) · 110 KB
/
Information Security.tex
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
\documentclass[10pt,a4paper]{book}
%\documentclass[12pt,report,russian]{ncc}
%\usepackage{a4wide}
\usepackage{cmap} % Поддержка поиска русских слов в PDF (pdflatex)
\usepackage[T1, T2A]{fontenc}
\usepackage[utf8]{inputenc}
\usepackage[english,russian]{babel}
%\usepackage{pscyr} % поддержка русских type1 шрифтов из пакета PSCyr
\usepackage{indentfirst} % Красная строка в первом абзаце
%\usepackage{misccorr}
%Может быть установлено 8pt, 9pt, 10pt, 11pt, 12pt, 14pt, 17pt, and 20pt
%\usepackage[12pt]{extsizes}
%\usepackage[mag=1000,a4paper,left=3cm,right=2cm,top=2cm,bottom=2cm,noheadfoot]{geometry}
\usepackage{amsfonts, amsmath, eucal, bm, amssymb, graphicx, color, mathabx}
\usepackage{algorithm, algorithmic} % 'algorithm' environments
\usepackage{multirow} % multirow cells in tables
\usepackage{arydshln} % dash lines in tables
\usepackage{subfig, float, wrapfig} % sub figures
\usepackage{makeidx, caption} % index, titles for figures
\usepackage{enumerate}
\usepackage{fancybox} % страница в рамке
%\usepackage{fancyhdr} % глава и секция вверху страницы
%\usepackage{layout}
\usepackage[left=1.84cm, right=1.5cm, paperwidth=14cm, top=1.8cm, bottom=2cm, height=19.8cm, paperheight=20cm]{geometry}
% поддержка гиперссылок; гиперссылки в pdf, должен быть последним загруженным пакетом
\ifx\pdfoutput\undefined
\usepackage[unicode,dvips]{hyperref}
\else
\usepackage[pdftex,colorlinks,unicode,bookmarks]{hyperref}
\fi
%\paperwidth=16.8cm \oddsidemargin=0cm \evensidemargin=0cm \hoffset=-0.33cm \textwidth=13.2cm
%\paperheight=24cm \voffset=-0.4cm \topmargin=0cm \headsep=0cm \headheight=0cm \textheight=19.8cm \footskip=0.9cm
% параметры PDF файла
\hypersetup{
pdftitle={Защита информации},
pdfauthor={Э. М. Габидулин, А. С. Кшевецкий, А. И. Колыбельников},
pdfsubject=учебное пособие,
pdfkeywords={защита информации, криптография, МФТИ}
}
% добавить точку после номера секции, раздела и т.д.
\makeatletter
\def\@seccntformat#1{\csname the#1\endcsname.\quad}
\def\numberline#1{\hb@xt@\@tempdima{#1\if&\else.\fi\hfil}}
\makeatother
% перенос слов с тире
%\lccode`\-=`\-
%\defaulthyphenchar=127
% изменить подписи к рисункам, таблицам и т.д.
\captionsetup{labelsep=period} % заменить : на .
\captionsetup{textformat=period} % Подписи завершать точкой
%\captionsetup[table]{position=above} % вертикальные отступы подписи таблицы для случая, когда подпись вверху
%\captionsetup[figure]{position=below} % вертикальные отступы подписи рисунка для случая, когда подпись внизу
%% стиль главы и секции вверху страницы
%\pagestyle{fancy}
%%\renewcommand{\chaptermark}[1]{\markboth{#1}{}}
%\renewcommand{\sectionmark}[1]{\markright{#1}{}}
%
%%\fancyhf{}
%%\fancyfoot[СE,CO]{\thepage}
%%\fancyhead[LE]{\textsc{\nouppercase{\leftmark}}}
%\fancyhead[RO]{\textsc{\nouppercase{\rightmark}}}
%
%\fancypagestyle{plain}{ %
%\fancyhf{} % remove everything
%\renewcommand{\headrulewidth}{0pt} % remove lines as well
%\renewcommand{\footrulewidth}{0pt}}
% запретить выходить за границы страницы
\sloppy
\newtheorem{theorem}{Теорема}[section]
\newtheorem{lemma}[theorem]{Лемма}
\newtheorem{definition}[theorem]{Определение}
\newtheorem{property}[theorem]{Утверждение}
\newtheorem{corollary}[theorem]{Следствие}
%\newtheorem{algorithm}[theorem]{Алгоритм}
\newtheorem{remark}[theorem]{Замечание}
\newcommand{\proof}{\noindent\textsc{Доказательство.\ }}
%\newtheorem{example}{\textsc{\textbf{Пример}}}
\newcommand{\example}{\textsc{\textbf{Пример.}} }
\newcommand{\exampleend}
\newcommand{\set}[1]{\mathbb{#1}}
\newcommand{\group}[1]{\mathbb{#1}}
\newcommand{\E}{\group{E}}
\newcommand{\F}{\group{F}}
\newcommand{\GF}[1]{\group{GF}(#1)}
\newcommand{\Gr}{\group{G}}
\newcommand{\R}{\group{R}}
\newcommand{\Z}{\group{Z}}
\newcommand{\MAC}{\textrm{MAC}}
\newcommand{\HMAC}{\textrm{HMAC}}
\newcommand{\PK}{\textrm{PK}}
\newcommand{\SK}{\textrm{SK}}
%Наконец, существует способ дублировать знаки операций, который мы приведем безо всяких пояснений. Включив
%\newcommand*{\hm}[1]{#1\nobreak\discretionary{}{\hbox{\mathsurround=0pt #1}}{}}
%в преамбулу, можно написать $a\hm+b\hm+c\hm+d$, при этом в формуле a\hm+b\hm+c\hm+d при переносе знак + будет продублирован.
% Дублирование символов бинарных операций ("+", "-", "="), набранных в строчных формулах, при переносе на другую строку:
%%begin{latexonly}
%\renewcommand\ne{\mathchar"3236\mathchar"303D\nobreak
% \discretionary{}{\usefont
% {OMS}{cmsy}{m}{n}\char"36\usefont
% {OT1}{cmr}{m}{n}\char"3D}{}}
%\begingroup
%\catcode`\+\active\gdef+{\mathchar8235\nobreak\discretionary{}%
% {\usefont{OT1}{cmr}{m}{n}\char43}{}}
%\catcode`\-\active\gdef-{\mathchar8704\nobreak\discretionary{}%
% {\usefont{OMS}{cmsy}{m}{n}\char0}{}}
%\catcode`\=\active\gdef={\mathchar12349\nobreak\discretionary{}%
% {\usefont{OT1}{cmr}{m}{n}\char61}{}}
%\endgroup
%\def\cdot{\mathchar8705\nobreak\discretionary{}%
% {\usefont{OMS}{cmsy}{m}{n}\char1}{}}
%\def\times{\mathchar8706\nobreak\discretionary{}%
% {\usefont{OMS}{cmsy}{m}{n}\char2}{}}
%\mathcode`\==32768
%\mathcode`\+=32768
%\mathcode`\-=32768
%%end{latexonly}
\makeindex
\begin{document}
%\layout
% рамка границ страницы http://www.ctan.org/tex-archive/macros/latex/contrib/fancybox/fancybox-doc.pdf
% сделать поиск по fancypage, thisfancypage
%\thisfancypage{}{\fbox}
%\thisfancypage{\fbox}{}
%\fancypage{}{\fbox} % закомментировать
%\fancypage{\fbox}{\fbox} % закомментировать
%\fancypage{\setlength{\fboxsep}{32pt}\fbox}{}
\title{Защита информации \\ Учебное пособие}
\author{Габидулин Эрнст Мухамедович \\ Кшевецкий Александр Сергеевич \\ Колыбельников Александр Иванович}
\date{
% \textbf{\textsc{Черновой вариант. Может содержать ошибки.}} \\
% \today
}
\maketitle
\setcounter{page}{3}
\newpage
%\thispagestyle{empty}
\setcounter{tocdepth}{2}
\tableofcontents
%\thispagestyle{empty}
\newpage
%\lhead[\leftmark]{}
%\rhead[]{\rightmark}
\input{foreword}
\chapter{Основные понятия и определения}
\input{Short_history_of_cryptography}
\input{model_of_the_transmission_system_with_crypto}
\section{Классификация криптосистем и шифров}
%\subsection{Секретные и открытые ключи}
%Различают два класса криптосистем -- с секретным и с открытым ключом.
%\sub
\input{secret-key_cryptosystem}
\input{public-key_cryptosystems}
\subsection{Шифры замены и перестановки}
По способу преобразования открытого текста в шифрованный текст шифры разделяются на шифры замены и шифры перестановки.
\input{substitution_ciphers}
\input{permutation_ciphers}
\input{composite_chiphers}
\subsection{Примеры современных криптопримитивов}
Приведем примеры названий некоторых современных криптографических примитивов, из которых строят системы защиты информации:
\begin{itemize}
\item DES, AES, ГОСТ 28147-89, Blowfish, RC5, RC6 -- блоковые симметричные шифры, скорость обработки десятки мегабайт в секунду,
\item A5/1, A5/2, A5/3, RC4 -- потоковые симметричные шифры с высокой скоростью, семейство A5 применяется в мобильной связи GSM, RC4 -- в компьютерных сетях для SSL соединения между браузером и вебсервером,
\item RSA\index{криптосистема!RSA} -- криптосистема с открытым ключом для шифрования,
\item RSA\index{криптосистема!RSA}, DSA, ГОСТ Р 34.10-2001 -- криптосистемы с открытым ключом для электронной подписи,
\item MD5, SHA-1, SHA-2, ГОСТ Р 34.11-94 -- криптографические хэш-функции.
\end{itemize}
\input{Cryptanalysis_methods_and_types_of_attacks}
\input{The_minimum_key_lengths}
\chapter{Классические шифры}
В главе приведены наиболее известные \emph{классические} шифры, которыми можно было пользоваться до появления роторных машин. К ним относятся шифр Цезаря, шифр Плейфера--Витстона, шифр Хилла, шифр Виженера. Они очень наглядно демонстрируют различные классы шифров.
\input{monoalphabetic_ciphers}
\input{bigrammnye_substitution_ciphers}
\input{hills_cipher}
% \subsection{Омофонные замены}
%
% Омофонными заменами называют криптопримитивы, в основе которых лежит замена групп символов открытого текста $M$ на группу символов $C$ с использованием ключа $K$. Такой метод шифрования вносит неоднозначность между $M$ и $C$, это позволяет защититься от методов частотного криптоанализа.
% \subsection{шифрокоды}
% Шифрокоды - это класс шифров сочетающих в себе свойства кодов и помехозащищенности со свойствами шифра и обеспечения конфиденциальности.
\input{vigeneres_chipher}
\input{polyalphabetic_cipher_cryptanalysis}
\input{perfect_secure_systems}
\chapter{Блоковые шифры}
\input{Feistel_cipher}
\input{GOST_28147-89}
\input{AES}
\input{Block_cipher_modes}
\section{Некоторые свойства блоковых шифров}
\input{feistel_network_reversibility}
\input{Feistel_cipher_without_s_blocks}
\input{Avalanche_effect}
\input{double_and_triple_ciphering}
\chapter{Потоковые шифры}
\input{per-char_encryption}
\section{Криптостойкие последовательности} %{Генерирование криптостойких псевдослучайных последовательностей бит}
Генераторы псевдослучайных чисел (ГПСЧ) ставят в соответствие набору символов $z_{1} z_{2} \dots z_{l}$ значение некоторой функции $f(z_{1} z_{2} \dots z_{l}) = f_{1}$. Следующим $l$ символам -- $f(z_{l+1} z_{l+2} \dots z_{2l}) = f_{2}$. Получают набор значений $f_{1} f_{2} \dots f_{N}$ и используют их в качестве случайной последовательности.
Для проверки степени близости к независимости и равномерному распределению символов существует набор тестов. Американский институт стандартизации NIST разработал 16 тестов на псевдослучайность. Подсчитывается число нулей и единиц, число одинаковых соседних пар, число одинаковых подпоследовательностей, автокорреляция, частота следующего символа в зависимости от предыдущих и т.д. Вычисляют вероятность символа 0 (или 1)
\[
P(f_i = 0 | f_{i-1} f_{i-2} \dots f_{i-k}) = \frac{1}{2} - \epsilon,
\]
Если вычисления осуществляются за полиномиальное время от длины подпоследовательности $k$, то есть с количеством битовых операций $O(k^{\textrm{const}})$, то тест называют \emph{полиномиальным}\index{задача!полиномиальная}.
Псевдослучайная последовательность удовлетворяет \textbf{тесту <<следующего бита>>}, если не существует полиномиального по $k$ теста, позволяющего по предыдущим $k$ битам определить следующий бит с вероятностью, отличной от $\frac{1}{2} - \epsilon$, принимая во внимание погрешность оценки $\epsilon$. Последовательность, удовлетворяющая тесту <<следующего бита>>, также удовлетворяет всем возможным полиномиальным тестам по $k$ на равномерность распределения, и наоборот.
Последовательность называется \emph{криптографически стойкой} или \emph{криптостойкой}, если она удовлетворяет тесту <<следующего бита>>.
\input{bbs_generator}
%\input{micalis_generator}
\input{maximal_period_sequences}
\section[Три способа улучшения последовательностей]{Три способа улучшения \protect\\ последовательностей}
\input{generators_with_multiple_shift_registers}
\input{generators_with_nonlinear_transformations}
\input{majority_generators}
\chapter{Криптографические хэш-функции}
\input{hash-function_properties}
\input{GOST_R_34.11-94.tex}
\input{MAC}
\section{Коллизии в хэш-функциях}
\input{birthdays_paradox}
\input{collisions_probability}
\input{hash-functions_combinations}
\chapter{Криптосистемы с открытым ключом}
\textbf{Криптосистемой с открытым ключом} (public-key cryptosystem, PKC) называется криптографическое преобразование, использующее два ключа -- открытый и секретный. Пара из \textbf{секретного}\index{ключ!секретный} (private key, secret key, SK) и \textbf{открытого}\index{ключ!открытый} (public key, PK) ключей создается пользователем, который свой секретный ключ держит в секрете, а открытый ключ делает общедоступным для всех пользователей. Криптографическое преобразование в одну сторону (шифрование) можно выполнить зная только открытый ключ, а в другую (расшифрование) -- только зная секретный ключ. Во многих криптосистемах из секретного ключа можно вычислить открытый ключ.
Если прямое преобразование выполняется открытым ключом, а обратное -- секретным, то криптосистема называется схемой \textbf{шифрования с открытым ключом}. Все пользователи, зная открытый ключ получателя, могут зашифровать для него сообщение, которое может расшифровать только владелец секретного ключа.
Если прямое преобразование выполняется секретным ключом, а обратное -- открытым, то криптосистема называется схемой \textbf{электронной подписи (ЭП)}, -- владелец секретного ключа может \emph{подписать} (зашифровать) сообщение, а все пользователи, зная открытый ключ, могут проверить, что подпись (шифротекст) была создана только владельцем секретного ключа и никем другим.
Некоторые криптосистемы с открытым ключом могут использоваться и как схема шифрования, и как схема ЭП с одним алгоритмом, например криптосистема RSA\index{криптосистема!RSA}. В общем случае это не так. Например, есть криптосистема с открытым ключом Эль-Гамаля\index{криптосистема!Эль-Гамаля} и другой алгоритм -- схема ЭП Эль-Гамаля\index{криптосистема!Эль-Гамаля}.
Для более простого опубликования открытых ключей производители операционных систем, браузеров и программных продуктов часто встраивают наборы открытых ключей различных организаций. Браузеры и операционные системы содержат десятки-сотни встроенных открытых ключей, принадлежащих центрам выдачи сертификатов X.509, производителям программных продуктов, банковским и интернет-сервисам. Фактически все пользователи \textbf{доверяют}\index{доверие} производителям ПО и тому, что открытые ключи, встроенные в продукт, действительно принадлежат их истинным владельцам.
Криптосистемы с открытым ключом построены на основе односторонних (однонаправленных) функций c потайным входом. Под \textbf{односторонней} функцией понимают \emph{вычислительную} невозможность вычисления ее обращения: вычисление значения функции $y = f(x)$ при заданном аргументе $x$ является легкой задачей, вычисление аргумента $x$ при заданном значении функции $y$ -- трудной задачей.
Рассмотрим, например, умножение больших целых чисел $p,q$, каждое из которых состоит из 500 бит в двоичной записи. Как известно, вычисление их произведения является легкой задачей, сложность которой по порядку не превышает $500^2$ битовых операций. Однако, обратная задача -- разложить 1000-битовое число $n=pq$, представляющее собой произведение двух простых 500-битовых чисел, на простые множители является трудной задачей, связанной с поиском делителей, сложность которой оценивается экспонентой от корня квадратного длины числа ($ \exp(1000^1/2)$).
Односторонняя функция $y = f(x,K)$ с \textbf{потайным входом}\index{функция!с потайным входом} $K$ определяется как функция, которая легко вычисляется при заданном $x$, и аргумент $x$ которой можно легко вычислить из $y$, если известен <<секретный>> параметр $K$, и вычислить невозможно, если параметр $K$ неизвестен.
Криптосистемы с открытым ключом построены на дискретной математике. Необходимые математические основы модульной арифметики, групп, полей и простых чисел приведены в Приложении \ref{chap:discrete-math}.
\input{rsa}
\input{el-gamal}
\input{GOST_R_34.10-2001.tex}
\input{pki_key_length}
\chapter{Распространение ключей}
Задачей распространения ключей между двумя пользователями является создание секретных псевдослучайных сеансовых ключей шифрования и аутентификации сообщений. Пользователи предварительно создают и обмениваются ключами аутентификации один раз. В дальнейшем для создания защищенной связи пользователи производят взаимную аутентификацию и вырабатывают сеансовые ключи\index{ключ!сеансовый}.
\input{shamirs_three-step_protocol}
\section{Протоколы с симметричными шифрами}
\subsection{Аутентификация и атаки воспроизведения}
Рассмотрим такую ситуацию: обе стороны $A$ и $B$ имеют общий долговременный ключ $K_{AB}$ и симметричную систему шифрования. Нужно выработать сеансовый секретный ключ $K$. Сторона $A$ создает ключ $K$ и желает его передать стороне $B$.
\begin{enumerate}
\item Для этого сторона $A$ с помощью общего ключа $K_{AB}$ создает и передает $B$ шифрованное сообщение:
\[ A \rightarrow B: ~ E_{K_{AB}}(K, B, A). \]
В этом сообщении имеются так называемые поля -- $(B,A)$ -- информация для дополнительного подтверждения.
\item Сторона $B$, используя общий ключ $K_{AB}$, расшифровывает полученное сообщение:
\[ D_{K_{AB}}( E_{K_{AB}}( K, B, A)) = (K, B, A). \]
В результате сторона $B$ получает сеансовый ключ $K$ и дополнительные данные $(B,A)$.
\end{enumerate}
Недостаток этого протокола состоит в том, что криптоаналитик может перехватывать сообщения и через некоторое время переслать их стороне $A$.
Рассмотрим другие варианты решения задачи о передаче сеансового ключа.
Задача остается прежней: обе стороны $A$ и $B$ имеют общий долговременный секретный ключ $K_{AB}$, сторона $A$ должна выработать сеансовый секретный ключ $K$ и доставить стороне $B$.
Протокол включает \textbf{метки времени} -- информацию о моменте $t_A$ отправки сообщения и моменте получения сообщения $t_B$.
\begin{enumerate}
\item Сторона $A$ вырабатывает $K$ и с помощью долговременного ключа $K_{AB}$ создает шифрованное сообщение с меткой времени $t_A$ и передает его стороне $B$:
\[ A \rightarrow B: ~ E_{K_{AB}}(K, t_A). \]
\item Сторона $B$ получает сообщение и расшифровывает его с помощью общего ключа:
\[ D_{K_{AB}}( E_{K_{AB}}( K, t_A) = (K, t_A). \]
В результате $B$ получает $(K, t_A)$, то есть, секретный ключ и метку времени. $B$ измеряет время прихода $t_B$ и интервал запаздывания. Если $|t_B - t_A| \le \delta$, то $B$ аутентифицирует $A$.
\end{enumerate}
Метка времени является одноразовой меткой и защищает от атак воспроизведения ранее записанных сообщений.
Рассмотрим другой способ передачи ключа с дополнительной информацией в виде \textbf{одноразовых случайных меток} (nonce -- number used once) вместо меток времени. Протокол передачи состоит в следующем.
\begin{enumerate}
\item Сторона $A$ вырабатывает случайное число $r_A$, шифрует сообщение, в котором $(r_A, A)$ -- реквизиты $A$, и передает его стороне $B$:
\[ A \rightarrow B: ~ E_{K_{AB}}(r_A, A). \]
\item Сторона $B$ вырабатывает сеансовый ключ $K$, создает шифрованное сообщение и посылает его $A$:
\[ A \leftarrow B: ~ E_{K_{AB}}(K, r_A, A). \]
\item Сторона $A$ расшифровывает полученное сообщение
\[ D_{K_{AB}}( E_{K_{AB}}( K, r_A, A)) = (K, r_A, A). \]
В результате $A$ получает сеансовый ключ и подтверждение своих реквизитов, что является дополнительной аутентификацией.
\end{enumerate}
Предположим, что сторона $B$ тоже желает убедиться, что имеет дело со стороной $A$. Тогда этот протокол следует дополнить передачей реквизитов $B$. По-прежнему считаем, что у $A$ и $B$ -- общая система шифрования с долговременным секретным ключом $K_{AB}$.
\begin{enumerate}
\item Сторона $A$ вырабатывает случайное число $r_A$, шифрует и передает стороне $B$ сообщение, в котором $(r_A, A)$ -- реквизиты $A$:
\[ A \rightarrow B: ~ E_{K_{AB}}(r_A, A). \]
\item Сторона $B$ вырабатывает случайное число $r_B$ и отправляет стороне $A$ зашифрованное сообщение:
\[ A \leftarrow B: ~ E_{K_{AB}}(K_B, r_B, r_A, A), \]
где $K_B$ -- ключ $B$.
\item Сторона $A$ осуществляет расшифрование
\[ D_{K_{AB}}(K_B, r_B, r_A, A) = (K_B, r_B, r_A, A) \]
и получает ключ $K_B$ и реквизиты $r_B, r_A, A$. Для аутентификации себя сторона $A$ создает свой ключ $K_A$ и отправляет стороне $B$ шифрованное сообщение
\[ A \rightarrow B: ~ E_{K_{AB}}(K_A, r_B, r_A, B). \]
\item Сторона $B$ осуществляет расшифрование
\[ D_{K_{AB}}(K_A, r_B, r_A, B) = (K_A, r_B, r_A, B), \]
которое определяет ключ $K_A$ и аутентифицирует $A$.
\end{enumerate}
Таким образом, обе стороны имеют в своем распоряжении ключи $K_A, K_B$ в качестве сеансовых секретных ключей.
\subsection{Протокол с ключевым кодом аутентификации}
При использовании хэш-функции $K = h(K_{A} \| K_{B})$ происходит усиление секретности. Здесь $(K_{A} \| K_{B})$ -- конкатенация $K_{A} $ и $K_{B}$.
% Достоинства: предположим, $K_{A} ,K_{B} $ - не обладают «хорошими» свойствами случайности (биты распределены неравномерно или зависимы друг от друга), т.е., $P_{K_{A} ,K_{B} } (0)=\frac{1}{2} -\varepsilon $, где $\varepsilon $ - мало, но не 0. Тогда вероятность того, что этот бит в \textit{K }будет равным нулю, $P_{K} (0)=\frac{1}{2} -\varepsilon ',\varepsilon '<\varepsilon $- усиление секретности.
Вычисление хэш-значения, как правило, выполняется быстрее, чем расшифрование. Поэтому были разработаны протоколы, в которых вместо функции шифрования используется ключевой код аутентификации на основе хэш-функции $\MAC_K$. Рассмотрим протокол такого рода.
\begin{enumerate}
\item Сторона $A$ вырабатывает сеансовый ключ $K$, использует одноразовую метку $t_{A}$, создает и пересылает стороне $B$ сообщение:
\[ A \rightarrow B: ~ t_A, ~ B, ~ K \oplus \MAC_{K_{AB}}( t_A, B), ~ \MAC_{K_{AB}}(K, t_A, B). \]
\item Сторона $B$ вычисляет
\[ \MAC_{K_{AB}}(t_A, B) \oplus K \oplus \MAC_{K_{AB}}(t_A, B) = K \]
и получает сеансовый ключ $K$.
\end{enumerate}
Заметим, что криптоаналитик может добавить в поле случайную последовательность, тогда вместо $K$ получаем <<$K$ плюс помеха>>. Вмешательство криптоаналитика будет выявлено благодаря наличию четвертого поля в сообщении. Используя полученное значение $K$, вычисляют $\MAC_{K_{AB}}(K, t_A, B)$ и сравнивают с четвертым полем. Если совпадает, то вмешательства криптоаналитика не было.
\input{needham-schroeder_protocol}
\section{Протоколы на криптосистемах с открытым ключом}
\subsection{Простой протокол}
Рассмотрим протокол распространения ключей с помощью асимметричных шифров. Введем обозначения: $K_B$ -- открытый ключ стороны $B$, а $K_A$ -- открытый ключ стороны $A$. Протокол включает три сеанса обмена информацией.
\begin{enumerate}
\item В первом сеансе сторона $A$ посылает стороне $B$ сообщение
\[ A \rightarrow B: ~ E_{K_B}(K_1, A), \]
где $K_1$ -- ключ, выработанный стороной $A$.
\item Сторона $B$ получает $(K_1, A)$ и передает стороне $A$ наряду с другой информацией свой ключ $K_2$ в сообщении, зашифрованном с помощью открытого ключа $K_A$:
\[ A \leftarrow B: ~ E_{K_A}(K_2, K_1, B). \]
\item Сторона $A$ получает и расшифровывает сообщение $(K_2, K_1, B)$. Во время третьего сеанса сторона $A$, чтобы подтвердить, что она знает ключ $K_2$, посылает стороне $B$ сообщение
\[ A \rightarrow B: ~ E_{K_B}(K_2). \]
\end{enumerate}
Общий ключ формируется из двух ключей $K_1, K_2$.
\subsection{Протоколы с цифровыми подписями}
Существуют протоколы обмена, в которых перед началом обмена ключами генерируются подписи сторон $A$ и $B$, соответственно $S_A(m)$ и $S_B(m)$. В этих протоколах можно использовать различные одноразовые метки. Рассмотрим пример.
\begin{enumerate}
\item Сторона $A$ выбирает ключ $K$ и вырабатывает сообщение
\[ \left( K, ~ t_A, ~ S_A(K, t_A, B) \right), \]
где $t_A$ -- метка времени. Зашифрованное сообщение передает стороне $B$:
\[ A \rightarrow B: ~ E_{K_B}(K, ~ t_A, ~ S_A(K, t_A, B)). \]
\item Сторона $B$ получает $\left( K, ~ t_A, ~ S_A(K, t_A, B) \right)$ и вырабатывает свою метку времени $t_B$. Проверка считается успешной, если $|t_B - t_A | < \delta $. Сторона $B$ знает свои реквизиты и может осуществлять проверку подписи.
\end{enumerate}
Имеется второй вариант протокола, в котором шифрование и подпись выполняются раздельно.
\begin{enumerate}
\item Сторона $A$ вырабатывает ключ $K$, использует одноразовую метку (или метку времени) $t_{A}$ и передает стороне $B$ два различных зашифрованных сообщения
\[ \begin{array}{ll}
A \rightarrow B: & ~ E_{K_B}(K, t_A), \\
A \rightarrow B: & ~ S_A(K, t_A, B). \\
\end{array} \]
\item Сторона $B$ получает это сообщение, расшифровывает $K, t_A$ и, добавив свои реквизиты $B$, может проверить подпись $S_A(K, t_A, B)$.
\end{enumerate}
В третьем варианте протокола сначала производится шифрование, потом подпись.
\begin{enumerate}
\item Сторона $A$ вырабатывает ключ $K$, использует одноразовую случайную метку или метку времени $t_A$ и передает стороне $B$ сообщение
\[ A \rightarrow B: ~ t_A, ~ E_{K_B}(K, A), ~ S_A(t_A, ~ K, ~ E_{K_B}(K, A)). \]
\item Сторона $B$ получает это сообщение, расшифровывает $\left( t_A, ~ K, ~ A, ~ E_{K_B}(K, A) \right)$ и проверяет подпись $S_A(t_A, ~ K, ~ E_{K_B}(K, A))$.
\end{enumerate}
\input{diffie-hellman}
%\section{Протоколы с аутентификацией}
\subsection{Односторонняя аутентификация}
\input{el-gamal_protocol}
\input{mti}
\input{sts}
\input{girrault}
В этом разделе были рассмотрены протоколы, в которых ключи вырабатываются в процессе обмена информацией.
%Существует и другой подход, который будет рассмотрен в следующих разделах.
\chapter{Разделение секрета}
\section{Пороговые схемы}
Идея \textbf{пороговой} $(n, N)$-схемы\index{разделение секрета!пороговое} разделения общего секрета среди $N$ пользователей состоит в следующем.
%описывается так:
Доверенная сторона хочет распределить некий секрет $K_0$ между $N$ пользователями таким образом, что:
%. Поставлены следующие условия:
\begin{itemize}
\item любые $m, ~ n \le m \le N$, легальных пользователей могут получить секрет (или доступ к секрету), если предъявят свои секретные ключи;
\item любые $m, ~ m < n$, легальных пользователей не могут получить секрет и не могут определить (вычислить) этот секрет, пытаясь решить трудную в вычислительном смысле задачу.
\end{itemize}
Далее рассмотрены два случая: $(n, N)$-схема Шамира и простая $(N,N)$-схема.
\input{shamirs_secret_sharing}
\input{xor_secret_sharing}
\section[Распределение секрета по коалициям]{Распределение секрета по \protect\\ коалициям}
\subsection[Схема для нескольких коалиций]{Распределение секрета по нескольким \protect\\ коалициям}
Предположим, что имеется $N$ легальных пользователей
\[ \{ U_1, U_2, \dots, U_N \}, \]
которым нужно сообщить (открыть, получить доступ к) общий секрет $K$.
Секрет может быть доступен только определенным коалициям\index{распределение секрета!по коалициям}, например
\[ \begin{array}{l}
C_1 = \{ U_1, U_2 \}, \\
C_2 = \{ U_1, U_3, U_4 \}, \\
C_3 = \{ U_2, U_3 \}, \\
\dots
\end{array} \]
При этом ни одна из коалиций $C_i, ~ i = 1, 2, \dots$ не должна быть подмножеством другой коалиции.
\subsubsection{Пример 1}
Имеется 4 участника
\[ \{ U_1, U_2, U_3, U_4 \}, \]
которые образуют 3 коалиции
\[ \begin{array}{l}
C_1 = \{ U_1, U_2 \}, \\
C_2 = \{ U_1, U_3 \}, \\
C_3 = \{ U_2, U_3, U_4 \}. \\
\end{array} \]
Распределение частичных секретов между ними представлено в виде табл. \ref{tab:secret-share-coalition-1}, в которой введены следующие обозначения: $a_1, b_1, c_2, c_3$ -- случайные числа из кольца $\Z_M$. В строках таблицы содержатся частичные секреты каждого из пользователей, в столбцах таблицы показаны частичные секреты, соответствующие каждой из коалиций.
\begin{table}[h!]
\centering
\caption{Распределение секрета по определенным коалициям\label{tab:secret-share-coalition-1}}
\begin{tabular}{|c||c|c|c|}
\hline
& $C_1 = \{ U_1, U_2 \}$ & $C_2 = \{U_1, U_3 \}$ & $C_3 = \{ U_2, U_3, U_4 \}$ \\
\hline \hline
$U_1$ & $a_1$ & $b_1$ & -- \\
$U_2$ & $K - a_1$ & -- & $c_2$ \\
$U_3$ & -- & $K - b_1$ & $c_3$ \\
$U_4$ & -- & -- & $K - c_2 - c_3$ \\
\hline
\end{tabular}
\end{table}
Как видно из приведенных данных, суммирование по модулю $M$ чисел, приведенных в каждом из столбцов таблицы, открывает секрет $K$.
\subsubsection{Пример 2}
%\section{Схема разделения секрета на монотонных булевых функциях}
%\example
В системе распределения секрета доверенный
%с использованием монотонных булевых функций
центр использует кольцо $\Z_m$ целых чисел по модулю $m$. Требуется разделить секрет $K$ между $5$ пользователями
\[ \{ U_1, U_2, U_3, U_4, U_5 \} \]
так, чтобы восстановить секрет могли только коалиции
\[ \begin{array}{lll}
C_1 = \{ U_1, U_2 \}, & & C_2 = \{ U_1, U_3 \}, \\
C_3 = \{ U_2, U_3, U_4 \}, & & C_4 = \{ U_2, U_3, U_5 \}, \\
C_5 = \{ U_3, U_4, U_5 \}, & & C_6 = \{ U_1, U_2, U_3 \}. \\
\end{array} \]
Заданное множество коалиций с доступом не является минимальным, так как одни коалиции входят в другие:
\[ C_1 \subset C_6, ~ C_2 \subset C_6. \]
Исключая $C_6$, получим минимальное множество коалиций с доступом к секрету -- ни одна из оставшихся коалиций не входит в другую $C_i \nsubseteq C_j$ для $i \neq j$. Пользователям выдаются тени по минимальному множеству коалиций с доступом. В строках таблицы \ref{tab:secret-share-coalition-2} содержатся частичные секреты каждого из пользователей, в столбцах таблицы показаны частичные секреты, соответствующие каждой из коалиций.
\begin{table}[h!]
\centering
\caption{Распределение секрета по определенным коалициям\label{tab:secret-share-coalition-2}}
\begin{tabular}{|c||c|c|c|c|c|}
\hline
& $C_1$ & $C_2$ & $C_3$ & $C_4$ & $C_5$ \\
\hline \hline
$U_1$ & $a_1$ & $b_1$ & -- & -- & -- \\
$U_2$ & $K - a_1$ & -- & $c_2$ & $d_2$ & --\\
$U_3$ & -- & $K - b_1$ & $c_3$ & $d_3$ & $e_3$ \\
$U_4$ & -- & -- & $K - c_2 - c_3$ & -- & $e_4$ \\
$U_5$ & -- & -- & -- & $K - d_2 - d_3$ & $K - e_3 - e_4$ \\
\hline
\end{tabular}
\end{table}
Тени выбираются случайно из кольца $\mathbb{\Z}_m$. В результате у пользователей будут тени:
%\exampleend
\input{brickells_scheme}
\input{bloms_scheme}
\chapter{Примеры систем защиты}
\input{kerberos}
\section{Инфраструктура открытых ключей}
\input{CAs}
\input{x509}
\input{pgp}
\input{tls}
\input{ipsec}
\section[Защита персональных данных в мобильной связи]{Защита персональных данных в \protect\\ мобильной связи}
\input{gsm2}
\input{gsm3}
%\section{Беспроводная сеть Wi-Fi}
%\subsection{WPA-PSK2, 802.11n, Radix?}
%\subsection{Wimax 802.16(?)}
\chapter{Аутентификация пользователя}
\section{Многофакторная аутентификация}
Для защищенных приложений применяется \textbf{многофакторная} аутентификация одновременно по факторам различной природы:
\begin{enumerate}
\item Свойство, которым обладает субъект. Например, биометрия, природные уникальные отличия: лицо, отпечатки пальцев, радужная оболочка глаз, капиллярные узоры, последовательность ДНК.
\item Знание -- информация, которую знает субъект. Например, пароль, PIN-код.
\item Владение -- вещь, которой обладает субъект. Например, электронная или магнитная карта, флеш-память.
% \item Факторы присвоения. Например, номер машины, RFID-метка.
\end{enumerate}
В обычных массовых приложениях, из-за удобства использования, применяется аутентификация только по \textbf{паролю}\index{пароль}, который является общим секретом пользователя и информационной системы. Биометрическая аутентификация по отпечаткам пальцев применяется существенно реже. Как правило, аутентификация по отпечаткам пальцев является дополнительным, а не вторым обязательным фактором (тоже из-за удобства ее использования).
%Так же явно или неявно используется аутентификация по факторам:
%\begin{enumerate}
% \item Социальная сеть. Доверие к индивидууму в личном общении или интернет на основании общих связей.
% \item Географическое положение. Например, для проверки оплаты товаров по кредитной карте.
% \item Время. Доступ к сервисам или местам только в определенное время.
% \item И др.
%\end{enumerate}
\section[Энтропия и криптостойкость паролей]{Энтропия и криптостойкость \protect\\ паролей}
Стандартный набор символов паролей, которые можно набрать на клавиатуре, используя английские буквы и небуквенные символы, состоит из $D=94$ символов. При длине пароля $L$ символов и предположении равновероятного использования символов энтропия паролей равна
\[ H = L \log_2 D. \]
Клод Шеннон, исследуя энтропию символов английского текста, исследовал вероятность успешного предсказания людьми следующего символа по первым нескольким символам слов или текста. В результате Шеннон получил оценку энтропии первого символа $s_1$ текста порядка $H(s_1) \approx 4.6$--$4.7$ бит/символ и оценки энтропий последующих символов, постепенно уменьшающиеся до $H(s_9) \approx 1.5$ бит/символ для 9-го символа. Энтропия для длинных текстов литературных произведений получила оценку $H(s_\infty) \approx 0.4$ бит/символ.
Статистические исследования баз паролей показывают, что наиболее часто используются буквы -- $a,e,o,r$, и цифра -- $1$.
NIST использует следующие рекомендации для оценки энтропии паролей\index{энтропия!пароля}, создаваемых людьми.
\begin{enumerate}
\item Энтропия первого символа $H(s_1) = 4$ бит/символ.
\item Энтропия со 2-го по 8-й символы $H(s_{2 \leq i \leq 8}) = 2$ бит/символ.
\item Энтропия с 9-го по 20-й символы $H(s_{9 \leq i \leq 20}) = 1.5$ бит/символ.
\item Энтропия с 21-го символа $H(s_{i \geq 21}) = 1$ бит/символ.
\item Проверка композиции на использование символов разных регистров и небуквенных символов добавляет до 6 бит энтропии пароля.
\item Словарная проверка на слова и часто используемые пароли добавляет до 6 бит энтропии для коротких паролей. Для 20-символьных и более длинных паролей прибавка к энтропии 0 бит.
\end{enumerate}
Для оценки энтропии пароля нужно сложить энтропии символов $H(s_i)$ и сделать дополнительные надбавки, если пароль удовлетворяет тестам на композицию и отсутствие в словаре.
\begin{table}[h!]
\centering
\caption{Оценка NIST предполагаемой энтропии паролей\label{tab:password-entropy}}
\resizebox{\textwidth}{!}{ \begin{tabular}{|c||c|c|c||c|}
\hline
\multirow{2}{*}{\parbox{1.5cm}{Длина пароля, символы}} & \multicolumn{3}{|c||}{\parbox{6cm}{Энтропия паролей пользователей по критериям NIST}} & \multirow{2}{*}{\parbox{2.5cm}{Энтропия случайных равновероятных паролей}} \\
\cline{2-4}
& \parbox{1.5cm}{Без проверок} & \parbox{2cm}{Словарная проверка} & \parbox{2.5cm}{Словарная и композиционная проверка} & \\
\hline
4 & 10 & 14 & 16 & 26.3 \\
6 & 14 & 20 & 23 & 39.5 \\
8 & 18 & 24 & 30 & 52.7 \\
10 & 21 & 26 & 32 & 65.9 \\
12 & 24 & 28 & 34 & 79.0 \\
16 & 30 & 32 & 38 & 105.4 \\
20 & 36 & 36 & 42 & 131.7 \\
24 & 40 & 40 & 46 & 158.0 \\
30 & 46 & 46 & 52 & 197.2 \\
40 & 56 & 56 & 62 & 263.4 \\
\hline
\end{tabular} }
\end{table}
В табл. \ref{tab:password-entropy} приведена оценка NIST на величину энтропии пользовательских паролей в зависимости от их длины и сравнение с энтропией случайных паролей с равномерным распределением символов из набора в $D=94$ символов клавиатуры. Вероятное число попыток для подбора пароля составляет $O(2^H)$. Из таблицы видно, что по критериям NIST энтропия реальных паролей в 2--4 раза меньше энтропии случайных паролей с равномерным распределением символов.
\example
Оценим общее количество существующих паролей. Население Земли -- 7 млрд. Предположим, что все население использует компьютеры, Интернет, и у каждого человека по 10 паролей. Общее количество существующих паролей -- $7 \cdot 10^{10} \approx 2^{36}$.
%Следовательно, \emph{реальная энтропия паролей не превышает 36 бит}.
Имея доступ к наиболее массовым интернет-сервисам с количеством пользователей десятки и сотни миллионов, в которых пароли часто хранятся в открытом виде из-за необходимости обновления ПО и, в частности, выполнения аутентификации, мы 1) имеем базу паролей, покрывающую существенную часть пользователей, 2) можем статистически построить правила генерирования паролей. Даже если пароль хранится в защищенном виде, то при вводе пароль, как правило, в открытом виде пересылается по Интернету, и все преобразования пароля для аутентификации осуществляет интернет-сервис, а не веб-браузер. Следовательно, интернет-сервис имеет доступ к исходному паролю.
\exampleend
В 2002 г. был подобран ключ для 64-битового блокового шифра RC5 сетью \texttt{distributed.net} персональных компьютеров, выполнявших вычисления в фоновом режиме. Суммарное время вычислений всех компьютеров -- 1757 дней, было проверено 83\% пространства всех ключей. Это означает, что пароли с оценочной энтропией менее 64 бит, то есть \emph{все пароли} до 40 символов по критериям NIST, могут быть подобраны в настоящее время. Конечно, с оговорками на то, что 1) нет ограничений на количество и скорость попыток аутентификаций, 2) алгоритм генерирования вероятных паролей эффективен.
Строго говоря, использование даже 40-символьного пароля для аутентификации или в качестве ключа блокового шифрования является небезопасным.
\subsubsection{Число паролей}
Приведем различные оценки числа паролей, создаваемых людьми.
Пароли, создаваемые людьми, основаны на словах или закономерностях естественного языка. В английском языке всего около $1\ 000\ 000 \approx 2^{20}$ слов, включая термины.
%http://www.springerlink.com/content/bh216312577r6w64/fulltext.pdf
%http://www.antimoon.com/forum/2004/4797.htm
Используемые слоги английского языка имеют вид V, CV, VC, CVV, VCC, CVC, CCV, CVCC, CVCCC, CCVCC, CCCVCC, где C -- согласная (consonant), V -- гласная (vowel). 70\% слогов имеют структуру VC или CVC. Общее число слогов $S = 8000 - 12000$. Средняя длина слога -- 3 буквы.
Предполагая равновероятное распределение всех слогов английского языка, для числа паролей из $r$ слогов получим верхнюю оценку
\[ N_1 = S^r = 2^{13 r} \approx 2^{4.3 L_1}. \]
Средняя длина паролей составит
\[ L_1 \approx 3 r. \]
Теперь предположим, что пароли могут состоять только из 2--3 буквенных слогов вида CV, VC, CVV, VCC, CVC, CCV с равновероятным распределением символов. Подсчитаем число паролей $N_2$, которые могут быть построены из $r$ таких слогов. В английском алфавите $n_v = 10, n_c = 16, n = n_v + n_c = 26$. Верхняя оценка числа $r$-слоговых паролей:
\[ N_2 = (n_c n_v + n_v n_c + n_c n_v n_v + n_v n_c n_c + n_c n_v n_c + n_c n_c n_v)^r \approx \]
\[ \approx \left( n_c n_v(3 n_c + n_v) \right)^r, \]
\[ N_2 \approx \left( \frac{n^3}{2} \right)^r \approx 2^{13 r} \approx 2^{4.3 L_2}. \]
Средняя длина паролей:
\[ L_2 = \frac{n_c n_v(2 + 2 + 3 n_v + 3 n_c + 3 n_c + 3 n_c)}{n_c n_v (1 + 1 + n_v + n_c + n_c + n_c)} \cdot r \approx 3 r. \]
Как видно, получились одинаковые оценки числа и длины паролей.
Подсчитаем верхние оценки числа паролей из $L$ символов, предполагая равномерное распределение символов из алфавита в $D$ символов: a) $D_1 = 26$ строчных буквы, б) все $D_2 = 94$ печатных символа клавиатуры (латиница и небуквенные символы):
\[ N_3 = D_1^L \approx 2^{4.7 L}, \]
\[ N_4 = D_2^L \approx 2^{6.6 L}. \]
\begin{table}[h!]
\centering
\caption{Различные верхние оценки числа паролей\label{tab:password-number}}
\resizebox{\textwidth}{!}{ \begin{tabular}{|c||c|c|c|}
\hline
\multirow{2}{*}{\parbox{1.5cm}{Длина пароля}} & \multicolumn{3}{|c|}{Число паролей} \\
\cline{2-4}
& \parbox{3cm}{На основе слоговой композиции} &
\parbox{3cm}{Алфавит $D=26$ символов} &
\parbox{3cm}{Алфавит $D=94$ символа} \\
\hline \hline
6 & $2^{26}$ & $2^{28}$ & $2^{39}$ \\
9 & $2^{39}$ & $2^{42}$ & $2^{59}$ \\
12 & $2^{52}$ & $2^{56}$ & $2^{79}$ \\
15 & $2^{65}$ & $2^{71}$ & $2^{98}$ \\
\hline
21 & $2^{91}$ & $2^{99}$ & $2^{137}$ \\
\hline
39 & $2^{169}$ & $2^{183}$ & $2^{256}$ \\
\hline
\end{tabular} }
\end{table}
Из таблицы \ref{tab:password-number} видно, что при доступном объеме вычислений в $2^{60 \ldots 70}$ операций пароли вплоть до 15 символов, построенные на словах, слогах, изменениях слов, вставках цифр, небольшом изменении регистров и других простейших модификациях, могут быть найдены перебором на кластере (или ПК) в настоящее время.
Для достижения криптостойкости паролей, сравнимой со 128- или 256-битовым секретным ключом, требуется выбирать пароль из 20 и 40 символов соответственно, что, как правило, не реализуется из-за сложности запоминания и ввода без ошибок.
%Подсчитаем число паролей $N_1$, которые могут могут построены из $r$ ~ 2-3 буквенных слогов: $cv, vc, ccv, cvc, vcc$, где $c$ -- согласная, $v$ -- гласная. В английском алфавите $n_v = 10, n_c = 16, n = n_v + n_c = 26$. Число паролей
% \[ N_1 = \left( n_v n_c (1 + 1 + n_c + n_c + n_c) \right)^r \approx 3^r n_v^r n_c^{2r}. \]
%Средняя длина паролей
% \[ L = r \left( \frac{2 + 2 + 3 n_c + 3 n_c + 3 n_c}{1 + 1 + n_c + n_c + n_c} \right) \approx 3r. \]
%
%%Учтем, что $b \leq r$ символов могут быть заглавными: $N_1 \rightarrow N_2 < N_1 \binom{L}{b} \left( \frac{n}{n_v} \right)^b$. Вставим $d$ цифр в случайные места: $N_2 \rightarrow N_3 = N_2 (10 (1 + L))^d \approx N_2 (10 L)^d$.
%%
%%Общее число паролей
%% \[ N = N_3 = 3^r 10^r 16^{2r} \binom{3r}{b} 2.6^b \left(10 \cdot 3 r \right)^d. \]
%%
%%\begin{table}[h!]
%% \centering
%% \small
%% \begin{tabular}{|c|c|c|c|c||cr|}
%% \hline
%% \parbox{1.3cm}{Слогов, $r$} & \parbox{1.8cm}{Заглавных букв, $b$} & \parbox{1.5cm}{Вставок цифр, $d$} & \parbox{2.8cm}{Средняя длина пароля, $L+d$} & \parbox{3cm}{Верхняя оценка числа паролей $N$} & \multicolumn{2}{|c|}{\parbox{3.2cm}{Число всех паролей}} \\
%% \hline
%% $2$ & $0$ & $0$ & $6$ & $2^{26}$ & $2^{36}$ & a-z \\
%% $2$ & $2$ & $0$ & $6$ & $2^{32}$ & $2^{48}$ & A-Z, a-z \\
%% $2$ & $2$ & $2$ & $8$ & $2^{45}$ & $2^{48}$ & A-Z, a-z, 0-9 \\
%% \hline
%% $3$ & $0$ & $0$ & $9$ & $2^{39}$ & $2^{54}$ & a-z \\
%% $3$ & $3$ & $0$ & $9$ & $2^{49}$ & $2^{54}$ & A-Z, a-z \\
%% $3$ & $3$ & $2$ & $11$ & $2^{63}$ & $2^{65}$ & A-Z, a-z, 0-9 \\
%% \hline
%% $4$ & $0$ & $0$ & $12$ & $2^{52}$ & $2^{93}$ & a-z \\
%% $4$ & $3$ & $0$ & $12$ & $2^{64}$ & $2^{186}$ & A-Z, a-z \\
%% $4$ & $3$ & $2$ & $14$ & $2^{78}$ & $2^{222}$ & A-Z, a-z, 0-9 \\
%% \hline
%% \end{tabular}
%% \caption{Сравнение верхней оценки числа паролей, построенных на слогах, со всем доступным множеством паролей.}
%% \label{tab:password-number}
%%\end{table}
%
%Учтем, что $b$ символов в пароле могут быть взяты не из 26-символьного алфавита строчных букв, а из всего алфавита в $D=94$ печатных символа клавиатуры (латиница и небуквенные символы):
%\[
% \begin{array}{ll}
% b=1 & N_1 \rightarrow N_2 = \frac{n_v}{n_v+n_c} 3^r n_v^{r-1} n_c^{2r} \cdot L. \]
%
% \[ N_1 \rightarrow N_2 < N_1 \binom{L}{b} \left( \frac{D}{n_v} \right)^b. \]
%
%
%
%Общее число паролей
% \[ N < 3^r n_v^r n_c^{2r} \binom{L}{b} \left( \frac{D}{n_v} \right)^b = 3^r 10^r 16^{2r} \binom{3r}{b} \left( \frac{94}{10} \right)^b. \]
%
%\begin{table}[h!]
% \centering
% \small
% \begin{tabular}{|c|c|c|c||cr|}
% \hline
% \parbox{1.5cm}{Слогов, $r$} & \parbox{3cm}{Средняя длина пароля, $L$} & \parbox{3cm}{Символов из всего алфавита, $b$} & \parbox{3cm}{Верхняя оценка числа паролей $N$} & \multicolumn{2}{|c|}{\parbox{3.2cm}{Число всех паролей, $D^L$}} \\
% \hline
% \multirow{3}{*}{2} & \multirow{3}{*}{6} & $0$ & $2^{26}$ & $2^{28}$ & a-z \\
% & & $1$ & $2^{32}$ & $2^{34}$ & A-Z, a-z \\
% & & $3$ & $2^{40}$ & $2^{39}$ & Весь алфавит \\
% \hline
% \multirow{3}{*}{3} & \multirow{3}{*}{9} & $0$ & $2^{39}$ & $2^{42}$ & a-z \\
% & & $2$ & $2^{50}$ & $2^{51}$ & A-Z, a-z \\
% & & $4$ & $2^{59}$ & $2^{59}$ & Весь алфавит \\
% \hline
% \multirow{3}{*}{4} & \multirow{3}{*}{12} & $0$ & $2^{52}$ & $2^{56}$ & a-z \\
% & & $3$ & $2^{69}$ & $2^{68}$ & A-Z, a-z \\
% & & $6$ & $2^{81}$ & $2^{77}$ & Весь алфавит \\
% \hline
% \end{tabular}
% \caption{Сравнение верхней оценки числа паролей, построенных на слогах, со всем доступным множеством паролей в алфавите из $D$ символов.}
% \label{tab:password-number}
%\end{table}
%
%Из таблицы \ref{tab:password-number} видно, что при доступном объеме вычислений в $2^{60 \ldots 70}$ операций, пароли вплоть до 12 символов, построенные на словах, слогах, изменениях слов, вставках цифр, небольшого изменения регистров и другой простейшей обфускации, могут быть найдены перебором на кластере (или ПК) в настоящее время.
\subsubsection{Атака для подбора паролей и ключей шифрования}
В схемах аутентификации по паролю иногда используется хэширование и хранение хэша пароля на сервере. В таких случаях применима словарная атака или атака с применением заранее вычисленных таблиц для ускорения поиска.
Для нахождения пароля, прообраза хэш-функции, или для нахождения ключа блокового шифрования по атаке с выбранным шифротекстом (для одного и того же известного открытого текста и соответствующего шифротекста) может быть применен метод перебора с балансом между памятью и временем вычислений. Самый быстрый метод радужных таблиц (rainbow tables)\index{радужные таблицы}, 2003 г., заранее вычисляет следующие цепочки и хранит результат в памяти.
Для нахождения пароля, прообраза хэш-функции $H$, цепочка строится как
\[ M_0 \xrightarrow{H(M_0)} h_0 \xrightarrow{R_0(h_0)} M_1 \ldots M_t \xrightarrow{H(M_t)} h_t \xrightarrow{R_t(h_t)} M_{t+1}, \]
где $R_i(h)$ -- функция редуцирования, преобразования хэша в пароль для следующего хэширования.
Для нахождения ключа блокового шифрования для одного и того же известного открытого текста $M$ таблица строится как
\[ K_0 \xrightarrow{E_{K_0}(M)} c_0 \xrightarrow{R_0(c_0)} K_1 \ldots K_t \xrightarrow{E_{K_t}(M)} c_t \xrightarrow{R_t(c_t)} K_{t+1}, \]
где $R_i(c)$ -- функция редуцирования, преобразования шифротекста в новый ключ.
Функция редуцирования $R_i$ зависит от номера итерации, чтобы избежать дублирующиеся подцепочки, которые возникают в случае коллизий между значениями в разных цепочках в разных итерациях, если $R$ постоянна. Rainbow-таблица размера $(m \times 2)$ состоит из строк $(M_{0,j}, M_{t+1,j})$ или $(K_{0,j}, K_{t+1,j})$, вычисленных для разных значений стартовых паролей $M_{0,j}$ или $K_{0,j}$ соответственно.
Опишем атаку на примере нахождения прообраза $\overline{M}$ хэша $\overline{h} = H(\overline{M})$. На первой итерации исходный хэш $\overline{h}$ редуцируется в сообщение $\overline{h} \xrightarrow{R_t(\overline{h})} \overline{M}_{t+1} $ и сравнивается со всеми значениями последнего столбца $M_{t+1,j}$ таблицы. Если нет совпадения, переходим ко второй итерации. Хэш $\overline{h}$ дважды редуцируется в сообщение $\overline{h} \xrightarrow{R_{t-1}(\overline{h})} \overline{M}_t \xrightarrow{H(\overline{M}_t)} \overline{h}_t \xrightarrow{R_t(\overline{h}_t)} \overline{M}_{t+1}$ и сравнивается со всеми значениями последнего столбца $M_{t+1,j}$ таблицы. Если не совпало, то переходим к третьей итерации и т.д. Если для $r$-кратного редуцирования сообщение $\overline{M}_{t+1}$ содержится в таблице во втором столбце, то из совпавшей строки берется $M_{0,j}$, и вся цепочка пробегается заново для поиска искомого сообщения $\overline{M}: ~ \overline{h} = H(\overline{M})$.
Найдем вероятность нахождения пароля в таблице. Пусть мощность множества всех паролей $N$. Изначально в столбце $M_{0,j}$ содержится $m_0 = m$ различных паролей. Предполагая случайное отображение с пересечениями паролей $M_{0,j} \rightarrow M_{1,j}$, в $M_{1,j}$ будет $m_1$ различных паролей. Согласно задаче о размещении,
\[
m_{i+1} = N \left( 1 - \left( 1 - \frac{1}{N} \right)^{m_i} \right) \approx N \left( 1 - e^{-\frac{m_i}{N}} \right).
\]
Вероятность нахождения пароля
\[
P = 1 - \prod \limits_{i=1}^t \left( 1 - \frac{m_i}{N} \right).
\]
Чем больше таблица из $m$ строк, тем больше шансов найти пароль или ключ, выполнив в наихудшем случае $O \left( m \frac{t(t+1)}{2} \right)$ операций.
Примеры применения атаки на хэш-функциях $\textrm{MD5}$\index{MD5}, $\textrm{LM} \sim \textrm{DES}_{\textrm{Password}} (\textrm{const})$ приведены в табл. \ref{tab:rainbow-tables}.
\begin{table}[h!]
\centering
\caption{Атаки на радужных таблицах на \emph{одном} ПК\label{tab:rainbow-tables}}
\resizebox{\textwidth}{!}{ \begin{tabular}{|c|c|c|c|c|c|c|}
\hline
\multirow{2}{*}{\parbox{1.0cm}{Длина, биты}} & \multicolumn{3}{|c|}{Пароль или ключ} &
\multicolumn{3}{|c|}{Радужная таблица} \\
\cline{2-7}
& \parbox{1.2cm}{Длина, симв.} & \parbox{1cm}{Множе- ство} & \parbox{1cm}{Мощн- ость} &
Объем & \parbox{1.5cm}{Время вычисления таблиц} & \parbox{1.3cm}{Время поиска} \\
\hline \hline
\multicolumn{7}{|c|}{Хэш LM} \\
\hline
\multirow{3}{*}{$2 \times 56$} & \multirow{3}{*}{14} &
A--Z & $2^{33}$ & 610 MB & & 6 с \\
& & A--Z, 0-9 & $2^{36}$ & 3 GB & & 15 с \\
& & все & $2^{43}$ & 64 GB & \parbox{1.5cm}{несколько лет} & 7 мин \\
\hline \hline
\multicolumn{7}{|c|}{Хэш MD5} \\
\hline
128 & 8 & a-z, 0-9 & $2^{41}$ & 36 GiB & - & 4 мин \\
\hline
\end{tabular} }
\end{table}
\section{Аутентификация по паролю}
Из-за малой энтропии пользовательских паролей во всех системах регистрации и аутентификации пользователей применяется специальная политика безопасности. Типичные минимальные требования:
\begin{enumerate}
\item Длина пароля от 8 символов. Использование разных регистров и небуквенных символов в паролях. Запрет паролей из словаря слов или часто используемых паролей. Запрет паролей в виде дат, номеров машин и других номеров.
\item Ограниченное время действия пароля. Обязательная смена пароля по истечении срока действия.
\item Блокирование возможности аутентификации после нескольких неудачных попыток. Ограниченное число актов аутентификаций в единицу времени. Временная задержка перед выдачей результата аутентификации.
\end{enumerate}
Дополнительные рекомендации (требования) пользователям:
\begin{enumerate}
\item Не использовать одинаковые или похожие пароли для разных систем. Например, электронная почта, вход в ОС, электронная платежная система, форумы, социальные сети. Пароль часто передается в открытом виде по сети. Пароль доступен администратору системы, возможны утечки конфиденциальной информации с серверов. Стараться выбирать случайные стойкие пароли.
\item Не записывать пароли. Никому не сообщать пароль, даже администратору. Не передавать пароли по почте, телефону, Интернету и т.д.
\item Не использовать одну и ту же учетную запись для разных пользователей даже в виде исключения.
\item Всегда блокировать компьютер, когда пользователь отлучается от него даже на короткое время.
\end{enumerate}
\section[Хранение паролей и аутентификация в ОС]{Хранение паролей и \protect\\ аутентификация в ОС}
Для усложнения подбора пароля и избежания словарной атаки используется добавление перед хэшированием к паролю соли, случайной битовой строки. \textbf{Солью} (salt)\index{соль} называется (псевдо)случайная битовая строка $s$, добавляемая к аргументу $m$ (паролю) функции хэширования $h(m)$ для рандомизации хэширования одинаковых сообщений. Соль передается (хранится) вместе с вычисленным хэшем для возможности повторных вычислений:
\[ s ~\|~ h(s ~\|~ m). \]
Соль применяется для избежания словарных атак.
\textbf{Словарная} атака заключается в том, что злоумышленник один раз заранее вычисляет таблицы хэшей от наиболее \emph{вероятных} сообщений, т.е. составляет словарь, и далее производит поиск по вычисленной таблице для взламывания исходного сообщения. Словарные атаки использовались ранее для взлома паролей $m$, которые хранились в виде обычных хэшей $h(m)$. Усовершенствованной словарной атакой является метод радужных таблиц, позволяющий практически взламывать хэши длиной до 64--128 бит.
Использование соли делает невозможной словарную атаку, так как после нахождения совпадения хэша в словаре злоумышленник вынужден будет подбирать соль, что вычислительно трудоемко или невозможно.
В рассмотренной ранее модели построения паролей в виде слогов с элементами небольшой модификации мы получили количество паролей около $2^{70}$ для 12-символьных паролей. Данный объем вычислений уже почти достижим. Следовательно, даже соль не защищает пароли от взлома, если у злоумышленника есть доступ к файлу с паролями или возможность неограниченных попыток аутентификации. Поэтому файлы с паролями дополнительно защищаются, а в системы аутентификации по паролю вводят ограничения на попытки неуспешной аутентификации.
\subsection[Unix]{Хранение паролей в Unix}
В ОС Unix пароль $m$ пользователя хранится в файле \texttt{/etc/shadow} в виде хэша (SHA, MD5 и~т.д.) или результата шифрования (DES, Blowfish и~т.д.), вычисленного с солью $s$ длиной от 2 (для функции crypt в оригинальной ОС UNIX) до 16 (для Blowfish в OpenBSD) ASCII-символов. То, как используется соль, зависит от используемого алгоритма. Например, в традиционном алгоритме, используемом в оригинальном UNIX, соль модифицирует S-блоки и P-блоки в протоколе DES.
Файл \texttt{/etc/shadow} доступен только привилегированным процессам, что вносит дополнительную защиту.
\subsection[Windows]{Хранение паролей и аутентификация в \protect\\ Windows}
%[MS-NLMP]: NT LAN Manager (NTLM) Authentication Protocol Specification -- 09/25/2009, Rev. 11.0
%http://blogs.technet.com/authentication/archive/2006/04/07/ntlm-s-time-has-passed.aspx
%http://technet.microsoft.com/en-us/library/cc755284(WS.10).aspx -- Windows Authentication, Updated: February 7, 2008
%http://207.46.16.252/en-us/magazine/2006.08.securitywatch.aspx - The Most Misunderstood Windows Security Setting of All Time, Jesper Johansson
%http://en.wikipedia.org/wiki/NTLM
%http://www.windowsnetworking.com/nt/atips/atips92.shtml
ОС Windows, начиная с Vista, Server 2008, Windows 7, сохраняет пароли в виде NT-хэша, который вычисляется как 128-битовый хэш MD4 от пароля в Unicode кодировке. NT-хэш не использует соль, поэтому применима словарная атака. На словарной атаке основаны программы поиска (взлома) паролей для Windows. Файл паролей называется SAM (Security Account Manager) в случае локальной аутентификации. Если пароли хранятся на сетевом сервере, то они хранятся в специальном файле, доступ к которому ограничен.
В последнем протоколе аутентификации NTLMv2\footnote{[MS-NLMP]: NT LAN Manager (NTLM) Authentication Protocol Specification, Rev. 11.}\index{NTLM, NTLMv2} пользователь для входа в свой компьютер аутентифицируется либо локально на компьютере, либо удаленным сервером, если учетная запись пользователя хранится на сервере. Пользователь с именем $user$ вводит пароль в программу-\emph{клиент}, которая, взаимодействуя с программой-\emph{сервером} (локальной или удаленной на сервере домена $domain$), аутентифицирует пользователя для входа в систему.
\begin{enumerate}
\item Клиент $\rightarrow$ Сервер: запрос аутентификации.
\item Клиент $\leftarrow$ Сервер: 64-битовая псевдослучайная одноразовая метка $n_s$.
\item Вводимый пользователем пароль хэшируется в $\textrm{NThash}$ без соли. Клиент генерирует 64-битовую псевдослучайную одноразовую метку $n_c$, создает метку времени $ts$. Далее вычисляются 128-битовые коды аутентификации сообщений $\HMAC$ на хэш-функции MD5 с ключами $\textrm{NT-hash}$ и $\textrm{NTOWF}$:
\[ \textrm{NThash} = \text{MD4}(\text{Unicode}(\text{пароль})), \]
\[ \textrm{NTOWF} = \textrm{HMAC-MD5}_{\textrm{NThash}}(user, domain), \]
%\[ \text{LMv2-response} = \text{HMAC-MD5}_{\text{NTLMv2-hash}}(n_c, n_s), \]
\[ \textrm{NTLMv2-response} = \textrm{HMAC-MD5}_{\textrm{NTOWF}}(n_c, n_s, ts, domain). \]
\item Клиент $\rightarrow$ Сервер: $(n_c, \textrm{NTLMv2-response})$. %LMv2-response,
\item Сервер для указанных имен пользователя и домена извлекает из базы паролей требуемый NT-hash, производит аналогичные вычисления и сравнивает значения кодов аутентификации. Если они совпадают, аутентификация успешна.
\end{enumerate}
В случае аутентификации на локальном компьютере сравниваются значения $\textrm{NTOWF}$, вычисленное от пароля пользователя и извлеченное из файла паролей SAM.
Как видно, протокол аутентификации NTLMv2 обеспечивает одностороннюю аутентификацию пользователя серверу (или своему ПК).
При удаленной аутентификации по сети последние версии Windows используют протокол Kerberos, который обеспечивает взаимную аутентификацию, и только если аутентификация по Kerberos не поддерживается клиентом или сервером, она происходит по NTLMv2.
\section[Аутентификация в интернет-сервисах]{Аутентификация в \protect\\ интернет-сервисах}
Взаимодействие браузера и веб-приложения происходит по протоколу HTTP\index{протокол!HTTP}, который не поддерживает состояния. Браузер, клиент, выполняет запросы к веб-серверу, а последний отсылает браузеру запрошенные файлы (HTML-страницы, изображения, стили, скрипты и вообще любые файлы). Для каждого запроса браузер указывает полный адрес (URI, uniform resource identifier). Самые часто используемые запросы: GET (получение файла с указанным URI), POST (отправка данных, введенных пользователем, и получение нового HTML файла веб-страницы), PUT (отправка файлов на указанный URI). При использовании JavaScript (AJAX) отправлять и получать данные можно без перезагрузки страницы, но взаимодействие происходит по стандартным HTTP-запросам.
\emph{Односторонняя} аутентификация пользователя интернет-сервисом состоит из двух фаз:
\begin{enumerate}
\item первичная аутентификация по паролю при первом GET-запросе к сервису;
\item вторичная аутентификация на основе токенов аутентификации, сгенерированных веб-приложением, для \emph{каждого} последующего запроса к сервису (GET, POST и т.д.). Каждый запрос к серверу должен быть аутентифицирован, так как протокол HTTP не поддерживает состояний и сеансов. Часто аутентификацию делают через cookie.
\end{enumerate}
\emph{Взаимная} аутентификация достигается \emph{двумя} разными односторонними аутентификациями:
\begin{enumerate}
\item аутентификация пользователя интернет-сервисом по паролю и последующим сгенерированным токенам;
\item аутентификация интернет-сервиса пользователем производится с помощью SSL-соединения, которое обеспечивает первичную аутентификацию на основе открытых ключей и вторичные аутентификации кодами аутентификации сообщения и шифрованием на сеансовых ключах, сгенерированных при первичной аутентификации. Первичная аутентификация веб-сервиса производится сертификатом X.509, удостоверяющим принадлежность доменного имени URL веб-сервису, предотвращая фальсификацию веб-сервиса. Сертификат содержит ЭП \emph{общей доверенной} третьей стороны, вычисленной от значения открытых ключей, URL и других полей.
\end{enumerate}
\subsection{Первичная аутентификация по паролю}
Стандартная первичная аутентификация в современных интернет-сервисах происходит обычной передачей логина и пароля в открытом виде по сети. Если SSL-соединение не используется, логин и пароль могут быть перехвачены. Даже при использовании SSL-соединения веб-приложение имеет доступ к паролю в открытом виде.
Более защищенным, но мало используемым способом аутентификации является вычисление хэша от пароля $m$, соли $s$ и псевдослучайных одноразовых меток $n_1, n_2$ с помощью JavaScript в браузере и отсылка по сети только результата вычисления хэша.
\[ \begin{array}{ll}
\text{Браузер} ~\rightarrow~ \text{Сервис:} & \text{HTTP GET-запрос} \\
\text{Браузер} ~\leftarrow~ \text{Сервис:} & s ~\|~ n_1 \\
\text{Браузер} ~\rightarrow~ \text{Сервис:} & n_2 ~\|~ h( h(s ~\|~ m) ~\|~ n_1 ~\|~ n_2) \\
\end{array} \]
Если веб-приложение хранит хэш от пароля и соли $h(s ~\|~ m)$, то пароль не может быть перехвачен ни по сети, ни веб-приложением.
В массовых интернет-сервисах пароли часто хранятся в открытом виде на сервере, что не является хорошей практикой для обеспечения защиты персональных данных пользователей.
\input{openid}
\input{cookies_auth}
\chapter{Программные уязвимости}
\input{security_models}
\input{os_access_controls}
\section{Виды программных уязвимостей}
В 1949 г. фон Нейман ввел понятие самовоспроизводящихся механических машин.
%Самовоспроизводящейся программой называется программа, создающая и распространяющая свои копии.
\textbf{Вирусом} называется самовоспроизводящаяся часть кода (подпрограмма)\index{вирус}, которая встраивается в носители (другие программы) для своего исполнения и распространения. Вирус не может исполняться и передаваться без своего носителя.
\textbf{Червем} называется самовоспроизводящаяся отдельная (под)программа\index{червь}, которая может исполняться и распространяться самостоятельно, не используя программу-носитель.