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

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

some big keypattern changes that are needed for christians work.

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            BigInteger size = pattern.setWildcardKey(settings.Key);           
425            KeyPattern[] patterns = splitPatternForThreads(pattern);
426
427            valuequeue = Queue.Synchronized(new Queue());
428
429            BigInteger[] doneKeysA = new BigInteger[patterns.Length];
430            BigInteger[] keycounters = new BigInteger[patterns.Length];
431            BigInteger[] keysleft = new BigInteger[patterns.Length];
432            Stack threadStack = Stack.Synchronized(new Stack());
433            startThreads(sender, bytesToUse, patterns, doneKeysA, keycounters, keysleft, threadStack);
434
435            //update message:
436            while (!stop)
437            {
438                Thread.Sleep(1000);
439
440                updateToplist(costList);
441
442                #region calculate global counters from local counters
443                BigInteger keycounter = 0;
444                BigInteger doneKeys = 0;
445                foreach (BigInteger dk in doneKeysA)
446                    doneKeys += dk;
447                foreach (BigInteger kc in keycounters)
448                    keycounter += kc;
449                #endregion
450
451                if (keycounter > size)
452                    GuiLogMessage("There must be an error, because we bruteforced too much keys...", NotificationLevel.Error);
453
454                #region determination of the thread with most keys
455                if (size - keycounter > 1000)
456                {
457                    maxThreadMutex.WaitOne();
458                    BigInteger max = 0;
459                    int id = -1;
460                    for (int i = 0; i < patterns.Length; i++)
461                        if (keysleft[i] > max)
462                        {
463                            max = keysleft[i];
464                            id = i;
465                        }
466                    maxThread = id;
467                    maxThreadMutex.ReleaseMutex();
468                }
469                #endregion
470
471                showProgress(costList, size, keycounter, doneKeys);
472
473                #region set doneKeys to 0
474                doneKeys = 0;
475                for (int i = 0; i < doneKeysA.Length; i++)
476                    doneKeysA[i] = 0;
477                #endregion
478
479                if (keycounter >= size)
480                    break;
481            }//end while
482
483            //wake up all sleeping threads, so they can stop:
484            while (threadStack.Count != 0)
485                ((ThreadStackElement)threadStack.Pop()).ev.Set();
486
487            if (!stop)
488                ProgressChanged(1, 1);
489        }
490
491        private void showProgress(LinkedList<ValueKey> costList, BigInteger size, BigInteger keycounter, BigInteger doneKeys)
492        {
493            LinkedListNode<ValueKey> linkedListNode;
494            ProgressChanged(Math.Pow(10, keycounter.log(10) - size.log(10)), 1.0);
495
496            if (QuickWatchPresentation.IsVisible && doneKeys != 0 && !stop)
497            {
498                double time = (Math.Pow(10, (size - keycounter).log(10) - doneKeys.log(10)));
499                TimeSpan timeleft = new TimeSpan(-1);
500
501                try
502                {
503                    if (time / (24 * 60 * 60) <= int.MaxValue)
504                    {
505                        int days = (int)(time / (24 * 60 * 60));
506                        time = time - (days * 24 * 60 * 60);
507                        int hours = (int)(time / (60 * 60));
508                        time = time - (hours * 60 * 60);
509                        int minutes = (int)(time / 60);
510                        time = time - (minutes * 60);
511                        int seconds = (int)time;
512
513                        timeleft = new TimeSpan(days, hours, minutes, (int)seconds, 0);
514                    }
515                }
516                catch
517                {
518                    //can not calculate time span
519                }
520
521                ((KeySearcherQuickWatchPresentation)QuickWatchPresentation).Dispatcher.Invoke(DispatcherPriority.Normal, (SendOrPostCallback)delegate
522                {
523                    ((KeySearcherQuickWatchPresentation)QuickWatchPresentation).keysPerSecond.Text = "" + doneKeys;
524                    if (timeleft != new TimeSpan(-1))
525                    {
526                        ((KeySearcherQuickWatchPresentation)QuickWatchPresentation).timeLeft.Text = "" + timeleft;
527                        try
528                        {
529                            ((KeySearcherQuickWatchPresentation)QuickWatchPresentation).endTime.Text = "" + DateTime.Now.Add(timeleft);
530                        }
531                        catch
532                        {
533                            ((KeySearcherQuickWatchPresentation)QuickWatchPresentation).endTime.Text = "in a galaxy far, far away...";
534                        }
535                    }
536                    else
537                    {
538                        ((KeySearcherQuickWatchPresentation)QuickWatchPresentation).timeLeft.Text = "incalculable :-)";
539                        ((KeySearcherQuickWatchPresentation)QuickWatchPresentation).endTime.Text = "in a galaxy far, far away...";
540                    }
541
542                    ((KeySearcherQuickWatchPresentation)QuickWatchPresentation).listbox.Items.Clear();
543                    linkedListNode = costList.First;
544                    System.Text.ASCIIEncoding enc = new System.Text.ASCIIEncoding();
545                    int i = 0;
546                    while (linkedListNode != null)
547                    {
548                        i++;
549                        ((KeySearcherQuickWatchPresentation)QuickWatchPresentation).listbox.Items.Add(i + ") " + Math.Round(linkedListNode.Value.value, 4) + " = " + linkedListNode.Value.key + " : \"" +
550                            enc.GetString(linkedListNode.Value.decryption).Replace("\n", "").Replace("\r", "").Replace("\t", "") + "\"");
551                        linkedListNode = linkedListNode.Next;
552                    }
553                }
554                , null);
555            }//end if
556
557
558            if (!stop && QuickWatchPresentation.IsVisible)
559            {
560
561                ((KeySearcherQuickWatchPresentation)QuickWatchPresentation).Dispatcher.Invoke(DispatcherPriority.Normal, (SendOrPostCallback)delegate
562                {
563                    ((KeySearcherQuickWatchPresentation)QuickWatchPresentation).listbox.Items.Clear();
564                    linkedListNode = costList.First;
565                    System.Text.ASCIIEncoding enc = new System.Text.ASCIIEncoding();
566                    int i = 0;
567                    while (linkedListNode != null)
568                    {
569                        i++;
570                        ((KeySearcherQuickWatchPresentation)QuickWatchPresentation).listbox.Items.Add(i + ") " + Math.Round(linkedListNode.Value.value, 4) + " = " + linkedListNode.Value.key + " : \"" +
571                            enc.GetString(linkedListNode.Value.decryption).Replace("\n", "").Replace("\r", "").Replace("\t", "") + "\"");
572                        linkedListNode = linkedListNode.Next;
573                    }
574                }
575                , null);
576            }
577        }
578
579        #region For TopList
580
581        private void fillListWithDummies(int maxInList, LinkedList<ValueKey> costList)
582        {
583            ValueKey valueKey = new ValueKey();
584            if (this.costMaster.getRelationOperator() == RelationOperator.LessThen)
585                valueKey.value = double.MaxValue;
586            else
587                valueKey.value = double.MinValue;
588            valueKey.key = "dummykey";
589            valueKey.decryption = new byte[0];
590            value_threshold = valueKey.value;
591            LinkedListNode<ValueKey> node = costList.AddFirst(valueKey);
592            for (int i = 1; i < maxInList; i++)
593            {
594                node = costList.AddAfter(node, valueKey);
595            }
596        }
597
598        private void updateToplist(LinkedList<ValueKey> costList)
599        {
600            LinkedListNode<ValueKey> node;
601            while (valuequeue.Count != 0)
602            {
603                ValueKey vk = (ValueKey)valuequeue.Dequeue();
604                if (this.costMaster.getRelationOperator() == RelationOperator.LargerThen)
605                {
606                    if (vk.value > costList.Last().value)
607                    {
608                        node = costList.First;
609                        while (node != null)
610                        {
611                            if (vk.value > node.Value.value)
612                            {
613                                costList.AddBefore(node, vk);
614                                costList.RemoveLast();
615                                value_threshold = costList.Last.Value.value;
616                                break;
617                            }
618                            node = node.Next;
619                        }//end while
620                    }//end if
621                }
622                else
623                {
624                    if (vk.value < costList.Last().value)
625                    {
626                        node = costList.First;
627                        while (node != null)
628                        {
629                            if (vk.value < node.Value.value)
630                            {
631                                costList.AddBefore(node, vk);
632                                costList.RemoveLast();
633                                value_threshold = costList.Last.Value.value;
634                                break;
635                            }
636                            node = node.Next;
637                        }//end while
638                    }//end if
639                }
640            }
641        }
642
643        #endregion
644
645        private void startThreads(IControlEncryption sender, int bytesToUse, KeyPattern[] patterns, BigInteger[] doneKeysA, BigInteger[] keycounters, BigInteger[] keysleft, Stack threadStack)
646        {
647            for (int i = 0; i < patterns.Length; i++)
648            {
649                WaitCallback worker = new WaitCallback(KeySearcherJob);
650                doneKeysA[i] = new BigInteger();
651                keycounters[i] = new BigInteger();
652                ThreadPool.QueueUserWorkItem(worker, new object[] { patterns, i, doneKeysA, keycounters, keysleft, sender.clone(), bytesToUse, threadStack });
653            }
654        }
655
656        private KeyPattern[] splitPatternForThreads(KeyPattern pattern)
657        {
658            KeyPattern[] patterns = new KeyPattern[settings.CoresUsed + 1];
659            if (settings.CoresUsed > 0)
660            {
661                KeyPattern[] patterns2 = pattern.split();
662                patterns[0] = patterns2[0];
663                patterns[1] = patterns2[1];
664                int p = 1;
665                int threads = settings.CoresUsed - 1;
666                while (threads > 0)
667                {
668                    int maxPattern = -1;
669                    BigInteger max = 0;
670                    for (int i = 0; i <= p; i++)
671                        if (patterns[i].size() > max)
672                        {
673                            max = patterns[i].size();
674                            maxPattern = i;
675                        }
676                    KeyPattern[] patterns3 = patterns[maxPattern].split();
677                    patterns[maxPattern] = patterns3[0];
678                    patterns[++p] = patterns3[1];
679                    threads--;
680                }
681            }
682            else
683                patterns[0] = Pattern;
684            return patterns;
685        }
686
687        private void keyPatternChanged()
688        {
689            Pattern = new KeyPattern(controlMaster.getKeyPattern());
690        }
691
692        // modified by Arnie - 2009.12.02
693        protected virtual void onStatusChanged(IControl sender, bool readyForExecution)
694        {
695            if (readyForExecution)
696            {
697                this.process((IControlEncryption)sender);
698            }
699        }
700
701        // added by Arnie -2009.12.02
702        // for inheritance reasons
703        public void BruteforcePattern(KeyPattern pattern, IControlEncryption encryptControl, IControlCost costControl)
704        {
705            ControlMaster = encryptControl;
706            CostMaster = costControl;
707            bruteforcePattern(pattern, encryptControl);
708        }
709
710        #endregion
711
712        public void GuiLogMessage(string message, NotificationLevel loglevel)
713        {
714            if (OnGuiLogNotificationOccured != null)
715                OnGuiLogNotificationOccured(this, new GuiLogEventArgs(message, this, loglevel));
716        }
717
718        public void ProgressChanged(double value, double max)
719        {
720            if (OnPluginProgressChanged != null)
721            {
722                OnPluginProgressChanged(this, new PluginProgressEventArgs(value, max));
723
724            }
725        }
726
727        /// <summary>
728        /// used for delivering the results from the worker threads to the main thread:
729        /// </summary>
730        private struct ValueKey
731        {
732            public double value;
733            public String key;
734            public byte[] decryption;
735        };
736    }
737}
Note: See TracBrowser for help on using the repository browser.