source: trunk/CrypPlugins/KeySearcher/KeySearcher.cs @ 825

Last change on this file since 825 was 825, checked in by Sven Rech, 12 years ago

fixed most stupid bug ever

File size: 25.1 KB
Line 
1using System;
2using System.Linq;
3using System.Text;
4using Cryptool.PluginBase.Analysis;
5using Cryptool.PluginBase;
6using System.Windows.Controls;
7using System.ComponentModel;
8using Cryptool.PluginBase.Control;
9using System.Collections;
10using System.Collections.Generic;
11using System.Threading;
12using System.Windows.Threading;
13
14namespace KeySearcher
15{
16    public class KeyPattern
17    {
18        private class Wildcard
19        {
20            private char[] values = new char[256];
21            private int length;
22            private int counter;
23           
24            public Wildcard(string valuePattern)
25            {
26                counter = 0;
27                length = 0;
28                int i = 1;
29                while (valuePattern[i] != ']')
30                {
31                    if (valuePattern[i + 1] == '-')
32                    {
33                        for (char c = valuePattern[i]; c <= valuePattern[i + 2]; c++)
34                            values[length++] = c;
35                        i += 2;
36                    }
37                    else
38                        values[length++] = valuePattern[i];
39                    i++;
40                }
41            }
42
43            public Wildcard(Wildcard wc)
44            {
45                length = wc.length;
46                counter = 0;
47                for (int i = 0; i < 256; i++)
48                    values[i] = wc.values[i];
49            }
50
51            private Wildcard()
52            {
53            }
54
55            public Wildcard[] split()
56            {
57                Wildcard[] wcs = new Wildcard[2];
58                wcs[0] = new Wildcard();
59                wcs[0].counter = 0;
60                wcs[0].length = length / 2;
61                wcs[1] = new Wildcard();
62                wcs[1].counter = 0;
63                wcs[1].length = length - wcs[0].length;
64                for (int i = 0; i < wcs[0].length; i++)
65                    wcs[0].values[i] = values[i];
66                for (int i = 0; i < wcs[1].length; i++)
67                    wcs[1].values[i] = values[i + wcs[0].length];
68                return wcs;
69            }
70
71            public char getChar()
72            {
73                return values[counter];
74            }
75
76            public bool succ()
77            {
78                counter++;
79                if (counter >= length)
80                {
81                    counter = 0;
82                    return true;
83                }
84                return false;
85            }
86
87            public int size()
88            {
89                return length;
90            }
91
92        }
93
94        private string pattern;
95        private string key;       
96        private ArrayList wildcardList;
97
98        public KeyPattern(string pattern)
99        {
100            this.pattern = pattern;
101        }
102
103        public KeyPattern[] split()
104        {
105            KeyPattern[] patterns = new KeyPattern[2];
106            for (int i = 0; i < 2; i++)
107            {
108                patterns[i] = new KeyPattern(pattern);
109                patterns[i].key = key;
110                patterns[i].wildcardList = new ArrayList();
111            }
112            bool s = false;
113            for (int i = 0; i < wildcardList.Count; i++)
114            {
115                if (!s && ((Wildcard)wildcardList[i]).size() > 1)
116                {
117                    Wildcard[] wc = ((Wildcard)wildcardList[i]).split();
118                    patterns[0].wildcardList.Add(wc[0]);
119                    patterns[1].wildcardList.Add(wc[1]);
120                    s = true;
121                }
122                else
123                {
124                    patterns[0].wildcardList.Add(new Wildcard((Wildcard)wildcardList[i]));
125                    patterns[1].wildcardList.Add(new Wildcard((Wildcard)wildcardList[i]));
126                }
127            }
128            return patterns;
129        }
130
131        public string giveWildcardKey()
132        {
133            string res = "";
134            int i = 0;
135            while (i < pattern.Length)
136            {
137                if (pattern[i] != '[')
138                    res += pattern[i];
139                else
140                {
141                    res += '*';
142                    while (pattern[i] != ']')
143                        i++;
144                }
145                i++;
146            }
147            return res;
148        }
149
150        public bool testKey(string key)
151        {
152            int kcount = 0;
153            int pcount = 0;
154            while (kcount < key.Length && pcount < pattern.Length)
155            {
156                if (pattern[pcount] != '[')
157                {
158                    if (key[kcount] != '*' && pattern[pcount] != key[kcount])
159                        return false;
160                    kcount++;
161                    pcount++;
162                }
163                else
164                {
165                    bool contains = false;
166                    pcount++;
167                    while (pattern[pcount] != ']')
168                    {
169                        if (key[kcount] != '*')
170                        {
171                            if (pattern[pcount + 1] == '-')
172                            {
173                                if (key[kcount] >= pattern[pcount] && key[kcount] <= pattern[pcount + 2])
174                                    contains = true;
175                                pcount += 2;
176                            }
177                            else
178                                if (pattern[pcount] == key[kcount])
179                                    contains = true;
180                        }
181                        pcount++;
182                    }
183                    if (!contains && !(key[kcount] == '*'))
184                        return false;
185                    kcount++;
186                    pcount++;
187                }               
188            }
189            if (pcount != pattern.Length || kcount != key.Length)
190                return false;
191            return true;
192        }
193
194        public long initKeyIteration(string key)
195        {
196            long counter = 1;
197            this.key = key;
198            int pcount = 0;
199            wildcardList = new ArrayList();
200            for (int i = 0; i < key.Length; i++)
201            {
202                if (key[i] == '*')
203                {
204                    Wildcard wc = new Wildcard(pattern.Substring(pcount, pattern.IndexOf(']', pcount) + 1 - pcount));
205                    wildcardList.Add(wc);
206                    counter *= wc.size();
207                }
208
209                if (pattern[pcount] == '[')
210                    while (pattern[pcount] != ']')
211                        pcount++;
212                pcount++;
213            }
214            return counter;
215        }
216
217        public bool nextKey()
218        {
219            int wildcardCount = wildcardList.Count-1;
220            bool overflow = ((Wildcard)wildcardList[wildcardCount]).succ();
221            wildcardCount--;
222            while (overflow && (wildcardCount >= 0))
223                overflow = ((Wildcard)wildcardList[wildcardCount--]).succ();
224            return !overflow;
225        }
226
227        public string getKey()
228        {
229            string res = "";
230            int wildcardCount = 0;
231            for (int i = 0; i < key.Length; i++)
232            {
233                if (key[i] != '*')
234                    res += key[i];
235                else
236                {
237                    Wildcard wc = (Wildcard)wildcardList[wildcardCount++];
238                    res += wc.getChar();
239                }
240            }
241            return res;
242        }
243    }
244   
245    [Author("Thomas Schmid", "thomas.schmid@cryptool.org", "Uni Siegen", "http://www.uni-siegen.de")]
246    //[Author("Sven Rech", "rech@cryptool.org", "Uni Duisburg-Essen", "http://www.uni-due.de")]
247    [PluginInfo(true, "KeySearcher", "Bruteforces a decryption algorithm.", null, "KeySearcher/Images/icon.png")]
248    public class KeySearcher : IAnalysisMisc
249    {
250        private Queue valuequeue;
251        private double value_threshold;
252
253        private KeyPattern pattern = null;
254        public KeyPattern Pattern
255        {
256            get
257            {
258                return pattern;
259            }
260            set
261            {
262                pattern = value;
263                if ((settings.Key == null) ||((settings.Key != null) && !pattern.testKey(settings.Key)))
264                    settings.Key = pattern.giveWildcardKey();
265            }
266        }
267
268        private bool stop;
269
270        #region IPlugin Members
271
272        public event StatusChangedEventHandler OnPluginStatusChanged;
273
274        public event GuiLogNotificationEventHandler OnGuiLogNotificationOccured;
275
276        public event PluginProgressChangedEventHandler OnPluginProgressChanged;
277
278        private KeySearcherSettings settings;
279
280        public KeySearcher()
281        {
282            settings = new KeySearcherSettings(this);
283            QuickWatchPresentation = new KeySearcherQuickWatchPresentation();
284        }
285
286        public ISettings Settings
287        {
288            get { return settings; }
289        }
290
291        public UserControl Presentation
292        {
293            get { return null; }
294        }
295
296        public UserControl QuickWatchPresentation
297        {
298            get;
299            private set;
300        }
301
302        public void PreExecution()
303        {
304        }
305
306        public void Execute()
307        {
308        }
309
310        private void KeySearcherJob(object param)
311        {
312            object[] parameters = (object[])param;
313            KeyPattern pattern = (KeyPattern)parameters[0];
314            int threadid = (int)parameters[1];
315            Int64[] doneKeysArray = (Int64[])parameters[2];
316            Int64[] keycounterArray = (Int64[])parameters[3];           
317            IControlEncryption sender = (IControlEncryption)parameters[4];
318            int bytesToUse = (int)parameters[5];
319
320            try
321            {
322
323                long size = pattern.initKeyIteration(settings.Key);
324
325                do
326                {
327                    ValueKey valueKey = new ValueKey();
328                    try
329                    {
330                        valueKey.key = Pattern.getKey();
331                    }
332                    catch (Exception ex)
333                    {
334                        GuiLogMessage("Could not get next Key: " + ex.Message, NotificationLevel.Error);
335                        return;
336                    }
337
338                    try
339                    {
340                        valueKey.decryption = sender.Decrypt(ControlMaster.getKeyFromString(valueKey.key), bytesToUse);
341                    }
342                    catch (Exception ex)
343                    {
344                        GuiLogMessage("Decryption is not possible: " + ex.Message, NotificationLevel.Error);
345                        GuiLogMessage("Stack Trace: " + ex.StackTrace, NotificationLevel.Error);
346                        return;
347                    }
348
349                    try
350                    {
351                        valueKey.value = CostMaster.calculateCost(valueKey.decryption);
352                    }
353                    catch (Exception ex)
354                    {
355                        GuiLogMessage("Cost calculation is not possible: " + ex.Message, NotificationLevel.Error);
356                        return;
357                    }
358
359                    if (this.costMaster.getRelationOperator() == RelationOperator.LargerThen)
360                    {
361                        if (valueKey.value > value_threshold)
362                            valuequeue.Enqueue(valueKey);
363                    }
364                    else
365                    {
366                        if (valueKey.value < value_threshold)
367                            valuequeue.Enqueue(valueKey);
368                    }
369
370                    doneKeysArray[threadid]++;
371                    keycounterArray[threadid]++;
372                } while (pattern.nextKey() && !stop);
373            }
374            finally
375            {
376                sender.Dispose();
377            }
378        }
379
380        public void process(IControlEncryption sender)
381        {
382            if (sender != null && costMaster != null)
383            {
384                int maxInList = 10;
385                LinkedList<ValueKey> costList = new LinkedList<ValueKey>();
386                ValueKey valueKey = new ValueKey();
387                if (this.costMaster.getRelationOperator() == RelationOperator.LessThen)
388                    valueKey.value = double.MaxValue;
389                else
390                    valueKey.value = double.MinValue;
391                valueKey.key = "dummykey";
392                valueKey.decryption = new byte[0];
393                value_threshold = valueKey.value;
394                LinkedListNode<ValueKey> node = costList.AddFirst(valueKey);
395                for (int i = 1; i < maxInList; i++)
396                {
397                    node = costList.AddAfter(node, valueKey);
398                }
399
400                stop = false;
401                if (!Pattern.testKey(settings.Key))
402                {
403                    GuiLogMessage("Wrong key pattern!", NotificationLevel.Error);
404                    return;
405                }
406
407                int bytesToUse = 0;
408
409                try
410                {
411                    bytesToUse = CostMaster.getBytesToUse();
412                }
413                catch (Exception ex)
414                {
415                    GuiLogMessage("Bytes used not valid: " + ex.Message, NotificationLevel.Error);
416                    return;
417                }
418
419                LinkedListNode<ValueKey> linkedListNode;
420
421                KeyPattern[] patterns;
422                long size = Pattern.initKeyIteration(settings.Key);
423
424                if (settings.CoresUsed > 0)
425                    patterns = Pattern.split();
426                else
427                {
428                    patterns = new KeyPattern[1];
429                    patterns[0] = Pattern;
430                }
431
432                valuequeue = Queue.Synchronized(new Queue());
433
434                Int64[] doneKeysA = new Int64[patterns.Length];
435                Int64[] keycounters = new Int64[patterns.Length];
436                for (int i = 0; i < patterns.Length; i++)
437                {
438                    WaitCallback worker = new WaitCallback(KeySearcherJob);
439                    doneKeysA[i] = new Int64();
440                    keycounters[i] = new Int64();
441                    ThreadPool.QueueUserWorkItem(worker, new object[] { patterns[i], i, doneKeysA, keycounters, sender.clone(), bytesToUse });
442                }
443               
444                //update message:
445                while (!stop)
446                {
447                    Thread.Sleep(1000);
448
449                    //update toplist:
450                    while (valuequeue.Count != 0)
451                    {
452                        ValueKey vk = (ValueKey)valuequeue.Dequeue();
453                        if (this.costMaster.getRelationOperator() == RelationOperator.LargerThen)
454                        {
455                            if (vk.value > costList.Last().value)
456                            {
457                                node = costList.First;
458                                while (node != null)
459                                {
460
461                                    if (vk.value > node.Value.value)
462                                    {
463                                        costList.AddBefore(node, vk);
464                                        costList.RemoveLast();
465                                        value_threshold = costList.Last.Value.value;
466                                        break;
467                                    }
468                                    node = node.Next;
469                                }//end while
470                            }//end if
471                        }
472                        else
473                        {
474                            node = costList.First;
475                            if (vk.value < costList.Last().value)
476                            {
477                                while (node != null)
478                                {
479
480                                    if (vk.value < node.Value.value)
481                                    {
482                                        costList.AddBefore(node, vk);
483                                        costList.RemoveLast();
484                                        value_threshold = costList.Last.Value.value;
485                                        break;
486                                    }
487                                    node = node.Next;
488                                }//end while
489                            }//end if
490                        }
491                    }
492
493                    long keycounter = 0;
494                    long doneKeys = 0;
495                    foreach (Int64 dk in doneKeysA)
496                        doneKeys += dk;
497                    foreach (Int64 kc in keycounters)
498                        keycounter += kc;
499
500                    ProgressChanged(keycounter, size);
501
502                    if (QuickWatchPresentation.IsVisible && doneKeys != 0)
503                    {
504                        double time = ((size - keycounter) / doneKeys);
505                        TimeSpan timeleft = new TimeSpan(-1);
506
507                        try
508                        {
509                            if (time / (24 * 60 * 60) <= int.MaxValue)
510                            {
511                                int days = (int)(time / (24 * 60 * 60));
512                                time = time - (days * 24 * 60 * 60);
513                                int hours = (int)(time / (60 * 60));
514                                time = time - (hours * 60 * 60);
515                                int minutes = (int)(time / 60);
516                                time = time - (minutes * 60);
517                                int seconds = (int)time;
518
519                                timeleft = new TimeSpan(days, hours, minutes, (int)seconds, 0);
520                            }
521                        }
522                        catch
523                        {
524                            //can not calculate time span
525                        }
526
527                        ((KeySearcherQuickWatchPresentation)QuickWatchPresentation).Dispatcher.Invoke(DispatcherPriority.Normal, (SendOrPostCallback)delegate
528                        {
529                            ((KeySearcherQuickWatchPresentation)QuickWatchPresentation).keysPerSecond.Text = "" + doneKeys;
530                            if (timeleft != new TimeSpan(-1))
531                            {
532                                ((KeySearcherQuickWatchPresentation)QuickWatchPresentation).timeLeft.Text = "" + timeleft;
533                                try
534                                {
535                                    ((KeySearcherQuickWatchPresentation)QuickWatchPresentation).endTime.Text = "" + DateTime.Now.Add(timeleft);
536                                }
537                                catch
538                                {
539                                    ((KeySearcherQuickWatchPresentation)QuickWatchPresentation).endTime.Text = "in a galaxy far, far away...";
540                                }
541                            }
542                            else
543                            {
544                                ((KeySearcherQuickWatchPresentation)QuickWatchPresentation).timeLeft.Text = "incalculable :-)";
545                                ((KeySearcherQuickWatchPresentation)QuickWatchPresentation).endTime.Text = "in a galaxy far, far away...";
546                            }
547
548                            ((KeySearcherQuickWatchPresentation)QuickWatchPresentation).listbox.Items.Clear();
549                            linkedListNode = costList.First;
550                            System.Text.ASCIIEncoding enc = new System.Text.ASCIIEncoding();
551                            int i = 0;
552                            while (linkedListNode != null)
553                            {
554                                i++;
555                                ((KeySearcherQuickWatchPresentation)QuickWatchPresentation).listbox.Items.Add(i + ") " + Math.Round(linkedListNode.Value.value, 4) + " = " + linkedListNode.Value.key + " : \"" +
556                                    enc.GetString(linkedListNode.Value.decryption).Replace("\n", "").Replace("\r", "").Replace("\t", "") + "\"");
557                                linkedListNode = linkedListNode.Next;
558                            }
559                        }
560                        , null);
561                    }//end if
562                    doneKeys = 0;
563                    for (int i = 0; i < doneKeysA.Length; i++)
564                        doneKeysA[i] = 0;
565
566                    if (!stop && QuickWatchPresentation.IsVisible)
567                    {
568
569                        ((KeySearcherQuickWatchPresentation)QuickWatchPresentation).Dispatcher.Invoke(DispatcherPriority.Normal, (SendOrPostCallback)delegate
570                        {
571                            ((KeySearcherQuickWatchPresentation)QuickWatchPresentation).listbox.Items.Clear();
572                            linkedListNode = costList.First;
573                            System.Text.ASCIIEncoding enc = new System.Text.ASCIIEncoding();
574                            int i = 0;
575                            while (linkedListNode != null)
576                            {
577                                i++;
578                                ((KeySearcherQuickWatchPresentation)QuickWatchPresentation).listbox.Items.Add(i + ") " + Math.Round(linkedListNode.Value.value, 4) + " = " + linkedListNode.Value.key + " : \"" +
579                                    enc.GetString(linkedListNode.Value.decryption).Replace("\n", "").Replace("\r", "").Replace("\t", "") + "\"");
580                                linkedListNode = linkedListNode.Next;
581                            }
582                        }
583                        , null);
584                    }
585
586                    if (keycounter >= size)
587                        break;
588                }//end while 
589            }//end if
590
591            if (!stop)
592                ProgressChanged(1, 1);
593 
594        }
595
596        public void PostExecution()
597        {
598        }
599
600        public void Pause()
601        {
602        }
603
604        public void Stop()
605        {
606            stop = true;
607        }
608
609        public void Initialize()
610        {
611        }
612
613        public void Dispose()
614        {
615        }
616
617        #endregion
618
619        #region INotifyPropertyChanged Members
620
621        public event PropertyChangedEventHandler PropertyChanged;
622
623        public void OnPropertyChanged(string name)
624        {
625            if (PropertyChanged != null)
626            {
627                PropertyChanged(this, new PropertyChangedEventArgs(name));
628            }
629        }
630
631        #endregion
632
633        private void keyPatternChanged()
634        {
635            Pattern = new KeyPattern(controlMaster.getKeyPattern());
636        }
637
638        private void onStatusChanged(IControl sender, bool readyForExecution)
639        {
640            if (readyForExecution)
641            {
642                this.process((IControlEncryption)sender);
643            }
644        }
645
646        #region IControlEncryption Members
647
648        private IControlEncryption controlMaster;
649        [PropertyInfo(Direction.ControlMaster, "Control Master", "Used for bruteforcing", "", DisplayLevel.Beginner)]
650        public IControlEncryption ControlMaster
651        {
652            get { return controlMaster; }
653            set
654            {
655                if (controlMaster != null)
656                {
657                    controlMaster.keyPatternChanged -= keyPatternChanged;
658                    controlMaster.OnStatusChanged -= onStatusChanged;
659                }
660                if (value != null)
661                {
662                    Pattern = new KeyPattern(value.getKeyPattern());
663                    value.keyPatternChanged += keyPatternChanged;
664                    value.OnStatusChanged += onStatusChanged;
665                    controlMaster = value;
666                    OnPropertyChanged("ControlMaster");
667                   
668                }
669                else
670                    controlMaster = null;
671            }
672        }
673
674        #endregion
675
676        #region IControlCost Members
677
678        private IControlCost costMaster;
679        [PropertyInfo(Direction.ControlMaster, "Cost Master", "Used for cost calculation", "", DisplayLevel.Beginner)]
680        public IControlCost CostMaster
681        {
682            get { return costMaster; }
683            set
684            {
685                costMaster = value;
686            }
687        }
688
689        #endregion
690
691        public void GuiLogMessage(string message, NotificationLevel loglevel)
692        {
693            if (OnGuiLogNotificationOccured != null)
694                OnGuiLogNotificationOccured(this, new GuiLogEventArgs(message, this, loglevel));
695        }
696
697        public void ProgressChanged(double value, double max)
698        {
699            if (OnPluginProgressChanged != null)
700            {
701                OnPluginProgressChanged(this, new PluginProgressEventArgs(value, max));
702
703            }
704        }
705
706        private struct ValueKey
707        {
708            public double value;
709            public String key;
710            public byte[] decryption;
711        };
712    }
713}
714
Note: See TracBrowser for help on using the repository browser.