Cracking SHA-1 derived passwords faster

Martyr

i could be wrong about the following, but so far i think all works well, atleast in theory, and a little experimenting..

Part of the process in SHA-1 involves expansion of the 16 word buffer to 80 words.

http://www.itl.nist.gov/fipspubs/fip180-1.htm

[PHP]b. For t = 16 to 79
let Wt = S1(Wt-3 XOR Wt-8 XOR Wt-14 XOR Wt-16).[/PHP]

3 main inputs which can be distinguished from each other are:

The 8-bits, at a specified index in the buffer.[EDIT:each character]
The end bit,(0x80) appended after all bytes in the buffer.
The number of bits stored in the buffer,usually at index 15.

To optimise a brute force attack on passwords created with SHA-1, follow the same pattern as attacking DES using Bit-or'ing of key schedules.

Take the first letter of the alphabet to be used in the crack, and create
1 pre-expanded buffer for each index up to max length of passwords to try.

Of course, this would require 10*320 bytes for just 1 character
if testing passwords up to 10 in length.

For demonstrations, just use 8, as this would take quite some time anyway, given something like 62 characters 0-9/A-Z/a-z in the alphabet being used.

still, up to 10, would be (62*10)*320 bytes, 198,400 KB - no worries about space

initially, the first buffer being passed to the main SHA-1 rounds will already
have the end bit and number of bits set.

then we take the first buffer of the first character, already processed through the expansion routine,and XOR these bits against the end bit/number of bits buffer,which has also been pre-processed through the expansion routine.

[PHP] for(length = 0 to maxlength, increase length)

for i = 0 to 79
a = charset_pre_expanded_buffers[length]
b = end_bits_and_other_chars

b ^= a
process_buffer = b
end for

hash = sha1(process_buffer)

if ( hash == hash_to_find )
print found
break
end if

end for[/PHP]
By eliminating the expansion, we can efficiently use SIMD instructions
in both desktop CPUs and Hardware (FPGA,ASIC) by avoiding the shifts/ors
required to complete bit rotations..somebody correct me if this is
already done in hardware!

there are still 2 more rotates for each round, but this may be avoidable also.
atleast there are 64 less rotates, and 128 less XORs to do now in a brute force attack

WPA-PSK cracking would probably benefit quite alot from any optimisations! such as cowpatty by johnny cache

EDIT:use an XOR, not OR as previously said..

Martyr

[PHP].686
.xmm
.model flat,stdcall

include <windows.inc>
include <stdio.inc>

includelib kernel32.lib
includelib crtdll.lib

print_block proto :dword
sha1_block_x86 proto :dword
pre_expand_buffer proto :dword,:dword

CStr macro pszText:REQ ; macro by Japheth
local szText
.const
szText db pszText,0
.code
exitm <offset szText>
endm

.data?


.data
sha_ctx_a dd 067452301h,0EFCDAB89h,098BADCFEh,010325476h,0C3D2E1F0h
sha_ctx_b dd 5 dup (0)

string db 64 dup (?)

string_1 db '11111111'
str_1_len equ $-string_1
db 64-str_1_len dup (0)

string_2 db str_1_len dup (0) ; here is space for string_1
string_2_start label dword
db '22222222'
str_2_len equ $-string_2_start
db 64-(str_1_len + str_2_len) dup (0)

end_and_bits db (str_1_len + str_2_len) dup (0) ; this is blank space for both strings
db 80h ; here is the end bit
db 60-((str_1_len + str_2_len)+1) dup (0) ; calculate how much space is left over
dd (str_1_len + str_2_len) * 8 ; number of bits
dd 0

align 16
w_buffer dd 80 dup (?)

align 16
buffer_1 dd 80 dup (?)

align 16
buffer_2 dd 80 dup (?)

align 16
buffer_3 dd 80 dup (?)

.code

start:
mov eax,dword ptr[end_and_bits+60]
bswap eax
mov dword ptr [end_and_bits+60],eax

