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} |
---|