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

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

keysearcher: better stop behaviour when using opencl

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