invoke pre_expand_buffer,addr buffer_1,addr string_1
invoke pre_expand_buffer,addr buffer_2,addr string_2
invoke pre_expand_buffer,addr buffer_3,addr end_and_bits

; now our 3 buffers have been pre-expanded, to join them together
; just use an XOR, this would be done more efficiently in crack procedure.

lea esi,[buffer_3]
lea edi,[buffer_2]
lea ebp,[buffer_1]

xor ecx,ecx

xor_buffers:
movdqa xmm0,[esi+ecx] ; get end bit / number of bits data
movdqa xmm1,[esi+ecx+16]
movdqa xmm2,[esi+ecx+32]
movdqa xmm3,[esi+ecx+48]

pxor xmm0,[edi+ecx] ; xor against '22222222'
pxor xmm1,[edi+ecx+16]
pxor xmm2,[edi+ecx+32]
pxor xmm3,[edi+ecx+48]

pxor xmm0,[ebp+ecx] ; xor against '11111111'
pxor xmm1,[ebp+ecx+16]
pxor xmm2,[ebp+ecx+32]
pxor xmm3,[ebp+ecx+48]

movdqa [w_buffer+ecx],xmm0 ; save
movdqa [w_buffer+ecx+16],xmm1
movdqa [w_buffer+ecx+32],xmm2
movdqa [w_buffer+ecx+48],xmm3

add ecx,64
cmp ecx,320
jne xor_buffers

invoke sha1_block_x86,addr sha_ctx_a

invoke printf,CStr(<13,10,'Expected Hash: da71c2960a19596187f7294c3f03b0c882640e60'>)
invoke print_block,addr sha_ctx_a

invoke ExitProcess,0

sha1 macro dwa,dwb,dwc,dwd,dwe,dwx

mov edi,dwc
mov ebp,[w_buffer+dwx]

xor edi,dwd
add dwe,ebp

and edi,dwb
mov ebp,dwa

xor edi,dwd
rol ebp,5

add dwe,05a827999h
ror dwb,2

add dwe,edi
add dwe,ebp
endm

; ++++++++++++++++++++++++++++++++++++++++

sha2 macro dwa,dwb,dwc,dwd,dwe,dwx

mov edi,dwc
mov ebp,[w_buffer+dwx]

xor edi,dwd
add dwe,ebp

xor edi,dwb
mov ebp,dwa

add dwe,06ed9eba1h
rol ebp,5

add dwe,edi
ror dwb,2

add dwe,ebp
endm

; ++++++++++++++++++++++++++++++++++++++++

sha3 macro dwa,dwb,dwc,dwd,dwe,dwx

mov edi,dwc
mov ebp,dwc

and edi,dwd
or ebp,dwd

add dwe,08f1bbcdch
and ebp,dwb

ror dwb,1
or edi,ebp

ror dwb,1
add dwe,edi

mov ebp,[w_buffer+dwx]
mov edi,dwa

add dwe,ebp
rol edi,5

add dwe,edi
endm

; ++++++++++++++++++++++++++++++++++++++++

sha4 macro dwa,dwb,dwc,dwd,dwe,dwx

mov edi,dwc
mov ebp,[w_buffer+dwx]

xor edi,dwd
add dwe,ebp

xor edi,dwb
mov ebp,dwa

add dwe,0ca62c1d6h
rol ebp,5

add dwe,edi
ror dwb,2

add dwe,ebp
endm

sha1_block_x86 proc uses esi edi ebx sha1_ctx:dword

mov [esp-4],ebp
mov ebp,[sha1_ctx]

init_buffer:

mov eax,[ebp][0]
mov ebx,[ebp][4]
mov ecx,[ebp][8]
mov edx,[ebp][12]
mov esi,[ebp][16]

; =================================

