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

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

some small keysearcher changes

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