CN105933120A - Spark platform-based password hash value recovery method and device - Google Patents

Abstract

The invention discloses a Spark platform-based password hash value recovery method and device. The design method includes a rainbow table data generation step and a rainbow table decryption step. According to the method, the first-of-chain node value of each rainbow chain is recorded as an SV (Start Value), and the last-of-chain node value of each rainbow chain is recorded as an EV (End Value); based on the processing capability of the Spark platform for large-scale data, a map function is utilized to effectively calculate EV corresponding to SV, so that rainbow chains can be generated, and are stored in an HDFS (Hadoop distributed file system), and rainbow table data generation is completed; and a filter function is utilized to find all SV corresponding to a ciphertext to be decrypted, and a foreach function is called to generate complete rainbow chains according to each SV, and the ciphertext can be decrypted.

Description

A password hash value recovery method and device based on Spark platform

technical field

The invention belongs to the technical field of network information security and the technical field of password reverse recovery in cryptography, and in particular relates to a password hash value recovery method and device based on a Spark platform.

Background technique

In order to ensure the non-tamperable modification of the security attribute of the data information, the plaintext of the password is usually not stored directly, but the hash value corresponding to the plaintext of the password after the hash operation is stored. Hash algorithm, also known as hash algorithm, converts plaintext input of any length into fixed-length hash value output through cryptographic modules such as permutation and confusion, and has a good one-way property, which cannot be easily reversed from the output. Input, due to the good confidentiality and verification functions of the hash function, it is widely used in applications such as digital signatures, download verification, and password storage.

Methods for cracking password hash values include brute force method and dictionary lookup method. The brute force method is feasible for simple passwords and simple cryptosystems, but for complex passwords and cryptosystems, an infinite dictionary will be generated. Therefore, a large amount of computing time is required; while the dictionary lookup method requires a large amount of storage space, and the decryption cost is too high.

In order to reduce the size of the required dictionary and reduce the time for generating and looking up the dictionary, the prior art provides a solution for collision chains—rainbow table, which is based on Martin Hellman theory (weight theory based on memory and time). The rainbow table is a compromise between brute force exhaustion and dictionary lookup. It reduces the time spent on password recovery through pre-computation. Its core idea is to map the hash value calculated by plaintext back to plaintext space by a mapping function, and then Alternately compute plaintext and hash values to reduce hashed password recovery time.

Spark is an open source cluster computing framework originally developed by AMPLab at the University of California, Berkeley. Compared with Hadoop's MapReduce, which will store the intermediary data in the disk after running the work, Spark uses the in-memory computing technology, which can analyze and calculate in the memory before the data is written to the hard disk. The calculation speed of Spark running programs in the memory can be 100 times faster than that of Hadoop MapReduce. Even when running programs on the hard disk, Spark can also be 10 times faster. The basic data structure of Spark is RDD, and the Spark platform encapsulates operations in transformation and action, where transformation is the transformation of RDD, and action is the calculation of RDD. Call the API in the transformation action, and the Spark platform will perform distributed computing on its own. Programmers only need to configure Spark without considering how the distribution is performed, which greatly reduces the threshold for using the platform.

Contents of the invention

In order to overcome the shortcomings of the above-mentioned prior art, the object of the present invention is to provide a password hash value recovery method and device based on the Spark platform, which can realize parallel generation of large-capacity rainbow tables, parallel filtering of rainbow chains and parallel decryption of rainbow chains, It has the advantages of high performance and low threshold.

In order to achieve the above object, the technical scheme adopted in the present invention is:

Use the Spark platform for distributed parallel generation of rainbow tables and decryption. In the process of generating the rainbow table, it is necessary to generate its corresponding chain tail node value based on all randomly generated chain head node values. Using the map function of the Spark platform, each chain head node can be independently operated, that is to say, the generation of the rainbow table can be highly parallelized, which greatly improves the generation efficiency. The rainbow table is stored in blocks in HDFS. By calling the filter function of the Spark platform, the rainbow chain corresponding to the ciphertext to be decrypted can be found from each block in parallel, which greatly speeds up the speed of text matching. Using the foreach function of the Spark platform, the plaintext corresponding to the ciphertext to be decrypted can be calculated from the rainbow chain in parallel.

