MD5 brute force cracking system and method based on FPGA
Technical Field
The invention relates to the technical field of information security, in particular to an MD5 brute force cracking system and method based on an FPGA.
Background
Brief description of the MD5 algorithm: the MD5 processes incoming information in 512-bit packets, each of which is divided into 16 32-bit sub-packets, and after a series of processing, the output of the algorithm consists of four 32-bit packets, which when concatenated will generate a 128-bit hash value that is unique.
MD5 main cycle 4 rounds, each round is very similar. Each round of operation is carried out for 16 times, namely 16 steps of operation; the first round is 16 FF (a, b, c, d, Mj, s, ti) operations, the second round is 16 GG (a, b, c, d, Mj, s, ti) operations, the third round is 16 HH (a, b, c, d, Mj, s, ti) operations, the fourth round is 16 II (a, b, c, d, Mj, s, ti) operations, and finally a 128-bit hash value consisting of 4 32-bit a, b, c, d is output.
Because the MD5 is irreversible, only different numbers, upper and lower case letters and character combinations can be used, one by one exhaustion is realized, namely brute force cracking, the secret key is sent to the MD5 arithmetic unit for arithmetic processing, the arithmetic result is the same as the hash value of the MD5 to be cracked, and the cracking is successful.
The patent search in the prior art finds that the 'ultrahigh throughput MD5 brute force cracking device realized based on the FPGA' of patent No. 201110099441 provides a design method of an MD5 algorithm based on the brute force cracking of the FPGA hardware, and the patent defects are as follows: one MD5 brute force cracking core operation unit is used for performing one-stage pipeline processing each time, namely 64-stage pipeline processing 64 operation operations (4 rounds of MD5 main cycle, 64 operation operations), one-stage pipeline processing limits the running speed of the MD5 brute force cracking operations in the FPGA, namely the clock frequency of the FPGA, and the patent refers to single-core MD5 brute force cracking. Yet another prior patent publication "hard-augmented MD5 function" proposes a design method based on an FPGA, but the MD5 core algorithm is implemented by 64-stage pipeline processing, which limits the clock frequency of the FPGA, and only has a single-core MD5 brute-force cracking operation unit and no parallel multi-core MD5 operation unit. "efficiency Implementation of HashAlgorithm a Processor" of patent No. 3/440,264 proposes a solution for implementing the MD5 algorithm based on an ARM Processor, which is deficient in that: the ARM processor is not as fast and efficient as the FPGA and is also a single-core MD5 brute-force arithmetic unit process. Another existing patent discloses a cracking method of file passwords and provides an exhaustive cracking scheme based on a PC (personal computer), the PC is a serial processing mechanism and can only process a single-core MD5 brute force cracking operation unit, the FPGA is parallel processing, and simultaneously, the multi-core MD5 brute force cracking operation unit can perform parallel processing, so the design defect of the patent is that the MD5 brute force cracking is long in time consumption and low in efficiency.
In summary, the prior art does not relate to a multi-core processing mechanism of an MD5 brute force cracking operation unit based on an FPGA hardware technology, nor does it relate to a multi-stage pipeline design idea of operating with a single-step operation; how to improve the computation rate and efficiency of MD5 brute force cracking, how to adopt a parallel processing mechanism of multi-core MD5 brute force cracking computation units, which is the key to improve the data processing rate and data throughput, and even more the bottleneck of improving the MD5 brute force cracking rate, is also a problem to be solved in the prior art.
Disclosure of Invention
The invention aims to solve the defects in the prior art and provides an MD5 brute force cracking system and method based on an FPGA.
According to the disclosed embodiment, the invention discloses an MD5 brute force system based on FPGA in the first aspect, the MD5 brute force system comprises an input interface unit, an N-core MD5 brute force operation unit and an output interface unit which are connected in sequence, wherein,
the input interface unit is connected with external controller equipment to realize communication between the FPGA and the controller, analyze and distribute messages sent by the controller and manage the N-core MD5 brute force cracking operation unit;
the N-core MD5 brute force cracking operation unit consists of N single-core MD5 brute force cracking operation units which are connected in parallel, a multi-core parallel processing mechanism is adopted, and each single core simultaneously generates a key in parallel, performs MD5 operation and then performs hash value matching to obtain matching results respectively;
the output interface unit is connected with external controller equipment, manages the cracking results of the N-core MD5 brute force cracking operation unit, performs message analysis and framing on the cracking results, successfully cracks and uploads the cracking results to the controller, and stops tasks; and if the cracking fails, uploading the data to the controller to wait for the starting of the next cracking of the task.
Further, the single-core MD5 brute force cracking operation unit comprises a key strategy generation module, an MD5 algorithm operation module, and a hash value matching module, which are connected in sequence, wherein,
the key strategy generation module realizes the combined generation of the keys with limited length according to the strategy issued by the controller;
the MD5 algorithm operation module comprises 4 rounds of operation of a main cycle, 16 times of operation in each round and 64 times of operation in total, and N-level pipeline processing is carried out on each operation, namely the MD5 single-step operation is realized by N-level pipeline processing;
the hash value matching module matches the data obtained by the MD5 algorithm operation module with the hash value to be cracked, the matching is successful, namely the corresponding key of the data is the cracked result, namely the cracking is successful, otherwise the cracking is failed.
Further, for different policy choices, the key combination generated by the key policy generation module may be a combination of numbers and special characters, numbers and upper and lower case letters, upper and lower case letters and special characters, pure numbers, pure letters, and pure characters.
According to the disclosed embodiment, the second aspect of the invention discloses an MD5 brute force cracking method based on an FPGA, wherein the MD5 brute force cracking method comprises the following steps:
the input interface unit is connected with external controller equipment to realize communication between the FPGA and the controller, and analyzes and distributes a message sent by the controller to the N-core MD5 brute force cracking operation unit;
the N-core MD5 brute force cracking operation unit is formed by connecting N single-core MD5 brute force cracking operation units in parallel, wherein a key strategy generation module in the single-core MD5 brute force cracking operation unit realizes the combined generation of keys with limited length according to a strategy issued by a controller;
an MD5 algorithm operation module in the single-core MD5 brute force cracking operation unit performs 4 rounds of operation of main cycle, each round of operation is performed for 16 times, 64 times of operation are performed totally, and N-level pipeline processing is performed on each operation, namely, the single-step operation of MD5 is realized by N-level pipeline processing;
a hash value matching module in the single-core MD5 brute force cracking arithmetic unit matches the data obtained by the MD5 arithmetic operation module with the hash value to be cracked, the matching is successful, namely the corresponding key of the data is the cracking result, namely the cracking is successful, otherwise the cracking is failed;
the output interface unit is connected with external controller equipment, manages the cracking results of the N-core MD5 brute force cracking operation unit, performs message analysis and framing on the cracking results, successfully cracks and uploads the cracking results to the controller, and stops tasks; and if the cracking fails, uploading the data to the controller to wait for the starting of the next cracking of the task.
Compared with the prior art, the invention has the following advantages and effects:
the method is based on the FPGA high-speed parallel processing capability, the single-step operation multi-level pipeline design idea and the multi-core parallel operation processing mechanism, and improves the core module data processing capability and the data operation throughput of the MD5 brute force cracking algorithm; compared with the traditional MD5 brute force cracking arithmetic unit which operates and calculates a first-level pipeline processing every time, the invention realizes 3-level pipelining every time of operation and calculation, namely, single-step operation and calculation of 3-level pipeline design, and improves the running clock frequency of the MD5 brute force cracking arithmetic unit, so that the higher the cracking rate in unit time is, the better the cracking efficiency is; compared with the traditional single-core MD5 brute force cracking design, the multi-core MD5 brute force cracking unit simultaneous parallel processing mechanism is designed, the cracking speed is improved by N times, and the cracking timeliness is stronger.
Drawings
FIG. 1 is a block diagram of an FPGA-based MD5 brute force cracking system disclosed in the present invention;
FIG. 2 is a block diagram of a single-core MD5 arithmetic operation unit module;
FIG. 3 is a key policy generation module flow diagram;
FIG. 4 is a flow chart of the MD5 algorithm module;
fig. 5 is a flow diagram of a hash value matching module.
Detailed Description
In order to make the objects, technical solutions and advantages of the embodiments of the present invention clearer, the technical solutions in the embodiments of the present invention will be clearly and completely described below with reference to the drawings in the embodiments of the present invention, and it is obvious that the described embodiments are some, but not all, embodiments of the present invention. All other embodiments, which can be derived by a person skilled in the art from the embodiments given herein without making any creative effort, shall fall within the protection scope of the present invention.
Example one
In the embodiment, the MD5 brute force cracking design based on the FPGA is realized, an FPGA hardware technology is used, a single-step operation multi-level pipeline design idea is adopted, and a multi-core MD5 brute force cracking operation unit parallel processing mechanism is adopted; for brute force cracking, the cracking speed is improved in unit time, and two schemes are mainly used for improving the cracking speed, wherein the running speed of the MD5 brute force cracking operation unit is improved, and the multi-core MD5 brute force cracking operation unit performs parallel processing; based on the two design ideas, the limitation of the MD5 algorithm operation on the FPGA running clock frequency is reduced to the maximum extent, namely the clock frequency of the FPGA for realizing the MD5 brute force algorithm operation is improved, and the design idea of a multi-core parallel processing mechanism is adopted, so that the MD5 brute force cracking speed is doubled, and the problem of low MD5 brute force cracking efficiency in the prior art is well solved.
As shown in fig. 1, the MD5 brute force cracking system based on FPGA disclosed in the present invention forms a block diagram to provide a brute force cracking design implementation of the MD5 based on FPGA, and a core part of the system is an N-core MD5 brute force cracking operation unit parallel processing mechanism. The single-core MD5 brute force cracking operation unit comprises a key strategy generation module, an MD5 algorithm operation module and a hash value matching module. The key strategy generation module completes the generation of the key combination with limited length, and the key length can support the maximum N bytes. The MD5 algorithm operation module comprises 4 rounds of main cycle operation, 16 times of operation in each round, 64 times of operation in total, and N-level pipeline processing is carried out on each operation, namely, the MD5 single-step operation is realized by N-level pipeline processing, so that the whole MD5 algorithm operation is carried out by 64 × N-level pipeline processing, and the design can improve the running clock frequency of the FPGA for realizing the MD5 algorithm operation.
The MD5 brute force cracking system based on the FPGA disclosed by the invention comprises: the device comprises an input interface unit, an N-core MD5 brute force operation unit and an output interface unit.
The external controller equipment is connected with the input interface unit to realize the communication between the FPGA and the controller; the input interface unit analyzes and distributes the messages sent by the controller and manages the N-core MD5 brute force cracking arithmetic unit.
The N-core MD5 brute force cracking operation units are connected in parallel by N single-core MD5 brute force cracking operation units and perform operation in parallel, the single cores are independent, and the operation speed is improved by N times compared with the single-core MD5 brute force cracking operation units.
The single-core MD5 brute force cracking operation unit mainly comprises: the system comprises a key strategy generation module, an MD5 algorithm operation module and a hash value matching module.
A key policy generation module: and realizing the combination generation of the keys with limited length according to the strategy issued by the controller, wherein for different strategy selections, the key combination can be all combinations of numbers and special characters, numbers and upper and lower case letters, upper and lower case letters and special characters, pure numbers, pure letters, pure characters and the like.
MD5 algorithm operation module: the bottleneck of brute force cracking is the cracking speed, and the improvement of the operation speed of the MD5 algorithm operation module is the core of design, so that each operation is performed by N-level pipeline processing, and the design greatly improves the operation speed of the MD5 algorithm operation.
A hash value matching module: the key generated by the key strategy generation module is sent to an MD5 algorithm operation unit, 4 32-bit a, b, c, d, 4 data are obtained through the operation of the MD5 algorithm operation unit module and are spliced into 128-bit data, the 128-bit data are matched with the hash value to be cracked, the matching is successful, namely the corresponding key of the data is a cracked result, namely the cracking is successful, or the cracking is failed.
An output interface unit: managing the cracking results of the N-core MD5 brute force cracking operation units, performing message analysis and framing on the cracking results, uploading the cracking results to the controller successfully, and stopping tasks; and if the cracking fails, uploading the data to the controller to wait for the starting of the next cracking of the task.
Example two
The embodiment discloses an MD5 brute force cracking system based on FPGA, which comprises: the device comprises an input interface unit, an 8-core MD5 brute force operation unit and an output interface unit.
The 8-core MD5 brute force cracking operation unit is formed by connecting 8 single-core MD5 brute force cracking operation units in parallel, wherein the single-core MD5 brute force cracking operation unit is a core for realizing the operation of an MD5 brute force cracking system, and the most important is to design and realize the operation of an MD5 algorithm.
In this embodiment, a pipeline design concept is adopted for MD5 brute force cracking based on the FPGA, a single-core MD5 brute force cracking operation unit is connected to all pipeline designs in parallel, and a multi-stage pipeline design is adopted for single-step MD5 operation, so that the running clock frequency of the MD5 algorithm operation implemented by the FPGA is increased, the running clock frequency of the MD5 algorithm designed by the present invention in the FPGA is 250MHz, and the following is mainly implemented:
a key policy generation module: and generating a key according to the parameters of the character set, the length of the character set, the sequence of the character set, the length of the key, the initial sequence bit of the key and the like issued by the controller and according to a strategy. For example, a 123abc key is a combination of digits and letters of the key length 6 bits, and a &% abs key is a combination of letters and characters of the key length 6 bits; the key policy generation module runs a clock frequency of 250MHz, i.e., produces 2.5 hundred million keys per second. For example, a key length of 8, a character set length of 10, and a character set of arabic numerals, the range of keys generated is 00000000 to 99999999, for a total of 1 hundred million keys.
The MD5 algorithm operation module adopts 4 rounds of main cycle operation, 16 times of operation in each round and 64 times of operation in total, 3-level pipeline processing is carried out in each operation in order to improve the clock rate of the MD5 algorithm in FPGA operation, namely 3-level pipeline processing is designed through single-step operation, 48-level pipeline processing is carried out in each 16 rounds of operation of the MD5, 192-level pipeline processing is totally counted in 4 rounds of the MD5 algorithm, the clock frequency of the MD5 algorithm in FPGA operation is improved, and the time sequence of the FPGA running MD5 algorithm is guaranteed not to be violated. The designed FPGA runs at a clock frequency of 250MHz, so that the cracking rate of the single-core MD5 brute force cracking operation unit is 2.5 hundred million times/s.
In order to match the clock frequency of FPGA operation, the clock frequency of three sub-modules of the MD5 brute force operation unit is 250MHz, so that the matching rate of the hash value matching module is 2.5 hundred million times/s, namely 2.5 hundred million times of keys are matched per second. The hash value matching module directly discards the result of the matching failure, and the result of the matching success is directly reported to the output interface unit. For the same task, the hash value matching module generates at most 2 useful messages, one is matching success, and the other is key matching traversal completion, so that the output data volume of the hash value matching module is small.
The speed of the single-core MD5 brute force cracking unit is improved, and the cracking efficiency is improved; the multi-core system further improves the cracking efficiency of MD5 brute force cracking. Therefore, the 8-core MD5 brute force cracking operation unit module is designed to perform parallel operation processing simultaneously, 8 cores are independent, the speed of the 8-core MD5 brute force cracking operation unit is 8 times that of a single-core MD 3526 brute force cracking operation unit, the speed of the single-core MD5 brute force cracking operation unit is 2.5 hundred million times/s, and the speed of the 8 cores is 20 hundred million times/s; for a 10-bit key combined by pure numbers, 100 hundred million key traversals are completed within 5 seconds, the MD5 brute force cracking efficiency is greatly improved, and the MD5 brute force cracking time is reduced.
The clock of the MD5 algorithm implemented by the FPGA of this embodiment is 250MHz, the bit width of the input data of the MD5 algorithm is 512 bits, and the data processing and data throughput of the MD5 algorithm operation of the 8-core FPGA is up to 128GB, that is, the data processing reaches 128 gbytes in 1 second, which shows that the data processing capability of this embodiment in unit time is extremely strong.
In the actual cracking situation, the simple keys are basically cracked in seconds, compared with the existing MD5 cracking technology, the time of MD5 brute force cracking is reduced by thousands of times, and the cracking efficiency is greatly improved.
EXAMPLE III
The embodiment provides an MD5 brute force cracking method based on the FPGA based MD5 brute force cracking system disclosed in the above embodiment, and the MD5 brute force cracking method includes the following steps:
the input interface unit is connected with external controller equipment to realize communication between the FPGA and the controller, and analyzes and distributes a message sent by the controller to the N-core MD5 brute force cracking operation unit;
the N-core MD5 brute force cracking operation unit is formed by connecting N single-core MD5 brute force cracking operation units in parallel, wherein a key strategy generation module in the single-core MD5 brute force cracking operation unit realizes the combined generation of keys with limited length according to a strategy issued by a controller;
an MD5 algorithm operation module in the single-core MD5 brute force cracking operation unit performs 4 rounds of operation of main cycle, each round of operation is performed for 16 times, 64 times of operation are performed totally, and N-level pipeline processing is performed on each operation, namely, the single-step operation of MD5 is realized by N-level pipeline processing;
a hash value matching module in the single-core MD5 brute force cracking arithmetic unit matches the data obtained by the MD5 arithmetic operation module with the hash value to be cracked, the matching is successful, namely the corresponding key of the data is the cracking result, namely the cracking is successful, otherwise the cracking is failed;
the output interface unit is connected with external controller equipment, manages the cracking results of the N-core MD5 brute force cracking operation unit, performs message analysis and framing on the cracking results, successfully cracks and uploads the cracking results to the controller, and stops tasks; and if the cracking fails, uploading the data to the controller to wait for the starting of the next cracking of the task.
To sum up, the MD5 brute force cracking system and method disclosed in the above embodiments fully utilize the multi-core parallel processing mechanism and the multi-stage pipeline processing thought of single-step operation, improve the speed of the single-core MD5 brute force cracking operation unit, and the design of the multi-core MD5 brute force cracking operation unit parallel operation processing mechanism, improves the efficiency of MD5 brute force cracking by times, reduces the time of MD5 brute force cracking, and well solves the problems of long time consumption and low efficiency of MD5 brute force cracking in the prior art.
The above embodiments are preferred embodiments of the present invention, but the present invention is not limited to the above embodiments, and any other changes, modifications, substitutions, combinations, and simplifications which do not depart from the spirit and principle of the present invention should be construed as equivalents thereof, and all such changes, modifications, substitutions, combinations, and simplifications are intended to be included in the scope of the present invention.