Changeset 2010


Ignore:
Timestamp:
Oct 23, 2010, 7:39:00 PM (11 years ago)
Author:
Sven Rech
Message:

new key finding algorithm for KeySearcher

This update is really huge.

Location:
trunk
Files:
6 added
13 edited

Legend:

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

    r1932 r2010  
    2828        byte[] Decrypt(byte[] ciphertext, byte[] key, byte[] IV);
    2929        string getKeyPattern();
    30         byte[] getKeyFromString(string key);
     30        KeyTranslator getKeyTranslator();
     31
    3132        void changeSettings(string setting, object value);
    3233        IControlEncryption clone();
  • trunk/CrypPluginBase/CrypPluginBase.csproj

    r1817 r2010  
    110110    <Compile Include="Control\IControlCost.cs" />
    111111    <Compile Include="Control\IControlEncryption.cs" />
     112    <Compile Include="Control\KeyTranslator.cs" />
    112113    <Compile Include="IO\CStream.cs" />
    113114    <Compile Include="IO\CStreamReader.cs" />
  • trunk/CrypPlugins/AES/AES.cs

    r1932 r2010  
    560560        }
    561561
    562         public byte[] getKeyFromString(string key)
    563         {
    564             int bytes = 0;
    565             switch (((AESSettings)plugin.Settings).Keysize)
    566             {
    567                 case 0:
    568                     bytes = 16;
    569                     break;
    570                 case 1:
    571                     bytes = 24;
    572                     break;
    573                 case 2:
    574                     bytes = 32;
    575                     break;
    576             }
    577 
    578             byte[] bkey = new byte[bytes];
    579             for (int i = 0; i < bytes; i++)
    580             {
    581                 try
    582                 {
    583                     string substr = key.Substring(i * 3, 2);
    584                     bkey[i] = Convert.ToByte(substr, 16);
    585                 }
    586                 catch (Exception ex)
    587                 {
    588                     return null;
    589                 }
    590             }
    591             return bkey;
    592         }
    593 
    594562        public IControlEncryption clone()
    595563        {
     
    602570        }
    603571
    604         #endregion
    605 
    606         #region IControlEncryption Member
    607 
    608 
    609572        public void changeSettings(string setting, object value)
    610573        {
    611            
     574        }
     575
     576        public KeyTranslator getKeyTranslator()
     577        {
     578            return new KeySearcher.KeyTranslators.ByteArrayKeyTranslator();
    612579        }
    613580
  • trunk/CrypPlugins/AES/AES.csproj

    r1487 r2010  
    122122      <Private>False</Private>
    123123    </ProjectReference>
     124    <ProjectReference Include="..\KeySearcher\KeySearcher.csproj">
     125      <Project>{0579E099-66B2-43C3-B8A0-43CAE4895E68}</Project>
     126      <Name>KeySearcher</Name>
     127    </ProjectReference>
    124128  </ItemGroup>
    125129  <ItemGroup>
  • trunk/CrypPlugins/DES/DES.cs

    r1932 r2010  
    536536            // Change the padding mode to zeroes, since we want to do bruteforcing..
    537537            ((DESSettings)plugin.Settings).Padding = 0;
    538         }
    539 
    540        
     538        }       
    541539
    542540        public byte[] Encrypt(byte[] key, int blocksize)
     
    565563        }
    566564
    567         public byte[] getKeyFromString(string key)
    568         {
    569             byte[] bkey = new byte[8];
    570 
    571             for (int i = 0; i <= 7; i++)
    572             {
    573                 string substr = key.Substring(i * 3, 2);
    574                 bkey[i] = Convert.ToByte(substr, 16);
    575             }
    576 
    577             return bkey;
    578         }
    579 
    580565        public IControlEncryption clone()
    581566        {
     
    594579        }
    595580
     581        public KeyTranslator getKeyTranslator()
     582        {
     583            return new KeySearcher.KeyTranslators.ByteArrayKeyTranslator();
     584        }
    596585    }
    597586    #endregion
  • trunk/CrypPlugins/DES/DES.csproj

    r1487 r2010  
    137137      <Private>False</Private>
    138138    </ProjectReference>
     139    <ProjectReference Include="..\KeySearcher\KeySearcher.csproj">
     140      <Project>{0579E099-66B2-43C3-B8A0-43CAE4895E68}</Project>
     141      <Name>KeySearcher</Name>
     142    </ProjectReference>
    139143  </ItemGroup>
    140144  <ItemGroup>
  • trunk/CrypPlugins/KeySearcher/KeyPattern/KeyPattern.cs

    r1932 r2010  
    2020using System.IO;
    2121using System.Numerics;
     22using System.Collections.Generic;
    2223
    2324namespace KeySearcher.KeyPattern
     
    259260        }
    260261
    261         /** used to jump to the next key.         
     262        /* used to jump to the next key.         
    262263         * if nextWildcard == -1, we return false
    263264         * if nextWildcard == -2, we return true
     
    278279            else
    279280                wildcardCount = nextWildcard;
    280             bool overflow = ((Wildcard)wildcardList[wildcardCount--]).succ();           
     281           
     282            bool overflow = ((Wildcard)wildcardList[wildcardCount--]).succ();
    281283            while (overflow && (wildcardCount >= 0))
    282284                overflow = ((Wildcard)wildcardList[wildcardCount--]).succ();
     285
    283286            return !overflow;
    284287        }
     
    289292        {
    290293            return nextKey(-3);
     294        }
     295
     296        /// <summary>
     297        /// Moves the key "add" steps further.
     298        /// So, addKey(1) would behave the same as nextKey().
     299        /// </summary>
     300        /// <param name="add"></param>
     301        /// <returns>false, if there are no keys left</returns>
     302        public bool addKey(int add)
     303        {
     304            int i = wildcardList.Count - 1;
     305            int carry = add;
     306
     307            while (carry != 0 && i >= 0)
     308            {
     309                carry = ((Wildcard)wildcardList[i--]).add(carry);
     310            }
     311
     312            return (i >= 0);
    291313        }
    292314
     
    338360        }
    339361
    340         public string getKeyBlock(ref int blocksize, ref int nextWildcard)
    341         {
    342             const int MAXSIZE = 65536;
    343             //find out how many wildcards we can group together:
    344             blocksize = 1;
    345             int pointer;
    346             for (pointer = wildcardList.Count - 1; pointer >= 0; pointer--)
    347             {
    348                 Wildcard wc = (Wildcard)wildcardList[pointer];
    349                 if (wc.isSplit || wc.count() != 0 || blocksize * wc.size() > MAXSIZE)
     362        /// <summary>
     363        /// Returns the progress of each relevant wildcard.
     364        /// </summary>
     365        /// <returns></returns>
     366        internal int[] getWildcardProgress()
     367        {
     368            int arraySize = 0;
     369            foreach (Wildcard wc in this.wildcardList)
     370                if (wc.getLength() > 1)
     371                    arraySize++;
     372
     373            int[] result = new int[arraySize];
     374
     375            int i = 0;
     376            for (int c = 0; c < wildcardList.Count; c++)
     377            {
     378                if (((Wildcard)this.wildcardList[c]).getLength() > 1)
     379                    result[i++] = ((Wildcard)wildcardList[c]).count();
     380            }
     381
     382            return result;
     383        }
     384
     385        /// <summary>
     386        /// returns the "movements" of the key, i.e. how each relevant wildcard has to be "rotated" to produce the next key.
     387        /// </summary>
     388        /// <returns></returns>
     389        public KeyMovement[] getKeyMovements()
     390        {
     391            KeyPattern fullKeyPattern = new KeyPattern(pattern);
     392            fullKeyPattern.WildcardKey = pattern;
     393
     394            int arraySize = 0;
     395            foreach (Wildcard wc in this.wildcardList)
     396                if (wc.getLength() > 1)
     397                    arraySize++;
     398
     399            KeyMovement[] result = new KeyMovement[arraySize];
     400
     401            int c = 0;
     402            for (int i = 0; i < wildcardList.Count; i++)
     403            {
     404                if (((Wildcard)this.wildcardList[i]).getLength() > 1)
     405                {
     406                    result[c] = getWildcardMovement((Wildcard)this.wildcardList[i], (Wildcard)fullKeyPattern.wildcardList[i]);
     407                    c++;
     408                }
     409            }
     410
     411            return result;
     412        }
     413
     414        /// <summary>
     415        /// Compares "wildcard" with "fullwildcard" and returns the movement of "wildcard", i.e. which intervals exists between the elements of "wildcard".       
     416        /// </summary>
     417        /// <param name="wildcard"></param>
     418        /// <param name="fullwildcard"></param>
     419        /// <returns>The movements</returns>
     420        private KeyMovement getWildcardMovement(Wildcard wildcard, Wildcard fullwildcard)
     421        {
     422            //check if linear:
     423            int a;
     424            int b;
     425
     426
     427            int i = 0;
     428            while (fullwildcard.getChars()[i] != wildcard.getChars()[0])
     429                i++;
     430
     431            b = i;
     432            i++;
     433
     434            while (fullwildcard.getChars()[i] != wildcard.getChars()[1])
     435                i++;
     436
     437            a = i-b;
     438           
     439            bool linear = true;
     440            for (int c = 0; c < wildcard.getLength(); c++)
     441            {
     442                if (fullwildcard.getChars()[c * a + b] != wildcard.getChars()[c])
     443                {
     444                    linear = false;
    350445                    break;
    351                 else
    352                     blocksize *= wc.size();
    353             }
    354 
    355             if (pointer >= wildcardList.Count)
    356                 return null;
    357 
    358             nextWildcard = pointer;
    359 
    360             //generate key:
    361             string res = "";
    362             int wildcardCount = 0;
    363             int i = 0;
    364             while (i < pattern.Length)
    365             {
    366                 if (pattern[i] != '[')
    367                     res += pattern[i++];
    368                 else
    369                 {
    370                     if (pointer < wildcardCount)
    371                         res += "*";
    372                     else
    373                     {
    374                         Wildcard wc = (Wildcard)wildcardList[wildcardCount++];
    375                         res += wc.getChar();
    376                     }
    377                     while (pattern[i++] != ']') ;
    378                 }
    379             }
    380             return res;
    381         }       
    382 
    383          /*
    384          * ARNIES SANDKASTEN - ALLE FOLGENDEN METHODEN SIND FÜR DIE VERTEILTE VERWENDUNG
    385          * DES KEYPATTERNS NOTWENDIG ODER ABER EINFACH UM DAS KEYPATTERN SCHÖN ALS
    386          * GUILOGMESSAGE AUSGEBEN ZU KÖNNEN ;-)
    387          */
    388 
    389         // Added by Arnold - 2010.02.04
     446                }
     447            }
     448
     449            if (linear)
     450            {
     451                return new LinearKeyMovement(a, b, wildcard.getLength());
     452            }
     453
     454            //not linear, so just list the intervals:
     455            List<int> intervalList = new List<int>();
     456
     457            for (int c = 0; c < wildcard.getLength(); c++)
     458            {
     459                for (int x = 0; x < fullwildcard.getLength(); x++)
     460                {
     461                    if (fullwildcard.getChars()[x] == wildcard.getChars()[c])
     462                        intervalList.Add(x);
     463                }
     464            }
     465
     466            return new IntervalKeyMovement(intervalList);
     467        }
     468
    390469        public KeyPattern(byte[] serializedPattern)
    391470        {
     
    399478        }
    400479
    401         //added by Christian Arnold - 2009.12.02
    402480        /// <summary>
    403481        /// returns type, key and pattern. If you want to get only the pattern for processing use GetPattern-method!
     
    412490        }
    413491
    414         //added by Christian Arnold - 2009.12.03
    415492        /// <summary>
    416493        /// returns ONLY the pattern as a string!
  • trunk/CrypPlugins/KeySearcher/KeyPattern/Wildcard.cs

    r1674 r2010  
    1 namespace KeySearcher.KeyPattern
     1/*                             
     2   Copyright 2009 Sven Rech (svenrech at googlemail dot com), 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
     17namespace KeySearcher.KeyPattern
    218{
    319    internal class Wildcard
     
    103119        }
    104120
     121        /// <summary>
     122        /// Adds "add" to the counter and returns the carry.
     123        /// </summary>
     124        /// <param name="add">The carry</param>
     125        /// <returns></returns>
     126        public int add(int add)
     127        {
     128            counter += add;
     129            if (counter >= length)
     130            {
     131                int result = counter / length;
     132                counter %= length;
     133                return result;
     134            }
     135            return 0;
     136        }
     137
    105138        public int size()
    106139        {
     
    174207            return true;
    175208        }
     209
     210        internal int getLength()
     211        {
     212            return length;
     213        }
     214
     215        internal char[] getChars()
     216        {
     217            return values;
     218        }
    176219    }
    177220}
  • trunk/CrypPlugins/KeySearcher/KeySearcher.cs

    r2009 r2010  
    1 using System;
     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;
    218using System.Diagnostics;
    319using System.Linq;
     
    191207            get
    192208            {
    193                 if (top1ValueKey.key != null) //added by Arnold - 2010.02.22
    194                 {
    195                     return ControlMaster.getKeyFromString(top1ValueKey.key);
     209                if (top1ValueKey.key != null)
     210                {
     211                    return top1ValueKey.keya;
    196212                }
    197213                else
     
    344360                    BigInteger size = pattern.size();
    345361                    keysLeft[threadid] = size;
     362
     363                    KeyTranslator keyTranslator = ControlMaster.getKeyTranslator();
     364                    keyTranslator.SetKeys(pattern);
     365
     366                    bool finish = false;
    346367
    347368                    do
     
    360381                                        patterns[threadid] = split[0];
    361382                                        pattern = split[0];
     383                                        keyTranslator = ControlMaster.getKeyTranslator();
     384                                        keyTranslator.SetKeys(pattern);
     385
    362386                                        ThreadStackElement elem = (ThreadStackElement)threadStack.Pop();
    363387                                        patterns[elem.threadid] = split[1];
     
    375399                        }
    376400
    377                         ValueKey valueKey = new ValueKey();
    378                         try
     401                        for (int count = 0; count < 256 * 256; count++)
    379402                        {
    380                             valueKey.key = pattern.getKey();
     403                            byte[] keya = keyTranslator.GetKey();
     404
     405                            if (!decryptAndCalculate(sender, bytesToUse, keya, keyTranslator))
     406                                return;
     407
     408                            finish = !keyTranslator.NextKey();
     409                            if (finish)
     410                                break;
    381411                        }
    382                         catch (Exception ex)
    383                         {
    384                             GuiLogMessage("Could not get next key: " + ex.Message, NotificationLevel.Error);
    385                             return;
    386                         }
    387 
    388                         byte[] keya = ControlMaster.getKeyFromString(valueKey.key);
    389 
    390                         if (!decryptAndCalculate(sender, bytesToUse, ref valueKey, keya, 0, null))
    391                             return;
    392 
    393                         doneKeysArray[threadid]++;
    394                         keycounterArray[threadid]++;
    395                         keysLeft[threadid]--;
    396 
    397                     } while (pattern.nextKey() && !stop);
     412                        int progress = keyTranslator.GetProgress();
     413
     414                        doneKeysArray[threadid] += progress;
     415                        keycounterArray[threadid] += progress;
     416                        keysLeft[threadid] -= progress;
     417
     418                    } while (!finish && !stop);
    398419
    399420                    if (stop)
     
    409430                    GuiLogMessage("Thread waiting for new keys.", NotificationLevel.Debug);
    410431                    el.ev.WaitOne();
    411                     GuiLogMessage("Thread waking up with new keys.", NotificationLevel.Debug);
    412                     pattern = patterns[threadid];
     432                    if (!stop)
     433                    {
     434                        GuiLogMessage("Thread waking up with new keys.", NotificationLevel.Debug);
     435                        pattern = patterns[threadid];
     436                    }
    413437                }
    414438            }
     
    421445        #region bruteforce methods
    422446
    423         private bool decryptAndCalculate(IControlEncryption sender, int bytesToUse, ref ValueKey valueKey, byte[] keya, int counter, KeyPattern.KeyPattern pattern)
    424         {
     447        private bool decryptAndCalculate(IControlEncryption sender, int bytesToUse, byte[] keya, KeyTranslator keyTranslator)
     448        {
     449            ValueKey valueKey;
     450
    425451            try
    426452            {
     
    434460                    return false;
    435461                }
    436                 //CryptoolStream cs = new CryptoolStream();
    437                 //if (this.CSEncryptedData == null)
    438                 //{
    439                 //    cs.OpenRead(this.EncryptedData);
    440                 //    valueKey.decryption = sender.Decrypt(this.EncryptedData, keya);
    441                 //}
    442                 //else
    443                 //{
    444                 //    cs.OpenRead(this.CSEncryptedData.FileName);
    445                 //    byte[] byteCS = new byte[cs.Length];
    446                 //    cs.Read(byteCS, 0, byteCS.Length);
    447                 //    //this.CSEncryptedData.Read(byteCS, 0, byteCS.Length);
    448                 //    valueKey.decryption = sender.Decrypt(byteCS, keya);
    449                 //}
    450 
    451                 //valueKey.decryption = sender.Decrypt(keya, bytesToUse);
    452462            }
    453463            catch (Exception ex)
     
    472482                if (valueKey.value > value_threshold)
    473483                {
    474                     if (pattern != null)
    475                         valueKey.key = pattern.getKey(counter);
    476                     valuequeue.Enqueue(valueKey);
     484                    valueKey.key = keyTranslator.GetKeyRepresentation();
     485                    valueKey.keya = (byte[])keya.Clone();
     486                    valuequeue.Enqueue(valueKey);                   
    477487                }
    478488            }
     
    481491                if (valueKey.value < value_threshold)
    482492                {
    483                     if (pattern != null)
    484                         valueKey.key = pattern.getKey(counter);
     493                    valueKey.key = keyTranslator.GetKeyRepresentation();
     494                    valueKey.keya = (byte[])keya.Clone();                 
    485495                    valuequeue.Enqueue(valueKey);
    486496                }
     
    514524        private DistributedBruteForceManager distributedBruteForceManager;
    515525
    516         // modified by Christian Arnold 2009.12.07 - return type LinkedList (top10List)
    517526        // main entry point to the KeySearcher
    518527        private LinkedList<ValueKey> bruteforcePattern(KeyPattern.KeyPattern pattern)
    519528        {
    520             //For evaluation issues - added by Arnold 2010.03.17
    521529            beginBruteforcing = DateTime.Now;
    522530            GuiLogMessage("Start bruteforcing pattern '" + pattern.getKey() + "'", NotificationLevel.Debug);
    523 
    524 
    525531                       
    526532            int maxInList = 10;
     
    10011007            public String key;
    10021008            public byte[] decryption;
     1009            public byte[] keya;
    10031010        };
    10041011    }
  • trunk/CrypPlugins/KeySearcher/KeySearcher.csproj

    r1751 r2010  
    110110    <Compile Include="Converter\TrueToVisibleConverter.cs" />
    111111    <Compile Include="Helper\KeyQualityHelper.cs" />
     112    <Compile Include="KeyPattern\IntervalKeyMovement.cs" />
    112113    <Compile Include="KeyPattern\KeyPattern.cs" />
    113114    <Compile Include="KeyPattern\KeyPatternPool.cs" />
     115    <Compile Include="KeyPattern\LinearKeyMovement.cs" />
     116    <Compile Include="KeyPattern\KeyMovement.cs" />
    114117    <Compile Include="KeySearcher.cs" />
     118    <Compile Include="KeyTranslators\ByteArrayKeyTranslator.cs" />
    115119    <Compile Include="P2P\Helper\ConnectionHelper.cs" />
    116120    <Compile Include="P2P\Helper\DatabaseStatistics.cs" />
  • trunk/CrypPlugins/SDES/SDES.cs

    r1932 r2010  
    2929using System.Windows.Threading;
    3030using System.Runtime.InteropServices;
     31using KeySearcher.KeyPattern;
    3132
    3233namespace Cryptool.Plugins.Cryptography.Encryption
     
    628629        }
    629630
    630         /// <summary>
    631         /// Makes a byte Array out of a String
    632         /// example
    633         /// "10101" -> 1,0,1,0,1
    634         ///
    635         /// A 0 is interpreted as 0
    636         /// any other character as 1
    637         /// </summary>
    638         /// <param name="key"></param>
    639         /// <returns></returns>
    640         public byte[] getKeyFromString(string key)
    641         {
    642             byte[] bkey = new byte[10];
    643             int count = 0;
    644             foreach (char c in key)
    645                 if (c == '*')
    646                     return null;    //blocks not supported yet
    647                 else if (c == '0')
    648                     bkey[count++] = 0;
    649                 else
    650                     bkey[count++] = 1;
    651             return bkey;
    652         }
    653 
    654631        public IControlEncryption clone()
    655632        {
     
    738715        }
    739716
     717        public void changeSettings(string setting, object value)
     718        {
     719
     720        }
     721
     722        public KeyTranslator getKeyTranslator()
     723        {
     724            return new SDESKeyTranslator();
     725        }
     726
    740727        #endregion
    741 
    742         #region IControlEncryption Member
    743 
    744 
    745         public void changeSettings(string setting, object value)
    746         {
    747 
    748         }
     728    }
     729
     730    class SDESKeyTranslator : KeyTranslator
     731    {
     732        private KeyPattern pattern;
     733        private int progress = 0;
     734
     735        #region KeyTranslator Members
     736
     737        public void SetKeys(object keys)
     738        {
     739            if (!(keys is KeyPattern))
     740                throw new Exception("Something went horribly wrong!");
     741
     742            pattern = (KeyPattern)keys;
     743        }
     744
     745        public byte[] GetKey()
     746        {
     747            string key = pattern.getKey();
     748            byte[] bkey = new byte[10];
     749            int count = 0;
     750            foreach (char c in key)
     751                if (c == '0')
     752                    bkey[count++] = 0;
     753                else
     754                    bkey[count++] = 1;
     755            return bkey;
     756        }
     757
     758        public bool NextKey()
     759        {
     760            progress++;           
     761            return pattern.nextKey();
     762        }
     763
     764        public string GetKeyRepresentation()
     765        {
     766            return pattern.getKey();
     767        }
     768
     769        public int GetProgress()
     770        {
     771            int result = progress;
     772            progress = 0;
     773            return result;
     774        }
     775
    749776        #endregion
    750777    }
  • trunk/CrypPlugins/SDES/SDES.csproj

    r1487 r2010  
    137137      <Private>False</Private>
    138138    </ProjectReference>
     139    <ProjectReference Include="..\KeySearcher\KeySearcher.csproj">
     140      <Project>{0579E099-66B2-43C3-B8A0-43CAE4895E68}</Project>
     141      <Name>KeySearcher</Name>
     142    </ProjectReference>
    139143  </ItemGroup>
    140144  <ItemGroup>
  • trunk/CrypPlugins/Transposition/Transposition.cs

    r1932 r2010  
    11601160        }
    11611161
    1162         public byte[] getKeyFromString(string key)
    1163         {
    1164             return null;
    1165         }
    1166 
    11671162        public string getKeyPattern()
    11681163        {
     
    11791174        {
    11801175            plugin.changeSettings(setting, value);
     1176        }
     1177
     1178        public KeyTranslator getKeyTranslator()
     1179        {
     1180            throw new NotImplementedException();
    11811181        }
    11821182
Note: See TracChangeset for help on using the changeset viewer.