Specifically, the technical scheme of the present invention is:

A password hash value recovery method based on the Spark platform, comprising a rainbow table data generation step and a rainbow table decryption step, characterized in that,

Assume that the number of rainbow chains is S, the length is L, and L>1, then the steps of generating rainbow table data include:

Step A: randomly generate S chain head node values SV according to the character set;

Step B: According to the generation rules of the rainbow chain, calculate the chain tail node value EV corresponding to the chain head node value SV;

Step C: saving all generated (SV, EV) tuples in the Hadoop distributed file system HDFS;

The steps of decrypting the rainbow table include:

Step D: read the rainbow table from HDFS;

Step E: Filter out the rainbow chain corresponding to the ciphertext from the rainbow table;

Step F: Calculate the plaintext corresponding to the ciphertext according to the obtained rainbow chain;

Specifically, the calculation of the chain tail node value EV includes the following steps:

Step B1: Execute the f function L-1 times for each chain head node value SV to generate L-2 intermediate nodes and a chain tail node; the f function includes two parts, the H function and the R function; the H function is the specified Encryption function, the R function is a function related to the current node position i (1≤i≤L-1), the definition domain and value range of this function need to be opposite to the H function; in this paper, R _i is used to represent the R function with parameter i, f _i represents the combination of the H function and the R _i function; R _i = (X+i) mod N (wherein X represents the character string processed by the H function, and N represents the scope of the plaintext); Step B2: call the Spark platform The map function executes step B1 in parallel.

Filtering out the rainbow chain corresponding to the ciphertext in the rainbow table includes the following steps:

Step E1: Guess the position i of the plaintext corresponding to the ciphertext to be decrypted in the rainbow chain, and try sequentially from L-1 to 1;

Step E2: Execute the R _i function on the ciphertext, save the result in the intermediate node M; then execute f _i+1 , f _i+2 , ..., f _L-1 on M, and assign the result to M;

Step E3: Call the filter function of the Spark platform to filter out all rainbow chains whose tail node value is equal to M in parallel. If there is no rainbow chain whose chain tail node value is equal to M in the rainbow table, try the next i; if all attempts fail If a rainbow chain that meets the requirements is found, the decryption fails; if there is a rainbow chain whose tail node value is equal to M, then enter the next step.

Calculating the plaintext according to the rainbow chain includes the following steps:

Step F1: Obtain the position i of the plaintext corresponding to the ciphertext in the rainbow chain from step E, execute f ₁ , f ₂ ,...,f _i-1 on the chain head node value SV of the rainbow chain, and the obtained result is is the plaintext corresponding to the ciphertext.

The present invention simultaneously proposes a password hash value recovery device based on the Spark platform, including a Spark configuration unit, a rainbow table data generation unit and a rainbow table decryption unit, wherein:

The Spark configuration unit executes the preparation work of the recovery device, and configures the computing power provided by the Spark platform;

The rainbow table data generation unit generates a collection of several rainbow chains, and each rainbow chain is calculated through a series of hash operations and mapping functions iteratively. The rainbow table data generation unit only needs to store the chain head node and the chain tail node;

The rainbow table decryption unit guesses the location of the plaintext corresponding to the ciphertext to be decrypted, and searches for the chain tail node corresponding to the ciphertext; then finds the rainbow chain whose chain tail node is the same as the chain tail node corresponding to the ciphertext in the rainbow table, Calculate the plaintext corresponding to the ciphertext based on these rainbow chains.

Specifically, the preparation of the Spark configuration unit mainly includes:

Build the Spark platform, configure the Master and Slave, and then configure the number and size of Workers.

Described rainbow table data generation unit execution function mainly comprises:

