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

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

some keysearcher cleanup

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