We are given a linux binary that emulates the ssh login requiring a password:

$ file crackme 
crackme: ELF 64-bit LSB executable, x86-64, version 1 (SYSV), statically linked, BuildID[sha1]=92ef00b31d91a827a5aed6b0fe03fe38fe20fb4d, stripped
$ ./crackme 
root@localhost's password: bla
Permission denied (password).
$ objdump -d crackme | wc -l
15809

When running objdump on it we can see obfuscation being used. The control flow graph is huge:
Instead of diving into the assembly and wasting time trying to figure out what is happening behind the obfuscation it proved useful to do a side-channel analysis using the number of instructions.

$ pin -t inscount0 -o out -- ./crackme ; cat out
root@localhost's password: a
Permission denied (password).
Count 715821
$ pin -t inscount0 -o out -- ./crackme ; cat out
root@localhost's password: b
Permission denied (password).
Count 716328
$ pin -t inscount0 -o out -- ./crackme ; cat out
root@localhost's password: c
Permission denied (password).
Count 716835
$ bc -lq
716328 -715821
507
716835 - 716328
507

Interesting, let's check all the ascii characters using a script:

$ python bf.py 
Input [!] -> [717933] delta [507]
Input ["] -> [718440] delta [507]
Input [#] -> [718947] delta [507]
Input [$] -> [719454] delta [507]
Input [%] -> [719961] delta [507]
Input [&] -> [720468] delta [507]
Input ['] -> [720975] delta [507]
Input [(] -> [721482] delta [507]
Input [)] -> [721989] delta [507]
Input [*] -> [722496] delta [507]
Input [+] -> [723003] delta [507]
Input [,] -> [723510] delta [507]
Input [-] -> [724017] delta [507]
Input [.] -> [724524] delta [507]
Input [/] -> [725031] delta [507]
Input [0] -> [725538] delta [507]
Input [1] -> [726045] delta [507]
Input [2] -> [726552] delta [507]
Input [3] -> [727059] delta [507]
Input [4] -> [727566] delta [507]
Input [5] -> [728073] delta [507]
Input [6] -> [728580] delta [507]
Input [7] -> [729087] delta [507]
Input [8] -> [729594] delta [507]
Input [9] -> [730101] delta [507]
Input [:] -> [730608] delta [507]
Input [;] -> [731115] delta [507]
Input [<] -> [731622] delta [507]
Input [=] -> [732129] delta [507]
Input [>] -> [732636] delta [507]
Input [?] -> [733143] delta [507]
Input [@] -> [733650] delta [507]
Input [A] -> [734157] delta [507]
Input [B] -> [734664] delta [507]
Input [C] -> [735171] delta [507]
Input [D] -> [735678] delta [507]
Input [E] -> [736185] delta [507]
Input [F] -> [736692] delta [507]
Input [G] -> [737199] delta [507]
Input [H] -> [701989] delta [-35210]
Input [I] -> [703653] delta [1664]
Input [J] -> [704160] delta [507]
Input [K] -> [704667] delta [507]
Input [L] -> [705174] delta [507]
Input [M] -> [705681] delta [507]
Input [N] -> [706188] delta [507]
Input [O] -> [706695] delta [507]
Input [P] -> [707202] delta [507]
Input [Q] -> [707709] delta [507]
Input [R] -> [708216] delta [507]
Input [S] -> [708723] delta [507]
Input [T] -> [709230] delta [507]
Input [U] -> [709737] delta [507]
Input [V] -> [710244] delta [507]
Input [W] -> [710751] delta [507]
Input [X] -> [711258] delta [507]
Input [Y] -> [711765] delta [507]
Input [Z] -> [712272] delta [507]
Input [[] -> [712779] delta [507]
Input [\] -> [713286] delta [507]
Input []] -> [713793] delta [507]
Input [^] -> [714300] delta [507]
Input [_] -> [714807] delta [507]
Input [`] -> [715314] delta [507]
Input [a] -> [715821] delta [507]
Input [b] -> [716328] delta [507]
Input [c] -> [716835] delta [507]
Input [d] -> [717342] delta [507]
Input [e] -> [717849] delta [507]
Input [f] -> [718356] delta [507]
Input [g] -> [718863] delta [507]
Input [h] -> [719370] delta [507]
Input [i] -> [719877] delta [507]
Input [j] -> [720384] delta [507]
Input [k] -> [720891] delta [507]
Input [l] -> [721398] delta [507]
Input [m] -> [721905] delta [507]
Input [n] -> [722412] delta [507]
Input [o] -> [722919] delta [507]
Input [p] -> [723426] delta [507]
Input [q] -> [723933] delta [507]
Input [r] -> [724440] delta [507]
Input [s] -> [724947] delta [507]
Input [t] -> [725454] delta [507]
Input [u] -> [725961] delta [507]
Input [v] -> [726468] delta [507]
Input [w] -> [726975] delta [507]
Input [x] -> [727482] delta [507]
Input [y] -> [727989] delta [507]
Input [z] -> [728496] delta [507]
Input [{] -> [729003] delta [507]
Input [|] -> [729510] delta [507]
Input [}] -> [730017] delta [507]
Input [~] -> [730524] delta [507]

If my assumption is correct the first letter should be “H”. Let's repeat the process for the next letters, but first since inscount1 is faster than inscount0 we use it instead. A modification to the script leads to this output:

$ python bf.py 
Trying input -> H
Trying input -> H4
Trying input -> H4P
Trying input -> H4PP
Trying input -> H4PPY
Trying input -> H4PPY_
Trying input -> H4PPY_C
Trying input -> H4PPY_C0
Trying input -> H4PPY_C0D
Trying input -> H4PPY_C0DE
Trying input -> H4PPY_C0DEG
Trying input -> H4PPY_C0DEGa
Trying input -> H4PPY_C0DEGaT
Trying input -> H4PPY_C0DEGaTE
Trying input -> H4PPY_C0DEGaTE_
Trying input -> H4PPY_C0DEGaTE_2
Trying input -> H4PPY_C0DEGaTE_20
Trying input -> H4PPY_C0DEGaTE_201
Trying input -> H4PPY_C0DEGaTE_2014
Trying input -> H4PPY_C0DEGaTE_2014_
Trying input -> H4PPY_C0DEGaTE_2014_C
Trying input -> H4PPY_C0DEGaTE_2014_CU
Trying input -> H4PPY_C0DEGaTE_2014_CU_
Trying input -> H4PPY_C0DEGaTE_2014_CU_1
Trying input -> H4PPY_C0DEGaTE_2014_CU_1"
Traceback (most recent call last):
  File "bf.py", line 52, in <module>

Ah, almost worked but it hangs because of some reason. Let's investigate:

$ python bf.py 
Input [H4PPY_C0DEGaTE_2014_CU_1!] -> [53426] delta [-713]
Input [H4PPY_C0DEGaTE_2014_CU_1"] -> [45776] delta [-7650]
Input [H4PPY_C0DEGaTE_2014_CU_1#] -> [46477] delta [701]
Input [H4PPY_C0DEGaTE_2014_CU_1$] -> [45776] delta [-701]
Input [H4PPY_C0DEGaTE_2014_CU_1%] -> [52724] delta [6948]
Input [H4PPY_C0DEGaTE_2014_CU_1&] -> [62623] delta [9899]
Input [H4PPY_C0DEGaTE_2014_CU_1'] -> [45977] delta [-16646]
Input [H4PPY_C0DEGaTE_2014_CU_1(] -> [45730] delta [-247]
Input [H4PPY_C0DEGaTE_2014_CU_1)] -> [45729] delta [-1]
Input [H4PPY_C0DEGaTE_2014_CU_1*] -> [45977] delta [248]
Input [H4PPY_C0DEGaTE_2014_CU_1+] -> [45730] delta [-247]
Input [H4PPY_C0DEGaTE_2014_CU_1,] -> [46506] delta [776]
Input [H4PPY_C0DEGaTE_2014_CU_1-] -> [45977] delta [-529]
Input [H4PPY_C0DEGaTE_2014_CU_1.] -> [47056] delta [1079]
Input [H4PPY_C0DEGaTE_2014_CU_1/] -> [47110] delta [54]
Input [H4PPY_C0DEGaTE_2014_CU_10] -> [45840] delta [-1270]
Input [H4PPY_C0DEGaTE_2014_CU_11] -> [46473] delta [633]
Input [H4PPY_C0DEGaTE_2014_CU_12] -> [38563] delta [-7910]
Input [H4PPY_C0DEGaTE_2014_CU_13] -> [39030] delta [467]
Input [H4PPY_C0DEGaTE_2014_CU_14] -> [38985] delta [-45]
Input [H4PPY_C0DEGaTE_2014_CU_15] -> [45977] delta [6992]
Input [H4PPY_C0DEGaTE_2014_CU_16] -> [38567] delta [-7410]
Input [H4PPY_C0DEGaTE_2014_CU_17] -> [37877] delta [-690]
Input [H4PPY_C0DEGaTE_2014_CU_18] -> [37877] delta [0]
Input [H4PPY_C0DEGaTE_2014_CU_19] -> [38563] delta [686]
Input [H4PPY_C0DEGaTE_2014_CU_1:] -> [37877] delta [-686]
Input [H4PPY_C0DEGaTE_2014_CU_1;] -> [29361] delta [-8516]
Input [H4PPY_C0DEGaTE_2014_CU_1<] -> [29277] delta [-84]
Input [H4PPY_C0DEGaTE_2014_CU_1=] -> [28905] delta [-372]
Input [H4PPY_C0DEGaTE_2014_CU_1>] -> [28919] delta [14]
Input [H4PPY_C0DEGaTE_2014_CU_1?] -> [29228] delta [309]
Input [H4PPY_C0DEGaTE_2014_CU_1@] -> [27920] delta [-1308]
Input [H4PPY_C0DEGaTE_2014_CU_1A] -> [29325] delta [1405]
Input [H4PPY_C0DEGaTE_2014_CU_1B] -> [20943] delta [-8382]
Input [H4PPY_C0DEGaTE_2014_CU_1C] -> [20675] delta [-268]
Input [H4PPY_C0DEGaTE_2014_CU_1D] -> [20681] delta [6]
Input [H4PPY_C0DEGaTE_2014_CU_1E] -> [19623] delta [-1058]
Input [H4PPY_C0DEGaTE_2014_CU_1F] -> [19765] delta [142]
Input [H4PPY_C0DEGaTE_2014_CU_1G] -> [20682] delta [917]
Input [H4PPY_C0DEGaTE_2014_CU_1H] -> [27800] delta [7118]
Input [H4PPY_C0DEGaTE_2014_CU_1I] -> [20666] delta [-7134]
Input [H4PPY_C0DEGaTE_2014_CU_1J] -> [19743] delta [-923]
Input [H4PPY_C0DEGaTE_2014_CU_1K] -> [19766] delta [23]
Input [H4PPY_C0DEGaTE_2014_CU_1L] -> [14431] delta [-5335]
Input [H4PPY_C0DEGaTE_2014_CU_1M] -> [14494] delta [63]
Input [H4PPY_C0DEGaTE_2014_CU_1N] -> [19765] delta [5271]
Input [H4PPY_C0DEGaTE_2014_CU_1O] -> [14436] delta [-5329]
Input [H4PPY_C0DEGaTE_2014_CU_1P] -> [13415] delta [-1021]
Input [H4PPY_C0DEGaTE_2014_CU_1Q] -> [13438] delta [23]
Input [H4PPY_C0DEGaTE_2014_CU_1R] -> [13415] delta [-23]
Input [H4PPY_C0DEGaTE_2014_CU_1S] -> [13252] delta [-163]
Input [H4PPY_C0DEGaTE_2014_CU_1T] -> [13415] delta [163]
Input [H4PPY_C0DEGaTE_2014_CU_1U] -> [14254] delta [839]
Input [H4PPY_C0DEGaTE_2014_CU_1V] -> [9118] delta [-5136]
Input [H4PPY_C0DEGaTE_2014_CU_1W] -> [14248] delta [5130]
Input [H4PPY_C0DEGaTE_2014_CU_1X] -> [13253] delta [-995]
Input [H4PPY_C0DEGaTE_2014_CU_1Y] -> [9062] delta [-4191]
Input [H4PPY_C0DEGaTE_2014_CU_1Z] -> [13252] delta [4190]
Input [H4PPY_C0DEGaTE_2014_CU_1[] -> [8975] delta [-4277]
Input [H4PPY_C0DEGaTE_2014_CU_1\] -> [8961] delta [-14]
Input [H4PPY_C0DEGaTE_2014_CU_1]] -> [14254] delta [5293]
Input [H4PPY_C0DEGaTE_2014_CU_1^] -> [14235] delta [-19]
Input [H4PPY_C0DEGaTE_2014_CU_1_] -> [8964] delta [-5271]
Input [H4PPY_C0DEGaTE_2014_CU_1`] -> [8154] delta [-810]
Input [H4PPY_C0DEGaTE_2014_CU_1a] -> [8039] delta [-115]
Input [H4PPY_C0DEGaTE_2014_CU_1b] -> [5905] delta [-2134]
Input [H4PPY_C0DEGaTE_2014_CU_1c] -> [5932] delta [27]
Input [H4PPY_C0DEGaTE_2014_CU_1d] -> [5858] delta [-74]
Input [H4PPY_C0DEGaTE_2014_CU_1e] -> [5960] delta [102]
Input [H4PPY_C0DEGaTE_2014_CU_1f] -> [5905] delta [-55]
Input [H4PPY_C0DEGaTE_2014_CU_1g] -> [5869] delta [-36]
Input [H4PPY_C0DEGaTE_2014_CU_1h] -> [5332] delta [-537]
Input [H4PPY_C0DEGaTE_2014_CU_1i] -> [5264] delta [-68]
Input [H4PPY_C0DEGaTE_2014_CU_1j] -> [5267] delta [3]
Input [H4PPY_C0DEGaTE_2014_CU_1k] -> [5237] delta [-30]
Input [H4PPY_C0DEGaTE_2014_CU_1l] -> [3197] delta [-2040]
Input [H4PPY_C0DEGaTE_2014_CU_1m] -> [5227] delta [2030]
Input [H4PPY_C0DEGaTE_2014_CU_1n] -> [3211] delta [-2016]
Input [H4PPY_C0DEGaTE_2014_CU_1o] -> [1487] delta [-1724]
Input [H4PPY_C0DEGaTE_2014_CU_1p] -> [1780] delta [293]
Input [H4PPY_C0DEGaTE_2014_CU_1q] -> [3202] delta [1422]
Input [H4PPY_C0DEGaTE_2014_CU_1r] -> [2447] delta [-755]
Input [H4PPY_C0DEGaTE_2014_CU_1s] -> [2447] delta [0]
Input [H4PPY_C0DEGaTE_2014_CU_1t] -> [2447] delta [0]
Input [H4PPY_C0DEGaTE_2014_CU_1u] -> [1492] delta [-955]
Input [H4PPY_C0DEGaTE_2014_CU_1v] -> [65] delta [-1427]
Input [H4PPY_C0DEGaTE_2014_CU_1w] -> [765] delta [700]
Input [H4PPY_C0DEGaTE_2014_CU_1x] -> [723] delta [-42]
Input [H4PPY_C0DEGaTE_2014_CU_1y] -> [691] delta [-32]
Input [H4PPY_C0DEGaTE_2014_CU_1z] -> [633] delta [-58]
Input [H4PPY_C0DEGaTE_2014_CU_1{] -> [581] delta [-52]
Input [H4PPY_C0DEGaTE_2014_CU_1|] -> [103] delta [-478]
Input [H4PPY_C0DEGaTE_2014_CU_1}] -> [103] delta [0]
Input [H4PPY_C0DEGaTE_2014_CU_1~] -> [34] delta [-69]

When reverting to the slower inscount0 we get clean outputs and can continue the search:

$ python bf.py 
Trying input -> H4PPY_C0DEGaTE_2014_CU_1N
Trying input -> H4PPY_C0DEGaTE_2014_CU_1N_
Trying input -> H4PPY_C0DEGaTE_2014_CU_1N_K
Trying input -> H4PPY_C0DEGaTE_2014_CU_1N_K0
Trying input -> H4PPY_C0DEGaTE_2014_CU_1N_K0R
Trying input -> H4PPY_C0DEGaTE_2014_CU_1N_K0RE
Output different for password [H4PPY_C0DEGaTE_2014_CU_1N_K0RE4]
$ ./crackme 
root@localhost's password: H4PPY_C0DEGaTE_2014_CU_1N_K0RE4
SUCCESS

Done! Work smart! Here's the script:

#!/usr/bin/python
import os, pexpect, time
from subprocess import Popen,PIPE
 
pinpath="/ctf/TOOLS/pin/pin"
 
 
def try_list(lst):
        procs = {}
	ret_dict = {}
        for (idx, s) in enumerate(lst):
		out_file = s.encode('hex')
                p = Popen([pinpath, "-t", "inscount0", "-o", "tmp/" + out_file, "--", "./crackme"], stdout = PIPE, stdin = PIPE)
                procs[s] = p
		p.stdin.write(s + "\n")
 
	prev = 0
	show_delta = False
	delta = {}
        for (idx,s) in enumerate(lst):
                while procs[s].poll() is None:
                        time.sleep(0.5)
		if "denied" not in procs[s].stdout.read():
			print "Output different for password [%s]" % s
			exit(-1)
		out_file = s.encode('hex')
                output = open("tmp/" + out_file).read().split(" ")[1].strip()
		instr_count = int(output)
		if show_delta:
	                #print "Input [%s] -> [%s] delta [%s]" % (s, instr_count, instr_count - prev)
			delta[s] = instr_count - prev
		else:
			show_delta = True
		prev = instr_count
 
	for (idx,s) in enumerate(lst):
		if idx < 2:
			continue
		if delta[s] != delta[lst[idx-1]]:
			return s
 
prefix = ""
while True:
	lst = [prefix + chr(i) for i in range(32,127)]
	prefix = try_list(lst)
	print "Trying input -> %s" % prefix