Randomly generate S chain head node values, and then calculate the chain tail node value corresponding to the chain head node value according to the rainbow chain generation rules, and call the map function of the Spark platform to store the calculation results in the Hadoop distributed file system HDFS.

Described rainbow table decryption unit executive function mainly comprises:

Guess the position i of the plaintext corresponding to the ciphertext to be decrypted in the rainbow chain, execute the R _i function on the ciphertext, and save the result in the intermediate node M; then execute f _i+1 , f _i+2 ,..., _If If there is no rainbow chain whose tail node value is equal to M in the rainbow table, try the next i; if all attempts fail to find a rainbow chain that meets the requirements, the decryption fails; if there is a rainbow chain whose tail node value is equal to M, call The foreach function of the Spark platform calculates the plaintext corresponding to the ciphertext for each rainbow chain.

Compared with the prior art, the beneficial effect of the present invention is that the efficiency of generating and decrypting the rainbow table is greatly improved by utilizing the high-efficiency calculation in the memory of the Spark platform and its highly parallel characteristics.

Description of drawings

Fig. 1 is a flowchart of a password hash value recovery method based on the Spark platform.

Fig. 2 is a flow chart of generating a rainbow table part based on the Spark platform password hash value recovery method.

Fig. 3 is a flow chart of the decryption part of the ciphertext to be decrypted based on the Spark platform password hash value recovery method.

Fig. 4 is a functional block diagram of a password hash value recovery device based on the Spark platform.

Fig. 5 is a functional block diagram of the rainbow table generation unit of the password hash value recovery device based on the Spark platform.

Fig. 6 is a functional block diagram of the decryption unit of the password hash value recovery device based on the Spark platform.

detailed description

The implementation of the present invention will be described in detail below in conjunction with the drawings and examples.

Spark is a common Hadoop MapReduce-like parallel computing framework open sourced by UC Berkeley AMP lab. Spark implements distributed computing based on the map reduce algorithm and has the advantages of Hadoop MapReduce. In addition, the intermediate output and results of Spark tasks can be stored in memory, which can speed up the read and write efficiency of calculations. RDD is the most basic abstraction of Spark. It is an abstract use of distributed memory and realizes the abstract implementation of operating distributed data sets in the way of operating local collections.

RDD is the core of Spark. It represents a partitioned, immutable data set that can be operated in parallel. Different data set formats correspond to different RDD implementations. RDD must be serializable. RDD can be cached in the memory, and the result of each operation on the RDD data set can be stored in the memory, and the next operation can be directly input from the memory, which saves a lot of disk IO operations of MapReduce.

The present invention utilizes the memory calculation and high parallelism of the Spark platform, uses RDD as an intermediate result, and efficiently realizes the generation and decryption of the rainbow table. Specifically, a password hash recovery method based on the Spark platform of the present invention includes three steps as shown in FIG. 1 .

Step1, configure the Spark platform parameters, mainly including building the Spark platform, configuring the Master and Slave of the Spark platform (that is, configuring how many hosts the Spark platform controls) and configuring the number and size of Workers on the Spark platform (that is, configuring the number of worker threads that each host has. and the size of memory and CPU available to each thread).

Step2, generate a rainbow table.

Step3, decrypt the ciphertext to be decrypted.

Specifically, the generation steps of the rainbow table include (see Figure 2, assuming that the size of the rainbow table is S, the length of each rainbow chain is L (L>1), the value of the first node of the rainbow chain is SV (Start Value), and the chain The end node value is EV(End Value)):

Step 21. Randomly generate S SVs of the first node of the rainbow chain and save them in the list list.

Step 22. According to the generation rules of the rainbow chain, use each SV in the list as the first node value of the rainbow chain to calculate the chain tail node value EV, call the map function in the transformation operation of Spark, and convert all (SV, EV) tuples Generate RDD datasets.

Step 23, save the RDD dataset in HDFS.

The decryption steps of the rainbow table include (see Figure 3):

Step 31, read the rainbow table from HDFS.

