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

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

some small KeyPattern changes

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