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

Last change on this file since 832 was 832, checked in by Sören Rinne, 12 years ago
  • slight changes in BerlekampMassey
  • changed CubeAttack, BooleanFunctionParser, Trivium to implement only one Controller interface (IControlGenerateBlackboxOutputBit)
  • modified samples
File size: 52.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        "dav083@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 the 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        /// <summary>
137        /// Complete CubeAttack
138        /// </summary>
139        public void Preprocessing()
140        {
141            ProcessCubeAttack(CubeAttackMode.preprocessing);
142        }
143
144        public void Online()
145        {
146            ProcessCubeAttack(CubeAttackMode.online);
147        }
148
149        /// <summary>
150        /// Manual input of public bits
151        /// </summary>
152        public void SetPublicBits()
153        {
154            ProcessCubeAttack(CubeAttackMode.setPublicBits);
155        }
156
157        #endregion
158
159
160        #region IPlugin members
161
162        public void Initialize()
163        {
164        }
165
166        public void Dispose()
167        {
168            stop = false;
169            foreach (CryptoolStream stream in listCryptoolStreamsOut)
170            {
171                stream.Close();
172            }
173            listCryptoolStreamsOut.Clear();
174        }
175
176        public bool HasChanges
177        {
178            get { return settings.HasChanges; }
179            set { settings.HasChanges = value; }
180        }
181
182        /// <summary>
183        /// Fire, if progress bar has to be updated
184        /// </summary>
185        public event PluginProgressChangedEventHandler OnPluginProgressChanged;
186        private void ProgressChanged(double value, double max)
187        {
188            EventsHelper.ProgressChanged(OnPluginProgressChanged, this, new PluginProgressEventArgs(value, max));
189        }
190
191        /// <summary>
192        /// Fire, if new message has to be shown in the status bar
193        /// </summary>
194        public event GuiLogNotificationEventHandler OnGuiLogNotificationOccured;
195
196        public UserControl Presentation
197        {
198            get { return null; }
199        }
200
201        public UserControl QuickWatchPresentation
202        {
203            get { return null; }
204        }
205
206        public void Stop()
207        {
208            this.stop = true;
209
210            /*if (settings.Action == 0) // Action = Preprocessing
211            {
212                settings.SaveOutputSuperpoly = outputSuperpoly;
213                settings.SaveSuperpolyMatrix = superpolyMatrix;
214                settings.SaveListCubeIndexes = listCubeIndexes;
215                settings.SaveOutputBitIndex = outputBitIndex;
216                settings.SaveCountSuperpoly = countSuperpoly;
217                settings.SaveMatrixCheckLinearitySuperpolys = matrixCheckLinearitySuperpolys;
218            }*/
219        }
220
221        public void PostExecution()
222        {
223            Dispose();
224
225            //if(countSuperpoly == settings.SecretVar)
226            /*settings.SaveOutputSuperpoly = null;
227            settings.SaveSuperpolyMatrix = null;
228            settings.SaveListCubeIndexes = null;
229            settings.SaveOutputBitIndex = null;
230            settings.SaveCountSuperpoly = 0;
231            settings.SaveMatrixCheckLinearitySuperpolys = null;
232            CubeAttack_LogMessage("blubbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb", NotificationLevel.Info); */
233        }
234
235        public void PreExecution()
236        {
237            Dispose();
238
239            /*if (settings.Action == 0) // Action = Preprocessing
240            {
241                if (settings.SaveCountSuperpoly != settings.SecretVar)
242                {
243                    if (settings.SaveOutputSuperpoly != null)
244                        outputSuperpoly = settings.SaveOutputSuperpoly;
245                    if (settings.SaveSuperpolyMatrix != null)
246                        superpolyMatrix = settings.SaveSuperpolyMatrix;
247                    if (settings.SaveListCubeIndexes != null)
248                        listCubeIndexes = settings.SaveListCubeIndexes;
249                    if (settings.SaveOutputBitIndex != null)
250                        outputBitIndex = settings.SaveOutputBitIndex;
251                    if (settings.SaveCountSuperpoly != 0)
252                        countSuperpoly = settings.SaveCountSuperpoly;
253                    if (settings.SaveMatrixCheckLinearitySuperpolys != null)
254                        matrixCheckLinearitySuperpolys = settings.SaveMatrixCheckLinearitySuperpolys;
255                }
256            }*/
257        }
258
259        #pragma warning disable 67
260                public event StatusChangedEventHandler OnPluginStatusChanged;
261        #pragma warning restore
262
263        private void GuiLogMessage(string message, NotificationLevel logLevel)
264        {
265            EventsHelper.GuiLogMessage(OnGuiLogNotificationOccured, this, new GuiLogEventArgs(message, this, logLevel));
266        }
267
268        public void Execute()
269        {
270            if (settings.MaxCube > settings.PublicVar)
271                CubeAttack_LogMessage("Error: Max Cube Size cannot be greater than Public Bit Size.", NotificationLevel.Error);
272            else
273            {
274                try
275                {
276                    switch (settings.Action)
277                    {
278                        case 0:
279                            Preprocessing();
280                            break;
281                        case 1:
282                            Online();
283                            break;
284                        case 2:
285                            SetPublicBits();
286                            break;
287                    }
288                }
289                catch (Exception ex)
290                {
291                    CubeAttack_LogMessage("Error: " + ex, NotificationLevel.Error);
292                }
293                finally
294                {
295                    ProgressChanged(1.0, 1.0);
296                }
297            }
298        }
299
300        /// <summary>
301        /// Returns the output bit of the master polynomial p
302        /// </summary>
303        /// <param name="v">Public bits.</param>
304        /// <param name="x">Secret bits.</param>
305        /// <returns>Returns the output bit of the master polynomial, either 0 or 1.</returns>
306        public int Blackbox(int[] v, int[] x)
307        {
308            /*// Begin Trivium
309            // Initialisierung
310                int[] a = new int[93];
311                int[] b = new int[84];
312            int[] c = new int[111];
313            int t1, t2, t3;
314            int i,j;
315                for (i = 0; i < 80; i++)
316            {
317                a[i] = x[i];
318                b[i] = v[i];
319                        c[i] = 0;
320                }
321                while (i < 84){
322                        a[i] = 0;
323                        b[i] = 0;
324                        c[i] = 0;
325                        i++;
326                }
327                while (i < 93){
328                        a[i] = 0;
329                        c[i] = 0;
330                        i++;
331                }
332                while (i < 108){
333                        c[i] = 0;
334                        i++;
335                }
336                while (i < 111){
337                        c[i] = 1;
338                        i++;
339                }
340
341                for (i = 0; i < 672; i++)
342            {
343                        t1 = a[65] ^ a[92];
344                        t2 = b[68] ^ b[83];
345                        t3 = c[65] ^ c[110];
346                        t1 = t1 ^ (a[90] & a[91]) ^ b[77];
347                        t2 = t2 ^ (b[81] & b[82]) ^ c[86];
348                        t3 = t3 ^ (c[108] & c[109]) ^ a[68];
349                        for (j = 92; j > 0; j--)
350                                a[j] = a[j-1];
351                        for (j = 83; j > 0; j--)
352                                b[j] = b[j-1];
353                        for (j = 110; j > 0; j--)
354                                c[j] = c[j-1];
355                        a[0] = t3;
356                        b[0] = t1;
357                        c[0] = t2;
358                }
359
360            // Keystream
361            List<int> keyOutput = new List<int>();
362                for (i = 0; i < 4; i++)
363            {
364                        t1 = a[65] ^ a[92];
365                        t2 = b[68] ^ b[83];
366                        t3 = c[65] ^ c[110];
367                keyOutput.Add(t1 ^ t2 ^ t3);
368                        t1 = t1 ^ (a[90] & a[91]) ^ b[77];
369                        t2 = t2 ^ (b[81] & b[82]) ^ c[86];
370                        t3 = t3 ^ (c[108] & c[109]) ^ a[68];
371                        for (j = 92; j > 0; j--)
372                                a[j] = a[j-1];
373                        for (j = 83; j > 0; j--)
374                                b[j] = b[j-1];
375                        for (j = 110; j > 0; j--)
376                                c[j] = c[j-1];
377                        a[0] = t3;
378                        b[0] = t1;
379                        c[0] = t2;
380                }
381            return keyOutput[3];
382            // End Trivium */
383
384            int result = 0;
385           
386            try
387            {
388                //switch (settings.BlackBox)
389                {
390                    // Parser as black box
391                    //case 0:
392                        bool[] vBool = new bool[v.Length];
393                        bool[] xBool = new bool[x.Length];
394                        for (int i = 0; i < v.Length; i++)
395                            vBool[i] = Convert.ToBoolean(v[i]);
396                        for (int i = 0; i < x.Length; i++)
397                            xBool[i] = Convert.ToBoolean(x[i]);
398                        result = CubeattackBlackbox.GenerateBlackboxOutputBit(v, x, indexOutputBit);   //ParserOutput.SolveFunction(vBool, xBool);
399                        //  break;
400                    // Trivium as black box
401                        //case 1:
402                        //result = TriviumOutput.GenerateTriviumKeystream(v, x, indexOutputBit, false);
403                    //break;
404                }
405            }
406            catch (Exception ex)
407            {
408                stop = true;
409                CubeAttack_LogMessage("Error: " + ex, NotificationLevel.Error);
410            }
411            return result; 
412        }
413
414        /// <summary>
415        /// The function derives the algebraic structure of the superpoly from the maxterm.
416        /// The structure is derived by computing the free term and the coefficients in the superpoly.
417        /// </summary>
418        /// <param name="cube">The summation cube I.</param>
419        /// <returns>Returns the superpoly of I in p.</returns>
420        public List<int> ComputeSuperpoly(int[] pubVarElement, List<int> maxterm)
421        {
422            int constant = 0;
423            int coeff = 0;
424            List<int> superpoly = new List<int>();
425            int[] secVarElement = new int[settings.SecretVar];
426
427            if (settings.EnableLogMessages)
428                CubeAttack_LogMessage("Start deriving the algebraic structure of the superpoly", NotificationLevel.Info);
429
430            // Compute the free term
431            for (ulong i = 0; i < Math.Pow(2, maxterm.Count); i++)
432            {
433                if (stop)
434                    return superpoly;
435
436                for (int j = 0; j < maxterm.Count; j++)
437                    pubVarElement[maxterm[j]] = (i & ((ulong)1 << j)) > 0 ? 1 : 0;
438                constant ^= Blackbox((int[])pubVarElement.Clone(), (int[])secVarElement.Clone());
439            }
440            superpoly.Add(constant);
441
442            if (settings.EnableLogMessages)
443                CubeAttack_LogMessage("Constant term = " + (constant).ToString(), NotificationLevel.Info);
444
445            // Compute coefficients
446            for (int k = 0; k < settings.SecretVar; k++)
447            {
448                for (ulong i = 0; i < Math.Pow(2, maxterm.Count); i++)
449                {
450                    if (stop)
451                        return superpoly;
452
453                    secVarElement[k] = 1;
454                    for (int j = 0; j < maxterm.Count; j++)
455                        pubVarElement[maxterm[j]] = (i & ((ulong)1 << j)) > 0 ? 1 : 0;
456                    coeff ^= Blackbox((int[])pubVarElement.Clone(), (int[])secVarElement.Clone());
457                }
458                superpoly.Add(constant ^ coeff);
459
460                if (settings.EnableLogMessages)
461                    CubeAttack_LogMessage("Coefficient of x" + k + " = " + (constant ^ coeff), NotificationLevel.Info);
462               
463                coeff = 0;
464                secVarElement[k] = 0;
465            }
466            return superpoly;
467        }
468
469        /// <summary>
470        /// The function outputs a the superpolys, cube indexes and output bits.
471        /// </summary>
472        /// <param name="cubeIndexes">The cube indexes of the maxterm.</param>
473        /// <param name="superpoly">The superpoly for the given cube indexes.</param>
474        public void OutputSuperpolys(List<int> cubeIndexes, List<int> superpoly)
475        {
476            StringBuilder output = new StringBuilder(string.Empty);
477            bool superpolyIsEmpty = true;
478            bool flag = false;
479            output.Append("Superpoly: ");
480            if (superpoly[0] == 1)
481            {
482                output.Append("1");
483                superpolyIsEmpty = false;
484                flag = true;
485            }
486            for (int i = 1; i < superpoly.Count; i++)
487                if (superpoly[i] == 1)
488                {
489                    if (flag)
490                        output.Append("+x" + Convert.ToString(i - 1));
491                    else
492                        output.Append("x" + Convert.ToString(i - 1));
493                    superpolyIsEmpty = false;
494                    flag = true;
495                }
496            if (superpolyIsEmpty)
497                output.Append("0");
498            output.Append("   Cube Indexes: {");
499            if (cubeIndexes.Count > 0)
500            {
501                cubeIndexes.Sort();
502                for (int i = 0; i < cubeIndexes.Count - 1; i++)
503                    output.Append(cubeIndexes[i] + ",");
504                output.Append(cubeIndexes[cubeIndexes.Count - 1] + "}");
505            }
506            else
507                output.Append(" }");
508
509            output.Append("   Output Bit: " + indexOutputBit + "\n");
510           
511            outputSuperpoly += output.ToString();
512            OnPropertyChanged("OutputSuperpoly");
513        }
514
515        /// <summary>
516        /// The function outputs the key bits.
517        /// </summary>
518        /// <param name="res">Result vector</param>
519        public void OutputKey(Vector res)
520        {
521            StringBuilder output = new StringBuilder(string.Empty);
522            for (int i=0; i<res.Length; i++)
523                output.AppendLine("x" + i + " = " + res[i]);
524            outputKeyBits = output.ToString();
525        }
526
527        /// <summary>
528        /// Test if superpoly is already in matrix.
529        /// </summary>
530        /// <param name="superpoly">The superpoly of I in p.</param>
531        /// <param name="matrix">An n x n matrix whose rows contain their corresponding superpolys.</param>
532        /// <returns>A boolean value indicating if the superpoly is in the matrix or not.</returns>
533        public bool InMatrix(List<int> superpoly, Matrix matrix)
534        {
535            bool isEqual = true;
536            for (int i = 0; i < matrix.Rows; i++)
537            {
538                isEqual = true;
539                for (int j = 0; j < superpoly.Count; j++)
540                    if (matrix[i, j] != superpoly[j])
541                        isEqual = false;
542                if (isEqual)
543                    return true;
544            }
545            return false;
546        }
547
548        /// <summary>
549        /// Test if a maxterm is already known.
550        /// </summary>
551        /// <param name="cubeList">A list of cube indexes.</param>
552        /// <param name="maxterm">The located maxterm.</param>
553        /// <returns>A boolean value indicating if the maxterm is already in the list of cubes indexes or not.</returns>
554        public bool MaxtermKnown(List<List<int>> cubeList, List<int> maxterm)
555        {
556            bool isEqual = true;
557            for (int i = 0; i < cubeList.Count; i++)
558            {
559                isEqual = true;
560                if (cubeList[i].Count == maxterm.Count)
561                {
562                    for (int j = 0; j < maxterm.Count; j++)
563                        if (!cubeList[i].Contains(maxterm[j]))
564                            isEqual = false;
565                    if (isEqual)
566                        return true;
567                }
568            }
569            return false;
570        }
571
572        /// <summary>
573        /// Test if a superpoly is linear (BLR linearity test).
574        /// </summary>
575        /// <param name="maxterm">The located maxterm.</param>
576        /// <returns>A boolean value indicating if the superpoly is probably linear or not.</returns>
577        public bool IsSuperpolyLinear(int[] pubVarElement, List<int> maxterm)
578        {
579            Random rnd = new Random();
580            int psLeft = 0;
581            int psRight = 0;
582            int[] vectorX = new int[settings.SecretVar];
583            int[] vectorY = new int[settings.SecretVar];
584            int[] vecXY = new int[settings.SecretVar];
585
586            for (int k = 0; k < settings.LinTest; k++)
587            {
588                if (settings.EnableLogMessages)
589                    CubeAttack_LogMessage("Linearity test " + (k + 1) + " of " + settings.LinTest, NotificationLevel.Info);
590               
591                psLeft = 0;
592                psRight = 0;
593
594                // Choose vectors x and y at random
595                for (int i = 0; i < settings.SecretVar; i++)
596                {
597                    vectorX[i] = rnd.Next(0, 2);
598                    vectorY[i] = rnd.Next(0, 2);
599                }
600
601                pubVarElement = new int[settings.PublicVar];
602                for (int i = 0; i < settings.SecretVar; i++)
603                    vecXY[i] = (vectorX[i] ^ vectorY[i]);
604
605                for (ulong i = 0; i < Math.Pow(2, maxterm.Count); i++)
606                {
607                    if (stop)
608                        return false;
609
610                    for (int j = 0; j < maxterm.Count; j++)
611                        pubVarElement[maxterm[j]] = (i & ((ulong)1 << j)) > 0 ? 1 : 0;
612                    psLeft ^= Blackbox((int[])pubVarElement.Clone(), new int[settings.SecretVar]) 
613                            ^ Blackbox((int[])pubVarElement.Clone(), (int[])vectorX.Clone()) 
614                            ^ Blackbox((int[])pubVarElement.Clone(), (int[])vectorY.Clone());
615                    psRight ^= Blackbox((int[])pubVarElement.Clone(), (int[])vecXY.Clone());
616                }
617                if (psLeft != psRight)
618                {
619                    if (settings.EnableLogMessages)
620                        CubeAttack_LogMessage("Linearity test " + (k + 1) + " failed", NotificationLevel.Info);
621                    return false;
622                }
623
624                if (stop)
625                    return false;
626            }
627            return true;
628        }
629
630        /// <summary>
631        /// Test if superpoly is a constant value.
632        /// </summary>
633        /// <param name="maxterm">The located maxterm.</param>
634        /// <returns>A boolean value indicating if the superpoly is constant or not.</returns>
635        public bool IsSuperpolyConstant(int[] pubVarElement, List<int> maxterm)
636        {
637            Random rnd = new Random();
638            int[] vectorX = new int[settings.SecretVar];
639            int flag = 0;
640            int output = 0;
641            int[] secVarElement = new int[settings.SecretVar];
642
643            string outputCube = string.Empty;
644            foreach (int element in maxterm)
645                outputCube += "v" + element + " ";
646            if(settings.ConstTest > 0)
647                if (settings.EnableLogMessages)
648                    CubeAttack_LogMessage("Test if superpoly of subset " + outputCube + " is constant", NotificationLevel.Info);
649            for (int i = 0; i < settings.ConstTest; i++)
650            {
651                for (int j = 0; j < settings.SecretVar; j++)
652                    vectorX[j] = rnd.Next(0, 2);
653                for (ulong j = 0; j < Math.Pow(2, maxterm.Count); j++)
654                {
655                    if (stop)
656                        return false;
657
658                    for (int k = 0; k < maxterm.Count; k++)
659                        pubVarElement[maxterm[k]] = (j & ((ulong)1 << k)) > 0 ? 1 : 0;
660                    output ^= Blackbox(pubVarElement, vectorX);
661                }
662                if (i == 0)
663                    flag = output;
664                if (flag != output)
665                {
666                    if (settings.EnableLogMessages)
667                        CubeAttack_LogMessage("Superpoly of subset " + outputCube + " is not constant", NotificationLevel.Info);
668                    return false;
669                }
670                output = 0;
671
672                if (stop)
673                    return false;
674            }
675            if (settings.ConstTest > 0)
676                return true;
677            else
678                return false;
679        }
680
681        /// <summary>
682        /// Generates a random permutation of a finite set—in plain terms, for randomly shuffling the set.
683        /// </summary>
684        /// <param name="ilist">A List of values.</param>
685        public static void Shuffle(List<int> ilist)
686        {
687            Random rand = new Random();
688            int iIndex;
689            int tTmp;
690            for (int i = 1; i < ilist.Count; ++i)
691            {
692                iIndex = rand.Next(i + 1);
693                tTmp = ilist[i];
694                ilist[i] = ilist[iIndex];
695                ilist[iIndex] = tTmp;
696            }
697        }
698
699        /// <summary>
700        /// Test if an n x m matrix contains n linearly independent vectors.
701        /// </summary>
702        /// <param name="A">n x m matrix.</param>
703        /// <returns>A boolean value indicating if the matrix is regular or not.</returns>
704        public bool IsLinearIndependent(Matrix A)
705        {
706            double maxval;
707            int maxind;
708            double temp;
709            int Rang = 0;
710            double[,] a = new double[A.Cols, A.Rows];
711
712            for (int i = 0; i < A.Cols; i++)
713                for (int j = 0; j < A.Rows; j++)
714                    a[i, j] = A[j, i];
715
716            for (int j = 0; j < A.Rows; j++)
717            {
718                // Find maximum
719                maxval = a[j, j];
720                maxind = j;
721                for (int k = j; k < A.Cols; k++)
722                {
723                    if (a[k, j] > maxval)
724                    {
725                        maxval = a[k, j];
726                        maxind = k;
727                    }
728                    if (-a[k, j] > maxval)
729                    {
730                        maxval = -a[k, j];
731                        maxind = k;
732                    }
733                }
734
735                if (maxval != 0)
736                {
737                    Rang++;
738                    // Swap_Rows(j, maxind)
739                    for (int k = j; k < A.Rows; k++)
740                    {
741                        temp = a[j, k];
742                        a[j, k] = a[maxind, k];
743                        a[maxind, k] = temp;
744                    }
745
746                    // Gauss elimination
747                    for (int i = j + 1; i < A.Cols; i++)
748                        for (int k = j + 1; k < A.Rows; k++)
749                            a[i, k] = a[i, k] - (a[i, j] / a[j, j] * a[j, k]);
750                }
751            }
752            if (A.Rows == Rang)
753                return true;
754            else
755                return false;
756        } 
757
758        /// <summary>
759        /// Preprocessing Phase of the cube attack.
760        /// Implementation of the algorithm Random-Walk to find maxterms.
761        /// </summary>
762        public void PreprocessingPhase()
763        {
764            CubeAttack_LogMessage("Start preprocessing, try to find " + settings.SecretVar + " linearly independent superpolys", NotificationLevel.Info);
765
766            indexOutputBit = settings.TriviumOutputBit;
767            pubVarGlob = null;
768
769            //if (countSuperpoly == settings.SecretVar)
770            {
771                outputSuperpoly = string.Empty;
772                superpolyMatrix = new Matrix(settings.SecretVar, settings.SecretVar + 1);
773                listCubeIndexes = new List<List<int>>();
774                outputBitIndex = new int[settings.SecretVar];
775                countSuperpoly = 0;
776                matrixCheckLinearitySuperpolys = new Matrix(0, settings.SecretVar);
777            }
778
779                if (outputSuperpoly == null)
780                    outputSuperpoly = string.Empty;
781                if (superpolyMatrix == null)
782                    superpolyMatrix = new Matrix(settings.SecretVar, settings.SecretVar + 1);
783                if (listCubeIndexes == null)
784                    listCubeIndexes = new List<List<int>>();
785                if (outputBitIndex == null)
786                    outputBitIndex = new int[settings.SecretVar];
787                //if (countSuperpoly == 0)
788                //countSuperpoly = 0;
789                if (matrixCheckLinearitySuperpolys == null)
790                    matrixCheckLinearitySuperpolys = new Matrix(0, settings.SecretVar);
791
792            Random rnd = new Random();
793            int numberOfVariables = 0;
794            List<int> chooseIndexI = new List<int>();
795            List<int> superpoly = new List<int>();
796            List<int> maxterm = new List<int>();
797            List<List<int>> cubeList = new List<List<int>>();
798
799            // Save all public variables indexes in a list
800            for (int i = 0; i < settings.PublicVar; i++)
801                chooseIndexI.Add(i);
802
803            // Find n maxterms and save their in the matrix
804            while (countSuperpoly < settings.SecretVar)
805            {
806                if (stop)
807                    return;
808                else
809                {
810                    maxterm = new List<int>();
811                    superpoly.Clear();
812
813                    // Generate random size k between 1 and the number of public variables
814                    numberOfVariables = rnd.Next(1, settings.MaxCube + 1);
815
816                    // Permutation of the public variables
817                    Shuffle(chooseIndexI);
818
819                    // Construct cube of size k. Add k public variables to the cube
820                    for (int i = 0; i < numberOfVariables; i++)
821                        maxterm.Add(chooseIndexI[i]);
822
823                    string outputCube = string.Empty;
824                    foreach (int element in maxterm)
825                        outputCube += "v" + element + " ";
826
827                    if (settings.EnableLogMessages)
828                        CubeAttack_LogMessage("Start search for maxterm with subterm: " + outputCube, NotificationLevel.Info); 
829                   
830                    if (settings.TriviumOutputBit != indexOutputBit)
831                    {
832                        // User has changed Output Bit index, store new value
833                        indexOutputBit = settings.TriviumOutputBit;
834
835                        // Reset list of cube indexes, since a single maxterms can be associated with multiple superpolys from different outputs
836                        cubeList = new List<List<int>>();
837                    }
838                    while (superpoly.Count == 0)
839                    {
840                        if (maxterm.Count == 0)
841                        {
842                            if (numberOfVariables < chooseIndexI.Count)
843                            {
844                                if (settings.EnableLogMessages)
845                                    CubeAttack_LogMessage("Subset is empty, add variable v" + chooseIndexI[numberOfVariables], NotificationLevel.Info);
846                                maxterm.Add(chooseIndexI[numberOfVariables]);
847                                numberOfVariables++;
848                            }
849                            else
850                                break;
851                        }
852                        if (MaxtermKnown(cubeList, maxterm))
853                        {
854                            // Maxterm is already known, break and restart with new subset
855                            if (settings.EnableLogMessages)
856                            {
857                                outputCube = string.Empty;
858                                foreach (int element in maxterm)
859                                    outputCube += "v" + element + " ";
860                                CubeAttack_LogMessage("Maxterm " + outputCube + " is already known, restart with new subset", NotificationLevel.Info);
861                            }
862                            break;
863                        }
864
865                        if (IsSuperpolyConstant(new int[settings.PublicVar], maxterm))
866                        {
867                            if (stop)
868                                return;
869                            else
870                            {
871                                if (settings.EnableLogMessages)
872                                    CubeAttack_LogMessage("Superpoly is likely constant, drop variable v" + maxterm[0], NotificationLevel.Info);
873                                maxterm.RemoveAt(0);
874                            }
875                        }
876                        else if (!IsSuperpolyLinear(new int[settings.PublicVar], maxterm))
877                        {
878                            if (stop)
879                                return;
880                            else
881                            {
882                                if (settings.EnableLogMessages)
883                                    CubeAttack_LogMessage("Superpoly is not linear", NotificationLevel.Info);
884                                if (numberOfVariables < chooseIndexI.Count)
885                                {
886                                    if (maxterm.Count < settings.MaxCube)
887                                    {
888                                        if (settings.EnableLogMessages)
889                                            CubeAttack_LogMessage("Add variable v" + chooseIndexI[numberOfVariables], NotificationLevel.Info);
890                                        maxterm.Add(chooseIndexI[numberOfVariables]);
891                                        numberOfVariables++;
892                                    }
893                                    else
894                                        break;
895                                }
896                                else
897                                    break;
898                            }
899                        }
900                        else
901                        {
902                            if (stop)
903                                return;
904                            else
905                            {
906                                cubeList.Add(maxterm);
907                                if (settings.EnableLogMessages)
908                                {
909                                    outputCube = string.Empty;
910                                    foreach (int element in maxterm)
911                                        outputCube += "v" + element + " ";
912                                    CubeAttack_LogMessage(outputCube + " is new maxterm", NotificationLevel.Info);
913                                    outputCube = string.Empty;
914                                }
915                                superpoly = ComputeSuperpoly(new int[settings.PublicVar], maxterm);
916                                bool flag = false;
917                                outputCube += "Superpoly: ";
918                                if (superpoly[0] == 1)
919                                {
920                                    outputCube += "1";
921                                    flag = true;
922                                }
923                                for (int i = 1; i < superpoly.Count; i++)
924                                    if (superpoly[i] == 1)
925                                    {
926                                        if (flag)
927                                            outputCube += "+x" + Convert.ToString(i - 1);
928                                        else
929                                            outputCube += "x" + Convert.ToString(i - 1);
930                                        flag = true;
931                                    }
932                                outputCube += "   Cube Indexes: {";
933                                if (maxterm.Count > 0)
934                                {
935                                    maxterm.Sort();
936                                    for (int i = 0; i < maxterm.Count - 1; i++)
937                                        outputCube += maxterm[i] + ",";
938                                    outputCube += maxterm[maxterm.Count - 1] + "}   Output Bit: " + indexOutputBit;
939                                }
940                                else
941                                    outputCube += " }   Output Bit: " + indexOutputBit;
942
943                                if (settings.EnableLogMessages)
944                                    CubeAttack_LogMessage(outputCube, NotificationLevel.Info);
945                                break;
946                            }
947                        }
948                    }//End while (superpoly.Count == 0)
949
950                    if (!InMatrix(superpoly, superpolyMatrix))
951                    {
952                        List<int> superpolyWithoutConstant = new List<int>();
953                        for (int i = 1; i < superpoly.Count; i++)
954                            superpolyWithoutConstant.Add(superpoly[i]);
955
956                        matrixCheckLinearitySuperpolys = matrixCheckLinearitySuperpolys.AddRow(superpolyWithoutConstant);
957                        if (IsLinearIndependent(matrixCheckLinearitySuperpolys))
958                        {
959                            for (int j = 0; j < superpoly.Count; j++)
960                                superpolyMatrix[countSuperpoly, j] = superpoly[j];
961
962                            listCubeIndexes.Add(maxterm);
963                            OutputSuperpolys(maxterm, superpoly);
964                            outputBitIndex[countSuperpoly] = indexOutputBit;
965                            countSuperpoly++;
966                            CubeAttack_LogMessage("Found " + countSuperpoly + " of " + settings.SecretVar + " linearly independent superpolys", NotificationLevel.Info);
967                            ProgressChanged((double)countSuperpoly / (double)settings.SecretVar, 1.0);
968                        }
969                        else
970                            matrixCheckLinearitySuperpolys = matrixCheckLinearitySuperpolys.DeleteLastRow();
971                    }
972
973                    if (countSuperpoly == settings.SecretVar)
974                        CubeAttack_LogMessage(settings.SecretVar + " linearly independent superpolys have been found, preprocessing phase completed", NotificationLevel.Info);
975                }
976            }//End while (countSuperpoly < settings.SecretVar)
977        }//End PreprocessingPhase
978
979        /// <summary>
980        /// Online Phase of the cube attack.
981        /// </summary>
982        /// <param name="superpolyMatrix">An n x n matrix which contains the superpolys.</param>
983        /// <param name="listCubeIndexes">A list of lists of cube indexes.</param>
984        public void OnlinePhase()
985        {   
986            if (settings.ReadSuperpolysFromFile)
987            {
988                if (File.Exists(settings.OpenFilename))
989                {
990                    superpolyMatrix = new Matrix(settings.SecretVar, settings.SecretVar + 1);
991                    listCubeIndexes = new List<List<int>>();
992                    outputBitIndex = new int[settings.SecretVar];
993
994                    int i = 0;
995                    foreach (string sLine in File.ReadAllLines(settings.OpenFilename))
996                    {
997                        string[] allValues = sLine.Split(' ');
998                        string[] variables = allValues[0].Split('+');
999                        string[] cubeIndex = allValues[1].Split(',');
1000
1001                        List<string> variablesList = new List<string>(variables); // Copy to List
1002
1003                        for (int j = 0; j < variablesList.Count; j++)
1004                            if (variablesList[j].Substring(0, 1) == "1")
1005                            {
1006                                superpolyMatrix[i, 0] = 1;
1007                                variablesList.Remove(variablesList[j]);
1008                            }
1009
1010                        for (int j = 0; j < variablesList.Count; j++)
1011                            if (variablesList[j].Substring(0, 1) == "x")
1012                                variablesList[j] = variablesList[j].Substring(1);
1013
1014                        List<int> superpoly = new List<int>();
1015                        for (int j = 0; j < variablesList.Count; j++)
1016                            superpoly.Add(Convert.ToInt32(variablesList[j]));
1017                        for (int j = 0; j < superpoly.Count; j++)
1018                            superpolyMatrix[i, superpoly[j] + 1] = 1;
1019
1020                        List<int> maxterm = new List<int>();
1021                        foreach (string cube in cubeIndex)
1022                            maxterm.Add(Convert.ToInt32(cube));
1023                        listCubeIndexes.Add(maxterm);
1024
1025                        outputBitIndex[i] = Convert.ToInt32(allValues[2]);
1026                        i++;
1027                    }
1028                }
1029                else
1030                {
1031                    CubeAttack_LogMessage("Please input a File", NotificationLevel.Error);
1032                    return;
1033                }
1034            }
1035
1036            if (superpolyMatrix == null || listCubeIndexes == null)
1037                CubeAttack_LogMessage("Preprocessing phase has to be executed first", NotificationLevel.Error);
1038            else
1039            {
1040                CubeAttack_LogMessage("Start online phase", NotificationLevel.Info);
1041
1042                outputSuperpoly = string.Empty;
1043                int[] pubVarElement = new int[settings.PublicVar];
1044
1045                if (pubVarGlob != null)
1046                {
1047                    for (int i = 0; i < settings.PublicVar; i++)
1048                        pubVarElement[i] = pubVarGlob[i];
1049                }
1050
1051                Vector b = new Vector(settings.SecretVar);
1052                StringBuilder output = new StringBuilder(string.Empty);
1053                bool flag = false;
1054                string logOutput = string.Empty;
1055
1056                for (int i = 0; i < listCubeIndexes.Count; i++)
1057                {
1058                    flag = false;
1059                    logOutput = string.Empty;
1060                    output.Append("Superpoly: ");
1061                    if (superpolyMatrix[i, 0] == 1)
1062                    {
1063                        output.Append("1");
1064                        logOutput += "1";
1065                        flag = true;
1066                    }
1067                    for (int j = 1; j < superpolyMatrix.Cols; j++)
1068                    {
1069                        if (superpolyMatrix[i, j] == 1)
1070                        {
1071                            if (flag)
1072                            {
1073                                output.Append("+x" + Convert.ToString(j - 1));
1074                                logOutput += "+x" + Convert.ToString(j - 1);
1075                            }
1076                            else
1077                            {
1078                                output.Append("x" + Convert.ToString(j - 1));
1079                                logOutput += "x" + Convert.ToString(j - 1);
1080                            }
1081                            flag = true;
1082                        }
1083                    }
1084                    CubeAttack_LogMessage("Compute value of maxterm equation " + logOutput, NotificationLevel.Info);
1085
1086                    for (ulong k = 0; k < Math.Pow(2, listCubeIndexes[i].Count); k++)
1087                    {
1088                        if (stop)
1089                            return;
1090                        for (int l = 0; l < listCubeIndexes[i].Count; l++)
1091                            pubVarElement[listCubeIndexes[i][l]] = (k & ((ulong)1 << l)) > 0 ? 1 : 0;
1092                        try
1093                        {
1094                            //switch(settings.BlackBox)
1095                            {
1096                                //case 0:
1097                                    // Online phase BooleanFunctionParser
1098                                //bool[] vBool = new bool[pubVarElement.Length];
1099                                    //for (int l = 0; l < pubVarElement.Length; l++)
1100                                        //  vBool[l] = Convert.ToBoolean(pubVarElement[l]);
1101                                    //b[i] ^= ParserOutput.SolveFunction(vBool, null);
1102                                  //  break;
1103                                    //case 1:
1104                                    // Online phase Trivium
1105                                b[i] ^= CubeattackBlackbox.GenerateBlackboxOutputBit(pubVarElement, null, outputBitIndex[i]);
1106                                //break;
1107                            }
1108                        }
1109                        catch (Exception ex)
1110                        {
1111                            CubeAttack_LogMessage("Error: " + ex, NotificationLevel.Error);
1112                        }
1113                    }
1114                    for (int j = 0; j < settings.PublicVar; j++)
1115                        pubVarElement[j] = 0;
1116
1117                    output.Append(" = " + b[i] + "   Cube Indexes: {");
1118                    listCubeIndexes[i].Sort();
1119                    for (int j = 0; j < listCubeIndexes[i].Count - 1; j++)
1120                        output.Append(listCubeIndexes[i][j] + ",");
1121                    output.Append(listCubeIndexes[i][listCubeIndexes[i].Count - 1] + "}   Output Bit: " + outputBitIndex[i] + "\n");
1122                    outputSuperpoly += output.ToString();
1123
1124                    OnPropertyChanged("OutputSuperpoly");
1125                    ProgressChanged((double)i / (double)listCubeIndexes.Count, 1.0);
1126                    outputSuperpoly = string.Empty;
1127                }
1128
1129                if (listCubeIndexes.Count == settings.SecretVar)
1130                {
1131                    CubeAttack_LogMessage("Solve system of equations", NotificationLevel.Info);
1132                    for (int i = 0; i < settings.SecretVar; i++)
1133                        b[i] ^= superpolyMatrix[i, 0];
1134                    // Delete first column and invert
1135                    OutputKey(superpolyMatrix.DeleteFirstColumn().Inverse() * b);
1136                    OnPropertyChanged("OutputKeyBits");
1137                    CubeAttack_LogMessage("Key bits successfully discovered, online phase completed", NotificationLevel.Info);
1138                }
1139                else
1140                    CubeAttack_LogMessage("Not enough linearly independent superpolys have been found in the preprocessing to discover all secret bits !", NotificationLevel.Info);
1141            }
1142        }
1143
1144        /// <summary>
1145        /// User-Mode to set public bit values manually.
1146        /// </summary>
1147        public void SetPublicBitsPhase()
1148        {
1149            outputSuperpoly = string.Empty;
1150            outputKeyBits = string.Empty;
1151            superpolyMatrix = new Matrix(settings.SecretVar, settings.SecretVar + 1);
1152            listCubeIndexes = new List<List<int>>();
1153            pubVarGlob = new int[settings.PublicVar];
1154            List<int> maxterm = new List<int>();
1155            bool fault = false;
1156
1157            if (settings.TriviumOutputBit != indexOutputBit)
1158                indexOutputBit = settings.TriviumOutputBit;
1159
1160            if (settings.SetPublicBits.Length != settings.PublicVar)
1161                CubeAttack_LogMessage("Input public bits must have size " + settings.PublicVar + " (Currently: " + settings.SetPublicBits.Length + " )", NotificationLevel.Error);
1162            else
1163            {
1164                for (int i = 0; i < settings.SetPublicBits.Length; i++)
1165                {
1166                    switch (settings.SetPublicBits[i])
1167                    {
1168                        case '0':
1169                            pubVarGlob[i] = 0;
1170                            break;
1171                        case '1':
1172                            pubVarGlob[i] = 1;
1173                            break;
1174                        case '*':
1175                            maxterm.Add(i);
1176                            break;
1177                        default:
1178                            fault = true;
1179                            break;
1180                    }
1181                }
1182                if (fault)
1183                    CubeAttack_LogMessage("The input public bits does not consists only of characters : \'0\',\'1\',\'*\' !", NotificationLevel.Error);
1184                else
1185                {
1186                    if (maxterm.Count > 0)
1187                    {
1188                        if (!IsSuperpolyConstant(pubVarGlob, maxterm))
1189                            if (IsSuperpolyLinear(pubVarGlob, maxterm))
1190                            {
1191                                List<int> superpoly = ComputeSuperpoly(pubVarGlob, maxterm);
1192                                if (!stop)
1193                                {
1194                                    for (int i = 0; i < superpoly.Count; i++)
1195                                        superpolyMatrix[0, i] = superpoly[i];
1196                                    listCubeIndexes.Add(maxterm);
1197                                    OutputSuperpolys(maxterm, superpoly);
1198                                }
1199                            }
1200                            else
1201                            {
1202                                if(!stop)
1203                                    CubeAttack_LogMessage("The corresponding superpoly is not a linear polynomial !", NotificationLevel.Info);
1204                            }
1205                        else
1206                            CubeAttack_LogMessage("The corresponding superpoly is constant !", NotificationLevel.Info);
1207                    }
1208                    else
1209                    {
1210                        StringBuilder output = new StringBuilder(string.Empty);
1211                        output.Append("Output bit: " + Blackbox(pubVarGlob, new int[settings.SecretVar]));
1212                        outputSuperpoly += output.ToString();
1213                        OnPropertyChanged("OutputSuperpoly");
1214                        CubeAttack_LogMessage("Output bit: " + Blackbox(pubVarGlob, new int[settings.SecretVar]), NotificationLevel.Info);
1215                    }
1216                }
1217            }
1218        }
1219
1220        public void Pause()
1221        {
1222        }
1223
1224        #endregion
1225
1226        #region Private methods
1227
1228        /// <summary>
1229        /// Does the actual CubeAttack processing
1230        /// </summary>
1231        private void ProcessCubeAttack(CubeAttackMode mode)
1232        {
1233            switch (mode)
1234            {
1235                case CubeAttackMode.preprocessing:
1236                    PreprocessingPhase();
1237                    break;
1238                case CubeAttackMode.online:
1239                    OnlinePhase();
1240                    break;
1241                case CubeAttackMode.setPublicBits:
1242                    SetPublicBitsPhase();
1243                    break;
1244            }
1245        }
1246
1247        /// <summary>
1248        /// Handles log messages
1249        /// </summary>
1250        private void CubeAttack_LogMessage(string msg, NotificationLevel logLevel)
1251        {
1252            if (OnGuiLogNotificationOccured != null)
1253            {
1254                OnGuiLogNotificationOccured(this, new GuiLogEventArgs(msg, this, logLevel));
1255            }
1256        }
1257
1258        #region IControlEncryption Members
1259
1260        /*private IControlSolveFunction parserOutput;
1261        [PropertyInfo(Direction.ControlMaster, "Master for BFP", "Master for BFP (SolveFunction)", "", DisplayLevel.Beginner)]
1262        public IControlSolveFunction ParserOutput
1263        {
1264            get { return parserOutput; }
1265            set
1266            {
1267                if (value != null)
1268                    parserOutput = value;
1269            }
1270        }
1271
1272        private IControlTrivium triviumOutput;
1273        [PropertyInfo(Direction.ControlMaster, "Master for Trivium", "Master for Trivium", "", DisplayLevel.Beginner)]
1274        public IControlTrivium TriviumOutput
1275        {
1276            get { return triviumOutput; }
1277            set
1278            {
1279                if (value != null)
1280                    triviumOutput = value;
1281            }
1282        }*/
1283
1284        private IControlCubeAttack cubeattackBlackbox;
1285        [PropertyInfo(Direction.ControlMaster, "Master for CubeAttack", "Master for CubeAttack", "", DisplayLevel.Beginner)]
1286        public IControlCubeAttack CubeattackBlackbox
1287        {
1288            get { return cubeattackBlackbox; }
1289            set
1290            {
1291                if (value != null)
1292                    cubeattackBlackbox = value;
1293            }
1294        }
1295
1296        #endregion
1297
1298        #endregion
1299
1300
1301        #region INotifyPropertyChanged Members
1302
1303        public event PropertyChangedEventHandler PropertyChanged;
1304        public void OnPropertyChanged(string name)
1305        {
1306            if (PropertyChanged != null)
1307            {
1308                PropertyChanged(this, new PropertyChangedEventArgs(name));
1309            }
1310        }
1311
1312        #endregion
1313    }
1314}
Note: See TracBrowser for help on using the repository browser.