Step 32. Guess the position i of the plaintext corresponding to the ciphertext, execute the R _i function on the ciphertext, and save the result in the intermediate node M.

Step 33. Execute f _i+1 , f _i+2 , ..., f _L-1 on M, and assign the result to M.

Step 34. Filter out the rainbow chain whose tail node value EV is equal to M from the rainbow table.

The specific steps of Step 32～Step34 are as follows:

Initialize i as L-1;

Execute the R _i function on the ciphertext to be decrypted to obtain the intermediate node M;

Let j=i+1;

If j≤L-1, execute H function and R _j+1 function on M, assign the result to M, and go to (5); otherwise, go to (6);

Make j=j+1, go to (4);

Call the filter function in Spark's transformation operation to filter out all SVs whose EV is equal to M from the rainbow table. If the quantity of SV is equal to 0, then make i=i-1, if i>0, then go to (2), if i=0, otherwise decryption fails; if the quantity of SV is greater than 0, then enter next step;

Step 35. Call the foreach function in Spark's action operation, and execute f1, f2, ..., fi-1 for each qualified rainbow chain chain first node value SV, and the result obtained is the corresponding plaintext.

The present invention simultaneously proposes a password hash recovery device based on the Spark platform, including 3 units as shown in Figure 4, a Spark configuration unit, a rainbow table generation unit and a decryption unit.

Among others, the functions performed by the Spark hive include:

Build the Spark platform, configure the Master and Slave, and configure the number and size of Workers.

As shown in Figure 5, the functions performed by the rainbow table generation unit include:

Chain head node generation unit, which is used to randomly generate S chain head nodes and ensure that the nodes are not repeated.

Chain tail node calculation unit, which calculates the chain tail node value corresponding to the chain head node value according to the rainbow chain generation rules, and calls the map function of the Spark platform to store the calculation results in the Hadoop distributed file system HDFS

As shown in Figure 6, the functions performed by the decryption unit include:

The calculation unit of the chain tail node corresponding to the ciphertext, which guesses the position i of the plaintext corresponding to the ciphertext to be decrypted in the rainbow chain, executes the R _i function on the ciphertext, saves the result in the intermediate node M, and then executes f _i+1 , f _i+2 , ..., f _L-1 , assign the result to M, and get the chain end node corresponding to the ciphertext.

Rainbow chain filtering unit, which calls the filter function of the Spark platform to filter out the rainbow chain whose chain tail node is equal to the chain tail node corresponding to the ciphertext from the rainbow table.

Generate a plaintext unit, which calls the foreach function of the Spark platform to calculate the plaintext corresponding to the ciphertext for each rainbow chain.

A kind of based on Spark platform password hash recovery method and device provided by the present invention has been introduced in detail above, the principle and specific implementation of the present invention have been set forth in this paper, the above detailed steps are used to help understand the method and method of the present invention core idea; at the same time, for those skilled in the art, according to the idea of the present invention, there will be changes and improvements in specific implementation methods, and these changes and improvements all belong to the protection scope of the present invention.

Claims (8)

