Changeset 1183


Ignore:
Timestamp:
Feb 24, 2010, 9:22:07 PM (12 years ago)
Author:
pretzsch
Message:

+ MD5Collider: Added description
+ MD5Collider: Added new optional input allowing user to specify prefix of generated colliding data blocks
o MD5Collider: Made RandomSeed input optional

Location:
trunk/CrypPlugins/MD5Collider
Files:
1 added
6 edited

Legend:

Unmodified
Added
Removed
  • trunk/CrypPlugins/MD5Collider/Algorithm/IMD5ColliderAlgorithm.cs

    r1171 r1183  
    1111        byte[] FirstCollidingData { get; }
    1212        byte[] SecondCollidingData { get; }
    13         byte[] RandomSeed { get; set; }
     13        byte[] RandomSeed { set; }
     14        byte[] IHV { set; }
    1415
    1516        TimeSpan ElapsedTime { get; }
  • trunk/CrypPlugins/MD5Collider/Algorithm/MD5ColliderBase.cs

    r1171 r1183  
    1212        public byte[] FirstCollidingData { get; protected set; }
    1313        public byte[] SecondCollidingData { get; protected set; }
    14         public byte[] RandomSeed { get; set; }
     14        public byte[] RandomSeed { protected get; set; }
     15        public byte[] IHV { protected get; set; }
    1516
    1617        private String _status;
     
    9495        public void FindCollision()
    9596        {
     97            CheckRandomSeed();
     98            CheckIHV();
     99
    96100            StartTimer();
    97101            PerformFindCollision();
    98102            StopTimer();
     103        }
     104
     105        private void CheckIHV()
     106        {
     107            if (IHV == null || IHV.Length != 16)
     108            {
     109                IHV = new byte[] { 0x01, 0x23, 0x45, 0x67, 0x89, 0xAB, 0xCD, 0xEF, 0xFE, 0xDC, 0xBA, 0x98, 0x76, 0x54, 0x32, 0x10 };
     110            }
     111        }
     112
     113        private void CheckRandomSeed()
     114        {
     115            if (RandomSeed == null)
     116            {
     117                RandomSeed = new byte[35];
     118                new Random().NextBytes(RandomSeed);
     119            }
    99120        }
    100121
  • trunk/CrypPlugins/MD5Collider/Algorithm/StevensCollider.cs

    r1171 r1183  
    1818            seed32_2 = (UInt32)(BitConverter.ToInt32(seedBytesMd5, 8) ^ BitConverter.ToInt32(seedBytesMd5, 12));
    1919
    20             UInt32[] standardIV = new UInt32[4];
    21             standardIV[0] = toLittleEndianInteger(new byte[] { 0x01, 0x23, 0x45, 0x67 });
    22             standardIV[1] = toLittleEndianInteger(new byte[] { 0x89, 0xAB, 0xCD, 0xEF });
    23             standardIV[2] = toLittleEndianInteger(new byte[] { 0xFE, 0xDC, 0xBA, 0x98 });
    24             standardIV[3] = toLittleEndianInteger(new byte[] { 0x76, 0x54, 0x32, 0x10 });
     20            UInt32[] startIV = new UInt32[4];
     21            startIV[0] = toLittleEndianInteger(IHV, 0);
     22            startIV[1] = toLittleEndianInteger(IHV, 4);
     23            startIV[2] = toLittleEndianInteger(IHV, 8);
     24            startIV[3] = toLittleEndianInteger(IHV, 12);
    2525
    2626            UInt32[] m1b0 = new UInt32[16], m1b1 = new UInt32[16], m2b0 = new UInt32[16], m2b1 = new UInt32[16];
    27             find_collision(standardIV, m1b0, m1b1, m2b0, m2b1);
     27            find_collision(startIV, m1b0, m1b1, m2b0, m2b1);
    2828
    2929            if (IsStopped)
     
    5858        }
    5959
     60        private UInt32 toLittleEndianInteger(byte[] bytes, int offset)
     61        {
     62            byte[] bytesInProperOrder = new byte[4];
     63            Array.Copy(bytes, offset, bytesInProperOrder, 0, 4);
     64            if (!BitConverter.IsLittleEndian)
     65                Array.Reverse(bytesInProperOrder);
     66
     67            return BitConverter.ToUInt32(bytesInProperOrder, 0);
     68        }
    6069        private UInt32 toLittleEndianInteger(byte[] bytes)
    6170        {
    62             byte[] bytesInProperOrder = new byte[4];
    63             Array.Copy(bytes, bytesInProperOrder, 4);
    64             if (!BitConverter.IsLittleEndian)
    65                 Array.Reverse(bytesInProperOrder);
    66 
    67             return BitConverter.ToUInt32(bytesInProperOrder, 0);
     71            return toLittleEndianInteger(bytes, 0);
    6872        }
    6973
  • trunk/CrypPlugins/MD5Collider/DetailedDescription/Description.xaml

    r957 r1183  
    1 <FlowDocument PagePadding="5,0,5,0" AllowDrop="True"
    2               NumberSubstitution.CultureSource="User"
    3               Background="White" FontFamily="Tahoma"
    4               FontSize="10"
    5               xmlns="http://schemas.microsoft.com/winfx/2006/xaml/presentation">
    6   <Paragraph>
    7     <Run FontWeight="Bold" FontSize="24">Message-Digest Algorithm 5</Run>
    8   </Paragraph>
    9   <Paragraph>
    10     <Run FontWeight="Bold" FontSize="12">MD5</Run>
    11     <Run FontSize="12" xml:space="preserve">(Message-Digest Algorithm 5) ist eine weit verbreitete kryptographische Hash-Funktion, die einen 128-Bit-Hashwert erzeugt. MD5 wurde 1991 von Ronald L. Rivest entwickelt. Die errechneten MD5-Summen (kurz md5sum) werden zum Beispiel zur IntegritÀtsprÃŒfung von Dateien eingesetzt.</Run>
    12   </Paragraph>
    13   <Paragraph>
    14     <Run FontWeight="Bold" FontSize="12">I</Run>
    15     <Run FontWeight="Bold" FontSize="12" xml:lang="de-de">n</Run>
    16     <Run FontWeight="Bold" FontSize="12">haltsverzeichnis</Run>
    17   </Paragraph>
    18   <List MarkerStyle="Decimal">
    19     <ListItem>
    20       <Paragraph>
    21         <Run FontSize="12">Geschichte</Run>
    22       </Paragraph>
    23     </ListItem>
    24     <ListItem>
    25       <Paragraph>
    26         <Run FontSize="12">MD5-Hashes</Run>
    27       </Paragraph>
    28     </ListItem>
    29     <ListItem>
    30       <Paragraph>
    31         <Run FontSize="12">Verwendung und VerfÃŒgbarkeit</Run>
    32       </Paragraph>
    33     </ListItem>
    34     <ListItem>
    35       <Paragraph>
    36         <Run FontSize="12">Algorithmus</Run>
    37       </Paragraph>
    38     </ListItem>
    39   </List>
    40   <Paragraph>
    41     <Run FontWeight="Bold" FontSize="16">Geschichte</Run>
    42   </Paragraph>
    43   <Paragraph>
    44     <Run FontSize="13.3333333333333">MD5 ist ein Vertreter aus einer Reihe von (kryptologischen) Hash-Funktionen, die von Professor Ronald L. Rivest am Massachusetts Institute of Technology entwickelt wurden. Als Analysen ergaben, dass der VorgÀnger MD4 wahrscheinlich unsicher ist, wurde MD5 1991 als sicherer Ersatz entwickelt. TatsÀchlich wurden spÀter von Hans Dobbertin SchwÀchen in MD4 gefunden.</Run>
    45   </Paragraph>
    46   <Paragraph>
    47     <Run FontSize="13.3333333333333">1996 meldete Dobbertin eine Kollision in der Kompressionsfunktion von MD5. Dies war zwar kein Angriff auf die vollstÀndige MD5-Funktion, dennoch empfahlen Kryptographen bereits damals, wenn möglich, auf sicherere Algorithmen wie SHA-256 oder RIPEMD-160 umzusteigen. Im August 2004 fanden chinesische Forscher Kollisionen fÃŒr die vollstÀndige MD5-Funktion. Wie sich diese Entdeckung auf die Verwendung von MD5 auswirkt, bleibt abzuwarten.</Run>
    48   </Paragraph>
    49   <Paragraph>
    50     <Run FontSize="13.3333333333333">Diese Attacken wirken sich allerdings nur auf Kollisionsangriffe aus, Preimage-Angriffe können auch mit diesen Methoden nicht in sinnvoller Zeit durchgefÃŒhrt werden. So kann ein bestehendes, mit MD5 erzeugtes Zertifikat nach wie vor nicht gefÀlscht werden.</Run>
    51   </Paragraph>
    52   <Paragraph>
    53     <Run FontSize="12" xml:lang="de-de">........</Run>
    54   </Paragraph>
    55   <Paragraph>
    56     <Run FontWeight="Bold" FontSize="16" xml:lang="de-de">Algorithmus</Run>
    57   </Paragraph>
    58   <Paragraph>
    59     <Run FontSize="13.3333333333333" xml:lang="de-de">MD5 erzeugt aus einer Nachricht variabler LÀnge eine Ausgabe fester LÀnge (128 Bit). Die Ausgangsnachricht wird zunÀchst so aufgefÃŒllt, dass ihre LÀnge 64 Bits davon entfernt ist durch 512 teilbar zu sein. Als erstes wird eine Eins angehÀngt, dann soviele Nullen wie nötig. Bei dem unwahrscheinlichen Fall, dass die Ausgangsnachricht schon die gewÃŒnschte LÀnge besitzt wird trotzdem eine Eins angehÀngt. Nun wird eine 64-Bit Zahl, die die LÀnge der Ausgangsnachricht reprÀsentiert, angehÀngt. Die NachrichtenlÀnge ist jetzt durch 512 teilbar.</Run>
    60   </Paragraph>
    61   <Paragraph>
    62     Der Hauptalgorithmus von MD5 arbeitet mit einem 128-Bit-Puffer, der in vier 32-Bit-Wörter A, B, C und D unterteilt ist. Diese werden mit bestimmten Konstanten initialisiert. Auf diesen Puffer wird nun die VerschlÃŒsselungsfunktion (hÀufig auch Komprimierungsfunktion genannt) mit dem ersten 512-Bit-Block als SchlÃŒsselparameter aufgerufen. Die Behandlung eines Nachrichtenblocks geschieht in vier einander Àhnlichen Stufen, von Kryptografen „Runden“ genannt. Jede Runde besteht aus 16 Operationen, basierend auf einer nichtlinearen Funktion „F“, modularer Addition und Linksrotation. Es gibt vier mögliche „F“-Funktionen, in jeder Runde wird davon eine andere verwendet:
    63     <InlineUIContainer>
    64       <Image Width="180" Height="197" Source="/MD5;Component/DetailedDescription/Images/MD5.png" />
    65     </InlineUIContainer>
    66   </Paragraph>
    67   <Paragraph />
    68   <Paragraph>
    69     <Run FontWeight="Bold" FontSize="20">Pseudocode</Run>
    70   </Paragraph>
    71   <Paragraph>
    72     <Run FontSize="13.3333333333333" Foreground="#FF008000" xml:lang="de-de">// Beachte: Alle Variablen sind vorzeichenlose 32 Bit-Werte und</Run>
    73     <LineBreak />
    74     <Run FontSize="13.3333333333333" Foreground="#FF008000" xml:lang="de-de">// verhalten sich bei Berechnungen kongruent (≡) modulo 2^32</Run>
    75     <LineBreak />
    76     <Run FontSize="13.3333333333333" Foreground="#FF008000" xml:lang="de-de">// Definiere r wie folgt:</Run>
    77   </Paragraph>
    78   <Paragraph>
    79     <Run FontWeight="Bold" FontSize="13.3333333333333" xml:lang="de-de" xml:space="preserve">var </Run>
    80     <Run FontSize="13.3333333333333" xml:lang="de-de">int[64] r, k</Run>
    81     <LineBreak />
    82     <Run FontSize="13.3333333333333" xml:lang="de-de" xml:space="preserve">r[ 0..15] := {7, 12, 17, 22,  7, 12, 17, 22,  7, 12, 17, 22,  7, 12, 17, 22}</Run>
    83     <LineBreak />
    84     <Run FontSize="13.3333333333333" xml:lang="de-de" xml:space="preserve">r[16..31] := {5,  9, 14, 20,  5,  9, 14, 20,  5,  9, 14, 20,  5,  9, 14, 20}</Run>
    85     <LineBreak />
    86     <Run FontSize="13.3333333333333" xml:lang="de-de" xml:space="preserve">r[32..47] := {4, 11, 16, 23,  4, 11, 16, 23,  4, 11, 16, 23,  4, 11, 16, 23}</Run>
    87     <LineBreak />
    88     <Run FontSize="13.3333333333333" xml:lang="de-de" xml:space="preserve">r[48..63] := {6, 10, 15, 21,  6, 10, 15, 21,  6, 10, 15, 21,  6, 10, 15, 21}</Run>
    89   </Paragraph>
    90 </FlowDocument>
     1<FlowDocument PagePadding="5,0,5,0" AllowDrop="True" NumberSubstitution.CultureSource="User" xmlns="http://schemas.microsoft.com/winfx/2006/xaml/presentation"><Paragraph><Run FontWeight="Bold" FontSize="18.6666666666667" xml:lang="de-de">MD5 collider</Run></Paragraph><Paragraph><Run FontSize="13.3333333333333" xml:lang="de-de" xml:space="preserve">The MD5 collider plugin allows you to create two blocks of differing binary data which either hash to the same MD5 value or can be used as part of data hashing to the same MD5 value. These blocks will always be exactly 128 bytes long. They are output as byte[] and stream objects. The plugin takes two optional inputs. </Run></Paragraph><Paragraph><Run FontSize="13.3333333333333" xml:lang="de-de" xml:space="preserve">The first is a </Run><Run FontWeight="Bold" FontSize="13.3333333333333" xml:lang="de-de">random seed</Run><Run FontSize="13.3333333333333" xml:lang="de-de">. This input - if connected - allows you to get a reproducable result: Two runs of the collider with the same random seed will generate the same binary output in approximately the same running time. If left unconnected, the output and running time will be different for each execution.</Run></Paragraph><Paragraph><Run FontSize="13.3333333333333" xml:lang="de-de" xml:space="preserve">As a second input, an optional </Run><Run FontWeight="Bold" FontSize="13.3333333333333" xml:lang="de-de">"prefix" parameter</Run><Run FontSize="13.3333333333333" xml:lang="de-de" xml:space="preserve"> can be given. If this parameter is omitted, you will simply receive two blocks of output that hash to the same MD5 value. Due to the nature of MD5, appending identical data to both of these blocks will still result in them hashing to the same value. However, prepending identical data to the blocks will break the collision.</Run></Paragraph><Paragraph><Run FontSize="13.3333333333333" xml:lang="de-de">If you want to prepend data to build your collision data, you should set this data as the prefix parameter. It must have a length that is a multiple of 64 bytes. When it is set to a non-empty value, an intermediate hash value is calculated from the input and used in the computation instead of the default starting IHV, resulting in different output blocks which will not hash to the same MD5 value on their own. However, if you concatenate the generated blocks B1 and B2 to the given prefix data P so that you receive two new blocks (P || B1) and (P || B2), they will have the same MD5. You can then append more identical data without breaking the collision. Thus, using the prefix parameter, you may create colliding blocks (Prefix || C1 || Postfix), (Prefix || C2 || Postfix) with identical pre- and postfixes.</Run></Paragraph></FlowDocument>
  • trunk/CrypPlugins/MD5Collider/MD5Collider.cs

    r1171 r1183  
    4848            Collider = new StevensCollider();
    4949            Collider.Status = "Waiting";
    50 
    51             worker = new BackgroundWorker();
    52             worker.DoWork += DoWork;
    5350        }
    5451
     
    114111
    115112        private byte[] randomSeed;
    116         [PropertyInfo(Direction.InputData, "Random seed", "Data used for initialization of RNG", "", true, false, DisplayLevel.Beginner, QuickWatchFormat.Hex, null)]
     113        [PropertyInfo(Direction.InputData, "Random seed", "Data used for initialization of RNG", "", false, false, DisplayLevel.Beginner, QuickWatchFormat.Hex, null)]
    117114        public byte[] RandomSeed
    118115        {
    119116            get { return randomSeed; }
    120             set
    121             {
    122                 this.randomSeed = value;
    123                 OnPropertyChanged("RandomSeed");
    124             }
     117            set { this.randomSeed = value; OnPropertyChanged("RandomSeed"); }
    125118        }
    126        
    127         BackgroundWorker worker;
     119
     120        private byte[] prefix;
     121        [PropertyInfo(Direction.InputData, "IHV", "Initial Hash Value", "", false, false, DisplayLevel.Beginner, QuickWatchFormat.Hex, null)]
     122        public byte[] Prefix
     123        {
     124            get { return prefix; }
     125            set { this.prefix = value; OnPropertyChanged("Prefix"); }
     126        }
     127
     128        public static bool testRun = true;
    128129
    129130        public void Execute()
    130131        {
    131             DoWork(this, null);
    132             return;
    133 
    134             if (worker.IsBusy)
     132            // TODO: EXTREMELY DIRTY IMPROVEME!
     133            // This exists to prevent the plugin from frezzing Cryptool when test-running at startup
     134            if (testRun)
     135            {
     136                testRun = false;
    135137                return;
    136 
    137             worker.RunWorkerAsync();
    138         }
    139 
    140         private void GuiLogMessage(string message, NotificationLevel logLevel)
    141         {
    142             EventsHelper.GuiLogMessage(OnGuiLogNotificationOccured, this, new GuiLogEventArgs(message, this, logLevel));
    143         }
    144 
    145         public void DoWork(object o, EventArgs e)
    146         {
    147             GuiLogMessage("DoWork()", NotificationLevel.Debug);
    148             Collider.Status = "Executing";
    149 
    150             if (RandomSeed == null)
    151                 return;
     138            }
    152139
    153140            ProgressChanged(0.5, 1.0);
    154141
    155142            Collider.RandomSeed = RandomSeed;
     143
     144            if (Prefix != null)
     145            {
     146                if (Prefix.Length % 64 != 0)
     147                {
     148                    GuiLogMessage("Prefix bytes must be a multiple of 64 bytes long!", NotificationLevel.Error);
     149                    return;
     150                }
     151
     152                Collider.IHV = new IHVCalculator(Prefix).GetIHV();
     153            }
     154
    156155            Collider.FindCollision();
    157156
     
    160159
    161160            ProgressChanged(1.0, 1.0);
     161        }
    162162
    163             Collider.Status = "Finished";
     163        private void GuiLogMessage(string message, NotificationLevel logLevel)
     164        {
     165            EventsHelper.GuiLogMessage(OnGuiLogNotificationOccured, this, new GuiLogEventArgs(message, this, logLevel));
    164166        }
    165167
  • trunk/CrypPlugins/MD5Collider/MD5Collider.csproj

    r1171 r1183  
    6060  </ItemGroup>
    6161  <ItemGroup>
     62    <Compile Include="Algorithm\IHVCalculator.cs" />
    6263    <Compile Include="Algorithm\IMD5ColliderAlgorithm.cs" />
    6364    <Compile Include="Algorithm\KlimaTunnelsCollider.cs" />
Note: See TracChangeset for help on using the changeset viewer.