source: trunk/CrypPlugins/KeySearcher/KeyTranslators/ByteArrayKeyTranslator.cs @ 2143

Last change on this file since 2143 was 2143, checked in by Sven Rech, 11 years ago

recomitted the keysearcher OpenCL optimization changes (hopefully this will work now...)

File size: 10.3 KB
Line 
1/*                             
2   Copyright 2010 Sven Rech (svenrech at googlemail dot com), Uni Duisburg-Essen
3
4   Licensed under the Apache License, Version 2.0 (the "License");
5   you may not use this file except in compliance with the License.
6   You may obtain a copy of the License at
7
8       http://www.apache.org/licenses/LICENSE-2.0
9
10   Unless required by applicable law or agreed to in writing, software
11   distributed under the License is distributed on an "AS IS" BASIS,
12   WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13   See the License for the specific language governing permissions and
14   limitations under the License.
15*/
16
17using System;
18using System.Collections.Generic;
19using System.Linq;
20using System.Text;
21using Cryptool.PluginBase.Control;
22using KeySearcher.KeyPattern;
23
24namespace KeySearcher.KeyTranslators
25{
26    /// <summary>
27    /// Implements a simple translator for bytearray keys that are represented by the pattern "[0-9A-F][0-9A-F]-[0-9A-F][0-9A-F]-...".
28    /// Is used by AES and DES.
29    /// </summary>
30    public class ByteArrayKeyTranslator : IKeyTranslator
31    {
32        private int progress = 0;
33        private KeyPattern.KeyPattern pattern;
34        private int[] movementStatus;
35        private byte[] keya;
36        private int[] movementPointers;
37        private IKeyMovement[] keyMovements;
38        private int openCLIndex;
39        private int openCLSize = 0;
40
41        #region KeyTranslator Members
42
43        public byte[] GetKeyFromRepresentation(string representation)
44        {
45            byte[] bkey = new byte[keya.Length];
46            for (int i = 0; i < bkey.Length; i++)
47            {
48                try
49                {
50                    string substr = representation.Substring(i * 3, 2);
51                    bkey[i] = Convert.ToByte(substr, 16);
52                }
53                catch (Exception ex)
54                {
55                    return null;
56                }
57            }
58            return bkey;
59        }
60
61        public void SetKeys(object keys)
62        {
63            if (!(keys is KeyPattern.KeyPattern))
64                throw new Exception("Something went horribly wrong!");
65
66            pattern = (KeyPattern.KeyPattern)keys;
67
68            keyMovements = pattern.getKeyMovements();
69            movementStatus = pattern.getWildcardProgress();
70            if (movementStatus.Length != keyMovements.Length)
71                throw new Exception("Movements and Wildcards do not fit together!");
72           
73            movementPointers = new int[movementStatus.Length];
74            int mpc = 0;
75
76            byte[] keya2 = new byte[256];
77            int kc = 0;
78            string wildcardKey = pattern.WildcardKey;
79            int i = 0;
80
81            bool first = true;
82
83            while (i < wildcardKey.Length)
84            {
85                if (wildcardKey[i] == '[')
86                {
87                    i++;
88                    while (wildcardKey[i++] != ']') ;
89                    i--;
90
91                    movementPointers[mpc++] = kc++;
92
93                    first = false;
94                }
95                else if (wildcardKey[i] == '-')
96                {
97                    first = true;
98                }
99                else
100                {
101                    byte val = Convert.ToByte(""+wildcardKey[i], 16);
102                    if (first)
103                        keya2[kc/2] = (byte)((int)val << 4);
104                    else
105                        keya2[kc/2] |= val;
106
107                    kc++;
108
109                    first = false;
110                }
111
112                i++;
113            }
114
115            keya = new byte[kc/2];
116            for (int c = 0; c < (kc/2); c++)
117                keya[c] = keya2[c];
118
119            for (int x = 0; x < movementStatus.Length - 1; x++)
120                SetWildcard(x);
121        }
122
123        public byte[] GetKey()
124        {
125            return keya;
126        }
127
128        public bool NextKey()
129        {
130            int i = movementStatus.Length - 1;
131            progress++;
132            return IncrementMovementStatus(i);
133        }
134
135        private bool IncrementMovementStatus(int index)
136        {
137            if (index < 0)
138                return false;
139
140            movementStatus[index]++;
141           
142            while (index >= 0 && !WildcardInRange(index))
143            {               
144                movementStatus[index] = 0;
145                SetWildcard(index);
146
147                index--;
148                if (index >= 0)
149                    movementStatus[index]++;         
150            }
151
152            if (index >= 0)
153                SetWildcard(index);
154
155            return index >= 0;
156        }
157
158        public string GetKeyRepresentation()
159        {
160            return pattern.getKey(progress);
161        }
162
163        public string GetKeyRepresentation(int add)
164        {
165            return pattern.getKey(add);
166        }
167
168        /// <summary>
169        /// Sets wildcard i in keya to the current progress
170        /// </summary>
171        /// <param name="i">the wildcard index</param>
172        private void SetWildcard(int i)
173        {
174            int index = movementPointers[i] / 2;
175            byte mask;
176            byte shift;
177            if (movementPointers[i] % 2 == 0)
178            {
179                mask = 1+2+4+8;
180                shift = 4;
181            }
182            else
183            {
184                mask = 16+32+64+128;
185                shift = 0;
186            }
187
188            keya[index] = (byte)((keya[index] & mask) | (CalcWildcard(i) << shift));
189        }
190
191        private int CalcWildcard(int i)
192        {
193            IKeyMovement mov = keyMovements[i];
194            if (mov is LinearKeyMovement)
195            {
196                return movementStatus[i] * (mov as LinearKeyMovement).A + (mov as LinearKeyMovement).B;
197            }
198            else if (mov is IntervalKeyMovement)
199            {
200                return (mov as IntervalKeyMovement).IntervalList[movementStatus[i]];
201            }
202
203            throw new Exception("Movement not implemented!");
204        }
205
206        private bool WildcardInRange(int i)
207        {
208            IKeyMovement mov = keyMovements[i];
209            if (mov is LinearKeyMovement)
210            {
211                return movementStatus[i] < (mov as LinearKeyMovement).UpperBound;
212            }
213            else if (mov is IntervalKeyMovement)
214            {
215                return movementStatus[i] < (mov as IntervalKeyMovement).IntervalList.Count;
216            }
217
218            return false;           
219        }
220
221        public int GetProgress()
222        {
223            int result = progress;
224            pattern.addKey(progress);
225
226            progress = 0;
227            return result;
228        }
229
230        public string ModifyOpenCLCode(string code, int approximateNumberOfKeys)
231        {
232            string[] byteReplaceStrings = new string[32];
233            for (int i = 0; i < 32; i++)
234                byteReplaceStrings[i] = "$$ADDKEYBYTE"+i+"$$";
235           
236            //Find out how many wildcards/keys we can bruteforce at once:
237            int j = movementStatus.Length - 1;
238            long size = 1;
239            while ((j >= 0) && ((size * keyMovements[j].Count()) <= approximateNumberOfKeys) && (movementStatus[j] == 0))
240                size *= keyMovements[j--].Count();
241
242            if (size < 256)
243                throw new Exception("Amount of keys to small to process with OpenCL.");    //it's futile to use OpenCL for so few keys
244
245            //generate the key movement string:
246            string[] movementStrings = new string[32];
247            string addVariable = "add";
248            for (int x = movementStatus.Length - 1; x > j; x--)
249            {
250                string movStr = string.Format("({0}%{1})", addVariable, keyMovements[x].Count());;
251
252                if (keyMovements[x] is LinearKeyMovement)
253                {
254                    var lkm = keyMovements[x] as LinearKeyMovement;
255                    movStr = string.Format("({0}*{1}+{2})", lkm.A, movStr, lkm.B);
256                }
257                else if (keyMovements[x] is IntervalKeyMovement)
258                {
259                    var ikm = keyMovements[x] as IntervalKeyMovement;
260
261                    //declare the invterval array:
262                    string s = string.Format("__constant int ikm{0}[{1}] = {{", x, ikm.Count());
263                    foreach (var c in ikm.IntervalList)
264                        s += c + ", ";
265                    s = s.Substring(0, s.Length - 2);
266                    s += "}; \n";
267                    code = code.Replace("$$MOVEMENTDECLARATIONS$$", s + "\n$$MOVEMENTDECLARATIONS$$");
268
269                    movStr = string.Format("ikm{0}[{1}]", x, movStr);
270                }
271                else
272                {
273                    throw new Exception("Key Movement not supported for OpenCL.");
274                }
275
276                if (movementPointers[x] % 2 == 0)
277                    movStr = "(" + movStr + " << 4)";
278                else
279                    movStr = "(" + movStr + ")";
280
281                addVariable = "(" + addVariable + "/" + keyMovements[x].Count() + ")";
282
283                int keyIndex = movementPointers[x]/2;
284                if (movementStrings[keyIndex] != null)
285                    movementStrings[keyIndex] += " | " + movStr;
286                else
287                    movementStrings[keyIndex] = movStr;
288            }
289
290            //put movement strings in code:
291            for (int y = 0; y < movementStrings.Length; y++)
292                code = code.Replace(byteReplaceStrings[y], movementStrings[y] != null ? ("("+movementStrings[y]+")") : "0");
293
294            code = code.Replace("$$MOVEMENTDECLARATIONS$$", "");
295
296            //progress:
297            openCLIndex = j;
298            openCLSize = (int)size;
299
300            return code;
301        }
302
303        public bool NextOpenCLBatch()
304        {
305            if (openCLSize > 0)
306            {
307                progress += openCLSize;
308                return IncrementMovementStatus(openCLIndex);
309            }
310            else
311            {
312                throw new Exception("This method can only be called if OpenCL code was generated!");
313            }
314        }
315
316        public int GetOpenCLBatchSize()
317        {
318            return openCLSize;
319        }
320
321        #endregion
322
323    }
324}
Note: See TracBrowser for help on using the repository browser.