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

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

small keysearcher fixes

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