EN | ZH

# Hash Attack¶

Common hash function attack methods are mainly

• Violent attack: does not depend on any algorithm details, only related to the length of the hash value;
• Birthday Attack: The structure and any algebraic weak nature of the hash function are not used, depending only on the length of the message digest, which is the length of the hash value.
• Meet-In-The-Middle: It is a variant of a birthday attack. Instead of comparing hash values, it compares intermediate variables. This type of attack is mainly used to attack Hash schemes with a packet chain structure.
• Password analysis: Depends on the design shortcomings of specific algorithms.

## violent attack¶

HashCat tool can be said to be the best CPU and GPU-based cracking Hash software, the related links are as follows

[HashCat official website] (http://www.hashcat.net/hashcat/)

[HashCat Simple to use] (http://www.freebuf.com/sectool/112479.html)

## hash length extension attacks¶

### Introduction¶

The basic definition is as follows, from [Wikipedia] (https://en.wikipedia.org/wiki/%E9%95%BF%E5%BA%A6%E6%89%A9%E5%B1%95%E6% 94% BB% E5% 87% BB).

Hash Length Extension Attacks are pointers to certain cryptographic hash functions that allow additional information. This attack applies to all hash functions that take the H(key ∥ message) construct in the case where the length of the message and the key is known. Algorithms based on the Merkle–Damgård constructs such as MD5 and SHA-1 show vulnerabilities to such attacks.

This type of hash function has the following characteristics

• The message padding method is similar. First, add a 1 after the message, then fill in a number of 0s until the total length is congruent with 448, and finally attach a 64-bit message length (before filling).
• Each link variable obtained will be used as the initial vector IV for the next execution of the hash function. In the last block, the corresponding link variable will be converted to a hash value.

The following conditions should be met during a general attack.

• We know the length of the key, if you don't know, you need to burst it out.
• We can control the message of the message.
• We already know the hash value of a message containing a key.

So we can get a pair (messge, x) to satisfy x = H (key ∥ message) although we are not sure about the contents of the key.

### Attack principle¶

Here we can assume that we know the hash value of hash(key+s), where s is known, then it will be filled when it is calculated. Then we can first get the key+s extended by key+s, ie

Then if we attach a part of the information extra after the now, ie

When you go to calculate the hash value,

1. The extra is filled until the condition is met.
2. Calculate the link variable IV1 corresponding to now, and we already know the hash value of this part, and the algorithm that the link variable produces the hash value is reversible, so we can get the link variable.
3. The hash algorithm is performed on the extra part according to the obtained link variable IV1, and the hash value is returned.

So now that we know the hash value of the first part, and we also know the value of extra, then we can get the last hash value.

And before we said that we can control the value of the message. So in fact, s, padding, extra, we can all control. So we can naturally find the corresponding (message, x) to satisfy x = hash (key | mesage).

### Examples¶

It seems that most of them are inside the web, and I don't know much about the web. I will not give examples for the time being.

### Tools¶

Please refer to the readme on github for how to use it.

## hash algorithm is incorrectly designed¶

Some custom hash algorithms may be reversible.

### Hashinator¶

The logic of the topic is very simple. Pick a password from a well-known password dictionary "rockyou" and use a variety of hash algorithms to randomly hash 32 rounds. We need to crack the original password from the final hash result.

#### Analysis¶

The hash algorithms used in the title are: md5, sha1, blake, scrypt. The key code is as follows:

    password = self.generate_password()     # from rock_you.txt

Hash_rounds = self.generate_rounds() # Generate the order in which the hash algorithm is executed


1. The program first randomly extracts a password from rockyou.txt as the encrypted plaintext.
2. Then generate a salt of length 128 - len(password) based on the length of the extracted password.
3. Extract from the four hash algorithms listed above to form 32 rounds of hash operations.
4. Calculate the last password_hash given to us based on the previously obtained password, salt.

Obviously, we can't complete the problem by the inverse hash algorithm. We know all the possible plaintexts, first considering whether we can complete the exhaustion by constructing a rainbow table. But notice that in the generate_salt() function, the length combination of salt and password exceeds the length of 128 bytes and is annotated.

    msize = 128 # f-you hashcat :D


So, can only helplessly give up.

In that case, there is only one possibility, that is, the algorithm is reversible. Looking at the concrete implementation of the calculate_hash() function, you can find the following suspicious code:

for i in range(len(hash_rounds)):

interim_salt = xor(interim_salt, hash_rounds[-1-i](interim_hash))

interim_hash = xor(interim_hash, hash_rounds[i](interim_salt))

final_hash = interim_salt + interim_hash


Reorganize the information we know: 1. There are 32 rounds stored in hash_rounds, which is the hash function handle to be used in each round. 2. final_hash is the last hash result for us. 3. The contents of hash_rounds will also be printed to us after generation. 4. We want to get the values of interim_salt and interim_hash in the first round. 5. interim_salt and interim_hash are both 64bytes in length.

A closer look at the calculations of interim_salt and interim_hash reveals that it is reversible.

$$interim_hash_1 = interim_hash_2 \oplus hash_roundsi$$

In this line of code, we know $interim\_hash_1$ and $interim\_salt_3$, so we can get the value of $interim\_hash_2$, and $interim\_hash_2$ is the last round of interim_hash. By pushing back 32 times in this way, you can get the initial password and salt.

The specific decryption script is:

import
import hashlib

import socket

import socketserver

import struct

import time

# import pyscrypt

from base64 import b64encode, b64decode

from pwn import *

def md5(bytestring):

return hashlib.md5(bytestring).digest()

def sha(bytestring):

return hashlib.sha1(bytestring).digest()

def blake(bytestring):

return hashlib.blake2b(bytestring).digest()

def scrypt(bytestring):

l = int(len(bytestring) / 2)

salt = bytestring[:l]

p = bytestring[l:]

return hashlib.scrypt(p, salt=salt, n=2**16, r=8, p=1, maxmem=67111936)

# return pyscrypt.hash(p, salt, 2**16, 8, 1, dkLen=64)

def xor(s1, s2):

return b''.join([bytes([s1[i] ^ s2[i % len(s2)]]) for i in range(len(s1))])

def main():

# io = socket.socket (family = socket.AF_INET)
# io.connect ((&#39;47.88.216.38&#39;, 20013))
io = remote (&#39;47 .88.216.38 &#39;, 20013)
print (io.recv (1000))
ans_array = bytearray()

while True:

buf = io.recv (1)
if buf:

ans_array.extend(buf)

if buf == b'!':

break

password_hash_base64 = ans_array[ans_array.find(b"b'") + 2: ans_array.find(b"'\n")]

method_bytes = ans_array[

ans_array.find(b'used:\n') + 6 : ans_array.find(b'\nYour')

]

methods = method_bytes.split(b'\n')

methods = [bytes(x.strip(b'- ')).decode() for x in methods]

print(methods)

for pos, neg in zip(methods, methods[::-1]):

'''

interim_salt = xor(interim_salt, hash_rounds[-1-i](interim_hash))

interim_hash = xor(interim_hash, hash_rounds[i](interim_salt))

'''

in_hash = xor(in_hash, eval("{}(in_salt)".format(neg)))

in_salt = xor(in_salt, eval("{}(in_hash)".format(pos)))

print(in_hash, in_salt)

print(in_hash[-20:])

io.interactive ()
main()


#### Original hash algorithm¶

import
import hashlib

import socket

import socketserver

import struct

import time

# import pyscrypt

from base64 import b64encode

def md5(bytestring):

return hashlib.md5(bytestring).digest()

def sha(bytestring):

return hashlib.sha1(bytestring).digest()

def blake(bytestring):

return hashlib.blake2b(bytestring).digest()

def scrypt(bytestring):

l = int(len(bytestring) / 2)

salt = bytestring[:l]

p = bytestring[l:]

return hashlib.scrypt(p, salt=salt, n=2**16, r=8, p=1, maxmem=67111936)

# return pyscrypt.hash(p, salt, 2**16, 8, 1)

def xor(s1, s2):

return b''.join([bytes([s1[i] ^ s2[i % len(s2)]]) for i in range(len(s1))])

class HashHandler (socketserver.BaseRequestHandler):

welcome_message = """

Welcome, young wanna-be Cracker, to the Hashinator.

To prove your worthiness, you must display the power of your cracking skills.

The test is easy:

1. We send you a password from the rockyou list, hashed using multiple randomly chosen algorithms.

2. You crack the hash and send back the original password.

As you already know the dictionary and won't need any fancy password rules, {} seconds should be plenty, right?

"""

hashes = [md5, sha, blake, scrypt]

timeout = 10

total_rounds = 32

def handle(self):

self.request.sendall(self.welcome_message.format(self.timeout).encode())

Hash_rounds = self.generate_rounds() # Generate the order in which the hash algorithm is executed

self.generate_delay()

self.request.sendall("Rounds used:\n".encode())

test_rounds = []

for r in hash_rounds:

test_rounds.append(r)

for r in hash_rounds:

self.request.sendall("- {}\n".format(r.__name__).encode())

self.request.settimeout(self.timeout)

try:

response = self.request.recv(1024)

self.request.sendall("Congratulations! You are a true cracking master!\n".encode())

self.request.sendall("Welcome to the club: {}\n".format(flag).encode())

return

except socket.timeout:

pass

rand = struct.unpack("I", os.urandom(4))

lines = 14344391 # size of rockyou

line = rand % lines

f = open('rockyou.txt', 'rb')

for i in range(line):

def generate_salt(self, p):

msize = 128 # f-you hashcat :D

salt_size = msize - len(p)

return os.urandom(salt_size)

def generate_rounds(self):

rand = struct.unpack("Q", os.urandom(8))

rounds = []

for i in range(self.total_rounds):

rounds.append(self.hashes[rand % len(self.hashes)])

rand = rand &gt;&gt; 2
return rounds

for i in range(len(hash_rounds)):

interim_salt = xor(interim_salt, hash_rounds[-1-i](interim_hash))

interim_hash = xor(interim_hash, hash_rounds[i](interim_salt))

'''

interim_hash = xor(

interim_hash,

hash_rounds[i](

xor(interim_salt, hash_rounds[-1-i](interim_hash))

)

)

'''

final_hash = interim_salt + interim_hash

return final_hash

def generate_delay(self):

rand = struct.unpack("I", os.urandom(4))

time.sleep(rand / 1000000000.0)

PORT = 1337

HOST = '0.0.0.0'

flag = ""

with open("flag.txt") as f:

def main():

server = ThreadedTCPServer ((HOST, PORT), HashHandler)