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

Last change on this file since 939 was 939, checked in by arnold, 12 years ago

Beiden Klassen umstrukturiert und teilweise kommentiert. Außerdem KeyPattern die Methode ToString() hinzugefügt

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