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

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