sha1 eax, ebx, ecx, edx, esi, 00*04
sha1 esi, eax, ebx, ecx, edx, 01*04
sha1 edx, esi, eax, ebx, ecx, 02*04
sha1 ecx, edx, esi, eax, ebx, 03*04
sha1 ebx, ecx, edx, esi, eax, 04*04

sha1 eax, ebx, ecx, edx, esi, 05*04
sha1 esi, eax, ebx, ecx, edx, 06*04
sha1 edx, esi, eax, ebx, ecx, 07*04
sha1 ecx, edx, esi, eax, ebx, 08*04
sha1 ebx, ecx, edx, esi, eax, 09*04

sha1 eax, ebx, ecx, edx, esi, 10*04
sha1 esi, eax, ebx, ecx, edx, 11*04
sha1 edx, esi, eax, ebx, ecx, 12*04
sha1 ecx, edx, esi, eax, ebx, 13*04
sha1 ebx, ecx, edx, esi, eax, 14*04

sha1 eax, ebx, ecx, edx, esi, 15*04
sha1 esi, eax, ebx, ecx, edx, 16*04
sha1 edx, esi, eax, ebx, ecx, 17*04
sha1 ecx, edx, esi, eax, ebx, 18*04
sha1 ebx, ecx, edx, esi, eax, 19*04

; =================================

sha2 eax, ebx, ecx, edx, esi, 20*04
sha2 esi, eax, ebx, ecx, edx, 21*04
sha2 edx, esi, eax, ebx, ecx, 22*04
sha2 ecx, edx, esi, eax, ebx, 23*04
sha2 ebx, ecx, edx, esi, eax, 24*04

sha2 eax, ebx, ecx, edx, esi, 25*04
sha2 esi, eax, ebx, ecx, edx, 26*04
sha2 edx, esi, eax, ebx, ecx, 27*04
sha2 ecx, edx, esi, eax, ebx, 28*04
sha2 ebx, ecx, edx, esi, eax, 29*04

sha2 eax, ebx, ecx, edx, esi, 30*04
sha2 esi, eax, ebx, ecx, edx, 31*04
sha2 edx, esi, eax, ebx, ecx, 32*04
sha2 ecx, edx, esi, eax, ebx, 33*04
sha2 ebx, ecx, edx, esi, eax, 34*04

sha2 eax, ebx, ecx, edx, esi, 35*04
sha2 esi, eax, ebx, ecx, edx, 36*04
sha2 edx, esi, eax, ebx, ecx, 37*04
sha2 ecx, edx, esi, eax, ebx, 38*04
sha2 ebx, ecx, edx, esi, eax, 39*04

; =================================

sha3 eax, ebx, ecx, edx, esi, 40*04
sha3 esi, eax, ebx, ecx, edx, 41*04
sha3 edx, esi, eax, ebx, ecx, 42*04
sha3 ecx, edx, esi, eax, ebx, 43*04
sha3 ebx, ecx, edx, esi, eax, 44*04

sha3 eax, ebx, ecx, edx, esi, 45*04
sha3 esi, eax, ebx, ecx, edx, 46*04
sha3 edx, esi, eax, ebx, ecx, 47*04
sha3 ecx, edx, esi, eax, ebx, 48*04
sha3 ebx, ecx, edx, esi, eax, 49*04

sha3 eax, ebx, ecx, edx, esi, 50*04
sha3 esi, eax, ebx, ecx, edx, 51*04
sha3 edx, esi, eax, ebx, ecx, 52*04
sha3 ecx, edx, esi, eax, ebx, 53*04
sha3 ebx, ecx, edx, esi, eax, 54*04

sha3 eax, ebx, ecx, edx, esi, 55*04
sha3 esi, eax, ebx, ecx, edx, 56*04
sha3 edx, esi, eax, ebx, ecx, 57*04
sha3 ecx, edx, esi, eax, ebx, 58*04
sha3 ebx, ecx, edx, esi, eax, 59*04

; =================================

