Openwall GNU/*/Linux - a small security-enhanced Linux distro for servers
[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Date: Fri, 8 Feb 2013 16:35:31 -0600
From: "jfoug" <jfoug@....net>
To: <john-users@...ts.openwall.com>
Subject: RE: Cracking SHA1 with some knowledge of password

From: Lex Par [mailto:ziptied@...il.com] 
>This might be a silly question, but why is there a 55 byte max?


Not a silly question at all.  

the short answer:
the 19 byte limit (in the format I provided), is due to requirements from
the optimizations that are being used.


The full answer:
SHA1 (and MD4/MD5, etc), all work on 64 byte blocks. However, there are 9
'extra' bytes needed.  The bit (full byte) right after the data being
encrypted is set to a 1 (so that byte gets set to a 0x80). Then the last 8
bytes of the last block (there can be more than 1 block), is set to hold the
number of bits being encrypted, as an 8 byte integer value.  Thus to make
things fit into 1 SHA block, you can have 55 bytes of password, followed a
single byte 0x80. Then there are still 8 bytes left, which is just enough to
place the length of the bit stream.   Anything over 55 bytes, will not fit
into a single SHA1 buffer.  Encrypting 56 bytes with SHA1, requires 128
bytes of buffer (2 64 byte buffers) to be encrypted.

Within our SSE code in the dynamic format we can only encrypt a single
block.  More 'can' be encrypted, but causes more code, and another full SHA1
on that block. This extra code, slows down most 'common' searches for
passwords.  It is very uncommon, for passwords to go past this 55 byte
threshold, thus we have made an assumption that only a single block will be
allowed, which removes this extra code overhead.  If you really need to do
passwords longer than this, then it is best to leave this format as is (with
19 char password max), and then make another format, that uses the dynamic
flag:  MGF_NOTSSE2Safe   This will force that format to NOT use SSE, but
revert to using slower OpenSSL library to do the SHA1.  That will allow up
to 96 (or 125??) bytes to be in the password.  So, if there are 36 bytes
used, you can for sure handle up to 60 byte passwords.  However, It would be
best to ONLY use that format to check passwords between 20 and 60 bytes,
using the faster version to process passwords from 0 to 19 bytes long.  In
real world situations, 19 byte passwords make up almost ALL of them.  there
are a few that go longer than that (often these longer passwords ARE the
high value accounts).

Jim.

Powered by blists - more mailing lists

Your e-mail address:

Confused about mailing lists and their use? Read about mailing lists on Wikipedia and check out these guidelines on proper formatting of your messages.