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

Last change on this file since 844 was 844, checked in by oruba, 12 years ago
  • modified output of superpolys
File size: 48.1 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            if (countSuperpoly > 0)
703                OnPropertyChanged("OutputSuperpoly");
704
705            // Save all public variables indexes in a list
706            for (int i = 0; i < settings.PublicVar; i++)
707                chooseIndexI.Add(i);
708
709            // Find n maxterms and save their in the matrix
710            while (countSuperpoly < settings.SecretVar)
711            {
712                if (stop)
713                    return;
714                else
715                {
716                    maxterm = new List<int>();
717                    superpoly.Clear();
718
719                    // Generate random size k between 1 and the number of public variables
720                    numberOfVariables = rnd.Next(1, settings.MaxCube + 1);
721
722                    // Permutation of the public variables
723                    Shuffle(chooseIndexI);
724
725                    // Construct cube of size k. Add k public variables to the cube
726                    for (int i = 0; i < numberOfVariables; i++)
727                        maxterm.Add(chooseIndexI[i]);
728
729                    if (settings.EnableLogMessages)
730                    {
731                        foreach (int element in maxterm)
732                            outputCube += "v" + element + " ";
733                        CubeAttack_LogMessage("Start search for maxterm with subterm: " + outputCube, NotificationLevel.Info);
734                    }
735                    if (settings.OutputBit != indexOutputBit)
736                    {
737                        // User has changed Output Bit index, store new value
738                        indexOutputBit = settings.OutputBit;
739
740                        // Reset list of cube indexes, since a single maxterms can be associated with multiple superpolys from different outputs
741                        cubeList = new List<List<int>>();
742                    }
743                    while (superpoly.Count == 0)
744                    {
745                        if (maxterm.Count == 0)
746                        {
747                            if (numberOfVariables < chooseIndexI.Count)
748                            {
749                                if (settings.EnableLogMessages)
750                                    CubeAttack_LogMessage("Subset is empty, add variable v" + chooseIndexI[numberOfVariables], NotificationLevel.Info);
751                                maxterm.Add(chooseIndexI[numberOfVariables]);
752                                numberOfVariables++;
753                            }
754                            else
755                                break;
756                        }
757                        if (MaxtermKnown(cubeList, maxterm))
758                        {
759                            // Maxterm is already known, break and restart with new subset
760                            if (settings.EnableLogMessages)
761                            {
762                                outputCube = string.Empty;
763                                foreach (int element in maxterm)
764                                    outputCube += "v" + element + " ";
765                                CubeAttack_LogMessage("Maxterm " + outputCube + " is already known, restart with new subset", NotificationLevel.Info);
766                            }
767                            break;
768                        }
769                        if (IsSuperpolyConstant(new int[settings.PublicVar], maxterm))
770                        {
771                            if (stop)
772                                return;
773                            else
774                            {
775                                if (settings.EnableLogMessages)
776                                    CubeAttack_LogMessage("Superpoly is likely constant, drop variable v" + maxterm[0], NotificationLevel.Info);
777                                maxterm.RemoveAt(0);
778                            }
779                        }
780                        else if (!IsSuperpolyLinear(new int[settings.PublicVar], maxterm))
781                        {
782                            if (stop)
783                                return;
784                            else
785                            {
786                                if (settings.EnableLogMessages)
787                                    CubeAttack_LogMessage("Superpoly is not linear", NotificationLevel.Info);
788                                if (numberOfVariables < chooseIndexI.Count)
789                                {
790                                    if (maxterm.Count < settings.MaxCube)
791                                    {
792                                        if (settings.EnableLogMessages)
793                                            CubeAttack_LogMessage("Add variable v" + chooseIndexI[numberOfVariables], NotificationLevel.Info);
794                                        maxterm.Add(chooseIndexI[numberOfVariables]);
795                                        numberOfVariables++;
796                                    }
797                                    else
798                                        break;
799                                }
800                                else
801                                    break;
802                            }
803                        }
804                        else
805                        {
806                            if (stop)
807                                return;
808                            else
809                            {
810                                cubeList.Add(maxterm);
811                                if (settings.EnableLogMessages)
812                                {
813                                    outputCube = string.Empty;
814                                    foreach (int element in maxterm)
815                                        outputCube += "v" + element + " ";
816                                    CubeAttack_LogMessage(outputCube + " is new maxterm", NotificationLevel.Info);
817                                    outputCube = string.Empty;
818                                }
819                                superpoly = ComputeSuperpoly(new int[settings.PublicVar], maxterm);
820                                bool flag = false;
821                                outputCube += "Superpoly: ";
822                                if (superpoly[0] == 1)
823                                {
824                                    outputCube += "1";
825                                    flag = true;
826                                }
827                                for (int i = 1; i < superpoly.Count; i++)
828                                    if (superpoly[i] == 1)
829                                    {
830                                        if (flag)
831                                            outputCube += "+x" + Convert.ToString(i - 1);
832                                        else
833                                            outputCube += "x" + Convert.ToString(i - 1);
834                                        flag = true;
835                                    }
836                                outputCube += "   Cube Indexes: {";
837                                if (maxterm.Count > 0)
838                                {
839                                    maxterm.Sort();
840                                    for (int i = 0; i < maxterm.Count - 1; i++)
841                                        outputCube += maxterm[i] + ",";
842                                    outputCube += maxterm[maxterm.Count - 1] + "}   Output Bit: " + indexOutputBit;
843                                }
844                                else
845                                    outputCube += " }   Output Bit: " + indexOutputBit;
846                                if (settings.EnableLogMessages)
847                                    CubeAttack_LogMessage(outputCube, NotificationLevel.Info);
848                                break;
849                            }
850                        }
851                    }//End while (superpoly.Count == 0)
852
853                    if (!InMatrix(superpoly, superpolyMatrix))
854                    {
855                        List<int> superpolyWithoutConstant = new List<int>();
856                        for (int i = 1; i < superpoly.Count; i++)
857                            superpolyWithoutConstant.Add(superpoly[i]);
858
859                        matrixCheckLinearitySuperpolys = matrixCheckLinearitySuperpolys.AddRow(superpolyWithoutConstant);
860                        if (IsLinearIndependent(matrixCheckLinearitySuperpolys))
861                        {
862                            for (int j = 0; j < superpoly.Count; j++)
863                                superpolyMatrix[countSuperpoly, j] = superpoly[j];
864                            listCubeIndexes.Add(maxterm);
865                            OutputSuperpolys(maxterm, superpoly);
866                            outputBitIndex[countSuperpoly] = indexOutputBit;
867                            countSuperpoly++;
868                            CubeAttack_LogMessage("Found " + countSuperpoly + " of " + settings.SecretVar + " linearly independent superpolys", NotificationLevel.Info);
869                            ProgressChanged((double)countSuperpoly / (double)settings.SecretVar, 1.0);
870                        }
871                        else
872                            matrixCheckLinearitySuperpolys = matrixCheckLinearitySuperpolys.DeleteLastRow();
873                    }
874                    if (countSuperpoly == settings.SecretVar)
875                        CubeAttack_LogMessage(settings.SecretVar + " linearly independent superpolys have been found, preprocessing phase completed", NotificationLevel.Info);
876                }
877            }//End while (countSuperpoly < settings.SecretVar)
878        }//End PreprocessingPhase
879
880        /// <summary>
881        /// Online phase of the cube attack.
882        /// </summary>
883        public void OnlinePhase()
884        {   
885            if (settings.ReadSuperpolysFromFile)
886            {
887                if (File.Exists(settings.OpenFilename))
888                {
889                    CubeAttack_LogMessage("Read superpolys from file !", NotificationLevel.Info);
890                    superpolyMatrix = new Matrix(settings.SecretVar, settings.SecretVar + 1);
891                    listCubeIndexes = new List<List<int>>();
892                    outputBitIndex = new int[settings.SecretVar];
893
894                    int i = 0;
895                    foreach (string sLine in File.ReadAllLines(settings.OpenFilename))
896                    {
897                        string[] allValues = sLine.Split(' ');
898                        string[] variables = allValues[0].Split('+');
899                        string[] cubeIndex = allValues[1].Split(',');
900
901                        List<string> variablesList = new List<string>(variables); // Copy to List
902
903                        for (int j = 0; j < variablesList.Count; j++)
904                        {
905                            if (variablesList[j].Substring(0, 1) == "1")
906                            {
907                                superpolyMatrix[i, 0] = 1;
908                                variablesList.Remove(variablesList[j]);
909                            }
910                        }
911                        for (int j = 0; j < variablesList.Count; j++)
912                            if (variablesList[j].Substring(0, 1) == "x")
913                                variablesList[j] = variablesList[j].Substring(1);
914
915                        List<int> superpoly = new List<int>();
916                        for (int j = 0; j < variablesList.Count; j++)
917                            superpoly.Add(Convert.ToInt32(variablesList[j]));
918                        for (int j = 0; j < superpoly.Count; j++)
919                            superpolyMatrix[i, superpoly[j] + 1] = 1;
920
921                        List<int> maxterm = new List<int>();
922                        foreach (string cube in cubeIndex)
923                            maxterm.Add(Convert.ToInt32(cube));
924                        listCubeIndexes.Add(maxterm);
925
926                        outputBitIndex[i] = Convert.ToInt32(allValues[2]);
927                        i++;
928                        // Save number of input superpolys
929                        countSuperpoly = i;
930                    }
931                }
932                else
933                {
934                    CubeAttack_LogMessage("Please input a File", NotificationLevel.Error);
935                    return;
936                }
937            }
938            if (superpolyMatrix == null || listCubeIndexes == null)
939                CubeAttack_LogMessage("Preprocessing phase has to be executed first", NotificationLevel.Error);
940            else
941            {
942                CubeAttack_LogMessage("Start online phase", NotificationLevel.Info);
943                outputSuperpoly = string.Empty;
944                int[] pubVarElement = new int[settings.PublicVar];
945
946                if (pubVarGlob != null)
947                {
948                    for (int i = 0; i < settings.PublicVar; i++)
949                        pubVarElement[i] = pubVarGlob[i];
950                }
951                Vector b = new Vector(settings.SecretVar);
952                StringBuilder output = new StringBuilder(string.Empty);
953                bool flag = false;
954                string logOutput = string.Empty;
955
956                for (int i = 0; i < listCubeIndexes.Count; i++)
957                {
958                    flag = false;
959                    logOutput = string.Empty;
960                    output.Append("Superpoly: ");
961                    if (superpolyMatrix[i, 0] == 1)
962                    {
963                        output.Append("1");
964                        logOutput += "1";
965                        flag = true;
966                    }
967                    for (int j = 1; j < superpolyMatrix.Cols; j++)
968                    {
969                        if (superpolyMatrix[i, j] == 1)
970                        {
971                            if (flag)
972                            {
973                                output.Append("+x" + Convert.ToString(j - 1));
974                                logOutput += "+x" + Convert.ToString(j - 1);
975                            }
976                            else
977                            {
978                                output.Append("x" + Convert.ToString(j - 1));
979                                logOutput += "x" + Convert.ToString(j - 1);
980                            }
981                            flag = true;
982                        }
983                    }
984                    CubeAttack_LogMessage("Compute value of maxterm equation " + logOutput, NotificationLevel.Info);
985
986                    for (ulong k = 0; k < Math.Pow(2, listCubeIndexes[i].Count); k++)
987                    {
988                        if (stop)
989                            return;
990                        for (int l = 0; l < listCubeIndexes[i].Count; l++)
991                            pubVarElement[listCubeIndexes[i][l]] = (k & ((ulong)1 << l)) > 0 ? 1 : 0;
992                        try
993                        {
994                            b[i] ^= CubeattackBlackbox.GenerateBlackboxOutputBit(pubVarElement, null, outputBitIndex[i]);
995                        }
996                        catch (Exception ex)
997                        {
998                            CubeAttack_LogMessage("Error: " + ex, NotificationLevel.Error);
999                        }
1000                    }
1001                    for (int j = 0; j < settings.PublicVar; j++)
1002                        pubVarElement[j] = 0;
1003
1004                    output.Append(" = " + b[i] + "   Cube Indexes: {");
1005                    listCubeIndexes[i].Sort();
1006                    for (int j = 0; j < listCubeIndexes[i].Count - 1; j++)
1007                        output.Append(listCubeIndexes[i][j] + ",");
1008                    output.Append(listCubeIndexes[i][listCubeIndexes[i].Count - 1] + "}   Output Bit: " + outputBitIndex[i] + "\n");
1009                    outputSuperpoly += output.ToString();
1010                    OnPropertyChanged("OutputSuperpoly");
1011                    ProgressChanged((double)i / (double)listCubeIndexes.Count, 1.0);
1012                    outputSuperpoly = string.Empty;
1013                }
1014                if (listCubeIndexes.Count == settings.SecretVar)
1015                {
1016                    CubeAttack_LogMessage("Solve system of equations", NotificationLevel.Info);
1017                    for (int i = 0; i < settings.SecretVar; i++)
1018                        b[i] ^= superpolyMatrix[i, 0];
1019                    // Delete first column and invert
1020                    OutputKey(superpolyMatrix.DeleteFirstColumn().Inverse() * b);
1021                    OnPropertyChanged("OutputKeyBits");
1022                    CubeAttack_LogMessage("Key bits successfully discovered, online phase completed", NotificationLevel.Info);
1023                }
1024                else
1025                    CubeAttack_LogMessage("Not enough linearly independent superpolys have been found in the preprocessing to discover all secret bits !", NotificationLevel.Info);
1026            }
1027        }
1028
1029        /// <summary>
1030        /// User-Mode to set public bit values manually.
1031        /// </summary>
1032        public void SetPublicBitsPhase()
1033        {
1034            outputSuperpoly = string.Empty;
1035            outputKeyBits = string.Empty;
1036            superpolyMatrix = new Matrix(settings.SecretVar, settings.SecretVar + 1);
1037            listCubeIndexes = new List<List<int>>();
1038            pubVarGlob = new int[settings.PublicVar];
1039            List<int> maxterm = new List<int>();
1040            bool fault = false;
1041
1042            if (settings.OutputBit != indexOutputBit)
1043                indexOutputBit = settings.OutputBit;
1044            if (settings.SetPublicBits.Length != settings.PublicVar)
1045                CubeAttack_LogMessage("Input public bits must have size " + settings.PublicVar + " (Currently: " + settings.SetPublicBits.Length + " )", NotificationLevel.Error);
1046            else
1047            {
1048                for (int i = 0; i < settings.SetPublicBits.Length; i++)
1049                {
1050                    switch (settings.SetPublicBits[i])
1051                    {
1052                        case '0':
1053                            pubVarGlob[i] = 0;
1054                            break;
1055                        case '1':
1056                            pubVarGlob[i] = 1;
1057                            break;
1058                        case '*':
1059                            maxterm.Add(i);
1060                            break;
1061                        default:
1062                            fault = true;
1063                            break;
1064                    }
1065                }
1066                if (fault)
1067                    CubeAttack_LogMessage("The input public bits does not consists only of characters : \'0\',\'1\',\'*\' !", NotificationLevel.Error);
1068                else
1069                {
1070                    if (maxterm.Count > 0)
1071                    {
1072                        if (!IsSuperpolyConstant(pubVarGlob, maxterm))
1073                            if (IsSuperpolyLinear(pubVarGlob, maxterm))
1074                            {
1075                                List<int> superpoly = ComputeSuperpoly(pubVarGlob, maxterm);
1076                                if (!stop)
1077                                {
1078                                    for (int i = 0; i < superpoly.Count; i++)
1079                                        superpolyMatrix[0, i] = superpoly[i];
1080                                    listCubeIndexes.Add(maxterm);
1081                                    OutputSuperpolys(maxterm, superpoly);
1082                                }
1083                            }
1084                            else
1085                            {
1086                                if(!stop)
1087                                    CubeAttack_LogMessage("The corresponding superpoly is not a linear polynomial !", NotificationLevel.Info);
1088                            }
1089                        else
1090                            CubeAttack_LogMessage("The corresponding superpoly is constant !", NotificationLevel.Info);
1091                    }
1092                    else
1093                    {
1094                        StringBuilder output = new StringBuilder(string.Empty);
1095                        output.Append("Output bit: " + Blackbox(pubVarGlob, new int[settings.SecretVar]));
1096                        outputSuperpoly += output.ToString();
1097                        OnPropertyChanged("OutputSuperpoly");
1098                        CubeAttack_LogMessage("Output bit: " + Blackbox(pubVarGlob, new int[settings.SecretVar]), NotificationLevel.Info);
1099                    }
1100                }
1101            }
1102        }
1103
1104        public void Pause()
1105        {
1106        }
1107
1108        #endregion
1109
1110
1111        #region Private methods
1112
1113        /// <summary>
1114        /// Does the actual CubeAttack processing
1115        /// </summary>
1116        private void ProcessCubeAttack(CubeAttackMode mode)
1117        {
1118            switch (mode)
1119            {
1120                case CubeAttackMode.preprocessing:
1121                    PreprocessingPhase();
1122                    break;
1123                case CubeAttackMode.online:
1124                    OnlinePhase();
1125                    break;
1126                case CubeAttackMode.setPublicBits:
1127                    SetPublicBitsPhase();
1128                    break;
1129            }
1130        }
1131
1132        /// <summary>
1133        /// Handles log messages
1134        /// </summary>
1135        private void CubeAttack_LogMessage(string msg, NotificationLevel logLevel)
1136        {
1137            if (OnGuiLogNotificationOccured != null)
1138            {
1139                OnGuiLogNotificationOccured(this, new GuiLogEventArgs(msg, this, logLevel));
1140            }
1141        }
1142
1143
1144        #region IControlEncryption Members
1145
1146        private IControlCubeAttack cubeattackBlackbox;
1147        [PropertyInfo(Direction.ControlMaster, "Master for CubeAttack", "Master for CubeAttack", "", DisplayLevel.Beginner)]
1148        public IControlCubeAttack CubeattackBlackbox
1149        {
1150            get { return cubeattackBlackbox; }
1151            set
1152            {
1153                if (value != null)
1154                    cubeattackBlackbox = value;
1155            }
1156        }
1157
1158        #endregion
1159
1160        #endregion
1161
1162
1163        #region INotifyPropertyChanged Members
1164
1165        public event PropertyChangedEventHandler PropertyChanged;
1166        public void OnPropertyChanged(string name)
1167        {
1168            if (PropertyChanged != null)
1169            {
1170                PropertyChanged(this, new PropertyChangedEventArgs(name));
1171            }
1172        }
1173
1174        #endregion
1175    }
1176}
Note: See TracBrowser for help on using the repository browser.