sha4 eax, ebx, ecx, edx, esi, 60*04
sha4 esi, eax, ebx, ecx, edx, 61*04
sha4 edx, esi, eax, ebx, ecx, 62*04
sha4 ecx, edx, esi, eax, ebx, 63*04
sha4 ebx, ecx, edx, esi, eax, 64*04

sha4 eax, ebx, ecx, edx, esi, 65*04
sha4 esi, eax, ebx, ecx, edx, 66*04
sha4 edx, esi, eax, ebx, ecx, 67*04
sha4 ecx, edx, esi, eax, ebx, 68*04
sha4 ebx, ecx, edx, esi, eax, 69*04

sha4 eax, ebx, ecx, edx, esi, 70*04
sha4 esi, eax, ebx, ecx, edx, 71*04
sha4 edx, esi, eax, ebx, ecx, 72*04
sha4 ecx, edx, esi, eax, ebx, 73*04
sha4 ebx, ecx, edx, esi, eax, 74*04

sha4 eax, ebx, ecx, edx, esi, 75*04
sha4 esi, eax, ebx, ecx, edx, 76*04
sha4 edx, esi, eax, ebx, ecx, 77*04
sha4 ecx, edx, esi, eax, ebx, 78*04
sha4 ebx, ecx, edx, esi, eax, 79*04

mov ebp,[esp-4]

mov edi,[sha1_ctx]

add [edi][0],eax
add [edi][4],ebx
add [edi][8],ecx
add [edi][12],edx
add [edi][16],esi

ret
sha1_block_x86 endp

print_block proc uses esi edi ebx ctx:dword

mov esi,[ctx]

lodsd
xchg eax,edi
lodsd
xchg eax,ebx
lodsd
xchg eax,ecx
lodsd
xchg eax,edx
lodsd
xchg eax,edi

invoke printf,CStr(<13,10,'Computed Result: %08x%08x%08x%08x%08x',13,10>),eax,ebx,ecx,edx,edi

ret

print_block endp

pre_expand_buffer proc uses esi edi ebx dst:dword,src:dword

mov edi,[dst]
mov esi,[src]
xor ecx,ecx

init_buffer: ; convert bytes to big-endian format, stupid stuff.

mov eax,[esi+4*ecx]
mov ebx,[esi+4*ecx+4]

bswap eax
bswap ebx

mov [edi+4*ecx],eax
mov [edi+4*ecx+4],ebx

add ecx,2
cmp ecx,16
jne init_buffer

transform_buffer: ; now do the expansion of 16 32-bit words to 80

mov eax,[edi+4*ecx-3*4]
mov ebx,[edi+4*ecx-3*4+4]

xor eax,[edi+4*ecx-8*4]
xor ebx,[edi+4*ecx-8*4+4]

xor eax,[edi+4*ecx-14*4]
xor ebx,[edi+4*ecx-14*4+4]

xor eax,[edi+4*ecx-16*4]
xor ebx,[edi+4*ecx-16*4+4]

rol eax,1
rol ebx,1

mov [edi+4*ecx],eax
mov [edi+4*ecx+4],ebx

add ecx,2
cmp ecx,80
jne transform_buffer

ret
pre_expand_buffer endp

end start[/PHP]

C:\mkit>prep

Expected Hash: da71c2960a19596187f7294c3f03b0c882640e60
Computed Result: da71c2960a19596187f7294c3f03b0c882640e60

C:\mkit>

mick.fr

So what the results means ?

Martyr

mick.fr wrote:

So what the results means ?

nothing major.. just that for those who wish to crack SHA-1 derived passwords faster, they can increase the speed by roughly 150% using the method i describe.

i've not seen it done before, so..i assume its new thing to experiment with.

i tested 1 password cracking app attacking SHA-1, which did about 2.1 million k/s - openssl sha-1 on its own does about 3.2 million k/s

the sha-1 i tested with described method was doing 5.7 million k/s which is equivilant to speed of full MD5.

alot of people write it off as nothing, but i think its interesting, and remember, you saw it here first!

