Changeset 865


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....

Location:
trunk
Files:
6 edited

Legend:

Unmodified
Added
Removed
  • trunk/CrypPluginBase/Control/IControlEncryption.cs

    r819 r865  
    1111        byte[] Decrypt(byte[] key, int blocksize);
    1212        string getKeyPattern();
    13         byte[] getKeyFromString(string key);
     13        byte[] getKeyFromString(string key, ref int[] arrayPointers, ref int[] arraySuccessors, ref int[] arrayUppers);
    1414        IControlEncryption clone();
    1515        event KeyPatternChanged keyPatternChanged;
  • trunk/CrypPlugins/AES/AES.cs

    r822 r865  
    875875        }
    876876
    877         public byte[] getKeyFromString(string key)
     877        public byte[] getKeyFromString(string key, ref int[] arrayPointers, ref int[] arraySuccessors, ref int[] arrayUppers)
    878878        {
    879879            int bytes = 0;
     
    891891            }
    892892            byte[] bkey = new byte[bytes];
     893            int counter = 0;
     894            bool allocated = false;
    893895            for (int i = 0; i < bytes; i++)
    894896            {
    895897                try
    896898                {
    897                     bkey[i] = Convert.ToByte(key.Substring(i * 3, 2), 16);
     899                    string substr = key.Substring(i * 3, 2);
     900                    if (!allocated && (substr[0] == '*' || substr[1] == '*'))
     901                    {
     902                        arrayPointers = new int[bytes];
     903                        for (int j = 0; j < bytes; j++)
     904                            arrayPointers[j] = -1;
     905                        arraySuccessors = new int[bytes];
     906                        arrayUppers = new int[bytes];
     907                        allocated = true;
     908                    }
     909                    if (substr[0] != '*' && substr[1] != '*')
     910                        bkey[i] = Convert.ToByte(substr, 16);
     911                    else if (substr[0] == '*' && substr[1] == '*')
     912                    {
     913                        bkey[i] = 0;
     914                        arrayPointers[counter] = i;
     915                        arraySuccessors[counter] = 1;
     916                        arrayUppers[counter] = 255;
     917                        counter++;
     918                    }
     919                    else if (substr[0] != '*' && substr[1] == '*')
     920                    {
     921                        bkey[i] = Convert.ToByte(substr[0] + "0", 16);
     922                        arrayPointers[counter] = i;
     923                        arraySuccessors[counter] = 1;
     924                        arrayUppers[counter] = Convert.ToByte(substr[0] + "F", 16);
     925                        counter++;
     926                    }
     927                    else if (substr[0] == '*' && substr[1] != '*')
     928                    {
     929                        bkey[i] = Convert.ToByte("0" + substr[1], 16);
     930                        arrayPointers[counter] = i;
     931                        arraySuccessors[counter] = 16;
     932                        arrayUppers[counter] = Convert.ToByte("F" + substr[1], 16);
     933                        counter++;
     934                    }
    898935                }
    899936                catch (Exception ex)
  • trunk/CrypPlugins/DES/DES.cs

    r819 r865  
    579579        }
    580580
    581         public byte[] getKeyFromString(string key)
     581        public byte[] getKeyFromString(string key, ref int[] arrayPointers, ref int[] arraySuccessors, ref int[] arrayUppers)
    582582        {
    583583            byte[] bkey = new byte[8];
     584            int counter = 0;
     585            bool allocated = false;
     586
    584587            for (int i = 0; i <= 7; i++)
    585588            {
    586                 bkey[i] = Convert.ToByte(key.Substring(i * 3, 2), 16);               
     589                string substr = key.Substring(i * 3, 2);
     590
     591                if (!allocated && (substr[0] == '*' || substr[1] == '*'))
     592                {
     593                    arrayPointers = new int[8];
     594                    for (int j = 0; j < 8; j++)
     595                        arrayPointers[j] = -1;
     596                    arraySuccessors = new int[8];
     597                    arrayUppers = new int[8];
     598                    allocated = true;
     599                }
     600
     601                if (substr[0] != '*' && substr[1] != '*')
     602                    bkey[i] = Convert.ToByte(substr, 16);
     603                else if (substr[0] == '*' && substr[1] == '*')
     604                {
     605                    bkey[i] = 0;
     606                    arrayPointers[counter] = i;
     607                    arraySuccessors[counter] = 1;
     608                    arrayUppers[counter] = 255;
     609                    counter++;
     610                }
     611                else if (substr[0] != '*' && substr[1] == '*')
     612                {
     613                    bkey[i] = Convert.ToByte(substr[0] + "0", 16);
     614                    arrayPointers[counter] = i;
     615                    arraySuccessors[counter] = 1;
     616                    arrayUppers[counter] = Convert.ToByte(substr[0] + "F", 16);
     617                    counter++;
     618                }
     619                else if (substr[0] == '*' && substr[1] != '*')
     620                {
     621                    bkey[i] = Convert.ToByte("0" + substr[1], 16);
     622                    arrayPointers[counter] = i;
     623                    arraySuccessors[counter] = 16;
     624                    arrayUppers[counter] = Convert.ToByte("F" + substr[1], 16);
     625                    counter++;
     626                }
    587627            }
    588628            return bkey;
  • 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                                    {
  • trunk/CrypPlugins/SDES/SDES.cs

    r819 r865  
    616616        /// <param name="key"></param>
    617617        /// <returns></returns>
    618         public byte[] getKeyFromString(string key)
     618        public byte[] getKeyFromString(string key, ref int[] arrayPointers, ref int[] arraySuccessors, ref int[] arrayUppers)
    619619        {
    620620            byte[] bkey = new byte[10];
    621621            int count = 0;
    622622            foreach (char c in key)
    623                 if (c == '0')
     623                if (c == '*')
     624                    return null;    //blocks not supported yet
     625                else if (c == '0')
    624626                    bkey[count++] = 0;
    625627                else
  • trunk/CrypPlugins/Transposition/Transposition.cs

    r859 r865  
    10831083        }
    10841084
    1085         public byte[] getKeyFromString(string key)
     1085        public byte[] getKeyFromString(string key, ref int[] arrayPointers, ref int[] arraySuccessors, ref int[] arrayUppers)
    10861086        {
    10871087            return null;
Note: See TracChangeset for help on using the changeset viewer.