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

Last change on this file since 2146 was 2146, checked in by Sven Rech, 11 years ago

Added opencl presentation in KeySearcher

File size: 49.2 KB
Line 
1/*                             
2   Copyright 2009 Sven Rech, Nils Kopal, Uni Duisburg-Essen
3
4   Licensed under the Apache License, Version 2.0 (the "License");
5   you may not use this file except in compliance with the License.
6   You may obtain a copy of the License at
7
8       http://www.apache.org/licenses/LICENSE-2.0
9
10   Unless required by applicable law or agreed to in writing, software
11   distributed under the License is distributed on an "AS IS" BASIS,
12   WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13   See the License for the specific language governing permissions and
14   limitations under the License.
15*/
16
17using System;
18using System.Diagnostics;
19using System.IO;
20using System.Linq;
21using System.Text;
22using Cryptool.P2P;
23using Cryptool.P2P.Internal;
24using Cryptool.PluginBase.Analysis;
25using Cryptool.PluginBase;
26using System.Windows.Controls;
27using System.ComponentModel;
28using Cryptool.PluginBase.Control;
29using System.Collections;
30using System.Collections.Generic;
31using System.Threading;
32using System.Windows.Threading;
33using Cryptool.PluginBase.IO;
34using System.Numerics;
35using KeySearcher.Helper;
36using KeySearcher.P2P;
37using KeySearcherPresentation;
38using KeySearcherPresentation.Controls;
39using OpenCLNet;
40
41namespace KeySearcher
42{   
43    [Author("Sven Rech, Nils Kopal, Raoul Falk, Dennis Nolte", "rech@cryptool.org", "Uni Duisburg-Essen", "http://www.uni-due.de")]
44    [PluginInfo(false, "KeySearcher", "Bruteforces a decryption algorithm.", "KeySearcher/DetailedDescription/Description.xaml", "KeySearcher/Images/icon.png")]
45    public class KeySearcher : IAnalysisMisc
46    {
47        /// <summary>
48        /// used for creating the TopList
49        /// </summary>
50        private Queue valuequeue;
51        private double value_threshold;
52        /// <summary>
53        /// the thread with the most keys left
54        /// </summary>
55        private int maxThread;
56        private readonly Mutex maxThreadMutex = new Mutex();
57        private ArrayList threadsStopEvents;
58
59        public bool IsKeySearcherRunning;
60        private KeyQualityHelper keyQualityHelper;
61        private readonly P2PQuickWatchPresentation p2PQuickWatchPresentation;
62        private readonly LocalQuickWatchPresentation localQuickWatchPresentation;
63
64        private OpenCLManager oclManager = null;
65        private Mutex openCLPresentationMutex = new Mutex();
66
67        private readonly Stopwatch localBruteForceStopwatch;
68
69        private KeyPattern.KeyPattern pattern;
70        public KeyPattern.KeyPattern Pattern
71        {
72            get
73            {
74                return pattern;
75            }
76            set
77            {
78                pattern = value;
79                if ((settings.Key == null) || ((settings.Key != null) && !pattern.testWildcardKey(settings.Key)))
80                    settings.Key = pattern.giveInputPattern();
81            }
82        }
83
84        internal bool stop;
85
86        #region IControlEncryption + IControlCost + InputFields
87
88        #region IControlEncryption Members
89
90        private IControlEncryption controlMaster;
91        [PropertyInfo(Direction.ControlMaster, "Control Master", "Used for bruteforcing", "", DisplayLevel.Beginner)]
92        public IControlEncryption ControlMaster
93        {
94            get { return controlMaster; }
95            set
96            {
97                if (controlMaster != null)
98                {
99                    controlMaster.keyPatternChanged -= keyPatternChanged;
100                }
101                if (value != null)
102                {
103                    Pattern = new KeyPattern.KeyPattern(value.getKeyPattern());
104                    value.keyPatternChanged += keyPatternChanged;
105                    controlMaster = value;
106                    OnPropertyChanged("ControlMaster");
107
108                }
109                else
110                    controlMaster = null;
111            }
112        }
113
114        #endregion
115
116        #region IControlCost Members
117
118        private IControlCost costMaster;
119        [PropertyInfo(Direction.ControlMaster, "Cost Master", "Used for cost calculation", "", DisplayLevel.Beginner)]
120        public IControlCost CostMaster
121        {
122            get { return costMaster; }
123            set
124            {
125                costMaster = value;
126                keyQualityHelper = new KeyQualityHelper(costMaster);
127            }
128        }
129
130        #endregion
131
132        /* BEGIN: following lines are from Arnie - 2010.01.12 */
133        CryptoolStream csEncryptedData;
134        [PropertyInfo(Direction.InputData, "CS Encrypted Data", "Encrypted data out of an Encryption PlugIn", "", false, false, DisplayLevel.Beginner, QuickWatchFormat.Hex, "")]
135        public virtual CryptoolStream CSEncryptedData
136        {
137            get { return this.csEncryptedData; }
138            set
139            {
140                if (value != this.csEncryptedData)
141                {
142                    this.csEncryptedData = value;
143                    this.encryptedData = GetByteFromCryptoolStream(value);
144                    OnPropertyChanged("CSEncryptedData");
145                }
146            }
147        }
148
149        byte[] encryptedData;
150        [PropertyInfo(Direction.InputData,"Encrypted Data","Encrypted data out of an Encryption PlugIn","",false,false,DisplayLevel.Beginner,QuickWatchFormat.Hex,"")]
151        public virtual byte[] EncryptedData
152        {
153            get { return this.encryptedData; }
154            set
155            {
156                if (value != this.encryptedData)
157                {
158                    this.encryptedData = value;
159                    OnPropertyChanged("EncryptedData");
160                }
161            }
162        }
163
164        /// <summary>
165        /// When the Input-Slot changed, set this variable to true, so the new Stream will be transformed to byte[]
166        /// </summary>
167        private byte[] GetByteFromCryptoolStream(CryptoolStream cryptoolStream)
168        {
169            byte[] encryptedByteData = null;
170
171            if (cryptoolStream != null)
172            {
173                CryptoolStream cs = new CryptoolStream();
174                cs.OpenRead(cryptoolStream.FileName);
175                encryptedByteData = new byte[cs.Length];
176                if(cs.Length > Int32.MaxValue)
177                    throw(new Exception("CryptoolStream length is longer than the Int32.MaxValue"));
178                cs.Read(encryptedByteData, 0, (int)cs.Length);
179            }
180            return encryptedByteData;
181        }
182
183        byte[] initVector;
184        [PropertyInfo(Direction.InputData, "Initialization Vector", "Initialization vector with which the data were encrypted", "", DisplayLevel.Beginner)]
185        public virtual byte[] InitVector
186        {
187            get { return this.initVector; }
188            set
189            {
190                if (value != this.initVector)
191                {
192                    this.initVector = value;
193                    OnPropertyChanged("InitVector");
194                }
195            }
196        }
197        /* END: Lines above are from Arnie - 2010.01.12 */
198
199        private ValueKey top1ValueKey;
200        public virtual ValueKey Top1
201        {
202            set { top1ValueKey = value; OnPropertyChanged("Top1Message"); OnPropertyChanged("Top1Key"); }
203        }
204
205        [PropertyInfo(Direction.OutputData, "Top1 Message", "The best message found", "", DisplayLevel.Beginner)]
206        public virtual byte[] Top1Message
207        {
208            get { return top1ValueKey.decryption; }
209        }
210        [PropertyInfo(Direction.OutputData, "Top1 Key", "The best key found", "", DisplayLevel.Beginner)]
211        public virtual byte[] Top1Key
212        {
213            get
214            {
215                if (top1ValueKey.key != null)
216                {
217                    return top1ValueKey.keya;
218                }
219                else
220                    return null;
221            }
222        }
223
224        #endregion
225
226        #region IPlugin Members
227
228        public event StatusChangedEventHandler OnPluginStatusChanged;
229
230        public event GuiLogNotificationEventHandler OnGuiLogNotificationOccured;
231
232        public event PluginProgressChangedEventHandler OnPluginProgressChanged;
233
234        private KeySearcherSettings settings;
235        private AutoResetEvent connectResetEvent;
236
237        public KeySearcher()
238        {
239            IsKeySearcherRunning = false;
240            if (OpenCL.NumberOfPlatforms > 0)
241            {
242                oclManager = new OpenCLManager();
243                oclManager.AttemptUseBinaries = false;
244                oclManager.AttemptUseSource = true;
245                oclManager.RequireImageSupport = false;
246                var directoryName = Path.Combine(DirectoryHelper.DirectoryLocalTemp, "KeySearcher");
247                oclManager.BinaryPath = Path.Combine(directoryName, "openclbin");
248                oclManager.BuildOptions = "";
249                oclManager.CreateDefaultContext(0, DeviceType.ALL);
250            }
251
252            settings = new KeySearcherSettings(this, oclManager);
253            QuickWatchPresentation = new QuickWatch();
254            localQuickWatchPresentation = ((QuickWatch) QuickWatchPresentation).LocalQuickWatchPresentation;
255            p2PQuickWatchPresentation = ((QuickWatch)QuickWatchPresentation).P2PQuickWatchPresentation;
256            p2PQuickWatchPresentation.UpdateSettings(this, settings);
257
258            settings.PropertyChanged += SettingsPropertyChanged;
259
260            localBruteForceStopwatch = new Stopwatch();
261        }
262
263        void SettingsPropertyChanged(object sender, PropertyChangedEventArgs e)
264        {
265            p2PQuickWatchPresentation.Dispatcher.BeginInvoke(DispatcherPriority.Normal,
266                                                             new Action(UpdateIsP2PEnabledSetting));
267        }
268
269        void UpdateIsP2PEnabledSetting()
270        {
271            ((QuickWatch)QuickWatchPresentation).IsP2PEnabled = settings.UsePeerToPeer;
272            ((QuickWatch)QuickWatchPresentation).IsOpenCLEnabled = settings.UseOpenCL;
273            p2PQuickWatchPresentation.UpdateSettings(this, settings);
274        }
275
276        public ISettings Settings
277        {
278            get { return settings; }
279        }
280
281        public UserControl Presentation
282        {
283            get { return QuickWatchPresentation; }
284        }
285
286        public UserControl QuickWatchPresentation
287        {
288            get;
289            private set;
290        }
291
292        public void PreExecution()
293        {
294        }
295
296        // because Encryption PlugIns were changed radical, the new StartPoint is here - Arnie 2010.01.12
297        public virtual void Execute()
298        {
299            IsKeySearcherRunning = true;
300
301            ((QuickWatch)QuickWatchPresentation).Dispatcher.BeginInvoke(DispatcherPriority.Normal, (SendOrPostCallback)delegate
302            {
303                openCLPresentationMutex.WaitOne();
304                ((QuickWatch)QuickWatchPresentation).OpenCLPresentation.AmountOfDevices = 0;
305                openCLPresentationMutex.ReleaseMutex();
306            }, null);
307
308            //either byte[] CStream input or CryptoolStream Object input
309            if (encryptedData != null || csEncryptedData != null) //to prevent execution on initialization
310            {
311                if (ControlMaster != null)
312                    process(ControlMaster);
313                else
314                {
315                    GuiLogMessage("You have to connect the KeySearcher with the Decryption Control!", NotificationLevel.Warning);
316                }
317            }
318        }
319
320        public void PostExecution()
321        {
322        }
323
324        public void Pause()
325        {
326        }
327
328        public void Stop()
329        {
330            IsKeySearcherRunning = false;
331            stop = true;
332        }
333
334        public void Initialize()
335        {
336            settings.Initialize();
337        }
338
339        public void Dispose()
340        {
341        }
342
343        #endregion
344
345        #region INotifyPropertyChanged Members
346
347        public event PropertyChangedEventHandler PropertyChanged;
348
349        public void OnPropertyChanged(string name)
350        {
351            if (PropertyChanged != null)
352            {
353                PropertyChanged(this, new PropertyChangedEventArgs(name));
354            }
355        }
356
357        #endregion
358
359        #region whole KeySearcher functionality
360
361        private class ThreadStackElement
362        {
363            public AutoResetEvent ev;
364            public int threadid;
365        }
366
367        #region code for the worker threads
368
369        private void KeySearcherJob(object param)
370        {
371            AutoResetEvent stopEvent = new AutoResetEvent(false);
372            threadsStopEvents.Add(stopEvent);
373
374            object[] parameters = (object[])param;
375            KeyPattern.KeyPattern[] patterns = (KeyPattern.KeyPattern[])parameters[0];
376            int threadid = (int)parameters[1];
377            BigInteger[] doneKeysArray = (BigInteger[])parameters[2];
378            BigInteger[] openCLDoneKeysArray = (BigInteger[])parameters[3];
379            BigInteger[] keycounterArray = (BigInteger[])parameters[4];
380            BigInteger[] keysLeft = (BigInteger[])parameters[5];
381            IControlEncryption sender = (IControlEncryption)parameters[6];
382            int bytesToUse = (int)parameters[7];
383            Stack threadStack = (Stack)parameters[8];
384            bool useOpenCL = (bool)parameters[9];
385
386            KeySearcherOpenCLCode keySearcherOpenCLCode = null;
387            KeySearcherOpenCLSubbatchOptimizer keySearcherOpenCLSubbatchOptimizer = null;
388            if (useOpenCL)
389            {
390                keySearcherOpenCLCode = new KeySearcherOpenCLCode(this, encryptedData, sender, CostMaster, 256 * 256 * 256 * 16);
391                keySearcherOpenCLSubbatchOptimizer = new KeySearcherOpenCLSubbatchOptimizer(oclManager.CQ[settings.OpenCLDevice].Device.MaxWorkItemSizes.Aggregate(1, (x, y) => (x * (int)y)) / 2);
392                ((QuickWatch)QuickWatchPresentation).Dispatcher.BeginInvoke(DispatcherPriority.Normal, (SendOrPostCallback)delegate
393                {
394                    openCLPresentationMutex.WaitOne();
395                    ((QuickWatch)QuickWatchPresentation).OpenCLPresentation.AmountOfDevices++;
396                    openCLPresentationMutex.ReleaseMutex();
397                }, null);
398            }
399
400            try
401            {
402                while (patterns[threadid] != null)
403                {
404                    BigInteger size = patterns[threadid].size();
405                    keysLeft[threadid] = size;
406                   
407                    IKeyTranslator keyTranslator = ControlMaster.getKeyTranslator();
408                    keyTranslator.SetKeys(patterns[threadid]);
409
410                    bool finish = false;
411
412                    do
413                    {
414                        //if we are the thread with most keys left, we have to share them:
415                        keyTranslator = ShareKeys(patterns, threadid, keysLeft, keyTranslator, threadStack);
416
417                        if (!useOpenCL)         //CPU
418                        {
419                            finish = BruteforceCPU(keyTranslator, sender, bytesToUse);
420                        }
421                        else                    //OpenCL
422                        {
423                            try
424                            {
425                                finish = BruteforceOpenCL(keySearcherOpenCLCode, keySearcherOpenCLSubbatchOptimizer, keyTranslator, sender, bytesToUse, parameters);
426                            }
427                            catch (Exception)
428                            {
429                                useOpenCL = false;
430                                ((QuickWatch)QuickWatchPresentation).Dispatcher.BeginInvoke(DispatcherPriority.Normal, (SendOrPostCallback)delegate
431                                {
432                                    openCLPresentationMutex.WaitOne();
433                                    ((QuickWatch)QuickWatchPresentation).OpenCLPresentation.AmountOfDevices--;
434                                    openCLPresentationMutex.ReleaseMutex();
435                                }, null);
436                                continue;
437                            }
438                        }
439                       
440                        int progress = keyTranslator.GetProgress();
441
442                        if (!useOpenCL)
443                        {
444                            doneKeysArray[threadid] += progress;
445                            keycounterArray[threadid] += progress;
446                            keysLeft[threadid] -= progress;
447                        }
448
449                    } while (!finish && !stop);
450
451                    if (stop)
452                        return;
453
454                    //Let's wait until another thread is willing to share with us:
455                    WaitForNewPattern(patterns, threadid, threadStack);
456                }
457            }
458            finally
459            {
460                sender.Dispose();
461                stopEvent.Set();
462            }
463        }
464
465        private unsafe bool BruteforceOpenCL(KeySearcherOpenCLCode keySearcherOpenCLCode, KeySearcherOpenCLSubbatchOptimizer keySearcherOpenCLSubbatchOptimizer, IKeyTranslator keyTranslator, IControlEncryption sender, int bytesToUse, object[] parameters)
466        {
467            int threadid = (int)parameters[1];
468            BigInteger[] doneKeysArray = (BigInteger[])parameters[2];
469            BigInteger[] openCLDoneKeysArray = (BigInteger[])parameters[3];
470            BigInteger[] keycounterArray = (BigInteger[])parameters[4];
471            BigInteger[] keysLeft = (BigInteger[])parameters[5];
472            try
473            {
474                Kernel bruteforceKernel = keySearcherOpenCLCode.GetBruteforceKernel(oclManager, keyTranslator);
475               
476                int deviceIndex = settings.OpenCLDevice;
477               
478                Mem userKey;
479                var key = keyTranslator.GetKey();
480                fixed (byte* ukp = key)
481                    userKey = oclManager.Context.CreateBuffer(MemFlags.USE_HOST_PTR, key.Length, new IntPtr((void*)ukp));
482
483                bruteforceKernel.SetArg(0, userKey);
484
485                int subbatches = keySearcherOpenCLSubbatchOptimizer.GetAmountOfSubbatches(keyTranslator);
486                int subbatchSize = keyTranslator.GetOpenCLBatchSize() / subbatches;
487                ((QuickWatch) QuickWatchPresentation).Dispatcher.BeginInvoke(DispatcherPriority.Normal, (SendOrPostCallback) delegate
488                                                                    {
489                                                                        ((QuickWatch)QuickWatchPresentation).OpenCLPresentation.batches.Content = subbatches;
490                                                                        ((QuickWatch)QuickWatchPresentation).OpenCLPresentation.threads.Content = subbatchSize;
491                                                                    }, null);
492                GuiLogMessage(string.Format("Now using {0} subbatches", subbatches), NotificationLevel.Info);
493               
494                float[] costArray = new float[subbatchSize];
495                Mem costs = oclManager.Context.CreateBuffer(MemFlags.READ_WRITE, costArray.Length * 4);
496                bruteforceKernel.SetArg(1, costs);
497
498                IntPtr[] globalWorkSize = { (IntPtr)subbatchSize };
499
500                keySearcherOpenCLSubbatchOptimizer.BeginMeasurement();
501
502                for (int i = 0; i < subbatches; i++)
503                {
504                    bruteforceKernel.SetArg(2, i * subbatchSize);
505                    oclManager.CQ[deviceIndex].EnqueueNDRangeKernel(bruteforceKernel, 1, null, globalWorkSize, null);
506                    oclManager.CQ[deviceIndex].EnqueueBarrier();
507
508                    Event e;
509                    fixed (float* costa = costArray)
510                        oclManager.CQ[deviceIndex].EnqueueReadBuffer(costs, true, 0, costArray.Length * 4, new IntPtr((void*)costa), 0, null, out e);
511
512                    e.Wait();
513
514                    checkOpenCLResults(keyTranslator, costArray, sender, bytesToUse, i * subbatchSize);
515
516                    doneKeysArray[threadid] += subbatchSize;
517                    openCLDoneKeysArray[threadid] += subbatchSize;
518                    keycounterArray[threadid] += subbatchSize;
519                    keysLeft[threadid] -= subbatchSize;
520                }
521
522                keySearcherOpenCLSubbatchOptimizer.EndMeasurement();
523
524                costs.Dispose();
525            }
526            catch (Exception ex)
527            {
528                GuiLogMessage(ex.Message, NotificationLevel.Error);
529                GuiLogMessage("Bruteforcing with OpenCL failed! Using CPU instead.", NotificationLevel.Error);
530                throw new Exception("Bruteforcing with OpenCL failed!");
531            }
532
533            return !keyTranslator.NextOpenCLBatch();
534        }
535
536        private void checkOpenCLResults(IKeyTranslator keyTranslator, float[] costArray, IControlEncryption sender, int bytesToUse, int add)
537        {
538            var op = this.costMaster.getRelationOperator();
539            for (int i = 0; i < costArray.Length; i++)
540            {
541                float cost = costArray[i];
542                if (((op == RelationOperator.LargerThen) && (cost > value_threshold))
543                    || (op == RelationOperator.LessThen) && (cost < value_threshold))
544                {
545                    ValueKey valueKey = new ValueKey { value = cost, key = keyTranslator.GetKeyRepresentation(i + add) };
546                    valueKey.keya = keyTranslator.GetKeyFromRepresentation(valueKey.key);
547                    valueKey.decryption = sender.Decrypt(this.encryptedData, valueKey.keya, InitVector, bytesToUse);
548                    valuequeue.Enqueue(valueKey);
549                }
550            }
551        }
552
553        private bool BruteforceCPU(IKeyTranslator keyTranslator, IControlEncryption sender, int bytesToUse)
554        {
555            bool finish = false;
556            for (int count = 0; count < 256 * 256; count++)
557            {
558                byte[] keya = keyTranslator.GetKey();
559
560                if (!decryptAndCalculate(sender, bytesToUse, keya, keyTranslator))
561                    throw new Exception("Bruteforcing not possible!");
562
563                finish = !keyTranslator.NextKey();
564                if (finish)
565                    break;
566            }
567            return finish;
568        }
569
570        private IKeyTranslator ShareKeys(KeyPattern.KeyPattern[] patterns, int threadid, BigInteger[] keysLeft, IKeyTranslator keyTranslator, Stack threadStack)
571        {
572            BigInteger size;
573            if (maxThread == threadid && threadStack.Count != 0)
574            {
575                try
576                {
577                    maxThreadMutex.WaitOne();
578                    if (maxThread == threadid && threadStack.Count != 0)
579                    {
580                        KeyPattern.KeyPattern[] split = patterns[threadid].split();
581                        if (split != null)
582                        {
583                            patterns[threadid] = split[0];
584                            keyTranslator = ControlMaster.getKeyTranslator();
585                            keyTranslator.SetKeys(patterns[threadid]);
586
587                            ThreadStackElement elem = (ThreadStackElement)threadStack.Pop();
588                            patterns[elem.threadid] = split[1];
589                            elem.ev.Set();    //wake the other thread up                                   
590                            size = patterns[threadid].size();
591                            keysLeft[threadid] = size;
592                        }
593                        maxThread = -1;
594                    }
595                }
596                finally
597                {
598                    maxThreadMutex.ReleaseMutex();
599                }
600            }
601            return keyTranslator;
602        }
603
604        private void WaitForNewPattern(KeyPattern.KeyPattern[] patterns, int threadid, Stack threadStack)
605        {
606            ThreadStackElement el = new ThreadStackElement();
607            el.ev = new AutoResetEvent(false);
608            el.threadid = threadid;
609            patterns[threadid] = null;
610            threadStack.Push(el);
611            GuiLogMessage("Thread waiting for new keys.", NotificationLevel.Debug);
612            el.ev.WaitOne();
613            if (!stop)
614            {
615                GuiLogMessage("Thread waking up with new keys.", NotificationLevel.Debug);
616            }
617        }
618
619        #region bruteforce methods
620
621        private bool decryptAndCalculate(IControlEncryption sender, int bytesToUse, byte[] keya, IKeyTranslator keyTranslator)
622        {
623            ValueKey valueKey;
624
625            try
626            {
627                if (this.encryptedData != null && this.encryptedData.Length > 0)
628                {
629                    valueKey.decryption = sender.Decrypt(this.encryptedData, keya, InitVector, bytesToUse);
630                }
631                else
632                {
633                    GuiLogMessage("Can't bruteforce empty input!", NotificationLevel.Error);
634                    return false;
635                }
636            }
637            catch (Exception ex)
638            {
639                GuiLogMessage("Decryption is not possible: " + ex.Message, NotificationLevel.Error);
640                GuiLogMessage("Stack Trace: " + ex.StackTrace, NotificationLevel.Error);
641                return false;
642            }
643
644            try
645            {
646                valueKey.value = CostMaster.calculateCost(valueKey.decryption);
647            }
648            catch (Exception ex)
649            {
650                GuiLogMessage("Cost calculation is not possible: " + ex.Message, NotificationLevel.Error);
651                return false;
652            }
653
654            if (this.costMaster.getRelationOperator() == RelationOperator.LargerThen)
655            {
656                if (valueKey.value > value_threshold)
657                {
658                    valueKey.key = keyTranslator.GetKeyRepresentation();
659                    valueKey.keya = (byte[])keya.Clone();
660                    valuequeue.Enqueue(valueKey);                   
661                }
662            }
663            else
664            {
665                if (valueKey.value < value_threshold)
666                {
667                    valueKey.key = keyTranslator.GetKeyRepresentation();
668                    valueKey.keya = (byte[])keya.Clone();                 
669                    valuequeue.Enqueue(valueKey);
670                }
671            }
672            return true;
673        }
674
675        #endregion
676
677        #endregion
678
679        public void process(IControlEncryption sender)
680        {
681            if (sender == null || costMaster == null)
682                return;
683            if (!Pattern.testWildcardKey(settings.Key))
684            {
685                GuiLogMessage("Wrong key pattern!", NotificationLevel.Error);
686                return;
687            }
688            Pattern.WildcardKey = settings.Key;
689            this.sender = sender;
690
691            bruteforcePattern(Pattern);
692        }
693
694        internal LinkedList<ValueKey> costList = new LinkedList<ValueKey>();
695        private int bytesToUse;
696        private IControlEncryption sender;
697        private DateTime beginBruteforcing;
698        private DistributedBruteForceManager distributedBruteForceManager;
699
700        // main entry point to the KeySearcher
701        private LinkedList<ValueKey> bruteforcePattern(KeyPattern.KeyPattern pattern)
702        {
703            beginBruteforcing = DateTime.Now;
704            GuiLogMessage("Start bruteforcing pattern '" + pattern.getKey() + "'", NotificationLevel.Debug);
705                       
706            int maxInList = 10;
707            costList = new LinkedList<ValueKey>();
708            fillListWithDummies(maxInList, costList);
709            valuequeue = Queue.Synchronized(new Queue());
710
711            stop = false;
712            if (!pattern.testWildcardKey(settings.Key))
713            {
714                GuiLogMessage("Wrong key pattern!", NotificationLevel.Error);
715                return null;
716            }
717
718            // bytesToUse = 0;
719
720            try
721            {
722                bytesToUse = CostMaster.getBytesToUse();
723            }
724            catch (Exception ex)
725            {
726                GuiLogMessage("Bytes used not valid: " + ex.Message, NotificationLevel.Error);
727                return null;
728            }
729
730            if (settings.UsePeerToPeer)
731            {
732                BruteForceWithPeerToPeerSystem();
733                return null;
734            }
735
736            return BruteForceWithLocalSystem(pattern);
737        }
738
739        private void BruteForceWithPeerToPeerSystem()
740        {
741            GuiLogMessage("Launching p2p based bruteforce logic...", NotificationLevel.Info);
742
743            try
744            {
745                distributedBruteForceManager = new DistributedBruteForceManager(this, pattern, settings,
746                                                                                keyQualityHelper,
747                                                                                p2PQuickWatchPresentation);
748                distributedBruteForceManager.Execute();
749            }
750            catch (NotConnectedException)
751            {
752                GuiLogMessage("P2P not connected.", NotificationLevel.Error);
753            }
754        }
755
756        internal LinkedList<ValueKey> BruteForceWithLocalSystem(KeyPattern.KeyPattern pattern, bool redirectResultsToStatisticsGenerator = false)
757        {
758            if (!redirectResultsToStatisticsGenerator)
759            {
760                localQuickWatchPresentation.Dispatcher.BeginInvoke(DispatcherPriority.Normal, new Action(SetStartDate));
761                localBruteForceStopwatch.Start();
762            }
763
764            BigInteger size = pattern.size();
765            KeyPattern.KeyPattern[] patterns = splitPatternForThreads(pattern);
766            if (patterns == null || patterns.Length == 0)
767            {
768                GuiLogMessage("No ressources to BruteForce available. Check the KeySearcher settings!", NotificationLevel.Error);
769                throw new Exception("No ressources to BruteForce available. Check the KeySearcher settings!");
770            }
771
772            BigInteger[] doneKeysA = new BigInteger[patterns.Length];
773            BigInteger[] openCLDoneKeysA = new BigInteger[patterns.Length];
774            BigInteger[] keycounters = new BigInteger[patterns.Length];
775            BigInteger[] keysleft = new BigInteger[patterns.Length];
776            Stack threadStack = Stack.Synchronized(new Stack());
777            threadsStopEvents = ArrayList.Synchronized(new ArrayList());
778            StartThreads(sender, bytesToUse, patterns, doneKeysA, openCLDoneKeysA, keycounters, keysleft, threadStack);
779
780            DateTime lastTime = DateTime.Now;
781
782            //update message:
783            while (!stop)
784            {
785                Thread.Sleep(2000);
786
787                updateToplist();
788
789                #region calculate global counters from local counters
790                BigInteger keycounter = 0;
791                BigInteger doneKeys = 0;
792                BigInteger openCLdoneKeys = 0;
793                foreach (BigInteger dk in doneKeysA)
794                    doneKeys += dk;
795                foreach (BigInteger dk in openCLDoneKeysA)
796                    openCLdoneKeys += dk;
797                foreach (BigInteger kc in keycounters)
798                    keycounter += kc;
799                #endregion
800
801                if (keycounter > size)
802                    GuiLogMessage("There must be an error, because we bruteforced too much keys...", NotificationLevel.Error);
803
804                #region determination of the thread with most keys
805                if (size - keycounter > 1000)
806                {
807                    try
808                    {
809                        maxThreadMutex.WaitOne();
810                        BigInteger max = 0;
811                        int id = -1;
812                        for (int i = 0; i < patterns.Length; i++)
813                            if (keysleft[i] != null && keysleft[i] > max)
814                            {
815                                max = keysleft[i];
816                                id = i;
817                            }
818                        maxThread = id;
819                    }
820                    finally
821                    {
822                        maxThreadMutex.ReleaseMutex();
823                    }
824                }
825                #endregion
826
827                long keysPerSecond = (long)((long)doneKeys/(DateTime.Now - lastTime).TotalSeconds);
828                long openCLKeysPerSecond = (long)((long)openCLdoneKeys / (DateTime.Now - lastTime).TotalSeconds);
829                lastTime = DateTime.Now;
830                if (redirectResultsToStatisticsGenerator)
831                {
832                    distributedBruteForceManager.StatisticsGenerator.ShowProgress(costList, size, keycounter, keysPerSecond);
833                }
834                else
835                {
836                    showProgress(costList, size, keycounter, keysPerSecond, openCLKeysPerSecond, (double)openCLdoneKeys / (double)doneKeys);
837                }
838               
839
840                #region set doneKeys to 0
841                doneKeys = 0;
842                for (int i = 0; i < doneKeysA.Length; i++)
843                    doneKeysA[i] = 0;
844                openCLdoneKeys = 0;
845                for (int i = 0; i < openCLDoneKeysA.Length; i++)
846                    openCLDoneKeysA[i] = 0;
847                #endregion
848
849                if (keycounter >= size)
850                    break;
851            }//end while
852
853            showProgress(costList, 1, 1, 1, 1, 1);
854
855            //wake up all sleeping threads, so they can stop:
856            while (threadStack.Count != 0)
857                ((ThreadStackElement)threadStack.Pop()).ev.Set();
858
859            //wait until all threads finished:
860            foreach (AutoResetEvent stopEvent in threadsStopEvents)
861            {
862                stopEvent.WaitOne();
863            }
864
865            if (!stop && !redirectResultsToStatisticsGenerator)
866                ProgressChanged(1, 1);
867
868            /* BEGIN: For evaluation issues - added by Arnold 2010.03.17 */
869            TimeSpan bruteforcingTime = DateTime.Now.Subtract(beginBruteforcing);
870            StringBuilder sbBFTime = new StringBuilder();
871            if (bruteforcingTime.Days > 0)
872                sbBFTime.Append(bruteforcingTime.Days.ToString() + " days ");
873            if (bruteforcingTime.Hours > 0)
874            {
875                if (bruteforcingTime.Hours <= 9)
876                    sbBFTime.Append("0");
877                sbBFTime.Append(bruteforcingTime.Hours.ToString() + ":");
878            }
879            if (bruteforcingTime.Minutes <= 9)
880                sbBFTime.Append("0");
881            sbBFTime.Append(bruteforcingTime.Minutes.ToString() + ":");
882            if (bruteforcingTime.Seconds <= 9)
883                sbBFTime.Append("0");
884            sbBFTime.Append(bruteforcingTime.Seconds.ToString() + "-");
885            if (bruteforcingTime.Milliseconds <= 9)
886                sbBFTime.Append("00");
887            if (bruteforcingTime.Milliseconds <= 99)
888                sbBFTime.Append("0");
889            sbBFTime.Append(bruteforcingTime.Milliseconds.ToString());
890
891            GuiLogMessage("Ended bruteforcing pattern '" + pattern.getKey() + "'. Bruteforcing TimeSpan: " + sbBFTime.ToString(), NotificationLevel.Debug);
892            /* END: For evaluation issues - added by Arnold 2010.03.17 */
893
894            return costList;
895        }
896
897
898
899        private void SetStartDate()
900        {
901            localQuickWatchPresentation.startTime.Content = DateTime.Now.ToString("g", Thread.CurrentThread.CurrentCulture); ;
902        }
903
904        internal void showProgress(LinkedList<ValueKey> costList, BigInteger size, BigInteger keycounter, long keysPerSecond, long openCLkeysPerSecond, double openclRatio)
905        {
906            System.Text.ASCIIEncoding enc = new System.Text.ASCIIEncoding();
907
908            LinkedListNode<ValueKey> linkedListNode;
909            ProgressChanged((double)keycounter / (double)size, 1.0);
910
911            if (localQuickWatchPresentation.IsVisible && keysPerSecond != 0 && !stop)
912            {
913                double time = (Math.Pow(10, BigInteger.Log((size - keycounter), 10) - Math.Log10(keysPerSecond)));
914                TimeSpan timeleft = new TimeSpan(-1);
915
916                try
917                {
918                    if (time / (24 * 60 * 60) <= int.MaxValue)
919                    {
920                        int days = (int)(time / (24 * 60 * 60));
921                        time = time - (days * 24 * 60 * 60);
922                        int hours = (int)(time / (60 * 60));
923                        time = time - (hours * 60 * 60);
924                        int minutes = (int)(time / 60);
925                        time = time - (minutes * 60);
926                        int seconds = (int)time;
927
928                        timeleft = new TimeSpan(days, hours, minutes, (int)seconds, 0);
929                    }
930                }
931                catch
932                {
933                    //can not calculate time span
934                }
935
936                localQuickWatchPresentation.Dispatcher.BeginInvoke(DispatcherPriority.Normal, (SendOrPostCallback)delegate
937                {
938                    localQuickWatchPresentation.elapsedTime.Content = localBruteForceStopwatch.Elapsed;
939                    localQuickWatchPresentation.keysPerSecond.Content = String.Format("{0:N}", keysPerSecond);
940                    if (timeleft != new TimeSpan(-1))
941                    {
942                        localQuickWatchPresentation.timeLeft.Content = "" + timeleft;
943                        try
944                        {
945                            localQuickWatchPresentation.endTime.Content = "" + DateTime.Now.Add(timeleft);
946                        }
947                        catch
948                        {
949                            localQuickWatchPresentation.endTime.Content = "in a galaxy far, far away...";
950                        }
951                    }
952                    else
953                    {
954                        localQuickWatchPresentation.timeLeft.Content = "incalculable :-)";
955                        localQuickWatchPresentation.endTime.Content = "in a galaxy far, far away...";
956                    }
957
958                    localQuickWatchPresentation.entries.Clear();
959                    linkedListNode = costList.First;
960
961                    int i = 0;
962                    while (linkedListNode != null)
963                    {
964                        i++;
965
966                        ResultEntry entry = new ResultEntry();
967                        entry.Ranking = "" + i;
968                        entry.Value = "" + Math.Round(linkedListNode.Value.value, 3);
969                        entry.Key = linkedListNode.Value.key;
970                        entry.Text = enc.GetString(linkedListNode.Value.decryption);
971
972                        localQuickWatchPresentation.entries.Add(entry);
973                        linkedListNode = linkedListNode.Next;
974                    }
975                }
976                , null);
977            }//end if
978
979
980            else if (!stop && localQuickWatchPresentation.IsVisible)
981            {
982
983                localQuickWatchPresentation.Dispatcher.BeginInvoke(DispatcherPriority.Normal, (SendOrPostCallback)delegate
984                {
985                    localQuickWatchPresentation.entries.Clear();
986                    linkedListNode = costList.First;
987                    int i = 0;
988
989                    while (linkedListNode != null)
990                    {
991                        i++;
992
993                        ResultEntry entry = new ResultEntry();
994                        entry.Ranking = "" + i;
995                        entry.Value = "" + Math.Round(linkedListNode.Value.value, 3);
996                        entry.Key = linkedListNode.Value.key;
997                        entry.Text = enc.GetString(linkedListNode.Value.decryption);
998
999                        localQuickWatchPresentation.entries.Add(entry);
1000                        linkedListNode = linkedListNode.Next;
1001                    }
1002                }
1003                , null);
1004            }
1005
1006            //show openCL keys/sec:
1007            ((QuickWatch)QuickWatchPresentation).Dispatcher.BeginInvoke(DispatcherPriority.Normal, (SendOrPostCallback)delegate
1008                    {
1009                        ((QuickWatch)QuickWatchPresentation).OpenCLPresentation.keysPerSecond.Content = String.Format("{0:N}", openCLkeysPerSecond);
1010                        ((QuickWatch)QuickWatchPresentation).OpenCLPresentation.ratio.Content = String.Format("{0:P}", openclRatio);
1011                    }, null);
1012
1013        }
1014
1015        #region For TopList
1016
1017        private void fillListWithDummies(int maxInList, LinkedList<ValueKey> costList)
1018        {
1019            ValueKey valueKey = new ValueKey();
1020            if (this.costMaster.getRelationOperator() == RelationOperator.LessThen)
1021                valueKey.value = double.MaxValue;
1022            else
1023                valueKey.value = double.MinValue;
1024            valueKey.key = "dummykey";
1025            valueKey.decryption = new byte[0];
1026            value_threshold = valueKey.value;
1027            LinkedListNode<ValueKey> node = costList.AddFirst(valueKey);
1028            for (int i = 1; i < maxInList; i++)
1029            {
1030                node = costList.AddAfter(node, valueKey);
1031            }
1032        }
1033
1034        internal void IntegrateNewResults(LinkedList<ValueKey> updatedCostList)
1035        {
1036            foreach (var valueKey in updatedCostList)
1037            {
1038                if (keyQualityHelper.IsBetter(valueKey.value, value_threshold))
1039                {
1040                    valuequeue.Enqueue(valueKey);
1041                }
1042            }
1043
1044            updateToplist();
1045        }
1046
1047        internal void updateToplist()
1048        {
1049            LinkedListNode<ValueKey> node;
1050            while (valuequeue.Count != 0)
1051            {
1052                ValueKey vk = (ValueKey)valuequeue.Dequeue();
1053
1054                //if (costList.Contains(vk)) continue;
1055                var result = costList.Where(valueKey => valueKey.key == vk.key);
1056                if (result.Count() > 0)
1057                {
1058                    continue;
1059                }
1060
1061                if (this.costMaster.getRelationOperator() == RelationOperator.LargerThen)
1062                {
1063                    if (vk.value > costList.Last().value)
1064                    {
1065                        node = costList.First;
1066                        while (node != null)
1067                        {
1068                            if (vk.value > node.Value.value)
1069                            {
1070                                if (node == costList.First)
1071                                    Top1 = vk;
1072                                costList.AddBefore(node, vk);
1073                                costList.RemoveLast();
1074                                value_threshold = costList.Last.Value.value;
1075                                break;
1076                            }
1077                            node = node.Next;
1078                        }//end while
1079                    }//end if
1080                }
1081                else
1082                {
1083                    if (vk.value < costList.Last().value)
1084                    {
1085                        node = costList.First;
1086                        while (node != null)
1087                        {
1088                            if (vk.value < node.Value.value)
1089                            {
1090                                if (node == costList.First)
1091                                    Top1 = vk;
1092                                costList.AddBefore(node, vk);
1093                                costList.RemoveLast();
1094                                value_threshold = costList.Last.Value.value;
1095                                break;
1096                            }
1097                            node = node.Next;
1098                        }//end while
1099                    }//end if
1100                }
1101            }
1102        }
1103
1104        #endregion
1105
1106        private void StartThreads(IControlEncryption sender, int bytesToUse, KeyPattern.KeyPattern[] patterns, BigInteger[] doneKeysA, BigInteger[] openCLDoneKeysA, BigInteger[] keycounters, BigInteger[] keysleft, Stack threadStack)
1107        {
1108            for (int i = 0; i < patterns.Length; i++)
1109            {
1110                WaitCallback worker = new WaitCallback(KeySearcherJob);
1111                doneKeysA[i] = new BigInteger();
1112                openCLDoneKeysA[i] = new BigInteger();
1113                keycounters[i] = new BigInteger();
1114                bool useOpenCL = false;
1115
1116                if (settings.UseOpenCL && (i == patterns.Length - 1))     //Last thread is the OpenCL thread
1117                    useOpenCL = true;
1118
1119                ThreadPool.QueueUserWorkItem(worker, new object[] { patterns, i, doneKeysA, openCLDoneKeysA, keycounters, keysleft, sender, bytesToUse, threadStack, useOpenCL });
1120            }
1121        }
1122
1123        private KeyPattern.KeyPattern[] splitPatternForThreads(KeyPattern.KeyPattern pattern)
1124        {
1125            int threads = settings.CoresUsed;
1126            if (settings.UseOpenCL)
1127                threads++;
1128
1129            if (threads < 1)
1130                return null;
1131
1132            KeyPattern.KeyPattern[] patterns = new KeyPattern.KeyPattern[threads];
1133            if (threads > 1)
1134            {
1135                KeyPattern.KeyPattern[] patterns2 = pattern.split();
1136                if (patterns2 == null)
1137                {
1138                    patterns2 = new KeyPattern.KeyPattern[1];
1139                    patterns2[0] = pattern;
1140                    return patterns2;
1141                }
1142                patterns[0] = patterns2[0];
1143                patterns[1] = patterns2[1];
1144                int p = 1;
1145                threads -= 2;
1146
1147                while (threads > 0)
1148                {
1149                    int maxPattern = -1;
1150                    BigInteger max = 0;
1151                    for (int i = 0; i <= p; i++)
1152                        if (patterns[i].size() > max)
1153                        {
1154                            max = patterns[i].size();
1155                            maxPattern = i;
1156                        }
1157                    KeyPattern.KeyPattern[] patterns3 = patterns[maxPattern].split();
1158                    if (patterns3 == null)
1159                    {
1160                        patterns3 = new KeyPattern.KeyPattern[p+1];
1161                        for (int i = 0; i <= p; i++)
1162                            patterns3[i] = patterns[i];
1163                        return patterns3;
1164                    }
1165                    patterns[maxPattern] = patterns3[0];
1166                    patterns[++p] = patterns3[1];
1167                    threads--;
1168                }
1169            }
1170            else
1171                patterns[0] = pattern;
1172            return patterns;
1173        }
1174
1175        private void keyPatternChanged()
1176        {
1177            Pattern = new KeyPattern.KeyPattern(controlMaster.getKeyPattern());
1178        }
1179
1180        // added by Arnie - 2009.12.07
1181        public delegate void BruteforcingEnded(LinkedList<ValueKey> top10List);
1182        /// <summary>
1183        /// This event gets thrown after Bruteforcing had ended. This is no evidence, that bruteforcing was successful.
1184        /// But when the returned List is filled, we have (at least a part) of the possible best keys
1185        /// </summary>
1186        public event BruteforcingEnded OnBruteforcingEnded;
1187
1188        // added by Arnie -2009.12.02
1189        // for inheritance reasons
1190        public void BruteforcePattern(KeyPattern.KeyPattern pattern, byte[] encryptedData, byte[] initVector, IControlEncryption encryptControl, IControlCost costControl)
1191        {
1192            /* Begin: New stuff because of changing the IControl data flow - Arnie 2010.01.18 */
1193            this.encryptedData = encryptedData;
1194            this.initVector = initVector;
1195            /* End: New stuff because of changing the IControl data flow - Arnie 2010.01.18 */
1196
1197            this.sender = encryptControl;
1198            LinkedList<ValueKey> lstRet = bruteforcePattern(pattern);
1199            if(OnBruteforcingEnded != null)
1200                OnBruteforcingEnded(lstRet);
1201        }
1202
1203        #endregion
1204
1205        public void GuiLogMessage(string message, NotificationLevel loglevel)
1206        {
1207            if (OnGuiLogNotificationOccured != null)
1208                OnGuiLogNotificationOccured(this, new GuiLogEventArgs(message, this, loglevel));
1209        }
1210
1211        public void ProgressChanged(double value, double max)
1212        {
1213            if (OnPluginProgressChanged != null)
1214            {
1215                OnPluginProgressChanged(this, new PluginProgressEventArgs(value, max));
1216
1217            }
1218        }
1219
1220        /// <summary>
1221        /// used for delivering the results from the worker threads to the main thread:
1222        /// </summary>
1223        public struct ValueKey
1224        {
1225            public double value;
1226            public String key;
1227            public byte[] decryption;
1228            public byte[] keya;
1229        };
1230    }
1231
1232    /// <summary>
1233    /// Represents one entry in our result list
1234    /// </summary>
1235    public class ResultEntry
1236    {
1237        public string Ranking { get; set; }
1238        public string Value { get; set; }
1239        public string Key { get; set; }
1240        public string Text { get; set; }
1241
1242    }
1243}
Note: See TracBrowser for help on using the repository browser.