% ------------------------------------------------------------ % Autogenerated LaTeX file for books % db2latex RELEASE: 0.8pre1 % db2latex VERSION: $Id: VERSION.xml,v 1.6 2004/01/31 12:47:11 j-devenish Exp $ % fithesis VERSION: 1.41 % ------------------------------------------------------------ \def\clsclass{rapport3} \documentclass{fithesis} % -------------------------------------------- % MetaFont and MetaPost logo support % -------------------------------------------- \usepackage{mflogo} % -------------------------------------------- % Load fithesis param % -------------------------------------------- \thesistitle{Automatické hľadanie závislostí v~kandidátnych hašovacích funkciách SHA-3} \thesissubtitle{Bakalárska práca} \thesisstudent{Ondrej Dubovec} \thesiswoman{false} \thesislang{sk} \thesisyear{jaro 2012} \thesisfaculty{fi} \thesisadvisor{RNDr. Petr Švenda, Ph.D.} % -------------------------------------------- \label{id307845}\usepackage{ifthen} % -------------------------------------------- % Check for PDFLaTeX/LaTeX % -------------------------------------------- \newif\ifpdf \ifx\pdfoutput\undefined \pdffalse % we are not running PDF\LaTeX \else \pdfoutput=1 % we are running PDF\LaTeX \pdftrue \fi % -------------------------------------------- % Load graphicx package with pdf if needed % -------------------------------------------- \ifpdf \usepackage[pdftex]{graphicx} \pdfcompresslevel=9 \else \usepackage{graphicx} \fi \usepackage{anysize} \marginsize{3cm}{2.5cm}{3.5cm}{3.5cm} \makeatletter % redefine the listoffigures and listoftables so that the name of the chapter % is printed whenever there are figures or tables from that chapter. encourage % pagebreak prior to the name of the chapter (discourage orphans). \let\save@@chapter\@chapter \let\save@@l@figure\l@figure \let\the@l@figure@leader\relax \def\@chapter[#1]#2{\save@@chapter[{#1}]{#2}% \addtocontents{lof}{\protect\def\the@l@figure@leader{\protect\pagebreak[0]\protect\contentsline{chapter}{\protect\numberline{\thechapter}#1}{}{\thepage}}}% \addtocontents{lot}{\protect\def\the@l@figure@leader{\protect\pagebreak[0]\protect\contentsline{chapter}{\protect\numberline{\thechapter}#1}{}{\thepage}}}% } \renewcommand*\l@figure{\the@l@figure@leader\let\the@l@figure@leader\relax\save@@l@figure} \let\l@table\l@figure \makeatother \usepackage{fancyhdr} \renewcommand{\headrulewidth}{0.4pt} \renewcommand{\footrulewidth}{0.4pt} % Safeguard against long headers. \IfFileExists{truncate.sty}{ \usepackage{truncate} % Use an ellipsis when text would be larger than x% of the text width. % Preserve left/right text alignment using \hfill (works for English). \fancyhead[ol]{\truncate{0.49\textwidth}{\sl\leftmark}} \fancyhead[er]{\truncate{0.49\textwidth}{\hfill\sl\rightmark}} \fancyhead[el]{\truncate{0.49\textwidth}{\sl\leftmark}} \fancyhead[or]{\truncate{0.49\textwidth}{\hfill\sl\rightmark}} }{\typeout{WARNING: truncate.sty wasn't available and functionality was skipped.}} \pagestyle{fancy} % ---------------------- % Most Common Packages % ---------------------- \usepackage{latexsym} \usepackage{enumerate} \usepackage{fancybox} \usepackage{float} \usepackage{ragged2e} \usepackage{fancyvrb} \makeatletter\@namedef{FV@fontfamily@default}{\def\FV@FontScanPrep{}\def\FV@FontFamily{}}\makeatother \fvset{obeytabs=true,tabsize=3} \makeatletter \let\dblatex@center\center\let\dblatex@endcenter\endcenter \def\dblatex@nolistI{\leftmargin\leftmargini\topsep\z@ \parsep\parskip \itemsep\z@} \def\center{\let\@listi\dblatex@nolistI\@listi\dblatex@center\let\@listi\@listI\@listi} \def\endcenter{\dblatex@endcenter} \makeatother \usepackage{rotating} \usepackage{subfigure} \usepackage{tabularx} \usepackage{url} % -------------------------------------------- % Load hyperref package with pdf if needed % -------------------------------------------- \ifpdf \usepackage[pdftex,bookmarksnumbered,colorlinks,backref,bookmarks,breaklinks,linktocpage,plainpages=false, pdfstartview=FitH, plainpages=false, pdfpagelabels, unicode]{hyperref} \else \usepackage[bookmarksnumbered,colorlinks,backref,bookmarks,breaklinks,linktocpage,plainpages=false, plainpages=false, pdfpagelabels]{hyperref} \fi % -------------------------------------------- % ---------------------------------------------- % Define a new LaTeX environment (adminipage) % ---------------------------------------------- \newenvironment{admminipage}% { % this code corresponds to the \begin{adminipage} command \begin{Sbox}% \begin{minipage}% } %done { % this code corresponds to the \end{adminipage} command \end{minipage} \end{Sbox} \fbox{\TheSbox} } %done % ---------------------------------------------- % Define a new LaTeX length (admlength) % ---------------------------------------------- \newlength{\admlength} % ---------------------------------------------- % Define a new LaTeX environment (admonition) % With 2 parameters: % #1 The file (e.g. note.pdf) % #2 The caption % ---------------------------------------------- \newenvironment{admonition}[2] { % this code corresponds to the \begin{admonition} command \hspace{0mm}\newline\hspace*\fill\newline \noindent \setlength{\fboxsep}{5pt} \setlength{\admlength}{\linewidth} \addtolength{\admlength}{-10\fboxsep} \addtolength{\admlength}{-10\fboxrule} \admminipage{\admlength} {\bfseries \sc\large{#2}} \newline \\[1mm] \sffamily \includegraphics[width=1cm]{#1} \addtolength{\admlength}{-1cm} \addtolength{\admlength}{-20pt} \begin{minipage}[lt]{\admlength} \parskip=0.5\baselineskip \advance\parskip by 0pt plus 2pt } %done { % this code corresponds to the \end{admonition} command \vspace{5mm} \end{minipage} \endadmminipage \vspace{.5em} \par } % -------------------------------------------- % Commands to manage/style/create floats % figures, tables, algorithms, examples, eqn % -------------------------------------------- \floatstyle{plain} \restylefloat{figure} \floatstyle{plain} \restylefloat{table} \floatstyle{plain} \newfloat{program}{ht}{lop}[section] \floatstyle{plain} \newfloat{example}{ht}{loe}[section] \floatname{example}{Príklad} \floatstyle{plain} \newfloat{dbequation}{ht}{loe}[section] \floatname{dbequation}{Rovnica} \floatstyle{boxed} \newfloat{algorithm}{ht}{loa}[section] \floatname{algorithm}{Algorithm} \ifpdf \DeclareGraphicsExtensions{.pdf,.png,.jpg} \else \DeclareGraphicsExtensions{.eps} \fi % -------------------------------------------- % $latex.caption.swapskip enabled for $formal.title.placement support \newlength{\docbooktolatextempskip} \newcommand{\captionswapskip}{\setlength{\docbooktolatextempskip}{\abovecaptionskip}\setlength{\abovecaptionskip}{\belowcaptionskip}\setlength{\belowcaptionskip}{\docbooktolatextempskip}} \usepackage[slovak]{babel} % Guard against a problem with old package versions. \makeatletter \AtBeginDocument{ \DeclareRobustCommand\ref{\@refstar} \DeclareRobustCommand\pageref{\@pagerefstar} } \makeatother % -------------------------------------------- \makeatletter \newcommand{\dbz}{\penalty \z@} \newcommand{\docbooktolatexpipe}{\ensuremath{|}\dbz} \newskip\docbooktolatexoldparskip \newcommand{\docbooktolatexnoparskip}{\docbooktolatexoldparskip=\parskip\parskip=0pt plus 1pt} \newcommand{\docbooktolatexrestoreparskip}{\parskip=\docbooktolatexoldparskip} \def\cleardoublepage{\clearpage\if@twoside \ifodd\c@page\else\hbox{}\thispagestyle{empty}\newpage\if@twocolumn\hbox{}\newpage\fi\fi\fi} \usepackage[latin2]{inputenc} \usepackage[T1]{fontenc} \ifx\dblatex@chaptersmark\@undefined\def\dblatex@chaptersmark#1{\markboth{\MakeUppercase{#1}}{}}\fi \let\save@makeschapterhead\@makeschapterhead \def\dblatex@makeschapterhead#1{\vspace*{-80pt}\save@makeschapterhead{#1}} \def\@makeschapterhead#1{\dblatex@makeschapterhead{#1}\dblatex@chaptersmark{#1}} \AtBeginDocument{\ifx\refname\@undefined\let\docbooktolatexbibname\bibname\def\docbooktolatexbibnamex{\bibname}\else\let\docbooktolatexbibname\refname\def\docbooktolatexbibnamex{\refname}\fi} % Facilitate use of \cite with \label \newcommand{\docbooktolatexbibaux}[2]{% \protected@write\@auxout{}{\string\global\string\@namedef{docbooktolatexcite@#1}{#2}} } % Provide support for bibliography `subsection' environments with titles \newenvironment{docbooktolatexbibliography}[3]{ \begingroup \let\save@@chapter\chapter \let\save@@section\section \let\save@@@mkboth\@mkboth \let\save@@bibname\bibname \let\save@@refname\refname \let\@mkboth\@gobbletwo \def\@tempa{#3} \def\@tempb{} \ifx\@tempa\@tempb \let\chapter\@gobbletwo \let\section\@gobbletwo \let\bibname\relax \else \let\chapter#2 \let\section#2 \let\bibname\@tempa \fi \let\refname\bibname \begin{thebibliography}{#1} }{ \end{thebibliography} \let\chapter\save@@chapter \let\section\save@@section \let\@mkboth\save@@@mkboth \let\bibname\save@@bibname \let\refname\save@@refname \endgroup } %\usepackage{cite} %\renewcommand\citeleft{(} % parentheses around list %\renewcommand\citeright{)} % parentheses around list \newcommand{\docbooktolatexcite}[2]{% \@ifundefined{docbooktolatexcite@#1}% {\cite{#1}}% {\def\@docbooktolatextemp{#2}\ifx\@docbooktolatextemp\@empty% \cite{\@nameuse{docbooktolatexcite@#1}}% \else\cite[#2]{\@nameuse{docbooktolatexcite@#1}}% \fi% }% } \newcommand{\docbooktolatexbackcite}[1]{% \ifx\Hy@backout\@undefined\else% \@ifundefined{docbooktolatexcite@#1}{% % emit warning? }{% \ifBR@verbose% \PackageInfo{backref}{back cite \string`#1\string' as \string`\@nameuse{docbooktolatexcite@#1}\string'}% \fi% \Hy@backout{\@nameuse{docbooktolatexcite@#1}}% }% \fi% } % -------------------------------------------- % A way to honour s % Blame j-devenish (at) users.sourceforge.net % In any other LaTeX context, this would probably go into a style file. \newcommand{\docbooktolatexusefootnoteref}[1]{\@ifundefined{@fn@label@#1}% {\hbox{\@textsuperscript{\normalfont ?}}% \@latex@warning{Footnote label `#1' was not defined}}% {\@nameuse{@fn@label@#1}}} \newcommand{\docbooktolatexmakefootnoteref}[1]{% \protected@write\@auxout{}% {\global\string\@namedef{@fn@label@#1}{\@makefnmark}}% \@namedef{@fn@label@#1}{\hbox{\@textsuperscript{\normalfont ?}}}% } \makeindex % index labeling helper \newif\ifdocbooktolatexprintindex\docbooktolatexprintindextrue \let\dbtolatex@@theindex\theindex \let\dbtolatex@@endtheindex\endtheindex \@ifundefined{@openrighttrue}{\newif\if@openright}{} \def\theindex{\relax} \def\endtheindex{\relax} \newenvironment{dbtolatexindex}[2] { \if@openright\cleardoublepage\else\clearpage\fi \let\dbtolatex@@indexname\indexname \def\dbtolatex@current@indexname{#2} \ifx\dbtolatex@current@indexname\@empty \def\dbtolatex@current@indexname{\dbtolatex@@indexname} \fi \def\dbtolatex@indexlabel{% \ifnum \c@secnumdepth >\m@ne \ifx\c@chapter\undefined\refstepcounter{section}\else\refstepcounter{chapter}\fi\fi% \label{#1}\hypertarget{#1}{\dbtolatex@current@indexname}% \global\docbooktolatexprintindexfalse} \def\indexname{\ifdocbooktolatexprintindex\dbtolatex@indexlabel\else\dbtolatex@current@indexname\fi} \dbtolatex@@theindex } { \dbtolatex@@endtheindex\let\indexname\dbtolatex@@indexname } \newlength\saveparskip \newlength\saveparindent \newlength\tempparskip \newlength\tempparindent \def\docbooktolatexgobble{\expandafter\@gobble} % Prevent multiple openings of the same aux file % (happens when backref is used with multiple bibliography environments) \ifx\AfterBeginDocument\undefined\let\AfterBeginDocument\AtBeginDocument\fi \AfterBeginDocument{ \let\latex@@starttoc\@starttoc \def\@starttoc#1{% \@ifundefined{docbooktolatex@aux#1}{% \global\@namedef{docbooktolatex@aux#1}{}% \latex@@starttoc{#1}% }{} } } % -------------------------------------------- % Hacks for honouring row/entry/@align % (\hspace not effective when in paragraph mode) % Naming convention for these macros is: % 'docbooktolatex' 'align' {alignment-type} {position-within-entry} % where r = right, l = left, c = centre \newcommand{\docbooktolatex@align}[2]{\protect\ifvmode#1\else\ifx\LT@@tabarray\@undefined#2\else#1\fi\fi} \newcommand{\docbooktolatexalignll}{\docbooktolatex@align{\raggedright}{}} \newcommand{\docbooktolatexalignlr}{\docbooktolatex@align{}{\hspace*\fill}} \newcommand{\docbooktolatexaligncl}{\docbooktolatex@align{\centering}{\hfill}} \newcommand{\docbooktolatexaligncr}{\docbooktolatex@align{}{\hspace*\fill}} \newcommand{\docbooktolatexalignrl}{\protect\ifvmode\raggedleft\else\hfill\fi} \newcommand{\docbooktolatexalignrr}{} \ifx\captionswapskip\@undefined\newcommand{\captionswapskip}{}\fi \makeatother \title{\bfseries Automatické hľadanie závislostí v~kandidátnych hašovacích funkciách SHA-3\\[12pt]\normalsize Bakalárska práca} \author{Ondrej Dubovec} % -------------------------------------------- \makeglossary % -------------------------------------------- \setcounter{tocdepth}{4} \setcounter{secnumdepth}{4} \begin{document} % -------------------------------------------- % Useing fithesis % -------------------------------------------- \FrontMatter \ThesisTitlePage \begin{ThesisDeclaration} \DeclarationText \AdvisorName \end{ThesisDeclaration} % -------------------------------------------- % Thanks % -------------------------------------------- \begin{ThesisThanks} Ďakujem vedúcemu práce RNDr. Petrovi Švendovi, Ph.D. za odborné vedenie práce, cenné rady a čas ktorý mi venoval. Poďakovanie patrí aj kolegovi Bc. Matejovi Prišťákovi za spoluprácu pri úpravách použitej aplikácie, ako aj celej mojej rodine za podporu.\end{ThesisThanks} % -------------------------------------------- % Abstract % -------------------------------------------- \begin{ThesisAbstract} Práca je zameraná na hľadanie závislostí v~kandidátnych hashovacích funkciách SHA-3 pomocou nástroja využívajúceho technológiu evolučného obvodu. Vybrané funkcie boli po oslabení bezpečnostných parametrov podrobené testom na vyhľadávanie nežiadúcich závislostí a to viacerými spôsobmi. \end{ThesisAbstract} % -------------------------------------------- % KeyWords % -------------------------------------------- \begin{ThesisKeyWords} hashovacie funkcie, kolízny útok, SHA-3 kandidáti, evolučný algoritmus, evolučný obvod, Sensor Security Simulator\end{ThesisKeyWords} \makeatletter \def\dbtolatex@contentsid{id268640} \def\dbtolatex@@contentsname{\latex@@contentsname} \let\latex@@contentsname\contentsname \newif\ifdocbooktolatexcontentsname\docbooktolatexcontentsnametrue \def\dbtolatex@contentslabel{% \label{\dbtolatex@contentsid}\hypertarget{\dbtolatex@contentsid}{\dbtolatex@@contentsname}% \global\docbooktolatexcontentsnamefalse} \def\contentsname{\ifdocbooktolatexcontentsname\dbtolatex@contentslabel\else\dbtolatex@@contentsname\fi} \let\save@@@mkboth\@mkboth \let\@mkboth\@gobbletwo \tableofcontents \let\@mkboth\save@@@mkboth \let\contentsname\latex@@contentsname \Hy@writebookmark{}{\dbtolatex@@contentsname}{\dbtolatex@contentsid}{0}{toc}% \makeatother \MainMatter % ------------------------------------------------------------- % Chapter Úvod % ------------------------------------------------------------- \chapter{Úvod} \label{ch01}\hypertarget{ch01}{}% Bezpečnosť bola jedným z~najdôležitejších aspektov pri komunikácii už v~dávnej minulosti. Vždy bolo potrebné dodanie nepoškodenej správy, poprípade zabezpečiť, aby správu dokázal prečítať len pravý príjemca. Takto vznikali rozličné techniky, ako napríklad napísanie správy na oholenú hlavu otroka, ktorý ju doručil až po opätovnom narastení vlasov, kde bolo cieľom zabrániť náhodnému človeku získať prepravovanú správu. Správa mohla byť počas prepravy úmyselne, či neúmyselne zmenená. Vyriešiť to mohli napríklad používané pečate, ktoré zabezpečovali \glqq podpis\textquotedblleft{} a teda overenie pôvodu správy. Spomínané techniky však nepredpokladali znalosť týchto postupov u~možných útočníkov. Techniky sa neustále zlepšovali, no v~posledných desaťročiach problém nabral nové rozmery. Rapídny rozvoj informačných technológií, verejne prístupný Internet a mnohé ďalšie aspekty zvýšili potrebu bezpečnosti a zabezpečenia dát. Je nutné poskytnúť bezpečnú autentizáciu pri prihlasovaní na akýkoľvek server. Zabezpečenie internetového bankovníctva, ktoré zaručuje, že prevod vykonávame skutočne na účet, ktorý sme zadali. Poskytovanie istoty, že dáta sú nám prezentované v~nezmenenej podobe od autora, ktorému dôverujeme. Preto je nutné zaistiť autenticitu, integritu, nepopierateľnosť dát, kde využívame techniky digitálnych podpisov, hashovania a šifrovania. V~súčastnosti medzi používané kryptografické hashovacie funkcie (ďalej označované ako hashovacie funkcie, pokiaľ nieje explicitne uvedené inak) patria funkcie MD5, SHA-1 a SHA-2. MD5 je stále rozšírená v~mnohých systémoch a to aj napriek odporúčaniu funkciu nepoužívať z~dôvodu jej prelomenia v~roku 2004. Funkcia SHA-1, ktorá vychádza z~pôvodnej SHA-0 bola taktiež prelomená v~roku 2005 publikovaným útokom, ktorý nachádzal kolízie v~čase lepšom ako v~prípade útoku hrubou silou \docbooktolatexcite{SHA1 collision}{}. Očakávanie prelomenia funkcie SHA-2 sú pravdepodobne jedným z~dôvodov vypísania súťaže o~novú hashovaciu funkciu, ktorá ponesie názov SHA-3. Prvá časť bakalárskej práce sa zaoberá všeobecným pohľadom na hashovacie funkcie, popisuje ich hlavné rozdelenie, v~krátkosti približuje aj funkcie, ktoré nie sú predmetom skúmania tejto práce a objasňuje ich využitie v~praxi. V~podkapitolách je podrobne rozobraté rozdelenie kryptografických hashovacích funkcií, ako aj bezpečnostné požiadavky kladené na každý typ funkcie. Práca pokračuje popisom všeobecných aj viac konkretizovaných útokov na hashovacie funkcie. Taktiež je v~krátkosti popísaná sútaž o~SHA-3 algoritmus, vymenované funkcie, ktoré sa do sútaže zapojili a ktoré z~nich sú hlavným cieľom nášho testovania. Nasledujúca kapitola spolu s~podkapitolami popisuje technológiu evolučných obvodov, ich funkcie a tiež ich implementáciu v~aplikácii Sensor Security Simulator. Je tu predstavené použitie obvodu na minulé výpočty, teda napr. pokusy o~hľadanie inverzie u~funkcií MD5 a SHA-1. Kapitola neskôr popisuje nami navrhnuté postupy testovania kandidátnych funkcií, ich konkrétne riešenia v~evolučnom obvode a implementáciu v~pôvodnej aplikácii. Tiež popisujeme spôsob integrácie SHA-3 kandidátov do projektu podľa predpísaného NIST rozhrania, ktoré museli kandidátne funkcie spĺňať. Posledná kapitola rozoberá jednotlivé testované algoritmy a prezentuje získané výsledky. Uvádzame nastavenia obvodu počas testov, výsledné hodnoty jednotlivých testov, porovnávame grafy behov a obvody, ktoré boli schopné sa na dátach učiť. Text bakalárskej práce bol vytvorený pomocou značkovacieho jazyku DocBook vo formáte XML. Následne boli na prevod použité XSL transformácie od Jana Pavloviča \docbooktolatexcite{Pavlovic}{}. Na generovanie grafov evolučných obvodov bol použitý software Graphviz \docbooktolatexcite{graphviz}{}. % ------------------------------------------------------------- % Chapter Hashovacie funkcie % ------------------------------------------------------------- \chapter{Hashovacie funkcie} \label{ch02}\hypertarget{ch02}{}% Kryptografické hashovacie funkcie tvoria nenahraditeľnú časť súčasnej kryptografie. Úlohou všetkých hashovacích funkcií je prevod vstupných dát rôzneho formátu a ľubovoľnej, ale konečnej dĺžky (správy, message) na výstup fixnej dĺžky, označovaný ako hash (hash value, message digest, digest), ktorý nám slúži ako kompaktná reprezentácia vstupných dát. Aby však funkcie využívané v~oblasti bezpečnosti boli schopné plniť svoju úlohu, kladieme dodatočné požiadavky na vlastnosti ich výstupu, čím nám vznikajú nástroje vhodné pri aplikáciách požadujúcich zvýšenú úroveň bezpečnosti. Z~dôvodu zabezpečenia integrity dát využívame hashovacie funkcie pri technikách digitálneho podpisu (digital signature). V~tomto prípade je dokument ľubovoľnej dĺžky najprv hashovaný pomocou známej hashovacej funkcie a až výsledný hash následne podpísaný (zašifrovaný) privátnym kľúčom odosielateľa. Možnosť podpisu krátkeho hashu poskytuje výhodu oproti nutnosti podpisovať pôvodný dokument, ktorého veľkosť sa može pohybovať v~MB i GB. Nieje totiž bezpečné dokument rozdeliť na menšie časti a tie následne podpisovať. Takto podpísanú správu je následne možné zo strany príjemcu overiť, a to na základe znalosti použitej hashovacej funkcie a znalosti verejneho kľúča. Digitálny podpis okrem integrity zabezpečuje aj autenticitu a nepopierateľnosť pôvodu dokumentu. Osobitnou triedou hashovacích funkcií sú Message Authentication Codes (MACs). Môžeme ich označiť ako kľúčované hashovacie funkcie (keyed hash functions). Ako vstup príjmajú dáta konečnej dĺžky a tajnú informáciu, ktorou je kľúč. Spomínaný kľúč musí byť vopred dohodnutým zdieľaným tajomstvom medzi odosielateľom a príjemcom, resp. medzi všetkými účastníkmi komunikácie, ako je to v~prípade symetrickej kryptografie. Výstupom je reťazec fixnej dĺžky, pričom bez znalosti tajného kľúča je \glqq obtiažne\textquotedblleft{} \label{fn0201}\begingroup\catcode`\#=12\footnote{ v~angličtine označované slovným spojením \glqq computationally infeasible\textquotedblleft{} - znamená možnosť riešenia problému len na teoretickej úrovni. Pri súčasnej dostupnej výpočetnej technike by praktické riešenie nebolo možné dosiahnuť v~konečnom čase. }\endgroup\docbooktolatexmakefootnoteref{fn0201} nájsť rovnaký hash bez znalosti daného kľúča. MACs nám zabezpečujú integritu dát, ako aj overenie autenticity dát medzi vlastníkmi tajného kľúča. Funkcie typu MAC je možné skonštruovať z~hashovacej funkcie (napríklad tajná časť hashu), alebo ľubovoľnej symetrickej šifry za predpokladu použitia režimu cipher block chaining \docbooktolatexcite{cbcchaining}{}. % ------------------------ % Section \section{Základné vlastnosti a definície} \label{sec0201}\hypertarget{sec0201}{}% Základné rozdelenie hashovacích funkcií vyjadruje nasledujúci obrázok \docbooktolatexcite{PreneelPhd}{} % figure ------------------------------------------------------ \begin{figure}[hbt] \hypertarget{obr0201}{}% \begin{center} {{\includegraphics[]{hashrozdelenie}}\hypertarget{id306702}{}% \label{id306702} } {{\caption[{Rozdelenie kryptografických hashovacích funkcií}]{{{Rozdelenie kryptografických hashovacích funkcií}}}\label{obr0201}}} \end{center} \end{figure} Hashovacie funkcie delíme podľa obrázku ( \hyperlink{obr0201}{Obrázok {\ref{obr0201}}}) na Autentizačné kódy správ (Message Authentication Codes, MACs) a Manipulačné detekčné kódy (Manipulation Detection Codes, MDCs). Druhá kategória funkcií sa ďalej rozdeľuje podľa bezpečnostných požiadavkov a to nasledovným spôsobom: \begin{itemize} %--- Item \item Jednosmerná hashovacia funkcia (One-way hash function, OWHF) %--- Item \item Hashovacia funkcia odolná voči kolízii (Collision resistant hash function, CRHF) %--- Item \item Univerzálna jednosmerná hashovacia funkcia (Universal one-way hash function, UOWHF) \end{itemize} \noindent Obecná hashovacia funkcia je funkcia h so vstupom X, ktorá spĺňa nasledovné podmienky: \begin{itemize} %--- Item \item Jednoduchosť výpočtu - pomocou funkcie h je jednoduché vypočítať hodnotu h(X). %--- Item \item Kompresia - vstup konečnej dĺžky X je pomocou funkcie h mapovaný na výstup h(X) o~fixnej dĺžke n bitov. \end{itemize} \noindent Podľa typu funkcie požadujeme dodatočné bezpečnostné vlastnosti. Tieto vlastnosti sú: \begin{itemize} %--- Item \item Odolnosť voči nájdeniu vzoru (preimage resistance). %--- Item \item Odolnosť voči nájdeniu druhého vzoru (second-preimage resistance). %--- Item \item Odolnosť voči kolíziám (collision resistance). \end{itemize} \noindent \subsection{Jednosmerná hashovacia funkcia (OWHF)} \label{sec020101}\hypertarget{sec020101}{}% Jednosmerná hashovacia funkcia h (one-way, hash function, weak one-way hash function) je funkcia (podľa definície z~\docbooktolatexcite{PreneelPhd}{}) spĺňajúca nasledujúce kritériá: \begin{itemize} %--- Item \item Popis funkcie h musí byť prístupný verejnosti a nesmie obsahovať žiadnu formu utajenej informácie potrebnú pre činnosť. Táto vlastnosť vychádza z~Kerckhoffovho princípu \docbooktolatexcite{Kerckhoff}{}, ktorý hovorí, že bezpečnosť systému zostáva zachovaná aj v~prípade, že algoritmus je známy širokej verejnosti. Jedinou utajovanou informáciou je teda kľúč. %--- Item \item Funkcia spĺňa vlastnosti obecnej hashovacej funkcie, ktorými sú kompresia a jednoduchosť výpočtu \hyperlink{sec0201}{{[2.1]}}. Dĺžka výstupu n navyše spĺňa podmienku (n $\geq$ 64). %--- Item \item Pre pevne daný hash Y je \glqq obtiažne\textquotedblleft{} nájsť správu X, pre ktorú platí Y = h(X). %--- Item \item Ku zadanej správe X je \glqq obtiažne\textquotedblleft{} nájsť správu X' takú, že X $\neq$ X' a h(X) = h(X'). \end{itemize} \noindent Tretia vlastnosť OWHF, taktiež označovaná ako jednosmernosť (one-wayness, preimage resistance) zabezpečuje funkcii odolnosť voči útokom typu preimage. Posledná vlastnosť sa tiež nazýva slabá bezkolíznosť (weak collision resistance, second-preimage resistance), je striktnejšia a relevantná pre využitie v~reálnych aplikáciách. Jednoduchým príkladom funkcie, ktorá nespĺňa jednosmernosť môže byť násobenie. Ľahko totiž vieme k~funkcii nájsť inverziu. Funkciou, ktorá jednosmerná je, môže byť napríklad faktoriál čísla. \subsection{Bezkolízna hashovacia funkcia (CRHF)} \label{sec020102}\hypertarget{sec020102}{}% Funkciu h označujeme ako bezkolíznu (collision resistant, niekedy aj strong one-way hash function) pokiaľ má nasledujúce vlastnosti \docbooktolatexcite{PreneelPhd}{}: \begin{itemize} %--- Item \item Funkcia spĺňa všetky požiadavky kladené na jednosmernú hashovaciu funkciu podľa \hyperlink{sec020101}{{[2.1.1]}}. Dĺžka výstupu n navyše spĺňa podmienku (n $\geq$ 128). %--- Item \item Je \glqq obtiažne\textquotedblleft{} nájsť 2 správy X, Y, pre ktoré platí X $\neq$ Y a h(X) = h(Y). \end{itemize} \noindent Pridaná vlastnosť funkcie značí bezkolíznosť (odolnosť voči kolíznym útokom, collision resistance). Ako však uvádza definícia, vlastnosť zaručuje obtiažny nález kolízie, ale možnosť existencie kolízie nijak nevylučuje. Uvážme hashovaciu funkciu podľa definície \hyperlink{sec020102}{{[2.1.2]}} s~výstupom dĺžky 128 bitov, ktorá má teda k~dispozícii 2 $^\textrm{\tiny 128}$ možných hodnôt hashov. V~prípade, keď uvážime vstupy ľubovoľnej dĺžky, je zrejmé, že funkcia nedokáže vyprodukovať unikátny hash pre každý z~týchto vstupov. \subsection{Univerzálna jednosmerná hashovacia funkcia (UOWHF)} \label{sec020103}\hypertarget{sec020103}{}% Koncept UOWHF bol prvý raz prezentovaný v~publikácii M. Naora a M. Yunga \docbooktolatexcite{uowhf}{}. Podstatou je používanie veľkej sady hashovacích funkcií namiesto jedinej. Funkcia je vybratá náhodne a nezávisle na type hashovaných dát, z~čoho vyplýva, že hľadanie kolízie pre jedinú z~nich je zbytočné. \subsection{Autentizačný kód správy (MAC)} \label{sec020104}\hypertarget{sec020104}{}% Funkcia h je typu MAC, pokiaľ spĺňa nasledujúce vlastnosti \docbooktolatexcite{PreneelPhd}{}: \begin{itemize} %--- Item \item Popis funkcie h musí byť prístupný verejnosti, kľúč je ale nutné udržať v~tajnosti. %--- Item \item Výsledok funkcie h(K,X) je fixnej dĺžky n (n $\geq$ 32...64), kde X je správa a K~tajný kľúč. %--- Item \item Pri zadanom h, X a K~je výpočet h(K,X) jednoduchý. %--- Item \item So znalosťou h a X je \glqq obtiažne\textquotedblleft{} získať hodnotu h(K,X) s~pravdepodobnosťou úspechu vyššou ako \ensuremath{1/2^n}. %--- Item \item Aj v~prípade, keď je známa veľká sada dvojíc \{X $_\textrm{\tiny i}$, h(K,X $_\textrm{\tiny i}$)\}, kde X $_\textrm{\tiny i}$ je zvolené útočníkom, je \glqq obtiažne\textquotedblleft{} získať kľúč K, alebo vypočítať h(K,X') pre každé X' $\neq$ X $_\textrm{\tiny i}$. \end{itemize} \noindent Princíp funkcií typu MAC je podobný tým typu MDC, pribúda nám však navyše réžia správy a distribúcie tajného kľúča. Funkcia tiež spĺňa podmienky kladené na obecnú hashovaciu funkciu (jednoduchosť výpočtu a kompresia). % ------------------------------------------------------------- % Chapter Útoky na hashovacie funkcie % ------------------------------------------------------------- \chapter{Útoky na hashovacie funkcie} \label{ch03}\hypertarget{ch03}{}% % ------------------------ % Section \section{Základné rozdelenie útokov} \label{sec0301}\hypertarget{sec0301}{}% Cieľom útokov na hashovacie funkcie je využitie slabiny, ktorú by funkcia teoreticky obsahovať nemala. Preto sú útoky stavané hlavne na predpoklade, že funkcia nebude spĺňať niektorú z~uvedených bezpečnostných požiadaviek a útočník sa ju pokúša odhaliť. Základné rozdelenie môže byť nasledovné: \begin{itemize} %--- Item \item Útoky na MDC %--- Item \item Útoky na MAC \end{itemize} \noindent \subsection{Útoky na MDC} \label{sec030101}\hypertarget{sec030101}{}% \begin{itemize} %--- Item \item (First-)preimage attack (vzorový útok) - podstata útoku je ku známemu hashu Y nájsť taký vzor (správu) X, pre ktorý bude platiť Y = h(X). %--- Item \item Second-preimage attack (druhý vzorový útok) - ku známej správe X a hodnote hashu h(X) hľadáme správu X', pre ktorú platí X $\neq$ X', h(X) = h(X'). \end{itemize} \noindent Úspech útoku je podmienený dĺžkou n výstupného hashu, tzn. komplexnosť je stanovená ako 2 $^\textrm{\tiny n}$. To je tiež dôvodom obmedzenia, ktoré určuje minimálnu dĺžku hashu ako 80 bitov a ďalšie zvýšenie poskytuje vyššiu odolnosť. Pokial útok typu first-, či second-preimage nedokážeme vykonať za menej, než spomínaných 2 $^\textrm{\tiny n}$ operácií, je funkcia považovaná za odolnú voči preimage útokom. \hyperlink{sec020101}{{[2.1.1]}}. \begin{itemize} %--- Item \item Collision attack (kolízny útok) - snahou útočníka je nájsť 2 správy X a Y také, že X $\neq$ Y a h(X) = h(Y). %--- Item \item Prefix collision attack (kolízny útok so zvoleným prefixom) - útočník vyberá 2 prefixy p1 a p2 také, že platí p1 $\neq$ p2. a k~týmto prefixom hľadá sufixy s1, s2, pre ktoré bude platiť h(p1.s1) = h(p2.s2), kde \glqq .\textquotedblleft{} je operátor zreťazenia. \end{itemize} \noindent Úspešnosť kolíznych útokov je zo všeobecného hľadiska vyššia ako pri preimage útokoch, a to z~dôvodu platnosti narodeninového paradoxu, ktorý vysvetľujeme ďalej v~kapitole. Môžeme ich však aplikovať len na funkcie typu CRHF, keďže OWHF odolnosť voči kolíziám nemajú. Vyššia náchylnosť funkcií vyplýva z~faktu, že na prelomenie funkcie stačí 2 $^\textrm{\tiny n/2}$ vykonaných pokusov, preto je minimálna požadovaná dĺžka hashu n = 160 bitov. Všetky vyššie uvedené typy útokov sa tiež nazývaju generické, pretože ich úspech závisí len na dĺžke hashu, nie však na ďalšej znalosti algoritmu. \subsection{Útoky na MAC} \label{sec030102}\hypertarget{sec030102}{}% Generický útok na MAC bude vyzerať nesledovne: \begin{itemize} %--- Item \item Za predpokladu znalosti X a hodnoty h(K,X) je útočník bez znalosti kľúča K~schopný nájsť správu X' a hash h(K,X'), pre ktorú platí X $\neq$ X'. \end{itemize} \noindent Negenerické útoky môžeme podľa dodatočných znalostí útočníka rozlišovať nasledovne \docbooktolatexcite{PreneelPhd}{}: \begin{itemize} %--- Item \item Known plaintext attack - útočník pozná niekoľko správ (plaintext) a k~nim odpovedajúce MACy. %--- Item \item Chosen plaintext attack - útočník si sám zvolí sadu plaintext správ a následne tiež všetky MACy k~týmto správam. %--- Item \item Adaptive chosen plaintext attack - najobecnejší útok, pri ktorom si útočník vyberá správy a k~nim získava odpovedajúce MACy. Každý nasledujúci výber je ovplyvnený výsledkom toho prechádzajúceho. \end{itemize} \noindent % ------------------------ % Section \section{Narodeninový útok} \label{sec0302}\hypertarget{sec0302}{}% Narodeninový útok (Birthday attack) ako najznámejší útok so zameraním na hľadanie kolízií využíva nasledujúce znalosti. V~skupine 23 ľudí majú aspoň 2 vybraní ľudia spoločný dátum narodenia s~pravdepodobnosťou vyššou ako 50\%. Pokiaľ uvážime skupinu o~počte 30 ľudí, pravdepodobnosť rovnakého javu prekročí dokonca 70\%. Výsledné pravdepodobnosti sú omnoho vyššie, než by sa očakávalo, preto tento jav nazývame \glqq narodeninový paradox\textquotedblleft{}. Všeobecný narodeninový útok môže vyzerať nasledovne: \begin{itemize} %--- Item \item Zvolíme si náhodne správy X $_\textrm{\tiny 1}$...X $_\textrm{\tiny n}$. %--- Item \item Pre zvolené správy vypočítame h(X $_\textrm{\tiny 1}$)...h(X $_\textrm{\tiny n}$). %--- Item \item Výsledné hashe porovnávame, ak nájdeme dvojicu zhodných, kolízia bola nájdená. \end{itemize} \noindent Jedným z~prvých aplikovaných útokov bol Yuvalov narodeninový útok, ktorý je možné využiť na každú bezkľúčovú hashovaciu funkciu a jeho zložitosť je O(2 $^\textrm{\tiny m/2}$) v~závislosti na dĺžke výstupu n. \begin{itemize} %--- Item \item Na začiatku zvolíme správu X $_\textrm{\tiny 1}$ a podvodnú správu X $_\textrm{\tiny 2}$ %--- Item \item Generujeme t = 2 $^\textrm{\tiny n/2}$ správ X' $_\textrm{\tiny 1}$, ktoré sú drobnými modifikáciami správy X $_\textrm{\tiny 1}$. %--- Item \item Každú z~upravených správ hashujeme zvolenou funkciou h a získané hodnoty ukladáme, aby bolo neskôr možné medzi nimi rýchlo vyhľadávať (v~čase O(t)). %--- Item \item Pre správu X $_\textrm{\tiny 2}$ generujeme jej drobné modifikácie X' $_\textrm{\tiny 2}$, ich hashe h(X' $_\textrm{\tiny 2}$) a postupne porovnávame s~hodnotou X' $_\textrm{\tiny 1}$. Postup opakujeme, pokiaľ nieje nájdená zhoda, ktorú očakávame po porovnaní t hodnôt X' $_\textrm{\tiny 2}$ (porovnávanie s~hodnotami uloženými v~tabuľke vyžaduje konštantný čas). %--- Item \item Výsledkom útoku sú hodnoty X' $_\textrm{\tiny 1}$ a X' $_\textrm{\tiny 2}$ získané drobnými úpravami X $_\textrm{\tiny 1}$ a X $_\textrm{\tiny 2}$, pre ktoré platí h(X' $_\textrm{\tiny 1}$) = h(X' $_\textrm{\tiny 2}$) \end{itemize} \noindent % ------------------------ % Section \section{Rainbow tables} \label{sec0303}\hypertarget{sec0303}{}% Útok využíva metódu time-memory trade-off, prvý raz publikovanú Martinom Hellmanom \docbooktolatexcite{hellmantimememory}{}, ktorý popísal jej aplikáciu v~oblasti kryptografie. Metóda nám poskytuje možnosť urýchlenia kryptoanalýzy vďaka vopred predpočítaným hodnotám uloženým v~pamäti. Rainbow table (v~podkapitole označená ako tabuľka) je tabuľka predpočítaných hodnôt, určená na získanie inverzie k~hashu (získanie plaintextu z~hodnoty hashu), v~praxi zvyčajne využívaná ako rozšírenie slovníkového útoku pri lámaní hesiel, za prekpokladu obmedzenej dĺžky a využitia znakov v~hesle. Útočník si vytvára tabuľku, kam ukladá vypočítané hashe pre bežne používané, alebo krátke heslá, plaintext k~týmto heslám s~usporiadaním podľa hashov. Následne po jeho získaní sme schopní tento hash v~krátkom čase v~tabuľke vyhľadať a tak k~nemu získať zodpovedajúce heslo. Problém nastáva v~prípade útoku na dlhšie heslá, čo spôsobuje nárast veľkosti tabuľky a zároveň nárast potrebnej pamäti. Hellman taktiež zaviedol používanie redukčnej funkcie r, ktorá v~našom prípade mapuje hashe na plaintext hodnoty. Spôsob mapovania, a teda spôsob tvorby hesla z~hashu je závislý na tom, pre aké heslá má útočník snahu tabuľku skonštruovať (výskyt a počet písmen, číslic, dĺžka hesla, atď.). Redukčná funkcia nám tým zaručuje výskyt hesiel s~určenou charakteristikou. S~pomocou tejto funkcie sa následne do tabuľky ukladá plaintext, na ktorý opakovane aplikujeme hashovaciu funkciu h a funkciu r. Ako sme uviedli, rainbow table obsahuje plaintext heslá a ich hashe. Tie sú usporiadané vo formáte tzv. Rainbow chains (reťazcov), pričom každý z~reťazcov začína heslom a pokračuje hashom získaným aplikáciou funkcie h na túto hodnotu. Nasleduje znovu heslo, získané aplikáciou funkcie r na predchádzajúci hash. Takto vytvorený reťazec je zakončený hashom, pričom v~tabuľke je v~skutočnosti uvedené len prvé heslo a posledný získaný hash. V~prípade, že sa rozhodneme v~každej iterácii redukcie použiť inú r funkciu, zabránime vzniku kolízií, ktoré spôsobujú zmenšenie spektra pokrytých hesiel a môžu znehodnotiť celé reťazce v~tabuľke. Je možné tiež využiť niekoľko tabuliek namiesto jedinej, s~tým, že r funkcie sa budú líšiť medzi jednotlivými tabuľkami. Medzi ďalšie vylepšenia algoritmu patria napríklad tzv. rozlišovacie body (distinguished points). Spôsob, ktorý publikoval Rivest v~praxi výrazne znižuje počet potrebných prístupov do pamäti počas kryptoanalýzy. Tieto \glqq body\textquotedblleft{} reprezentujú kľúče, ktoré udávajú istú spoločnú vlastnosť (napríklad prvých 10 bitov je 0). Následne počas prístupu do pamäti kľúč vyhľadávame len v~prípade, že danú vlastnosť splňuje. Vyhľadávanie v~tabuľke môže vyzerať nasledovne: \begin{enumerate} %--- Item \item Je zadaný hash h(x), pre ktorý hľadáme inverziu. Začíname prehľadávaním posledného stĺpca tabuľky, ktorý obsahuje finálne hodnoty reťazcov (hashe) a hľadáme zhodu. %--- Item \item V~prípade, že zhodu hashov neobjavíme, používame redukčnú funkciu a jej výsledok hashujeme (ak sme pri konštrukcii tabuľky používali viac r funkcií, začíname tou poslednou). Znovu porovnávame hodnotu s~posledným stĺpcom tabuľky. %--- Item \item V~prípade objavenia zhody vieme, že nami hľadané heslo je súčasťou reťazcu v~ktorom sme na zhodu narazili. Vezmeme prvú hodnotu reťazcu a opakovane aplikujeme hashovaciu a redukčnú funkciu. Akonáhle je hash lokalizovaný, hľadaným heslom je predchádzajúca hodnota v~reťazci. \end{enumerate} \noindent Nasledujúci obrázok prebraný z~\docbooktolatexcite{rainbowwiki}{} ukazuje úspešné nájdenie hesla k~zadanému hashu: % figure ------------------------------------------------------ \begin{figure}[hbt] \hypertarget{obr0303}{}% \begin{center} {{\includegraphics[scale=0.85]{Rainbow_table2}}\hypertarget{id316061}{}% \label{id316061} } {{\caption[{Vyhľadávanie hesla v~rainbow table s~konečným úspechom}]{{{Vyhľadávanie hesla v~rainbow table s~konečným úspechom}}}\label{obr0303}}} \end{center} \end{figure} Účinnou obranou proti útokom pomocou Rainbow tables je solenie hesiel. Soľ je dodatočná informácia, náhodne generovaná a pridávaná ku heslu pred tým, než je hashované. Dostatočne veľká a unikátna hodnota soli pre každého užívateľa nám zabezpečuje, že i rovnaké heslá budú mať rozdielne hodnoty hashov. % ------------------------ % Section \section{Praktický útok na MD5} \label{sec0304}\hypertarget{sec0304}{}% Prvý z~praktických útokov na funkciu MD5 bol publikovaný tímom X. Wangovej \docbooktolatexcite{wangmd5}{}. Ide o~kolízny útok schopný rádovo v~čase jednej hodiny nájsť 2 správy s~dĺžkou 1024 bitov, produkujúce totožný hash. Prvým krokom, ktorý zaberá väčšinu času útoku je nájdenie dvoch polspráv o~dĺžke 512 bitov M $_\textrm{\tiny 1}$ a M $_\textrm{\tiny 2}$, medzi ktorými je nasledujúci vzťah: \begin{itemize} %--- Item \item M $_\textrm{\tiny 2}$ = M $_\textrm{\tiny 1}$ + C $_\textrm{\tiny 1}$, kde C $_\textrm{\tiny 1}$ je 512 bitová konštanta, ktorá obsahuje tri zo šestnástich 32-bitových podblokov s~nenulovou hodnotou. \end{itemize} \noindent Následne hľadáme polsprávy N $_\textrm{\tiny 1}$ a N $_\textrm{\tiny 2}$, čo sme schopní dosiahnuť v~čase od 15 sekúnd do 5 minút: \begin{itemize} %--- Item \item N $_\textrm{\tiny 2}$ = N $_\textrm{\tiny 1}$ + C $_\textrm{\tiny 2}$, kde C $_\textrm{\tiny 2}$ je 512 bitová konštanta, ktorá obsahuje tri zo šestnástich 32-bitových podblokov s~nenulovou hodnotou a nie je zhodná s~N $_\textrm{\tiny 1}$. \end{itemize} \noindent Vo výsledku tak dostávame správy (M $_\textrm{\tiny 1}$,N $_\textrm{\tiny 1}$) a (M $_\textrm{\tiny 2}$,N $_\textrm{\tiny 2}$), pre ktoré platí h(M $_\textrm{\tiny 1}$,N $_\textrm{\tiny 1}$) = h(M $_\textrm{\tiny 2}$,N $_\textrm{\tiny 2}$). Útok bol publikovaný s~použitím pôvodných iniciálnych hodnôt hashovacej funkcie. Autori však uvádzajú, že funguje nezávisle na ich hodnotách. Princíp generovania správ M a N však zverejnený nebol. O~rok neskôr bol publikovaný útok V. Klímy, ktorý vychádzal z~predchádzajúceho útoku a tiež z~analýz, ktoré sa pokúšali odhaliť algoritmus generovania správ M a N. Útočník postupoval podobným spôsobom hľadania polspráv M $_\textrm{\tiny 1,2}$ a N $_\textrm{\tiny 1,2}$, pričom prvá fáza prebiehala 1000-2000 krát rýchlejšie, druhá ale 2-80 krát pomalšie, autor tak uvádza 3-6 krát vyššiu rýchlosť vyhľadania kolízie ako u~prechádzajúcej metódy \docbooktolatexcite{klima}{}. % ------------------------------------------------------------- % Chapter Použité nástroje a evolúcia % ------------------------------------------------------------- \chapter{Použité nástroje a evolúcia} \label{ch04}\hypertarget{ch04}{}% V~nasledujúcej časti práce popisujeme spôsob testovania kandidátnych funkcií, v~krátkosti vysvetľujeme evolučné algoritmy a ich využitie spolu s~evolučným obvodom v~aplikácii použitej pri testovaní. % ------------------------ % Section \section{Evolučné a genetické algoritmy} \label{sec0401}\hypertarget{sec0401}{}% Evolučné algoritmy (Evolutionary algorithms) sú algoritmy, ktoré využívajú spôsoby založené na genetike a evolúcii, zvyčajne na riešenie zložitých matematických a iných úloh. Existuje viacero podtried evolučných algoritmov, ktoré sa líšia v~závislosti na riešenom probléme a implementačných detailoch. V~našom prípade ide o~tzv. Genetické algoritmy (Genetic algorithms), kde riešený problém a jeho dáta reprezentujeme vo forme znakových reťazcov, väčšinou v~binárnej forme. Genetický algoritmus počas svojho behu pracuje s~populáciou reťazcov (reprezentuje jedno z~možných riešení zadaného problému), ktorá obsahuje množstvo individuálnych jedincov. Evolúcia na začiatku pracuje s~náhodne vygenerovanými jedincami, pri ktorých nás zaujíma ich fitness (hodnota, ktorá reprezentuje úspešnosť daného jedinca). Na základe hodnôt fitness vyberáme vhodných jedincov, modifikujeme pomocou rôznych techník ako sú napríklad kríženie (crossover) a mutácia (mutation) so snahou priblížiť sa správnemu riešeniu. Takto vzníká nová populácia, ktorá bude následne použitá v~ďalšej iterácii algoritmu. Beh algoritmu je ukončený v~prípade, že bolo vygenerované maximálne množstvo generácií alebo bola dosiahnutá uspokojivá hodnota fitness. Použité pojmy vysvetľujeme nasledovne: \begin{itemize} %--- Item \item Kríženie (crossover) - proces kríženia vyžaduje minimálne 2 jedincov, označovaných tiež ako rodičov (parents), z~ktorých následne vznikajú potomkovia (children). Kríženie si zvolí spoločný bod u~obidvoch rodičov, následne všetky dáta za zvoleným bodom zamení, čím vznikajú potomkovia. % figure ------------------------------------------------------ \begin{figure}[hbt] \hypertarget{obr0401a}{}% \begin{center} {{\includegraphics[scale=0.75]{crossover}}\hypertarget{id316309}{}% \label{id316309} } {{\caption[{Proces kríženia jedincov}]{{{Proces kríženia jedincov}}}\label{obr0401a}}} \end{center} \end{figure} Ilustrovaný príklad zobrazuje tzv. jednobodové kríženie. Existuje množstvo ďalších spôsobov, ako napríklad dvojbodové kríženie (u~rodičov volíme 2 body, ktoré ohraničujú zamenené dáta), alebo spôsob, kde pre každého rodiča volíme bod kríženia osobitne, čím vznikajú potomkovia rozličnej dĺžky. %--- Item \item Mutácia (mutation) - mutácia v~genetických algoritmoch poskytuje možnosť zmeny bitov v~reťazci na hodnotu opačnú ako bola pôvodná. Pravdepodobnosť zmeny každého z~bitov býva zvyčajne 1/n, kde n je dĺžka bitovej postupnosti. % figure ------------------------------------------------------ \begin{figure}[hbt] \hypertarget{obr0401b}{}% \begin{center} {{\includegraphics[scale=0.8]{mutation}}\hypertarget{id316355}{}% \label{id316355} } {{\caption[{Proces mutácie u~jedinca}]{{{Proces mutácie u~jedinca}}}\label{obr0401b}}} \end{center} \end{figure} %--- Item \item Fitness - funkcia fitness je spôsob ohodnotenia výstupu genetického algoritmu. Jej úlohou je určiť, ako sa daná generácia približuje skutočnému riešeniu, na základe čoho následne vyberáme vhodných jedincov, z~ktorých formujeme ďalšiu generáciu algoritmu. \end{itemize} \noindent % ------------------------ % Section \section{Evolučné obvody, Sensor Security Simulator} \label{sec0402}\hypertarget{sec0402}{}% Aplikácia Sensor Security Simulator \docbooktolatexcite{sensorsim}{} bola pôvodne vyvinutá Masarykovou Univerzitou na riešenie vybraných problémov bezpečnosti IT. Kód je napísaný v~jazyku C++ pre operačné systém MS Windows 2000/XP/Vista. Jednou z~implementovaných funkcionalít je simulácia evolučného obvodu, založeného na princípe evolučného algoritmu s~použitím knižnice GAlib \docbooktolatexcite{galib}{}. Obvod tvorí vstupná vrstva, výstupná vrstva a niekoľko interných vrstiev. Vrstvy sú medzi sebou prepojené pomocou konektorov, ktoré ovplyvňujú veľkosť vstupu z~predchádzajúcej vrstvy. Uzly v~obvode predstavujú funkcie, ktoré môžu byť nasledovné: \begin{itemize} %--- Item \item FNC\_NOP - žiadna operácia, funkcia predá na výstup rovnakú hodnotu ako získala. %--- Item \item FNC\_OR - vykoná sa operácia disjunkcie na vstupoch %--- Item \item FNC\_AND - vykoná sa operácia konjunkcie na vstupoch %--- Item \item FNC\_CONST - na výstup vraciame konštantu %--- Item \item FNC\_XOR - vykoná na vstupoch operáciu exkluzívnej disjunkcie %--- Item \item FNC\_NOR - vykoná na vstupoch negáciu logického súčtu (disjunkcie) %--- Item \item FNC\_NAND - vykoná na vstupoch negáciu logického súčinu (konjunkcie) %--- Item \item FNC\_ROTL - vykoná na vstupoch operáciu bitového posunu vľavo %--- Item \item FNC\_ROTR - vykoná na vstupoch operáciu bitového posunu vpravo %--- Item \item FNC\_BITSELECTOR - vykoná na vstupoch operáciu bitového súčinu %--- Item \item FNC\_SUM - vykoná na vstupoch operáciu súčtu %--- Item \item FNC\_SUBS - vykoná na vstupoch operáciu rozdielu %--- Item \item FNC\_ADD - vykoná na vstupoch operáciu súčtu, navyše oproti funkcii FNC\_SUM pripočíta hodnotu uzlu na rovnakej pozícii z~prechádzajúcej vrstvy %--- Item \item FNC\_MULT - vykoná na vstupoch operáciu násobenia %--- Item \item FNC\_DIV - funkcia celočíselne delí hodnotu uzlu na rovnakej pozícii z~prechádzajúcej vrstvy hodnotami pripojených uzlov %--- Item \item FNC\_READ - funkcia podľa hodnoty uzlu na rovnakej pozícii z~prechádzajúcej vrstvy prečíta jeden zo vstupov obvodu \end{itemize} \noindent Evolúcia ako bola uvedená v~\hyperlink{sec0401}{{[4.1]}} sa dostáva na úroveň obvodov, čím zachovávame všetky techniky využívané evolúciou. Tie fungujú nasledovne: \begin{itemize} %--- Item \item Kríženie - v~pozícii jedincov (rodičov, potomkov) figurujú celé obvody. Proces prebieha na úrovni vrstiev, čo v~tomto prípade značí ako vrstvy s~funkciami, tak vrstvy s~prepojením. Po zvolení bodu kríženia (výber jednej z~vrstiev) sú všetky nasledujúce vymenené medzi rodičmi. %--- Item \item Mutácia - prebieha na úrovni prepojení aj na úrovni funkcií vo vrstve (funkciu nahradíme inou, náhodne vybranou, pridáme/odoberieme prepojenie). %--- Item \item Fitness - ako bolo spomenuté pri evolučných algoritmoch, úlohou funkcie fitness je ohodnotiť úspešnosť poskytnutého (možného) riešenia. Riešenie úlohy v~našom prípade predstavuje obvod. \end{itemize} \noindent Ako príklad uvádzame jednoduchý obvod s~piatimi vrstvami a počtom uzlov na vrstvu 4. Skutočne však algoritmus generoval 16 vstupov pre obvod, z~ktorých sú v~tomto stave obvodu zapojené len 3 (vstup 0, 1 a 7). Hodnota každého z~uzlov je výsledkom funkcie uvedenej v~grafe, ktorá je interne reprezentovaná hodnotou 0-255. V~závislosti na funkcii je potom možnosť privádzať uzlu na vstup jednu/niekoľko hodnôt z~predchádzajúcej vrstvy. % figure ------------------------------------------------------ \begin{figure}[hbt] \hypertarget{obr0402}{}% \begin{center} {{\includegraphics[scale=0.5]{eac}}\hypertarget{id316615}{}% \label{id316615} } {{\caption[{Príklad evolučného obvodu}]{{{Príklad evolučného obvodu}}}\label{obr0402}}} \end{center} \end{figure} % ------------------------ % Section \section{Náhodné dáta} \label{sec0403}\hypertarget{sec0403}{}% Aplikácia primárne využíva náhodný generátor postavený na báze funkcie MD5. Výhodou je v~tomto prípade spolu s~používaním tzv. seedu \label{fn040301}\begingroup\catcode`\#=12\footnote{ Náhodné číslo, generované na začiatku každého behu aplikácie. Po vygenerovaní pomocou neho inicializujeme náhodný generátor aplikácie. }\endgroup\docbooktolatexmakefootnoteref{fn040301} fakt, že vďaka znalosti seedu sme schopní každé náhodné rozhodnutie algoritmu reprodukovať a tak spustiť vybrané testy znovu. Uvedený generátor vďaka svojej závislosti na seede a tiež vďaka faktu, že je postavený práve na hashovacej funkcii nieje v~niektorých prípadoch využiteľný. Jedná sa napr. o~nutnosť použitia skutočne náhodných dát, ktoré dodávame ako vstup SHA-3 kandidátom. Pre tento účel využívame dáta generované kvantovým generátorom dostupným na \docbooktolatexcite{rng}{}. Aplikácia má prístup ku 100 súborom o~celkovej veľkosti 1,5GB binárnych dát. % ------------------------ % Section \section{Implementácia kandidátnych funkcií} \label{sec0404}\hypertarget{sec0404}{}% Pred samotným spúšťaním testov bolo nutné pôvodnú aplikáciu Sensor Security Simulator upraviť, aby bolo neskôr možné spúštať testy pomocou nástroja BOINC na počítačoch v~LaBAK-u \label{fn040401}\begingroup\catcode`\#=12\footnote{ Laboratoř bezpečnosti a aplikované kryptografie. }\endgroup\docbooktolatexmakefootnoteref{fn040401}. Hlavná funkcionalita bola oddelená od GUI spolu s~úpravami kódu, ktoré boli vykonané z~dôvodu prípravy aplikácie na platformovú nezávislosť, kedže ju bolo možné používať len na systémoch MS Windows. Súťaž o~novú hashovaciu funkciu bola vypísaná 2. novembra 2007 Americkým štandardizačným inštitútom \label{fn040402}\begingroup\catcode`\#=12\footnote{ National Institute of Standards and Technology. }\endgroup\docbooktolatexmakefootnoteref{fn040402}, na konci ktorej výherný algoritmus ponesie pomenovanie SHA-3. Prihlásených algoritmov bolo spolu 64, z~ktorých 51 kandidátov postúpilo do prvého kola a 14 ich bolo vybraných do druhého kola. Kandidátne funkcie boli prístupné kryptografickej komunite a na základe spätnej väzby bolo zvolených 5 finalistov. Podmienky na zapojenie sa zahŕňali napríklad použitie jazyka C (podľa normy ANSI C) a tiež implementáciu predpísaného API \docbooktolatexcite{sha3interface}{}. Rozhranie popisuje dátové typy a štruktúry používané pri ukladaní potrebných hodnôt počas hashovania, ako aj 4 funkcie určené na výpočet hashu. Podľa rozhrania tiež musí každá z~kandidátnych funkcií podporovať výstupné hashe o~dĺžke 224, 256, 384 a 512 bitov, poprípade aj iné, ktoré už niesú nutné. Do testovacej aplikácie sme implementovali všetky algoritmy od 1. kola (s~výnimkou dvoch, ktoré upresňujeme v~podkapitole \hyperlink{sec0405}{{[4.5]}}), čo značí 51 funkcií. Použité boli najnovšie dostupné verzie, tzn. verzie pre posledné kolo, ktorého sa daný algoritmus zúčastnil. V~kóde sú používané pomocou spoločného rozhrania (mierne modifikované pôvodné rozhranie), čo znamenalo nutnosť pre každú z~nich vytvoriť triedu, ktorá rozhranie implementuje. Funkciu si užívateľ vyberie zmenou hodnoty v~konfiguračnom súbore. % ------------------------ % Section \section{Priebeh testov} \label{sec0405}\hypertarget{sec0405}{}% Ako sme uviedli v~\hyperlink{sec0404}{{[4.4]}}, počet algoritmov v~prvom výberovom kole bol 51. Počas ich implementácie sme vynechali 2, z~dôvodu veľkosti zdrojových súborov a rýchlosti (tie presahovali v~jednom z~prípadov 100 MB). Následne sme pre testovanie vybrali algoritmy, kde bolo možné obmedziť počet rund, keďže testy primárne prebiehali na oslabených variantách, čo vo výsledku znamenalo 34 algoritmov upravených na testovanie. Nastavenie zvoleného počtu rund prebieha taktiež z~konfiguračného súboru. Využívali sme funkcie s~výstupom dĺžky 256 bitov. Testovanie prebiehalo simultánne na 15 strojoch Mefitas pomocou aplikácie BOINC určenej na distribuované výpočty. Keďže počet aktuálne spracovaných úloh pre jednotlivé počítače je prideľovaný pre každé jadro procesoru, bolo možné pracovať (podľa aktuálnej dostupnosti) maximálne na 30-tich výsledkoch naraz. Priebeh každého z~testov vyzerá nasledovne: \begin{itemize} %--- Item \item Vytvárame populáciu niekoľkých obvodov, inicializujeme a nastavujeme podľa hodnôt v~konfiguračnom súbore, ustanovujeme (popr. načítame) seed pre náhodné generátory, generujeme prvé testovacie vektory. %--- Item \item Evaluácia - ohodnotenie výsledkov, ktoré nám obvody vrátia. %--- Item \item Evolúcia - využívame techniky evolúcie (mutácia, kríženie), formujeme obvody nové. Následne opakujeme hodnotenie a porovnávame výsledky s~predchádzajúcimi (sú výsledky lepšie?). Tento krok spolu s~minulým opakujeme pre každú generáciu, pričom v~istých intervaloch generujeme aj nové testovacie vektory. %--- Item \item Finálne hodnotenie - na záver dostáva obvod nové dáta, na ktorých sa predtým nikdy neučil. Vyberáme najlepšieho jedinca, ktorého hodnotíme. Túto výslednú hodnotu používame pri prezentácii výsledkov testov. \end{itemize} \noindent Okrem spomínanej finálnej hodnoty fitness program generuje niekoľko priebežných výstupov v~rôznych formátoch, ktoré nás taktiež zaujímajú: \begin{itemize} %--- Item \item EAC\_fitnessProgress.txt - každých niekoľko (napr. 10) generácií ukladáme hodnoty ako sú maximálna a priemerná fitness, celkové maximum dosiahnuté počas behu. Maximálne a priemerné hodnoty fitness ukladáme tiež v~odobitných súboroch, ktoré je možné použiť na generovanie grafov a pod. %--- Item \item EAC\_circuit.dot - formát dot je používaný pri generovaní grafov obvodu, vytvárané sú tiež samostatné súbory pre každé nové nájdené maximum hodnoty fitness. %--- Item \item EAC\_circuit.txt - textová reprezentácia obvodu, generujeme podobne ako u~.dot formátu. %--- Item \item EAC\_circuit.bin - súbor s~uloženým obvodom v~binárnej forme, využívaný v~prípade, že chceme pokračovať s~už získaným obvodom. %--- Item \item EAC\_circuit.c - zdrojový súbor obvodu, ktorý je možné skompilovať. \end{itemize} \noindent % ------------------------------------------------------------- % Chapter Spôsoby testovania a výsledky % ------------------------------------------------------------- \chapter{Spôsoby testovania a výsledky} \label{ch05}\hypertarget{ch05}{}% % ------------------------ % Section \section{Rozlišovanie pri obmedzenom vstupe funkcie} \label{sec0501}\hypertarget{sec0501}{}% Úlohou obvodu bolo správne odhadnúť pôvod dodaných dát a tak správne rozlišovať medzi dvomi rôznymi typmi vstupných dát. Hashovacej funkcii dodávame vstup so známou štruktúrou. \subsection{Testovacie vektory} \label{sec050101}\hypertarget{sec050101}{}% Generovanie sady testovacích vektorov začína výberom a prípravou náhodných dát z~kvantového generátoru \hyperlink{sec0403}{{[4.3]}}. Každú sadu tvorí niekoľko sto až tisíc vektorov, v~závislosti na nastavení, pričom pri generovaní novej sady je znovu náhodne zvolený jeden zo súborov s~dátami. Následne prebieha výber, ktorý z~2 typov vektorov budeme generovať. Presná postupnosť generovania nieje nijak určená, ale algoritmus po vygenerovaní celej sady zaručuje vyvážený pomer medzi vektormi. Tieto vektory sú: \begin{itemize} %--- Item \item Náhodné dáta -- pseudo-náhodné dáta, načítané priamo z~vybraného súboru. Dáta boli načítavané po blokoch, ktorých dĺžka závisí na dĺžke výstupných hashov. %--- Item \item Hash -- výstupy hashovacej funkcie. Vstupy funkcie tvorili bloky rovnakej dĺžky ako výstupný hash, nie však ľubovoľné. Tvorili sme bloky vo formáte: {\texttt{{XYXYXYXY.\dbz{}.\dbz{}.\dbz{}.\dbz{}.\dbz{}XY}}}, tzn. bloky, ktoré tvorili 2 opakujúce sa byty. \end{itemize} \noindent Každý testovací vektor počas jeho generovania označujeme, či sa jedná o~náhodné dáta (označené hodnotou 0xff hexadecimálne), alebo o~výstup hashovacej funkcie (označené hodnotou 0x00). Výsledná sada môže následne vyzerať ako: \begin{Verbatim}[fontsize=\small] 1. <473029411faa6733015ed10158d115c9; 0x00> 2. <98d603fa3425c6ed06be541806ce22c1; 0x00> 3. 4. ..... ..... 200. \end{Verbatim} \subsection{Vstupy obvodu} \label{sec050102}\hypertarget{sec050102}{}% Ako vstup poskytujeme evolučnému obvodu prvú časť vektoru, tzn. náhodné dáta, alebo hash. Z~toho dôvodu sa veľkosť vstupnej vrstvy obvodu nastavuje podľa dĺžky týchto dát. \subsection{Výstupy obvodu} \label{sec050103}\hypertarget{sec050103}{}% Očakávaným výstupom obvodu je určenie, či na vstupe boli náhodné dáta, alebo hash. Na tento účel postačuje výstupná vrstva tvorená jediným uzlom. \subsection{Spôsoby predikcie} \label{sec050104}\hypertarget{sec050104}{}% Ako sme uviedli, očakávané výstupy obvodu sú v~tomto prípade 2 možné hodnoty, z~ktorých jedna reprezentuje hash, druhá náhodné dáta. Aj prípade nastavenia výstupnej vrstvy obvodu na minimum, tzn. 1 uzol (reprezentovaný premennou typu unsigned char) dostávame výstupné hodnoty v~rozsahu 0-255, ktoré musíme nejakým spôsobom porovnať so \glqq správnym\textquotedblleft{} výstupom a určiť mieru zhody. Naskytli sa nám tak 2 možné prediktory: \begin{itemize} %--- Item \item Predikcia na základe číselnej hodnoty - výstupy v~rozsahu 0-127 sú považované za hash, na druhej strane tie v~rozsahu 128-255 sú považované za náhodné dáta. %--- Item \item Predikcia na základe hammingovej váhy -- hodnoty s~váhou 0-4 reprezentovali hash, s~váhou 5-8 reprezentovali náhodné dáta. \end{itemize} \noindent Prvými testmi, realizovanými na funkcii MD5 uvedených v~\hyperlink{sec050107}{{[5.1.7]}} sa ukázal lepší prvý spôsob predikcie. Počas predikcie počítame počet správne predikovaných hodnôt (správne určenie o~aký vstup sa jednalo) a celkový počet predikcií. Hodnotu fitness nám následne určuje vzťah {\texttt{{fit = predikovane\_\dbz{}spravne /\dbz{} predikovane\_\dbz{}celkovo}}}. Hodnota funkcie fitness je v~tomto prípade určená podielom správne odhadnutých výstupov ku celkovému počtu vykonaných odhadov (1*200, tzn. jedna odhadovaná hodnota na každý z~200 testovacích vektorov v~sade). \subsection{Rozšírenie vstupov obvodu} \label{sec050105}\hypertarget{sec050105}{}% Ďalšou z~možností testovania bolo poskytnúť obvodu viac dát na rozhodovanie, napríklad 256 bytov na rozdiel od pôvodných X bytov (pre SHA-3 32 bytov). Skutočná veľkosť vstupnej vrstvy obvodu sa však nemení, preto má obvod na začiatku dostupných pôvodných X bytov. Plnú dĺžku využívame prostredníctvom funkcie FNC\_READ \hyperlink{sec0402}{{[4.2]}}, ktorá podľa vstupu z~predchádzajúcej vrstvy obvodu v~rozsahu 0-255 načíta hodnotu vstupnej vrstvy na danej pozícii ako zobrazuje \hyperlink{fncread}{Obrázok {\ref{fncread}}}. Samotné testovacie vektory, konkrétne hodnoty vstupnej vrstvy obvodu sú z~dôvodu pevnej dĺžky výstupu hashovacej funkcie tvorené zreťazením niekoľkých hashov \hyperlink{256b}{Obrázok {\ref{256b}}}. V~prípade náhodných dát postupujeme rovnakým spôsobom. \subsection{Nastavenie evolúcie a obvodu} \label{sec050106}\hypertarget{sec050106}{}% % table ------------------------------------------------------ \begin{table}[htb] \begin{center}% \hypertarget{id317153}{}% \begin{minipage}{\linewidth} \begin{tabular}{|c|c|} \hline {{Veľkosť populácie}} & {{20}} \tabularnewline \hline {{Počet testovacích vektorov}} & {{200}} \tabularnewline \hline {{Pravdepodobnosť mutácie}} & {{0,05}} \tabularnewline \hline {{Pravdepodobnosť kríženia}} & {{0,5}} \tabularnewline \hline {{Počet generácií evolúcie}} & {{100000}} \tabularnewline \hline {{Počet vrstiev v~obvode}} & {{8}} \tabularnewline \hline {{Veľkosť vstupnej vrstvy obvodu}} & {{32}} \tabularnewline \hline {{Veľkosť vnútorných vrstiev obvodu}} & {{16}} \tabularnewline \hline {{Veľkosť výstupnej vrstvy obvodu}} & {{1}} \tabularnewline \hline {{Počet konektorov na vrstvu}} & {{16}} \tabularnewline \hline {{Frekvencia zmeny testovacích vektorov}} & {{po 10 generáciách \label{fn05010601}\begingroup\catcode`\#=12\footnote{ Obvod potrebuje istý čas na učenie sa, no na druhej strane je schopný z~jednej sady testovacích vektorov získať len obmedzené znalosti. Najlepšie sa po prvých testoch na MD5 prejavila verzia s~10-generačnými zmenami. }\endgroup\docbooktolatexmakefootnoteref{fn05010601}}} \tabularnewline \hline \end{tabular} \end{minipage} {{\caption{Nastavenie evolúcie a obvodu}\label{id317153}}} \end{center} \end{table} \subsection{Testy na funkcii MD5} \label{sec050107}\hypertarget{sec050107}{}% Prvé testy vykonané na funkcii MD5 nám pomohli rozhodnúť pri niektorých z~nastavení evolučného obvodu, ako napríklad výber prediktoru pri rozlišovaní, frekvenciu zmeny testovacích vektorov a pod. Ako prvý uvádzame rozdiel medzi prediktormi. Vychádzali sme z~porovnania 4 a 5 rundovej verzie pri zmene testovacích vektorov po 10 generáciách a výslednej hodnoty pre 15 behov každej z~nich (výsledky dosiahnuté po 100000 generáciách). % table ------------------------------------------------------ \begin{table}[htb] \begin{center}% \hypertarget{id317309}{}% \begin{tabular}{|c|c|c|} \hline {{}} & {{4 rundy}} & {{5 rund}} \tabularnewline \hline {{Prediktor č. 1}} & {{0,879}} & {{0,6663}} \tabularnewline \hline {{Prediktor č. 2}} & {{0,826}} & {{0,6177}} \tabularnewline \hline \end{tabular} {{\caption{Nastavenie evolúcie a obvodu}\label{id317309}}} \end{center} \end{table} Jeden z~úspešných behov 4-rundovej verzie pri zmene testovacích vektorov (skrátene TV) po 10 generáciách a použití prediktoru č.1 vykresľujeme \hyperlink{add1}{Obrázok {\ref{add1}}} a tiež pre prediktor č.2, kde sa obvod učí zhruba po rovnakom čase, priemerne ale nedosahuje výsledky ako prvá verzia predikcie \hyperlink{add2}{Obrázok {\ref{add2}}}. Z~grafov vidíme, že krivka hodnôt fitness nemá čisto rastúcu tendenciu. Toto je spôsobené hlavne zmenou TV v~pravidelných intervaloch, kedy fitness poklesne. Následne sme testovali jednotlivé kombinácie nastavení počtu rund a zmeny TV. Hodnoty v~tabuľkách značia priemernú hodnotu výslednej fitness všetkých 10 behov testu. Výsledky pre rundy 1-3 neuvádzame, MD5 pri tomto nastavení generuje istú časť výstupného hashu konštantnú, obvod ju preto rozpozná behom niekoľkých generácií. Výsledky poslúžili k~faktu, že sme pri testovaní SHA-3 kandidátov zvolili zmenu TV každých 10 generácií. % table ------------------------------------------------------ \begin{table}[htb] \begin{center}% \hypertarget{id317389}{}% \begin{tabular}{|c|c|c|c|} \hline {{}} & {{1}} & {{10}} & {{100}} \tabularnewline \hline {{4 rundy (200000 gen.)}} & {{0,8}} & {{0,99}} & {{0,9475}} \tabularnewline \hline {{5 rund (200000 gen.)}} & {{0,5}} & {{0,83}} & {{0,6525}} \tabularnewline \hline {{6 rund (200000 gen.)}} & {{0,51}} & {{0,4917}} & {{0,4883}} \tabularnewline \hline {{7 rund (200000 gen.)}} & {{0,5}} & {{0,52}} & {{0,4883}} \tabularnewline \hline \end{tabular} {{\caption{Nastavenie evolúcie a obvodu}\label{id317389}}} \end{center} \end{table} Posledným z~testov bolo zistenie vplyvu väčších vstupných dát na priebeh evolúcie, ako sme uvádzali v~\hyperlink{sec050105}{{[5.1.5]}}. Nasleduje porovnanie výsledkov pre 4 a 5 rundovú verziu so zmenou po 10 a 100 generáciách. Verzia s~pôvodných 16B vstupom nepoužíva funkciu READ: % table ------------------------------------------------------ \begin{table}[htb] \begin{center}% \hypertarget{id317496}{}% \begin{tabular}{|c|c|c|} \hline {{}} & {{10}} & {{100}} \tabularnewline \hline {{4 rundy, 16B}} & {{0,99}} & {{0,975}} \tabularnewline \hline {{4 rundy, 256B}} & {{0,842}} & {{0,992}} \tabularnewline \hline {{5 rund, 16B}} & {{0,83}} & {{0,6525}} \tabularnewline \hline {{5 rund, 256B}} & {{0,6815}} & {{0,567}} \tabularnewline \hline \end{tabular} {{\caption{Nastavenie evolúcie a obvodu}\label{id317496}}} \end{center} \end{table} Z~výsledkov pre 4 rundovú verziu sa pre 256 vstupov javí vhodné meniť TV menej frekventovane (po 100 generáciách), než u~prvej varianty. Po zvýšení rund na 5 však nedostávame lepšie výsledky, práve naopak, varianta sa prejavila horšie ako pri vstupe dĺžkou 16 bytov, preto sme tento spôsob ďalej nepoužívali. \subsection{Výsledky pre SHA-3 kandidátov} \label{sec050108}\hypertarget{sec050108}{}% Zvolený počet rund u~funkcií uvádzame pri každej z~nich v~zátvorke. Niektoré z~funkcíí nemalo zmysel testovať s~počtom rund menším, než sme zvolili a to z~dôvodu konštantnej časti výstupu, popr. celého výstupu. Uvedená hodnota určuje priemer finálnych hodnôt fitness \hyperlink{sec0405}{{[4.5]}} z~10tich behov testu. Z~výsledkov je zjavné, že vo väčšine prípadov obvod žiadne závislosti vo vstupných hashoch neodhalil, preto sa výsledky pohybujú okolo hodnoty 0,5, tzn. aj na konci evolúcie rozlišujeme medzi hashom a náhodnými dátami s~50\% úspechom. % tabular ------------------------------------------------------ \begin{center} \label{id317608}\hypertarget{id317608}{}% \begin{minipage}{\linewidth} \begin{tabular}{|c|c|c|c|c|c|c|} \hline {{Abacus(1)}} & {{Arirang(4)}} & {{Aurora(1)}} & {{Blake(1)}} & {{Blender(1)}} & {{BMW \label{fn05010801}\begingroup\catcode`\#=12\footnote{ Blue Midnight Wish }\endgroup\docbooktolatexmakefootnoteref{fn05010801}(1)}} & {{Boole(1)}} \tabularnewline \hline {{0,5195}} & {{0,4935}} & {{0,506}} & {{0,4935}} & {{0,503}} & {{0,4895}} & {{0,4965}} \tabularnewline \hline \end{tabular} \end{minipage} \end{center} % tabular ------------------------------------------------------ \begin{center} \label{id317679}\hypertarget{id317679}{}% \begin{minipage}{\linewidth} \begin{tabular}{|c|c|c|c|c|c|c|} \hline {{Cheetah(2)}} & {{CHI(1)}} & {{Crunch(34)}} & {{Cubehash(1)}} & {{DCH(1)}} & {{DSHA(5) \label{fn05010802}\begingroup\catcode`\#=12\footnote{ Dynamic SHA }\endgroup\docbooktolatexmakefootnoteref{fn05010802}}} & {{DSHA 2(1)}} \tabularnewline \hline {{0,4845}} & {{0,5045}} & {{0,516}} & {{0,4905}} & {{0,5145}} & {{0,7815}} & {{0,5135}} \tabularnewline \hline \end{tabular} \end{minipage} \end{center} % tabular ------------------------------------------------------ \begin{center} \label{id317750}\hypertarget{id317750}{}% \begin{tabular}{|c|c|c|c|c|c|c|} \hline {{ECHO(1)}} & {{ESSENCE(1)}} & {{Fugue(1)}} & {{Grostl(1)}} & {{Hamsi(1)}} & {{JH(7)}} & {{Lesamnta(3)}} \tabularnewline \hline {{0,497}} & {{0,481}} & {{0,496}} & {{0,529}} & {{0,502}} & {{0,563}} & {{0,606}} \tabularnewline \hline \end{tabular} \end{center} % tabular ------------------------------------------------------ \begin{center} \label{id317813}\hypertarget{id317813}{}% \begin{tabular}{|c|c|c|c|c|c|c|} \hline {{Luffa(8)}} & {{Lux(1)}} & {{MD6(7)}} & {{MeshHash(1)}} & {{SANDstorm(3)}} & {{Sarmal(1)}} & {{SHAvite3(2)}} \tabularnewline \hline {{0,531}} & {{0,498}} & {{0,4975}} & {{0,501}} & {{0,5325}} & {{0,5375}} & {{0,4865}} \tabularnewline \hline \end{tabular} \end{center} % table ------------------------------------------------------ \begin{table}[htb] \begin{center}% \hypertarget{id317876}{}% \begin{tabular}{|c|c|c|c|c|c|c|} \hline {{SIMD(1)}} & {{Tangle(7)}} & {{Tib3(1)}} & {{Twister(7)}} & {{WaMM(2)}} & {{Waterfall(1)}} \tabularnewline \hline {{0,482}} & {{0,4945}} & {{0,5335}} & {{0,504}} & {{0,4985}} & {{0,5085}} \tabularnewline \hline \end{tabular} {{\caption{Výsledky pre SHA-3 kandidátov}\label{id317876}}} \end{center} \end{table} Jediný úspech zaznamenal náš postup v~prípade funkcie Dynamic SHA, kde správne rozlišoval hash od náhodných dát v~priemere s~úspešnosťou 78\%. V~testoch sme preto pokračovali s~postupným zvyšovaním počtu rund na 8 (zo 16) a tiež zvýšeným počtom generácií na 200000. Nasledujúca tabuľka zobrazuje výsledky z~jednotlivých behov pre každé nastavenie: % table ------------------------------------------------------ \begin{table}[htb] \begin{center}% \hypertarget{id317944}{}% \begin{tabular}{|c|c|c|c|c|} \hline {{}} & {{5 rund}} & {{6 rund}} & {{7 rund}} & {{8 rund}} \tabularnewline \hline {{1.}} & {{0,755}} & {{0,78}} & {{0,895}} & {{0,535}} \tabularnewline \hline {{2.}} & {{0,79}} & {{0,87}} & {{0,74}} & {{0,55}} \tabularnewline \hline {{3.}} & {{0,79}} & {{0,8}} & {{0,845}} & {{0,5}} \tabularnewline \hline {{4.}} & {{0,755}} & {{0,805}} & {{0,825}} & {{0,5}} \tabularnewline \hline {{5.}} & {{0,765}} & {{0,75}} & {{0,795}} & {{0,515}} \tabularnewline \hline {{6.}} & {{0,855}} & {{0,815}} & {{0,73}} & {{0,47}} \tabularnewline \hline {{7.}} & {{0,785}} & {{0,75}} & {{0,785}} & {{0,505}} \tabularnewline \hline {{8.}} & {{0,785}} & {{0,79}} & {{0,725}} & {{0,52}} \tabularnewline \hline {{9.}} & {{0,765}} & {{0,79}} & {{0,785}} & {{0,535}} \tabularnewline \hline {{10.}} & {{0,77}} & {{0,75}} & {{0,74}} & {{0,52}} \tabularnewline \hline \end{tabular} {{\caption{Testy na Dynamic SHA}\label{id317944}}} \end{center} \end{table} Pre verziu s~5 rundami uvádzame behy číslo 2 a neskôr aj 3. Hodnoty grafu zobrazujú maximálne hodnoty fitness namerané pri hodnotení, ktoré sme opakovali každých 10 generácií. Prvé skokové vylepšenie evolúcie pozorujeme už po 750 generáciách, pričom neskôr nasledujú ďalšie 2. V~druhom grafe vidíme detail na prvých 3000 generácií behu. % figure ------------------------------------------------------ \begin{figure}[hbt] \hypertarget{dynsha_5r}{}% \begin{center} {{\includegraphics[scale=0.45]{bestfitgraph1_5r}}\hypertarget{id318187}{}% \label{id318187} } {{\caption[{2. beh pre 5 rundovú verziu}]{{{2. beh pre 5 rundovú verziu}}}\label{dynsha_5r}}} \end{center} \end{figure} % figure ------------------------------------------------------ \begin{figure}[hbt] \hypertarget{dynsha_5r_detail}{}% \begin{center} {{\includegraphics[scale=0.45]{bestfitgraph1_5r_detail}}\hypertarget{id318212}{}% \label{id318212} } {{\caption[{Detail 2. behu pre 5 rundovú verziu}]{{{Detail 2. behu pre 5 rundovú verziu}}}\label{dynsha_5r_detail}}} \end{center} \end{figure} Následne pre porovnanie uvádzame nájdené obvody počas behu. Prvý z~nich je obvod pre fitness 0,53 \hyperlink{add3}{Obrázok {\ref{add3}}}, ktorý odhaduje vstupy len s~priemerným úspechom. Obvod je z~z~rannej fázy evolúcie, keďže využíva len niekoľko z~prvých vrstiev. Druhý obvod \hyperlink{add4}{Obrázok {\ref{add4}}} je už lepší, pričom využíva viac vstupov než predchádzajúca verzia. Finálna verzia obvodu potom vyzerá nasledovne \hyperlink{add5}{Obrázok {\ref{add5}}}. Beh číslo 3, ktorý skončil s~rovnakým výsledkom uvádzame ako druhý príklad. Zo začiatku evolúcie prebieha podobne ako v~predchádzajúcom behu, s~rýchlym skokom, neskôr však pozorujeme pomalý nárast evolúcie (od generácie 15000 do 60000). % figure ------------------------------------------------------ \begin{figure}[hbt] \hypertarget{dynsha_5r2}{}% \begin{center} {{\includegraphics[scale=0.45]{bestfitgraph2_5r}}\hypertarget{id318265}{}% \label{id318265} } {{\caption[{Detail 3. behu pre 5 rundovú verziu}]{{{Detail 3. behu pre 5 rundovú verziu}}}\label{dynsha_5r2}}} \end{center} \end{figure} % figure ------------------------------------------------------ \begin{figure}[hbt] \hypertarget{dynsha_5r_detail2}{}% \begin{center} {{\includegraphics[scale=0.45]{bestfitgraph2_5r_detail}}\hypertarget{id318291}{}% \label{id318291} } {{\caption[{Detail 3. behu pre 5 rundovú verziu}]{{{Detail 3. behu pre 5 rundovú verziu}}}\label{dynsha_5r_detail2}}} \end{center} \end{figure} Nasledujúce grafy zobrazujú najlepšie behy pre 6 a 7 rundovú verziu funkcie Dynamic SHA. Pre lepšie porovnanie s~predchádzajúcou verziou je uvedený tiež graf pre prvú polovicu behu. Evolúcia prebieha vo všetkých troch prípadoch podobne, s~rýchlym rastom na začiatku, obvodu sa však ani pri zvýšení počtu generácií na dvojnásobok nepodarilo naučiť viac % figure ------------------------------------------------------ \begin{figure}[hbt] \hypertarget{dynsha_6r}{}% \begin{center} {{\includegraphics[scale=0.45]{bestfitgraph_6r}}\hypertarget{id318325}{}% \label{id318325} } {{\caption[{2. beh pre 6 rundovú verziu}]{{{2. beh pre 6 rundovú verziu}}}\label{dynsha_6r}}} \end{center} \end{figure} % figure ------------------------------------------------------ \begin{figure}[hbt] \hypertarget{dynsha_6r_detail}{}% \begin{center} {{\includegraphics[scale=0.45]{bestfitgraph_6r_detail}}\hypertarget{id318351}{}% \label{id318351} } {{\caption[{Prvých 100000 generácií behu pre 6 rundovú verziu}]{{{Prvých 100000 generácií behu pre 6 rundovú verziu}}}\label{dynsha_6r_detail}}} \end{center} \end{figure} % figure ------------------------------------------------------ \begin{figure}[hbt] \hypertarget{dynsha_7r}{}% \begin{center} {{\includegraphics[scale=0.45]{bestfitgraph_7r}}\hypertarget{id318377}{}% \label{id318377} } {{\caption[{2. beh pre 7 rundovú verziu}]{{{2. beh pre 7 rundovú verziu}}}\label{dynsha_7r}}} \end{center} \end{figure} % figure ------------------------------------------------------ \begin{figure}[hbt] \hypertarget{dynsha_7r_detail}{}% \begin{center} {{\includegraphics[scale=0.45]{bestfitgraph_7r_detail}}\hypertarget{id318403}{}% \label{id318403} } {{\caption[{Prvých 100000 generácií behu pre 7 rundovú verziu}]{{{Prvých 100000 generácií behu pre 7 rundovú verziu}}}\label{dynsha_7r_detail}}} \end{center} \end{figure} Obvody pre uvedené 6 \hyperlink{add6}{Obrázok {\ref{add6}}} a 7 \hyperlink{add6}{Obrázok {\ref{add6}}} rundové behy sú podobné, než u~5 rundovej verzie. Môžeme si napr. všimnúť, že na výsledok obvodu nemajú skoro žiadny vplyv vstupy 0-12, z~ktorých väčsina nieje do obvodu zapojená. % ------------------------ % Section \section{Odhad obmedzenej časti vstupných dát} \label{sec0502}\hypertarget{sec0502}{}% Úlohou obvodu je zo znalosti hashov odhadovať informácie o~malej časti vstupného bloku. \subsection{Testovacie vektory} \label{sec050201}\hypertarget{sec050201}{}% Sada testovacích vektorov je na rozdiel od minulého prípadu tvorená jedným typom dát. Prvou časťou vektoru je plaintext, pričom ho tvoria dáta načítané z~kvantového generátoru \hyperlink{sec0403}{{[4.3]}}. Takto načítaný blok náhodných dát je hashovaný vybranou funkciou, ktorej výstup tvorí druhú časť testovacieho vektoru. \subsection{Vstupy obvodu} \label{sec050202}\hypertarget{sec050202}{}% Na vstup obvodu privádzame výsledné hashe. Rovnako ako v~predchádzajúcich testoch používame 256 bitovú dĺžku hashov. \subsection{Výstupy obvodu} \label{sec050203}\hypertarget{sec050203}{}% Očakávaným výstupom je odhad informácií o~malej časti vstupu hashovacej funkcie, ktorý daný hash vyprodukoval. Používali sme vrstvu o~veľkosti 2 uzlov a teda odhadovali informácie o~prvých dvoch bytoch vstupného bloku funkcie. \subsection{Spôsob predikcie} \label{sec050204}\hypertarget{sec050204}{}% Spôsob predikcie je založený na porovnávaní hammingovej váhy a to nasledovne: \begin{itemize} %--- Item \item Výpočet hammingovej váhy pre aktuálne porovnávané byty. %--- Item \item Pred porovnaním výsledkov vypočítame zhodu na body a to nasledovným spôsobom: {\texttt{{points = NUM\_\dbz{}BITS -\dbz{} abs(\dbz{}predictWeight -\dbz{} correctWeight)\dbz{}}}} (konštanta NUM\_BITS značí počet bitov na 1 byte, teda 8, predictWeight a correctWeight ukladajú hammingovu váhu). Takto vypočítaná hodnota poskytuje obvodu presnejšie informácie o~zlepšení/zhoršení evolúcie, keďže obvod nedostáva len informáciu, či hammingovu váhu trafil, ale tiež vie, nakoľko sa k~zhode v~prípade neúspechu priblížil. Hodnotu \glqq points\textquotedblleft{} následne delíme počtom vsetkých predikovaných bytov a dostávame výstupnú hodnotu fitness. \end{itemize} \noindent \subsection{Nastavenie evolúcie a obvodu} \label{sec050205}\hypertarget{sec050205}{}% % table ------------------------------------------------------ \begin{table}[htb] \begin{center}% \hypertarget{id318572}{}% \begin{tabular}{|c|c|} \hline {{Veľkosť populácie}} & {{20}} \tabularnewline \hline {{Počet testovacích vektorov}} & {{200}} \tabularnewline \hline {{Pravdepodobnosť mutácie}} & {{0,05}} \tabularnewline \hline {{Pravdepodobnosť kríženia}} & {{0,5}} \tabularnewline \hline {{Počet generácií evolúcie}} & {{100000}} \tabularnewline \hline {{Počet vrstiev v~obvode}} & {{8}} \tabularnewline \hline {{Veľkosť vstupnej vrstvy obvodu}} & {{32}} \tabularnewline \hline {{Veľkosť vnútorných vrstiev obvodu}} & {{16}} \tabularnewline \hline {{Veľkosť výstupnej vrstvy obvodu}} & {{2}} \tabularnewline \hline {{Počet konektorov na vrstvu}} & {{16}} \tabularnewline \hline {{Frekvencia zmeny testovacích vektorov}} & {{po 10 generáciách}} \tabularnewline \hline \end{tabular} {{\caption{Nastavenie evolúcie a obvodu}\label{id318572}}} \end{center} \end{table} \subsection{Výsledky pre SHA-3 kandidátov} \label{sec050206}\hypertarget{sec050206}{}% Počet rund sme zvolili rovnako ako pri predchádzajúcich testoch. Uvedená hodnota určuje priemer finálnych hodnôt fitness \hyperlink{sec0405}{{[4.5]}} z~10tich behov testu, pričom reprezentuje mieru zhody ako sme uviedli v~XrefId[??]. Výsledky sa pohybujú priemerne okolo hodnoty 3,5; čo značí v~priemere 3 až 4 správne odhadnuté bity na jeden byte. Hodnota je nižšia ako priemer, čo značí, že sa obvod nebol schopný pri daných podmienkach učiť a nezískal znalosti pre lepší odhad vstupov. % tabular ------------------------------------------------------ \begin{center} \label{id318730}\hypertarget{id318730}{}% \begin{minipage}{\linewidth} \begin{tabular}{|c|c|c|c|c|c|c|} \hline {{Abacus(1)}} & {{Arirang(4)}} & {{Aurora(1)}} & {{Blake(1)}} & {{Blender(1)}} & {{BMW \label{fn05010801}\begingroup\catcode`\#=12\footnote{ Blue Midnight Wish }\endgroup\docbooktolatexmakefootnoteref{fn05010801}(1)}} & {{Boole(1)}} \tabularnewline \hline {{3,58975}} & {{3,587875}} & {{3,600875}} & {{3,5945}} & {{3,5945}} & {{3,598375}} & {{3,60525}} \tabularnewline \hline \end{tabular} \end{minipage} \end{center} % tabular ------------------------------------------------------ \begin{center} \label{id318803}\hypertarget{id318803}{}% \begin{minipage}{\linewidth} \begin{tabular}{|c|c|c|c|c|c|c|} \hline {{Cheetah(2)}} & {{CHI(1)}} & {{Crunch(34)}} & {{Cubehash(1)}} & {{DCH(1)}} & {{DSHA(5) \label{fn05010802}\begingroup\catcode`\#=12\footnote{ Dynamic SHA }\endgroup\docbooktolatexmakefootnoteref{fn05010802}}} & {{DSHA 2(1)}} \tabularnewline \hline {{3,599625}} & {{3,60825}} & {{3,592}} & {{3,57225}} & {{3,599625}} & {{3,579875}} & {{3,584625}} \tabularnewline \hline \end{tabular} \end{minipage} \end{center} % tabular ------------------------------------------------------ \begin{center} \label{id318875}\hypertarget{id318875}{}% \begin{tabular}{|c|c|c|c|c|c|c|} \hline {{ECHO(1)}} & {{ESSENCE(1)}} & {{Fugue(1)}} & {{Grostl(1)}} & {{Hamsi(1)}} & {{JH(7)}} & {{Lesamnta(3)}} \tabularnewline \hline {{3,594625}} & {{3,5645}} & {{3,5915}} & {{3,596125}} & {{3,58025}} & {{3,578125}} & {{3,60625}} \tabularnewline \hline \end{tabular} \end{center} % tabular ------------------------------------------------------ \begin{center} \label{id318938}\hypertarget{id318938}{}% \begin{tabular}{|c|c|c|c|c|c|c|} \hline {{Luffa(8)}} & {{Lux(1)}} & {{MD6(7)}} & {{MeshHash(1)}} & {{SANDstorm(3)}} & {{Sarmal(1)}} & {{SHAvite3(2)}} \tabularnewline \hline {{3,609125}} & {{3,57828125}} & {{3,5959375}} & {{3,5996875}} & {{3,59109375}} & {{3,58625}} & {{3,58265625}} \tabularnewline \hline \end{tabular} \end{center} % table ------------------------------------------------------ \begin{table}[htb] \begin{center}% \hypertarget{id319000}{}% \begin{tabular}{|c|c|c|c|c|c|c|} \hline {{SIMD(1)}} & {{Tangle(7)}} & {{Tib3(1)}} & {{Twister(7)}} & {{WaMM(2)}} & {{Waterfall(1)}} \tabularnewline \hline {{3,59265625}} & {{3,5940625}} & {{3,5765625}} & {{3,61921875}} & {{3,6}} & {{3,58640625}} \tabularnewline \hline \end{tabular} {{\caption{Výsledky pre SHA-3 kandidátov}\label{id319000}}} \end{center} \end{table} % ------------------------ % Section \section{Avalanche efekt} \label{sec0503}\hypertarget{sec0503}{}% Úlohou obvodu je hľadať a porovnávať vstupné bloky, pre ktoré bude vo výsledných hodnotách hashov rozdielnych viac, resp. menej bitov, než je očakávaná hodnota 1/2. \subsection{Testovacie vektory} \label{sec050301}\hypertarget{sec050301}{}% Testovacie vektory sú v~tomto prípade tvorené 16 bytovými blokmi náhodných dát. Dáta využívame ako vstup pre evolučný obvod, tiež ich ale potrebujeme vo fáze predikcie. \subsection{Vstupy obvodu} \label{sec050302}\hypertarget{sec050302}{}% Obvodu na vstup dodávame testovacie vektory v~podobe blokov náhodných dát. Veľkosť vstupnej vrstvy obvodu je prispôsobená dĺžke týchto dát. \subsection{Výstupy obvodu} \label{sec050303}\hypertarget{sec050303}{}% Očakávaným výstupom obvodu je blok dát rovnakej dĺžky ako pôvodný vstup. Hľadáme však také bloky, pre ktoré sa budú výstupné hodnoty hashov odlišovať vo väčšom/menšom počte bitov, ako je 1/2. \subsection{Spôsob predikcie} \label{sec050304}\hypertarget{sec050304}{}% Spôsob predikcie je založený na porovnávaní bitov medzi výstupnými hashmi testovanej funkcie. Hashovanie dát je však nutné vykonávať až ne úrovni prediktoru, pretože testovacie vektory aj obvod pracujú s~dátami nehashovanými. Predikcia prebieha v~nasledujúcich krokoch: \begin{itemize} %--- Item \item Porovnanie vstupných a výstupných dát obvodu - nutnosť porovnania vychádza z~faktu, že algoritmus v~krátkom čase nájde ideálny obvod, ktorý bude len vracať nezmenené vstupné dáta na výstup, čím samozrejme vzniká pri porovnaní hashov kolízia na celej dĺžke. Takto vytvoreným obvodom automaticky priraďujeme hodnotu fitness 0. %--- Item \item Hashovanie vstupu a výstupu obvodu zvolenou kandidátnou funkciou. %--- Item \item Porovnanie získaných hashov z~minulého kroku na celej ich dĺžke. Jedná sa o~porovnanie každého z~bitov. Hodnotu fitness tak počítame ako {\texttt{{fitness = pocet\_\dbz{}zhodnych\_\dbz{}bitov /\dbz{} dlzka\_\dbz{}hashu}}} (využitie hashov o~dĺžke 256 bitov zostáva). \end{itemize} \noindent \subsection{Nastavenie evolúcie a obvodu} \label{sec050305}\hypertarget{sec050305}{}% Na rozdiel od minulých testov sme nastavenia mierne upravili, keďže ide o~priemerné hodnoty fitness počas celého behu. Snažíme sa preto obvodu dodávať väčšie množstvo rôznych dát (zníženie počtu a častejšie generovanie nových testovacích vektorov). % table ------------------------------------------------------ \begin{table}[htb] \begin{center}% \hypertarget{id319207}{}% \begin{tabular}{|c|c|} \hline {{Veľkosť populácie}} & {{20}} \tabularnewline \hline {{Počet testovacích vektorov}} & {{100}} \tabularnewline \hline {{Pravdepodobnosť mutácie}} & {{0,05}} \tabularnewline \hline {{Pravdepodobnosť kríženia}} & {{0,5}} \tabularnewline \hline {{Počet generácií evolúcie}} & {{100000}} \tabularnewline \hline {{Počet vrstiev v~obvode}} & {{8}} \tabularnewline \hline {{Veľkosť vstupnej vrstvy obvodu}} & {{16}} \tabularnewline \hline {{Veľkosť vnútorných vrstiev obvodu}} & {{16}} \tabularnewline \hline {{Veľkosť výstupnej vrstvy obvodu}} & {{16}} \tabularnewline \hline {{Počet konektorov na vrstvu}} & {{16}} \tabularnewline \hline {{Frekvencia zmeny testovacích vektorov}} & {{každú generáciu}} \tabularnewline \hline \end{tabular} {{\caption{Nastavenie evolúcie a obvodu}\label{id319207}}} \end{center} \end{table} \subsection{Výsledky pre SHA-3 kandidátov} \label{sec050306}\hypertarget{sec050306}{}% Počet rund je volený rovnako, ako pri predchádzajúcich testoch. V~tomto prípade sme pri priemerovaní výsledkov nepoužívali finálnu hodnotu fitness, ale brali sme do úvahy priemerné hodnoty počas celého behu. Ako ukazujú výsledky, funkcie sa pohybujú okolo predpokladanej hodnoty 0,5; pričom číslo nižšie ako 0,5 znamená väčší počet zmenených bitov v~priemere. % tabular ------------------------------------------------------ \begin{center} \label{id319352}\hypertarget{id319352}{}% \begin{minipage}{\linewidth} \begin{tabular}{|c|c|c|c|c|c|c|} \hline {{Abacus(1)}} & {{Arirang(4)}} & {{Aurora(1)}} & {{Blake(1)}} & {{Blender(1)}} & {{BMW \label{fn05010801}\begingroup\catcode`\#=12\footnote{ Blue Midnight Wish }\endgroup\docbooktolatexmakefootnoteref{fn05010801}(1)}} & {{Boole(1)}} \tabularnewline \hline {{0.476563}} & {{0.464844}} & {{0.527344}} & {{0.464844}} & {{0.449219}} & {{0.46875}} & {{0.519531}} \tabularnewline \hline \end{tabular} \end{minipage} \end{center} % tabular ------------------------------------------------------ \begin{center} \label{id319424}\hypertarget{id319424}{}% \begin{minipage}{\linewidth} \begin{tabular}{|c|c|c|c|c|c|c|} \hline {{Cheetah(2)}} & {{CHI(1)}} & {{Crunch(34)}} & {{Cubehash(1)}} & {{DCH(1)}} & {{DSHA(5) \label{fn05010802}\begingroup\catcode`\#=12\footnote{ Dynamic SHA }\endgroup\docbooktolatexmakefootnoteref{fn05010802}}} & {{DSHA 2(1)}} \tabularnewline \hline {{0.480469}} & {{0.472656}} & {{0.429688}} & {{0.503906}} & {{0.484375}} & {{0.507813}} & {{0.488281}} \tabularnewline \hline \end{tabular} \end{minipage} \end{center} % tabular ------------------------------------------------------ \begin{center} \label{id319496}\hypertarget{id319496}{}% \begin{tabular}{|c|c|c|c|c|c|c|} \hline {{ECHO(1)}} & {{ESSENCE(1)}} & {{Fugue(1)}} & {{Grostl(1)}} & {{Hamsi(1)}} & {{JH(7)}} & {{Lesamnta(3)}} \tabularnewline \hline {{0.46875}} & {{0.464844}} & {{0.484375}} & {{0.511719}} & {{0.445313}} & {{0.484375}} & {{0.507813}} \tabularnewline \hline \end{tabular} \end{center} % tabular ------------------------------------------------------ \begin{center} \label{id319558}\hypertarget{id319558}{}% \begin{tabular}{|c|c|c|c|c|c|c|} \hline {{Luffa(8)}} & {{Lux(1)}} & {{MD6(7)}} & {{MeshHash(1)}} & {{SANDstorm(3)}} & {{Sarmal(1)}} & {{SHAvite3(2)}} \tabularnewline \hline {{0.460938}} & {{0.476563}} & {{0.46875}} & {{0.480469}} & {{0.46875}} & {{0.472656}} & {{0.476563}} \tabularnewline \hline \end{tabular} \end{center} % table ------------------------------------------------------ \begin{table}[htb] \begin{center}% \hypertarget{id319621}{}% \begin{tabular}{|c|c|c|c|c|c|c|} \hline {{SIMD(1)}} & {{Tangle(7)}} & {{Tib3(1)}} & {{Twister(7)}} & {{WaMM(2)}} & {{Waterfall(1)}} \tabularnewline \hline {{0.488281}} & {{0.488281}} & {{0.429688}} & {{0.464844}} & {{0.476563}} & {{0.445313}} \tabularnewline \hline \end{tabular} {{\caption{Výsledky pre SHA-3 kandidátov}\label{id319621}}} \end{center} \end{table} % ------------------------------------------------------------- % Chapter Záver % ------------------------------------------------------------- \chapter{Záver} \label{ch06}\hypertarget{ch06}{}% Cielom práce bolo niekoľkými spôsobmi otestovať kandidátne hashovacie funkcie SHA-3 so zameraním na vyhľadávanie závislostí vo výstupných hashoch. V~teoretickej časti rozoberáme hashovacie funkcie, ich rozdelenie a funkcionalitu. Popisujeme základné typy útokov na jednotlivé druhy funkcií a tiež prakticky vykonané útoky na používaných funkciách s~uvedenými príkladmi. Praktická časť spájala prípravu testovacej aplikácie, implementáciu testovaných funkcií a tiež testy. Použité nastavenia obvodu vychádzali z~už známeho chovania a testov, na ktoré bola aplikácia využívaná v~minulosti, ale aj z~vlastných testov, vykonaných na hashovacej funkcii MD5. Tiež musíme poznamenať, že zvolené nastavenia pravdepodobne nie sú jediné vhodné pre hľadanie riešenia nášho problému. Výsledky práce sme sústredili na popis vykonaných testov a tiež výsledkov fitness, ktoré nám poskytujú prehľad o~odolnosti zapojených kandidátov voči našim útokom. Najlepšie výsledky sme dosiahli pri funkcii DynamicSHA, kde sa prvou metódou testovania odhalila závislosť, aj keď len pri obmedzenom počte rund. Najviac perspektívne sa preto prejavil prvý testovací spôsob so známou štruktúrou vstupnej správy. Vďaka tejto práci som nadobudol množstvo nových znalostí, či už sa jedná o~znalosti v~problematike hashovacích funkcií a útokov na ne, tiež aj genetických algoritmov, s~ktorými som sa stretol poprvý raz. Tiež som si uvedomil nutnosť správnej funkcionality a odolnosti hashovacích funkcií voči útokom, ktoré tak poskytujú dostatočnú bezpečnosť vo všetkých oblastich využitia, kde je potrebná. \newcommand{\dbappendix}[1]{\chapter{#1}}% % ------------------------------------------------------------- % Appendices start here % ------------------------------------------------------------- \appendix % ------------------------------------------------------------- % appendix: Grafy % ------------------------------------------------------------- \dbappendix{Grafy} \label{id319728}\hypertarget{id319728}{}% % figure ------------------------------------------------------ \begin{figure}[hbt] \hypertarget{fncread}{}% \begin{center} {{\includegraphics[scale=0.6]{fncread}}\hypertarget{id319745}{}% \label{id319745} } {{\caption[{Funkcia FNC\_READ}]{{{Funkcia FNC\_READ}}}\label{fncread}}} \end{center} \end{figure} % figure ------------------------------------------------------ \begin{figure}[hbt] \hypertarget{256b}{}% \begin{center} {{\includegraphics[scale=0.6]{256bhash}}\hypertarget{id319771}{}% \label{id319771} } {{\caption[{Tvorba testovacieho vektoru o~dĺžke 256 bytov}]{{{Tvorba testovacieho vektoru o~dĺžke 256 bytov}}}\label{256b}}} \end{center} \end{figure} % figure ------------------------------------------------------ \begin{figure}[hbt] \hypertarget{add1}{}% \begin{center} {{\includegraphics[scale=0.6]{MD5_byte_4r_10chng}}\hypertarget{id319796}{}% \label{id319796} } {{\caption[{MD5, prediktor č. 1}]{{{MD5, prediktor č. 1}}}\label{add1}}} \end{center} \end{figure} % figure ------------------------------------------------------ \begin{figure}[hbt] \hypertarget{add2}{}% \begin{center} {{\includegraphics[scale=0.6]{MD5_byte_5r}}\hypertarget{id319821}{}% \label{id319821} } {{\caption[{MD5, prediktor č. 2}]{{{MD5, prediktor č. 2}}}\label{add2}}} \end{center} \end{figure} % figure ------------------------------------------------------ \begin{figure}[hbt] \hypertarget{add3}{}% \begin{center} {{\includegraphics[scale=0.3]{eac1_5r_053dot}}\hypertarget{id319846}{}% \label{id319846} } {{\caption[{Dynamic SHA, 5 rund, obvod pre hodnotu fitness 0,53}]{{{Dynamic SHA, 5 rund, obvod pre hodnotu fitness 0,53}}}\label{add3}}} \end{center} \end{figure} % figure ------------------------------------------------------ \begin{figure}[hbt] \hypertarget{add4}{}% \begin{center} {{\includegraphics[scale=0.35]{eac1_5r_068dot}}\hypertarget{id319870}{}% \label{id319870} } {{\caption[{Dynamic SHA, 5 rund, obvode pre hodnotu fitness 0,68}]{{{Dynamic SHA, 5 rund, obvode pre hodnotu fitness 0,68}}}\label{add4}}} \end{center} \end{figure} % figure ------------------------------------------------------ \begin{figure}[hbt] \hypertarget{add5}{}% \begin{center} {{\includegraphics[scale=0.4]{eac1_5r_full}}\hypertarget{id319896}{}% \label{id319896} } {{\caption[{Dynamic SHA, 5 rund, obvod na konci evolúcie}]{{{Dynamic SHA, 5 rund, obvod na konci evolúcie}}}\label{add5}}} \end{center} \end{figure} % figure ------------------------------------------------------ \begin{figure}[hbt] \hypertarget{add6}{}% \begin{center} {{\includegraphics[scale=0.35]{eac_6r}}\hypertarget{id319922}{}% \label{id319922} } {{\caption[{Dynamic SHA, 6 rund, obvod na konci evolúcie}]{{{Dynamic SHA, 6 rund, obvod na konci evolúcie}}}\label{add6}}} \end{center} \end{figure} % figure ------------------------------------------------------ \begin{figure}[hbt] \hypertarget{add7}{}% \begin{center} {{\includegraphics[scale=0.35]{eac_7r}}\hypertarget{id319948}{}% \label{id319948} } {{\caption[{Dynamic SHA, 7 rund, obvod na konci evolúcie}]{{{Dynamic SHA, 7 rund, obvod na konci evolúcie}}}\label{add7}}} \end{center} \end{figure} % ------------------------------------------- % % Bibliography - chapter % % ------------------------------------------- \begin{thebibliography}{123}\hypertarget{id319963}{} % ............. biblioentry \bibitem{Kerckhoff}\docbooktolatexbibaux{id320265}{Kerckhoff} \hypertarget{id320265}{} Kerckhoff, A.: \emph{Kerckhoffov princíp}, {\textless}\url{http://artofinfosec.com/335/crypto-kerckhoffs-principle/}{\textgreater} . % ............. biblioentry \bibitem{Pavlovic}\docbooktolatexbibaux{id320231}{Pavlovic} \hypertarget{id320231}{} Pavlovič, J.: \emph{Návod k~modulu xslt2}, 2006, {\textless}\url{http://www.fi.muni.cz/~xpavlov/xml/}{\textgreater} . % ............. biblioentry \bibitem{PreneelPhd}\docbooktolatexbibaux{id320297}{PreneelPhd} \hypertarget{id320297}{} Preneel, B.: \emph{Analysis and Design of Cryptographic Hash Functions}, , Február 1993, , {\textless}\url{http://homes.esat.kuleuven.be/~preneel/phd_preneel_feb1993.pdf}{\textgreater} . % ............. biblioentry \bibitem{SHA1 collision}\docbooktolatexbibaux{id320168}{SHA1 collision} \hypertarget{id320168}{} Wang, X. a Yin, Y. a Yu, H.: \emph{Finding Collisions in the Full SHA-1}, Springer Berlin / Heidelberg, 2005, 978-3-540-28114-6, {\textless}\url{http://dx.doi.org/10.1007/11535218_2}{\textgreater} . % ............. biblioentry \bibitem{cbcchaining}\docbooktolatexbibaux{id320404}{cbcchaining} \hypertarget{id320404}{} Bellare, M. a Kilian, J. a Rogaway, P.: \emph{The Security of the Cipher Block Chaining Message Authentication Code}, Journal of Computer and System Sciences, Volume 61, Issue 3, December 2000, {\textless}\url{http://www.sciencedirect.com/science/article/pii/S002200009991694X}{\textgreater} . % ............. biblioentry \bibitem{galib}\docbooktolatexbibaux{id320004}{galib} \hypertarget{id320004}{} \emph{GAlib, A~C++ Library of Genetic Algorithm Components}, {\textless}\url{http://lancet.mit.edu/ga/}{\textgreater} . % ............. biblioentry \bibitem{graphviz}\docbooktolatexbibaux{id319965}{graphviz} \hypertarget{id319965}{} \emph{Graphviz - Graph Visualization Software, domovská stránka}, {\textless}\url{http://www.graphviz.org/}{\textgreater} . % ............. biblioentry \bibitem{hellmantimememory}\docbooktolatexbibaux{id320070}{hellmantimememory} \hypertarget{id320070}{} Hellman, M.: \emph{A~Cryptanalytic Time-Memory Trade-Off}, IEEE transactions on Information Theory, Vol. 26, 1980, {\textless}\url{http://caislab.kaist.ac.kr/lecture/2010/spring/cs548/basic/B01.pdf}{\textgreater} . % ............. biblioentry \bibitem{klima}\docbooktolatexbibaux{id320340}{klima} \hypertarget{id320340}{} Klíma, V.: \emph{Finding MD5 Collisions -- a Toy For a Notebook}, , 5. Marec 2005, , {\textless}\url{http://cryptography.hyperlink.cz/md5/MD5_collisions.pdf}{\textgreater} . % ............. biblioentry \bibitem{rainbowwiki}\docbooktolatexbibaux{id320041}{rainbowwiki} \hypertarget{id320041}{} \emph{Príklad útoku pomocou Rainbow tables}, Wikipedia, 2006, {\textless}\url{http://en.wikipedia.org/wiki/File:Rainbow_table2.svg}{\textgreater} . % ............. biblioentry \bibitem{rng}\docbooktolatexbibaux{id320383}{rng} \hypertarget{id320383}{} \emph{Quantum Random Generator Service}, , {\textless}\url{https://qrng.physik.hu-berlin.de/}{\textgreater} . % ............. biblioentry \bibitem{sensorsim}\docbooktolatexbibaux{id320022}{sensorsim} \hypertarget{id320022}{} \emph{Sensor Security Simulator (S3), domovská stránka}, {\textless}\url{http://www.fi.muni.cz/~xsvenda/s3.html}{\textgreater} . % ............. biblioentry \bibitem{sha3interface}\docbooktolatexbibaux{id319984}{sha3interface} \hypertarget{id319984}{} \emph{ANSI C Cryptographic API Profile for SHA-3 Candidate Algorithm Submissions}, {\textless}\url{http://csrc.nist.gov/groups/ST/hash/documents/SHA3-C-API.pdf}{\textgreater} . % ............. biblioentry \bibitem{uowhf}\docbooktolatexbibaux{id320113}{uowhf} \hypertarget{id320113}{} Naor, M. a Yung, M.: \emph{Universal One-Way Hash Functions and their Cryptographic Applications}, Proceedings of the twenty-first annual ACM symposium on Theory of computing, Seattle, Washington, United States , 1989, 0-89791-307-8, {\textless}\url{http://doi.acm.org/10.1145/73007.73011}{\textgreater} . % ............. biblioentry \bibitem{wangmd5}\docbooktolatexbibaux{id320467}{wangmd5} \hypertarget{id320467}{} Wang, X. a Feng, D. a Lai, X. a Yu, H.: \emph{Collisions for Hash Functions MD4, MD5, HAVAL-128 and RIPEMD}, 17. August 2004, {\textless}\url{http://eprint.iacr.org/2004/199.pdf}{\textgreater} . \end{thebibliography} \addcontentsline{toc}{chapter}{Bibliografia} \end{document}