See discussions, stats, and author profiles for this publication at: [Link]
net/publication/221611105
Cryptanalysis of Hash Functions Using Advanced Multiprocessing.
Conference Paper · January 2010
Source: DBLP
CITATION READS
1 217
6 authors, including:
Julio Gómez Francisco G. Montoya
Universidad de Almería Universidad de Almería
193 PUBLICATIONS 1,462 CITATIONS 130 PUBLICATIONS 2,609 CITATIONS
SEE PROFILE SEE PROFILE
Consolación Gil Alfredo Alcayde
University of Almería CEIA3 Universidad de Almería
105 PUBLICATIONS 3,136 CITATIONS 68 PUBLICATIONS 1,581 CITATIONS
SEE PROFILE SEE PROFILE
Some of the authors of this publication are also working on these related projects:
VALOR DEL ETEST View project
ANTIBIÓTICOS. REVISIÓN. View project
All content following this page was uploaded by Francisco G. Montoya on 27 June 2014.
The user has requested enhancement of the downloaded file.
CRYPTANALYSIS OF HASH FUNCTIONS
USING ADVANCED MULTIPROCESSING
Gómez J., Montoya F.G., Benedicto R., Jimenez A., Gil C. and Alcayde A.
University of Almeria, Spain
{jgomez, pagilm, rbenedicto, ajimenez, cgilm, aalcayde}@[Link]
Abstract. Every time it is more often to audit the communications in companies to
verify their right operation and to check that there is no illegal activity. The main
problem is that the tools of audit are inefficient when communications are
encrypted.
There are hacking and cryptanalysis techniques that allow intercepting and
auditing encrypted communications with a computational cost so high that it is not
a viable application in real time.
Moreover, the recent use of Graphics Processing Unit (GPU) in high-performance
servers is changing this trend.
This article presents obtained results from implementations of brute force attacks
and rainbow table generation, sequentially, using threads, MPI and CUDA. As a
result of this work, we designed a tool (myEchelon) that allows auditing encrypted
communications based on the use of hash functions.
Keywords: CUDA, MPI, hash, audit tools, rainbow tables, brute force.
1 Introduction
From its origins computing has revolutionized the way in which companies
communicate, coming to play an important role in their success. The constant
emergence of new technologies and the ability to interconnect through networks
gives significant improvements in productivity and business market. This has
great benefits but also new challenges. The most important challenge is the
computer security [1].
Given the importance of computer systems, laws and standards have been
provided to regulate the use and transmission of information. For example, in
Spain we can find the Data Protection Act [2], while at international level we can
2
find the ISO 1799/BS [3] and ISO / IEC 27001 [4]. All these legal advances,
together with the increased complexity of computer systems have caused an
increment of computer security audits.
An audit of computer security [5] allows to check the security level of a
computer system using all kinds of tools and techniques for finding the problems
and weaknesses. To make a security audit is necessary to use a large set of tools to
easily audit unencrypted communications. Therefore, the main challenge and
objective of this work is to create an auditing tool that allows encrypted
communications audit based on the use of hash functions.
For that, in section two, we analyze the attacks on hash functions. Section three
explains how to use the hash functions attacks on MyEchelon to audit encrypted
communications. In sections four and five we analized the results of implementing
the brute force attacks and generation of rainbows table using different
technologies multiprocessing to provide greater power to MyEchelon.
2 Criptoanalysis of hash functions
One of the great allies of computer security is cryptography. A clear example is
the use of hash functions, which we can find in communications, to check the
passwords, to verify the integrity of messages, etc.
A hash function allows to calculate the trace (the summary) that uniquely
identifies a particular set of data. Table 1 shows the characteristics of the most
important hash functions: MD5 [6], SHA-1 [7] and NTLM/MD4 [8].
MD5 SHA1 NTLM / MD4
Summary size 128 bits 160 bits 128 bits
Block size 512 bits 512 bits 512 bits
Number of steps 64 80 48
Message size ∞ ∞ ∞
128 160
Strength preimage 2 2 2128
Table 1 Comparative Hash functions
The scientific community began to question about the security provided by the
hash functions when Xiaoyun Wang [9] published the first results on the breaking
of the MD5 hash function and Antoine Joux [10] demonstrated vulnerabilities in
the SHA-0 hash function.
The classical way to break the hash functions is to use brute force attacks [11]
that consists on generating all possibles solutions until you find the right one. This
implies a high computational cost for large and complex passwords. For that, it
becomes necessary to find an efficient solution to this problem. This solution was
found in the use of tables Rainbow [12] that is an elegant solution from the known
hash tables [13] created by Martin Hellman, avoiding as far as possible the large
3
number of collisions inherited from his predecessor. The disadvantage of both
techniques is that they have a very high computational cost, making unfeasible its
use in conventional equipments.
3 myEchelon
MyEchelon is created with the aim to automate the audit process of a system
using a large set of tools. When myEchelon runs, it analyzes and takes control of
the network where you are. Once the network scans, it carries out an attack Man
In The Middle to the networks devices to audit communications (see Figure 1).
Logically, unencrypted communications can be audited but the problem is the
encrypted communications.
hash
password
Audited
comunication
Fig. 1. Architecture of a network auditing myEchelon
To allow auditing the encrypted communications, myEchelon uses a high
performance server which will be responsible for making the crypto-analysis (see
Figure 1).
As we will see, the brute force attacks can audit https secure communications
and the use of rainbow tables allows obtaining the passwords that are transmitted
over the network.
To improve the performance of cryptanalysis it is going to be compared brute
force attacks and generating rainbow tables sequentially, using threads [14], MPI
[15] and using Graphics Processors Unit (GPU) using CUDA [16].
All results have been obtained on the server MX DUAL AZServer Xenon and
NVIDIA TESLA 1070. The server has two processors Dual / Quad Core Intel
Xenon 2.66 GHz, 8 2Gb SDRAM and two SATA hard drives of 1TB in RAID 1.
Moreover, the TESLA team has four cards tesla 1070 T10, which makes a total of
960 cores of 1.44 GHz each.
4
4 Brute force using advanced multiprocessing
Basically, this type of cryptanalysis is based on the birthday attack [17]. This
attack is that given a hash m, it has to find a text M´ whose value Hash (M´) is
equal to the original hash (m).
For example, in the case of SHA1 (160 bits), this attack requires to generate
280 tests to obtain the solution.
One application of this cryptanalysis is the forgery of certificates https secure
communications. An https security certificate is composed by a series of data that
identifies the server (e.g. name, domain) that are signed by a certification
authority. To ensure the integrity of the digital certificate is used a digital
signature algorithm, which in the case of https certificate is the MD5 hash
function.
To audit the https encrypted communications is necessary to generate a
certificate in real time so that the signature of the certificate is the same than the
original. In this sense, Arjen Lenstra [18] demonstrated the creation of two X.509
certificates with different public keys and the same MD5 hash value. Thus, it is
possible to modify an original certificate and find a collision to allow the new
certificate had the same hash value. The process is computationally expensive
because it must test a great set of solutions to obtain a collision.
We implemented the brute force attack using different multiprocessing
technologies for different hash functions. As an example, Figure 2 shows the
comparative on the performance of different technologies to generate the brute
force attack for the MD5 hash function. If we analyze the results we can see that
CUDA has the best performance with more than 135 millions hash/sec. However,
as happens to MPI, it needs a time to start the system which penalizes the
generation of a small number of hashes.
3 4 5 6 7 8 9
10 10 10 10 10 10 10
Fig. 2. Generation MD5 Hash
If we compare the results between the perfomance of different implementations
with respect to the sequential implementation (see Figure 3 and Table 2), we see
5
that the use of threads and MPI represents a better performance of 780% and
CUDA provides the best results with a performance of 4410% over its sequential
implementation.
6000%
5000%
Avg Perfomance
4000%
3000% Threa ds
MPI
2000%
CUDA
1000%
0%
MD5 SHA1 NTLM
Hash Function
Fig. 3. Comparison of performance on the brute force attack
MD5 SHA1 NTLM
Threads 806% 769% 764%
MPI 792% 766% 781%
CUDA 5222% 4046% 3962%
Table 2. Perfomance on the brute force attack
5 Rainbow Tables using advanced multiprocessing
The use of Rainbow Tables is the fastest way to make brute force attacks. For
the use of Rainbow Tables it has been used Rainbow-Crack project [19]. The
process of breaking a hash consists of three phases: generation of tables (rigen), to
put order in the tables (rtshort) and use of ordered tables to obtain the value of a
given hash (rtcrack). The first two steps should be performed once, while the third
step is repeated for each of the hash that we want to break.
The main problem is that the required size and the time for generating tables
are related exponentially to the size of the password that you want to analyze. For
example, to generate a rainbow table that enables to break an alphanumeric
password of seven character is necessary to generate a table of 2Gb for what it
would be necessary about three days. To decrypt passwords of nine characters we
need 500 tables of 2Gb and it would take about three years.
6
Basically, a rainbow table is composed of a set of vector data. The generation
of each vector can be done completely independently and for this, as it is shown in
Figure 4, it is necessary to use mainly three functions: 1) IndexToPlain is
responsible for converting a numerical value to a string belonging to the set of
possible values 2) PlainToHash is the most important function since it is
responsible for calculating the hash of the string above, 3) HashTolndex converts
the hash value to a numeric value.
While (chain_num)
While (chain_len)
Generate Save Save
IndexToPlain PlainToHash HashToIndex
Index Index Index
Fig. 4. Rainbow Tables Generation sequentially
If we analyze the processing time we can observe that PlainToHash function
represents a 44.58% of the time, IndexToPlain a 15.75%, HashTolndex a 8.27%
and the 31.6% left is used in various operations reading and writing.
The parallelization of the generation of Rainbow Tables has been made taking
into account the characteristics of each technology.
In the case of threads and MPI parallelization is easy and can be calculated
separately each of vector in the table. But in CUDA case parallelization is more
complicated because CUDA does not allow operations W/R and therefore it
generates a CPU thread for each vector. To complete the calculations on the GPU
functions have been implemented PlainToHash, IndexToPlain and HashTolndex
in CUDA. Thus, the CPU thread is responsible for carrying out the operations
W/R and GPUs performs the calculations.
Figure 5 shows the results obtained by different technologies of
multiprocessing. In this case, the use of threads and MPI represents a perfomance
of 783% close to the ideal one while CUDA is much lower than the sequential
implementation.
The CUDA implementation for the generation of tables Rainbows presents the
worst results. It is produced as it makes a continuous movement of data between
the CPU and the GPU system.
7
900%
800%
700%
600%
Perfomance
500%
Threads
400%
MPI
300%
200% CUDA
100%
0%
MD5 SHA1 NTLM
Hash Function
Fig. 5. Performance Comparison in Rainbow Tables generation
MD5 SHA1 NTLM
Threads 765% 780% 770%
MPI 800% 797% 787%
CUDA 78% 36% 33%
Table 3. Comparasion in Rainbow Tables generation
6 Conclusions
This article presents the results of the implementation of brute force attacks and
Rainbow Tables generation, so sequential, using threads, MPI, CUDA. Finally, we
can say that CUDA has the best technology in brute force attacks while MPI
presents the best results in the generation of tables Rainbow.
These results have been applied to myEchelon allowing intercepting and
auditing encrypted communications using in each case the best multiprocessing
technology.
7 Acknowledgements
This work has been financed by the Excellence Project of Junta de Andalucia
(P07-TIC02988), in part financed by the European Regional Development Fund
(ERDF).
8
8 References
[1] Julio Gómez López, Raúl Baños Navarro. Seguridad en Sistemas Operativos Windows y
Linux. Ra-Ma. 2006.
[2] Ley orgánica 15/1999, de 13 de diciembre, de Protección de datos de Carácter Personal.
1999.
[3] Mike Kenning. Security Management Standard — ISO 17799/BS 7799. Springer
Netherlands. 2001.
[4] Estándar Internacional ISO/IEC 27001. 2005.
[5] K.K. Mookhey, Nilesh Burghate. Linux - Security, Audit and Control Features. ISACA.
2005.
[6] R. Rivest. The MD5 Message-Digest Algorithm. Network Working Group. Abril 1992.
[Link]
[7] D. Eastlake, P. Jone. US Secure Hash Algorithm 1 (SHA1). Network Working Group.
Septiembre 2001. [Link]
[8] R. Rivest. The MD4 Message-Digest Algorithm. Network Working Group. Abril 1992.
[Link]
[9] Xiaoyun Wang, Hongbo Yu. How to Break MD5 and Other Hash Functions. Shandong
University, Jinan 250100, China. 2004.
[10] Antoine Joux, Florent Chaveaud. Differential Collisions in SHA-0. Centre d´Électronique
de l´Armament. France. 2004.
[11] S. Halevi, H. Krawczyk. Strengthening Digital Signatures via Randomized Hashing. CFRG.
Mayo 2005.
[12] Philippe Oechslin. Making a Faster Cryptanalytic Time-Memory Trade-Off. LASEC. 2003.
[13] Martin [Link]. A Cryptanalytic Time-Memory Trade-Off. IEEE Tansactions on
Information Theory. 1980.
[14] Ernesto Cuadros Vargas. Aplicaciones Multi Hebras. Arequipa – Perú. Octubre 2001.
[15] José Miguel Alonso. Programación de aplicaciones paralelas con MPI. Enero 1997.
[16] NVIDIA CUDA Compute Unified Device Architecture Programming Guide v2.0.
Septiembre 2008.
[17] Paul C et All, Parallel Collision Search with Application to Hash Functions and Discrete
Logarithms, Conference on Computer and Communications Security, ACM 2004
[18] Arjen Lenstra, Xiaoyun Wang, Benne de Weger. Colliding X.509 Certificates, Cryptology
ePrint Archive Report 2005/067, 1 Mar 2005, revised 6 May 2005. Retrieved July 27, 2008.
[19] [Link] Accessed 26 April 2010
View publication stats
