Ignore:
Timestamp:
Sep 15, 2009, 3:48:53 PM (12 years ago)
Author:
oruba
Message:

Performance improvement in the preprocessing phase.

Location:
trunk/CrypPlugins/CubeAttack
Files:
2 edited

Legend:

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

    r478 r519  
    3232        private string outputMaxterm;
    3333        private string outputKeyBits;
    34         private enum CubeAttackMode { findMaxterms, setPublicBits };
     34        private enum CubeAttackMode { preprocessing, setPublicBits };
    3535        private List<CryptoolStream> listCryptoolStreamsOut = new List<CryptoolStream>();
    3636        private bool stop = false;
     
    5858                    CryptoolStream cs = new CryptoolStream();
    5959                    listCryptoolStreamsOut.Add(cs);
    60                     cs.OpenRead(this.GetPluginInfoAttribute().Caption, Encoding.Default.GetBytes(outputMaxterm.ToCharArray()));
     60                    cs.OpenRead(Encoding.Default.GetBytes(outputMaxterm.ToCharArray()));
    6161                    return cs;
    6262                }
     
    8686                    CryptoolStream cs = new CryptoolStream();
    8787                    listCryptoolStreamsOut.Add(cs);
    88                     cs.OpenRead(this.GetPluginInfoAttribute().Caption, Encoding.Default.GetBytes(outputKeyBits.ToCharArray()));
     88                    cs.OpenRead(Encoding.Default.GetBytes(outputKeyBits.ToCharArray()));
    8989                    return cs;
    9090                }
     
    123123        /// Complete CubeAttack
    124124        /// </summary>
    125         public void FindMaxterms()
    126         {
    127             ProcessCubeAttack(CubeAttackMode.findMaxterms);
     125        public void Preprocessing()
     126        {
     127            ProcessCubeAttack(CubeAttackMode.preprocessing);
    128128        }
    129129
     
    212212        public void Execute()
    213213        {
    214             try
    215             {
    216                 switch (settings.Action)
    217                 {
    218                     case 0:
    219                         FindMaxterms();
    220                         break;
    221                     case 1:
    222                         SetPublicBits();
    223                         break;
    224                 }
    225             }
    226             catch (Exception ex)
    227             {
    228                 CubeAttack_LogMessage("Error: " +  ex, NotificationLevel.Error);
    229             }
    230             finally
    231             {
    232                 ProgressChanged(1.0, 1.0);
     214            if (settings.MaxCube > settings.PublicVar)
     215                CubeAttack_LogMessage("Error: Max cube size cannot be greater than Public bit size.", NotificationLevel.Error);
     216            else
     217            {
     218                try
     219                {
     220                    switch (settings.Action)
     221                    {
     222                        case 0:
     223                            Preprocessing();
     224                            break;
     225                        case 1:
     226                            SetPublicBits();
     227                            break;
     228                    }
     229                }
     230                catch (Exception ex)
     231                {
     232                    CubeAttack_LogMessage("Error: " + ex, NotificationLevel.Error);
     233                }
     234                finally
     235                {
     236                    ProgressChanged(1.0, 1.0);
     237                }
    233238            }
    234239        }
     
    272277                return result;
    273278           
    274             // ****** Beispiel Master Polynome ******
    275 
    276             //       i_0.0 * i_0.2 + i_0.0 * i_0.3 + i_0.1 * i_0.3 + i_0.0 + i_0.3 + i_0.0 * i_0.1 + i_0.1 * i_0.2 * i_0.3 + 1
    277             //return v[0]  & x[0]  ^ v[0]  & x[1]  ^ v[1]  & x[1]  ^ v[0]  ^ x[1]  ^ v[0]  & v[1]  ^ v[1]  & x[0]  & x[1]  ^ 1;
    278            
    279             //i_0.0 * i_0.1 * i_0.3 + i_0.0 * i_0.1 * i_0.4 + i_0.2 * i_0.3 * i_0.5 + i_0.1 * i_0.5 + i_0.0 * i_0.3 + i_0.0 * i_0.1 + i_0.3 * i_0.5 + i_0.1 + i_0.5 + 1
    280             //return v[0] & v[1] & x[0] ^ v[0] & v[1] & x[1] ^ v[2] & x[0] & x[2] ^ v[1] & x[2] ^ v[0] & x[0] ^ v[0] & v[1] ^
    281               //   x[0] & x[2] ^ v[1] ^ x[2] ^ 1;
    282 
    283             // i_0.0 * i_0.1 * i_0.3 + i_0.0 * i_0.1 * i_0.5 + i_0.2 * i_0.3 * i_0.4 + i_0.0 * i_0.3 + i_0.0 * i_0.4 + i_0.1 * i_0.5 + i_0.2 * i_0.4 + i_0.3 * i_0.5 + i_0.0 + i_0.1 + i_0.3 + i_0.4 + 1
    284             //return v[0] & v[1] & x[0] ^ v[0] & v[1] & x[2] ^ v[2] & x[0] & x[1] ^ v[0] & x[0] ^ v[0] & x[1] ^ v[1] & x[2] ^
    285               //         v[2] & x[1] ^ x[0] & x[2] ^ v[0] ^ v[1] ^ x[0] ^ x[1] ^ 1;
    286 
    287             //i_0.0 * i_0.1 * i_0.7 + i_0.2 * i_0.4 * i_0.6 + i_0.0 * i_0.3 * i_0.8 + i_0.0 * i_0.3 * i_0.7 + i_0.1 * i_0.2 * i_0.6 + i_0.3 * i_0.4 * i_0.9 + i_0.2 * i_0.4 * i_0.8 + i_0.2 * i_0.4 * i_0.9 + i_0.2 * i_0.4 * i_0.5 + i_0.2 * i_0.4 * i_0.7 + i_0.0 * i_0.1 * i_0.2 + i_0.0 * i_0.1 + i_0.3 * i_0.6 + i_0.3 * i_0.4 + i_0.6 * i_0.7 + i_0.6 * i_0.8 + i_0.4 + i_0.7 + i_0.6 + i_0.5 + i_0.1 * i_0.9
    288             /*return v[0] & v[1] & x[2] ^ v[2] & v[4] & x[1] ^ v[0] & v[3] & x[3] ^ v[0] & v[3] & x[2] ^
    289                 v[1] & v[2] & x[1] ^ v[3] & v[4] & x[4] ^ v[2] & v[4] & x[3] ^ v[2] & v[4] & x[4] ^
    290                 v[2] & v[4] & x[0] ^ v[2] & v[4] & x[2] ^ v[0] & v[1] & v[2] ^ v[0] & v[1] ^ v[3] & x[1] ^
    291                 v[3] & v[4] ^ x[1] & x[2] ^ x[1] & x[3] ^ v[4] ^ x[2] ^ x[1] ^ x[0] ^ v[1] & x[4];
    292             // ****** Ende Beispiel Master Polynome ****** */
    293 
    294 
    295279            /*// Begin Trivium
    296280            // Initialisierung
     
    384368            int[] secVarElement = new int[settings.SecretVar];
    385369
    386             CubeAttack_LogMessage("Computing superpoly...", NotificationLevel.Info);
     370            CubeAttack_LogMessage("Compute superpoly", NotificationLevel.Info);
    387371
    388372            // Compute the free term
     
    405389                        pubVarElement[cube[j]] = (i & (1 << j)) > 0 ? 1 : 0;
    406390                    coeff ^= Blackbox((int[])pubVarElement.Clone(), (int[])secVarElement.Clone());
     391
     392                    if (stop)
     393                    {
     394                        ProgressChanged(0.0, 1.0);
     395                        break;
     396                    }
    407397                }
    408398                superpoly.Add(constant ^ coeff);
     
    529519            int[] vecXY = new int[settings.SecretVar];
    530520
     521            CubeAttack_LogMessage("Linearity test", NotificationLevel.Info);
     522
    531523            for (int k = 0; k < settings.LinTest; k++)
    532524            {
    533                 //CubeAttack_LogMessage("Linearly Test " + k.ToString() + ": ", NotificationLevel.Info);
    534525                psLeft = 0;
    535526                psRight = 0;
     
    557548                if (psLeft != psRight)
    558549                    return false;
     550
     551                if (stop)
     552                {
     553                    ProgressChanged(0.0, 1.0);
     554                    break;
     555                }
    559556            }
    560557            return true;
     
    562559
    563560        /// <summary>
    564         /// Test if superpoly is constant.
     561        /// Test if superpoly is a constant value.
    565562        /// </summary>
    566563        /// <param name="cube">The summation Cube I.</param>
     
    575572            int[] pubVarElement = new int[settings.PublicVar];
    576573
    577             for (int i = 0; i < settings.SecretVar; i++)
     574            CubeAttack_LogMessage("Test if superpoly is constant", NotificationLevel.Info);
     575
     576            for (int i = 0; i < settings.ConstTest; i++)
    578577            {
    579578                for (int j = 0; j < settings.SecretVar; j++)
     
    584583                        pubVarElement[cube[k]] = (j & (1 << k)) > 0 ? 1 : 0;
    585584                    output ^= Blackbox(pubVarElement, vectorX);
     585
     586                    if (stop)
     587                    {
     588                        ProgressChanged(0.0, 1.0);
     589                        break;
     590                    }
    586591                }
    587592                if (i == 0)
     
    591596                output = 0;
    592597            }
    593             return true;
    594 
    595             /*for (int i = 0; i < Math.Pow(2, settings.SecretVar); i++)
    596             {
    597                 for (int j = 0; j < settings.SecretVar; j++)
    598                     secVarElement[j] = (i & (1 << j)) > 0 ? 1 : 0;
    599                 for (int j = 0; j < Math.Pow(2, cube.Count); j++)
    600                 {
    601                     for (int k = 0; k < cube.Count; k++)
    602                         pubVarElement[cube[k]] = (j & (1 << k)) > 0 ? 1 : 0;
    603                     output ^= Blackbox(pubVarElement, secVarElement);
    604                 }
    605                 if (i == 0)
    606                     flag = output;
    607                 if (flag != output)
    608                     return false;
    609                 output = 0;
    610             }
    611             return true; */
     598            return true;
    612599        }
    613600
     
    692679        /// Preprocessing Phase of the cube attack. Implementation of the algorithm RandomWalk to find maxterms.
    693680        /// </summary>
    694         public void FindMaxtermsPhase()
    695         {
     681        public void PreprocessingPhase()
     682        {
     683            CubeAttack_LogMessage("Begin preprocessing", NotificationLevel.Info);
     684
    696685            outputMaxterm = string.Empty;
    697686            int countMaxterms = 0;
     
    706695            List<List<int>> cubeIndex = new List<List<int>>();
    707696            List<List<int>> mCube = new List<List<int>>();
    708             int countRuns = 0;
    709697
    710698            // Save all public variables indexes in a list
     
    715703            while (countMaxterms < settings.SecretVar)
    716704            {
    717                 if (stop)
    718                 {
    719                     ProgressChanged(0.0, 1.0);
    720                     return;
    721                 }
    722 
    723                 // Maybe all maxterms have been found ?
    724                 if (countRuns > 300)
    725                     break;
    726                 countRuns++;
    727 
    728705                cube = new List<int>();
    729706                superpoly.Clear();
     
    731708                // Generate random size k between 1 and the number of public variables
    732709                numberOfVariables = rnd.Next(1, settings.MaxCube + 1);
     710
     711                // Permutation of the public variables
    733712                Shuffle<int>(chooseIndexI);
    734713
     714                // Construct cube of size k. Add k public variables to the cube
    735715                for (int i = 0; i < numberOfVariables; i++)
    736716                    cube.Add(chooseIndexI[i]);
    737 
    738                 int count = 0;
     717               
     718                string outputCube = string.Empty;
     719                foreach (int element in cube)
     720                    outputCube += "v" + element + " ";
     721                CubeAttack_LogMessage("Begin search for maxterm with subterm: " + outputCube, NotificationLevel.Info);
    739722                while (superpoly.Count == 0)
    740723                {
    741                     if (count > 200)
     724                    if (cube.Count == 0)
     725                    {
     726                        // Subterm is empty, restart with new subset
    742727                        break;
    743                     count++;
    744                     if (IsSuperpolyConstant(cube) && (cube.Count != 0))
     728                    }
     729
     730                    if (IsSuperpolyConstant(cube))
     731                    {
     732                        CubeAttack_LogMessage("Superpoly is constant, drop variable v" + cube[0], NotificationLevel.Info);
    745733                        cube.RemoveAt(0);
     734                    }
    746735                    else if (!IsLinear(cube))
    747736                    {
     737                        CubeAttack_LogMessage("Superpoly is not linear", NotificationLevel.Info);
    748738                        if (numberOfVariables < chooseIndexI.Count)
    749739                        {
    750                             cube.Add(chooseIndexI[numberOfVariables]);
    751                             numberOfVariables++;
     740                            if (cube.Count <= settings.MaxCube)
     741                            {
     742                                CubeAttack_LogMessage("Add variable v" + chooseIndexI[numberOfVariables], NotificationLevel.Info);
     743                                cube.Add(chooseIndexI[numberOfVariables]);
     744                                numberOfVariables++;
     745                            }
    752746                        }
    753747                        else
     
    756750                    else
    757751                    {
    758                         if (cube.Count > 0)
     752                        if (!CubeKnown(mCube, cube))
    759753                        {
    760                             string bla = string.Empty;
    761                             for (int i = 0; i < cube.Count; i++)
    762                                 bla += cube[i].ToString();
    763                             //CubeAttack_LogMessage("cube values: " + bla, NotificationLevel.Error);
    764                             if (!CubeKnown(mCube, cube))
    765                             {
    766                                 mCube.Add(cube);
    767                                 superpoly = ComputePSI(cube);
    768                             }
     754                            mCube.Add(cube);
     755                            outputCube = string.Empty;
     756                            foreach (int element in cube)
     757                                outputCube += "v" + element + " ";
     758                            CubeAttack_LogMessage(outputCube + " is new maxterm", NotificationLevel.Info);
     759                            superpoly = ComputePSI(cube);
     760                            break;
    769761                        }
    770                     }
     762                        else
     763                        {
     764                            // Maxterm is already known, break and restart with new subset
     765                            CubeAttack_LogMessage("Maxterm is already known, restart with new subset", NotificationLevel.Info);
     766                            break;
     767                        }
     768                    }
     769
     770                    outputCube = string.Empty;
     771                    foreach (int element in cube)
     772                        outputCube += "v" + element + " ";
     773                    CubeAttack_LogMessage("Subterm: " + outputCube, NotificationLevel.Info);
    771774                }
    772775
     
    791794                        mCheckLinearity = mCheckLinearity.DeleteLastRow();
    792795                }
     796                if (stop)
     797                {
     798                    ProgressChanged(0.0, 1.0);
     799                    return;
     800                }
    793801            }
    794802
     
    811819                }
    812820            }
    813             else
    814                 CubeAttack_LogMessage("Only " + countMaxterms.ToString() + " maxterms have been found !", NotificationLevel.Info);
    815821        }
    816822
     
    823829        public void OnlinePhase(Matrix mSuperpoly, Vector b, List<List<int>> cubeIndex)
    824830        {
    825             int[] secVarElement = new int[settings.SecretVar];
    826             secVarElement[0] = 1; secVarElement[1] = 1; //secVarElement[2] = 0; secVarElement[3] = 0; secVarElement[4] = 0;
     831            CubeAttack_LogMessage("Begin online phase", NotificationLevel.Info);
     832
    827833            int[] pubVarElement = new int[settings.PublicVar];
    828834           
     
    835841                    for (int l = 0; l < cubeIndex[i].Count; l++)
    836842                        pubVarElement[cubeIndex[i][l]] = (k & (1 << l)) > 0 ? 1 : 0;
    837                     //b[i] ^= Blackbox(pubVarElement, secVarElement);
     843
    838844                    try
    839845                    {
     
    841847
    842848                        for (int l = 0; l < pubVarElement.Length; l++)
    843                         {
    844849                            vBool[l] = Convert.ToBoolean(pubVarElement[l]);
    845                         }
    846850
    847851                        b[i] ^= TestProperty.SolveFunction(null, vBool, 2);
     
    852856                    }
    853857                }
     858                CubeAttack_LogMessage("Secret bit x" + i + " = " + b[i], NotificationLevel.Info);
    854859            }
    855860            OutputKey(mSuperpoly * b);
     
    907912                    else
    908913                    {
    909                         CubeAttack_LogMessage("Summation cube must contain at least one variable !", NotificationLevel.Error);
     914                        StringBuilder output = new StringBuilder(string.Empty);
     915                        output.Append("Output bit: " + Blackbox(pubVari, secVari));
     916                        outputMaxterm += output.ToString();
     917                        OnPropertyChanged("OutputMaxterm");
     918                        CubeAttack_LogMessage("Output bit: " + Blackbox(pubVari, secVari), NotificationLevel.Info);
    910919                    }
    911920                }
     
    928937            switch (mode)
    929938            {
    930                 case CubeAttackMode.findMaxterms:
    931                     FindMaxtermsPhase();
     939                case CubeAttackMode.preprocessing:
     940                    PreprocessingPhase();
    932941                    break;
    933942                case CubeAttackMode.setPublicBits:
     
    958967            {
    959968                if (value != null)
    960                 {
    961969                    testProperty = value;
    962                     /* try
    963                     {
    964                         // here comes the function to be solved, now just a dummy
    965                         string function = "i_0.0 + i_0.1";
    966                         // the result of the function
    967                         int result = -1;
    968                         // the data to fill the functin variables
    969                         bool[] data = new bool[] { false, true };
    970                         // the result is computed by calling the SolveFunction function with parameters
    971                         // the SolveFunction is also implemented by the slave, the BooleanFunctionParser
    972                         result = testProperty.SolveFunction(function, data);
    973                         GuiLogMessage("Rückgabewert: " + result, NotificationLevel.Info);
    974                     }
    975                     catch (Exception ex)
    976                     {
    977                         GuiLogMessage("Problem: " + ex, NotificationLevel.Error);
    978                     }
    979                     */
    980                 }
    981970            }
    982971        }
  • trunk/CrypPlugins/CubeAttack/CubeAttackSettings.cs

    r472 r519  
    4747        private int secretVar;
    4848        private int maxcube;
    49         private int linTest = 100;
    50         private string setPublicBits = "0*00*000*00***0000*00000000*0000000*0*0*000000*0*0***0*0*00000**0*000000*00000*0";
     49        private int constTest = 50;
     50        private int linTest = 50;
     51        private string setPublicBits = "0*00*";
    5152       
    5253        #endregion
     
    6263            ContextMenuControlType.ComboBox,
    6364            null,
    64             "Find maxterms",
    65             "Set public bits" )]
     65            "Preprocessing/Online Phase",
     66            "Input public bits")]
    6667        [TaskPane("Action",
    6768            "Select the phase",
     
    7071            false,
    7172            DisplayLevel.Beginner,
    72             ControlType.ComboBox, 
    73             new string[] { "Find maxterms", "Set public bits" })]
     73            ControlType.ComboBox,
     74            new string[] { "Preprocessing/Online Phase", "Input public bits" })]
    7475        public int Action
    7576        {
     
    8485
    8586        [PropertySaveOrder(2)]
    86         [ContextMenu("Try to recover key",
    87             "Online phase of the cube attack which tries to solve the system of linear maxterm equations to recover the secret key.",
     87        [ContextMenu("Try to discover key",
     88            "Online phase of the cube attack which tries to solve the system of linear maxterm equations to discover the secret key.",
    8889            2,
    8990            DisplayLevel.Beginner,
     
    9192            null,
    9293            "")]
    93         [TaskPane("Try to recover key",
    94             "Online phase of the cube attack which tries to solve the system of linear maxterm equations to recover the secret key.",
     94        [TaskPane("Try to discover key",
     95            "Online phase of the cube attack which tries to solve the system of linear maxterm equations to discover the secret key.",
    9596            null,
    9697            2,
     
    110111
    111112        [PropertySaveOrder(3)]
    112         [TaskPane("Public variables",
    113             "Number of public variables.",
     113        [TaskPane("Public bit size",
     114            "Public input bits (IV or plaintext) of the attacked cryptosystem.",
    114115            null,
    115116            3,
     
    132133
    133134        [PropertySaveOrder(4)]
    134         [TaskPane("Secret variables",
    135             "Number of secret variables.",
     135        [TaskPane("Secret bit size",
     136            "Key size or key length  of the attacked cryptosystem.",
    136137            null,
    137138            4,
     
    155156        [PropertySaveOrder(5)]
    156157        [TaskPane("Max cube size",
    157             "Maxmium size of cube.",
     158            "Maxmium size of the summation cube.",
    158159            null,
    159160            5,
     
    176177
    177178        [PropertySaveOrder(6)]
    178         [TaskPane("Linearity tests",
    179             "Number of linearity tests.",
    180             null,
    181             6,
     179        [TaskPane("Constant Test",
     180            "Number of tests to check if the superpoly is a constant value or not.",
     181            null,
     182            6,
     183            false,
     184            DisplayLevel.Beginner,
     185            ControlType.NumericUpDown,
     186            ValidationType.RangeInteger,
     187            0,
     188            100000)]
     189        public int ConstTest
     190        {
     191            get { return constTest; }
     192            set
     193            {
     194                if (value != this.constTest) HasChanges = true;
     195                constTest = value;
     196                OnPropertyChanged("ConstTest");
     197            }
     198        }
     199
     200        [PropertySaveOrder(7)]
     201        [TaskPane("Linearity tests",
     202            "Number of linearity tests to check if the superpoly is linear or not.",
     203            null,
     204            7,
    182205            false,
    183206            DisplayLevel.Beginner,
     
    197220        }
    198221
    199         [PropertySaveOrder(7)]
    200         [TaskPane("Set public bits",
     222        [PropertySaveOrder(8)]
     223        [TaskPane("Input public bits",
    201224            "Manual input of public bits.",
    202225            null,
    203             6,
    204             false,
    205             DisplayLevel.Beginner,
    206             ControlType.TextBox, 
     226            8,
     227            false,
     228            DisplayLevel.Beginner,
     229            ControlType.TextBox,
    207230            null)]
    208231        public string SetPublicBits
Note: See TracChangeset for help on using the changeset viewer.