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

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

sourced out KeyPattern class

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