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

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

fixed some bugs in KeySearcher

File size: 25.3 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 long size()
218        {
219            long counter = 1;
220            foreach (Wildcard wc in wildcardList)
221                    counter *= wc.size();
222            return counter;
223        }
224
225        public bool nextKey()
226        {
227            int wildcardCount = wildcardList.Count-1;
228            bool overflow = ((Wildcard)wildcardList[wildcardCount]).succ();
229            wildcardCount--;
230            while (overflow && (wildcardCount >= 0))
231                overflow = ((Wildcard)wildcardList[wildcardCount--]).succ();
232            return !overflow;
233        }
234
235        public string getKey()
236        {
237            string res = "";
238            int wildcardCount = 0;
239            for (int i = 0; i < key.Length; i++)
240            {
241                if (key[i] != '*')
242                    res += key[i];
243                else
244                {
245                    Wildcard wc = (Wildcard)wildcardList[wildcardCount++];
246                    res += wc.getChar();
247                }
248            }
249            return res;
250        }
251    }
252   
253    [Author("Thomas Schmid", "thomas.schmid@cryptool.org", "Uni Siegen", "http://www.uni-siegen.de")]
254    //[Author("Sven Rech", "rech@cryptool.org", "Uni Duisburg-Essen", "http://www.uni-due.de")]
255    [PluginInfo(true, "KeySearcher", "Bruteforces a decryption algorithm.", null, "KeySearcher/Images/icon.png")]
256    public class KeySearcher : IAnalysisMisc
257    {
258        private Queue valuequeue;
259        private double value_threshold;
260
261        private KeyPattern pattern = null;
262        public KeyPattern Pattern
263        {
264            get
265            {
266                return pattern;
267            }
268            set
269            {
270                pattern = value;
271                if ((settings.Key == null) ||((settings.Key != null) && !pattern.testKey(settings.Key)))
272                    settings.Key = pattern.giveWildcardKey();
273            }
274        }
275
276        private bool stop;
277
278        #region IPlugin Members
279
280        public event StatusChangedEventHandler OnPluginStatusChanged;
281
282        public event GuiLogNotificationEventHandler OnGuiLogNotificationOccured;
283
284        public event PluginProgressChangedEventHandler OnPluginProgressChanged;
285
286        private KeySearcherSettings settings;
287
288        public KeySearcher()
289        {
290            settings = new KeySearcherSettings(this);
291            QuickWatchPresentation = new KeySearcherQuickWatchPresentation();
292        }
293
294        public ISettings Settings
295        {
296            get { return settings; }
297        }
298
299        public UserControl Presentation
300        {
301            get { return null; }
302        }
303
304        public UserControl QuickWatchPresentation
305        {
306            get;
307            private set;
308        }
309
310        public void PreExecution()
311        {
312        }
313
314        public void Execute()
315        {
316        }
317
318        private void KeySearcherJob(object param)
319        {
320            object[] parameters = (object[])param;
321            KeyPattern pattern = (KeyPattern)parameters[0];
322            int threadid = (int)parameters[1];
323            Int64[] doneKeysArray = (Int64[])parameters[2];
324            Int64[] keycounterArray = (Int64[])parameters[3];           
325            IControlEncryption sender = (IControlEncryption)parameters[4];
326            int bytesToUse = (int)parameters[5];
327
328            try
329            {
330
331                long size = pattern.size();
332
333                do
334                {
335                    ValueKey valueKey = new ValueKey();
336                    try
337                    {
338                        valueKey.key = pattern.getKey();
339                    }
340                    catch (Exception ex)
341                    {
342                        GuiLogMessage("Could not get next Key: " + ex.Message, NotificationLevel.Error);
343                        return;
344                    }
345
346                    try
347                    {
348                        valueKey.decryption = sender.Decrypt(ControlMaster.getKeyFromString(valueKey.key), bytesToUse);
349                    }
350                    catch (Exception ex)
351                    {
352                        GuiLogMessage("Decryption is not possible: " + ex.Message, NotificationLevel.Error);
353                        GuiLogMessage("Stack Trace: " + ex.StackTrace, NotificationLevel.Error);
354                        return;
355                    }
356
357                    try
358                    {
359                        valueKey.value = CostMaster.calculateCost(valueKey.decryption);
360                    }
361                    catch (Exception ex)
362                    {
363                        GuiLogMessage("Cost calculation is not possible: " + ex.Message, NotificationLevel.Error);
364                        return;
365                    }
366
367                    if (this.costMaster.getRelationOperator() == RelationOperator.LargerThen)
368                    {
369                        if (valueKey.value > value_threshold)
370                            valuequeue.Enqueue(valueKey);
371                    }
372                    else
373                    {
374                        if (valueKey.value < value_threshold)
375                            valuequeue.Enqueue(valueKey);
376                    }
377
378                    doneKeysArray[threadid]++;
379                    keycounterArray[threadid]++;
380                } while (pattern.nextKey() && !stop);
381            }
382            finally
383            {
384                sender.Dispose();
385            }
386        }
387
388        public void process(IControlEncryption sender)
389        {
390            if (sender != null && costMaster != null)
391            {
392                int maxInList = 10;
393                LinkedList<ValueKey> costList = new LinkedList<ValueKey>();
394                ValueKey valueKey = new ValueKey();
395                if (this.costMaster.getRelationOperator() == RelationOperator.LessThen)
396                    valueKey.value = double.MaxValue;
397                else
398                    valueKey.value = double.MinValue;
399                valueKey.key = "dummykey";
400                valueKey.decryption = new byte[0];
401                value_threshold = valueKey.value;
402                LinkedListNode<ValueKey> node = costList.AddFirst(valueKey);
403                for (int i = 1; i < maxInList; i++)
404                {
405                    node = costList.AddAfter(node, valueKey);
406                }
407
408                stop = false;
409                if (!Pattern.testKey(settings.Key))
410                {
411                    GuiLogMessage("Wrong key pattern!", NotificationLevel.Error);
412                    return;
413                }
414
415                int bytesToUse = 0;
416
417                try
418                {
419                    bytesToUse = CostMaster.getBytesToUse();
420                }
421                catch (Exception ex)
422                {
423                    GuiLogMessage("Bytes used not valid: " + ex.Message, NotificationLevel.Error);
424                    return;
425                }
426
427                LinkedListNode<ValueKey> linkedListNode;
428
429                KeyPattern[] patterns;
430                long size = Pattern.initKeyIteration(settings.Key);
431
432                if (settings.CoresUsed > 0)
433                    patterns = Pattern.split();
434                else
435                {
436                    patterns = new KeyPattern[1];
437                    patterns[0] = Pattern;
438                }
439
440                valuequeue = Queue.Synchronized(new Queue());
441
442                Int64[] doneKeysA = new Int64[patterns.Length];
443                Int64[] keycounters = new Int64[patterns.Length];
444                for (int i = 0; i < patterns.Length; i++)
445                {
446                    WaitCallback worker = new WaitCallback(KeySearcherJob);
447                    doneKeysA[i] = new Int64();
448                    keycounters[i] = new Int64();
449                    ThreadPool.QueueUserWorkItem(worker, new object[] { patterns[i], i, doneKeysA, keycounters, sender.clone(), bytesToUse });
450                }
451               
452                //update message:
453                while (!stop)
454                {
455                    Thread.Sleep(1000);
456
457                    //update toplist:
458                    while (valuequeue.Count != 0)
459                    {
460                        ValueKey vk = (ValueKey)valuequeue.Dequeue();
461                        if (this.costMaster.getRelationOperator() == RelationOperator.LargerThen)
462                        {
463                            if (vk.value > costList.Last().value)
464                            {
465                                node = costList.First;
466                                while (node != null)
467                                {
468
469                                    if (vk.value > node.Value.value)
470                                    {
471                                        costList.AddBefore(node, vk);
472                                        costList.RemoveLast();
473                                        value_threshold = costList.Last.Value.value;
474                                        break;
475                                    }
476                                    node = node.Next;
477                                }//end while
478                            }//end if
479                        }
480                        else
481                        {
482                            node = costList.First;
483                            if (vk.value < costList.Last().value)
484                            {
485                                while (node != null)
486                                {
487
488                                    if (vk.value < node.Value.value)
489                                    {
490                                        costList.AddBefore(node, vk);
491                                        costList.RemoveLast();
492                                        value_threshold = costList.Last.Value.value;
493                                        break;
494                                    }
495                                    node = node.Next;
496                                }//end while
497                            }//end if
498                        }
499                    }
500
501                    long keycounter = 0;
502                    long doneKeys = 0;
503                    foreach (Int64 dk in doneKeysA)
504                        doneKeys += dk;
505                    foreach (Int64 kc in keycounters)
506                        keycounter += kc;
507
508                    ProgressChanged(keycounter, size);
509
510                    if (QuickWatchPresentation.IsVisible && doneKeys != 0)
511                    {
512                        double time = ((size - keycounter) / doneKeys);
513                        TimeSpan timeleft = new TimeSpan(-1);
514
515                        try
516                        {
517                            if (time / (24 * 60 * 60) <= int.MaxValue)
518                            {
519                                int days = (int)(time / (24 * 60 * 60));
520                                time = time - (days * 24 * 60 * 60);
521                                int hours = (int)(time / (60 * 60));
522                                time = time - (hours * 60 * 60);
523                                int minutes = (int)(time / 60);
524                                time = time - (minutes * 60);
525                                int seconds = (int)time;
526
527                                timeleft = new TimeSpan(days, hours, minutes, (int)seconds, 0);
528                            }
529                        }
530                        catch
531                        {
532                            //can not calculate time span
533                        }
534
535                        ((KeySearcherQuickWatchPresentation)QuickWatchPresentation).Dispatcher.Invoke(DispatcherPriority.Normal, (SendOrPostCallback)delegate
536                        {
537                            ((KeySearcherQuickWatchPresentation)QuickWatchPresentation).keysPerSecond.Text = "" + doneKeys;
538                            if (timeleft != new TimeSpan(-1))
539                            {
540                                ((KeySearcherQuickWatchPresentation)QuickWatchPresentation).timeLeft.Text = "" + timeleft;
541                                try
542                                {
543                                    ((KeySearcherQuickWatchPresentation)QuickWatchPresentation).endTime.Text = "" + DateTime.Now.Add(timeleft);
544                                }
545                                catch
546                                {
547                                    ((KeySearcherQuickWatchPresentation)QuickWatchPresentation).endTime.Text = "in a galaxy far, far away...";
548                                }
549                            }
550                            else
551                            {
552                                ((KeySearcherQuickWatchPresentation)QuickWatchPresentation).timeLeft.Text = "incalculable :-)";
553                                ((KeySearcherQuickWatchPresentation)QuickWatchPresentation).endTime.Text = "in a galaxy far, far away...";
554                            }
555
556                            ((KeySearcherQuickWatchPresentation)QuickWatchPresentation).listbox.Items.Clear();
557                            linkedListNode = costList.First;
558                            System.Text.ASCIIEncoding enc = new System.Text.ASCIIEncoding();
559                            int i = 0;
560                            while (linkedListNode != null)
561                            {
562                                i++;
563                                ((KeySearcherQuickWatchPresentation)QuickWatchPresentation).listbox.Items.Add(i + ") " + Math.Round(linkedListNode.Value.value, 4) + " = " + linkedListNode.Value.key + " : \"" +
564                                    enc.GetString(linkedListNode.Value.decryption).Replace("\n", "").Replace("\r", "").Replace("\t", "") + "\"");
565                                linkedListNode = linkedListNode.Next;
566                            }
567                        }
568                        , null);
569                    }//end if
570                    doneKeys = 0;
571                    for (int i = 0; i < doneKeysA.Length; i++)
572                        doneKeysA[i] = 0;
573
574                    if (!stop && QuickWatchPresentation.IsVisible)
575                    {
576
577                        ((KeySearcherQuickWatchPresentation)QuickWatchPresentation).Dispatcher.Invoke(DispatcherPriority.Normal, (SendOrPostCallback)delegate
578                        {
579                            ((KeySearcherQuickWatchPresentation)QuickWatchPresentation).listbox.Items.Clear();
580                            linkedListNode = costList.First;
581                            System.Text.ASCIIEncoding enc = new System.Text.ASCIIEncoding();
582                            int i = 0;
583                            while (linkedListNode != null)
584                            {
585                                i++;
586                                ((KeySearcherQuickWatchPresentation)QuickWatchPresentation).listbox.Items.Add(i + ") " + Math.Round(linkedListNode.Value.value, 4) + " = " + linkedListNode.Value.key + " : \"" +
587                                    enc.GetString(linkedListNode.Value.decryption).Replace("\n", "").Replace("\r", "").Replace("\t", "") + "\"");
588                                linkedListNode = linkedListNode.Next;
589                            }
590                        }
591                        , null);
592                    }
593
594                    if (keycounter >= size)
595                        break;
596                }//end while 
597            }//end if
598
599            if (!stop)
600                ProgressChanged(1, 1);
601 
602        }
603
604        public void PostExecution()
605        {
606        }
607
608        public void Pause()
609        {
610        }
611
612        public void Stop()
613        {
614            stop = true;
615        }
616
617        public void Initialize()
618        {
619        }
620
621        public void Dispose()
622        {
623        }
624
625        #endregion
626
627        #region INotifyPropertyChanged Members
628
629        public event PropertyChangedEventHandler PropertyChanged;
630
631        public void OnPropertyChanged(string name)
632        {
633            if (PropertyChanged != null)
634            {
635                PropertyChanged(this, new PropertyChangedEventArgs(name));
636            }
637        }
638
639        #endregion
640
641        private void keyPatternChanged()
642        {
643            Pattern = new KeyPattern(controlMaster.getKeyPattern());
644        }
645
646        private void onStatusChanged(IControl sender, bool readyForExecution)
647        {
648            if (readyForExecution)
649            {
650                this.process((IControlEncryption)sender);
651            }
652        }
653
654        #region IControlEncryption Members
655
656        private IControlEncryption controlMaster;
657        [PropertyInfo(Direction.ControlMaster, "Control Master", "Used for bruteforcing", "", DisplayLevel.Beginner)]
658        public IControlEncryption ControlMaster
659        {
660            get { return controlMaster; }
661            set
662            {
663                if (controlMaster != null)
664                {
665                    controlMaster.keyPatternChanged -= keyPatternChanged;
666                    controlMaster.OnStatusChanged -= onStatusChanged;
667                }
668                if (value != null)
669                {
670                    Pattern = new KeyPattern(value.getKeyPattern());
671                    value.keyPatternChanged += keyPatternChanged;
672                    value.OnStatusChanged += onStatusChanged;
673                    controlMaster = value;
674                    OnPropertyChanged("ControlMaster");
675                   
676                }
677                else
678                    controlMaster = null;
679            }
680        }
681
682        #endregion
683
684        #region IControlCost Members
685
686        private IControlCost costMaster;
687        [PropertyInfo(Direction.ControlMaster, "Cost Master", "Used for cost calculation", "", DisplayLevel.Beginner)]
688        public IControlCost CostMaster
689        {
690            get { return costMaster; }
691            set
692            {
693                costMaster = value;
694            }
695        }
696
697        #endregion
698
699        public void GuiLogMessage(string message, NotificationLevel loglevel)
700        {
701            if (OnGuiLogNotificationOccured != null)
702                OnGuiLogNotificationOccured(this, new GuiLogEventArgs(message, this, loglevel));
703        }
704
705        public void ProgressChanged(double value, double max)
706        {
707            if (OnPluginProgressChanged != null)
708            {
709                OnPluginProgressChanged(this, new PluginProgressEventArgs(value, max));
710
711            }
712        }
713
714        private struct ValueKey
715        {
716            public double value;
717            public String key;
718            public byte[] decryption;
719        };
720    }
721}
722
Note: See TracBrowser for help on using the repository browser.