640 \end{frame}} |
640 \end{frame}} |
641 |
641 |
642 |
642 |
643 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
643 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
644 |
644 |
645 |
645 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
646 \mode<presentation>{ |
|
647 \begin{frame}[c] |
|
648 \frametitle{One More Thing} |
|
649 |
|
650 \begin{itemize} |
|
651 \item I arrived at King's last year |
|
652 \item Maxime Crochemore told me about a string algorithm (suffix sorting) that appeared at a |
|
653 conference in 2007 (ICALP) |
|
654 \item ``horribly incomprehensible'', no implementation, but claims to be the best \bl{$O(n + k)$} algorithm\bigskip\pause |
|
655 |
|
656 \item Jian Jiang found 1 error and 1 superfluous step |
|
657 \item he received 88\% for the project and won the prize for the best 7CCSMPRJ project |
|
658 \item no proof \ldots{} yet |
|
659 \end{itemize} |
|
660 |
|
661 \end{frame}} |
|
662 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
663 |
646 |
664 |
647 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
665 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
648 \mode<presentation>{ |
666 \mode<presentation>{ |
649 \begin{frame}[c] |
667 \begin{frame}[c] |
650 \frametitle{Trusted Third Party} |
668 \frametitle{Trusted Third Party} |
775 |
793 |
776 \begin{itemize} |
794 \begin{itemize} |
777 \item an engine \bl{$E$} and a transponder \bl{$T$} share a key \bl{$K$}\bigskip |
795 \item an engine \bl{$E$} and a transponder \bl{$T$} share a key \bl{$K$}\bigskip |
778 \item \bl{$E$} sends out a \alert{nonce} \bl{$N$} (random number) to \bl{$T$}\bigskip |
796 \item \bl{$E$} sends out a \alert{nonce} \bl{$N$} (random number) to \bl{$T$}\bigskip |
779 \item \bl{$T$} responds with \bl{$\{N\}_K$}\bigskip |
797 \item \bl{$T$} responds with \bl{$\{N\}_K$}\bigskip |
780 \item if \bl{$E$} receives \bl{$\{N\}_K$} from \bl{$T$} then starts engine |
798 \item if \bl{$E$} receives \bl{$\{N\}_K$} from \bl{$T$}, it starts engine |
781 \end{itemize} |
799 \end{itemize} |
782 |
800 |
783 \end{frame}} |
801 \end{frame}} |
784 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
802 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
785 |
803 |
786 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
804 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
787 \mode<presentation>{ |
805 \mode<presentation>{ |
788 \begin{frame}[c] |
806 \begin{frame}[c] |
789 \frametitle{Challenge-Response Protokol} |
807 \frametitle{Challenge-Response Protocol} |
790 |
808 |
791 \begin{center} |
809 \begin{center} |
792 \bl{\begin{tabular}{l} |
810 \bl{\begin{tabular}{l} |
793 $E \;\text{says}\; N$\hfill(start)\\ |
811 $E \;\text{says}\; N$\hfill(start)\\ |
794 $E \;\text{sends}\; T : N$\hfill(challenge)\\ |
812 $E \;\text{sends}\; T : N$\hfill(challenge)\\ |
803 |
821 |
804 \bl{$\Gamma \vdash \text{start\_engine}(T)$}? |
822 \bl{$\Gamma \vdash \text{start\_engine}(T)$}? |
805 \end{frame}} |
823 \end{frame}} |
806 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
824 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
807 |
825 |
|
826 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
827 \mode<presentation>{ |
|
828 \begin{frame}[c] |
|
829 \frametitle{Exchange of a Fresh Key} |
|
830 |
|
831 \begin{itemize} |
|
832 \item assumption \bl{$K_{AB}$} is only known to \bl{$A$} and \bl{$B$}\bigskip |
|
833 \item \bl{$A \,\text{sends}\, B : A, \{N_A\}_{K_{AB}}$} |
|
834 \item \bl{$B\,\text{sends}\, A : \{N_A + 1, N_B\}_{K_{AB}}$} |
|
835 \item \bl{$A \,\text{sends}\, B : \{N_B + 1\}_{K_{AB}}$} |
|
836 \item \bl{$B \,\text{sends}\, A : \{K^{new}_{AB}, N^{new}_B\}_{K_{AB}}$} |
|
837 \end{itemize}\bigskip\pause |
|
838 |
|
839 We hope \bl{$K^{new}_{AB}$} is only known to \bl{$A$} and \bl{$B$}.\\ |
|
840 \bl{$N^{new}_B$} is to be used in future messages |
|
841 \end{frame}} |
|
842 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
843 |
|
844 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
845 \mode<presentation>{ |
|
846 \begin{frame}[c] |
|
847 \frametitle{The Attack} |
|
848 |
|
849 An intruder \bl{$I$} convinces \bl{$B$} to accept an old compromised key |
|
850 |
|
851 \begin{itemize} |
|
852 \item \bl{$A \,\text{sends}\, B : A, \{N_A\}_{K_{AB}}$} |
|
853 \item \bl{$B\,\text{sends}\, A : \{N_A + 1, N_B\}_{K_{AB}}$} |
|
854 \item \bl{$A \,\text{sends}\, B : \{N_B + 1\}_{K_{AB}}$} |
|
855 \item \bl{$B \,\text{sends}\, A : \{K^{new}_{AB}, N^{new}_B\}_{K_{AB}}$}\pause |
|
856 \end{itemize} |
|
857 |
|
858 \end{frame}} |
|
859 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
860 |
808 \end{document} |
861 \end{document} |
809 |
862 |
810 %%% Local Variables: |
863 %%% Local Variables: |
811 %%% mode: latex |
864 %%% mode: latex |
812 %%% TeX-master: t |
865 %%% TeX-master: t |