# CryptoCTF 2021 - Salt and Pepper

> Salt and Pepper, Salty and Spicy! Can we attack these unnormalized served foods?
>
> nc 02.cr.yp.toc.tf 28010

:::spoiler salt_pepper.py

#!/usr/bin/env python3

from hashlib import md5, sha1
import sys
from secret import salt, pepper
from flag import flag

assert len(salt) == len(pepper)	== 19
assert md5(salt).hexdigest()	== '5f72c4360a2287bc269e0ccba6fc24ba' 
assert sha1(pepper).hexdigest()	== '3e0d000a4b0bd712999d730bc331f400221008e0' 


def auth_check(salt, pepper, username, password, h):
	return sha1(pepper + password + md5(salt + username).hexdigest().encode('utf-8')).hexdigest() == h

def die(*args):
	pr(*args)
	quit()

def pr(*args):
	s = " ".join(map(str, args))
	sys.stdout.write(s + "\n")
	sys.stdout.flush()

def sc():
	return sys.stdin.readline().strip()

def main():
	border = "+"
	pr(border*72)
	pr(border, "  welcome to hash killers battle, your mission is to login into the ", border)
	pr(border, "  ultra secure authentication server with provided information!!    ", border)
	pr(border*72)

	USERNAME = b'n3T4Dm1n'
	PASSWORD = b'P4s5W0rd'

	while True:
		pr("| Options: \n|\t[L]ogin to server \n|\t[Q]uit")
		ans = sc().lower()
		if ans == 'l':
			pr('| send your username, password as hex string separated with comma: ')
			inp = sc()
			try:
				inp_username, inp_password = [bytes.fromhex(s) for s in inp.split(',')]
			except:
				die('| your input is not valid, bye!!')
			pr('| send your authentication hash: ')
			inp_hash = sc()
			if USERNAME in inp_username and PASSWORD in inp_password:
				if auth_check(salt, pepper, inp_username, inp_password, inp_hash):
					die(f'| Congrats, you are master in hash killing, and it is the flag: {flag}')
				else:
					die('| your credential is not valid, Bye!!!')
			else:
				die('| Kidding me?! Bye!!!')
		elif ans == 'q':
			die("Quitting ...")
		else:
			die("Bye ...")

if __name__ == '__main__':
	main()

:::

## 分析
まず、salt_pepper.pyを読みます。

初めに、usernameとpasswordを16進数表記にしてカンマ区切りにしたものを入力させられます。

inp = sc()
try:
	inp_username, inp_password = [bytes.fromhex(s) for s in inp.split(',')]
except:
    die('| your input is not valid, bye!!')

# ------------------------------------------------------

if USERNAME in inp_username and PASSWORD in inp_password:
	if auth_check(salt, pepper, inp_username, inp_password, inp_hash):
		die(f'| Congrats, you are master in hash killing, and it is the flag: {flag}')
	else:
		die('| your credential is not valid, Bye!!!')

これらはそれぞれ、

USERNAME = b'n3T4Dm1n'
PASSWORD = b'P4s5W0rd'

を部分文字列に含んでいる必要があります。

次にハッシュの入力を求められます。このハッシュが正しければ、flagがもらえるようです。どのようなハッシュを入力すればよいかを調べるために`auth_check()`関数を見ます。

assert len(salt) == len(pepper)	== 19
assert md5(salt).hexdigest()	== '5f72c4360a2287bc269e0ccba6fc24ba' 
assert sha1(pepper).hexdigest()	== '3e0d000a4b0bd712999d730bc331f400221008e0' 


def auth_check(salt, pepper, username, password, h):
	return sha1(pepper + password + md5(salt + username).hexdigest().encode('utf-8')).hexdigest() == h

`md5(salt)`と`sha1(pepper)`の値が分かっていますが、`salt`と`pepper`の値は不明です。この状態から、`sha1(pepper + password + md5(salt + username).hexdigest().encode('utf-8')).hexdigest()`の値を入力しなければならないようです。

まず前提として、md5やsha1は一方向関数です。そのため、有名な値とかでもない限り逆変換は厳しいです。一応試せるものはすべて試して可能性を潰しましたが、`md5(salt), sha1(pepper)`の値から`salt, pepper`の値を得ることはできなかったです。

## Length Extension Attack

ではどうすればハッシュの値を得ることができるのでしょうか。

今回は`md5(salt), sha1(pepper)`の値が分かっていることから、**Length Extension Attack**が使えそうです。

Length Extension Attackの分かりやすい記事はこちら
- https://ptr-yudai.hatenablog.com/entry/2018/08/28/205129
- https://www.slideshare.net/trmr105/katagaitai-ctf-5-crypto

かいつまんで言えば、$H$をハッシュ関数として、$H(m1)$の値がわかっている時に、$H(m1+m2)$の値を求める攻撃です。(正確には、$H(m1+padding+m2)$)

Merkle–Damgård 構成法に基づいて作られているハッシュ関数にはこの攻撃が使えて、MD5やSHA-1もその中の1つです。

よって、今回はLength Extension Attackによって`md5(salt)`の値から`md5(salt+username)`の値を求め、そこから更に`sha1(pepper+password+md5(salt+username))`の値を求めればハッシュが作れます。

ただし、上の記事の方法をそのまま適用することはできません。

なぜなら、MD5やSHA-1はハッシュの計算をする前にpadding処理を行うため、厳密に言えば`md5(salt)`は実質`salt+(paddingされた文字)`のハッシュであるからです。従って、何も考えずにLength Extensionをすると、ハッシュ値が`md5(salt+padding+username)`によるものになってしまいます。SHA-1についてもMD5と同様のpadding処理が行われるため、少し工夫が必要です。

## 解法
そこで、もう一度ソースコードを眺めていくと、`inp_username`と`inp_password`には、`USERNAME, PASSWORD`さえ含まれていればいい、ということが使えそうな気がしてきます。

具体的には、初めの入力には、

(md5で本来paddingされる予定である文字列)+USERNAME,(sha1で本来paddingされる予定である文字列)+PASSWORD

を入力します。そうすれば、そのままLength Extension Attackを行うことで手元でサーバー側で作られるハッシュと同じものが作れます。

ただし、更に注意する点があります。それはやはりpaddingです。

MD5やSHA-1は、引数によって与えられる文字列長によってpaddingされる文字列が決まります。例えばMD5の場合、サーバー側では`(md5で本来paddingされる予定である文字列)+USERNAME`によってpaddingされる文字列が決まるのですが、こちら側では`USERNAME`の長さによってpaddingされる文字列が決まってしまいます。

よって、Length Extensionをする際には、サーバー側でpaddingされる文字列と同じ文字列を初めにpaddingする様に実装をいじってハッシュの計算をしなければなりません。

自分はここで大分ハマりました...

実装にあたっては、MD5とSHA-1をいじる必要があるので、どちらの実装も持ってこなければなりません。MD5に関しては上の記事を~~丸パク~~参考にし、SHA-1に関しては[Pythonのhashlibの内部実装っぽいもの](https://github.com/TheAlgorithms/Python/blob/master/hashes/sha1.py)を見つけてきて参考にして実装しました。

本番に書いたコードがあまりにも汚かったので少し手直ししました。(それでもめちゃくちゃですが...)

解答コード：https://gist.github.com/siro53/6f6761792e1bb8b09257c6963579a03e

# 感想
md5とsha1の2回もLength Extensionさせられて辛かった