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

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

hopefully fixed keysearcher opencl bug now

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            //either byte[] CStream input or CryptoolStream Object input
302            if (encryptedData != null || csEncryptedData != null) //to prevent execution on initialization
303            {
304                if (ControlMaster != null)
305                    process(ControlMaster);
306                else
307                {
308                    GuiLogMessage("You have to connect the KeySearcher with the Decryption Control!", NotificationLevel.Warning);
309                }
310            }
311        }
312
313        public void PostExecution()
314        {
315        }
316
317        public void Pause()
318        {
319        }
320
321        public void Stop()
322        {
323            IsKeySearcherRunning = false;
324            stop = true;
325        }
326
327        public void Initialize()
328        {
329            settings.Initialize();
330        }
331
332        public void Dispose()
333        {
334        }
335
336        #endregion
337
338        #region INotifyPropertyChanged Members
339
340        public event PropertyChangedEventHandler PropertyChanged;
341
342        public void OnPropertyChanged(string name)
343        {
344            if (PropertyChanged != null)
345            {
346                PropertyChanged(this, new PropertyChangedEventArgs(name));
347            }
348        }
349
350        #endregion
351
352        #region whole KeySearcher functionality
353
354        private class ThreadStackElement
355        {
356            public AutoResetEvent ev;
357            public int threadid;
358        }
359
360        #region code for the worker threads
361
362        private void KeySearcherJob(object param)
363        {
364            AutoResetEvent stopEvent = new AutoResetEvent(false);
365            threadsStopEvents.Add(stopEvent);
366
367            object[] parameters = (object[])param;
368            KeyPattern.KeyPattern[] patterns = (KeyPattern.KeyPattern[])parameters[0];
369            int threadid = (int)parameters[1];
370            BigInteger[] doneKeysArray = (BigInteger[])parameters[2];
371            BigInteger[] openCLDoneKeysArray = (BigInteger[])parameters[3];
372            BigInteger[] keycounterArray = (BigInteger[])parameters[4];
373            BigInteger[] keysLeft = (BigInteger[])parameters[5];
374            IControlEncryption sender = (IControlEncryption)parameters[6];
375            int bytesToUse = (int)parameters[7];
376            Stack threadStack = (Stack)parameters[8];
377            bool useOpenCL = (bool)parameters[9];
378
379            KeySearcherOpenCLCode keySearcherOpenCLCode = null;
380            KeySearcherOpenCLSubbatchOptimizer keySearcherOpenCLSubbatchOptimizer = null;
381            if (useOpenCL)
382            {
383                keySearcherOpenCLCode = new KeySearcherOpenCLCode(this, encryptedData, sender, CostMaster, 256 * 256 * 256 * 16);
384                keySearcherOpenCLSubbatchOptimizer = new KeySearcherOpenCLSubbatchOptimizer(oclManager.CQ[settings.OpenCLDevice].Device.MaxWorkItemSizes.Aggregate(1, (x, y) => (x * (int)y)) / 2);
385                ((QuickWatch)QuickWatchPresentation).Dispatcher.BeginInvoke(DispatcherPriority.Normal, (SendOrPostCallback)delegate
386                {
387                    openCLPresentationMutex.WaitOne();
388                    ((QuickWatch)QuickWatchPresentation).OpenCLPresentation.AmountOfDevices++;
389                    openCLPresentationMutex.ReleaseMutex();
390                }, null);
391            }
392
393            try
394            {
395                while (patterns[threadid] != null)
396                {
397                    BigInteger size = patterns[threadid].size();
398                    keysLeft[threadid] = size;
399                   
400                    IKeyTranslator keyTranslator = ControlMaster.getKeyTranslator();
401                    keyTranslator.SetKeys(patterns[threadid]);
402
403                    bool finish = false;
404
405                    do
406                    {
407                        //if we are the thread with most keys left, we have to share them:
408                        keyTranslator = ShareKeys(patterns, threadid, keysLeft, keyTranslator, threadStack);
409
410                        if (!useOpenCL)         //CPU
411                        {
412                            finish = BruteforceCPU(keyTranslator, sender, bytesToUse);
413                        }
414                        else                    //OpenCL
415                        {
416                            try
417                            {
418                                finish = BruteforceOpenCL(keySearcherOpenCLCode, keySearcherOpenCLSubbatchOptimizer, keyTranslator, sender, bytesToUse, parameters);
419                            }
420                            catch (Exception)
421                            {
422                                useOpenCL = false;
423                                ((QuickWatch)QuickWatchPresentation).Dispatcher.BeginInvoke(DispatcherPriority.Normal, (SendOrPostCallback)delegate
424                                {
425                                    openCLPresentationMutex.WaitOne();
426                                    ((QuickWatch)QuickWatchPresentation).OpenCLPresentation.AmountOfDevices--;
427                                    openCLPresentationMutex.ReleaseMutex();
428                                }, null);
429                                continue;
430                            }
431                        }
432                       
433                        int progress = keyTranslator.GetProgress();
434
435                        if (!useOpenCL)
436                        {
437                            doneKeysArray[threadid] += progress;
438                            keycounterArray[threadid] += progress;
439                            keysLeft[threadid] -= progress;
440                        }
441
442                    } while (!finish && !stop);
443
444                    if (stop)
445                        return;
446
447                    //Let's wait until another thread is willing to share with us:
448                    WaitForNewPattern(patterns, threadid, threadStack);
449                }
450            }
451            finally
452            {
453                sender.Dispose();
454                stopEvent.Set();
455            }
456        }
457
458        private unsafe bool BruteforceOpenCL(KeySearcherOpenCLCode keySearcherOpenCLCode, KeySearcherOpenCLSubbatchOptimizer keySearcherOpenCLSubbatchOptimizer, IKeyTranslator keyTranslator, IControlEncryption sender, int bytesToUse, object[] parameters)
459        {
460            int threadid = (int)parameters[1];
461            BigInteger[] doneKeysArray = (BigInteger[])parameters[2];
462            BigInteger[] openCLDoneKeysArray = (BigInteger[])parameters[3];
463            BigInteger[] keycounterArray = (BigInteger[])parameters[4];
464            BigInteger[] keysLeft = (BigInteger[])parameters[5];
465            try
466            {
467                Kernel bruteforceKernel = keySearcherOpenCLCode.GetBruteforceKernel(oclManager, keyTranslator);
468               
469                int deviceIndex = settings.OpenCLDevice;
470               
471                Mem userKey;
472                var key = keyTranslator.GetKey();
473                fixed (byte* ukp = key)
474                    userKey = oclManager.Context.CreateBuffer(MemFlags.USE_HOST_PTR, key.Length, new IntPtr((void*)ukp));
475
476               
477
478                int subbatches = keySearcherOpenCLSubbatchOptimizer.GetAmountOfSubbatches(keyTranslator);
479                int subbatchSize = keyTranslator.GetOpenCLBatchSize() / subbatches;
480                ((QuickWatch) QuickWatchPresentation).Dispatcher.BeginInvoke(DispatcherPriority.Normal, (SendOrPostCallback) delegate
481                                                                    {
482                                                                        ((QuickWatch)QuickWatchPresentation).OpenCLPresentation.batches.Content = subbatches;
483                                                                        ((QuickWatch)QuickWatchPresentation).OpenCLPresentation.threads.Content = subbatchSize;
484                                                                    }, null);
485                GuiLogMessage(string.Format("Now using {0} subbatches", subbatches), NotificationLevel.Info);
486               
487                float[] costArray = new float[subbatchSize];
488                Mem costs = oclManager.Context.CreateBuffer(MemFlags.READ_WRITE, costArray.Length * 4);
489               
490
491                IntPtr[] globalWorkSize = { (IntPtr)subbatchSize };
492
493                keySearcherOpenCLSubbatchOptimizer.BeginMeasurement();
494
495                for (int i = 0; i < subbatches; i++)
496                {
497                    bruteforceKernel.SetArg(0, userKey);
498                    bruteforceKernel.SetArg(1, costs);
499                    bruteforceKernel.SetArg(2, i * subbatchSize);
500                    oclManager.CQ[deviceIndex].EnqueueNDRangeKernel(bruteforceKernel, 1, null, globalWorkSize, null);
501                    oclManager.CQ[deviceIndex].EnqueueBarrier();
502
503                    Event e;
504                    fixed (float* costa = costArray)
505                        oclManager.CQ[deviceIndex].EnqueueReadBuffer(costs, true, 0, costArray.Length * 4, new IntPtr((void*)costa), 0, null, out e);
506
507                    e.Wait();
508
509                    checkOpenCLResults(keyTranslator, costArray, sender, bytesToUse, i * subbatchSize);
510
511                    doneKeysArray[threadid] += subbatchSize;
512                    openCLDoneKeysArray[threadid] += subbatchSize;
513                    keycounterArray[threadid] += subbatchSize;
514                    keysLeft[threadid] -= subbatchSize;
515                }
516
517                keySearcherOpenCLSubbatchOptimizer.EndMeasurement();
518
519                costs.Dispose();
520            }
521            catch (Exception ex)
522            {
523                GuiLogMessage(ex.Message, NotificationLevel.Error);
524                GuiLogMessage("Bruteforcing with OpenCL failed! Using CPU instead.", NotificationLevel.Error);
525                throw new Exception("Bruteforcing with OpenCL failed!");
526            }
527
528            return !keyTranslator.NextOpenCLBatch();
529        }
530
531        private void checkOpenCLResults(IKeyTranslator keyTranslator, float[] costArray, IControlEncryption sender, int bytesToUse, int add)
532        {
533            var op = this.costMaster.getRelationOperator();
534            for (int i = 0; i < costArray.Length; i++)
535            {
536                float cost = costArray[i];
537                if (((op == RelationOperator.LargerThen) && (cost > value_threshold))
538                    || (op == RelationOperator.LessThen) && (cost < value_threshold))
539                {
540                    ValueKey valueKey = new ValueKey { value = cost, key = keyTranslator.GetKeyRepresentation(i + add) };
541                    valueKey.keya = keyTranslator.GetKeyFromRepresentation(valueKey.key);
542                    valueKey.decryption = sender.Decrypt(this.encryptedData, valueKey.keya, InitVector, bytesToUse);
543                    valuequeue.Enqueue(valueKey);
544                }
545            }
546        }
547
548        private bool BruteforceCPU(IKeyTranslator keyTranslator, IControlEncryption sender, int bytesToUse)
549        {
550            bool finish = false;
551            for (int count = 0; count < 256 * 256; count++)
552            {
553                byte[] keya = keyTranslator.GetKey();
554
555                if (!decryptAndCalculate(sender, bytesToUse, keya, keyTranslator))
556                    throw new Exception("Bruteforcing not possible!");
557
558                finish = !keyTranslator.NextKey();
559                if (finish)
560                    break;
561            }
562            return finish;
563        }
564
565        private IKeyTranslator ShareKeys(KeyPattern.KeyPattern[] patterns, int threadid, BigInteger[] keysLeft, IKeyTranslator keyTranslator, Stack threadStack)
566        {
567            BigInteger size;
568            if (maxThread == threadid && threadStack.Count != 0)
569            {
570                try
571                {
572                    maxThreadMutex.WaitOne();
573                    if (maxThread == threadid && threadStack.Count != 0)
574                    {
575                        KeyPattern.KeyPattern[] split = patterns[threadid].split();
576                        if (split != null)
577                        {
578                            patterns[threadid] = split[0];
579                            keyTranslator = ControlMaster.getKeyTranslator();
580                            keyTranslator.SetKeys(patterns[threadid]);
581
582                            ThreadStackElement elem = (ThreadStackElement)threadStack.Pop();
583                            patterns[elem.threadid] = split[1];
584                            elem.ev.Set();    //wake the other thread up                                   
585                            size = patterns[threadid].size();
586                            keysLeft[threadid] = size;
587                        }
588                        maxThread = -1;
589                    }
590                }
591                finally
592                {
593                    maxThreadMutex.ReleaseMutex();
594                }
595            }
596            return keyTranslator;
597        }
598
599        private void WaitForNewPattern(KeyPattern.KeyPattern[] patterns, int threadid, Stack threadStack)
600        {
601            ThreadStackElement el = new ThreadStackElement();
602            el.ev = new AutoResetEvent(false);
603            el.threadid = threadid;
604            patterns[threadid] = null;
605            threadStack.Push(el);
606            GuiLogMessage("Thread waiting for new keys.", NotificationLevel.Debug);
607            el.ev.WaitOne();
608            if (!stop)
609            {
610                GuiLogMessage("Thread waking up with new keys.", NotificationLevel.Debug);
611            }
612        }
613
614        #region bruteforce methods
615
616        private bool decryptAndCalculate(IControlEncryption sender, int bytesToUse, byte[] keya, IKeyTranslator keyTranslator)
617        {
618            ValueKey valueKey;
619
620            try
621            {
622                if (this.encryptedData != null && this.encryptedData.Length > 0)
623                {
624                    valueKey.decryption = sender.Decrypt(this.encryptedData, keya, InitVector, bytesToUse);
625                }
626                else
627                {
628                    GuiLogMessage("Can't bruteforce empty input!", NotificationLevel.Error);
629                    return false;
630                }
631            }
632            catch (Exception ex)
633            {
634                GuiLogMessage("Decryption is not possible: " + ex.Message, NotificationLevel.Error);
635                GuiLogMessage("Stack Trace: " + ex.StackTrace, NotificationLevel.Error);
636                return false;
637            }
638
639            try
640            {
641                valueKey.value = CostMaster.calculateCost(valueKey.decryption);
642            }
643            catch (Exception ex)
644            {
645                GuiLogMessage("Cost calculation is not possible: " + ex.Message, NotificationLevel.Error);
646                return false;
647            }
648
649            if (this.costMaster.getRelationOperator() == RelationOperator.LargerThen)
650            {
651                if (valueKey.value > value_threshold)
652                {
653                    valueKey.key = keyTranslator.GetKeyRepresentation();
654                    valueKey.keya = (byte[])keya.Clone();
655                    valuequeue.Enqueue(valueKey);                   
656                }
657            }
658            else
659            {
660                if (valueKey.value < value_threshold)
661                {
662                    valueKey.key = keyTranslator.GetKeyRepresentation();
663                    valueKey.keya = (byte[])keya.Clone();                 
664                    valuequeue.Enqueue(valueKey);
665                }
666            }
667            return true;
668        }
669
670        #endregion
671
672        #endregion
673
674        public void process(IControlEncryption sender)
675        {
676            if (sender == null || costMaster == null)
677                return;
678            if (!Pattern.testWildcardKey(settings.Key))
679            {
680                GuiLogMessage("Wrong key pattern!", NotificationLevel.Error);
681                return;
682            }
683            Pattern.WildcardKey = settings.Key;
684            this.sender = sender;
685
686            bruteforcePattern(Pattern);
687        }
688
689        internal LinkedList<ValueKey> costList = new LinkedList<ValueKey>();
690        private int bytesToUse;
691        private IControlEncryption sender;
692        private DateTime beginBruteforcing;
693        private DistributedBruteForceManager distributedBruteForceManager;
694
695        // main entry point to the KeySearcher
696        private LinkedList<ValueKey> bruteforcePattern(KeyPattern.KeyPattern pattern)
697        {
698            beginBruteforcing = DateTime.Now;
699            GuiLogMessage("Start bruteforcing pattern '" + pattern.getKey() + "'", NotificationLevel.Debug);
700                       
701            int maxInList = 10;
702            costList = new LinkedList<ValueKey>();
703            fillListWithDummies(maxInList, costList);
704            valuequeue = Queue.Synchronized(new Queue());
705
706            stop = false;
707            if (!pattern.testWildcardKey(settings.Key))
708            {
709                GuiLogMessage("Wrong key pattern!", NotificationLevel.Error);
710                return null;
711            }
712
713            // bytesToUse = 0;
714
715            try
716            {
717                bytesToUse = CostMaster.getBytesToUse();
718            }
719            catch (Exception ex)
720            {
721                GuiLogMessage("Bytes used not valid: " + ex.Message, NotificationLevel.Error);
722                return null;
723            }
724
725            if (settings.UsePeerToPeer)
726            {
727                BruteForceWithPeerToPeerSystem();
728                return null;
729            }
730
731            return BruteForceWithLocalSystem(pattern);
732        }
733
734        private void BruteForceWithPeerToPeerSystem()
735        {
736            GuiLogMessage("Launching p2p based bruteforce logic...", NotificationLevel.Info);
737
738            try
739            {
740                distributedBruteForceManager = new DistributedBruteForceManager(this, pattern, settings,
741                                                                                keyQualityHelper,
742                                                                                p2PQuickWatchPresentation);
743                distributedBruteForceManager.Execute();
744            }
745            catch (NotConnectedException)
746            {
747                GuiLogMessage("P2P not connected.", NotificationLevel.Error);
748            }
749        }
750
751        internal LinkedList<ValueKey> BruteForceWithLocalSystem(KeyPattern.KeyPattern pattern, bool redirectResultsToStatisticsGenerator = false)
752        {
753            ((QuickWatch)QuickWatchPresentation).Dispatcher.BeginInvoke(DispatcherPriority.Normal, (SendOrPostCallback)delegate
754            {
755                openCLPresentationMutex.WaitOne();
756                ((QuickWatch)QuickWatchPresentation).OpenCLPresentation.AmountOfDevices = 0;
757                openCLPresentationMutex.ReleaseMutex();
758            }, null);
759
760            if (!redirectResultsToStatisticsGenerator)
761            {
762                localQuickWatchPresentation.Dispatcher.BeginInvoke(DispatcherPriority.Normal, new Action(SetStartDate));
763                localBruteForceStopwatch.Start();
764            }
765
766            BigInteger size = pattern.size();
767            KeyPattern.KeyPattern[] patterns = splitPatternForThreads(pattern);
768            if (patterns == null || patterns.Length == 0)
769            {
770                GuiLogMessage("No ressources to BruteForce available. Check the KeySearcher settings!", NotificationLevel.Error);
771                throw new Exception("No ressources to BruteForce available. Check the KeySearcher settings!");
772            }
773
774            BigInteger[] doneKeysA = new BigInteger[patterns.Length];
775            BigInteger[] openCLDoneKeysA = new BigInteger[patterns.Length];
776            BigInteger[] keycounters = new BigInteger[patterns.Length];
777            BigInteger[] keysleft = new BigInteger[patterns.Length];
778            Stack threadStack = Stack.Synchronized(new Stack());
779            threadsStopEvents = ArrayList.Synchronized(new ArrayList());
780            StartThreads(sender, bytesToUse, patterns, doneKeysA, openCLDoneKeysA, keycounters, keysleft, threadStack);
781
782            DateTime lastTime = DateTime.Now;
783
784            //update message:
785            while (!stop)
786            {
787                Thread.Sleep(2000);
788
789                updateToplist();
790
791                #region calculate global counters from local counters
792                BigInteger keycounter = 0;
793                BigInteger doneKeys = 0;
794                BigInteger openCLdoneKeys = 0;
795                foreach (BigInteger dk in doneKeysA)
796                    doneKeys += dk;
797                foreach (BigInteger dk in openCLDoneKeysA)
798                    openCLdoneKeys += dk;
799                foreach (BigInteger kc in keycounters)
800                    keycounter += kc;
801                #endregion
802
803                if (keycounter > size)
804                    GuiLogMessage("There must be an error, because we bruteforced too much keys...", NotificationLevel.Error);
805
806                #region determination of the thread with most keys
807                if (size - keycounter > 1000)
808                {
809                    try
810                    {
811                        maxThreadMutex.WaitOne();
812                        BigInteger max = 0;
813                        int id = -1;
814                        for (int i = 0; i < patterns.Length; i++)
815                            if (keysleft[i] != null && keysleft[i] > max)
816                            {
817                                max = keysleft[i];
818                                id = i;
819                            }
820                        maxThread = id;
821                    }
822                    finally
823                    {
824                        maxThreadMutex.ReleaseMutex();
825                    }
826                }
827                #endregion
828
829                long keysPerSecond = (long)((long)doneKeys/(DateTime.Now - lastTime).TotalSeconds);
830                long openCLKeysPerSecond = (long)((long)openCLdoneKeys / (DateTime.Now - lastTime).TotalSeconds);
831                lastTime = DateTime.Now;
832                if (redirectResultsToStatisticsGenerator)
833                {
834                    distributedBruteForceManager.StatisticsGenerator.ShowProgress(costList, size, keycounter, keysPerSecond);
835                }
836                else
837                {
838                    showProgress(costList, size, keycounter, keysPerSecond, openCLKeysPerSecond, (double)openCLdoneKeys / (double)doneKeys);
839                }
840               
841
842                #region set doneKeys to 0
843                doneKeys = 0;
844                for (int i = 0; i < doneKeysA.Length; i++)
845                    doneKeysA[i] = 0;
846                openCLdoneKeys = 0;
847                for (int i = 0; i < openCLDoneKeysA.Length; i++)
848                    openCLDoneKeysA[i] = 0;
849                #endregion
850
851                if (keycounter >= size)
852                    break;
853            }//end while
854
855            showProgress(costList, 1, 1, 1, 1, 1);
856
857            //wake up all sleeping threads, so they can stop:
858            while (threadStack.Count != 0)
859                ((ThreadStackElement)threadStack.Pop()).ev.Set();
860
861            //wait until all threads finished:
862            foreach (AutoResetEvent stopEvent in threadsStopEvents)
863            {
864                stopEvent.WaitOne();
865            }
866
867            if (!stop && !redirectResultsToStatisticsGenerator)
868                ProgressChanged(1, 1);
869
870            /* BEGIN: For evaluation issues - added by Arnold 2010.03.17 */
871            TimeSpan bruteforcingTime = DateTime.Now.Subtract(beginBruteforcing);
872            StringBuilder sbBFTime = new StringBuilder();
873            if (bruteforcingTime.Days > 0)
874                sbBFTime.Append(bruteforcingTime.Days.ToString() + " days ");
875            if (bruteforcingTime.Hours > 0)
876            {
877                if (bruteforcingTime.Hours <= 9)
878                    sbBFTime.Append("0");
879                sbBFTime.Append(bruteforcingTime.Hours.ToString() + ":");
880            }
881            if (bruteforcingTime.Minutes <= 9)
882                sbBFTime.Append("0");
883            sbBFTime.Append(bruteforcingTime.Minutes.ToString() + ":");
884            if (bruteforcingTime.Seconds <= 9)
885                sbBFTime.Append("0");
886            sbBFTime.Append(bruteforcingTime.Seconds.ToString() + "-");
887            if (bruteforcingTime.Milliseconds <= 9)
888                sbBFTime.Append("00");
889            if (bruteforcingTime.Milliseconds <= 99)
890                sbBFTime.Append("0");
891            sbBFTime.Append(bruteforcingTime.Milliseconds.ToString());
892
893            GuiLogMessage("Ended bruteforcing pattern '" + pattern.getKey() + "'. Bruteforcing TimeSpan: " + sbBFTime.ToString(), NotificationLevel.Debug);
894            /* END: For evaluation issues - added by Arnold 2010.03.17 */
895
896            return costList;
897        }
898
899
900
901        private void SetStartDate()
902        {
903            localQuickWatchPresentation.startTime.Content = DateTime.Now.ToString("g", Thread.CurrentThread.CurrentCulture); ;
904        }
905
906        internal void showProgress(LinkedList<ValueKey> costList, BigInteger size, BigInteger keycounter, long keysPerSecond, long openCLkeysPerSecond, double openclRatio)
907        {
908            System.Text.ASCIIEncoding enc = new System.Text.ASCIIEncoding();
909
910            LinkedListNode<ValueKey> linkedListNode;
911            ProgressChanged((double)keycounter / (double)size, 1.0);
912
913            if (localQuickWatchPresentation.IsVisible && keysPerSecond != 0 && !stop)
914            {
915                double time = (Math.Pow(10, BigInteger.Log((size - keycounter), 10) - Math.Log10(keysPerSecond)));
916                TimeSpan timeleft = new TimeSpan(-1);
917
918                try
919                {
920                    if (time / (24 * 60 * 60) <= int.MaxValue)
921                    {
922                        int days = (int)(time / (24 * 60 * 60));
923                        time = time - (days * 24 * 60 * 60);
924                        int hours = (int)(time / (60 * 60));
925                        time = time - (hours * 60 * 60);
926                        int minutes = (int)(time / 60);
927                        time = time - (minutes * 60);
928                        int seconds = (int)time;
929
930                        timeleft = new TimeSpan(days, hours, minutes, (int)seconds, 0);
931                    }
932                }
933                catch
934                {
935                    //can not calculate time span
936                }
937
938                localQuickWatchPresentation.Dispatcher.BeginInvoke(DispatcherPriority.Normal, (SendOrPostCallback)delegate
939                {
940                    localQuickWatchPresentation.elapsedTime.Content = localBruteForceStopwatch.Elapsed;
941                    localQuickWatchPresentation.keysPerSecond.Content = String.Format("{0:N}", keysPerSecond);
942                    if (timeleft != new TimeSpan(-1))
943                    {
944                        localQuickWatchPresentation.timeLeft.Content = "" + timeleft;
945                        try
946                        {
947                            localQuickWatchPresentation.endTime.Content = "" + DateTime.Now.Add(timeleft);
948                        }
949                        catch
950                        {
951                            localQuickWatchPresentation.endTime.Content = "in a galaxy far, far away...";
952                        }
953                    }
954                    else
955                    {
956                        localQuickWatchPresentation.timeLeft.Content = "incalculable :-)";
957                        localQuickWatchPresentation.endTime.Content = "in a galaxy far, far away...";
958                    }
959
960                    localQuickWatchPresentation.entries.Clear();
961                    linkedListNode = costList.First;
962
963                    int i = 0;
964                    while (linkedListNode != null)
965                    {
966                        i++;
967
968                        ResultEntry entry = new ResultEntry();
969                        entry.Ranking = "" + i;
970                        entry.Value = "" + Math.Round(linkedListNode.Value.value, 3);
971                        entry.Key = linkedListNode.Value.key;
972                        entry.Text = enc.GetString(linkedListNode.Value.decryption);
973
974                        localQuickWatchPresentation.entries.Add(entry);
975                        linkedListNode = linkedListNode.Next;
976                    }
977                }
978                , null);
979            }//end if
980
981
982            else if (!stop && localQuickWatchPresentation.IsVisible)
983            {
984
985                localQuickWatchPresentation.Dispatcher.BeginInvoke(DispatcherPriority.Normal, (SendOrPostCallback)delegate
986                {
987                    localQuickWatchPresentation.entries.Clear();
988                    linkedListNode = costList.First;
989                    int i = 0;
990
991                    while (linkedListNode != null)
992                    {
993                        i++;
994
995                        ResultEntry entry = new ResultEntry();
996                        entry.Ranking = "" + i;
997                        entry.Value = "" + Math.Round(linkedListNode.Value.value, 3);
998                        entry.Key = linkedListNode.Value.key;
999                        entry.Text = enc.GetString(linkedListNode.Value.decryption);
1000
1001                        localQuickWatchPresentation.entries.Add(entry);
1002                        linkedListNode = linkedListNode.Next;
1003                    }
1004                }
1005                , null);
1006            }
1007
1008            //show openCL keys/sec:
1009            ((QuickWatch)QuickWatchPresentation).Dispatcher.BeginInvoke(DispatcherPriority.Normal, (SendOrPostCallback)delegate
1010                    {
1011                        ((QuickWatch)QuickWatchPresentation).OpenCLPresentation.keysPerSecond.Content = String.Format("{0:N}", openCLkeysPerSecond);
1012                        ((QuickWatch)QuickWatchPresentation).OpenCLPresentation.ratio.Content = String.Format("{0:P}", openclRatio);
1013                    }, null);
1014
1015        }
1016
1017        #region For TopList
1018
1019        private void fillListWithDummies(int maxInList, LinkedList<ValueKey> costList)
1020        {
1021            ValueKey valueKey = new ValueKey();
1022            if (this.costMaster.getRelationOperator() == RelationOperator.LessThen)
1023                valueKey.value = double.MaxValue;
1024            else
1025                valueKey.value = double.MinValue;
1026            valueKey.key = "dummykey";
1027            valueKey.decryption = new byte[0];
1028            value_threshold = valueKey.value;
1029            LinkedListNode<ValueKey> node = costList.AddFirst(valueKey);
1030            for (int i = 1; i < maxInList; i++)
1031            {
1032                node = costList.AddAfter(node, valueKey);
1033            }
1034        }
1035
1036        internal void IntegrateNewResults(LinkedList<ValueKey> updatedCostList)
1037        {
1038            foreach (var valueKey in updatedCostList)
1039            {
1040                if (keyQualityHelper.IsBetter(valueKey.value, value_threshold))
1041                {
1042                    valuequeue.Enqueue(valueKey);
1043                }
1044            }
1045
1046            updateToplist();
1047        }
1048
1049        internal void updateToplist()
1050        {
1051            LinkedListNode<ValueKey> node;
1052            while (valuequeue.Count != 0)
1053            {
1054                ValueKey vk = (ValueKey)valuequeue.Dequeue();
1055
1056                //if (costList.Contains(vk)) continue;
1057                var result = costList.Where(valueKey => valueKey.key == vk.key);
1058                if (result.Count() > 0)
1059                {
1060                    continue;
1061                }
1062
1063                if (this.costMaster.getRelationOperator() == RelationOperator.LargerThen)
1064                {
1065                    if (vk.value > costList.Last().value)
1066                    {
1067                        node = costList.First;
1068                        while (node != null)
1069                        {
1070                            if (vk.value > node.Value.value)
1071                            {
1072                                if (node == costList.First)
1073                                    Top1 = vk;
1074                                costList.AddBefore(node, vk);
1075                                costList.RemoveLast();
1076                                value_threshold = costList.Last.Value.value;
1077                                break;
1078                            }
1079                            node = node.Next;
1080                        }//end while
1081                    }//end if
1082                }
1083                else
1084                {
1085                    if (vk.value < costList.Last().value)
1086                    {
1087                        node = costList.First;
1088                        while (node != null)
1089                        {
1090                            if (vk.value < node.Value.value)
1091                            {
1092                                if (node == costList.First)
1093                                    Top1 = vk;
1094                                costList.AddBefore(node, vk);
1095                                costList.RemoveLast();
1096                                value_threshold = costList.Last.Value.value;
1097                                break;
1098                            }
1099                            node = node.Next;
1100                        }//end while
1101                    }//end if
1102                }
1103            }
1104        }
1105
1106        #endregion
1107
1108        private void StartThreads(IControlEncryption sender, int bytesToUse, KeyPattern.KeyPattern[] patterns, BigInteger[] doneKeysA, BigInteger[] openCLDoneKeysA, BigInteger[] keycounters, BigInteger[] keysleft, Stack threadStack)
1109        {
1110            for (int i = 0; i < patterns.Length; i++)
1111            {
1112                WaitCallback worker = new WaitCallback(KeySearcherJob);
1113                doneKeysA[i] = new BigInteger();
1114                openCLDoneKeysA[i] = new BigInteger();
1115                keycounters[i] = new BigInteger();
1116                bool useOpenCL = false;
1117
1118                if (settings.UseOpenCL && (i == patterns.Length - 1))     //Last thread is the OpenCL thread
1119                    useOpenCL = true;
1120
1121                ThreadPool.QueueUserWorkItem(worker, new object[] { patterns, i, doneKeysA, openCLDoneKeysA, keycounters, keysleft, sender, bytesToUse, threadStack, useOpenCL });
1122            }
1123        }
1124
1125        private KeyPattern.KeyPattern[] splitPatternForThreads(KeyPattern.KeyPattern pattern)
1126        {
1127            int threads = settings.CoresUsed;
1128            if (settings.UseOpenCL)
1129                threads++;
1130
1131            if (threads < 1)
1132                return null;
1133
1134            KeyPattern.KeyPattern[] patterns = new KeyPattern.KeyPattern[threads];
1135            if (threads > 1)
1136            {
1137                KeyPattern.KeyPattern[] patterns2 = pattern.split();
1138                if (patterns2 == null)
1139                {
1140                    patterns2 = new KeyPattern.KeyPattern[1];
1141                    patterns2[0] = pattern;
1142                    return patterns2;
1143                }
1144                patterns[0] = patterns2[0];
1145                patterns[1] = patterns2[1];
1146                int p = 1;
1147                threads -= 2;
1148
1149                while (threads > 0)
1150                {
1151                    int maxPattern = -1;
1152                    BigInteger max = 0;
1153                    for (int i = 0; i <= p; i++)
1154                        if (patterns[i].size() > max)
1155                        {
1156                            max = patterns[i].size();
1157                            maxPattern = i;
1158                        }
1159                    KeyPattern.KeyPattern[] patterns3 = patterns[maxPattern].split();
1160                    if (patterns3 == null)
1161                    {
1162                        patterns3 = new KeyPattern.KeyPattern[p+1];
1163                        for (int i = 0; i <= p; i++)
1164                            patterns3[i] = patterns[i];
1165                        return patterns3;
1166                    }
1167                    patterns[maxPattern] = patterns3[0];
1168                    patterns[++p] = patterns3[1];
1169                    threads--;
1170                }
1171            }
1172            else
1173                patterns[0] = pattern;
1174            return patterns;
1175        }
1176
1177        private void keyPatternChanged()
1178        {
1179            Pattern = new KeyPattern.KeyPattern(controlMaster.getKeyPattern());
1180        }
1181
1182        // added by Arnie - 2009.12.07
1183        public delegate void BruteforcingEnded(LinkedList<ValueKey> top10List);
1184        /// <summary>
1185        /// This event gets thrown after Bruteforcing had ended. This is no evidence, that bruteforcing was successful.
1186        /// But when the returned List is filled, we have (at least a part) of the possible best keys
1187        /// </summary>
1188        public event BruteforcingEnded OnBruteforcingEnded;
1189
1190        // added by Arnie -2009.12.02
1191        // for inheritance reasons
1192        public void BruteforcePattern(KeyPattern.KeyPattern pattern, byte[] encryptedData, byte[] initVector, IControlEncryption encryptControl, IControlCost costControl)
1193        {
1194            /* Begin: New stuff because of changing the IControl data flow - Arnie 2010.01.18 */
1195            this.encryptedData = encryptedData;
1196            this.initVector = initVector;
1197            /* End: New stuff because of changing the IControl data flow - Arnie 2010.01.18 */
1198
1199            this.sender = encryptControl;
1200            LinkedList<ValueKey> lstRet = bruteforcePattern(pattern);
1201            if(OnBruteforcingEnded != null)
1202                OnBruteforcingEnded(lstRet);
1203        }
1204
1205        #endregion
1206
1207        public void GuiLogMessage(string message, NotificationLevel loglevel)
1208        {
1209            if (OnGuiLogNotificationOccured != null)
1210                OnGuiLogNotificationOccured(this, new GuiLogEventArgs(message, this, loglevel));
1211        }
1212
1213        public void ProgressChanged(double value, double max)
1214        {
1215            if (OnPluginProgressChanged != null)
1216            {
1217                OnPluginProgressChanged(this, new PluginProgressEventArgs(value, max));
1218
1219            }
1220        }
1221
1222        /// <summary>
1223        /// used for delivering the results from the worker threads to the main thread:
1224        /// </summary>
1225        public struct ValueKey
1226        {
1227            public double value;
1228            public String key;
1229            public byte[] decryption;
1230            public byte[] keya;
1231        };
1232    }
1233
1234    /// <summary>
1235    /// Represents one entry in our result list
1236    /// </summary>
1237    public class ResultEntry
1238    {
1239        public string Ranking { get; set; }
1240        public string Value { get; set; }
1241        public string Key { get; set; }
1242        public string Text { get; set; }
1243
1244    }
1245}
Note: See TracBrowser for help on using the repository browser.