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

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

keysearcher...

File size: 49.1 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)) / 8);
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);
839                }
840
841                //show OpenCL keys/sec:
842                var ratio = (double) openCLdoneKeys/(double) doneKeys;
843                ((QuickWatch)QuickWatchPresentation).Dispatcher.BeginInvoke(DispatcherPriority.Normal, (SendOrPostCallback)delegate
844                {
845                    ((QuickWatch)QuickWatchPresentation).OpenCLPresentation.keysPerSecond.Content = String.Format("{0:N}", openCLKeysPerSecond);
846                    ((QuickWatch)QuickWatchPresentation).OpenCLPresentation.ratio.Content = String.Format("{0:P}", ratio);
847                }, null);
848               
849
850                #region set doneKeys to 0
851                doneKeys = 0;
852                for (int i = 0; i < doneKeysA.Length; i++)
853                    doneKeysA[i] = 0;
854                openCLdoneKeys = 0;
855                for (int i = 0; i < openCLDoneKeysA.Length; i++)
856                    openCLDoneKeysA[i] = 0;
857                #endregion
858
859                if (keycounter >= size)
860                    break;
861            }//end while
862
863            showProgress(costList, 1, 1, 1);
864
865            //wake up all sleeping threads, so they can stop:
866            while (threadStack.Count != 0)
867                ((ThreadStackElement)threadStack.Pop()).ev.Set();
868
869            //wait until all threads finished:
870            foreach (AutoResetEvent stopEvent in threadsStopEvents)
871            {
872                stopEvent.WaitOne();
873            }
874
875            if (!stop && !redirectResultsToStatisticsGenerator)
876                ProgressChanged(1, 1);
877
878            /* BEGIN: For evaluation issues - added by Arnold 2010.03.17 */
879            TimeSpan bruteforcingTime = DateTime.Now.Subtract(beginBruteforcing);
880            StringBuilder sbBFTime = new StringBuilder();
881            if (bruteforcingTime.Days > 0)
882                sbBFTime.Append(bruteforcingTime.Days.ToString() + " days ");
883            if (bruteforcingTime.Hours > 0)
884            {
885                if (bruteforcingTime.Hours <= 9)
886                    sbBFTime.Append("0");
887                sbBFTime.Append(bruteforcingTime.Hours.ToString() + ":");
888            }
889            if (bruteforcingTime.Minutes <= 9)
890                sbBFTime.Append("0");
891            sbBFTime.Append(bruteforcingTime.Minutes.ToString() + ":");
892            if (bruteforcingTime.Seconds <= 9)
893                sbBFTime.Append("0");
894            sbBFTime.Append(bruteforcingTime.Seconds.ToString() + "-");
895            if (bruteforcingTime.Milliseconds <= 9)
896                sbBFTime.Append("00");
897            if (bruteforcingTime.Milliseconds <= 99)
898                sbBFTime.Append("0");
899            sbBFTime.Append(bruteforcingTime.Milliseconds.ToString());
900
901            GuiLogMessage("Ended bruteforcing pattern '" + pattern.getKey() + "'. Bruteforcing TimeSpan: " + sbBFTime.ToString(), NotificationLevel.Debug);
902            /* END: For evaluation issues - added by Arnold 2010.03.17 */
903
904            return costList;
905        }
906
907
908
909        private void SetStartDate()
910        {
911            localQuickWatchPresentation.startTime.Content = DateTime.Now.ToString("g", Thread.CurrentThread.CurrentCulture); ;
912        }
913
914        internal void showProgress(LinkedList<ValueKey> costList, BigInteger size, BigInteger keycounter, long keysPerSecond)
915        {
916            System.Text.ASCIIEncoding enc = new System.Text.ASCIIEncoding();
917
918            LinkedListNode<ValueKey> linkedListNode;
919            ProgressChanged((double)keycounter / (double)size, 1.0);
920
921            if (localQuickWatchPresentation.IsVisible && keysPerSecond != 0 && !stop)
922            {
923                double time = (Math.Pow(10, BigInteger.Log((size - keycounter), 10) - Math.Log10(keysPerSecond)));
924                TimeSpan timeleft = new TimeSpan(-1);
925
926                try
927                {
928                    if (time / (24 * 60 * 60) <= int.MaxValue)
929                    {
930                        int days = (int)(time / (24 * 60 * 60));
931                        time = time - (days * 24 * 60 * 60);
932                        int hours = (int)(time / (60 * 60));
933                        time = time - (hours * 60 * 60);
934                        int minutes = (int)(time / 60);
935                        time = time - (minutes * 60);
936                        int seconds = (int)time;
937
938                        timeleft = new TimeSpan(days, hours, minutes, (int)seconds, 0);
939                    }
940                }
941                catch
942                {
943                    //can not calculate time span
944                }
945
946                localQuickWatchPresentation.Dispatcher.BeginInvoke(DispatcherPriority.Normal, (SendOrPostCallback)delegate
947                {
948                    localQuickWatchPresentation.elapsedTime.Content = localBruteForceStopwatch.Elapsed;
949                    localQuickWatchPresentation.keysPerSecond.Content = String.Format("{0:N}", keysPerSecond);
950                    if (timeleft != new TimeSpan(-1))
951                    {
952                        localQuickWatchPresentation.timeLeft.Content = "" + timeleft;
953                        try
954                        {
955                            localQuickWatchPresentation.endTime.Content = "" + DateTime.Now.Add(timeleft);
956                        }
957                        catch
958                        {
959                            localQuickWatchPresentation.endTime.Content = "in a galaxy far, far away...";
960                        }
961                    }
962                    else
963                    {
964                        localQuickWatchPresentation.timeLeft.Content = "incalculable :-)";
965                        localQuickWatchPresentation.endTime.Content = "in a galaxy far, far away...";
966                    }
967
968                    localQuickWatchPresentation.entries.Clear();
969                    linkedListNode = costList.First;
970
971                    int i = 0;
972                    while (linkedListNode != null)
973                    {
974                        i++;
975
976                        ResultEntry entry = new ResultEntry();
977                        entry.Ranking = "" + i;
978                        entry.Value = "" + Math.Round(linkedListNode.Value.value, 3);
979                        entry.Key = linkedListNode.Value.key;
980                        entry.Text = enc.GetString(linkedListNode.Value.decryption);
981
982                        localQuickWatchPresentation.entries.Add(entry);
983                        linkedListNode = linkedListNode.Next;
984                    }
985                }
986                , null);
987            }//end if
988            else if (!stop && localQuickWatchPresentation.IsVisible)
989            {
990
991                localQuickWatchPresentation.Dispatcher.BeginInvoke(DispatcherPriority.Normal, (SendOrPostCallback)delegate
992                {
993                    localQuickWatchPresentation.entries.Clear();
994                    linkedListNode = costList.First;
995                    int i = 0;
996
997                    while (linkedListNode != null)
998                    {
999                        i++;
1000
1001                        ResultEntry entry = new ResultEntry();
1002                        entry.Ranking = "" + i;
1003                        entry.Value = "" + Math.Round(linkedListNode.Value.value, 3);
1004                        entry.Key = linkedListNode.Value.key;
1005                        entry.Text = enc.GetString(linkedListNode.Value.decryption);
1006
1007                        localQuickWatchPresentation.entries.Add(entry);
1008                        linkedListNode = linkedListNode.Next;
1009                    }
1010                }
1011                , null);
1012            }
1013        }
1014
1015        #region For TopList
1016
1017        private void fillListWithDummies(int maxInList, LinkedList<ValueKey> costList)
1018        {
1019            ValueKey valueKey = new ValueKey();
1020            if (this.costMaster.getRelationOperator() == RelationOperator.LessThen)
1021                valueKey.value = double.MaxValue;
1022            else
1023                valueKey.value = double.MinValue;
1024            valueKey.key = "dummykey";
1025            valueKey.decryption = new byte[0];
1026            value_threshold = valueKey.value;
1027            LinkedListNode<ValueKey> node = costList.AddFirst(valueKey);
1028            for (int i = 1; i < maxInList; i++)
1029            {
1030                node = costList.AddAfter(node, valueKey);
1031            }
1032        }
1033
1034        internal void IntegrateNewResults(LinkedList<ValueKey> updatedCostList)
1035        {
1036            foreach (var valueKey in updatedCostList)
1037            {
1038                if (keyQualityHelper.IsBetter(valueKey.value, value_threshold))
1039                {
1040                    valuequeue.Enqueue(valueKey);
1041                }
1042            }
1043
1044            updateToplist();
1045        }
1046
1047        internal void updateToplist()
1048        {
1049            LinkedListNode<ValueKey> node;
1050            while (valuequeue.Count != 0)
1051            {
1052                ValueKey vk = (ValueKey)valuequeue.Dequeue();
1053
1054                //if (costList.Contains(vk)) continue;
1055                var result = costList.Where(valueKey => valueKey.key == vk.key);
1056                if (result.Count() > 0)
1057                {
1058                    continue;
1059                }
1060
1061                if (this.costMaster.getRelationOperator() == RelationOperator.LargerThen)
1062                {
1063                    if (vk.value > costList.Last().value)
1064                    {
1065                        node = costList.First;
1066                        while (node != null)
1067                        {
1068                            if (vk.value > node.Value.value)
1069                            {
1070                                if (node == costList.First)
1071                                    Top1 = vk;
1072                                costList.AddBefore(node, vk);
1073                                costList.RemoveLast();
1074                                value_threshold = costList.Last.Value.value;
1075                                break;
1076                            }
1077                            node = node.Next;
1078                        }//end while
1079                    }//end if
1080                }
1081                else
1082                {
1083                    if (vk.value < costList.Last().value)
1084                    {
1085                        node = costList.First;
1086                        while (node != null)
1087                        {
1088                            if (vk.value < node.Value.value)
1089                            {
1090                                if (node == costList.First)
1091                                    Top1 = vk;
1092                                costList.AddBefore(node, vk);
1093                                costList.RemoveLast();
1094                                value_threshold = costList.Last.Value.value;
1095                                break;
1096                            }
1097                            node = node.Next;
1098                        }//end while
1099                    }//end if
1100                }
1101            }
1102        }
1103
1104        #endregion
1105
1106        private void StartThreads(IControlEncryption sender, int bytesToUse, KeyPattern.KeyPattern[] patterns, BigInteger[] doneKeysA, BigInteger[] openCLDoneKeysA, BigInteger[] keycounters, BigInteger[] keysleft, Stack threadStack)
1107        {
1108            for (int i = 0; i < patterns.Length; i++)
1109            {
1110                WaitCallback worker = new WaitCallback(KeySearcherJob);
1111                doneKeysA[i] = new BigInteger();
1112                openCLDoneKeysA[i] = new BigInteger();
1113                keycounters[i] = new BigInteger();
1114                bool useOpenCL = false;
1115
1116                if (settings.UseOpenCL && (i == patterns.Length - 1))     //Last thread is the OpenCL thread
1117                    useOpenCL = true;
1118
1119                ThreadPool.QueueUserWorkItem(worker, new object[] { patterns, i, doneKeysA, openCLDoneKeysA, keycounters, keysleft, sender, bytesToUse, threadStack, useOpenCL });
1120            }
1121        }
1122
1123        private KeyPattern.KeyPattern[] splitPatternForThreads(KeyPattern.KeyPattern pattern)
1124        {
1125            int threads = settings.CoresUsed;
1126            if (settings.UseOpenCL)
1127                threads++;
1128
1129            if (threads < 1)
1130                return null;
1131
1132            KeyPattern.KeyPattern[] patterns = new KeyPattern.KeyPattern[threads];
1133            if (threads > 1)
1134            {
1135                KeyPattern.KeyPattern[] patterns2 = pattern.split();
1136                if (patterns2 == null)
1137                {
1138                    patterns2 = new KeyPattern.KeyPattern[1];
1139                    patterns2[0] = pattern;
1140                    return patterns2;
1141                }
1142                patterns[0] = patterns2[0];
1143                patterns[1] = patterns2[1];
1144                int p = 1;
1145                threads -= 2;
1146
1147                while (threads > 0)
1148                {
1149                    int maxPattern = -1;
1150                    BigInteger max = 0;
1151                    for (int i = 0; i <= p; i++)
1152                        if (patterns[i].size() > max)
1153                        {
1154                            max = patterns[i].size();
1155                            maxPattern = i;
1156                        }
1157                    KeyPattern.KeyPattern[] patterns3 = patterns[maxPattern].split();
1158                    if (patterns3 == null)
1159                    {
1160                        patterns3 = new KeyPattern.KeyPattern[p+1];
1161                        for (int i = 0; i <= p; i++)
1162                            patterns3[i] = patterns[i];
1163                        return patterns3;
1164                    }
1165                    patterns[maxPattern] = patterns3[0];
1166                    patterns[++p] = patterns3[1];
1167                    threads--;
1168                }
1169            }
1170            else
1171                patterns[0] = pattern;
1172            return patterns;
1173        }
1174
1175        private void keyPatternChanged()
1176        {
1177            Pattern = new KeyPattern.KeyPattern(controlMaster.getKeyPattern());
1178        }
1179
1180        // added by Arnie - 2009.12.07
1181        public delegate void BruteforcingEnded(LinkedList<ValueKey> top10List);
1182        /// <summary>
1183        /// This event gets thrown after Bruteforcing had ended. This is no evidence, that bruteforcing was successful.
1184        /// But when the returned List is filled, we have (at least a part) of the possible best keys
1185        /// </summary>
1186        public event BruteforcingEnded OnBruteforcingEnded;
1187
1188        // added by Arnie -2009.12.02
1189        // for inheritance reasons
1190        public void BruteforcePattern(KeyPattern.KeyPattern pattern, byte[] encryptedData, byte[] initVector, IControlEncryption encryptControl, IControlCost costControl)
1191        {
1192            /* Begin: New stuff because of changing the IControl data flow - Arnie 2010.01.18 */
1193            this.encryptedData = encryptedData;
1194            this.initVector = initVector;
1195            /* End: New stuff because of changing the IControl data flow - Arnie 2010.01.18 */
1196
1197            this.sender = encryptControl;
1198            LinkedList<ValueKey> lstRet = bruteforcePattern(pattern);
1199            if(OnBruteforcingEnded != null)
1200                OnBruteforcingEnded(lstRet);
1201        }
1202
1203        #endregion
1204
1205        public void GuiLogMessage(string message, NotificationLevel loglevel)
1206        {
1207            if (OnGuiLogNotificationOccured != null)
1208                OnGuiLogNotificationOccured(this, new GuiLogEventArgs(message, this, loglevel));
1209        }
1210
1211        public void ProgressChanged(double value, double max)
1212        {
1213            if (OnPluginProgressChanged != null)
1214            {
1215                OnPluginProgressChanged(this, new PluginProgressEventArgs(value, max));
1216
1217            }
1218        }
1219
1220        /// <summary>
1221        /// used for delivering the results from the worker threads to the main thread:
1222        /// </summary>
1223        public struct ValueKey
1224        {
1225            public double value;
1226            public String key;
1227            public byte[] decryption;
1228            public byte[] keya;
1229        };
1230    }
1231
1232    /// <summary>
1233    /// Represents one entry in our result list
1234    /// </summary>
1235    public class ResultEntry
1236    {
1237        public string Ranking { get; set; }
1238        public string Value { get; set; }
1239        public string Key { get; set; }
1240        public string Text { get; set; }
1241
1242    }
1243}
Note: See TracBrowser for help on using the repository browser.