Making a Higher Hit Ratio Cryptanalytic Time-Memory Trade-Off Attack on Passwords

ZOU Jing; LIN Dongdai; HAO Chunhui; LI Zhenqi; WANG Wenhao; LU Yao

Article Contents

Article Navigation > Chinese Journal of Electronics > 2013 > 22(4): 671-676

ZOU Jing, LIN Dongdai, HAO Chunhui, et al., “Making a Higher Hit Ratio Cryptanalytic Time-Memory Trade-Off Attack on Passwords,” Chinese Journal of Electronics, vol. 22, no. 4, pp. 671-676, 2013,

Citation:

ZOU Jing, LIN Dongdai, HAO Chunhui, et al., “Making a Higher Hit Ratio Cryptanalytic Time-Memory Trade-Off Attack on Passwords,” Chinese Journal of Electronics, vol. 22, no. 4, pp. 671-676, 2013,

ZOU Jing, LIN Dongdai, HAO Chunhui, et al., “Making a Higher Hit Ratio Cryptanalytic Time-Memory Trade-Off Attack on Passwords,” Chinese Journal of Electronics, vol. 22, no. 4, pp. 671-676, 2013,

Citation:

PDF( 211 KB)

Making a Higher Hit Ratio Cryptanalytic Time-Memory Trade-Off Attack on Passwords

ZOU Jing^{1,2,3
,},
LIN Dongdai¹,
HAO Chunhui^4,2,3,
LI Zhenqi^2,5,
WANG Wenhao^1,2,
LU Yao^1,2

1.
State Key Laboratory of Information Security, Institute of Information Engineering, Chinese Academy of Sciences, Beijing 100093, China;
2.
Graduate University of Chinese Academy of Sciences, Beijing 100190, China;
3.
Huaiyin Normal University, Huai'an 223300, China;
4.
Laboratory of Complex Systems and Intelligence Science, Institute Automation, Chinese Academy of Sciences, Beijing 100190, China;
5.
Institute of Software, Chinese Academy of Sciences, Beijing 100190, China

Funds: This work is supported by the National Basic Research Program of China (973 Program) (No.2011CBC302400), the National Natural Science Foundation of China (No.60970152), and the Young Teacher's Fund Project of Huaiyin Normal University (No.07HSQN020).

More Information

Corresponding author: ZOU Jing, LIN Dongdai, HAO Chunhui, LI Zhenqi, WANG Wenhao, LU Yao
Received Date: 2012-02-01
Rev Recd Date: 2013-02-01
Publish Date: 2013-09-25

Abstract

Abstract

Most of implementations of the cryptanalytic time-memory trade-off attacks such as Hellman's original method, Rivest's distinguished points cracking and Oechslin's rainbow attack are also considered as an exhaustive attack to passwords in a limited length range on a certain charset. However, the distributions of structures and strings making up real human memorable passwords do not appear random. Based upon these, we propose a method to generate passwords in those cryptanalytic timememory trade-off methods. It achieves a higher hit ratio in attacking actual passwords and reduces search space drastically with requirement of only a little extra memory. It makes time-memory trade-off more practical. Even to attack long length passwords, the results of experiments show that our approach has a higher hit ratio compared with Oechslin's method. In addition, this method can be used in the distributed and parallel attack.
- Time-memory trade-off,
- Cryptanalysis,
- High hit ratio

FullText(HTML)

References(20)

References

S. Alexander, “Password protection for modern operating systems”,h ttp://USENIXusenix.org/publications/login/2004-06/p dfs/alexander.pdf, 2004.

K. Helkala, E. Snekkenes, “Password generation and searchs pace reduction”, Journal of Computers, Vol.4, No.7, pp.663-6 69, 2009.

A. Narayanan, V. Shmatikov, “Fast dictionary attacks on passwordsu sing time-space tradeoff”, Proc. of ACM Conference on Computer and Communications Security, Alexandria, Virginia,U SA, pp.364-372, 2005.

S. Marechal, “Advances in password cracking”, Proc. of SSTIC2 007, J. Compute, Vol.2008, No.4, pp.73-81, 2008.

M. Weir, S. Aggarwal, B. de Medeiros, B. Glodek, “Passwordc racking using probabilistic context-free grammars”, Proc. ofI EEE Symposium on Security and Privacy, pp.391-405, 2009.

M. Weir, S. Aggarwal, M. Collins, H. Stern, “Testing metricsf or password creation policies by attacking large sets of revealedp asswords”, Proc. of CCS, Chicago, Illinois, USA, pp.162-174,2 010.

M.E. Hellman, “A cryptanalytic time-memory trade-off”, IEEET ransactions on Information Theory, Vol.IT, No.26, pp.401-4 06, 1980.

D. Denning, Cryptography and Data Security, Addison-Wesley Publishing Company, Boston, MA, USA, pp.100, 1982.

P. Ochslin, “Making a faster cryptanalytic time-memory tradeoff”, Proc. of Advances in Cryptology, Santa Barbara, California,U SA, Vol.2729 of Lecture Notes in Computer Science,p p.617-630, 2003.

G. Avoine, P. Junod, P. Ochslin, “Time-memory tradeoffs:f alse alarm detection using checkpoints”, Proc. of INDOCRYPT,S pringer, Heidelberg, Vol.3797, pp.183-196, 2005.

M. Agren, T. Johansson, M. Hell, “Improving the rainbow attackb y reusing colours”, Proc. of CANS2009, LNCS 5888,p p.362-378, 2009.

A. Biryukov, A. Shamir, D. Vagner, “Real time cryptanalysis ofA 5/1 on a PC”, Proc. of Fast Software Encryption, New York,U SA, Vol.1978 of Lecture Notes in Computer Science, pp.1-18,2 000.

S. Zhu, “Rainbowcrack-crack hashes with rainbow tables”,h ttp://project-rainbowcrack.com, Retrieved 2011.

M.D. Amico, P. Michiardi, Y. Roudier, “Password strength: Ane mpirical analysis”, Proc. of IEEE INFOCOM, 2010.

R. Morris, K. Thompson, “Password security: A case history”, Commun. ACM, Vol.22, No.11, pp.594-597, 1979.

D.V. Klein, “Foiling the cracker: A survey of, and improvementst o, password security”, Proc. of UNIX Security Workshop,1 990.

E.H. Spafford, “Obeserving reusable password choices”, Proc. of the 3rd Security Symposium, Usenix, pp.299-312, 1992.

A. Forget, S. Chiasson, P.C.V. Oorschot, R. Biddle, “Improvingt ext passwords through persuasion”, Proc. of Symposium onU sable Privacy and Security (SOUPS), Pittsburgh, PA USA,2 008.

J. Yan, A. Blackwell, R. Anderson, A. Grant, “Password memorability and security: Empirical results”, IEEE Security and Privacy Magazine, Vol.2, No.5, pp.25-31, 2004.

I. Jermyn, A. Mayer, F. Monrose, M.K. Reiter, A.D. Rubin,“The design and analysis of graphical passwords”, Proc. ofU SENIX Security Symposium, Washington, D.C., USA, 1999.

Relative Articles

Supplements(0)

Cited By

Proportional views