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

Last change on this file since 2189 was 2189, checked in by matkovic, 11 years ago

-added numeric separators

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