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

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

Minimal extended version (new BruteforcePattern method for distant calls)

File size: 27.5 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        // modified by Arnie - 2009.12.02
692        protected virtual void onStatusChanged(IControl sender, bool readyForExecution)
693        {
694            if (readyForExecution)
695            {
696                this.process((IControlEncryption)sender);
697            }
698        }
699
700        // added by Arnie -2009.12.02
701        // for inheritance reasons
702        public void BruteforcePattern(KeyPattern pattern, IControlEncryption encryptControl, IControlCost costControl)
703        {
704            ControlMaster = encryptControl;
705            CostMaster = costControl;
706            bruteforcePattern(pattern, encryptControl);
707        }
708
709        #endregion
710
711        public void GuiLogMessage(string message, NotificationLevel loglevel)
712        {
713            if (OnGuiLogNotificationOccured != null)
714                OnGuiLogNotificationOccured(this, new GuiLogEventArgs(message, this, loglevel));
715        }
716
717        public void ProgressChanged(double value, double max)
718        {
719            if (OnPluginProgressChanged != null)
720            {
721                OnPluginProgressChanged(this, new PluginProgressEventArgs(value, max));
722
723            }
724        }
725
726        /// <summary>
727        /// used for delivering the results from the worker threads to the main thread:
728        /// </summary>
729        private struct ValueKey
730        {
731            public double value;
732            public String key;
733            public byte[] decryption;
734        };
735    }
736}
Note: See TracBrowser for help on using the repository browser.