Ignore:
Timestamp:
Nov 17, 2009, 9:31:19 PM (12 years ago)
Author:
Sven Rech
Message:

some big optimizations to the keypattern mechanism of the keysearcher.
The keysearcher itself should have zero performace overhead now.
But bruteforcing AES and DES is still very slow.
By profiling, we found out that the Microsoft Crypto implementations are to blame, because they aren't optimized for speed.
So the next step would be to replace those implementations....

File:
1 edited

Legend:

Unmodified
Added
Removed
  • trunk/CrypPlugins/KeySearcher/KeySearcher.cs

    r851 r865  
    2121            private int length;
    2222            private int counter;
     23            public bool isSplit
     24            {
     25                get;
     26                private set;
     27            }
    2328           
    2429            public Wildcard(string valuePattern)
    2530            {
     31                isSplit = false;
    2632                counter = 0;
    2733                length = 0;
     
    4349            public Wildcard(Wildcard wc)
    4450            {
     51                isSplit = wc.isSplit;
    4552                length = wc.length;
    4653                counter = wc.counter;
     
    6774                for (int i = 0; i < wcs[1].length; i++)
    6875                    wcs[1].values[i] = values[i + this.counter + wcs[0].length];
     76                wcs[0].isSplit = true;
     77                wcs[1].isSplit = true;
    6978                return wcs;
    7079            }
     
    7382            {
    7483                return values[counter];
     84            }
     85
     86            public char getChar(int add)
     87            {
     88                return values[(counter+add)%length];
    7589            }
    7690
     
    141155                }
    142156            }
     157            if (!s)
     158                throw new Exception("Can't be split!");
    143159            return patterns;
    144160        }
     
    240256        }
    241257
    242         public bool nextKey()
    243         {
    244             int wildcardCount = wildcardList.Count-1;
     258        /** used to jump to the next Key.         
     259         * if nextWildcard == -1, we return false
     260         * if nextWildcard == -2, we return true
     261         * if nextWildcard == -3, we increase the rightmost wildcard
     262         * if nextWildcard >= 0, we increase the wildcard on the position 'nextWildcard'
     263         * returns false if there is no key left.
     264         */
     265        public bool nextKey(int nextWildcard)
     266        {
     267            if (nextWildcard == -2)
     268                return true;
     269            if (nextWildcard == -1)
     270                return false;
     271
     272            int wildcardCount;
     273            if (nextWildcard == -3)
     274                wildcardCount = wildcardList.Count - 1;
     275            else
     276                wildcardCount = nextWildcard;
    245277            bool overflow = ((Wildcard)wildcardList[wildcardCount]).succ();
    246278            wildcardCount--;
     
    266298            return res;
    267299        }
     300
     301        public string getKey(int add)
     302        {
     303            string res = "";
     304            int div = 1;
     305            int wildcardCount = wildcardList.Count-1;
     306            for (int i = key.Length-1; i >= 0; i--)
     307            {
     308                if (key[i] != '*')
     309                    res += key[i];
     310                else
     311                {
     312                    Wildcard wc = (Wildcard)wildcardList[wildcardCount--];
     313                    if (add < div)
     314                        res += wc.getChar();
     315                    else
     316                    {
     317                        res += wc.getChar((add / div) % wc.size());
     318                        div *= wc.size();
     319                    }
     320                }
     321            }
     322            char[] r = res.ToCharArray();
     323            Array.Reverse(r);
     324            return new string(r);
     325        }
     326
     327        public string getKeyBlock(ref int blocksize, ref int nextWildcard)
     328        {
     329            const int MAXSIZE = 65536;
     330            //find out how many wildcards we can group together:
     331            blocksize = 1;
     332            int pointer;
     333            for (pointer = wildcardList.Count - 1; pointer >= 0; pointer--)
     334            {
     335                Wildcard wc = (Wildcard)wildcardList[pointer];
     336                if (wc.isSplit || wc.count() != 0 || blocksize*wc.size() > MAXSIZE)               
     337                    break;
     338                else
     339                    blocksize *= wc.size();
     340            }           
     341
     342            if (pointer >= wildcardList.Count)
     343                return null;
     344
     345            nextWildcard = pointer;           
     346
     347            //generate key:
     348            string res = "";
     349            int wildcardCount = 0;
     350            for (int i = 0; i < key.Length; i++)
     351            {
     352                if (key[i] != '*')
     353                    res += key[i];
     354                else
     355                {
     356                    if (pointer < wildcardCount)
     357                        res += "*";
     358                    else
     359                    {
     360                        Wildcard wc = (Wildcard)wildcardList[wildcardCount++];
     361                        res += wc.getChar();
     362                    }
     363                }
     364            }
     365            return res;
     366        }
     367
    268368    }
    269369   
     
    355455            KeyPattern pattern = patterns[threadid];
    356456
     457            bool useKeyblocks = true;
     458
    357459            try
    358460            {
     
    361463                    long size = pattern.size();
    362464                    keysLeft[threadid] = size;
     465                    int nextWildcard;
    363466
    364467                    do
    365468                    {
    366                         ValueKey valueKey = new ValueKey();
    367                         try
    368                         {
    369                             valueKey.key = pattern.getKey();
    370                         }
    371                         catch (Exception ex)
    372                         {
    373                             GuiLogMessage("Could not get next Key: " + ex.Message, NotificationLevel.Error);
    374                             return;
    375                         }
    376 
    377                         try
    378                         {
    379                             valueKey.decryption = sender.Decrypt(ControlMaster.getKeyFromString(valueKey.key), bytesToUse);
    380                         }
    381                         catch (Exception ex)
    382                         {
    383                             GuiLogMessage("Decryption is not possible: " + ex.Message, NotificationLevel.Error);
    384                             GuiLogMessage("Stack Trace: " + ex.StackTrace, NotificationLevel.Error);
    385                             return;
    386                         }
    387 
    388                         try
    389                         {
    390                             valueKey.value = CostMaster.calculateCost(valueKey.decryption);
    391                         }
    392                         catch (Exception ex)
    393                         {
    394                             GuiLogMessage("Cost calculation is not possible: " + ex.Message, NotificationLevel.Error);
    395                             return;
    396                         }
    397 
    398                         if (this.costMaster.getRelationOperator() == RelationOperator.LargerThen)
    399                         {
    400                             if (valueKey.value > value_threshold)
    401                                 valuequeue.Enqueue(valueKey);
    402                         }
    403                         else
    404                         {
    405                             if (valueKey.value < value_threshold)
    406                                 valuequeue.Enqueue(valueKey);
    407                         }
    408 
    409                         doneKeysArray[threadid]++;
    410                         keycounterArray[threadid]++;
    411                         keysLeft[threadid]--;
    412 
    413469                        //if we are the thread with most keys left, we have to share them:
    414470                        if (maxThread == threadid && threadStack.Count != 0)
     
    417473                            if (maxThread == threadid && threadStack.Count != 0)
    418474                            {
    419                                 KeyPattern[] split = pattern.split();
    420                                 patterns[threadid] = split[0];
    421                                 pattern = split[0];
    422                                 ThreadStackElement elem = (ThreadStackElement)threadStack.Pop();
    423                                 patterns[elem.threadid] = split[1];
    424                                 elem.ev.Set();    //wake the other thread up
     475                                try
     476                                {
     477                                    KeyPattern[] split = pattern.split();
     478                                    patterns[threadid] = split[0];
     479                                    pattern = split[0];
     480                                    ThreadStackElement elem = (ThreadStackElement)threadStack.Pop();
     481                                    patterns[elem.threadid] = split[1];
     482                                    elem.ev.Set();    //wake the other thread up                                   
     483                                    size = pattern.size();
     484                                    keysLeft[threadid] = size;
     485                                }
     486                                catch (Exception e)
     487                                {
     488                                    //pattern can't be split? who cares :)
     489                                }
    425490                                maxThread = -1;
    426                                 size = pattern.size();
    427                                 keysLeft[threadid] = size;
    428491                            }
    429492                            maxThreadMutex.ReleaseMutex();
    430493                        }
    431494
    432                     } while (pattern.nextKey() && !stop);
     495
     496                        ValueKey valueKey = new ValueKey();
     497                        int blocksize = 0;
     498                        nextWildcard = -3;
     499                        try
     500                        {
     501                            string key = "";
     502                            if (useKeyblocks)
     503                                key = pattern.getKeyBlock(ref blocksize, ref nextWildcard);
     504                            if (key == null)
     505                                useKeyblocks = false;
     506                            if (!useKeyblocks)
     507                                key = pattern.getKey();
     508                            valueKey.key = key;
     509                        }
     510                        catch (Exception ex)
     511                        {
     512                            GuiLogMessage("Could not get next key: " + ex.Message, NotificationLevel.Error);
     513                            return;
     514                        }
     515
     516                        int[] arrayPointers = null;
     517                        int[] arraySuccessors = null;
     518                        int[] arrayUppers = null;
     519                        byte[] keya = ControlMaster.getKeyFromString(valueKey.key, ref arrayPointers, ref arraySuccessors, ref arrayUppers);
     520                        if (keya == null)
     521                        {
     522                            useKeyblocks = false;
     523                            nextWildcard = -2;
     524                            continue;   //try again
     525                        }
     526
     527                        if (arrayPointers == null)  //decrypt only one key
     528                        {
     529                            if (!decryptAndCalculate(sender, bytesToUse, ref valueKey, keya, 0, null))
     530                                return;                           
     531                            doneKeysArray[threadid]++;
     532                            keycounterArray[threadid]++;
     533                            keysLeft[threadid]--;
     534                        }
     535                        else  //decrypt several keys
     536                        {
     537                            int counter = 0;
     538                            if (!bruteforceBlock(sender, bytesToUse, ref valueKey, keya, arrayPointers, arraySuccessors, arrayUppers, 0, ref counter, pattern))
     539                                return;
     540                            doneKeysArray[threadid] += blocksize;
     541                            keycounterArray[threadid] += blocksize;
     542                            keysLeft[threadid] -= blocksize;
     543                        }
     544                    } while (pattern.nextKey(nextWildcard) && !stop);
     545
     546                    if (stop)
     547                        return;
    433548
    434549                    //Let's wait until another thread is willing to share with us:
     
    449564                sender.Dispose();
    450565            }
     566        }
     567       
     568        private bool bruteforceBlock(IControlEncryption sender, int bytesToUse, ref ValueKey valueKey, byte[] keya, int[] arrayPointers,
     569            int[] arraySuccessors, int[] arrayUppers, int arrayPointer, ref int counter, KeyPattern pattern)
     570        {
     571            byte store = keya[arrayPointers[arrayPointer]];
     572            while (!stop)
     573            {
     574                if (arrayPointer+1 < arrayPointers.Length && arrayPointers[arrayPointer+1] != -1)
     575                {
     576                    if (!bruteforceBlock(sender, bytesToUse, ref valueKey, keya, arrayPointers, arraySuccessors, arrayUppers, arrayPointer + 1, ref counter, pattern))
     577                        return false;
     578                }
     579                else
     580                {
     581                    if (!decryptAndCalculate(sender, bytesToUse, ref valueKey, keya, counter, pattern))
     582                        return false;
     583                }
     584
     585                if (keya[arrayPointers[arrayPointer]] + arraySuccessors[arrayPointer] <= arrayUppers[arrayPointer])
     586                {
     587                    keya[arrayPointers[arrayPointer]] += (byte)arraySuccessors[arrayPointer];
     588                    counter++;
     589                }
     590                else
     591                    break;
     592            }
     593            keya[arrayPointers[arrayPointer]] = store;
     594            if (stop)
     595                return false;
     596            return true;
     597        }
     598
     599        private bool decryptAndCalculate(IControlEncryption sender, int bytesToUse, ref ValueKey valueKey, byte[] keya, int counter, KeyPattern pattern)
     600        {
     601            try
     602            {
     603                valueKey.decryption = sender.Decrypt(keya, bytesToUse);
     604            }
     605            catch (Exception ex)
     606            {
     607                GuiLogMessage("Decryption is not possible: " + ex.Message, NotificationLevel.Error);
     608                GuiLogMessage("Stack Trace: " + ex.StackTrace, NotificationLevel.Error);
     609                return false;
     610            }
     611
     612            try
     613            {
     614                valueKey.value = CostMaster.calculateCost(valueKey.decryption);
     615            }
     616            catch (Exception ex)
     617            {
     618                GuiLogMessage("Cost calculation is not possible: " + ex.Message, NotificationLevel.Error);
     619                return false;
     620            }
     621
     622            if (this.costMaster.getRelationOperator() == RelationOperator.LargerThen)
     623            {
     624                if (valueKey.value > value_threshold)
     625                {
     626                    if (pattern != null)
     627                        valueKey.key = pattern.getKey(counter);
     628                    valuequeue.Enqueue(valueKey);
     629                }
     630            }
     631            else
     632            {
     633                if (valueKey.value < value_threshold)
     634                {
     635                    if (pattern != null)
     636                        valueKey.key = pattern.getKey(counter);
     637                    valuequeue.Enqueue(valueKey);
     638                }
     639            }
     640            return true;
    451641        }
    452642
     
    551741                                while (node != null)
    552742                                {
    553 
    554743                                    if (vk.value > node.Value.value)
    555744                                    {
Note: See TracChangeset for help on using the changeset viewer.