source: trunk/CrypPlugins/CubeAttack/CubeAttack.cs @ 840

Last change on this file since 840 was 840, checked in by oruba, 12 years ago
  • modified preprocessing phase
  • results can be saved in .cte-files
File size: 48.0 KB
Line 
1using System;
2using System.Collections.Generic;
3using System.Linq;
4using System.Text;
5using System.IO;
6using System.ComponentModel;
7using System.Windows.Controls;
8using Cryptool.PluginBase;
9using Cryptool.PluginBase.Analysis;
10using Cryptool.PluginBase.Cryptography;
11using Cryptool.PluginBase.Miscellaneous;
12using Cryptool.PluginBase.IO;
13// Reference to the CubeAttackController interface (own dll)
14using Cryptool.CubeAttackController;
15
16namespace Cryptool.CubeAttack
17{
18    [Author("David Oruba",
19        "david.oruba@web.de",
20        "Uni-Bochum",
21        "http://www.ruhr-uni-bochum.de/")]
22    [PluginInfo(true,
23        "Cube Attack",
24        "Cube Attack",
25        "CubeAttack/DetailedDescription/Description.xaml",
26        "CubeAttack/Images/ca_color.png")]
27    public class CubeAttack : IAnalysisMisc
28    {
29        #region Private variables
30
31        private CubeAttackSettings settings;
32        private string outputKeyBits;
33        private enum CubeAttackMode { preprocessing, online, setPublicBits };
34        private List<CryptoolStream> listCryptoolStreamsOut = new List<CryptoolStream>();
35        private bool stop = false;
36       
37        #endregion
38
39
40        #region Public variables
41
42        public int[] pubVarGlob = null;
43        public int indexOutputBit = 1;
44
45        public string outputSuperpoly = null;
46        public Matrix superpolyMatrix = null;
47        public List<List<int>> listCubeIndexes = null;
48        public int[] outputBitIndex = null;
49        public int countSuperpoly = 0;
50        public Matrix matrixCheckLinearitySuperpolys = null;
51
52        #endregion
53
54
55        #region Properties (Inputs/Outputs)
56       
57        [PropertyInfo(Direction.OutputData,
58            "Output of superpolys",
59            "Output of located linearly independent superpolys, cube indexes and its corresponding output bits.",
60            "",
61            false,
62            false,
63            DisplayLevel.Beginner,
64            QuickWatchFormat.Text,
65            null)]
66        public CryptoolStream OutputSuperpoly
67        {
68            get
69            {
70                if (outputSuperpoly != null)
71                {
72                    CryptoolStream cs = new CryptoolStream();
73                    listCryptoolStreamsOut.Add(cs);
74                    cs.OpenRead(Encoding.Default.GetBytes(outputSuperpoly.ToCharArray()));
75                    return cs;
76                }
77                else
78                {
79                    return null;
80                }
81            }
82            set { }
83        }
84
85        [PropertyInfo(Direction.OutputData,
86            "Key bits",
87            "This output provides the result of the secret key bits",
88            "",
89            false,
90            false,
91            DisplayLevel.Beginner,
92            QuickWatchFormat.Text,
93            null)]
94        public CryptoolStream OutputKeyBits
95        {
96            get
97            {
98                if (outputKeyBits != null)
99                {
100                    CryptoolStream cs = new CryptoolStream();
101                    listCryptoolStreamsOut.Add(cs);
102                    cs.OpenRead(Encoding.Default.GetBytes(outputKeyBits.ToCharArray()));
103                    return cs;
104                }
105                else
106                {
107                    return null;
108                }
109            }
110            set { }
111        }
112
113        #endregion
114
115
116        #region Public interface
117
118        /// <summary>
119        /// Contructor
120        /// </summary>
121        public CubeAttack()
122        {
123            this.settings = new CubeAttackSettings();
124            ((CubeAttackSettings)(this.settings)).LogMessage += CubeAttack_LogMessage;
125        }
126
127        /// <summary>
128        /// Get or set all settings for this algorithm
129        /// </summary>
130        public ISettings Settings
131        {
132            get { return (ISettings)this.settings; }
133            set { this.settings = (CubeAttackSettings)value; }
134        }     
135
136        public void Preprocessing()
137        {
138            ProcessCubeAttack(CubeAttackMode.preprocessing);
139        }
140
141        public void Online()
142        {
143            ProcessCubeAttack(CubeAttackMode.online);
144        }
145
146        public void SetPublicBits()
147        {
148            ProcessCubeAttack(CubeAttackMode.setPublicBits);
149        }
150
151        #endregion
152
153
154        #region IPlugin members
155
156        public void Initialize()
157        {
158        }
159
160        public void Dispose()
161        {
162            stop = false;
163            foreach (CryptoolStream stream in listCryptoolStreamsOut)
164            {
165                stream.Close();
166            }
167            listCryptoolStreamsOut.Clear();
168        }
169
170        public bool HasChanges
171        {
172            get { return settings.HasChanges; }
173            set { settings.HasChanges = value; }
174        }
175
176        /// <summary>
177        /// Fire, if progress bar has to be updated
178        /// </summary>
179        public event PluginProgressChangedEventHandler OnPluginProgressChanged;
180        private void ProgressChanged(double value, double max)
181        {
182            EventsHelper.ProgressChanged(OnPluginProgressChanged, this, new PluginProgressEventArgs(value, max));
183        }
184
185        /// <summary>
186        /// Fire, if new message has to be shown in the status bar
187        /// </summary>
188        public event GuiLogNotificationEventHandler OnGuiLogNotificationOccured;
189
190        public UserControl Presentation
191        {
192            get { return null; }
193        }
194
195        public UserControl QuickWatchPresentation
196        {
197            get { return null; }
198        }
199
200        public void Stop()
201        {
202            this.stop = true;
203            if (settings.Action == 0) // Action = Preprocessing
204            {
205                settings.SaveOutputSuperpoly = outputSuperpoly; 
206                settings.SaveSuperpolyMatrix = superpolyMatrix;
207                settings.SaveListCubeIndexes = listCubeIndexes;
208                settings.SaveOutputBitIndex = outputBitIndex;
209                settings.SaveCountSuperpoly = countSuperpoly;
210                settings.SaveMatrixCheckLinearitySuperpolys = matrixCheckLinearitySuperpolys;
211                settings.SavePublicBitSize = settings.PublicVar;
212                settings.SaveSecretBitSize = settings.SecretVar;
213            }
214        }
215
216        public void PostExecution()
217        {
218            Dispose();
219        }
220
221        public void PreExecution()
222        {
223            Dispose();
224            if (settings.Action == 0) // Action = Preprocessing
225            { 
226                if ((settings.PublicVar != settings.SavePublicBitSize) || (settings.SecretVar != settings.SaveSecretBitSize))
227                {
228                    settings.SaveCountSuperpoly = 0;
229                    settings.SaveListCubeIndexes = null;
230                    settings.SaveMatrixCheckLinearitySuperpolys = null;
231                    settings.SaveOutputBitIndex = null;
232                    settings.SaveOutputSuperpoly = null;
233                    settings.SaveSuperpolyMatrix = null;
234
235                    outputSuperpoly = string.Empty;
236                    superpolyMatrix = new Matrix(settings.SecretVar, settings.SecretVar + 1);
237                    listCubeIndexes = new List<List<int>>();
238                    outputBitIndex = new int[settings.SecretVar];
239                    countSuperpoly = 0;
240                    matrixCheckLinearitySuperpolys = new Matrix(0, settings.SecretVar);
241                }
242
243                if (settings.SaveCountSuperpoly != settings.SecretVar)
244                {
245                    if (settings.SaveOutputSuperpoly != null)
246                        outputSuperpoly = settings.SaveOutputSuperpoly;
247                    if (settings.SaveSuperpolyMatrix != null)
248                        superpolyMatrix = settings.SaveSuperpolyMatrix;
249                    if (settings.SaveListCubeIndexes != null)
250                        listCubeIndexes = settings.SaveListCubeIndexes;
251                    if (settings.SaveOutputBitIndex != null)
252                        outputBitIndex = settings.SaveOutputBitIndex;
253                    if (settings.SaveCountSuperpoly != 0)
254                        countSuperpoly = settings.SaveCountSuperpoly;
255                    if (settings.SaveMatrixCheckLinearitySuperpolys != null)
256                        matrixCheckLinearitySuperpolys = settings.SaveMatrixCheckLinearitySuperpolys;
257                }
258            }
259        }
260
261        #pragma warning disable 67
262                public event StatusChangedEventHandler OnPluginStatusChanged;
263        #pragma warning restore
264
265        private void GuiLogMessage(string message, NotificationLevel logLevel)
266        {
267            EventsHelper.GuiLogMessage(OnGuiLogNotificationOccured, this, new GuiLogEventArgs(message, this, logLevel));
268        }
269
270        public void Execute()
271        {
272            if (settings.MaxCube > settings.PublicVar)
273                CubeAttack_LogMessage("Error: Max Cube Size cannot be greater than Public Bit Size.", NotificationLevel.Error);
274            else
275            {
276                try
277                {
278                    switch (settings.Action)
279                    {
280                        case 0:
281                            Preprocessing();
282                            break;
283                        case 1:
284                            Online();
285                            break;
286                        case 2:
287                            SetPublicBits();
288                            break;
289                    }
290                }
291                catch (Exception ex)
292                {
293                    CubeAttack_LogMessage("Error: " + ex, NotificationLevel.Error);
294                }
295                finally
296                {
297                    ProgressChanged(1.0, 1.0);
298                }
299            }
300        }
301
302        /// <summary>
303        /// The function returns the black box output bit.
304        /// </summary>
305        /// <param name="v">Public variables.</param>
306        /// <param name="x">Secret variables.</param>
307        /// <returns>Returns the black box output bit, either 0 or 1.</returns>
308        public int Blackbox(int[] v, int[] x)
309        {
310            int result = 0;
311            try
312            {
313                result = CubeattackBlackbox.GenerateBlackboxOutputBit(v, x, indexOutputBit);
314            }
315            catch (Exception ex)
316            {
317                stop = true;
318                CubeAttack_LogMessage("Error: " + ex, NotificationLevel.Error);
319            }
320            return result; 
321        }
322
323        /// <summary>
324        /// The function derives the algebraic structure of the superpoly from the maxterm.
325        /// The structure is derived by computing the free term and the coefficients in the superpoly.
326        /// </summary>
327        /// <param name="pubVarElement">Public variables.</param>
328        /// <param name="maxterm">Maxterm.</param>
329        /// <returns>Returns the superpoly.</returns>
330        public List<int> ComputeSuperpoly(int[] pubVarElement, List<int> maxterm)
331        {
332            int constant = 0;
333            int coeff = 0;
334            List<int> superpoly = new List<int>();
335            int[] secVarElement = new int[settings.SecretVar];
336
337            if (settings.EnableLogMessages)
338                CubeAttack_LogMessage("Start deriving the algebraic structure of the superpoly", NotificationLevel.Info);
339
340            // Compute the free term
341            for (ulong i = 0; i < Math.Pow(2, maxterm.Count); i++)
342            {
343                if (stop)
344                    return superpoly;
345                for (int j = 0; j < maxterm.Count; j++)
346                    pubVarElement[maxterm[j]] = (i & ((ulong)1 << j)) > 0 ? 1 : 0;
347                constant ^= Blackbox((int[])pubVarElement.Clone(), (int[])secVarElement.Clone());
348            }
349            superpoly.Add(constant);
350
351            if (settings.EnableLogMessages)
352                CubeAttack_LogMessage("Constant term = " + (constant).ToString(), NotificationLevel.Info);
353
354            // Compute coefficients
355            for (int k = 0; k < settings.SecretVar; k++)
356            {
357                for (ulong i = 0; i < Math.Pow(2, maxterm.Count); i++)
358                {
359                    if (stop)
360                        return superpoly;
361                    secVarElement[k] = 1;
362                    for (int j = 0; j < maxterm.Count; j++)
363                        pubVarElement[maxterm[j]] = (i & ((ulong)1 << j)) > 0 ? 1 : 0;
364                    coeff ^= Blackbox((int[])pubVarElement.Clone(), (int[])secVarElement.Clone());
365                }
366                superpoly.Add(constant ^ coeff);
367
368                if (settings.EnableLogMessages)
369                    CubeAttack_LogMessage("Coefficient of x" + k + " = " + (constant ^ coeff), NotificationLevel.Info);
370               
371                coeff = 0;
372                secVarElement[k] = 0;
373            }
374            return superpoly;
375        }
376
377        /// <summary>
378        /// The function outputs the superpolys, cube indexes and output bits.
379        /// </summary>
380        /// <param name="cubeIndexes">The cube indexes of the maxterm.</param>
381        /// <param name="superpoly">The superpoly for the given cube indexes.</param>
382        public void OutputSuperpolys(List<int> cubeIndexes, List<int> superpoly)
383        {
384            StringBuilder output = new StringBuilder(string.Empty);
385            bool superpolyIsEmpty = true;
386            bool flag = false;
387            output.Append("Superpoly: ");
388            if (superpoly[0] == 1)
389            {
390                output.Append("1");
391                superpolyIsEmpty = false;
392                flag = true;
393            }
394            for (int i = 1; i < superpoly.Count; i++)
395                if (superpoly[i] == 1)
396                {
397                    if (flag)
398                        output.Append("+x" + Convert.ToString(i - 1));
399                    else
400                        output.Append("x" + Convert.ToString(i - 1));
401                    superpolyIsEmpty = false;
402                    flag = true;
403                }
404            if (superpolyIsEmpty)
405                output.Append("0");
406            output.Append("   Cube Indexes: {");
407            if (cubeIndexes.Count > 0)
408            {
409                cubeIndexes.Sort();
410                for (int i = 0; i < cubeIndexes.Count - 1; i++)
411                    output.Append(cubeIndexes[i] + ",");
412                output.Append(cubeIndexes[cubeIndexes.Count - 1] + "}");
413            }
414            else
415                output.Append(" }");
416
417            output.Append("   Output Bit: " + indexOutputBit + "\n");
418            outputSuperpoly += output.ToString();
419            OnPropertyChanged("OutputSuperpoly");
420        }
421
422        /// <summary>
423        /// The function outputs the key bits.
424        /// </summary>
425        /// <param name="res">Result vector</param>
426        public void OutputKey(Vector res)
427        {
428            StringBuilder output = new StringBuilder(string.Empty);
429            for (int i=0; i<res.Length; i++)
430                output.AppendLine("x" + i + " = " + res[i]);
431            outputKeyBits = output.ToString();
432        }
433
434        /// <summary>
435        /// Test if superpoly is already in matrix.
436        /// </summary>
437        /// <param name="superpoly">The superpoly.</param>
438        /// <param name="matrix">An n x n matrix whose rows contain their corresponding superpolys.</param>
439        /// <returns>A boolean value indicating if the superpoly is in the matrix or not.</returns>
440        public bool InMatrix(List<int> superpoly, Matrix matrix)
441        {
442            bool isEqual = true;
443            for (int i = 0; i < matrix.Rows; i++)
444            {
445                isEqual = true;
446                for (int j = 0; j < superpoly.Count; j++)
447                    if (matrix[i, j] != superpoly[j])
448                        isEqual = false;
449                if (isEqual)
450                    return true;
451            }
452            return false;
453        }
454
455        /// <summary>
456        /// Test if a maxterm is already known.
457        /// </summary>
458        /// <param name="cubeList">A list of cube indexes.</param>
459        /// <param name="maxterm">The located maxterm.</param>
460        /// <returns>A boolean value indicating if the maxterm is already in the list of cubes indexes or not.</returns>
461        public bool MaxtermKnown(List<List<int>> cubeList, List<int> maxterm)
462        {
463            bool isEqual = true;
464            for (int i = 0; i < cubeList.Count; i++)
465            {
466                isEqual = true;
467                if (cubeList[i].Count == maxterm.Count)
468                {
469                    for (int j = 0; j < maxterm.Count; j++)
470                        if (!cubeList[i].Contains(maxterm[j]))
471                            isEqual = false;
472                    if (isEqual)
473                        return true;
474                }
475            }
476            return false;
477        }
478
479        /// <summary>
480        /// Test if a superpoly is linear (BLR linearity test).
481        /// </summary>
482        /// <param name="pubVarElement">Public variables.</param>
483        /// <param name="maxterm">The located maxterm.</param>
484        /// <returns>A boolean value indicating if the superpoly is probably linear or not.</returns>
485        public bool IsSuperpolyLinear(int[] pubVarElement, List<int> maxterm)
486        {
487            Random rnd = new Random();
488            int psLeft = 0;
489            int psRight = 0;
490            int[] vectorX = new int[settings.SecretVar];
491            int[] vectorY = new int[settings.SecretVar];
492            int[] vecXY = new int[settings.SecretVar];
493
494            for (int k = 0; k < settings.LinTest; k++)
495            {
496                if (settings.EnableLogMessages)
497                    CubeAttack_LogMessage("Linearity test " + (k + 1) + " of " + settings.LinTest, NotificationLevel.Info);
498               
499                psLeft = 0;
500                psRight = 0;
501
502                // Choose vectors x and y at random
503                for (int i = 0; i < settings.SecretVar; i++)
504                {
505                    vectorX[i] = rnd.Next(0, 2);
506                    vectorY[i] = rnd.Next(0, 2);
507                }
508
509                pubVarElement = new int[settings.PublicVar];
510                for (int i = 0; i < settings.SecretVar; i++)
511                    vecXY[i] = (vectorX[i] ^ vectorY[i]);
512
513                for (ulong i = 0; i < Math.Pow(2, maxterm.Count); i++)
514                {
515                    if (stop)
516                        return false;
517                    for (int j = 0; j < maxterm.Count; j++)
518                        pubVarElement[maxterm[j]] = (i & ((ulong)1 << j)) > 0 ? 1 : 0;
519                    psLeft ^= Blackbox((int[])pubVarElement.Clone(), new int[settings.SecretVar]) 
520                            ^ Blackbox((int[])pubVarElement.Clone(), (int[])vectorX.Clone()) 
521                            ^ Blackbox((int[])pubVarElement.Clone(), (int[])vectorY.Clone());
522                    psRight ^= Blackbox((int[])pubVarElement.Clone(), (int[])vecXY.Clone());
523                }
524                if (psLeft != psRight)
525                {
526                    if (settings.EnableLogMessages)
527                        CubeAttack_LogMessage("Linearity test " + (k + 1) + " failed", NotificationLevel.Info);
528                    return false;
529                }
530                if (stop)
531                    return false;
532            }
533            return true;
534        }
535
536        /// <summary>
537        /// Test if superpoly is a constant value.
538        /// </summary>
539        /// <param name="pubVarElement">Public variables.</param>
540        /// <param name="maxterm">The located maxterm.</param>
541        /// <returns>A boolean value indicating if the superpoly is constant or not.</returns>
542        public bool IsSuperpolyConstant(int[] pubVarElement, List<int> maxterm)
543        {
544            Random rnd = new Random();
545            int[] vectorX = new int[settings.SecretVar];
546            int flag = 0;
547            int output = 0;
548            int[] secVarElement = new int[settings.SecretVar];
549
550            string outputCube = string.Empty;
551            foreach (int element in maxterm)
552                outputCube += "v" + element + " ";
553            if(settings.ConstTest > 0)
554                if (settings.EnableLogMessages)
555                    CubeAttack_LogMessage("Test if superpoly of subset " + outputCube + " is constant", NotificationLevel.Info);
556            for (int i = 0; i < settings.ConstTest; i++)
557            {
558                for (int j = 0; j < settings.SecretVar; j++)
559                    vectorX[j] = rnd.Next(0, 2);
560                for (ulong j = 0; j < Math.Pow(2, maxterm.Count); j++)
561                {
562                    if (stop)
563                        return false;
564                    for (int k = 0; k < maxterm.Count; k++)
565                        pubVarElement[maxterm[k]] = (j & ((ulong)1 << k)) > 0 ? 1 : 0;
566                    output ^= Blackbox(pubVarElement, vectorX);
567                }
568                if (i == 0)
569                    flag = output;
570                if (flag != output)
571                {
572                    if (settings.EnableLogMessages)
573                        CubeAttack_LogMessage("Superpoly of subset " + outputCube + " is not constant", NotificationLevel.Info);
574                    return false;
575                }
576                output = 0;
577                if (stop)
578                    return false;
579            }
580            if (settings.ConstTest > 0)
581                return true;
582            else
583                return false;
584        }
585
586        /// <summary>
587        /// Generates a random permutation of a finite set—in plain terms, for randomly shuffling the set.
588        /// </summary>
589        /// <param name="ilist">A List of values.</param>
590        public static void Shuffle(List<int> ilist)
591        {
592            Random rand = new Random();
593            int iIndex;
594            int tTmp;
595            for (int i = 1; i < ilist.Count; ++i)
596            {
597                iIndex = rand.Next(i + 1);
598                tTmp = ilist[i];
599                ilist[i] = ilist[iIndex];
600                ilist[iIndex] = tTmp;
601            }
602        }
603
604        /// <summary>
605        /// Test if an n x m matrix contains n linearly independent vectors.
606        /// </summary>
607        /// <param name="A">n x m matrix.</param>
608        /// <returns>A boolean value indicating if the matrix is regular or not.</returns>
609        public bool IsLinearIndependent(Matrix A)
610        {
611            double maxval;
612            int maxind;
613            double temp;
614            int Rang = 0;
615            double[,] a = new double[A.Cols, A.Rows];
616
617            for (int i = 0; i < A.Cols; i++)
618                for (int j = 0; j < A.Rows; j++)
619                    a[i, j] = A[j, i];
620
621            for (int j = 0; j < A.Rows; j++)
622            {
623                // Find maximum
624                maxval = a[j, j];
625                maxind = j;
626                for (int k = j; k < A.Cols; k++)
627                {
628                    if (a[k, j] > maxval)
629                    {
630                        maxval = a[k, j];
631                        maxind = k;
632                    }
633                    if (-a[k, j] > maxval)
634                    {
635                        maxval = -a[k, j];
636                        maxind = k;
637                    }
638                }
639
640                if (maxval != 0)
641                {
642                    Rang++;
643                    // Swap_Rows(j, maxind)
644                    for (int k = j; k < A.Rows; k++)
645                    {
646                        temp = a[j, k];
647                        a[j, k] = a[maxind, k];
648                        a[maxind, k] = temp;
649                    }
650
651                    // Gauss elimination
652                    for (int i = j + 1; i < A.Cols; i++)
653                        for (int k = j + 1; k < A.Rows; k++)
654                            a[i, k] = a[i, k] - (a[i, j] / a[j, j] * a[j, k]);
655                }
656            }
657            if (A.Rows == Rang)
658                return true;
659            else
660                return false;
661        } 
662
663        /// <summary>
664        /// Preprocessing phase of the cube attack.
665        /// </summary>
666        public void PreprocessingPhase()
667        {
668            indexOutputBit = settings.OutputBit;
669            pubVarGlob = null;
670
671            if (countSuperpoly == settings.SecretVar)
672            {
673                outputSuperpoly = string.Empty;
674                superpolyMatrix = new Matrix(settings.SecretVar, settings.SecretVar + 1);
675                listCubeIndexes = new List<List<int>>();
676                outputBitIndex = new int[settings.SecretVar];
677                countSuperpoly = 0;
678                matrixCheckLinearitySuperpolys = new Matrix(0, settings.SecretVar);
679            }
680
681            if (outputSuperpoly == null)
682                outputSuperpoly = string.Empty;
683            if (superpolyMatrix == null)
684                superpolyMatrix = new Matrix(settings.SecretVar, settings.SecretVar + 1);
685            if (listCubeIndexes == null)
686                listCubeIndexes = new List<List<int>>();
687            if (outputBitIndex == null)
688                outputBitIndex = new int[settings.SecretVar];
689            if (matrixCheckLinearitySuperpolys == null)
690                matrixCheckLinearitySuperpolys = new Matrix(0, settings.SecretVar);
691
692            CubeAttack_LogMessage("Start preprocessing: \nTry to find " + settings.SecretVar + " linearly independent superpolys. (Already found: " + countSuperpoly + ")", NotificationLevel.Info);
693
694            Random rnd = new Random();
695            int numberOfVariables = 0;
696            List<int> chooseIndexI = new List<int>();
697            List<int> superpoly = new List<int>();
698            List<int> maxterm = new List<int>();
699            List<List<int>> cubeList = new List<List<int>>();
700            string outputCube = string.Empty;
701
702            // Save all public variables indexes in a list
703            for (int i = 0; i < settings.PublicVar; i++)
704                chooseIndexI.Add(i);
705
706            // Find n maxterms and save their in the matrix
707            while (countSuperpoly < settings.SecretVar)
708            {
709                if (stop)
710                    return;
711                else
712                {
713                    maxterm = new List<int>();
714                    superpoly.Clear();
715
716                    // Generate random size k between 1 and the number of public variables
717                    numberOfVariables = rnd.Next(1, settings.MaxCube + 1);
718
719                    // Permutation of the public variables
720                    Shuffle(chooseIndexI);
721
722                    // Construct cube of size k. Add k public variables to the cube
723                    for (int i = 0; i < numberOfVariables; i++)
724                        maxterm.Add(chooseIndexI[i]);
725
726                    if (settings.EnableLogMessages)
727                    {
728                        foreach (int element in maxterm)
729                            outputCube += "v" + element + " ";
730                        CubeAttack_LogMessage("Start search for maxterm with subterm: " + outputCube, NotificationLevel.Info);
731                    }
732                    if (settings.OutputBit != indexOutputBit)
733                    {
734                        // User has changed Output Bit index, store new value
735                        indexOutputBit = settings.OutputBit;
736
737                        // Reset list of cube indexes, since a single maxterms can be associated with multiple superpolys from different outputs
738                        cubeList = new List<List<int>>();
739                    }
740                    while (superpoly.Count == 0)
741                    {
742                        if (maxterm.Count == 0)
743                        {
744                            if (numberOfVariables < chooseIndexI.Count)
745                            {
746                                if (settings.EnableLogMessages)
747                                    CubeAttack_LogMessage("Subset is empty, add variable v" + chooseIndexI[numberOfVariables], NotificationLevel.Info);
748                                maxterm.Add(chooseIndexI[numberOfVariables]);
749                                numberOfVariables++;
750                            }
751                            else
752                                break;
753                        }
754                        if (MaxtermKnown(cubeList, maxterm))
755                        {
756                            // Maxterm is already known, break and restart with new subset
757                            if (settings.EnableLogMessages)
758                            {
759                                outputCube = string.Empty;
760                                foreach (int element in maxterm)
761                                    outputCube += "v" + element + " ";
762                                CubeAttack_LogMessage("Maxterm " + outputCube + " is already known, restart with new subset", NotificationLevel.Info);
763                            }
764                            break;
765                        }
766                        if (IsSuperpolyConstant(new int[settings.PublicVar], maxterm))
767                        {
768                            if (stop)
769                                return;
770                            else
771                            {
772                                if (settings.EnableLogMessages)
773                                    CubeAttack_LogMessage("Superpoly is likely constant, drop variable v" + maxterm[0], NotificationLevel.Info);
774                                maxterm.RemoveAt(0);
775                            }
776                        }
777                        else if (!IsSuperpolyLinear(new int[settings.PublicVar], maxterm))
778                        {
779                            if (stop)
780                                return;
781                            else
782                            {
783                                if (settings.EnableLogMessages)
784                                    CubeAttack_LogMessage("Superpoly is not linear", NotificationLevel.Info);
785                                if (numberOfVariables < chooseIndexI.Count)
786                                {
787                                    if (maxterm.Count < settings.MaxCube)
788                                    {
789                                        if (settings.EnableLogMessages)
790                                            CubeAttack_LogMessage("Add variable v" + chooseIndexI[numberOfVariables], NotificationLevel.Info);
791                                        maxterm.Add(chooseIndexI[numberOfVariables]);
792                                        numberOfVariables++;
793                                    }
794                                    else
795                                        break;
796                                }
797                                else
798                                    break;
799                            }
800                        }
801                        else
802                        {
803                            if (stop)
804                                return;
805                            else
806                            {
807                                cubeList.Add(maxterm);
808                                if (settings.EnableLogMessages)
809                                {
810                                    outputCube = string.Empty;
811                                    foreach (int element in maxterm)
812                                        outputCube += "v" + element + " ";
813                                    CubeAttack_LogMessage(outputCube + " is new maxterm", NotificationLevel.Info);
814                                    outputCube = string.Empty;
815                                }
816                                superpoly = ComputeSuperpoly(new int[settings.PublicVar], maxterm);
817                                bool flag = false;
818                                outputCube += "Superpoly: ";
819                                if (superpoly[0] == 1)
820                                {
821                                    outputCube += "1";
822                                    flag = true;
823                                }
824                                for (int i = 1; i < superpoly.Count; i++)
825                                    if (superpoly[i] == 1)
826                                    {
827                                        if (flag)
828                                            outputCube += "+x" + Convert.ToString(i - 1);
829                                        else
830                                            outputCube += "x" + Convert.ToString(i - 1);
831                                        flag = true;
832                                    }
833                                outputCube += "   Cube Indexes: {";
834                                if (maxterm.Count > 0)
835                                {
836                                    maxterm.Sort();
837                                    for (int i = 0; i < maxterm.Count - 1; i++)
838                                        outputCube += maxterm[i] + ",";
839                                    outputCube += maxterm[maxterm.Count - 1] + "}   Output Bit: " + indexOutputBit;
840                                }
841                                else
842                                    outputCube += " }   Output Bit: " + indexOutputBit;
843                                if (settings.EnableLogMessages)
844                                    CubeAttack_LogMessage(outputCube, NotificationLevel.Info);
845                                break;
846                            }
847                        }
848                    }//End while (superpoly.Count == 0)
849
850                    if (!InMatrix(superpoly, superpolyMatrix))
851                    {
852                        List<int> superpolyWithoutConstant = new List<int>();
853                        for (int i = 1; i < superpoly.Count; i++)
854                            superpolyWithoutConstant.Add(superpoly[i]);
855
856                        matrixCheckLinearitySuperpolys = matrixCheckLinearitySuperpolys.AddRow(superpolyWithoutConstant);
857                        if (IsLinearIndependent(matrixCheckLinearitySuperpolys))
858                        {
859                            for (int j = 0; j < superpoly.Count; j++)
860                                superpolyMatrix[countSuperpoly, j] = superpoly[j];
861                            listCubeIndexes.Add(maxterm);
862                            OutputSuperpolys(maxterm, superpoly);
863                            outputBitIndex[countSuperpoly] = indexOutputBit;
864                            countSuperpoly++;
865                            CubeAttack_LogMessage("Found " + countSuperpoly + " of " + settings.SecretVar + " linearly independent superpolys", NotificationLevel.Info);
866                            ProgressChanged((double)countSuperpoly / (double)settings.SecretVar, 1.0);
867                        }
868                        else
869                            matrixCheckLinearitySuperpolys = matrixCheckLinearitySuperpolys.DeleteLastRow();
870                    }
871                    if (countSuperpoly == settings.SecretVar)
872                        CubeAttack_LogMessage(settings.SecretVar + " linearly independent superpolys have been found, preprocessing phase completed", NotificationLevel.Info);
873                }
874            }//End while (countSuperpoly < settings.SecretVar)
875        }//End PreprocessingPhase
876
877        /// <summary>
878        /// Online phase of the cube attack.
879        /// </summary>
880        public void OnlinePhase()
881        {   
882            if (settings.ReadSuperpolysFromFile)
883            {
884                if (File.Exists(settings.OpenFilename))
885                {
886                    CubeAttack_LogMessage("Read superpolys from file !", NotificationLevel.Info);
887                    superpolyMatrix = new Matrix(settings.SecretVar, settings.SecretVar + 1);
888                    listCubeIndexes = new List<List<int>>();
889                    outputBitIndex = new int[settings.SecretVar];
890
891                    int i = 0;
892                    foreach (string sLine in File.ReadAllLines(settings.OpenFilename))
893                    {
894                        string[] allValues = sLine.Split(' ');
895                        string[] variables = allValues[0].Split('+');
896                        string[] cubeIndex = allValues[1].Split(',');
897
898                        List<string> variablesList = new List<string>(variables); // Copy to List
899
900                        for (int j = 0; j < variablesList.Count; j++)
901                        {
902                            if (variablesList[j].Substring(0, 1) == "1")
903                            {
904                                superpolyMatrix[i, 0] = 1;
905                                variablesList.Remove(variablesList[j]);
906                            }
907                        }
908                        for (int j = 0; j < variablesList.Count; j++)
909                            if (variablesList[j].Substring(0, 1) == "x")
910                                variablesList[j] = variablesList[j].Substring(1);
911
912                        List<int> superpoly = new List<int>();
913                        for (int j = 0; j < variablesList.Count; j++)
914                            superpoly.Add(Convert.ToInt32(variablesList[j]));
915                        for (int j = 0; j < superpoly.Count; j++)
916                            superpolyMatrix[i, superpoly[j] + 1] = 1;
917
918                        List<int> maxterm = new List<int>();
919                        foreach (string cube in cubeIndex)
920                            maxterm.Add(Convert.ToInt32(cube));
921                        listCubeIndexes.Add(maxterm);
922
923                        outputBitIndex[i] = Convert.ToInt32(allValues[2]);
924                        i++;
925                        // Save number of input superpolys
926                        countSuperpoly = i;
927                    }
928                }
929                else
930                {
931                    CubeAttack_LogMessage("Please input a File", NotificationLevel.Error);
932                    return;
933                }
934            }
935            if (superpolyMatrix == null || listCubeIndexes == null)
936                CubeAttack_LogMessage("Preprocessing phase has to be executed first", NotificationLevel.Error);
937            else
938            {
939                CubeAttack_LogMessage("Start online phase", NotificationLevel.Info);
940                outputSuperpoly = string.Empty;
941                int[] pubVarElement = new int[settings.PublicVar];
942
943                if (pubVarGlob != null)
944                {
945                    for (int i = 0; i < settings.PublicVar; i++)
946                        pubVarElement[i] = pubVarGlob[i];
947                }
948                Vector b = new Vector(settings.SecretVar);
949                StringBuilder output = new StringBuilder(string.Empty);
950                bool flag = false;
951                string logOutput = string.Empty;
952
953                for (int i = 0; i < listCubeIndexes.Count; i++)
954                {
955                    flag = false;
956                    logOutput = string.Empty;
957                    output.Append("Superpoly: ");
958                    if (superpolyMatrix[i, 0] == 1)
959                    {
960                        output.Append("1");
961                        logOutput += "1";
962                        flag = true;
963                    }
964                    for (int j = 1; j < superpolyMatrix.Cols; j++)
965                    {
966                        if (superpolyMatrix[i, j] == 1)
967                        {
968                            if (flag)
969                            {
970                                output.Append("+x" + Convert.ToString(j - 1));
971                                logOutput += "+x" + Convert.ToString(j - 1);
972                            }
973                            else
974                            {
975                                output.Append("x" + Convert.ToString(j - 1));
976                                logOutput += "x" + Convert.ToString(j - 1);
977                            }
978                            flag = true;
979                        }
980                    }
981                    CubeAttack_LogMessage("Compute value of maxterm equation " + logOutput, NotificationLevel.Info);
982
983                    for (ulong k = 0; k < Math.Pow(2, listCubeIndexes[i].Count); k++)
984                    {
985                        if (stop)
986                            return;
987                        for (int l = 0; l < listCubeIndexes[i].Count; l++)
988                            pubVarElement[listCubeIndexes[i][l]] = (k & ((ulong)1 << l)) > 0 ? 1 : 0;
989                        try
990                        {
991                            b[i] ^= CubeattackBlackbox.GenerateBlackboxOutputBit(pubVarElement, null, outputBitIndex[i]);
992                        }
993                        catch (Exception ex)
994                        {
995                            CubeAttack_LogMessage("Error: " + ex, NotificationLevel.Error);
996                        }
997                    }
998                    for (int j = 0; j < settings.PublicVar; j++)
999                        pubVarElement[j] = 0;
1000
1001                    output.Append(" = " + b[i] + "   Cube Indexes: {");
1002                    listCubeIndexes[i].Sort();
1003                    for (int j = 0; j < listCubeIndexes[i].Count - 1; j++)
1004                        output.Append(listCubeIndexes[i][j] + ",");
1005                    output.Append(listCubeIndexes[i][listCubeIndexes[i].Count - 1] + "}   Output Bit: " + outputBitIndex[i] + "\n");
1006                    outputSuperpoly += output.ToString();
1007                    OnPropertyChanged("OutputSuperpoly");
1008                    ProgressChanged((double)i / (double)listCubeIndexes.Count, 1.0);
1009                    outputSuperpoly = string.Empty;
1010                }
1011                if (listCubeIndexes.Count == settings.SecretVar)
1012                {
1013                    CubeAttack_LogMessage("Solve system of equations", NotificationLevel.Info);
1014                    for (int i = 0; i < settings.SecretVar; i++)
1015                        b[i] ^= superpolyMatrix[i, 0];
1016                    // Delete first column and invert
1017                    OutputKey(superpolyMatrix.DeleteFirstColumn().Inverse() * b);
1018                    OnPropertyChanged("OutputKeyBits");
1019                    CubeAttack_LogMessage("Key bits successfully discovered, online phase completed", NotificationLevel.Info);
1020                }
1021                else
1022                    CubeAttack_LogMessage("Not enough linearly independent superpolys have been found in the preprocessing to discover all secret bits !", NotificationLevel.Info);
1023            }
1024        }
1025
1026        /// <summary>
1027        /// User-Mode to set public bit values manually.
1028        /// </summary>
1029        public void SetPublicBitsPhase()
1030        {
1031            outputSuperpoly = string.Empty;
1032            outputKeyBits = string.Empty;
1033            superpolyMatrix = new Matrix(settings.SecretVar, settings.SecretVar + 1);
1034            listCubeIndexes = new List<List<int>>();
1035            pubVarGlob = new int[settings.PublicVar];
1036            List<int> maxterm = new List<int>();
1037            bool fault = false;
1038
1039            if (settings.OutputBit != indexOutputBit)
1040                indexOutputBit = settings.OutputBit;
1041            if (settings.SetPublicBits.Length != settings.PublicVar)
1042                CubeAttack_LogMessage("Input public bits must have size " + settings.PublicVar + " (Currently: " + settings.SetPublicBits.Length + " )", NotificationLevel.Error);
1043            else
1044            {
1045                for (int i = 0; i < settings.SetPublicBits.Length; i++)
1046                {
1047                    switch (settings.SetPublicBits[i])
1048                    {
1049                        case '0':
1050                            pubVarGlob[i] = 0;
1051                            break;
1052                        case '1':
1053                            pubVarGlob[i] = 1;
1054                            break;
1055                        case '*':
1056                            maxterm.Add(i);
1057                            break;
1058                        default:
1059                            fault = true;
1060                            break;
1061                    }
1062                }
1063                if (fault)
1064                    CubeAttack_LogMessage("The input public bits does not consists only of characters : \'0\',\'1\',\'*\' !", NotificationLevel.Error);
1065                else
1066                {
1067                    if (maxterm.Count > 0)
1068                    {
1069                        if (!IsSuperpolyConstant(pubVarGlob, maxterm))
1070                            if (IsSuperpolyLinear(pubVarGlob, maxterm))
1071                            {
1072                                List<int> superpoly = ComputeSuperpoly(pubVarGlob, maxterm);
1073                                if (!stop)
1074                                {
1075                                    for (int i = 0; i < superpoly.Count; i++)
1076                                        superpolyMatrix[0, i] = superpoly[i];
1077                                    listCubeIndexes.Add(maxterm);
1078                                    OutputSuperpolys(maxterm, superpoly);
1079                                }
1080                            }
1081                            else
1082                            {
1083                                if(!stop)
1084                                    CubeAttack_LogMessage("The corresponding superpoly is not a linear polynomial !", NotificationLevel.Info);
1085                            }
1086                        else
1087                            CubeAttack_LogMessage("The corresponding superpoly is constant !", NotificationLevel.Info);
1088                    }
1089                    else
1090                    {
1091                        StringBuilder output = new StringBuilder(string.Empty);
1092                        output.Append("Output bit: " + Blackbox(pubVarGlob, new int[settings.SecretVar]));
1093                        outputSuperpoly += output.ToString();
1094                        OnPropertyChanged("OutputSuperpoly");
1095                        CubeAttack_LogMessage("Output bit: " + Blackbox(pubVarGlob, new int[settings.SecretVar]), NotificationLevel.Info);
1096                    }
1097                }
1098            }
1099        }
1100
1101        public void Pause()
1102        {
1103        }
1104
1105        #endregion
1106
1107
1108        #region Private methods
1109
1110        /// <summary>
1111        /// Does the actual CubeAttack processing
1112        /// </summary>
1113        private void ProcessCubeAttack(CubeAttackMode mode)
1114        {
1115            switch (mode)
1116            {
1117                case CubeAttackMode.preprocessing:
1118                    PreprocessingPhase();
1119                    break;
1120                case CubeAttackMode.online:
1121                    OnlinePhase();
1122                    break;
1123                case CubeAttackMode.setPublicBits:
1124                    SetPublicBitsPhase();
1125                    break;
1126            }
1127        }
1128
1129        /// <summary>
1130        /// Handles log messages
1131        /// </summary>
1132        private void CubeAttack_LogMessage(string msg, NotificationLevel logLevel)
1133        {
1134            if (OnGuiLogNotificationOccured != null)
1135            {
1136                OnGuiLogNotificationOccured(this, new GuiLogEventArgs(msg, this, logLevel));
1137            }
1138        }
1139
1140
1141        #region IControlEncryption Members
1142
1143        private IControlCubeAttack cubeattackBlackbox;
1144        [PropertyInfo(Direction.ControlMaster, "Master for CubeAttack", "Master for CubeAttack", "", DisplayLevel.Beginner)]
1145        public IControlCubeAttack CubeattackBlackbox
1146        {
1147            get { return cubeattackBlackbox; }
1148            set
1149            {
1150                if (value != null)
1151                    cubeattackBlackbox = value;
1152            }
1153        }
1154
1155        #endregion
1156
1157        #endregion
1158
1159
1160        #region INotifyPropertyChanged Members
1161
1162        public event PropertyChangedEventHandler PropertyChanged;
1163        public void OnPropertyChanged(string name)
1164        {
1165            if (PropertyChanged != null)
1166            {
1167                PropertyChanged(this, new PropertyChangedEventArgs(name));
1168            }
1169        }
1170
1171        #endregion
1172    }
1173}
Note: See TracBrowser for help on using the repository browser.