EDIT: i think david hulton, who compiled coWPAtty for FPGAs may be interested in this, because of the number of rounds required by WPA-PSK to compute a key.

i think its roughly 4096 rounds of SHA-1 for each key..hehe, any kind of speed increase would be welcome..

the main problem in hardware/SIMD i can say is bit-rotations.
these hash algorithms were all designed for little-endian 32-bit cpus which natively support bit-rotations.

so you need to do shifts/ors, which can take quite alot of time in pc desktops which aren't suitable of course.

it would be great to remove all bit-rotations, if its possible.

dlofnep

I think you've gone far and beyond my limited cryptology knowledge

Capt'n Midnight

http://en.wikipedia.org/wiki/Custom_hardware_attack#History

Cost-Optimized Parallel COde Breaker)
...
COPACOBANA costs about $10,000 to build and will recover a DES key in under 9 days on average

DES is not the same as SHA-1 but http://en.wikipedia.org/wiki/Sha-1 says "lowering the complexity required for finding a collision in SHA-1 to 2^63" and the http://www.copacobana.org/faq.html says No, any symmetric cipher with up to roughly 64 key bits can be attacked with COPACOBANA. Examples include CSA (Common Scrambling Algorithm) or GSM A5. Moreover, presumingly strong ciphers with a long theoretical key size can be broken if the number of required steps is less than 2^{64}. This can, for instance, be the case for ciphers with a weak key derivation function, e.g., AES with 8-character keys, etc...

So it's possible to get serious crunching hardware for less than some www.barryboys.co.uk spend on tarting up a Nissan Micra. I don't know how many days/weeks it would take to break SHA-1 but this just means you could get your answer in 2/3 thirds of the time.

Or you could buy more hardware and get the answer faster. But the thing to remember is how long does the information have to be kept for ? For live stock quotes, the answer is 15 minutes, because after that they are free. For satellite TV maybe a little longer. For your diary presumably you don't want it decrypted in your lifetime. So far Moores law says that processing power per dollar doubles ever 18 months ( or two years or something ). However algorithms improve too , not as predictably as Moores law and you'd have to factor that in too. Example if twenty years ago the best algorithm would take 100 years to crack on a top of the range computer, today it would take one year, using the same program on modern hardware. Factor in another factor of 10 for parallel processing / gpu / fgpa kit and algorithm improvements and that 100 years is now in the order of a month or two. Factor in a botnet and you could be talking next day

Breaking encrytion is slow and even modest tweaks are worth the hassle, and they all add up.

Martyr

i don't know of many applications that employ SHA-1 to generate passwords, but here are a few.

[PHP]MySQL SHA-1 (SHA-1(password)) (since 4.1, older algorithm is weaker)
LDAP Schema Base64(SHA-1(password))
Apache Base64(SHA-1(password)) (MD5Crypt used by default)[/PHP]

others?

some networking clients are written to use SHA-1 in authentication.
if a challenge is involved, just create a pre-expanded challenge separately, then XOR it against each new password.
we can create multiple buffers for multiple challenges/salts and its no problem generating new hashes based on same password.

HMAC-SHA-1 would be quicker to attack also, with just a different approach.
Rainbow tables are available for SHA-1, but not HMAC/challenges or salts.

Screaming Monkey

A presentation from Toorcon 07 on building a home encryption cracking FPGA he mentions COPACOBANA and the DES cracker from EFF, along with other random musings...

http://video.google.com/videoplay?docid=7695444172378347123&q=toorcon.org&pr=goog-sl

Martyr

don't mean to drag this thread up again, but i just wrote a little program to show the attack in practice, its very basic, which just displays seconds elapsed and the password (if found)

you can get C/ASM sources here
there are nasm/masm versions of the sha1 assembly.

also, some of you probably saw the FPGA SHA-1 cracker discussed on hackaday which can crack a 64-bit key in roughly a day.
very impressive.