1. A password hash value recovery method based on Spark platform, comprising rainbow table data generation step and rainbow table decryption step, is characterized in that, Assume that the number of rainbow chains is S, the length is L, and L>1, then the steps of generating rainbow table data include: Step A: randomly generate S chain head node values SV according to the character set; Step B: According to the generation rules of the rainbow chain, calculate the chain tail node value EV corresponding to the chain head node value SV; Step C: saving all generated (SV, EV) tuples in the Hadoop distributed file system HDFS; The steps of decrypting the rainbow table include: Step D: read the rainbow table from HDFS; Step E: Filter out the rainbow chain corresponding to the ciphertext from the rainbow table; Step F: Calculate the plaintext corresponding to the ciphertext according to the obtained rainbow chain. 2. the password hash value recovery method based on Spark platform according to claim 1, is characterized in that, the calculation of described chain tail node value EV comprises the following steps: Step B1: Execute the f function L-1 times for each chain head node value SV to generate L-2 intermediate nodes and a chain tail node; the f function includes two parts, the H function and the R function; the H function is the specified Encryption function, the R function is a function related to the current node position i (1≤i≤L-1), the definition domain and value range of this function need to be opposite to the H function; use R _i to represent the R function with parameter i, f _i represents the combination of the H function and the R _i function; make R _i =(X+i) mod N, where X represents the character string processed by the H function, and N represents the scope of the plaintext; Step B2: call the map function of the Spark platform to execute step B1 in parallel. 3. according to the described password hash value recovery method based on Spark platform of claim 2, it is characterized in that, filtering out the rainbow chain corresponding to ciphertext in the described rainbow table comprises the following steps: Step E1: guess the position i of the plaintext corresponding to the ciphertext to be decrypted in the rainbow chain, and try from L-1 to 1 in turn; Step E2: Execute the R _i function on the ciphertext, save the result in the intermediate node M; then execute f _i+1 , f _i+2 , ..., f _L-1 on M, and assign the result to M; Step E3: Call the filter function of the Spark platform to filter out all rainbow chains whose tail node value is equal to M in parallel. If there is no rainbow chain whose chain tail node value is equal to M in the rainbow table, try the next i; if all attempts fail If a rainbow chain that meets the requirements is found, the decryption fails; if there is a rainbow chain whose tail node value is equal to M, then enter the next step. 4. the password hash value recovery method based on Spark platform according to claim 3, is characterized in that, calculates plaintext according to rainbow chain and comprises the following steps: Step F1: Obtain the position i of the plaintext corresponding to the ciphertext in the rainbow chain from step E, execute f ₁ , f ₂ ,...,f _i-1 on the chain head node value SV of the rainbow chain, and the obtained result is is the plaintext corresponding to the ciphertext. 5. a password hash value recovery device based on Spark platform, is characterized in that, comprises Spark configuration unit, rainbow table data generation unit and rainbow table decryption unit, wherein: The Spark configuration unit executes the preparation work of the recovery device, and configures the computing power provided by the Spark platform; The rainbow table data generation unit generates a collection of several rainbow chains, and each rainbow chain is calculated through a series of hash operations and mapping functions iteratively. The rainbow table data generation unit only needs to store the chain head node and the chain tail node; The rainbow table decryption unit guesses the location of the plaintext corresponding to the ciphertext to be decrypted, and searches for the chain tail node corresponding to the ciphertext; then finds the rainbow chain whose chain tail node is the same as the chain tail node corresponding to the ciphertext in the rainbow table, Calculate the plaintext corresponding to the ciphertext based on these rainbow chains. 6. according to the described password hash value recovery device based on Spark platform of claim 5, it is characterized in that, the preparatory work of described Spark configuration unit mainly comprises: Build the Spark platform, configure the Master and Slave, and then configure the number and size of Workers. 7. the password hash value recovery device based on Spark platform according to claim 5, is characterized in that, Described rainbow table data generation unit execution function mainly comprises: Randomly generate S chain head node values, and then calculate the chain tail node value corresponding to the chain head node value according to the rainbow chain generation rules, and call the map function of the Spark platform to store the calculation results in the Hadoop distributed file system HDFS. 8. according to the described password hash value recovery device based on Spark platform of claim 5, it is characterized in that, described rainbow table deciphering unit execution function mainly comprises: Guess the position i of the plaintext corresponding to the ciphertext to be decrypted in the rainbow chain, execute the R _i function on the ciphertext, and save the result in the intermediate node M; then execute f _i+1 , f _i+2 ,..., _If If there is no rainbow chain whose tail node value is equal to M in the rainbow table, try the next i; if all attempts fail to find a rainbow chain that meets the requirements, the decryption fails; if there is a rainbow chain whose tail node value is equal to M, call The foreach function of the Spark platform calculates the plaintext corresponding to the ciphertext for each rainbow chain.