[166] | 1 | % vim: set tw=78 aw: |
---|
| 2 | \documentclass{beamer} |
---|
| 3 | |
---|
| 4 | \usepackage[utf8x]{inputenc} % diacritice |
---|
| 5 | \usepackage[english]{babel} |
---|
| 6 | \usepackage{color} % highlight |
---|
| 7 | \usepackage{alltt} % highlight |
---|
| 8 | \usepackage{hyperref} % folositi \url{http://...} |
---|
| 9 | \usepackage{graphicx} |
---|
| 10 | \mode<presentation> |
---|
| 11 | { \usetheme{Rochester} } % TODO: settle this |
---|
| 12 | |
---|
| 13 | % Titlul nu foloseÅte Unicode pentru cÄ e o problemÄ cÄreia nu i-am dat de |
---|
| 14 | % cap. |
---|
| 15 | \title[Cracking A5/1]{Cracking A5/1} |
---|
| 16 | %\subtitle{} |
---|
| 17 | \institute{OSP} |
---|
| 18 | \author{Lucian Adrian Grijincu \\ \texttt{lucian.grijincu@gmail.com}} |
---|
| 19 | |
---|
| 20 | |
---|
| 21 | \begin{document} |
---|
| 22 | |
---|
| 23 | % Slide-urile cu mai multe pÄrÅ£i sunt marcate cu textul (cont.) |
---|
| 24 | \setbeamertemplate{frametitle continuation}[from second] |
---|
| 25 | % ArÄtÄm numÄrul frame-ului |
---|
| 26 | \setbeamertemplate{footline}[frame number] |
---|
| 27 | |
---|
| 28 | \frame{\titlepage} |
---|
| 29 | \frame{\tableofcontents} |
---|
| 30 | |
---|
| 31 | \section{Introduction} |
---|
| 32 | \frame{\tableofcontents[currentsection]} |
---|
| 33 | |
---|
| 34 | \begin{frame}{A5/what?} |
---|
| 35 | \begin{itemize} |
---|
| 36 | \item A5/1 - stream cipher used for OTA privacy in GSM networks |
---|
| 37 | \item A5/2 - a weaker version of A5/1 |
---|
| 38 | \item A5/3 - (aka KASUMI) newer version, other kind of algorithm |
---|
| 39 | \end{itemize} |
---|
| 40 | \end{frame} |
---|
| 41 | |
---|
| 42 | |
---|
| 43 | \begin{frame}{A5/1} |
---|
| 44 | \begin{itemize} |
---|
| 45 | \item designed from the start to be easy to break: |
---|
| 46 | \item 1994 - first disclosure of the algorithm |
---|
| 47 | \item 1997 - A5/1 shown academically broken |
---|
| 48 | \item 2000 - more proof ... |
---|
| 49 | \item 2003 - more proof ... |
---|
| 50 | \item 2005 - and then some more ... |
---|
| 51 | \item 2008 - rainbow tables computed (but never released publicly) |
---|
| 52 | \item 2009 - A5/1 Security Project announce project to build public rainbow table |
---|
| 53 | \item 2010 - rainbow tables released on bittorrent (2TB) |
---|
| 54 | \end{itemize} |
---|
| 55 | \end{frame} |
---|
| 56 | |
---|
| 57 | \begin{frame}{A5/1 used in GSM} |
---|
| 58 | \begin{itemize} |
---|
| 59 | \item first plain-text frames of a GSM call have a distinct |
---|
| 60 | pattern: |
---|
| 61 | \begin{itemize} |
---|
| 62 | \item some bits are always zero |
---|
| 63 | \item ACK bits |
---|
| 64 | \item state encoding bits |
---|
| 65 | \end{itemize} |
---|
| 66 | \item this limmits the search space significantly |
---|
| 67 | \end{itemize} |
---|
| 68 | \end{frame} |
---|
| 69 | |
---|
| 70 | \begin{frame}{History lesson} |
---|
| 71 | similar technique used to break the German cypher in WW2: |
---|
| 72 | \begin{itemize} |
---|
| 73 | \item messages longer than a page began with |
---|
| 74 | \item FORT (\textit{Fortsetzung}) |
---|
| 75 | \item the time of the previous message between \texttt{Y}s |
---|
| 76 | \item the time of the previous message between \texttt{Y}s, again! |
---|
| 77 | \item ``continuation of message sent at 2330'' â ``FORTYWEEPYYWEEPY'' |
---|
| 78 | \end{itemize} |
---|
| 79 | \end{frame} |
---|
| 80 | |
---|
| 81 | |
---|
| 82 | \section{Rainbow tables} |
---|
| 83 | \frame{\tableofcontents[currentsection]} |
---|
| 84 | |
---|
| 85 | \begin{frame}{Cypher tables} |
---|
| 86 | \begin{itemize} |
---|
| 87 | \item for each plain text |
---|
| 88 | \begin{itemize} |
---|
| 89 | \item for each password |
---|
| 90 | \begin{itemize} |
---|
| 91 | \item compute crypto(text, password) |
---|
| 92 | \end{itemize} |
---|
| 93 | \end{itemize} |
---|
| 94 | \end{itemize} |
---|
| 95 | \end{frame} |
---|
| 96 | |
---|
| 97 | \begin{frame}{Cypher tables} |
---|
| 98 | \begin{itemize} |
---|
| 99 | \item pass=0000 |
---|
| 100 | \begin{itemize} |
---|
| 101 | \item 0000 - A7B7 |
---|
| 102 | \item 0001 - HJ89 |
---|
| 103 | \item ... |
---|
| 104 | \item 9999 - 21J3 |
---|
| 105 | \end{itemize} |
---|
| 106 | \item pass=0001 |
---|
| 107 | \begin{itemize} |
---|
| 108 | \item 0000 - 32H4 |
---|
| 109 | \item 0001 - 5JL3 |
---|
| 110 | \item ... |
---|
| 111 | \item 9999 - HJ89 |
---|
| 112 | \end{itemize} |
---|
| 113 | \end{itemize} |
---|
| 114 | \end{frame} |
---|
| 115 | |
---|
| 116 | \begin{frame}{Cypher tables} |
---|
| 117 | \begin{itemize} |
---|
| 118 | \item size grows exponentially with |
---|
| 119 | \begin{itemize} |
---|
| 120 | \item plain text length |
---|
| 121 | \item password length |
---|
| 122 | \end{itemize} |
---|
| 123 | \item duplicates in the table. HJ89 bellongs to: |
---|
| 124 | \begin{itemize} |
---|
| 125 | \item text=0001 and pass=0000 |
---|
| 126 | \item text=9999 and pass=0001 |
---|
| 127 | \item etc. |
---|
| 128 | \end{itemize} |
---|
| 129 | \end{itemize} |
---|
| 130 | \end{frame} |
---|
| 131 | |
---|
| 132 | \begin{frame}{Rainbow tables} |
---|
| 133 | \begin{itemize} |
---|
| 134 | \item select a random set of input secret values |
---|
| 135 | \item reduce the size of the table |
---|
| 136 | \item increase the lookup time |
---|
| 137 | \end{itemize} |
---|
| 138 | \end{frame} |
---|
| 139 | |
---|
| 140 | \begin{frame}{Rainbow tables} |
---|
| 141 | \includegraphics[scale=0.6]{pics/rainbow.png} |
---|
| 142 | \end{frame} |
---|
| 143 | |
---|
| 144 | \begin{frame}{Rainbow tables} |
---|
| 145 | \includegraphics[scale=0.6]{pics/r-lookup.png} |
---|
| 146 | \end{frame} |
---|
| 147 | |
---|
| 148 | \begin{frame}{Rainbow tables} |
---|
| 149 | \begin{itemize} |
---|
| 150 | \item R functions are not inverses of H! |
---|
| 151 | \item chains of $2^{15}$ R functions per table |
---|
| 152 | \item posibility of overlapping last entries: |
---|
| 153 | \item use many tables with other sets of R functions |
---|
| 154 | \end{itemize} |
---|
| 155 | \end{frame} |
---|
| 156 | |
---|
| 157 | \section{Hadoop} |
---|
| 158 | \frame{\tableofcontents[currentsection]} |
---|
| 159 | |
---|
| 160 | \begin{frame}{Hadoop} |
---|
| 161 | \begin{itemize} |
---|
| 162 | \item open source map-reduce |
---|
| 163 | \item highly scalable (thousand of nodes) |
---|
| 164 | \end{itemize} |
---|
| 165 | \end{frame} |
---|
| 166 | |
---|
| 167 | \begin{frame}{Hadoop} |
---|
| 168 | \textbf{Map} |
---|
| 169 | \begin{itemize} |
---|
| 170 | \item read input |
---|
| 171 | \item create basic $<key, value>$ pairs |
---|
| 172 | \end{itemize} |
---|
| 173 | \end{frame} |
---|
| 174 | |
---|
| 175 | \begin{frame}{Hadoop} |
---|
| 176 | \textbf{Reduce} |
---|
| 177 | \begin{itemize} |
---|
| 178 | \item combine $<key, value>$ pairs with same $key$ |
---|
| 179 | \item write output |
---|
| 180 | \end{itemize} |
---|
| 181 | \end{frame} |
---|
| 182 | |
---|
| 183 | |
---|
| 184 | |
---|
| 185 | |
---|
| 186 | \section{Cracking A5/1 with Hadoop} |
---|
| 187 | \frame{\tableofcontents[currentsection]} |
---|
| 188 | \begin{frame}{Cracking steps} |
---|
| 189 | precalculate tables - done once |
---|
| 190 | \begin{enumerate} |
---|
| 191 | \item create a set of random initial secret values |
---|
| 192 | \item map-reduce the creation of the tables |
---|
| 193 | \end{enumerate} |
---|
| 194 | search for a secret based on hashes |
---|
| 195 | \end{frame} |
---|
| 196 | |
---|
| 197 | |
---|
| 198 | \begin{frame}{Table calculation - \textbf{Map}} |
---|
| 199 | \begin{itemize} |
---|
| 200 | \item break input set of secrets |
---|
| 201 | \item each mapper computes a chain |
---|
| 202 | \item results are sent with |
---|
| 203 | \begin{itemize} |
---|
| 204 | \item $key$=last secret in chain |
---|
| 205 | \item $value$=first secret in chain |
---|
| 206 | \end{itemize} |
---|
| 207 | \end{itemize} |
---|
| 208 | \end{frame} |
---|
| 209 | |
---|
| 210 | |
---|
| 211 | \begin{frame}{Table calculation - \textbf{Reduce}} |
---|
| 212 | \begin{itemize} |
---|
| 213 | \item reduce multiple $<key, value>$ pairs: |
---|
| 214 | \item group entries in tables |
---|
| 215 | \item group all start secrets that generate the same end secret |
---|
| 216 | \end{itemize} |
---|
| 217 | \end{frame} |
---|
| 218 | |
---|
| 219 | \begin{frame}{Lookup} |
---|
| 220 | in each table: |
---|
| 221 | \begin{itemize} |
---|
| 222 | \item \textbf{Map} - find all secrets that might generate the searched $hash$ |
---|
| 223 | \item \textbf{Reduce} - from all secrets, only select the most |
---|
| 224 | frequent appearing secret |
---|
| 225 | \end{itemize} |
---|
| 226 | \end{frame} |
---|
| 227 | |
---|
| 228 | \begin{frame}{Lookup algorithm} |
---|
| 229 | \includegraphics[scale=0.6]{pics/r-lookup.png} |
---|
| 230 | \end{frame} |
---|
| 231 | |
---|
| 232 | |
---|
| 233 | \section{Conclusion} |
---|
| 234 | \begin{frame}{Conclusion} |
---|
| 235 | \begin{itemize} |
---|
| 236 | \item depending on the size of the chains: 1TB - 32TB tables |
---|
| 237 | \item this permits near real-time lookup |
---|
| 238 | \end{itemize} |
---|
| 239 | \end{frame} |
---|
| 240 | |
---|
| 241 | \begin{frame}{Other GSM bad news} |
---|
| 242 | \begin{itemize} |
---|
| 243 | \item A5/2 - is weaker than A5/1 |
---|
| 244 | \item key sizes less than 64 bits make cracking possible |
---|
| 245 | \item hardware and software (open source) for GSM radio |
---|
| 246 | transmissions is already avaliable |
---|
| 247 | \item A5/3 - has 64 and 128 bit key sizes |
---|
| 248 | \item devices that support A5/3 use 64 bits because it consumes less power |
---|
| 249 | \end{itemize} |
---|
| 250 | \end{frame} |
---|
| 251 | |
---|
| 252 | \begin{frame}{Why weak algorithms?} |
---|
| 253 | \begin{itemize} |
---|
| 254 | \item they don't protect the user privacy |
---|
| 255 | \item only protect network operator's pockets |
---|
| 256 | \item crippled from the start to permit eavesdropping |
---|
| 257 | \end{itemize} |
---|
| 258 | \end{frame} |
---|
| 259 | |
---|
| 260 | \begin{frame}{Other results} |
---|
| 261 | \begin{itemize} |
---|
| 262 | \item The C3 group used 40 NVIDIA CUDA machines for three months |
---|
| 263 | \item rainbow table size: 2TB |
---|
| 264 | \item efficient distribuition of this table permits real-time |
---|
| 265 | cracking if the call is intercepted from the start |
---|
| 266 | \end{itemize} |
---|
| 267 | \end{frame} |
---|
| 268 | |
---|
| 269 | \end{document} |
---|